日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
常見數(shù)據(jù)結(jié)構(gòu)和Javascript實現(xiàn)總結(jié)

做前端的同學(xué)不少都是自學(xué)成才或者半路出家，計算機基礎(chǔ)的知識比較薄弱，尤其是數(shù)據(jù)結(jié)構(gòu)和算法這塊，所以今天整理了一下常見的數(shù)據(jù)結(jié)構(gòu)和對應(yīng)的Javascript的實現(xiàn)，希望能幫助大家完善這方面的知識體系。

創(chuàng)新互聯(lián)"三網(wǎng)合一"的企業(yè)建站思路。企業(yè)可建設(shè)擁有電腦版、微信版、手機版的企業(yè)網(wǎng)站。實現(xiàn)跨屏營銷，產(chǎn)品發(fā)布一步更新，電腦網(wǎng)絡(luò)+移動網(wǎng)絡(luò)一網(wǎng)打盡，滿足企業(yè)的營銷需求！創(chuàng)新互聯(lián)具備承接各種類型的成都網(wǎng)站制作、成都做網(wǎng)站、外貿(mào)營銷網(wǎng)站建設(shè)項目的能力。經(jīng)過十多年的努力的開拓，為不同行業(yè)的企事業(yè)單位提供了優(yōu)質(zhì)的服務(wù)，并獲得了客戶的一致好評。

1. Stack(棧)

Stack的特點是后進先出(last in first out)。生活中常見的Stack的例子比如一摞書，你最后放上去的那本你之后會最先拿走;又比如瀏覽器的訪問歷史，當(dāng)點擊返回按鈕，最后訪問的網(wǎng)站最先從歷史記錄中彈出。

  1. Stack一般具備以下方法：
  2. push：將一個元素推入棧頂
  3. pop：移除棧頂元素，并返回被移除的元素
  4. peek：返回棧頂元素
  5. length：返回棧中元素的個數(shù)

Javascript的Array天生具備了Stack的特性，但我們也可以從頭實現(xiàn)一個 Stack類：

 
 
 
 
    
  
  
  
  
  1. function Stack() {
    2. 
  
  
  
  
  2.   this.count = 0;
    3. 
  
  
  
  
  3.   this.storage = {};
    4. 
  
  
  
  
  4. 
  
  
  
  
  5.   this.push = function (value) {
    6. 
  
  
  
  
  6.     this.storage[this.count] = value;
    7. 
  
  
  
  
  7.     this.count++;
    8. 
  
  
  
  
  8.   }
    9. 
  
  
  
  
  9. 
  
  
  
  
  10.   this.pop = function () {
    11. 
  
  
  
  
  11.     if (this.count === 0) {
    12. 
  
  
  
  
  12.       return undefined;
    13. 
  
  
  
  
  13.     }
    14. 
  
  
  
  
  14.     this.count--;
    15. 
  
  
  
  
  15.     var result = this.storage[this.count];
    16. 
  
  
  
  
  16.     delete this.storage[this.count];
    17. 
  
  
  
  
  17.     return result;
    18. 
  
  
  
  
  18.   }
    19. 
  
  
  
  
  19. 
  
  
  
  
  20.   this.peek = function () {
    21. 
  
  
  
  
  21.     return this.storage[this.count - 1];
    22. 
  
  
  
  
  22.   }
    23. 
  
  
  
  
  23. 
  
  
  
  
  24.   this.size = function () {
    25. 
  
  
  
  
  25.     return this.count;
    26. 
  
  
  
  
  26.   }
    27. 
  
  
  
  
  27. }
    28.

2. Queue(隊列)

Queue和Stack有一些類似，不同的是Stack是先進后出，而Queue是先進先出。Queue在生活中的例子比如排隊上公交，排在第一個的總是最先上車;又比如打印機的打印隊列，排在前面的最先打印。

  • Queue一般具有以下常見方法：
  • enqueue：入列，向隊列尾部增加一個元素
  • dequeue：出列，移除隊列頭部的一個元素并返回被移除的元素
  • front：獲取隊列的第一個元素
  • isEmpty：判斷隊列是否為空
  • size：獲取隊列中元素的個數(shù)

Javascript中的Array已經(jīng)具備了Queue的一些特性，所以我們可以借助Array實現(xiàn)一個Queue類型：

 
 
 
 
    
  
  
  
  
  1. function Queue() {
    2. 
  
  
  
  
  2.   var collection = [];
    3. 
  
  
  
  
  3. 
  
  
  
  
  4.   this.print = function () {
    5. 
  
  
  
  
  5.     console.log(collection);
    6. 
  
  
  
  
  6.   }
    7. 
  
  
  
  
  7. 
  
  
  
  
  8.   this.enqueue = function (element) {
    9. 
  
  
  
  
  9.     collection.push(element);
    10. 
  
  
  
  
  10.   }
    11. 
  
  
  
  
  11. 
  
  
  
  
  12.   this.dequeue = function () {
    13. 
  
  
  
  
  13.     return collection.shift();
    14. 
  
  
  
  
  14.   }
    15. 
  
  
  
  
  15. 
  
  
  
  
  16.   this.front = function () {
    17. 
  
  
  
  
  17.     return collection[0];
    18. 
  
  
  
  
  18.   }
    19. 
  
  
  
  
  19. 
  
  
  
  
  20.   this.isEmpty = function () {
    21. 
  
  
  
  
  21.     return collection.length === 0;
    22. 
  
  
  
  
  22.   }
    23. 
  
  
  
  
  23. 
  
  
  
  
  24.   this.size = function () {
    25. 
  
  
  
  
  25.     return collection.length;
    26. 
  
  
  
  
  26.   }
    27. 
  
  
  
  
  27. }
    28.

