数据结构

数组(Array)

一个存储元素的线性的连续存储结构，元素可以通过索引来任意存取

栈(Stack)

栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，具有后入先出的特点(LIFO)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function Stack() {
  this.dataStore = [];
  this.top = 0;
  this.push = function (ele) {
    this.dataStore[this.top++] = ele;
  };
  this.pop = function () {
    return this.dataStore[--this.top];
  };
  this.peek = function () {
    return this.dataStore[this.top-1];
  };
  this.clear =  function () {
    this.top = 0;
  }
  this.length = function () {
    return this.top;
  }
}

解决问题：

数制间的相互转换

1
2
3
4
5
6
7
8
9
10
11
12
function mulBase(num, base) {
  var s = new Stack();
  do {
     s.push(num % base);
     num = Math.floor(num /= base);
  } while (num > 0);
  var converted = "";
  while (s.length() > 0) {
     converted += s.pop();
  }
  return converted;
}

判断回文数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function isPalindrome(word) {
  var s = new Stack();
  for (var i = 0; i < word.length; ++i) {
     s.push(word[i]);
  }
  var rword = "";
  while (s.length() > 0) {
     rword += s.pop();
  }
  if (word == rword) {
     return true;
} else {
     return false;
  }
}

队列(Queue)

队列是一种特殊的列表，不同的是队列只能在队尾插入元素，在队首删除元素，具有先进先出的特点(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() {
  this.dataStore = [];
  this.enqueue = function (element) {
    this.dataStore.push(element);
  };
  this.dequeue =  function () {
    return this.dataStore.shift();
  };
  this.front = function () {
    return this.dataStore[0];
  };
  this.back = function () {
    return this.dataStore[this.dataStore.length-1];
  };
  this.toString = function () {
    var retStr = "";
    for (var i = 0; i < this.dataStore.length; ++i) {
       retStr += this.dataStore[i] + "\n";
    }
    return retStr;
  };
  this.empty = function() {
    if (this.dataStore.length == 0) {
       return true;
    } else {
       return false;
    }
  };
}

优先队列

在一般情况下，从队列中删除的元素，一定是率先入队的元素。但是也有一些使用队列的应用，在删除元素时不必遵守先进先出的约定，比如优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
function Patient(name, code) {
  this.name = name;
  this.code = code;
}
function dequeue() {
  var priority = this.dataStore[0].code;
  for (var i = 1; i < this.dataStore.length; ++i) {
    if (this.dataStore[i].code < priority) {
      priority = i;
    }
  }
  return this.dataStore.splice(priority, 1);
}

数组不总是组织数据的最佳数据结构：

  • 在很多编程语言中，数组的长度是固定的，所以当数组已被填满时，再要加入新的元素就会非常困难
  • 在数组中，添加和删除元素也很麻烦，因为需要将数组中的其他元素向前或向后平移，以反映数组刚刚进行了添加或删除操作
  • JavaScript中数组被实现成了对象，效率很低

链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继。指向另一个节点的引用叫做链

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
// Node类
function Node(element) {
  this.element = element;
  this.next = null;
}
function LList() {
  this.head = new Node("head");
  this.find = function (item) {
    var currNode = this.head;
    while (currNode.element != item) {
       currNode = currNode.next;
    }
    return currNode;
  };
  this.insert = function (newElement, item) {
    var newNode = new Node(newElement);
    var current = this.find(item);
    newNode.next = current.next;
    current.next = newNode;
  };
  this.remove = function (item) {
    var prevNode = this.findPrevious(item);
    if (!(prevNode.next == null)) {
        prevNode.next = prevNode.next.next;
    }
  };
  this.display = function () {
    var currNode = this.head;
    while (!(currNode.next == null)) {
       print(currNode.next.element);
       currNode = currNode.next;
    }
  };
}

还有

字典(Dictionary)

字典是一种以键值对形式存储数据的数据结构，就像电话号码簿里的名字和电话号码一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function Dictionary() {
  this.datastore = new Array();
  this.add = function (key, value) {
    this.datastore[key] = value;
  };
  this.find = function (key) {
    return this.datastore[key];
  };
  this.remove = function (key) {
     delete this.datastore[key];
  };
  this.showAll = function () {
     for(var key in Object.keys(this.datastore)) {
       print(key + " -> " + this.datastore[key]);
     }
  };   
}

散列(HashTable)

散列是一种常用的数据存储技术，每个键值映射为一个唯一的数组索引，散列后的数据可以快速地插入或取用非常快

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
function HashTable() {
  this.table = new Array(137);
  this.betterHash = function (string) {
    // 霍纳算法，先计算字符串中各字符的 ASCII 码值，求和时每次要乘以一个质数
    const H = 37;
    var total = 0;
    for (var i = 0; i < string.length; ++i) {
       total += H * total + string.charCodeAt(i);
    }
    total = total % this.table.length;
    if (total < 0) {
       total += this.table.length-1;
    }
    return parseInt(total);
  };
  this.showDistro = function () {
    var n = 0;
    for (var i = 0; i < this.table.length; ++i) {
      if (this.table[i] != undefined) {
        print(i + ": " + this.table[i]);
      }
    }
  };
  this.put = function (data) {
    var pos = this.betterHash(data);
    this.table[pos] = data;
  };
  this.get = function (key) {
    return this.table[this.betterHash(key)];
  }
}

碰撞处理：开链法

在创建存储散列过的键值的数组时，通过调用一个函数创建一个新的空数组，然后将该数组赋给散列表里的每个数组元素。这样就创建了一个二维数组，存储多个键

挂载新的函数在散列上：

1
2
3
4
5
function buildChains() {
  for (var i = 0; i < this.table.length; ++i) {
    this.table[i] = new Array();
  }
}

put方法将键值散列，散列后的值对应数组中的一个位置，先尝试将数据放到该位置上的数组中的第一个单元格，如果该单元格里已经有数据了，put方法会搜索下一个位置，直到找到能放置数据的单元格，并把数据存储进去
get方法先对键值散列，根据散列后的值找到散列表中相应的位置，然后搜索该位置上的链，直到找到键值。如果找到，就将紧跟在键值后面的数据返回

碰撞处理：线性探索法

当发生碰撞时，线性探测法检查散列表中的下一个位置是否为空。如果为空，就将数据存入该位置;如果不为空，则继续检查下一个位置，直到找到一个空的位置为止。该技术是基于这样一个事实:每个散列表都会有很多空的单元格，可以使用它们来存储数据

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
function put(key, data) {
  var pos = this.betterHash(key);
  if (this.table[pos] == undefined) {
     this.table[pos] = key;
     this.values[pos] = data;
  } else {
    while (this.table[pos] != undefined) {
      pos++;
    }
    this.table[pos] = key;
    this.values[pos] = data;
  }
}
function get(key) {
  var hash = -1;
  hash = this.betterHash(key);
  if (hash > -1) {
    for (var i = hash; this.table[hash] != undefined; i++) {
      if (this.table[hash] == key) {
         return this.values[hash];
      }
    }
  }
  return undefined;
}

集合(Set)

集合是一种包含不同元素的数据结构。集合中的元素称为成员。集合的两个最重 要特性是:首先，集合中的成员是无序的;其次，集合中不允许相同成员存在

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
function Set() {
  this.dataStore = [];
  this.add = function (data) {
    if (this.dataStore.indexOf(data) < 0) {
       this.dataStore.push(data);
       return true;
    }
    else {
       return false;
    }
  };
  this.remove = function (data) {
    var pos = this.dataStore.indexOf(data);
    if (pos > -1) {
      this.dataStore.splice(pos, 1);
      return true;
    } else {
      return false;
    }
  };
  this.size = size;
  //this.contains、this.size略
  this.union = function (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;
  };
  this.intersect =  function (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;
  };
  this.subset =  function (set) {
    if (this.size() > set.size()) {
      this.difference = difference;
      return false;
    } else {
      for (var member in this.dataStore) {
        if (!set.contains(member)) {
           return false;
        }
      }
    }
    return true;
  }
  this.difference = function (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;
  }
}

二叉树

树是一种非线性的数据结构，以分层的方式存储数据，被用来存储具有层级关系的数据和有序列表。二叉树是一种特殊的树，它的子节点不超过两个，使得它们之上的操作非常高效。

二叉树有三种遍历方式：

  • 中序：升序访问所有的
  • 先序：先访问根节点，再访问左节点和右节点
  • 后序：先访问叶子节点，从左节点到右节点
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 Node(data, left, right) {
  this.data = data;
  this.left = left;
  this.right = right;
}
function BST() {
  this.root = null;
  this.insert = function (data) {
    var n = new Node(data, null, null)
    if (this.root == null) {
      //如果二叉树是空的，就插入到根
      this.root = n;
    } else {
      var current = this.root;
      var parent;
      while (1) {
        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;
          }
        }
      }
    }
  };
  // 中序遍历
  this.inOrder = function (node) {
    // 参数一般是根节点
    if (!(node == null)) {
      // 先展示最左节点，然后到其父节点从左到右遍历，依次向上
      inOrder(node.left);
      node.show()
      inOrder(node.right);
    }
  };
  // 先序遍历
  this.preOrder = function () {
    if (!(node == null)) {
      // 先展示根节点，然后访问其左节点，到最左再访问其右节点
      node.show()
      preOrder(node.left);
      preOrder(node.right);
    }
  };
  // 后序遍历
  this.postOrder = function () {
    if (!(node == null)) {
      // 先展示最左节点，然后访问其父节点的右节点，再访问父节点
      postOrder(node.left);
      postOrder(node.right);
      node.show()
    }
  };
  this.getMin = function () {
    var current = this.root;
    while (!(current.left == null)) {
      current = current.left;
    }
    return current.data
  };
  this.find = function () {
    var current = this.root;
    while (!(current.left == null)) {
      if (current.data == data) {
        return current
      } else if (data < current.data) {
        current = current.left;
      } else {
        current = current.right;
      }
    }
    return null;
  };
  this.remove = function (data) {
    root = removeNode(this.root, data)
  }
  this.removeNode = function (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 = getMin(node.right);
      node.data = tempNode.data;
      node.right = removeNode(node.right, tempNode.data);
      return node;
    } else if (data < node.data) {
      // 查找数据小于该节点，向左侧子节点搜索
      node.left = this.removeNode(node.left, data);
      return node;
    } else {
      // 查找数据大于该节点，向右侧子节点搜索
      node.right = this.removeNode(node.right, data);
      return node;
    }
  }
}

