zxy的前端日志

# 基础数据结构

# 列表

  • 列表是一组有序的数据。每个列表中的数据项称为元素。元素的数量受内存控制。
  • 不包含任何怨怒是的列表称为空列表。
function List() {
  this.listSize = 0; // 列表元素个数
  this.pos = 0; // 列表当前位置
  this.dataStore = []; // 初始化一个空数组用来保存列表
  this.clear = clear; // 清空列表汇总的所有元素
  this.find = find; // 查找元素
  this.toString = toString; // 返回列表字符串形式
  this.insert = insert; // 在所有元素后插入新元素
  this.append = append; // 在列表元素末尾增加新元素
  this.remove = remove; // 从列表中删除元素
  this.front = front; // 从列表的当前位置移动到第一个元素
  this.end = end; // 从列表的当前位置移动到最后一个位置
  this.prev = prev; // 将当前位置后移一位
  this.next = next; // 将当前位置后移一位
  this.length = length; // 列表包含元素的个数
  this.currPos = currPos; // 返回列表当前位置
  this.moveTo = moveTo; // 当前位置移动到制定位置
  this.getElement = getElement; // 显示当前的元素
  this.contains = contains; // 是否包含该元素
}

function append(element) {
  this.dataStore[this.listSize++] = element;
}

function find(element) {
  for (var i = 0, len = this.dataStore.length; i < len; ++i) {
    if (this.dataStore[i] === element) {
      return i;
    }
  }
  return -1;
}

function remove(element) {
  var foundAt = this.find(element);
  if (foundAt > -1) {
    this.dataStore.slice(foundAt, 1);
    --this.listSize;
    return;
  }
  return false;
}

function length() {
  return this.listSize;
}

function toString() {
  return this.dataStore;
}

function insert(element, after) {
  var insertPos = this.find(after);
  if (insertPos > -1) {
    this.dataStore.splice(insertPos + 1, 0, element);
    ++this.listSize;
    return true;
  }
  return false;
}

function clear() {
  delete this.dataStore;
  this.dataStore.length = 0;
  this.listSize = this.pos = 0;
}

function contains(element) {
  for (var i = 0, len = this.dataStore.length; i < len; ++i) {
    if (this.dataStore[i] == element) {
      return true;
    }
  }
  return false;
}

function front() {
  this.pos = 0;
}

function end() {
  this.pos = this.listSize - 1;
}

function prev() {
  if (this.pos > 0) {
    --this.pos;
  }
}

function next() {
  if (this.pos < this.listSize) {
    ++this.pos;
  }
}

function currPos() {
  return this.pos;
}

function moveTo(position) {
  this.pos = position;
}

function getElement() {
  return this.dataStore[this.pos];
}
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

# 栈

  • 栈内元素只能通过列表的一端访问，这一端称为栈顶
  • 栈被称为一种后入先出的数据结构
  • 插入新元素又称作进栈、入栈或压栈，从一个栈删除元素又称作出栈或退栈
function Stack() {
  this.dataStore = []; // 保存栈内元素
  this.top = 0; // 标记可以插入新元素的位置 栈内压入元素该变量变大 弹出元素 变量变小
  this.push = push; // 入栈操作
  this.pop = pop; // 出栈操作
  this.peek = peek; // 返回栈顶元素
  this.clear = clear; //  清空栈
  this.length = length; // 栈的长度
}

function push() {
  this.dataStore[this.top++] = element;
}

function pop() {
  return this.dataStore[--this.top];
}

function peek() {
  return this.dataStore[this.top - 1];
}

function length() {
  return this.top;
}

function clear() {
  this.top = 0;
}
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() {
  this.dataStore = [];
  this.enqueue = enqueue;
  this.dequeue = dequeue;
  this.front = front;
  this.back = back;
  this.empty = empty;
  this.toString = toString;
}

function enqueue(element) {
  this.dataStore.push(element);
}

function dequeue() {
  return this.dataStore.shift();
}

function front() {
  return this.dataStore[0];
}

function back() {
  return this.dataStore[this.dataStore.length - 1];
}

function empty() {
  if (this.dataStore.length === 0) {
    return true;
  } else {
    return false;
  }
}

