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程序设计有所帮助。
相关推荐
-
JavaScript数组实现数据结构中的队列与堆栈
一.队列和堆栈的简单介绍 1.1.队列的基本概念 队列:是一种支持先进先出(FIFO)的集合,即先被插入的数据,先被取出! 如下图所示: 1.2.堆栈的基本概念 堆栈:是一种支持后进先出(LIFO)的集合,即后被插入的数据,先被取出! 如下图所示: 二. 在JavaScript中实现队列和堆栈 在JavaScript中实现队列和数组主要是通过数组,js数组中提供了以下几个方法可以让我们很方便实现队列和堆栈: •shift:从数组中把第一个元素删除,并返回这个元素的值. •unshift: 在数组
-
js单向链表的具体实现实例
复制代码 代码如下: function linkNode(_key, _value){ /// <summary> /// 链表类的节点类 /// </summary> this.Key = _key; this.Value = _value; this.next = null;}function Link(){ /// <summary> /// 创建一个链表类 /// </summary> th
-
Node.js环境下JavaScript实现单链表与双链表结构
单链表(LinkedList)的javascript实现 npmjs相关库: complex-list.smart-list.singly-linked-list 编程思路: add方法用于将元素追加到链表尾部,借由insert方法来实现: 注意各个函数的边界条件处理. 自己的实现: SingleNode.js (function(){ "use strict"; function Node(element){ this.element = element; this.next = n
-
JavaScript实现的链表数据结构实例
此例是javascript来建立链表.. 并对此进行了排序.. 还可以在GenericList一般链表上进行扩展. 实现各种排序及增,删,改结点.. 复制代码 代码如下: function Node(){ this.data=null; this.next=null; } function GenericList(){ this.head=null; this.current=null; //打出所有的链表结点 this.print= function(){ this
-
js实现双向链表互联网机顶盒实战应用实现
上实战代码: linkedlistnode.js 节点类 复制代码 代码如下: /* * 链表节点 */ Dare.LinkedListNode = function () { this.data = null;//数据域 this.prev = null;//前驱 this.next = null;//后驱 }; Dare.extend(Dare.LinkedListNode, Dare); Dare.LinkedListNode.prototype.getValue = function (
-
JavaScript数据结构和算法之图和图算法
图的定义 图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合. 有向图 有向边:若从顶点Vi到Vj的边有方向,则称这条边为有向边,也成为弧(Arc),用有序偶<Vi,Vj>来表示,Vi称为弧尾,Vj称为弧头. 无序图 无向边:若顶点Vi到Vj之间的边没有方向,则称这条边为无向边(Edge),用无序偶(Vi,Vj)来表示. 简单图 简单图:在图结构中,若不存在顶点到其自身的边,且同一条边不重复出现,
-
javascript循环链表之约瑟夫环的实现方法
前言 传说在公元1 世纪的犹太战争中,犹太历史学家弗拉维奥·约瑟夫斯和他的40 个同胞被罗马士兵包围.犹太士兵决定宁可自杀也不做俘虏,于是商量出了一个自杀方案.他们围成一个圈,从一个人开始,数到第三个人时将第三个人杀死,然后再数,直到杀光所有人.约瑟夫和另外一个人决定不参加这个疯狂的游戏,他们快速地计算出了两个位置,站在那里得以幸存.写一段程序将n 个人围成一圈,并且第m个人会被杀掉,计算一圈人中哪两个人最后会存活.使用循环链表解决该问题. 看到这个问题首先想到的是要用到循环链表,还有就是要计算
-
JavaScript数据结构和算法之二叉树详解
二叉树的概念 二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的.分别称为根结点的左子树和右子树的二叉树组成. 二叉树的特点 每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点.二叉树中每一个节点都是一个对象,每一个数据节点都有三个指针,分别是指向父母.左孩子和右孩子的指针.每一个节点都是通过指针相互连接的.相连指针的关系都是父子关系. 二叉树节点的定义 二叉树节点定义如下: 复制代码 代码如下: struct
-
JavaScript数据结构之链表的实现
前面楼主分别讨论了数据结构栈与队列的实现,当时所用的数据结构都是用的数组来进行实现,但是数组有的时候并不是最佳的数据结构,比如在数组中新增删除元素的时候需要将其他元素进行移动,而在javascript中使用spit()方法不需要访问其他元素.如果你在使用数组的时候发现很慢,就可以考虑使用链表. 链表的概念 链表是一种常见的数据结构.它是动态地进行存储分配的一种结构.链表有一个"头指针"变量,以head表示,它存放一个地址,指向一个元素.每个结点都使用一个对象的引用指标它的后继,指向另一
-
JavaScript实现链表插入排序和链表归并排序
本篇文章详细的介绍了JavaScript实现链表插入排序和链表归并排序,链表的归并排序就是对每个部分都进行归并排序,然后合并在一起. 1.链表 1.1链表的存储表示 //链表的存储表示 typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList; 1.2基本操作 创建链表: /* * 创建链表. * 形参num为链表的长度,函数返回链表的头指针. */ Link
-
JavaScript数据结构之双向链表定义与使用方法示例
本文实例讲述了JavaScript数据结构之双向链表定义与使用方法.分享给大家供大家参考,具体如下: 双向链表和普通链表的区别在于,在链表中,一个节点只有链向下一个节点的链接,而在双向链表中,链接是双向的:一个链向下一个元素,另一个链向前一个元素. 双向链表提供了两种迭代列表的方法:从头到尾,或者反过来.我们也可以访问一个特定节点的下一个或前一个元素.在单向链表中,如果迭代列表时错过了要找的元素,就需要回到列表起点,重新开始迭代.这是双向链表的一个优点. function DoubleLink(
-
使用JavaScript实现链表的数据结构的代码
链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer) - 维基百科 上面是维基百科对 链表 的解读.下面我们用 JavaScript 代码对链表的数据结构进行实现 实现Node类表示节点 /** * Node 类用来表示节点 * element 用来保存节点上的数据 * next 用来保存指向下一个节点的链接 */ function Node(element) { this.elemen