国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 語言 > JavaScript > 正文

javascript數(shù)據(jù)結(jié)構(gòu)之雙鏈表插入排序?qū)嵗斀?/h1>
2024-05-06 16:25:15
字體：大 中 小
供稿：網(wǎng)友

這篇文章主要介紹了javascript數(shù)據(jù)結(jié)構(gòu)之雙鏈表插入排序?qū)崿F(xiàn)方法,較為詳細(xì)的分析了插入排序的原理及雙鏈表插入排序的實現(xiàn)技巧,對于學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)具有一定參考借鑒價值,需要的朋友可以參考下

本文實例講述了javascript數(shù)據(jù)結(jié)構(gòu)之雙鏈表插入排序?qū)崿F(xiàn)方法。分享給大家供大家參考，具體如下：

數(shù)組存儲前提下，插入排序算法，在最壞情況下，前面的元素需要不斷向后移，以便在插入點留出空位，讓目標(biāo)元素插入。

換成鏈表時，顯然無需做這種大量移動，根據(jù)每個節(jié)點的前驅(qū)節(jié)點“指針”，向前找到插入點后，直接把目標(biāo)值從原鏈表上摘下，然后在插入點把鏈表斷成二截，然后跟目標(biāo)點重新接起來即可。

 

 
  1. <!doctype html> 
  2. <html> 
  3. <head> 
  4. <title>雙鏈表-插入排序</title> 
  5. <meta http-equiv="Content-Type" content="text/html; charset=gb2312" /> 
  6. </head> 
  7. <script type="text/javascript"> 
  8. //節(jié)點類 
  9. var Node = function (pData) { 
  10. this.next = null; //后繼“指針” 
  11. this.prev = null; //前驅(qū)"指針" 
  12. this.data = pData; 
  13. } 
  14. //單鏈表(約定：頭節(jié)點不放內(nèi)容，當(dāng)哨兵位，有效元素從頭節(jié)點后的第1個元素開始) 
  15. var DbLinkList = function () { 
  16. this.head = new Node(null); //頭節(jié)點  
  17. //插入新元素 
  18. this.insert = function (pNodeValue) { 
  19. var newNode = new Node(pNodeValue); 
  20. //如果只有頭節(jié)點 
  21. if (this.head.next == null) { 
  22. this.head.next = newNode; 
  23. newNode.prev = this.head; 
  24. return; 
  25. } 
  26. //否則遍歷找到尾節(jié)點 
  27. var p = this.head; 
  28. while (p.next != null) { 
  29. p = p.next; 
  30. } 
  31. p.next = newNode; 
  32. newNode.prev = p; 
  33. } 
  34. //獲取第n個元素的數(shù)據(jù)值 
  35. this.getData = function (index) { 
  36. if (index < 1 || index > this.size) { 
  37. return null; 
  38. } 
  39. var p = this.head; 
  40. var i = 1; 
  41. while (p.next != null && i <= index) { 
  42. p = p.next; 
  43. i += 1; 
  44. } 
  45. return p.data; 
  46. } 
  47. //取尾節(jié)點 
  48. this.getTail = function () { 
  49. if (this.head.next == null) { 
  50. return null; 
  51. } 
  52. var p = this.head.next; 
  53. while (p.next != null) { 
  54. p = p.next; 
  55. } 
  56. return p; 
  57. } 
  58. //刪除指定位置的元素 
  59. this.removeAt = function (index) { 
  60. if (index < 1 || index > this.size) { 
  61. return null; 
  62. } 
  63. var p = this.head; 
  64. var i = 1; 
  65. //從頭開始遍歷，找到index位置的前一個元素 
  66. while (p.next != null && i < index) { 
  67. p = p.next; 
  68. i += 1; 
  69. } 
  70. p.next = p.next.next; //修改index位置前一個元素的后繼指針 
  71. p.next.prev = p; 
  72. return p.data; //返回刪除元素的值  
  73. } 
  74. //打印所有元素 
  75. this.print = function () { 
  76. document.write("<br/>"); 
  77. if (this.head.next == null) { 
  78. return; 
  79. } 
  80. var p = this.head.next; 
  81. while (p.next != null) { 
  82. document.write(p.data + " "); 
  83. p = p.next; 
  84. } 
  85. document.write(p.data + " "); //最后一個元素，需要單獨(dú)打印 
  86. document.write("<br/>"); 
  87. } 
  88. //從后打印所有元素 
  89. this.printFromBack = function () { 
  90. document.write("該鏈表共有" + this.size + "個元素，從后向前分別為:<br/>"); 
  91. var tail = this.getTail(); 
  92. var p = tail; 
  93. if (p == null) { 
  94. return; 
  95. } 
  96. while (p.prev != null) { 
  97. document.write(p.data + " "); 
  98. p = p.prev; 
  99. } 
  100. document.write("<br/>"); 
  101. } 
  102. //插入排序 
  103. this.insertSort = function () { 
  104. if (this.head.next == null || this.head.next.next == null) { 
  105. return; 
  106. } 
  107. var p = this.head.next; 
  108. while (true) { 
  109. if (p == null) { 
  110. return; 
  111. } 
  112. var t = p.prev; 
  113. //向前查找p之前的插入點 
  114. while (t.prev != null && t.data > p.data) { 
  115. t = t.prev; 
  116. } 
  117. //如果插入點就是p的前驅(qū)節(jié)點，不用調(diào)整， 
  118. //忽略，直接進(jìn)入下一輪 
  119. if (t.next == p) { 
  120. p = p.next; 
  121. continue; 
  122. } 
  123. //將p的后續(xù)節(jié)點先保護(hù)起來，以便下一輪循環(huán)時確定起始位置 
  124. var x = p.next; 
  125. //將p從鏈表上摘下 
  126. if (p.next != null) { 
  127. p.next.prev = p.prev; 
  128. } 
  129. p.prev.next = p.next; 
  130. //p插入到t之后 
  131. t.next.prev = p; 
  132. p.next = t.next; 
  133. t.next = p; 
  134. p.prev = t; 
  135. this.print(); //打印輸出，調(diào)試用  
  136. //重新將p定位到下一輪循環(huán)的"正確"起始節(jié)點 
  137. p = x; 
  138. } 
  139. } 
  140. } 
  141. var linkTest = new DbLinkList(); 
  142. linkTest.insert(10); 
  143. linkTest.insert(9); 
  144. linkTest.insert(8); 
  145. linkTest.insert(7); 
  146. linkTest.insert(6); 
  147. linkTest.insert(5); 
  148. linkTest.insert(4); 
  149. linkTest.insert(3); 
  150. linkTest.insert(2); 
  151. linkTest.insert(1); 
  152. document.write("--排序前---<br/>") 
  153. linkTest.print(); 
  154. linkTest.insertSort(); 
  155. document.write("<br/>--排序后---<br/>") 
  156. linkTest.print(); 
  157. </script> 
  158. </html> 