Priority Queue(優(yōu)先隊列)

Queue還有個升級版本，給每個元素賦予優(yōu)先級，優(yōu)先級高的元素入列時將排到低優(yōu)先級元素之前。區(qū)別主要是enqueue方法的實現(xiàn)：

 
 
 
 
    
  
  
  
  
  1. function PriorityQueue() {
    2. 
  
  
  
  
  2. 
  
  
  
  
  3.   ...
    4. 
  
  
  
  
  4. 
  
  
  
  
  5.   this.enqueue = function (element) {
    6. 
  
  
  
  
  6.     if (this.isEmpty()) {
    7. 
  
  
  
  
  7.       collection.push(element);
    8. 
  
  
  
  
  8.     } else {
    9. 
  
  
  
  
  9.       var added = false;
    10. 
  
  
  
  
  10.       for (var i = 0; i < collection.length; i++) {
    11. 
  
  
  
  
  11.         if (element[1] < collection[i][1]) {
    12. 
  
  
  
  
  12.           collection.splice(i, 0, element);
    13. 
  
  
  
  
  13.           added = true;
    14. 
  
  
  
  
  14.           break;
    15. 
  
  
  
  
  15.         }
    16. 
  
  
  
  
  16.       }
    17. 
  
  
  
  
  17.       if (!added) {
    18. 
  
  
  
  
  18.         collection.push(element);
    19. 
  
  
  
  
  19.       }
    20. 
  
  
  
  
  20.     }
    21. 
  
  
  
  
  21.   }
    22. 
  
  
  
  
  22. }
    23.

測試一下：

 
 
 
 
    
  
  
  
  
  1. var pQ = new PriorityQueue();
    2. 
  
  
  
  
  2. 
  
  
  
  
  3. pQ.enqueue(['gannicus', 3]);
    4. 
  
  
  
  
  4. pQ.enqueue(['spartacus', 1]);
    5. 
  
  
  
  
  5. pQ.enqueue(['crixus', 2]);
    6. 
  
  
  
  
  6. pQ.enqueue(['oenomaus', 4]);
    7. 
  
  
  
  
  7. 
  
  
  
  
  8. pQ.print();
    9.

結(jié)果：

 
 
 
 
    
  
  
  
  
  1. [
    2. 
  
  
  
  
  2.   [ 'spartacus', 1 ],
    3. 
  
  
  
  
  3.   [ 'crixus', 2 ],
    4. 
  
  
  
  
  4.   [ 'gannicus', 3 ],
    5. 
  
  
  
  
  5.   [ 'oenomaus', 4 ]
    6. 
  
  
  
  
  6. ]
    7.

3. Linked List(鏈表)

顧名思義，鏈表是一種鏈式數(shù)據(jù)結(jié)構(gòu)，鏈上的每個節(jié)點包含兩種信息：節(jié)點本身的數(shù)據(jù)和指向下一個節(jié)點的指針。鏈表和傳統(tǒng)的數(shù)組都是線性的數(shù)據(jù)結(jié)構(gòu)，存儲的都是一個序列的數(shù)據(jù)，但也有很多區(qū)別，如下表：

一個單向鏈表通常具有以下方法：

  1. size：返回鏈表中節(jié)點的個數(shù)
  2. head：返回鏈表中的頭部元素
  3. add：向鏈表尾部增加一個節(jié)點
  4. remove：刪除某個節(jié)點
  5. indexOf：返回某個節(jié)點的index
  6. elementAt：返回某個index處的節(jié)點
  7. addAt：在某個index處插入一個節(jié)點
  8. removeAt：刪除某個index處的節(jié)點

