【crixus】通用数据结构和JavaScript实现综述

做前端的同学都是自学成才或半路出家，计算机基础的知识比较薄弱。特别是数据结构和算法这一点，今天整理了一般的数据结构和相应的JavaScript的实现情况，希望大家能帮助完善这方面的知识体系。(大卫亚设)。

1.Stack(堆栈)

Stack以后进先出(last in first out)为特征。人生中常见的Stack的例子是一堆书，你最后放上来的那本书以后会最先拿走。(伯纳德肖，生活)在浏览器的访问历史记录等情况下，单击“后退”按钮，最后访问的网站将首先在记录中弹出。

Stack通常有以下方法：推：将元素推送到堆栈顶部。pop:移除堆叠顶端的元素，并传回移除的元素。peek:返回堆栈顶部的元素length:返回堆栈中的元素数。Javascript中的Array本质上具有Stack特性，但您也可以从头开始实施Stack

Function Stack() {

=0；

={ }；

=function(值){

[]=值；

中选择另一种天花板类型。

}

=function () {

If (===0) {

Return undefined

}

-；

var result=[]；

删除[]；

Return result

}

=function () {

return[-1]；

}

=function () {

Return

}

}

2.Queue(队列)

Queue和Stack有一些相似之处。但是，Stack是先进先出，Queue是先进先出。Queue的生活例子就像排队坐公交车一样，第一位总是第一位乘坐。(威廉莎士比亚，模板，生活)例如，打印机的打印队列首先打印在最前面。

Queue通常有以下常用方法：enqueue:输入，将元素添加到队列末尾dequeue:列，删除队列头部的元素并返回删除的元素Array:获取队列中的第一个元素isEmpty:检查队列是否为空size:获取队列中的元素数javava

Function Queue() {

var collection=[]；

=function () {

集合(con)；

}

=function(元素){

COLLEC(ELEMEMENT)；

}

=function () {

return collec()；

}

=function () {

return collection[0]；

}

=function () {

Return collec====

}

=function () {

Return collec

}

}

优先级队列(Priority Queue)

队列还有一个升级版本，用于优先考虑每个元素。优先级较高的元素将添加到优先级较低的元素之前。区别主要在于enqueue方法的实现。

Function PriorityQueue() {

.

=function(元素){

if(){

COLLEC(ELEMEMENT)；

} else {

Var added=false

for(var I=0；I collecI) {

If (element [1]集合[I] [1]) {

Collec(i，0，element)；

Added=true

布雷克；

}

}

If(！Added) {

COLLEC(ELEMEMENT)；

}

}

}

}

测试：

var pQ=new priority queue()；

([‘GANNICUS’，3])；

(['spartacus '，1)

]); (['crixus', 2]); (['oenomaus', 4]); ();

结果：

