关于前端:JS中的数据结构

1. Stack（栈）

Stack 的特点是后进先出（last in first out）。生存中常见的 Stack 的例子比方一摞书，你最初放上去的那本你之后会最先拿走；又比方浏览器的拜访历史，当点击返回按钮，最初拜访的网站最先从历史记录中弹出。

Stack 个别具备以下办法：

1. push：将一个元素推入栈顶
2. pop：移除栈顶元素，并返回被移除的元素
3. peek：返回栈顶元素
4. length：返回栈中元素的个数

Javascript 的 Array 天生具备了 Stack 的个性，但咱们也能够从头实现一个 Stack 类：

function Stack() {
  this.count = 0;
  this.storage = {};


  this.push = function (value) {this.storage[this.count] = value;
    this.count++;
  }


  this.pop = function () {if (this.count === 0) {return undefined;}
    this.count--;
    var result = this.storage[this.count];
    delete this.storage[this.count];
    return result;
  }


  this.peek = function () {return this.storage[this.count - 1];
  }


  this.size = function () {return this.count;}
}

2. Queue（队列）

Queue 和 Stack 有一些相似，不同的是 Stack 是先进后出，而 Queue 是先进先出。Queue 在生活中的例子比方排队上公交，排在第一个的总是最先上车；又比方打印机的打印队列，排在后面的最先打印。

Queue 个别具备以下常见办法：

1. enqueue：入列，向队列尾部减少一个元素
2. dequeue：出列，移除队列头部的一个元素并返回被移除的元素
3. front：获取队列的第一个元素
4. isEmpty：判断队列是否为空
5. size：获取队列中元素的个数

Javascript 中的 Array 曾经具备了 Queue 的一些个性，所以咱们能够借助 Array 实现一个 Queue 类型：

function Queue() {var collection = [];


  this.print = function () {console.log(collection);
  }


  this.enqueue = function (element) {collection.push(element);
  }


  this.dequeue = function () {return collection.shift();
  }


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


  this.isEmpty = function () {return collection.length === 0;}


  this.size = function () {return collection.length;}
}

Priority Queue（优先队列）

Queue 还有个降级版本，给每个元素赋予优先级，优先级高的元素入列时将排到低优先级元素之前。区别次要是 enqueue 办法的实现：

function PriorityQueue() {


  ...


  this.enqueue = function (element) {if (this.isEmpty()) {collection.push(element);
    } else {
      var added = false;
      for (var i = 0; i < collection.length; i++) {if (element[1] < collection[i][1]) {collection.splice(i, 0, element);
          added = true;
          break;
        }
      }
      if (!added) {collection.push(element);
      }
    }
  }
}

测试一下：

var pQ = new PriorityQueue();


pQ.enqueue(['gannicus', 3]);
pQ.enqueue(['spartacus', 1]);
pQ.enqueue(['crixus', 2]);
pQ.enqueue(['oenomaus', 4]);


pQ.print();

后果：

[[ 'spartacus', 1],
  ['crixus', 2],
  ['gannicus', 3],
  ['oenomaus', 4]
]

3. Linked List（链表）

顾名思义，链表是一种链式数据结构，链上的每个节点蕴含两种信息：节点自身的数据和指向下一个节点的指针。链表和传统的数组都是线性的数据结构，存储的都是一个序列的数据，但也有很多区别，如下表：

一个单向链表通常具备以下办法：

1. size：返回链表中节点的个数
2. head：返回链表中的头部元素
3. add：向链表尾部减少一个节点
4. remove：删除某个节点
5. indexOf：返回某个节点的 index
6. elementAt：返回某个 index 处的节点
7. addAt：在某个 index 处插入一个节点
8. removeAt：删除某个 index 处的节点

单向链表的 Javascript 实现：

/**
 * 链表中的节点 
 */
function Node(element) {
  // 节点中的数据
  this.element = element;
  // 指向下一个节点的指针
  this.next = null;
}


