javascript数据结构之双链表插入排序实例详解
本文实例讲述了javascript数据结构之双链表插入排序实现方法。分享给大家供大家参考，具体如下：
数组存储前提下，插入排序算法，在最坏情况下，前面的元素需要不断向后移，以便在插入点留出空位，让目标元素插入。
换成链表时，显然无需做这种大量移动，根据每个节点的前驱节点“指针”，向前找到插入点后，直接把目标值从原链表上摘下，然后在插入点把链表断成二截，然后跟目标点重新接起来即可。
<!doctypehtml>
<html>
<head>
<title>双链表-插入排序</title>
<metahttp-equiv="Content-Type"content="text/html;charset=gb2312"/>
</head>
<scripttype="text/javascript">
//节点类
varNode=function(pData){
this.next=null;//后继“指针”
this.prev=null;//前驱"指针"
this.data=pData;
}
//单链表(约定：头节点不放内容，当哨兵位，有效元素从头节点后的第1个元素开始)
varDbLinkList=function(){
this.head=newNode(null);//头节点
//插入新元素
this.insert=function(pNodeValue){
varnewNode=newNode(pNodeValue);
//如果只有头节点
if(this.head.next==null){
this.head.next=newNode;
newNode.prev=this.head;
return;
}
//否则遍历找到尾节点
varp=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){
returnnull;
}
varp=this.head;
vari=1;
while(p.next!=null&&i<=index){
p=p.next;
i+=1;
}
returnp.data;
}
//取尾节点
this.getTail=function(){
if(this.head.next==null){
returnnull;
}
varp=this.head.next;
while(p.next!=null){
p=p.next;
}
returnp;
}
//删除指定位置的元素
this.removeAt=function(index){
if(index<1||index>this.size){
returnnull;
}
varp=this.head;
vari=1;
//从头开始遍历，找到index位置的前一个元素
while(p.next!=null&&i<index){
p=p.next;
i+=1;
}
p.next=p.next.next;//修改index位置前一个元素的后继指针
p.next.prev=p;
returnp.data;//返回删除元素的值
}
//打印所有元素
this.print=function(){
document.write("<br/>");
if(this.head.next==null){
return;
}
varp=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/>");
vartail=this.getTail();
varp=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;
}
varp=this.head.next;
while(true){
if(p==null){
return;
}
vart=p.prev;
//向前查找p之前的插入点
while(t.prev!=null&&t.data>p.data){
t=t.prev;
}
//如果插入点就是p的前驱节点，不用调整，
//忽略，直接进入下一轮
if(t.next==p){
p=p.next;
continue;
}
//将p的后续节点先保护起来，以便下一轮循环时确定起始位置
varx=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;
}
}
}
varlinkTest=newDbLinkList();
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>
运行结果如下：
--排序前--- 10987654321 91087654321 89107654321 78910654321 67891054321 56789104321 45678910321 34567891021 23456789101 12345678910 --排序后--- 12345678910
希望本文所述对大家JavaScript程序设计有所帮助。