function toString() {
  var reStr = "";
  for (var i = 0; i < this.dataStore.length; i++) {
    reStr += this.dataStore[i] + "\n";
  }
  return reStr;
}
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

# 链表

  • 链表是由一系列节点组成的集合，每个街斗都使用一个对象的引用指向它的后继，指向另一个节点的引用叫链
  • 链表元素靠相互之间的关系进行引用 A -> B -> C，B 并不是链表的第二个元素而是 B 跟在 A 后面，遍历链表就是跟着链接，从链接的首元素一直到尾元素，但不包含头节点，头元素常常被称为链表的接入点。
  • 向单向链表插入一个节点，需要修改它前面的节点使其指向新加入的节点，而新加入的节点则指向原来前驱指向的节点
  • 从单向链表删除一个元素，需要将待删除的元素的前驱节点指向待删除元素的后继节点，同时将删除元素指向 null

# 单向链表

// 节点
function Node(element) {
  this.element = element;
  this.next = null;
}
// 初始化链表
function LList() {
  this.head = new Node("head");
  this.find = find;
  this.insert = insert;
  this.display = display;
}
// 查找元素
function find(item) {
  var currNode = this.head;
  while (currNode.element !== item) {
    currNode = currNode.next;
  }
  return currNode;
}
// 插入节点
function insert(newElement, item) {
  var newNode = new Node(newElement);
  var currNode = this.find(item);
  newNode.next = currNode.next;
  currNode.next = newNode;
}
// 遍历
function display() {
  var currNode = this.head;
  while (currNode.next !== null) {
    console.log(currNode.next.element);
    currNode = currNode.next;
  }
}

function findPrevious() {
  var currNode = this.head;
  while (currNode.next != null && currNode.next.element != item) {
    currNode = currNode.next;
  }
  return currNode;
}

function remove(item) {
  var preNode = this.findPrevious(item);
  var currNode = this.find(item);
  if (preNode.next != null) {
    preNode.next = currNode.next;
    currNode.next = null;
  }
}

var cities = new LList();
cities.insert("first", "head");
cities.insert("second", "first");
cities.insert("third", "second");
cities.display();
cities.remove("second");
cities.display();
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

# 双向链表

function Node(element) {
  this.element = element;
  this.next = null;
  this.previous = null;
}
// 初始化链表
function LList() {
  this.head = new Node("head");
  this.find = find;
  this.insert = insert;
  this.display = display;
  this.remove = remove;
}
// 查找元素
function find(item) {
  var currNode = this.head;
  while (currNode.element !== item) {
    currNode = currNode.next;
  }
  return currNode;
}
// 插入节点
function insert(newElement, item) {
  var newNode = new Node(newElement);
  var currNode = this.find(item);
  newNode.next = currNode.next;
  newNode.previous = currNode;
  currNode.next = newNode;
  if (newNode.next !== null) {
    newNode.next.previous = newNode;
  }
}
// 遍历
function display() {
  var currNode = this.head;
  while (currNode.next !== null) {
    console.log(currNode.next.element);
    currNode = currNode.next;
  }
}

function remove(item) {
  var currNode = this.find(item);
  if (currNode.next != null) {
    currNode.previous.next = currNode.next;
    currNode.next.previous = currNode.previous;
    currNode.next = null;
    currNode.previous = null;
  } else {
    currNode.previous.next = null;
    currNode.previous = null;
  }
}
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

# 字典

字典以一种键值对形式存储

function Dictionary() {
  this.dataStore = new Array();
  this.add = add;
  this.find = find;
  this.remove = remove;
  this.showAll = showAll;
  this.count = count;
  this.clear = clear;
}

function add(key, value) {
  this.dataStore[key] = value;
}

function find(key) {
  return this.dataStore[key];
}

function remove(key) {
  delete this.dataStore[key];
}

function showAll() {
  var datakeys = Object.keys(this.dataStore);
  for (var keys in datakeys) {
    console.log(datakeys[keys] + "-->" + this.dataStore[datakeys[keys]]);
  }
}

function count() {
  return Object.keys(this.dataStore).length;
}

function clear() {
  var datakeys = Object.keys(this.dataStore);
  for (var keys in datakeys) {
    delete this.dataStore[datakeys[keys]];
  }
}
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