图

图是由边的集合以及顶点的集合组成，分为有向图和无序图。
圈是至少有一条边，且第一个顶点和最后一个顶点相同的路径，没有重复边或者重复顶点的圈是简单圈，除了第一个和最后一个顶点以外，路径的其它顶点有重复的圈被称为平凡圈

1
2
3
4
5
function Vertex(label, vasVisited) {
  this.label = label;//顶点
  this.wasVisited = wasVisited;//是否被访问过
}
function

排序

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function bubbleSort(arr) {
  var temp
  for (var outer = arr.length; outer > 1; --outer) {
    //从末尾遍历到2
    for (var inner = 0; inner < outer; ++inner) {
      //从0遍历outer-1
      if (arr[inner] > arr[inner+1]) {
        // 01比较 12比较 23比较
        // 01 12
        // 01
        temp = arr[inner]
        arr[inner] = arr[inner+1]
        arr[inner+1] = temp
      }
    }
  }
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function selectionSort(arr) {
  var min, temp
  for (var outer = 0; out < arr.length - 1; ++outer) {
    // 从0遍历到倒数第二个
    min = outer
    for (var inner = outer+1; inner < arr.length ; ++inner) {
      // 从outer+1（1开始）遍历到最后
      if (arr[inner] < arr[min]) {
        min = inner
      }
      // 0到最后中最小的值交换到0，
      // 1到最后中最小的值交换到1，
      // ...
      temp = outer
      outer = min
      min = temp
    }
  }
}

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function insertionSort(arr) {
  var temp, inner
  for (var outer = 1; outer < arr.length; ++outer) {
    // 从第二个遍历到最后（一个个插入）
    temp = arr[outer]
    inner = outer
    while (inner > 0 && arr[inner-1] >= temp) {
      // 一个一个向前查找前面的元素，大于temp则右移，不大于则把temp换过去再停止
      arr[inner] = arr[inner-1]
      --inner
    }
    arr[inner] = temp
  }
}

快速排序

适用于大型数据集合，小数据性能反而下降

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function qSort(arr) {
  if (arr.length === 0) {
    return []
  }
  var left = []
  var right = []
  var pivot = arr[0]
  for (var i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i])
    } else {
      right.push(arr[i])
    }
  }
  return qSort(left).concat(pivot, qSort(right))
}

