javascript数据结构之双链表插入排序实例详解
网络编程 2021-07-04 21:03www.168986.cn编程入门
这篇文章主要介绍了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
希望本文所述对大家JavaScript程序设计有所帮助。
编程语言
- 如何快速学会编程 如何快速学会ug编程
- 免费学编程的app 推荐12个免费学编程的好网站
- 电脑怎么编程:电脑怎么编程网咯游戏菜单图标
- 如何写代码新手教学 如何写代码新手教学手机
- 基础编程入门教程视频 基础编程入门教程视频华
- 编程演示:编程演示浦丰投针过程
- 乐高编程加盟 乐高积木编程加盟
- 跟我学plc编程 plc编程自学入门视频教程
- ug编程成航林总 ug编程实战视频
- 孩子学编程的好处和坏处
- 初学者学编程该从哪里开始 新手学编程从哪里入
- 慢走丝编程 慢走丝编程难学吗
- 国内十强少儿编程机构 中国少儿编程机构十强有
- 成人计算机速成培训班 成人计算机速成培训班办
- 孩子学编程网上课程哪家好 儿童学编程比较好的
- 代码编程教学入门软件 代码编程教程