運(yùn)行結(jié)果如下：

 

 
  1. --排序前--- 
  2.  
  3. 10 9 8 7 6 5 4 3 2 1  
  4.  
  5. 9 10 8 7 6 5 4 3 2 1  
  6.  
  7. 8 9 10 7 6 5 4 3 2 1  
  8.  
  9. 7 8 9 10 6 5 4 3 2 1  
  10.  
  11. 6 7 8 9 10 5 4 3 2 1  
  12.  
  13. 5 6 7 8 9 10 4 3 2 1  
  14.  
  15. 4 5 6 7 8 9 10 3 2 1  
  16.  
  17. 3 4 5 6 7 8 9 10 2 1  
  18.  
  19. 2 3 4 5 6 7 8 9 10 1  
  20.  
  21. 1 2 3 4 5 6 7 8 9 10  
  22.  
  23. --排序后--- 
  24.  
  25. 1 2 3 4 5 6 7 8 9 10 

希望本文所述對大家JavaScript程序設(shè)計有所幫助。


注：相關(guān)教程知識閱讀請移步到JavaScript/Ajax教程頻道。

發(fā)表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發(fā)表

圖片精選

主站蜘蛛池模板： 唐山市| 阆中市| 麻江县| 贵州省| 新巴尔虎右旗| 蕲春县| 鲜城| 若尔盖县| 申扎县| 琼海市| 湖州市| 伊通| 林州市| 阜新| 建平县| 得荣县| 肃宁县| 吉水县| 永寿县| 黄浦区| 出国| 碌曲县| 和田县| 东明县| 兖州市| 岑巩县| 平顺县| 漯河市| 右玉县| 肇庆市| 盱眙县| 徐闻县| 陇南市| 乌兰察布市| 丹巴县| 萨嘎县| 渝中区| 焉耆| 嘉鱼县| 兴和县| 太白县|