單向鏈表的Javascript實現(xiàn)：

 
 
 
 
    
  
  
  
  
  1. /**
    2. 
  
  
  
  
  2.  * 鏈表中的節(jié)點 
    3. 
  
  
  
  
  3.  */
    4. 
  
  
  
  
  4. function Node(element) {
    5. 
  
  
  
  
  5.   // 節(jié)點中的數(shù)據(jù)
    6. 
  
  
  
  
  6.   this.element = element;
    7. 
  
  
  
  
  7.   // 指向下一個節(jié)點的指針
    8. 
  
  
  
  
  8.   this.next = null;
    9. 
  
  
  
  
  9. }
    10. 
  
  
  
  
  10. 
  
  
  
  
  11. function LinkedList() {
    12. 
  
  
  
  
  12.   var length = 0;
    13. 
  
  
  
  
  13.   var head = null;
    14. 
  
  
  
  
  14. 
  
  
  
  
  15.   this.size = function () {
    16. 
  
  
  
  
  16.     return length;
    17. 
  
  
  
  
  17.   }
    18. 
  
  
  
  
  18. 
  
  
  
  
  19.   this.head = function () {
    20. 
  
  
  
  
  20.     return head;
    21. 
  
  
  
  
  21.   }
    22. 
  
  
  
  
  22. 
  
  
  
  
  23.   this.add = function (element) {
    24. 
  
  
  
  
  24.     var node = new Node(element);
    25. 
  
  
  
  
  25.     if (head == null) {
    26. 
  
  
  
  
  26.       head = node;
    27. 
  
  
  
  
  27.     } else {
    28. 
  
  
  
  
  28.       var currentNode = head;
    29. 
  
  
  
  
  29. 
  
  
  
  
  30.       while (currentNode.next) {
    31. 
  
  
  
  
  31.         currentNode = currentNode.next;
    32. 
  
  
  
  
  32.       }
    33. 
  
  
  
  
  33. 
  
  
  
  
  34.       currentNode.next = node;
    35. 
  
  
  
  
  35.     }
    36. 
  
  
  
  
  36.     length++;
    37. 
  
  
  
  
  37.   }
    38. 
  
  
  
  
  38. 
  
  
  
  
  39.   this.remove = function (element) {
    40. 
  
  
  
  
  40.     var currentNode = head;
    41. 
  
  
  
  
  41.     var previousNode;
    42. 
  
  
  
  
  42.     if (currentNode.element === element) {
    43. 
  
  
  
  
  43.       head = currentNode.next;
    44. 
  
  
  
  
  44.     } else {
    45. 
  
  
  
  
  45.       while (currentNode.element !== element) {
    46. 
  
  
  
  
  46.         previousNode = currentNode;
    47. 
  
  
  
  
  47.         currentNode = currentNode.next;
    48. 
  
  
  
  
  48.       }
    49. 
  
  
  
  
  49.       previousNode.next = currentNode.next;
    50. 
  
  
  
  
  50.     }
    51. 
  
  
  
  
  51.     length--;
    52. 
  
  
  
  
  52.   }
    53. 
  
  
  
  
  53. 
  
  
  
  
  54.   this.isEmpty = function () {
    55. 
  
  
  
  
  55.     return length === 0;
    56. 
  
  
  
  
  56.   }
    57. 
  
  
  
  
  57. 
  
  
  
  
  58.   this.indexOf = function (element) {
    59. 
  
  
  
  
  59.     var currentNode = head;
    60. 
  
  
  
  
  60.     var index = -1;
    61. 
  
  
  
  
  61.     while (currentNode) {
    62. 
  
  
  
  
  62.       index++;
    63. 
  
  
  
  
  63.       if (currentNode.element === element) {
    64. 
  
  
  
  
  64.         return index;
    65. 
  
  
  
  
  65.       }
    66. 
  
  
  
  
  66.       currentNode = currentNode.next;
    67. 
  
  
  
  
  67.     }
    68. 
  
  
  
  
  68. 
  
  
  
  
  69.     return -1;
    70. 
  
  
  
  
  70.   }
    71. 
  
  
  
  
  71. 
  
  
  
  
  72.   this.elementAt = function (index) {
    73. 
  
  
  
  
  73.     var currentNode = head;
    74. 
  
  
  
  
  74.     var count = 0;
    75. 
  
  
  
  
  75.     while (count < index) {
    76. 
  
  
  
  
  76.       count++;
    77. 
  
  
  
  
  77.       currentNode = currentNode.next;
    78. 
  
  
  
  
  78.     }
    79. 
  
  
  
  
  79.     return currentNode.element;
    80. 
  
  
  
  
  80.   }
    81. 
  
  
  
  
  81. 
  
  
  
  
  82.   this.addAt = function (index, element) {
    83. 
  
  
  
  
  83.     var node = new Node(element);
    84. 
  
  
  
  
  84.     var currentNode = head;
    85. 
  
  
  
  
  85.     var previousNode;
    86. 
  
  
  
  
  86.     var currentIndex = 0;
    87. 
  
  
  
  
  87. 
  
  
  
  
  88.     if (index > length) {
    89. 
  
  
  
  
  89.       return false;
    90. 
  
  
  
  
  90.     }
    91. 
  
  
  
  
  91. 
  
  
  
  
  92.     if (index === 0) {
    93. 
  
  
  
  
  93.       node.next = currentNode;
    94. 
  
  
  
  
  94.       head = node;
    95. 
  
  
  
  
  95.     } else {
    96. 
  
  
  
  
  96.       while (currentIndex < index) {
    97. 
  
  
  
  
  97.         currentIndex++;
    98. 
  
  
  
  
  98.         previousNode = currentNode;
    99. 
  
  
  
  
  99.         currentNode = currentNode.next;
    100. 
  
  
  
  
  100.       }
    101. 
  
  
  
  
  101.       node.next = currentNode;
    102. 
  
  
  
  
  102.       previousNode.next = node;
    103. 
  
  
  
  
  103.     }
    104. 
  
  
  
  
  104.     length++;
    105. 
  
  
  
  
  105.   }
    106. 
  
  
  
  
  106. 
  
  
  
  
  107.   this.removeAt = function (index) {
    108. 
  
  
  
  
  108.     var currentNode = head;
    109. 
  
  
  
  
  109.     var previousNode;
    110. 
  
  
  
  
  110.     var currentIndex = 0;
    111. 
  
  
  
  
  111.     if (index < 0 || index >= length) {
    112. 
  
  
  
  
  112.       return null;
    113. 
  
  
  
  
  113.     }
    114. 
  
  
  
  
  114.     if (index === 0) {
    115. 
  
  
  
  
  115.       head = currentIndex.next;
    116. 
  
  
  
  
  116.     } else {
    117. 
  
  
  
  
  117.       while (currentIndex < index) {
    118. 
  
  
  
  
  118.         currentIndex++;
    119. 
  
  
  
  
  119.         previousNode = currentNode;
    120. 
  
  
  
  
  120.         currentNode = currentNode.next;
    121. 
  
  
  
  
  121.       }
    122. 
  
  
  
  
  122.       previousNode.next = currentNode.next;
    123. 
  
  
  
  
  123.     }
    124. 
  
  
  
  
  124.     length--;
    125. 
  
  
  
  
  125.     return currentNode.element;
    126. 
  
  
  
  
  126.   }
    127. 
  
  
  
  
  127. }
    128.

