# 栈
function Stack(arr) {
this.arr = arr;
}
Stack.prototype.push = function (o) {
this.arr.push(o);
};
Stack.prototype.pop = function (o) {
this.arr.pop(o);
};
Stack.prototype.isEmpty = function (o) {
return this.arr.length === 0;
};
Stack.prototype.top = function (o) {
return this.arr[this.arr.lenght - 1];
};
Stack.prototype.clear = function (o) {
this.arr = [];
};
Stack.prototype.size = function (o) {
return this.arr.length;
};
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
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
# 队列
function Queue() {
this.arr = [];
}
Queue.prototype.enqueue = function (o) {
this.arr.push(o);
};
Queue.prototype.dequeue = function (o) {
this.arr.shift();
};
Queue.prototype.front = function (o) {
return this.arr[0];
};
Queue.prototype.isEmpty = function (o) {
return this.arr.length === 0;
};
Queue.prototype.size = function (o) {
return this.arr.length;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 链表
单链表
function Node(elem) {
this.elem = elem;
this.next = null;
}
function LinkedList() {
this.node = null;
this.next = null;
this.head = null;
this.length = 0;
}
LinkedList.prototype.append = function (o) {
const node = new Node(o);
if (this.head === null) {
this.head = node;
this.node = node;
} else {
this.node.next = node;
this.node = node;
}
this.length++;
};
LinkedList.prototype.insert = function (position, elem) {
const len = this.length();
if (position < 0 || position > len) {
throw new Error("越界");
}
if (position === undefined || elem === undefined) {
throw new Error("insert调用参数不全");
}
if (position === len) {
this.append(elem);
return;
}
let index = 0;
let cur = this.head;
while (index < position) {
cur = cur.next;
index++;
}
let nextNode = cur.next;
let newNode = new Node(elem);
newNode.next = nextNode;
cur.next = newNode;
this.length++;
};
LinkedList.prototype.find = function (elem) {
let cur = this.head;
while (cur) {
if (cur.elem === elem) {
return cur;
}
cur = cur.next;
}
return null;
};
LinkedList.prototype.findPre = function (elem) {
let cur = this.head;
while (cur) {
if (cur.next && cur.next.elem === elem) {
return cur;
}
cur = cur.next;
}
return null;
};
LinkedList.prototype.remove = function (elem) {
const preNode = this.findPre(elem);
console.log(preNode);
if (!preNode) {
throw new Error("找不到该元素");
}
preNode.next = preNode.next.next;
this.length--;
};
LinkedList.prototype.log = function () {
let cur = this.head;
while (cur) {
console.log(cur.elem);
cur = cur.next;
}
};
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
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
# 双向链表
function Node(elem) {
this.elem = elem;
this.next = null;
this.pre = null;
}
function LinkedList() {
this.node = null;
this.head = null;
this.length = 0;
}
LinkedList.prototype.append = function (elem) {
const newNode = new Node(elem);
if (this.head) {
this.node.next = newNode;
newNode.pre = this.node;
} else {
this.head = newNode;
}
this.node = newNode;
};
LinkedList.prototype.find = function (elem) {
let cur = this.head;
while (cur) {
if (cur.elem === elem) {
return cur;
}
cur = cur.next;
}
return null;
};
LinkedList.prototype.remove = function (elem) {
let findNode = this.find(elem);
if (!findNode.pre) {
findNode.next.pre = null;
this.head = findNode.next;
} else if (!findNode.next) {
findNode.pre.next = null;
} else {
let nextNode = findNode.next;
findNode.pre.next = nextNode;
nextNode.pre = findNode.pre;
}
findNode = null;
};
LinkedList.prototype.log = function () {
let cur = this.head;
while (cur) {
console.log(cur);
cur = cur.next;
}
};
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
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
# 二叉树
# 构造
function Node(elem, left, right) {
this.elem = elem;
this.left = left || null;
this.right = right || null;
}
function BST() {
this.root = null;
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
# 插入
BST.prototype.insert = function (elem) {
const newNode = new Node(elem);
if (!this.root) {
this.root = newNode;
} else {
let cur = this.root;
let parent;
while (true) {
parent = cur;
if (elem < cur.elem) {
cur = cur.left;
if (cur === null) {
parent.left = newNode;
break;
}
} else {
cur = cur.right;
if (cur === null) {
parent.right = newNode;
break;
}
}
}
}
};
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 遍历
递归
function inOrder(node) {
if (node !== null) {
inOrder(node.left);
console.log(node.elem);
inOrder(node.right);
}
}
function preOrder(node) {
if (node !== null) {
console.log(node.elem);
preOrder(node.left);
preOrder(node.right);
}
}
function postOrder(node) {
if (node !== null) {
postOrder(node.left);
postOrder(node.right);
console.log(node.elem);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 查找
BST.prototype.find = function (elem) {
let cur = this.root;
while (cur !== null && cur.elem !== elem) {
if (cur.elem > elem) {
cur = cur.left;
} else {
cur = cur.right;
}
}
return cur;
};
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 图
# 无向图
function Vertex(label) {
this.label = label;
}
function Graph(v) {
this.vertices = v;
this.edges = 0;
this.adj = [];
for (var i = 0; i < this.vertices; ++i) {
this.adj[i] = [];
}
}
Graph.prototype.addEdge = function (v, w) {
const vVertex = new Vertex(v);
const wVertex = new Vertex(w);
this.adj[v].push(wVertex);
this.adj[w].push(vVertex);
this.edges++;
};
Graph.prototype.show = function () {
let log = "";
for (var i = 0; i < this.vertices; ++i) {
log = `${i} -> `;
for (var j = 0; j < this.vertices; ++j) {
const item = this.adj[i][j];
if (item !== undefined) {
log = log.concat(`${item.label}, `);
}
}
console.log(log);
}
};
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
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
# 搜索图
# 深度优先搜索
function Graph(v) {
this.vertices = v;
this.edges = 0;
this.marked = [];
this.adj = [];
for (var i = 0; i < this.vertices; ++i) {
this.adj[i] = [];
this.marked[i] = false;
}
}
Graph.prototype.addEdge = function (v, w) {
this.adj[v].push(w);
this.adj[w].push(v);
this.edges++;
};
Graph.prototype.show = function () {
let log = "";
for (var i = 0; i < this.vertices; ++i) {
log = `${i} -> `;
for (var j = 0; j < this.vertices; ++j) {
const item = this.adj[i][j];
if (item !== undefined) {
log = log.concat(`${item}, `);
}
}
console.log(log);
}
};
Graph.prototype.dfs = function (v = 0) {
this._dfs(v);
};
Graph.prototype._dfs = function (v) {
this.marked[v] = true;
console.log(v);
this.adj[v].forEach((w) => {
if (!this.marked[w]) {
this._dfs(w);
}
});
};
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
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
# 广度优先搜索
Graph.prototype.bfs = function (v) {
const queue = [];
queue.push(v);
this.marked[v] = true;
while (queue.length > 0) {
let log = "";
let curV = queue.shift();
log = log.concat(`${curV} `);
console.log(curV);
this.adj[curV].forEach((w) => {
if (!this.marked[w]) {
this.marked[w] = true;
queue.push(w);
}
});
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# BFS 寻找最短路径
d 记录距离,pred 记录前溯点
Graph.prototype.bfs = function (v) {
const queue = [];
const d = [];
const pred = [];
for (let i = 0; i < this.vertices; i++) {
d[i] = 0;
pred[i] = null;
}
queue.push(v);
this.marked[v] = true;
while (queue.length > 0) {
let curV = queue.shift();
this.adj[curV].forEach((w) => {
if (!this.marked[w]) {
d[w] = d[curV] + 1;
pred[w] = curV;
this.marked[w] = true;
queue.push(w);
}
});
}
return { d, pred };
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Git →