function LinkedList() {
  var length = 0;
  var head = null;


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


  this.head = function () {return head;}


  this.add = function (element) {var node = new Node(element);
    if (head == null) {head = node;} else {
      var currentNode = head;


      while (currentNode.next) {currentNode = currentNode.next;}


      currentNode.next = node;
    }
    length++;
  }


  this.remove = function (element) {
    var currentNode = head;
    var previousNode;
    if (currentNode.element === element) {head = currentNode.next;} else {while (currentNode.element !== element) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }
      previousNode.next = currentNode.next;
    }
    length--;
  }


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


  this.indexOf = function (element) {
    var currentNode = head;
    var index = -1;
    while (currentNode) {
      index++;
      if (currentNode.element === element) {return index;}
      currentNode = currentNode.next;
    }


    return -1;
  }


  this.elementAt = function (index) {
    var currentNode = head;
    var count = 0;
    while (count < index) {
      count++;
      currentNode = currentNode.next;
    }
    return currentNode.element;
  }


  this.addAt = function (index, element) {var node = new Node(element);
    var currentNode = head;
    var previousNode;
    var currentIndex = 0;


    if (index > length) {return false;}


    if (index === 0) {
      node.next = currentNode;
      head = node;
    } else {while (currentIndex < index) {
        currentIndex++;
        previousNode = currentNode;
        currentNode = currentNode.next;
      }
      node.next = currentNode;
      previousNode.next = node;
    }
    length++;
  }


  this.removeAt = function (index) {
    var currentNode = head;
    var previousNode;
    var currentIndex = 0;
    if (index < 0 || index >= length) {return null;}
    if (index === 0) {head = currentIndex.next;} else {while (currentIndex < index) {
        currentIndex++;
        previousNode = currentNode;
        currentNode = currentNode.next;
      }
      previousNode.next = currentNode.next;
    }
    length--;
    return currentNode.element;
  }
}

4. Set（汇合）

汇合是数学中的一个基本概念，示意具备某种个性的对象汇总成的个体。在 ES6 中也引入了汇合类型 Set，Set 和 Array 有肯定水平的类似，不同的是 Set 中不容许呈现反复的元素而且是无序的。

一个典型的 Set 应该具备以下办法：

1. values：返回汇合中的所有元素
2. size：返回汇合中元素的个数
3. has：判断汇合中是否存在某个元素
4. add：向汇合中增加元素
5. remove：从汇合中移除某个元素
6. union：返回两个汇合的并集
7. intersection：返回两个汇合的交加
8. difference：返回两个汇合的差集
9. subset：判断一个汇合是否为另一个汇合的子集

应用 Javascript 能够将 Set 进行如下实现，为了区别于 ES6 中的 Set 命名为 MySet：

function MySet() {var collection = [];
  this.has = function (element) {return (collection.indexOf(element) !== -1);
  }


  this.values = function () {return collection;}


  this.size = function () {return collection.length;}


  this.add = function (element) {if (!this.has(element)) {collection.push(element);
      return true;
    }
    return false;
  }


  this.remove = function (element) {if (this.has(element)) {index = collection.indexOf(element);
      collection.splice(index, 1);
      return true;
    }
    return false;
  }


  this.union = function (otherSet) {var unionSet = new MySet();
    var firstSet = this.values();
    var secondSet = otherSet.values();
    firstSet.forEach(function (e) {unionSet.add(e);
    });
    secondSet.forEach(function (e) {unionSet.add(e);
    });
    return unionSet;
  }


  this.intersection = function (otherSet) {var intersectionSet = new MySet();
    var firstSet = this.values();
    firstSet.forEach(function (e) {if (otherSet.has(e)) {intersectionSet.add(e);
      }
    });
    return intersectionSet;
  }


  this.difference = function (otherSet) {var differenceSet = new MySet();
    var firstSet = this.values();
    firstSet.forEach(function (e) {if (!otherSet.has(e)) {differenceSet.add(e);
      }
    });
    return differenceSet;
  }


  this.subset = function (otherSet) {var firstSet = this.values();
    return firstSet.every(function (value) {return otherSet.has(value);
    });
  }
}

5. Hash Table（哈希表 / 散列表）

Hash Table 是一种用于存储键值对（key value pair）的数据结构，因为 Hash Table 依据 key 查问 value 的速度很快，所以它罕用于实现 Map、Dictinary、Object 等数据结构。如上图所示，Hash Table 外部应用一个 hash 函数将传入的键转换成一串数字，而这串数字将作为键值对理论的 key，通过这个 key 查问对应的 value 十分快，工夫复杂度将达到 O(1)。Hash 函数要求雷同输出对应的输入必须相等，而不同输出对应的输入必须不等，相当于对每对数据打上惟一的指纹。

一个 Hash Table 通常具备下列办法：

1. add：减少一组键值对
2. remove：删除一组键值对
3. lookup：查找一个键对应的值

一个繁难版本的 Hash Table 的 Javascript 实现：

function hash(string, max) {
  var hash = 0;
  for (var i = 0; i < string.length; i++) {hash += string.charCodeAt(i);
  }
  return hash % max;
}