4. Set(集合)

集合是數(shù)學(xué)中的一個基本概念，表示具有某種特性的對象匯總成的集體。在ES6中也引入了集合類型Set，Set和Array有一定程度的相似，不同的是Set中不允許出現(xiàn)重復(fù)的元素而且是無序的。

一個典型的Set應(yīng)該具有以下方法：

  1. values：返回集合中的所有元素
  2. size：返回集合中元素的個數(shù)
  3. has：判斷集合中是否存在某個元素
  4. add：向集合中添加元素
  5. remove：從集合中移除某個元素
  6. union：返回兩個集合的并集
  7. intersection：返回兩個集合的交集
  8. difference：返回兩個集合的差集
  9. subset：判斷一個集合是否為另一個集合的子集

使用Javascript可以將Set進行如下實現(xiàn)，為了區(qū)別于ES6中的Set命名為MySet：

 
 
 
 
    
  
  
  
  
  1. function MySet() {
    2. 
  
  
  
  
  2.   var collection = [];
    3. 
  
  
  
  
  3.   this.has = function (element) {
    4. 
  
  
  
  
  4.     return (collection.indexOf(element) !== -1);
    5. 
  
  
  
  
  5.   }
    6. 
  
  
  
  
  6. 
  
  
  
  
  7.   this.values = function () {
    8. 
  
  
  
  
  8.     return collection;
    9. 
  
  
  
  
  9.   }
    10. 
  
  
  
  
  10. 
  
  
  
  
  11.   this.size = function () {
    12. 
  
  
  
  
  12.     return collection.length;
    13. 
  
  
  
  
  13.   }
    14. 
  
  
  
  
  14. 
  
  
  
  
  15.   this.add = function (element) {
    16. 
  
  
  
  
  16.     if (!this.has(element)) {
    17. 
  
  
  
  
  17.       collection.push(element);
    18. 
  
  
  
  
  18.       return true;
    19. 
  
  
  
  
  19.     }
    20. 
  
  
  
  
  20.     return false;
    21. 
  
  
  
  
  21.   }
    22. 
  
  
  
  
  22. 
  
  
  
  
  23.   this.remove = function (element) {
    24. 
  
  
  
  
  24.     if (this.has(element)) {
    25. 
  
  
  
  
  25.       index = collection.indexOf(element);
    26. 
  
  
  
  
  26.       collection.splice(index, 1);
    27. 
  
  
  
  
  27.       return true;
    28. 
  
  
  
  
  28.     }
    29. 
  
  
  
  
  29.     return false;
    30. 
  
  
  
  
  30.   }
    31. 
  
  
  
  
  31. 
  
  
  
  
  32.   this.union = function (otherSet) {
    33. 
  
  
  
  
  33.     var unionSet = new MySet();
    34. 
  
  
  
  
  34.     var firstSet = this.values();
    35. 
  
  
  
  
  35.     var secondSet = otherSet.values();
    36. 
  
  
  
  
  36.     firstSet.forEach(function (e) {
    37. 
  
  
  
  
  37.       unionSet.add(e);
    38. 
  
  
  
  
  38.     });
    39. 
  
  
  
  
  39.     secondSet.forEach(function (e) {
    40. 
  
  
  
  
  40.       unionSet.add(e);
    41. 
  
  
  
  
  41.     });
    42. 
  
  
  
  
  42.     return unionSet;
    43. 
  
  
  
  
  43.   }
    44. 
  
  
  
  
  44. 
  
  
  
  
  45.   this.intersection = function (otherSet) {
    46. 
  
  
  
  
  46.     var intersectionSet = new MySet();
    47. 
  
  
  
  
  47.     var firstSet = this.values();
    48. 
  
  
  
  
  48.     firstSet.forEach(function (e) {
    49. 
  
  
  
  
  49.       if (otherSet.has(e)) {
    50. 
  
  
  
  
  50.         intersectionSet.add(e);
    51. 
  
  
  
  
  51.       }
    52. 
  
  
  
  
  52.     });
    53. 
  
  
  
  
  53.     return intersectionSet;
    54. 
  
  
  
  
  54.   }
    55. 
  
  
  
  
  55. 
  
  
  
  
  56.   this.difference = function (otherSet) {
    57. 
  
  
  
  
  57.     var differenceSet = new MySet();
    58. 
  
  
  
  
  58.     var firstSet = this.values();
    59. 
  
  
  
  
  59.     firstSet.forEach(function (e) {
    60. 
  
  
  
  
  60.       if (!otherSet.has(e)) {
    61. 
  
  
  
  
  61.         differenceSet.add(e);
    62. 
  
  
  
  
  62.       }
    63. 
  
  
  
  
  63.     });
    64. 
  
  
  
  
  64.     return differenceSet;
    65. 
  
  
  
  
  65.   }
    66. 
  
  
  
  
  66. 
  
  
  
  
  67.   this.subset = function (otherSet) {
    68. 
  
  
  
  
  68.     var firstSet = this.values();
    69. 
  
  
  
  
  69.     return firstSet.every(function (value) {
    70. 
  
  
  
  
  70.       return otherSet.has(value);
    71. 
  
  
  
  
  71.     });
    72. 
  
  
  
  
  72.   }
    73. 
  
  
  
  
  73. }
    74.