# 散列

  • 数组长度是预先设定的，可以随时增加，所有元素根据和该元素对应的键，保存数组特定位置。
  • 即使使用高效的散列函数，仍然存在两个键值相同的情况，这种现象称为碰撞
  • 数组的长度应该是一个质数，所有的策略都基于碰撞
  • 开链法：两个键相同保存位置一样。开辟第二数组，也称第二个数组为链。
  • 线性探测法属于开放寻址散列，查找散列位置如果当前位置没有继续寻找下一个位置。存储数据较大较适合。数组大小>=1.5 _ 数据（开链法），数组大小>=2 _ 数据（线性探测法）。
function HashTable() {
  this.table = new Array(137);
  this.simpleHash = simpleHash;
  this.put = put;
  this.get = get;
  this.showDistro = showDistro;
}

// 除留余数法
function simpleHash(data) {
  var total = 0;
  for (var i = 0; i < data.length; i++) {
    total += data.charCodeAt(i);
  }
  return total % this.table.length;
}

// 比 simpleHash 更优化一些
function betterHash(data) {
  var H = 31;
  var total = 0;
  for (var i = 0; i < data.length; i++) {
    total += H * total + data.charCodeAt(i);
  }
  if (total < 0) {
    total += this.table.length - 1;
  }
  return total % this.table.length;
}

function put(data) {
  // var pos = this.simpleHash(data);
  var pos = this.betterHash(data);
  this.table[pos] = data;
}

function get(key) {
  return this.table[this.simpleHash(data)];
}

function showDistro() {
  var n = 0;
  for (var i = 0; i < this.table.length; i++) {
    if (this.table[i] != undefined) {
      console.log("键值是->" + i + "值是" + this.table[i]);
    }
  }
}
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

# 集合

  • 集合是一组无序单彼此之间又有一定相关性的成员构成的，集合中的元素称为成员
  • 不包含任何成员的集合称为空集，全集则是包含一切可能成员的集合
  • 如果两个集合的成员完全相同，则称两个集合相等
  • 如果一个集合中的所有成员都属于另外一个集合，则前一集合成为后一集合的子集
  • 并集：将两个集合中的成员进行合并，得到一个新集合
  • 交集：两个集合中共同存在的成员组成一个新的集合
  • 补集：属于一个集合不属于另一个集合的成员组成的集合
function set() {
  this.dataStore = [];
  this.add = add;
  this.remove = add;
  this.show = add;
  this.union = union;
  this.contains = contains;
  this.intersect = intersect;
  this.difference = difference;
  this.size = size;
  this.subset = subset;
}
function add(data) {
  if (this.dataStore.indexOf(data) < 0) {
    this.dataStore.push(data);
  } else {
    return false;
  }
}

function remove() {
  var pos = this.dataStore.indexOf(data);
  if (pos > -1) {
    this.dataStore.splice(pos, 1);
  } else {
    return false;
  }
}

function show() {
  return this.dataStore;
}

// 定义一些集合的方法 交集补集

function union(set) {
  var tempSet = new Set();
  for (var i = 0; i < this.dataStore.length; i++) {
    tempSet.add(this.dataStore[i]);
  }
  for (var i = 0; i < set.dataStore.length; i++) {
    if (tempSet.contains(set.dataStore[i])) {
      tempSet.dataStore.push(set.dataStore[i]);
    }
  }
  return tempSet;
}

function contains(data) {
  if (this.dataStore.indexOf(data) > -1) {
    return true;
  } else {
    return false;
  }
}

function intersect(set) {
  var tempSet = new Set();
  for (var i = 0; i < this.dataStore.length; i++) {
    if (set.contains(this.dataStore[i])) {
      tempSet.add(this.dataStore[i]);
    }
  }
}

function difference(set) {
  var tempSet = new Set();
  for (var i = 0; i < this.dataStore.length; i++) {
    if (set.contains(this.dataStore[i])) {
      tempSet.add(this.dataStore[i]);
    }
  }
  return tempSet;
}

function size() {
  return this.dataStore.length;
}

function subset(set) {
  if (set.size() > this.size()) {
    return false;
  } else {
    for (var i = 0; i < set.dataStore.length; i++) {
      if (!this.contains(set.dataStore[i])) {
        return false;
      }
    }
    return true;
  }
}
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