检索

顺序查找

1
2
3
4
5
6
7
8
9
function seqSearch(arr, data) {
  for (var i = 0; i<arr.length; ++i) {
    if (arr[i] === data) {
      swap(arr[i], arr[i-1])// 自组织
      return i
    }
  }
  return -1
}

二分查找

相比顺序查找，二分查找算法比顺序查找更高效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function binSearch (arr, data) {
  var upperBound = arr.length - 1
  var lowerBound = 0
  while (lowerBound <= upperBound) {
    var mid = Math.floor((upperBound + lowerBound) / 2)
    if (arr[mid] < data) {
      lowerBound = mid + 1
    } else if (arr[mid] > data) {
      upperBound = mid - 1
    } else {
      return mid
    }
  }
  return -1
}

动态规划

动态规划从问题的底部开始解决（与递归相反），把小问题解决合并成一个整体解决方案

得到斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function recurFib (n) {
  if (n<2) {
    return n
  } else {
    return recurFib(n-1) + recurFib(n-2)
  }
}// 效率很差，没有保存之前的值

function dynFib (n) {
  var last = 1
  var nextLast = 1
  var result = 1
  for(var i = 2; i < n; ++i) {
    result = last + nextLast
    nextLast = last
    last = result
  }
  return result
}// 更强

背包问题

// 递归方式
function knapsack (capacity, size, value, n) {
  // 容量，大小arr，价值arr，数量
  // 递归方式
  if (n == 0 || capacity == 0) {
    return 0
  }
  if (size[n-1] > capacity) {
    // 装不下就找下一个
    return knapsack(capacity, size, value, n - 1)
  } else {
    // 装得下就比较大小看看装不装
    return Math.max(
      value[n - 1] + knapsack(capacity - size[n - 1], size, value, n - 1),
      knapsack(capacity, size, value, n - 1)
    )
  }
}