function HashTable() {let storage = [];
  const storageLimit = 4;


  this.add = function (key, value) {var index = hash(key, storageLimit);
    if (storage[index] === undefined) {storage[index] = [[key, value]
      ];
    } else {
      var inserted = false;
      for (var i = 0; i < storage[index].length; i++) {if (storage[index][i][0] === key) {storage[index][i][1] = value;
          inserted = true;
        }
      }
      if (inserted === false) {storage[index].push([key, value]);
      }
    }
  }


  this.remove = function (key) {var index = hash(key, storageLimit);
    if (storage[index].length === 1 && storage[index][0][0] === key) {delete storage[index];
    } else {for (var i = 0; i < storage[index]; i++) {if (storage[index][i][0] === key) {delete storage[index][i];
        }
      }
    }
  }


  this.lookup = function (key) {var index = hash(key, storageLimit);
    if (storage[index] === undefined) {return undefined;} else {for (var i = 0; i < storage[index].length; i++) {if (storage[index][i][0] === key) {return storage[index][i][1];
        }
      }
    }
  }
}

6. Tree（树）

顾名思义，Tree 的数据结构和自然界中的树极其类似，有根、树枝、叶子，如上图所示。Tree 是一种多层数据结构，与 Array、Stack、Queue 相比是一种非线性的数据结构，在进行插入和搜寻操作时很高效。在形容一个 Tree 时常常会用到下列概念：

1. Root（根）：代表树的根节点，根节点没有父节点
2. Parent Node（父节点）：一个节点的间接下级节点，只有一个
3. Child Node（子节点）：一个节点的间接上级节点，可能有多个
4. Siblings（兄弟节点）：具备雷同父节点的节点
5. Leaf（叶节点）：没有子节点的节点
6. Edge（边）：两个节点之间的连接线
7. Path（门路）：从源节点到指标节点的间断边
8. Height of Node（节点的高度）：示意节点与叶节点之间的最长门路上边的个数
9. Height of Tree（树的高度）：即根节点的高度
10. Depth of Node（节点的深度）：示意从根节点到该节点的边的个数
11. Degree of Node（节点的度）：示意子节点的个数

咱们以二叉查找树为例，展现树在 Javascript 中的实现。在二叉查找树中，即每个节点最多只有两个子节点，而左侧子节点小于以后节点，而右侧子节点大于以后节点，如图所示：

一个二叉查找树应该具备以下罕用办法：

1. add：向树中插入一个节点
2. findMin：查找树中最小的节点
3. findMax：查找树中最大的节点
4. find：查找树中的某个节点
5. isPresent：判断某个节点在树中是否存在
6. remove：移除树中的某个节点

以下是二叉查找树的 Javascript 实现：

class Node {constructor(data, left = null, right = null) {
    this.data = data;
    this.left = left;
    this.right = right;
  }
}


class BST {constructor() {this.root = null;}


  add(data) {
    const node = this.root;
    if (node === null) {this.root = new Node(data);
      return;
    } else {const searchTree = function (node) {if (data < node.data) {if (node.left === null) {node.left = new Node(data);
            return;
          } else if (node.left !== null) {return searchTree(node.left);
          }
        } else if (data > node.data) {if (node.right === null) {node.right = new Node(data);
            return;
          } else if (node.right !== null) {return searchTree(node.right);
          }
        } else {return null;}
      };
      return searchTree(node);
    }
  }


  findMin() {
    let current = this.root;
    while (current.left !== null) {current = current.left;}
    return current.data;
  }


  findMax() {
    let current = this.root;
    while (current.right !== null) {current = current.right;}
    return current.data;
  }


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


  isPresent(data) {
    let current = this.root;
    while (current) {if (data === current.data) {return true;}
      if (data < current.data) {current = current.left;} else {current = current.right;}
    }
    return false;
  }


  remove(data) {const removeNode = function (node, data) {if (node == null) {return null;}
      if (data == node.data) {
        // node 没有子节点
        if (node.left == null && node.right == null) {return null;}
        // node 没有左侧子节点
        if (node.left == null) {return node.right;}
        // node 没有右侧子节点
        if (node.right == null) {return node.left;}
        // node 有两个子节点
        var tempNode = node.right;
        while (tempNode.left !== null) {tempNode = tempNode.left;}
        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;
      }
    }
    this.root = removeNode(this.root, data);
  }
}

测试一下：

const bst = new BST();