# 二叉树

  • 树由一组以边连接的节点组成
  • 一棵树最上面的节点称为根节点，如果一个节点下面连接多个节点，那么节点称为父节点，它下面的节点被称为子节点。一个节点可以有 0 个、1 个或多个子节点。没有任何子节点的节点称为叶子结点。
  • 二叉树是一种特殊的树，子节点个数不超过两个
  • 从一个节点走到另一个节点的这一组边称为路径
  • 以某种特定顺序访问树中所有节点称为树的遍历
  • 树分为几个层次，根节点是第 0 层，它的子节点第 1 层，以此类推。我们定义树的层数就是树的深度
  • 每个节点都有一个与之相关的值，该值有时候被称为键
  • 一个父节点的两个子节点分别称为左节点和右节点。二叉查找树是一种特殊的二叉树，相对较小的值保存在左节点，较大的值保存在右节点，这一特性使得查找效率很高
function Node(data, left, right) {
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show;
}

function show() {
  return this.data;
}

// 二叉树
function BST() {
  this.root = null;
  this.insert = insert;
  this.inOrder = inOrder;
  this.getSmallest = getSmallest;
  this.getMax = getMax;
  this.find = find;
  this.remove = remove;
}

// 插入
function insert(data) {
  var n = new Node(data, null, null);
  if (this.root == null) {
    this.root = n;
  } else {
    var current = this.root;
    var parent;
    while (true) {
      parent = current;
      if (data < current.data) {
        current = current.left;
        if (current == null) {
          parent.left = n;
          break;
        }
      } else {
        current = current.right;
        if (current == null) {
          parent.right = n;
          break;
        }
      }
    }
  }
}

// 中序查询
function inOrder(node) {
  if (node !== null) {
    inOrder(node.left);
    console.log(node.data);
    inOrder(node.right);
  }
}

function getSmallest(data) {
  var current = this.root || root;
  while (current.left !== null) {
    current = current.left;
  }
  return current.data;
}

function getMax(data) {
  var current = this.root || root;
  while (current.right !== null) {
    current = current.right;
  }
  return current.data;
}

function find(data) {
  var current = this.root;
  while (current !== null) {
    if (current.data == data) {
      return current;
    } else if (data < current.data) {
      current = current.left;
    } else {
      current = current.right;
    }
  }
  return null;
}

function remove(data) {
  removeNode(this.root, data);
}

function removeNode(node, data) {
  if (node == null) {
    return null;
  }
  if (data == node.data) {
    if (node.left == null && node.right == null) {
      return null;
    }
    if (node.left == null) {
      return node.right;
    }
    if (node.right == null) {
      return node.left;
    }
    var tempNode = getSmallest(node, data);
    node.data = tempNode.data;
    node.right = removeNode(node.right, tempNode.data);
    return node;
  } else if (data < node.data) {
    node.left = removeNode(node.left, data);
    return node;
  } else {
    node.right = removeNode(node.right, data);
    return node;
  }
}

var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(17);
nums.insert(34);
nums.insert(54);
nums.insert(3);
nums.insert(88);
nums.insert(49);
nums.insert(9);
nums.insert(76);
console.log("遍历节点");
nums.inOrder(nums.root);
console.log("最小值", nums.getSmallest(nums));
console.log("最大值", nums.getMax(nums));
// nums.remove(23)
// nums.inOrder(nums.root);
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
125
126
127
128
129
130
131
132
133
134
135
136

# 图

// 创建图
function Graph(v) {
  this.vertices = v;
  this.edges = 0;
  this.adj = [];
  this.marked = [];
  for (var i = 0; i < this.vertices; i++) {
    this.adj[i] = [];
  }
  this.addEdge = addEdge;
  this.showGraph = showGraph;
  this.dfs = dfs;
  this.bfs = bfs;
  this.edgeTo = [];
  this.hasPathTo = hasPathTo;
  this.pathTo = pathTo;
}

// 添加
function addEdge(v, w) {
  this.adj[v].push(w);
  this.adj[w].push(v);
  this.edges++;
}

