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