Nancy's Studio.

JavaScript数据结构与算法学习

Word count: 2,167 / Reading time: 12 min
2019/07/05 Share

数组

添加、插入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var numbers = [0,1,2,3,4,5];
//向数组尾部添加
number.push(6);
number.push(7,8,9); //[0,1,2,3,4,5,6,7,8,9]
//插入元素到首位
for (var i = numbers.length; i >= 0; i--) {
numbers[i] = numbers[i-1];
}
numbers[0] = -1;
//或者用unshift()方法
numbers.unshift(-2);
numbers.unshift(-5,-4,-3); //[-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9]
//在任意位置添加元素(比如在位置5插入1,2,3)
splice(5,0,1,2,3) //因为在这里不删元素,所以第二个参数为零

删除元素

1
2
3
4
5
6
7
8
9
10
//删除末尾元素
numbers.pop();
//删除首位元素
for (var i = 0; i < numbers.length; i++) {
numbers[i] = numbers[i+1];
}
//或者用shift()方法
numbers.shift();
//在任意位置删除元素(比如在位置5删除3个元素,即删掉了位置5、6、7上的元素)
numbers.splice(5,3);

合并数组

1
2
3
4
var zero = 0;
var positiveNumbers = [1,2,3];
var negativeNumbers = [-1,-2,-3];
var numbers = negativeNumbers.concat(zero, positiveNumbers);

数组的迭代器函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//遍历
numbers.forEach(x => {
console.log(x);
});
for (let n of numbers) {
console.log(n);
}
//一个判断是否为偶数的函数
var isEven = (x) => {
return (x % 2 == 0) ? true : false;
}
numbers.every(isEven); //false;全部为偶才返回true
numbers.some(isEven); //true;只要存在偶数就返回true
numbers.map(isEven); // [false, true, false, true, false, true, false, true, false, true];返回结果数组
numbers.filter(isEven); //[2, 4, 6, 8, 10];返回所有符合条件的元素所组成的数组
//reduce()会将每次的结果叠加到累加器,执行结束返回累加器的值
numbers.reduce(function(prev, curr, index) { //数组求和
return prev + curr;
});

数组排序

1
2
3
4
5
6
7
8
9
10
11
12
//逆序
numbers.reverse();
//升序
numbers.sort((a,b) => {
if (a < b) {
return -1;
}
if (a > b) {
return 1;
}
return 0;
});

栈 (后进先出LIFO)

1
2
3
4
5
6
7
8
9
10
11
12
function Stack () {
let items = []; //保存栈中的元素

//向栈添加元素
this.push = function(element) {
items.push(element);
}
//从栈移除元素
this.pop = function() {
return items.pop();
}
}

用ES6的class创建:

1
2
3
4
5
6
7
8
9
class Stack {
constructor () {
this.items = [];
}
push(element) {
this.items.push(element);
}
//其他方法与上述写法类似
}

例子:用栈实现十进制转二进制的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function divideBy2(dec) {
var remStack = new Stack(),
rem,
binaryString = '';

while (dec > 0) {
rem = Math.floor(dec % 2);
remStack.push(rem);
dec = Math.floor(dec / 2);
}

while (!remStack.isEmpty()) {
binaryString += remStack.pop().toString();
}

return binaryString;
}

队列 (先进先出FIFO)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function Queue () {
let items = [];
//向队列添加元素
this.enqueue = function(element) {
items.push(element);
}
//从队列移除元素
this.dequeue = function() {
return items.shift();
}
//查看队头元素
this.front = function() {
return items[0];
}
//检查队列是否为空
this.isEmpty = function() {
return items.length == 0;
}
//打印队列元素个数
this.size = function() {
return items.length;
}
//打印队列元素
this.print = function() {
console.log(items.toString());
}
}
let queue = new Queue();
queue.enqueue('Nancy');

优先队列(对应的优先级数字越小优先级越高)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function PriorityQueue() {
let items = [];
function QueueElement (element, priority) {
this.element = element;
this.priority = priority;
}

this.enqueue = function(element, priority) {
let queueElement = new QueueElement(element, priority);
let added = false;
for (let i = 0; i < items.length; i++) {
if (queueElement.priority < items[i].priority) {
items.splice(i,0,queueElement);
added = true;
break;
}
}
if (!added) {
items.push(queueElement);
}
};

this.print = function() {
for (let i = 0; i < items.length; i++) {
console.log(`${items[i].element},${items[i].priority}`);
}
};
//其他方法与普通队列一致
}

链表