5. Hash Table(哈希表/散列表)

Hash Table是一種用于存儲鍵值對(key value pair)的數(shù)據(jù)結(jié)構(gòu)，因為Hash Table根據(jù)key查詢value的速度很快，所以它常用于實現(xiàn)Map、Dictinary、Object等數(shù)據(jù)結(jié)構(gòu)。如上圖所示，Hash Table內(nèi)部使用一個hash函數(shù)將傳入的鍵轉(zhuǎn)換成一串?dāng)?shù)字，而這串?dāng)?shù)字將作為鍵值對實際的key，通過這個key查詢對應(yīng)的value非常快，時間復(fù)雜度將達到O(1)。Hash函數(shù)要求相同輸入對應(yīng)的輸出必須相等，而不同輸入對應(yīng)的輸出必須不等，相當(dāng)于對每對數(shù)據(jù)打上唯一的指紋。

一個Hash Table通常具有下列方法：

  1. add：增加一組鍵值對
  2. remove：刪除一組鍵值對
  3. lookup：查找一個鍵對應(yīng)的值

一個簡易版本的Hash Table的Javascript實現(xiàn)：

 
 
 
 
    
  
  
  
  
  1. function hash(string, max) {
    2. 
  
  
  
  
  2.   var hash = 0;
    3. 
  
  
  
  
  3.   for (var i = 0; i < string.length; i++) {
    4. 
  
  
  
  
  4.     hash += string.charCodeAt(i);
    5. 
  
  
  
  
  5.   }
    6. 
  
  
  
  
  6.   return hash % max;
    7. 
  
  
  
  
  7. }
    8. 
  
  
  
  
  8. 
  
  
  
  
  9. function HashTable() {
    10. 
  
  
  
  
  10.   let storage = [];
    11. 
  
  
  
  
  11.   const storageLimit = 4;
    12. 
  
  
  
  
  12. 
  
  
  
  
  13.   this.add = function (key, value) {
    14. 
  
  
  
  
  14.     var index = hash(key, storageLimit);
    15. 
  
  
  
  
  15.     if (storage[index] === undefined) {
    16. 
  
  
  
  
  16.       storage[index] = [
    17. 
  
  
  
  
  17.         [key, value]
    18. 
  
  
  
  
  18.       ];
    19. 
  
  
  
  
  19.     } else {
    20. 
  
  
  
  
  20.       var inserted = false;
    21. 
  
  
  
  
  21.       for (var i = 0; i < storage[index].length; i++) {
    22. 
  
  
  
  
  22.         if (storage[index][i][0] === key) {
    23. 
  
  
  
  
  23.           storage[index][i][1] = value;
    24. 
  
  
  
  
  24.           inserted = true;
    25. 
  
  
  
  
  25.         }
    26. 
  
  
  
  
  26.       }
    27. 
  
  
  
  
  27.       if (inserted === false) {
    28. 
  
  
  
  
  28.         storage[index].push([key, value]);
    29. 
  
  
  
  
  29.       }
    30. 
  
  
  
  
  30.     }
    31. 
  
  
  
  
  31.   }
    32. 
  
  
  
  
  32. 
  
  
  
  
  33.   this.remove = function (key) {
    34. 
  
  
  
  
  34.     var index = hash(key, storageLimit);
    35. 
  
  
  
  
  35.     if (storage[index].length === 1 && storage[index][0][0] === key) {
    36. 
  
  
  
  
  36.       delete storage[index];
    37. 
  
  
  
  
  37.     } else {
    38. 
  
  
  
  
  38.       for (var i = 0; i < storage[index]; i++) {
    39. 
  
  
  
  
  39.         if (storage[index][i][0] === key) {
    40. 
  
  
  
  
  40.           delete storage[index][i];
    41. 
  
  
  
  
  41.         }
    42. 
  
  
  
  
  42.       }
    43. 
  
  
  
  
  43.     }
    44. 
  
  
  
  
  44.   }
    45. 
  
  
  
  
  45. 
  
  
  
  
  46.   this.lookup = function (key) {
    47. 
  
  
  
  
  47.     var index = hash(key, storageLimit);
    48. 
  
  
  
  
  48.     if (storage[index] === undefined) {
    49. 
  
  
  
  
  49.       return undefined;
    50. 
  
  
  
  
  50.     } else {
    51. 
  
  
  
  
  51.       for (var i = 0; i < storage[index].length; i++) {
    52. 
  
  
  
  
  52.         if (storage[index][i][0] === key) {
    53. 
  
  
  
  
  53.           return storage[index][i][1];
    54. 
  
  
  
  
  54.         }
    55. 
  
  
  
  
  55.       }
    56. 
  
  
  
  
  56.     }
    57. 
  
  
  
  
  57.   }
    58. 
  
  
  
  
  58. }
    59.