// 显示图
function showGraph() {
  for (var i = 0; i < this.vertices; i++) {
    var edges = "";
    for (var j = 0; j < this.vertices; j++) {
      if (this.adj[i][j]) {
        edges += this.adj[i][j] + " ";
      }
    }
    console.log(i + "->" + edges);
  }
}

function dfs(v) {
  this.marked[v] = true;
  if (this.adj[v] != undefined) {
    console.log(v + "【节点已经被访问】");
  }
  for (var w in this.adj[v]) {
    var current = this.adj[v][w];
    if (!this.marked[current]) {
      this.dfs(current);
    }
  }
}

// 广度搜索
function bfs(s) {
  var queue = [];
  this.marked[s] = true;
  queue.push(s);
  while (queue.length > 0) {
    var v = queue.shift();
    if (v != undefined) {
      console.log("[bfs]" + v + "【节点已经被访问】");
    }
    for (var w in this.adj[v]) {
      var current = this.adj[v][w];
      if (!this.marked[current]) {
        this.marked[current] = true;
        this.edgeTo(current) = v;
        queue.push(current);
      }
    }
  }
}

function hasPathTo(v) {
  return this.marked[v];
}

// 最短路径
function pathTo(v) {
  var source = 0;
  if (this.hasPathTo(v)) {
    return undefined;
  }
  var path = [];
  for (var i = v; i != source; i = this.edgeTo(i)) {
    path.push(i);
  }
  path.push(source);
  return path;
}

var g = new Graph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.showGraph();
g.dfs(0);
g.bfs(0);

var paths = g.pathTo(4);
var str = "";
while (paths.length > 0) {
  if (paths.length > 1) {
    str += paths.pop() + "->";
  } else str += paths.pop();
}

console.log(str);
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

# 动态规划

动态规划被认为是一种与递归相反的技术。递归从顶部开始分解出多个小问题，合并成一个解决方案。动态规划解决方案从底部分解很多小问题解决掉，组成解决方案。

用动态规划写斐波那契数列

function dynFib(n) {
  var val = [];
  for (var i = 0; i <= n; i++) {
    val[i] = 0;
  }
  if (n == 0) {
    return 0;
  } else if (n == 1 || n == 2) {
    return 1;
  } else {
    val[1] = 1;
    val[2] = 1;
    for (var i = 3; i <= n; i++) {
      val[i] = val[i - 1] + val[i - 2];
    }
    console.log(val);
    return val[n];
  }
}
console.log("动态规划", dynFib(10));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

不借助数组实现

function iterFib(n) {
  if (n > 0) {
    var last = 1;
    var nestLast = 1;
    var result = 1;
    for (var i = 2; i < n; i++) {
      result = last + nestLast;
      nestLast = last;
      last = result;
    }
    return result;
  } else {
    return 0;
  }
}
console.log("动态规划非数组", iterFib(10));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 贪心算法

它是一种寻找“优质解”为手段达成整体解决方案的算法。这些优质的解决方案称为局部最优解。酱油希望得到正确答案的最终解决方案称为全局最优解，“贪心”会用那些看起来近乎无法找到完整解决方案的问题，次优解也是可以接受的。

找零问题

function makeChange(orginRmb, coins) {
  var remianRmb = 0;
  if (orginRmb % 50 < orginRmb) {
    coins[3] = parseInt(orginRmb % 50, 10);
    remianRmb = orginRmb % 50;
    orginRmb = remianRmb;
  }
  if (orginRmb % 10 < orginRmb) {
    coins[2] = parseInt(orginRmb % 10, 10);
    remianRmb = orginRmb % 10;
    orginRmb = remianRmb;
  }
  if (orginRmb % 5 < orginRmb) {
    coins[1] = parseInt(orginRmb % 5, 10);
    remianRmb = orginRmb % 5;
    orginRmb = remianRmb;
  }
  coins[0] = orginRmb % 1;
}

var orginRmb = 63;
var coins = [];
makeChange(orginRmb, coins);

if (coins[3] > 0) {
  console.log("继续使用10块钱");
}

if (coins[2] > 0) {
  console.log("继续使用5块钱");
}

if (coins[1] > 0) {
  console.log("继续使用1块钱");
}

if (coins[0] == 0) {
  console.log("找完了");
}

console.log(coins);
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

← 排序算法 →