javascript數據結構之雙鏈表插入排序實例詳解

2024-05-06 16:25:15

字體：大中小

來源：轉載

供稿：網友

這篇文章主要介紹了javascript數據結構之雙鏈表插入排序實現方法,較為詳細的分析了插入排序的原理及雙鏈表插入排序的實現技巧,對于學習JavaScript數據結構具有一定參考借鑒價值,需要的朋友可以參考下

本文實例講述了javascript數據結構之雙鏈表插入排序實現方法。分享給大家供大家參考，具體如下：

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

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

<!doctype html>

<html>

<head>

<title>雙鏈表-插入排序</title>

<meta http-equiv="Content-Type" content="text/html; charset=gb2312" />

</head>

<script type="text/javascript">

//節點類

var Node = function (pData) {

this.next = null; //后繼“指針”

this.prev = null; //前驅"指針"

this.data = pData;

}

//單鏈表(約定：頭節點不放內容，當哨兵位，有效元素從頭節點后的第1個元素開始)

var DbLinkList = function () {

this.head = new Node(null); //頭節點

//插入新元素

this.insert = function (pNodeValue) {

var newNode = new Node(pNodeValue);

//如果只有頭節點

if (this.head.next == null) {

this.head.next = newNode;

newNode.prev = this.head;

return;

}

//否則遍歷找到尾節點

var p = this.head;

while (p.next != null) {

p = p.next;

}

p.next = newNode;

newNode.prev = p;

}

//獲取第n個元素的數據值

this.getData = function (index) {

if (index < 1 || index > this.size) {

return null;

}

var p = this.head;

var i = 1;

while (p.next != null && i <= index) {

p = p.next;

i += 1;

}

return p.data;

}

//取尾節點

this.getTail = function () {

if (this.head.next == null) {

return null;

}

var p = this.head.next;

while (p.next != null) {

p = p.next;

}

return p;

}

//刪除指定位置的元素

this.removeAt = function (index) {

if (index < 1 || index > this.size) {

return null;

}

var p = this.head;

var i = 1;

//從頭開始遍歷，找到index位置的前一個元素

while (p.next != null && i < index) {

p = p.next;

i += 1;

}

p.next = p.next.next; //修改index位置前一個元素的后繼指針

p.next.prev = p;

return p.data; //返回刪除元素的值

}

//打印所有元素

this.print = function () {

document.write("<br/>");

if (this.head.next == null) {

return;

}

var p = this.head.next;

while (p.next != null) {

document.write(p.data + " ");

p = p.next;

}

document.write(p.data + " "); //最后一個元素，需要單獨打印

document.write("<br/>");

}

//從后打印所有元素

this.printFromBack = function () {

document.write("該鏈表共有" + this.size + "個元素，從后向前分別為:<br/>");

var tail = this.getTail();

var p = tail;

if (p == null) {

return;

}

while (p.prev != null) {

document.write(p.data + " ");

p = p.prev;

}

document.write("<br/>");

}

//插入排序

this.insertSort = function () {

if (this.head.next == null || this.head.next.next == null) {

return;

}

var p = this.head.next;

while (true) {

if (p == null) {

return;

}

var t = p.prev;

//向前查找p之前的插入點

while (t.prev != null && t.data > p.data) {

t = t.prev;

}

//如果插入點就是p的前驅節點，不用調整，

//忽略，直接進入下一輪

if (t.next == p) {

p = p.next;

continue;

}

//將p的后續節點先保護起來，以便下一輪循環時確定起始位置

var x = p.next;

//將p從鏈表上摘下

if (p.next != null) {

p.next.prev = p.prev;

}

p.prev.next = p.next;

//p插入到t之后

t.next.prev = p;

p.next = t.next;

t.next = p;

p.prev = t;

this.print(); //打印輸出，調試用

//重新將p定位到下一輪循環的"正確"起始節點

p = x;

}

}

}

var linkTest = new DbLinkList();

linkTest.insert(10);

linkTest.insert(9);

linkTest.insert(8);

linkTest.insert(7);

linkTest.insert(6);

linkTest.insert(5);

linkTest.insert(4);

linkTest.insert(3);

linkTest.insert(2);

linkTest.insert(1);

document.write("--排序前---<br/>")

linkTest.print();

linkTest.insertSort();

document.write("<br/>--排序后---<br/>")

linkTest.print();

</script>

</html>

運行結果如下：

--排序前---

10 9 8 7 6 5 4 3 2 1

9 10 8 7 6 5 4 3 2 1

8 9 10 7 6 5 4 3 2 1

7 8 9 10 6 5 4 3 2 1

6 7 8 9 10 5 4 3 2 1

5 6 7 8 9 10 4 3 2 1

4 5 6 7 8 9 10 3 2 1

3 4 5 6 7 8 9 10 2 1

2 3 4 5 6 7 8 9 10 1

1 2 3 4 5 6 7 8 9 10

--排序后---

1 2 3 4 5 6 7 8 9 10