6. Tree(樹)

顧名思義，Tree的數(shù)據(jù)結(jié)構(gòu)和自然界中的樹極其相似，有根、樹枝、葉子，如上圖所示。Tree是一種多層數(shù)據(jù)結(jié)構(gòu)，與Array、Stack、Queue相比是一種非線性的數(shù)據(jù)結(jié)構(gòu)，在進行插入和搜索操作時很高效。在描述一個Tree時經(jīng)常會用到下列概念：

  1. Root(根)：代表樹的根節(jié)點，根節(jié)點沒有父節(jié)點
  2. Parent Node(父節(jié)點)：一個節(jié)點的直接上級節(jié)點，只有一個
  3. Child Node(子節(jié)點)：一個節(jié)點的直接下級節(jié)點，可能有多個
  4. Siblings(兄弟節(jié)點)：具有相同父節(jié)點的節(jié)點
  5. Leaf(葉節(jié)點)：沒有子節(jié)點的節(jié)點
  6. Edge(邊)：兩個節(jié)點之間的連接線
  7. Path(路徑)：從源節(jié)點到目標節(jié)點的連續(xù)邊
  8. Height of Node(節(jié)點的高度)：表示節(jié)點與葉節(jié)點之間的最長路徑上邊的個數(shù)
  9. Height of Tree(樹的高度)：即根節(jié)點的高度
  10. Depth of Node(節(jié)點的深度)：表示從根節(jié)點到該節(jié)點的邊的個數(shù)
  11. Degree of Node(節(jié)點的度)：表示子節(jié)點的個數(shù)

我們以二叉查找樹為例，展示樹在Javascript中的實現(xiàn)。在二叉查找樹中，即每個節(jié)點最多只有兩個子節(jié)點，而左側(cè)子節(jié)點小于當(dāng)前節(jié)點，而右側(cè)子節(jié)點大于當(dāng)前節(jié)點，如圖所示：

一個二叉查找樹應(yīng)該具有以下常用方法：

  1. add：向樹中插入一個節(jié)點
  2. findMin：查找樹中最小的節(jié)點
  3. findMax：查找樹中最大的節(jié)點
  4. find：查找樹中的某個節(jié)點
  5. isPresent：判斷某個節(jié)點在樹中是否存在
  6. remove：移除樹中的某個節(jié)點