[ [ '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) { // 节点中的数据 = element; // 指向下一个节点的指针 = null; } function LinkedList() { var length = 0; var head = null; = function () { return length; } = function () { return head; } = function (element) { var node = new Node(element); if (head == null) { head = node; } else { var currentNode = head; while ) { currentNode = curren; } curren = node; } length++; } = function (element) { var currentNode = head; var previousNode; if === element) { head = curren; } else { while !== element) { previousNode = currentNode; currentNode = curren; } = curren; } length--; } = function () { return length === 0; } = function (element) { var currentNode = head; var index = -1; while (currentNode) { index++; if === element) { return index; } currentNode = curren; } return -1; } At = function (index) { var currentNode = head; var count = 0; while (count < index) { count++; currentNode = curren; } return curren; } At = 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 = curren; } node.next = currentNode; = node; } length++; } At = function (index) { var currentNode = head; var previousNode; var currentIndex = 0; if (index < 0 || index >= length) { return null; } if (index === 0) { head = curren; } else { while (currentIndex < index) { currentIndex++; previousNode = currentNode; currentNode = curren; } = curren; } length--; return curren; } }

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 = []; = function (element) { return (element) !== -1); } = function () { return collection; } = function () { return collec; } = function (element) { if (!(element)) { collec(element); return true; } return false; } = function (element) { if ((element)) { index = collec(element); collec(index, 1); return true; } return false; } = function (otherSet) { var unionSet = new MySet(); var firstSet = (); var secondSet = o(); (function (e) { unionSet.add(e); }); (function (e) { unionSet.add(e); }); return unionSet; } = function (otherSet) { var intersectionSet = new MySet(); var firstSet = (); (function (e) { if (e)) { in(e); } }); return intersectionSet; } = function (otherSet) { var differenceSet = new MySet(); var firstSet = (); (function (e) { if (!o(e)) { di(e); } }); return differenceSet; } = function (otherSet) { var firstSet = (); return (function (value) { return o(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 < ; i++) { hash += (i); } return hash % max; } function HashTable() { let storage = []; const storageLimit = 4; = 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]); } } } = 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]; } } } } = 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) { = data; = left; = right; } } class BST { constructor() { = null; } add(data) { const node = ; if (node === null) { = new Node(data); return; } else { const searchTree = function (node) { if (data < node.data) { if === null) { node.left = new Node(data); return; } else if !== null) { return searchTree); } } else if (data > node.data) { if === null) { node.right = new Node(data); return; } else if !== null) { return searchTree); } } else { return null; } }; return searchTree(node); } } findMin() { let current = ; while !== null) { current = current.left; } return current.data; } findMax() { let current = ; while !== null) { current = current.right; } return current.data; } find(data) { let current = ; while !== data) { if (data < current.data) { current = current.left } else { current = current.right; } if (current === null) { return null; } } return current; } isPresent(data) { let current = ; 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 == null && node.right == null) { return null; } // node没有左侧子节点 if == null) { return node.right; } // node没有右侧子节点 if == null) { return node.left; } // node有两个子节点 var tempNode = node.right; while !== null) { tempNode = ; } node.data = ; node.right = removeNode, ); return node; } else if (data < node.data) { node.left = removeNode, data); return node; } else { node.right = removeNode, data); return node; } } = removeNode(, data); } }

测试一下：

const bst = new BST(); b(4); b(2); b(6); b(1); b(3); b(5); b(7); b(4); con()); con()); b(7); con()); con(4));

打印结果：

1 7 6 false

7. Trie(字典树，读音同try)

Trie也可以叫做Prefix Tree(前缀树)，也是一种搜索树。Trie分步骤存储数据，树中的每个节点代表一个步骤，trie常用于存储单词以便快速查找，比如实现单词的自动完成功能。 Trie中的每个节点都包含一个单词的字母，跟着树的分支可以可以拼写出一个完整的单词，每个节点还包含一个布尔值表示该节点是否是单词的最后一个字母。

Trie一般有以下方法：

• add：向字典树中增加一个单词
• isWord：判断字典树中是否包含某个单词
• print：返回字典树中的所有单词

/** * Trie的节点 */ function Node() { = new Map(); = false; = function () { = true; }; = function () { return ; } } function Trie() { = new Node(); = function (input, node = ) { if === 0) { node.setEnd(); return; } else if (!node.keys.has(input[0])) { node.keys.set(input[0], new Node()); return (1), node.keys.get(input[0])); } else { return (1), node.keys.get(input[0])); } } = function (word) { let node = ; while > 1) { if (!node.keys.has(word[0])) { return false; } else { node = node.keys.get(word[0]); word = word.substr(1); } } return (word) && node.keys.get(word).isEnd()) ? true : false; } = function () { let words = new Array(); let search = function (node = , string) { if != 0) { for (let letter of node.keys.keys()) { searc(letter), (letter)); } if ()) { words.push(string); } } else { > 0 ? words.push(string) : undefined; return; } }; search(, 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 < gra; i++) { nodesLen[i] = Infinity; } nodesLen[root] = 0; var queue = [root]; var current; while != 0) { current = queue.shift(); var curConnected = graph[current]; var neighborIdx = []; var idx = curConnec(1); while (idx != -1) { neig(idx); idx = curConnec(1, idx + 1); } for (var j = 0; j < neig; 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] ]; con(bfs(graph, 1));

打印：

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

最后，推荐大家使用Fundebug，一款很好用的BUG监控工具~

本文旨在向广大前端同学普及常见的数据结构，本人对这一领域也只是初窥门径，说的有差池的地方欢迎指出。也希望大家能打牢基础，在这条路上走的更高更远!