业务研究

当前位置:首页 > 新闻中心> 业务研究

Javascript中的8种常见数据结构

发布时间:2020/8/3 16:23:03   来源:原创  作者:admin  浏览量:

1.Stack(栈)

image.png

堆栈遵循LIFO(后进先出)的原则。如果你把书堆叠起来,上面的书会比下面的书先拿。或者当你在网上浏览时,后退按钮会引导你到最近浏览的页面。

Stack具有以下常见方法:

· push:输入一个新元素

· pop:删除顶部元素,返回删除的元素

· peek:返回顶部元素

· length:返回堆栈中元素的数量

Javascript中的数组具有Stack的属性,但是我们使用 function Stack() 从头开始构建Stack

1. function Stack() { 

2.     this.count = 0; 

3.   this.storage = {}; 

4.  

5.   this.push = function (value) { 

6.     this.storage[this.count] = value; 

7.     this.count++; 

8.   } 

9.  

10.   this.pop = function () { 

11.     if (this.count === 0) { 

12.       return undefined; 

13.     } 

14.     this.count--; 

15.     var result = this.storage[this.count]; 

16.     delete this.storage[this.count]; 

17.     return result; 

18.   } 

19.  

20.   this.peek = function () { 

21.     return this.storage[this.count - 1]; 

22.   } 

23.  

24.   this.size = function () { 

25.     return this.count

26.   } 

27. 

2.Queue(队列)

image.png

Queue与Stack类似。唯一不同的是,Queue使用的是FIFO原则(先进先出)。换句话说,当你排队等候公交车时,队列中的第一个总是先上车。

队列具有以下方法:

· enqueue:输入队列,在最后添加一个元素

· dequeue:离开队列,删除前元素并返回

· front:得到第一个元素

· isEmpty:确定队列是否为空

· size:获取队列中元素的数量

JavaScript中的数组具有Queue的某些属性,因此我们可以使用数组来构造Queue的示例:

1. function Queue() { 

2.   var collection = []; 

3.   this.print = function () { 

4.     console.log(collection); 

5.   } 

6.   this.enqueue = function (element) { 

7.     collection.push(element); 

8.   } 

9.   this.dequeue = function () { 

10.     return collection.shift(); 

11.   } 

12.   this.front = function () { 

13.     return collection[0]; 

14.   } 

15.  

16.   this.isEmpty = function () { 

17.     return collection.length === 0; 

18.   } 

19.   this.size = function () { 

20.     return collection.length; 

21.   } 

22. 

优先队列

队列还有另一个高级版本。为每个元素分配优先级,并将根据优先级对它们进行排序:

1. function PriorityQueue() { 

2.  

3.   ... 

4.  

5.   this.enqueue = function (element) { 

6.     if (this.isEmpty()) { 

7.       collection.push(element); 

8.     } else { 

9.       var added = false

10.       for (var i = 0; i < collection.length; i++) { 

11.         if (element[1] < collection[i][1]) { 

12.           collection.splice(i, 0, element); 

13.           added = true

14.           break; 

15.         } 

16.       } 

17.       if (!added) { 

18.         collection.push(element); 

19.       } 

20.     } 

21.   } 

22. 

测试一下:

1. var pQ = new PriorityQueue(); 

2. pQ.enqueue([ gannicus , 3]); 

3. pQ.enqueue([ spartacus , 1]); 

4. pQ.enqueue([ crixus , 2]); 

5. pQ.enqueue([ oenomaus , 4]); 

6. pQ.print(); 

返回

1. 

2.   [  spartacus , 1 ], 

3.   [  crixus , 2 ], 

4.   [  gannicus , 3 ], 

5.   [  oenomaus , 4 ] 

6. 

3. Linked List(链表)

image.png

从字面上看,链表是一个链式数据结构,每个节点由两个信息组成:节点的数据和指向下一个节点的指针。链表和传统数组都是线性数据结构,具有序列化的存储方式。当然,它们也有差异:

image.png

单边链表通常具有以下方法:

· size:返回节点数

· head:返回头部的元素

· add:在尾部添加另一个节点

· remove:删除某些节点

· indexOf:返回节点的索引

· elementAt:返回索引的节点

· addAt:在特定索引处插入节点

· removeAt:删除特定索引处的节点

1. /** 链表中的节点 **/ 

2. function Node(element) { 

3.     // 节点中的数据 

4.     this.element = element; 

5.     // 指向下一个节点的指针 

6.     this.next = null

7. 

8. function LinkedList() { 

9.   var length = 0; 

10.   var head = null

11.   this.size = function () { 

12.     return length; 

13.   } 

14.   this.head = function () { 

15.     return head; 

16.   } 

17.   this.add = function (element) { 

18.     var node = new Node(element); 

19.     if (head == null) { 

20.       head = node; 

21.     } else { 

22.       var currentNode = head; 

23.       while (currentNode.next) { 

24.         currentNode = currentNode.next

25.       } 

26.       currentNode.next = node; 

27.     } 

28.     length++; 

29.   } 

30.   this.remove = function (element) { 

31.     var currentNode = head; 

32.     var previousNode; 

33.     if (currentNode.element === element) { 

34.       head = currentNode.next

35.     } else { 

36.       while (currentNode.element !== element) { 

37.         previousNode = currentNode; 

38.         currentNode = currentNode.next

39.       } 

40.       previousNode.next = currentNode.next

41.     } 

42.     length--; 

43.   } 

44.   this.isEmpty = function () { 

45.     return length === 0; 

46.   } 

47.   this.indexOf = function (element) { 

48.     var currentNode = head; 

49.     var index = -1; 

50.     while (currentNode) { 

51.       index++; 

52.       if (currentNode.element === element) { 

53.         return index

54.       } 

55.       currentNode = currentNode.next

56.     } 

57.     return -1; 

58.   } 

59.   this.elementAt = function (index) { 

60.     var currentNode = head; 

61.     var count = 0; 

62.     while (count < index) { 

63.       count++; 

64.       currentNode = currentNode.next

65.     } 

66.     return currentNode.element; 

67.   } 

68.   this.addAt = function (index, element) { 

69.     var node = new Node(element); 

70.     var currentNode = head; 

71.     var previousNode; 

72.     var currentIndex = 0; 

73.     if (index > length) { 

74.       return false

75.     } 

76.     if (index === 0) { 

77.       node.next = currentNode; 

78.       head = node; 

79.     } else { 

80.       while (currentIndex < index) { 

81.         currentIndex++; 

82.         previousNode = currentNode; 

83.         currentNode = currentNode.next

84.       } 

85.       node.next = currentNode; 

86.       previousNode.next = node; 

87.     } 

88.     length++; 

89.   } 

90.   this.removeAt = function (index) { 

91.     var currentNode = head; 

92.     var previousNode; 

93.     var currentIndex = 0; 

94.     if (index < 0 || index >= length) { 

95.       return null

96.     } 

97.     if (index === 0) { 

98.       head = currentIndex.next

99.     } else { 

100.       while (currentIndex < index) { 

101.         currentIndex++; 

102.         previousNode = currentNode; 

103.         currentNode = currentNode.next

104.       } 

105.       previousNode.next = currentNode.next

106.     } 

107.     length--; 

108.     return currentNode.element; 

109.   } 

110. 

4. Set(集合)

image.png

集合是数学的基本概念:定义明确且不同的对象的集合。ES6引入了集合的概念,它与数组有一定程度的相似性。但是,集合不允许重复元素,也不会被索引。

一个典型的集合具有以下方法:

· values:返回集合中的所有元素

· size:返回元素个数

· has:确定元素是否存在

· add:将元素插入集合

· remove:从集合中删除元素

· union:返回两组交集

· difference:返回两组的差

· subset:确定某个集合是否是另一个集合的子集

为了区分ES6中的 set,我们在以下示例中声明为 MySet:

1. function MySet() { 

2.   var collection = []; 

3.   this.has = function (element) { 

4.     return (collection.indexOf(element) !== -1); 

5.   } 

6.   this.values = function () { 

7.     return collection; 

8.   } 

9.   this.size = function () { 

10.     return collection.length; 

11.   } 

12.   this.add = function (element) { 

13.     if (!this.has(element)) { 

14.       collection.push(element); 

15.       return true

16.     } 

17.     return false

18.   } 

19.   this.remove = function (element) { 

20.     if (this.has(element)) { 

21.       index = collection.indexOf(element); 

22.       collection.splice(index, 1); 

23.       return true

24.     } 

25.     return false

26.   } 

27.   this.union = function (otherSet) { 

28.     var unionSet = new MySet(); 

29.     var firstSet = this.values(); 

30.     var secondSet = otherSet.values(); 

31.     firstSet.forEach(function (e) { 

32.       unionSet.add(e); 

33.     }); 

34.     secondSet.forEach(function (e) { 

35.       unionSet.add(e); 

36.     }); 

37.     return unionSet;  } 

38.   this.intersection = function (otherSet) { 

39.     var intersectionSet = new MySet(); 

40.     var firstSet = this.values(); 

41.     firstSet.forEach(function (e) { 

42.       if (otherSet.has(e)) { 

43.         intersectionSet.add(e); 

44.       } 

45.     }); 

46.     return intersectionSet; 

47.   } 

48.   this.difference = function (otherSet) { 

49.     var differenceSet = new MySet(); 

50.     var firstSet = this.values(); 

51.     firstSet.forEach(function (e) { 

52.       if (!otherSet.has(e)) { 

53.         differenceSet.add(e); 

54.       } 

55.     }); 

56.     return differenceSet; 

57.   } 

58.   this.subset = function (otherSet) { 

59.     var firstSet = this.values(); 

60.     return firstSet.every(function (value) { 

61.       return otherSet.has(value); 

62.     }); 

63.   } 

64. 

5. Hast table(哈希表)

 

哈希表是一种键值数据结构。由于通过键值查询的速度快如闪电,所以常用于Map、Dictionary或Object数据结构中。如上图所示,哈希表使用哈希函数(hash function)将键转换为数字列表,这些数字作为对应键的值。要快速使用键获取价值,时间复杂度可以达到O(1)。相同的键必须返回相同的值——这是哈希函数的基础。

哈希表具有以下方法:

· add:添加键值对

· remove:删除键值对

· lookup:使用键查找对应的值

一个Javascript中简化的哈希表的例子:

1. function hash(string, max) { 

2.   var hash = 0; 

3.   for (var i = 0; i < string.length; i++) { 

4.     hash += string.charCodeAt(i); 

5.   } 

6.   return hash % max

7. 

8.  

9. function HashTable() { 

10.   let storage = []; 

11.   const storageLimit = 4; 

12.  

13.   this.add = function (key, value) { 

14.     var index = hash(key, storageLimit); 

15.     if (storage[index] === undefined) { 

16.       storage[index] = [ 

17.         [key, value] 

18.       ]; 

19.     } else { 

20.       var inserted = false

21.       for (var i = 0; i < storage[index].length; i++) { 

22.         if (storage[index][i][0] === key) { 

23.           storage[index][i][1] = value; 

24.           inserted = true

25.         } 

26.       } 

27.       if (inserted === false) { 

28.         storage[index].push([key, value]); 

29.       } 

30.     } 

31.   } 

32.  

33.   this.remove = function (key) { 

34.     var index = hash(key, storageLimit); 

35.     if (storage[index].length === 1 && storage[index][0][0] === key) { 

36.       delete storage[index]; 

37.     } else { 

38.       for (var i = 0; i < storage[index]; i++) { 

39.         if (storage[index][i][0] === key) { 

40.           delete storage[index][i]; 

41.         } 

42.       } 

43.     } 

44.   } 

45.  

46.   this.lookup = function (key) { 

47.     var index = hash(key, storageLimit); 

48.     if (storage[index] === undefined) { 

49.       return undefined; 

50.     } else { 

51.       for (var i = 0; i < storage[index].length; i++) { 

52.         if (storage[index][i][0] === key) { 

53.           return storage[index][i][1]; 

54.         } 

55.       } 

56.     } 

57.   } 

58. 

6. Tree(树)

image.png

Tree(树)数据结构是多层结构。与Array,Stack和Queue相比,它也是一种非线性数据结构。这种结构在插入和搜索操作时效率很高。我们来看看树型数据结构的一些概念。

· root:树的根节点,无父节点

· parent node:上层的直接节点,只有一个

· child node:下层的直接节点可以有多个

· siblings:共享同一个父节点

· leaf:没有孩子的节点

· Edge:节点之间的分支或链接

· path:从起始节点到目标节点的边

· Height of Nod:特定节点到叶节点的最长路径的边数

· Height of Tree:根节点到叶节点的最长路径的边数

· Depth of Node:从根节点到特定节点的边数

· Degree of Node:子节点数

这里以二叉树为例。每个节点最多有两个节点,左边节点比当前节点小,右边节点比当前节点大。

image.png


二叉树中的常用方法:

· add:将节点插入树

· findMin:获取最小节点

· findMax:获取最大节点

· find:搜索特定节点

· isPresent:确定某个节点的存在

· remove:从树中删除节点

JavaScript中的示例:

1. class Node { 

2.   constructor(data, left = nullright = null) { 

3.     this.data = data; 

4.     this.left = left

5.     this.right = right

6.   } 

7. 

8.  

9. class BST { 

10.   constructor() { 

11.     this.root = null

12.   } 

13.  

14.   add(data) { 

15.     const node = this.root; 

16.     if (node === null) { 

17.       this.root = new Node(data); 

18.       return

19.     } else { 

20.       const searchTree = function (node) { 

21.         if (data < node.data) { 

22.           if (node.left === null) { 

23.             node.left = new Node(data); 

24.             return

25.           } else if (node.left !== null) { 

26.             return searchTree(node.left); 

27.           } 

28.         } else if (data > node.data) { 

29.           if (node.right === null) { 

30.             node.right = new Node(data); 

31.             return

32.           } else if (node.right !== null) { 

33.             return searchTree(node.right); 

34.           } 

35.         } else { 

36.           return null

37.         } 

38.       }; 

39.       return searchTree(node); 

40.     } 

41.   } 

42.  

43.   findMin() { 

44.     let current = this.root; 

45.     while (current.left !== null) { 

46.       current = current.left

47.     } 

48.     return current.data; 

49.   } 

50.  

51.   findMax() { 

52.     let current = this.root; 

53.     while (current.right !== null) { 

54.       current = current.right

55.     } 

56.     return current.data; 

57.   } 

58.  

59.   find(data) { 

60.     let current = this.root; 

61.     while (current.data !== data) { 

62.       if (data < current.data) { 

63.         current = current.left 

64.       } else { 

65.         current = current.right

66.       } 

67.       if (current === null) { 

68.         return null

69.       } 

70.     } 

71.     return current

72.   } 

73.  

74.   isPresent(data) { 

75.     let current = this.root; 

76.     while (current) { 

77.       if (data === current.data) { 

78.         return true

79.       } 

80.       if (data < current.data) { 

81.         current = current.left

82.       } else { 

83.         current = current.right

84.       } 

85.     } 

86.     return false

87.   } 

88.  

89.   remove(data) { 

90.     const removeNode = function (node, data) { 

91.       if (node == null) { 

92.         return null

93.       } 

94.       if (data == node.data) { 

95.         // no child node 

96.         if (node.left == null && node.right == null) { 

97.           return null

98.         } 

99.         // no left node 

100.         if (node.left == null) { 

101.           return node.right

102.         } 

103.         // no right node 

104.         if (node.right == null) { 

105.           return node.left

106.         } 

107.         // has 2 child nodes 

108.         var tempNode = node.right

109.         while (tempNode.left !== null) { 

110.           tempNode = tempNode.left

111.         } 

112.         node.data = tempNode.data; 

113.         node.right = removeNode(node.right, tempNode.data); 

114.         return node; 

115.       } else if (data < node.data) { 

116.         node.left = removeNode(node.left, data); 

117.         return node; 

118.       } else { 

119.         node.right = removeNode(node.right, data); 

120.         return node; 

121.       } 

122.     } 

123.     this.root = removeNode(this.root, data); 

124.   } 

125. 

测试一下:

1. const bst = new BST(); 

2. bst.add(4); 

3. bst.add(2); 

4. bst.add(6); 

5. bst.add(1); 

6. bst.add(3); 

7. bst.add(5); 

8. bst.add(7); 

9. bst.remove(4); 

10. console.log(bst.findMin()); 

11. console.log(bst.findMax()); 

12. bst.remove(7); 

13. console.log(bst.findMax()); 

14. console.log(bst.isPresent(4)); 

15.  

16. 

17. 

18. 

19. false 

7. Trie (发音为 “try”)

image.png

Trie或“前缀树”也是搜索树的一种。Trie分步存储数据——树中的每个节点代表一个步骤。Trie是用来存储词汇的,所以它可以快速搜索,特别是自动完成功能。

Trie中的每个节点都有一个字母——分支之后可以组成一个完整的单词。它还包括一个布尔指示符,以显示这是否是最后一个字母。

Trie具有以下方法:

· add:在字典树中插入一个单词

· isWord:确定树是否由某些单词组成

· print:返回树中的所有单词

1. /** Node in Trie **/ 

2. function Node() { 

3.   this.keys = new Map(); 

4.   this.end = false

5.   this.setEnd = function () { 

6.     this.end = true

7.   }; 

8.   this.isEnd = function () { 

9.     return this.end

10.   } 

11. 

12.  

13. function Trie() { 

14.   this.root = new Node(); 

15.   this.add = function (input, node = this.root) { 

16.     if (input.length === 0) { 

17.       node.setEnd(); 

18.       return

19.     } else if (!node.keys.has(input[0])) { 

20.       node.keys.set(input[0], new Node()); 

21.       return this.add(input.substr(1), node.keys.get(input[0])); 

22.     } else { 

23.       return this.add(input.substr(1), node.keys.get(input[0])); 

24.     } 

25.   } 

26.   this.isWord = function (word) { 

27.     let node = this.root; 

28.     while (word.length > 1) { 

29.       if (!node.keys.has(word[0])) { 

30.         return false

31.       } else { 

32.         node = node.keys.get(word[0]); 

33.         word = word.substr(1); 

34.       } 

35.     } 

36.     return (node.keys.has(word) && node.keys.get(word).isEnd()) ? true : false

37.   } 

38.   this.print = function () { 

39.     let words = new Array(); 

40.     let search = function (node = this.root, string) { 

41.       if (node.keys.size != 0) { 

42.         for (let letter of node.keys.keys()) { 

43.           search(node.keys.get(letter), string.concat(letter)); 

44.         } 

45.         if (node.isEnd()) { 

46.           words.push(string); 

47.         } 

48.       } else { 

49.         string.length > 0 ? words.push(string) : undefined; 

50.         return

51.       } 

52.     }; 

53.     search(this.root, new String()); 

54.     return words.length > 0 ? words : null

55.   } 

56. 

8. Graph(图)

image.png

Graph(有时称为网络)是指具有链接(或边)的节点集。根据联系是否有方向性,可以进一步分为两组(即定向图和不定向图)。Graph在我们的生活中被广泛使用——在导航应用中计算最佳路线,或者在社交媒体中推荐朋友,举两个例子。

图有两种表示形式:

邻接清单

在此方法中,我们在左侧列出所有可能的节点,并在右侧显示已连接的节点。

image.png

邻接矩阵

相邻矩阵以行和列的形式显示节点,行和列的交点诠释了节点之间的关系,0表示没有联系,1表示有联系,>1表示权重不同。

image.png


要查询图中的节点,必须用 “宽度优先搜索"(BFS)方法或 "深度优先搜索"(DFS)方法在整个树网中进行搜索。

让我们看一个例子的BFS在Javascript:

1. function bfs(graph, root) { 

2.   var nodesLen = {}; 

3.   for (var i = 0; i < graph.length; i++) { 

4.     nodesLen[i] = Infinity; 

5.   } 

6.   nodesLen[root] = 0; 

7.   var queue = [root]; 

8.   var current

9.   while (queue.length != 0) { 

10.     current = queue.shift(); 

11.  

12.     var curConnected = graph[current]; 

13.     var neighborIdx = []; 

14.     var idx = curConnected.indexOf(1); 

15.     while (idx != -1) { 

16.       neighborIdx.push(idx); 

17.       idx = curConnected.indexOf(1, idx + 1); 

18.     } 

19.     for (var j = 0; j < neighborIdx.length; j++) { 

20.       if (nodesLen[neighborIdx[j]] == Infinity) { 

21.         nodesLen[neighborIdx[j]] = nodesLen[current] + 1; 

22.         queue.push(neighborIdx[j]); 

23.       } 

24.     } 

25.   } 

26.   return nodesLen; 

27. 

测试一下:

1. var graph = [ 

2.   [0, 1, 1, 1, 0], 

3.   [0, 0, 1, 0, 0], 

4.   [1, 1, 0, 0, 0], 

5.   [0, 0, 0, 1, 0], 

6.   [0, 1, 0, 0, 0] 

7. ]; 

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

9.  

10. // 结果 

11. 

12.   0: 2, 

13.   1: 0, 

14.   2: 1, 

15.   3: 3, 

16.   4: Infinity 

17. 


分享到:
热线:400-892-0289 版权所有(C) 2019-2025 安徽康樱网络科技有限公司 增值电信业务经营许可证编号:B2-20196319 皖ICP备19022243号    皖公网安备 34019202000744号  OA 后台