以下是二叉查找樹的Javascript實現(xiàn)：

 
 
 
 
    
  
  
  
  
  1. class Node {
    2. 
  
  
  
  
  2.   constructor(data, left = null, right = null) {
    3. 
  
  
  
  
  3.     this.data = data;
    4. 
  
  
  
  
  4.     this.left = left;
    5. 
  
  
  
  
  5.     this.right = right;
    6. 
  
  
  
  
  6.   }
    7. 
  
  
  
  
  7. }
    8. 
  
  
  
  
  8. 
  
  
  
  
  9. class BST {
    10. 
  
  
  
  
  10.   constructor() {
    11. 
  
  
  
  
  11.     this.root = null;
    12. 
  
  
  
  
  12.   }
    13. 
  
  
  
  
  13. 
  
  
  
  
  14.   add(data) {
    15. 
  
  
  
  
  15.     const node = this.root;
    16. 
  
  
  
  
  16.     if (node === null) {
    17. 
  
  
  
  
  17.       this.root = new Node(data);
    18. 
  
  
  
  
  18.       return;
    19. 
  
  
  
  
  19.     } else {
    20. 
  
  
  
  
  20.       const searchTree = function (node) {
    21. 
  
  
  
  
  21.         if (data < node.data) {
    22. 
  
  
  
  
  22.           if (node.left === null) {
    23. 
  
  
  
  
  23.             node.left = new Node(data);
    24. 
  
  
  
  
  24.             return;
    25. 
  
  
  
  
  25.           } else if (node.left !== null) {
    26. 
  
  
  
  
  26.             return searchTree(node.left);
    27. 
  
  
  
  
  27.           }
    28. 
  
  
  
  
  28.         } else if (data > node.data) {
    29. 
  
  
  
  
  29.           if (node.right === null) {
    30. 
  
  
  
  
  30.             node.right = new Node(data);
    31. 
  
  
  
  
  31.             return;
    32. 
  
  
  
  
  32.           } else if (node.right !== null) {
    33. 
  
  
  
  
  33.             return searchTree(node.right);
    34. 
  
  
  
  
  34.           }
    35. 
  
  
  
  
  35.         } else {
    36. 
  
  
  
  
  36.           return null;
    37. 
  
  
  
  
  37.         }
    38. 
  
  
  
  
  38.       };
    39. 
  
  
  
  
  39.       return searchTree(node);
    40. 
  
  
  
  
  40.     }
    41. 
  
  
  
  
  41.   }
    42. 
  
  
  
  
  42. 
  
  
  
  
  43.   findMin() {
    44. 
  
  
  
  
  44.     let current = this.root;
    45. 
  
  
  
  
  45.     while (current.left !== null) {
    46. 
  
  
  
  
  46.       current = current.left;
    47. 
  
  
  
  
  47.     }
    48. 
  
  
  
  
  48.     return current.data;
    49. 
  
  
  
  
  49.   }
    50. 
  
  
  
  
  50. 
  
  
  
  
  51.   findMax() {
    52. 
  
  
  
  
  52.     let current = this.root;
    53. 
  
  
  
  
  53.     while (current.right !== null) {
    54. 
  
  
  
  
  54.       current = current.right;
    55. 
  
  
  
  
  55.     }
    56. 
  
  
  
  
  56.     return current.data;
    57. 
  
  
  
  
  57.   }
    58. 
  
  
  
  
  58. 
  
  
  
  
  59.   find(data) {
    60. 
  
  
  
  
  60.     let current = this.root;
    61. 
  
  
  
  
  61.     while (current.data !== data) {
    62. 
  
  
  
  
  62.       if (data < current.data) {
    63. 
  
  
  
  
  63.         current = current.left
    64. 
  
  
  
  
  64.       } else {
    65. 
  
  
  
  
  65.         current = current.right;
    66. 
  
  
  
  
  66.       }
    67. 
  
  
  
  
  67.       if (current === null) {
    68. 
  
  
  
  
  68.         return null;
    69. 
  
  
  
  
  69.       }
    70. 
  
  
  
  
  70.     }
    71. 
  
  
  
  
  71.     return current;
    72. 
  
  
  
  
  72.   }
    73. 
  
  
  
  
  73. 
  
  
  
  
  74.   isPresent(data) {
    75. 
  
  
  
  
  75.     let current = this.root;
    76. 
  
  
  
  
  76.     while (current) {
    77. 
  
  
  
  
  77.       if (data === current.data) {
    78. 
  
  
  
  
  78.         return true;
    79. 
  
  
  
  
  79.       }
    80. 
  
  
  
  
  80.       if (data < current.data) {
    81. 
  
  
  
  
  81.         current = current.left;
    82. 
  
  
  
  
  82.       } else {
    83. 
  
  
  
  
  83.         current = current.right;
    84. 
  
  
  
  
  84.       }
    85. 
  
  
  
  
  85.     }
    86. 
  
  
  
  
  86.     return false;
    87. 
  
  
  
  
  87.   }
    88. 
  
  
  
  
  88. 
  
  
  
  
  89.   remove(data) {
    90. 
  
  
  
  
  90.     const removeNode = function (node, data) {
    91. 
  
  
  
  
  91.       if (node == null) {
    92. 
  
  
  
  
  92.         return null;
    93. 
  
  
  
  
  93.       }
    94. 
  
  
  
  
  94.       if (data == node.data) {
    95. 
  
  
  
  
  95.         // node沒有子節(jié)點
    96. 
  
  
  
  
  96.         if (node.left == null && node.right == null) {
    97. 
  
  
  
  
  97.           return null;
    98. 
  
  
  
  
  98.         }
    99. 
  
  
  
  
  99.         // node沒有左側(cè)子節(jié)點
    100. 
  
  
  
  
  100.         if (node.left == null) {
    101. 
  
  
  
  
  101.           return node.right;
    102. 
  
  
  
  
  102.         }
    103. 
  
  
  
  
  103.         // node沒有右側(cè)子節(jié)點
    104. 
  
  
  
  
  104.         if (node.right == null) {
    105. 
  
  
  
  
  105.           return node.left;
    106. 
  
  
  
  
  106.         }
    107. 
  
  
  
  
  107.         // node有兩個子節(jié)點
    108. 
  
  
  
  
  108.         var tempNode = node.right;
    109. 
  
  
  
  
  109.         while (tempNode.left !== null) {
    110. 
  
  
  
  
  110.           tempNode = tempNode.left;
    111. 
  
  
  
  
  111.         }
    112. 
  
  
  
  
  112.         node.data = tempNode.data;
    113. 
  
  
  
  
  113.         node.right = removeNode(node.right, tempNode.data);
    114. 
  
  
  
  
  114.         return node;
    115. 
  
  
  
  
  115.       } else if (data < node.data) {
    116. 
  
  
  
  
  116.         node.left = removeNode(node.left, data);
    117. 
  
  
  
  
  117.         return node;
    118. 
  
  
  
  
  118.       } else {
    119. 
  
  
  
  
  119.         node.right = removeNode(node.right, data);
    120. 
  
  
  
  
  120.         return node;
    121. 
  
  
  
  
  121.       }
    122. 
  
  
  
  
  122.     }
    123. 
  
  
  
  
  123.     this.root = removeNode(this.root, data);
    124. 
  
  
  
  
  124.   }
    125. 
  
  
  
  
  125. }
    126.