普通链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
function LinkedList() {
//创建Node类表示链表项
let Node = function(element) {
this.element = element;
this.next = null;
}

let length = 0;
let head = null;

//向链表末尾追加节点
this.append = function(element) {
let node = new Node(element),
current;

if(head == null) {
head = node;
} else {
current = head;
while(current.next) {
current = current.next;
}
current.next = node;
}

length++;
};

//删除指定位置的节点
this.removeAt = function(position) {
if(position > -1 && position < length) {
let current = head,
previous,
index = 0;

if(position === 0) {
head = current.next;
} else {
while(index++ < position) {
previous = current;
current = current.next;
}
previous.next = current.next;
}

length--;

return current.element;
} else {
return null;
}
}

//在任意位置插入节点
this.insert = function(position, element) {
if(position >= 0 && position <= length) {
let node = new Node(element),
current = head,
previous,
index = 0;

if(position === 0){
node.next = current;
head = node;
} else {
while(index++ < position) {
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}

length++;
return true;
} else {
return false;
}
};

//把LinkedList对象转换成字符串
this.toString = function() {
let current = head,
string = '';

while(current){
string += current.element + (current.next ? '\n' : '');
current = current.next;
}

return string;
};

//返回节点对应的索引值
this.indexOf = function(element) {
let current = head;
index = 0;

while(current) {
if(current.element === element) {
return index;
}
index++;
current = current.next;
}

return -1;
};

//判空
this.isEmpty = function() {
return length === 0;
};

//获取链表长度
this.size = function() {
return length;
};

//获取头节点
this.getHead = function() {
return head;
}
}

双向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
function DoublyLinkedList() {
let Node = function(element) {
this.element = element;
this.prev = null;
this.next = null;
}

let length = 0;
let head = null;
let tail = null;

this.insert = function(position, element) {
if(position >= 0 && position <= length) {
let node = new Node(element),
current = head,
previous,
index = 0;

if(position === 0) {
if(!head) {
head = node;
tail = node;
} else {
node.next = current;
current.prev = node;
head = node;
}
} else if (position === length) {
current = tail;
current.next = node;
node.prev = current;
tail = node;
} else {
while(index++ < position){
previous = current;
current = current.next;
}
node.next = current;
node.prev = previous;
}

length++;
return true;
} else {
return false;
}
};

this.removeAt = function(position) {
if(position > -1 && position < length){
let current = head,
previous,
index = 0;

if(position === 0) {
head = current.next;
if(length === 1) {
tail = null;
} else {
head.prev = null;
}
} else if (position === length-1) {
current = tail;
tail = current.prev;
tail.next = null;
} else {
while(index++ < position) {
previous = current;
current = current.next;
}
previous.next = current.next;
current.next.prev = previous;
}

length--;
return current.element;
} else {
return null;
}
};
}

循环链表

与普通链表的区别在于tail.next不是null而是head。

集合

集合由一组无序且唯一的项组成。

创建集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
function Set() {
let items = {};

this.has = function(value) {
return items.hasOwnProperty(value);
};

this.add = function(value) {
if(!this.has(value)){
items[value] = value;
return true;
}
return false;
};

this.remove = function(value) {
if(this.has(value)){
delete items[value];
return true;
}
return false;
};

this.clear = function() {
items = {};
};

this.size = function() {
return Object.keys(items).length;
};

//size()方法的兼容版本
this.sizeLegacy = function() {
let count = 0;
for(let key in items) {
if(items.haOwnProperty(key)) ++count;
}
return count;
}

this.values = function() {
let values = [];
for(let i = 0, keys = Object.keys(items); i<keys.length; i++) {
values.push(items[keys[i]])
}
return values;
}

//values()的兼容版本
this.valuesLegacy = function() {
let values = [];
for(let key in items) {
if(items.hasOwnProperty(key)) {
values.push(items[key]);
}
}
return values;
};

//取并集
this.union = function(otherSet) {
let unionSet = new Set();

let values = this.values();
for(let i=0; i<values.length; i++) {
unionSet.add(values[i]);
}

values = otherSet.values();
for(let i=0; i<values.length; i++) {
unionSet.add(values[i]);
}

return unionSet;
};

//取交集
this.intersection = function(otherSet) {
let intersectionSet = new Set();

let values = this.values();
for(let i=0; i<values.length; i++) {
if(otherSet.has(values[i])) {
intersectionSet.add(values[i]);
}
}

return intersectionSet;
};

//差集
this.difference = function(otherSet) {
let differenceSet = new Set();

let values = this.values();
for (let i=0; i<values.length; i++) {
if(!otherSet.has(values[i])) {
differenceSet.add(values[i]);
}
}

return differenceSet;
};

//判断是否是另一个集合的子集
this.subset = function(otherSet) {
if(this.size() > otherSet.size()) {
return false;
} else {
let values = this.values();
for (let i=0; i<values.length; i++) {
if(!otherSet.has(values[i])){
return false;
}
}
return true;
}
};

}

ES6——Set类

区别:values()方法返回一个Iterator;自身具有size属性;无自带的并集、交集、差集和子集方法,但可以用其他自身方法实现。

并集

1
2
3
let unionAB = new Set();
for (let x of setA) unionAB.add(x);
for (let x of setB) unionAB.add(x);

交集

1
2
3
4
5
6
7
8
9
10
let intersection = function(setA, setB) {
let intersectionSet = new Set();
for (let x of setA) {
if(setB.has(x)) {
intersectionSet.add(x);
}
}
return intersectionSet;
};
let intersectionAB = intersection(setA, setB);

差集

1
2
3
4
5
6
7
8
9
10
11
12
13
let difference = function(setA, setB) {
let differenceSet = new Set();
for (let x of setA) {
if (!setB.has(x)) {
differenceSet.add(x);
}
}
return differenceSet;
};
let differenceAB = difference(setA, setB);

//或者用ES6的写法实现
differenceAB = new Set([x for (x of setA) if (!setB.has(x))]);

字典和散列表

Map和Set

CATALOG
  1. 1. 数组
    1. 1.1. 添加、插入元素
    2. 1.2. 删除元素
    3. 1.3. 合并数组
    4. 1.4. 数组的迭代器函数
    5. 1.5. 数组排序
  2. 2. 栈 (后进先出LIFO)
  3. 3. 队列 (先进先出FIFO)
  4. 4. 链表
    1. 4.1. 普通链表
    2. 4.2. 双向链表
    3. 4.3. 循环链表
  5. 5. 集合
  6. 6. 字典和散列表
  7. 7.
  8. 8.