bst.add(4);
bst.add(2);
bst.add(6);
bst.add(1);
bst.add(3);
bst.add(5);
bst.add(7);
bst.remove(4);
console.log(bst.findMin());
console.log(bst.findMax());
bst.remove(7);
console.log(bst.findMax());
console.log(bst.isPresent(4));

打印后果：

1
7
6
false

7. Trie（字典树，读音同 try）

Trie 也能够叫做 Prefix Tree（前缀树），也是一种搜寻树。Trie 分步骤存储数据，树中的每个节点代表一个步骤，trie 罕用于存储单词以便疾速查找，比方实现单词的主动实现性能。Trie 中的每个节点都蕴含一个单词的字母，跟着树的分支能够能够拼写出一个残缺的单词，每个节点还蕴含一个布尔值示意该节点是否是单词的最初一个字母。

Trie 个别有以下办法：

1. add：向字典树中减少一个单词
2. isWord：判断字典树中是否蕴含某个单词
3. print：返回字典树中的所有单词

/**
 * Trie 的节点
 */
function Node() {this.keys = new Map();
  this.end = false;
  this.setEnd = function () {this.end = true;};
  this.isEnd = function () {return this.end;}
}


function Trie() {this.root = new Node();


  this.add = function (input, node = this.root) {if (input.length === 0) {node.setEnd();
      return;
    } else if (!node.keys.has(input[0])) {node.keys.set(input[0], new Node());
      return this.add(input.substr(1), node.keys.get(input[0]));
    } else {return this.add(input.substr(1), node.keys.get(input[0]));
    }
  }


  this.isWord = function (word) {
    let node = this.root;
    while (word.length > 1) {if (!node.keys.has(word[0])) {return false;} else {node = node.keys.get(word[0]);
        word = word.substr(1);
      }
    }
    return (node.keys.has(word) && node.keys.get(word).isEnd()) ? true : false;
  }


  this.print = function () {let words = new Array();
    let search = function (node = this.root, string) {if (node.keys.size != 0) {for (let letter of node.keys.keys()) {search(node.keys.get(letter), string.concat(letter));
        }
        if (node.isEnd()) {words.push(string);
        }
      } else {string.length > 0 ? words.push(string) : undefined;
        return;
      }
    };
    search(this.root, new String());
    return words.length > 0 ? words : null;
  }
}

8. Graph（图）

Graph 是节点（或顶点）以及它们之间的连贯（或边）的汇合。Graph 也能够称为 Network（网络）。依据节点之间的连贯是否有方向又能够分为 Directed Graph（有向图）和 Undrected Graph（无向图）。Graph 在理论生存中有很多用处，比方：导航软件计算最佳门路，社交软件进行好友举荐等等。

Graph 通常有两种表达方式：

Adjaceny List（邻接列表）：

邻接列表能够示意为左侧是节点的列表，右侧列出它所连贯的所有其余节点。

和 Adjacency Matrix（邻接矩阵）：

邻接矩阵用矩阵来示意节点之间的连贯关系，每行或者每列示意一个节点，行和列的交叉处的数字示意节点之间的关系：0 示意没用连贯，1 示意有连贯，大于 1 示意不同的权重。

拜访 Graph 中的节点须要应用遍历算法，遍历算法又分为广度优先和深度优先，次要用于确定指标节点和根节点之间的间隔，

在 Javascript 中，Graph 能够用一个矩阵（二维数组）示意，广度优先搜索算法能够实现如下：

function bfs(graph, root) {var nodesLen = {};


  for (var i = 0; i < graph.length; i++) {nodesLen[i] = Infinity;
  }


  nodesLen[root] = 0;


  var queue = [root];
  var current;


  while (queue.length != 0) {current = queue.shift();


    var curConnected = graph[current];
    var neighborIdx = [];
    var idx = curConnected.indexOf(1);
    while (idx != -1) {neighborIdx.push(idx);
      idx = curConnected.indexOf(1, idx + 1);
    }


    for (var j = 0; j < neighborIdx.length; j++) {if (nodesLen[neighborIdx[j]] == Infinity) {nodesLen[neighborIdx[j]] = nodesLen[current] + 1;
        queue.push(neighborIdx[j]);
      }
    }
  }


  return nodesLen;
}

测试一下：

var graph = [[0, 1, 1, 1, 0],
  [0, 0, 1, 0, 0],
  [1, 1, 0, 0, 0],
  [0, 0, 0, 1, 0],
  [0, 1, 0, 0, 0]
];


console.log(bfs(graph, 1));

打印：

{
  0: 2,
  1: 0,
  2: 1,
  3: 3,
  4: Infinity
}