測試一下：

 
 
 
 
    
  
  
  
  
  1. const bst = new BST();
    2. 
  
  
  
  
  2. 
  
  
  
  
  3. bst.add(4);
    4. 
  
  
  
  
  4. bst.add(2);
    5. 
  
  
  
  
  5. bst.add(6);
    6. 
  
  
  
  
  6. bst.add(1);
    7. 
  
  
  
  
  7. bst.add(3);
    8. 
  
  
  
  
  8. bst.add(5);
    9. 
  
  
  
  
  9. bst.add(7);
    10. 
  
  
  
  
  10. bst.remove(4);
    11. 
  
  
  
  
  11. console.log(bst.findMin());
    12. 
  
  
  
  
  12. console.log(bst.findMax());
    13. 
  
  
  
  
  13. bst.remove(7);
    14. 
  
  
  
  
  14. console.log(bst.findMax());
    15. 
  
  
  
  
  15. console.log(bst.isPresent(4));
    16.

打印結(jié)果：

 
 
 
 
    
  
  
  
  
  1. 1
    2. 
  
  
  
  
  2. 7
    3. 
  
  
  
  
  3. 6
    4. 
  
  
  
  
  4. false
    5.

7. Trie(字典樹，讀音同try)

Trie也可以叫做Prefix Tree(前綴樹)，也是一種搜索樹。Trie分步驟存儲數(shù)據(jù)，樹中的每個節(jié)點代表一個步驟，trie常用于存儲單詞以便快速查找，比如實現(xiàn)單詞的自動完成功能。 Trie中的每個節(jié)點都包含一個單詞的字母，跟著樹的分支可以可以拼寫出一個完整的單詞，每個節(jié)點還包含一個布爾值表示該節(jié)點是否是單詞的最后一個字母。

Trie一般有以下方法：

  • add：向字典樹中增加一個單詞
  • isWord：判斷字典樹中是否包含某個單詞
  • print：返回字典樹中的所有單詞
 
 
 
 
    
  
  
  
  
  1. /**
    2. 
  
  
  
  
  2.  * Trie的節(jié)點
    3. 
  
  
  
  
  3.  */
    4. 
  
  
  
  
  4. function Node() {
    5. 
  
  
  
  
  5.   this.keys = new Map();
    6. 
  
  
  
  
  6.   this.end = false;
    7. 
  
  
  
  
  7.   this.setEnd = function () {
    8. 
  
  
  
  
  8.     this.end = true;
    9. 
  
  
  
  
  9.   };
    10. 
  
  
  
  
  10.   this.isEnd = function () {
    11. 
  
  
  
  
  11.     return this.end;
    12. 
  
  
  
  
  12.   }
    13. 
  
  
  
  
  13. }
    14. 
  
  
  
  
  14. 
  
  
  
  
  15. function Trie() {
    16. 
  
  
  
  
  16.   this.root = new Node();
    17. 
  
  
  
  
  17. 
  
  
  
  
  18.   this.add = function (input, node = this.root) {
    19. 
  
  
  
  
  19.     if (input.length === 0) {
    20. 
  
  
  
  
  20.       node.setEnd();
    21. 
  
  
  
  
  21.       return;
    22. 
  
  
  
  
  22.     } else if (!node.keys.has(input[0])) {
    23. 
  
  
  
  
  23.       node.keys.set(input[0], new Node());
    24. 
  
  
  
  
  24.       return this.add(input.substr(1), node.keys.get(input[0]));
    25. 
  
  
  
  
  25.     } else {
    26. 
  
  
  
  
  26.       return this.add(input.substr(1), node.keys.get(input[0]));
    27. 
  
  
  
  
  27.     }
    28. 
  
  
  
  
  28.   }
    29. 
  
  
  
  
  29. 
  
  
  
  
  30.   this.isWord = function (word) {
    31. 
  
  
  
  
  31.     let node = this.root;
    32. 
  
  
  
  
  32.     while (word.length > 1) {
    33. 
  
  
  
  
  33.       if (!node.keys.has(word[0])) {
    34. 
  
  
  
  
  34.         return false;
    35. 
  
  
  
  
  35.       } else {
    36. 
  
  
  
  
  36.         node = node.keys.get(word[0]);
    37. 
  
  
  
  
  37.         word = word.substr(1);
    38. 
  
  
  
  
  38.       }
    39. 
  
  
  
  
  39.     }
    40. 
  
  
  
  
  40.     return (node.keys.has(word) && node.keys.get(word).isEnd()) ? true : false;
    41. 
  
  
  
  
  41.   }
    42. 
  
  
  
  
  42. 
  
  
  
  
  43.   this.print = function () {
    44. 
  
  
  
  
  44.     let words = new Array();
    45. 
  
  
  
  
  45.     let search = function (node = this.root, string) {
    46. 
  
  
  
  
  46.       if (node.keys.size != 0) {
    47. 
  
  
  
  
  47.         for (let letter of node.keys.keys()) {
    48. 
  
  
  
  
  48.           search(node.keys.get(letter), string.concat(letter));
    49. 
  
  
  
  
  49.         }
    50. 
  
  
  
  
  50.         if (node.isEnd()) {
    51. 
  
  
  
  
  51.           words.push(string);
    52. 
  
  
  
  
  52.    &nbs                                                
    
                                                分享名稱：常見數(shù)據(jù)結(jié)構(gòu)和Javascript實現(xiàn)總結(jié)                                                
    
                                                當(dāng)前URL：http://www.5511xx.com/article/dpehepo.html