学习写链表!~~~~

Myth丶恋晨 2022-08-07 07:48 158阅读 0赞

链表

链表有线性链表,循环链表,双向链表.

线性 : 最后一个节点不指向其他节点

循环 : 最后一个节点指向头节点

双向 : 双向链表也叫双链表，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点.

有图有真相

![a][]

![b][]

![c][]

比想象的要烦琐的多.测试都花了好多时间,还不知道是不是完全正确,郁闷..............................

单链表...

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="Content-Type" content="text/html; charset=gb2312" /> <title>List</title> <style type="text/css"> div \{ height:30px ; width:auto;font-size:14px; padding-left:100px; \} </style> </head> <body> <body > <script> function LinkedList()\{ this.\_length = 0; this.\_head = null; //永远保存第一个节点 \}; LinkedList.prototype = \{ constructor : LinkedList, add : function(data)\{ var item = \{ data : data, next : null \}; if(this.\_head == null)\{ this.\_head = item; \}else\{ this.find(this.\_length-1).next = item ; \} this.\_length++; \}, find : function(index)\{ if(index < 0||index > this.\_length-1)return; var item = this.\_head,i = 0; while(i++<index) \{ item = item.next; \} return item; \}, insert : function(data,index)\{ if(index < 0||index > this.\_length)return; var item = \{ data : data, next : null \}; this.find(index)&&(item.next=this.find(index)); this.find(index-1)&&(this.find(index-1).next = item); index==0&&(this.\_head = item); this.\_length++; return item; \}, remove :function(index)\{ if(index < 0||index > this.\_length-1)return; var item = this.find(index); index==0&&(this.\_head = this.find(1)); this.find(index+1)&&this.find(index-1)&&(this.find(index-1).next = item.next); this.\_length--; return item; \}, toArray : function()\{ var arrs = \[\],item = this.\_head; while(item)\{ arrs.push(item.data); item = item.next; \} return arrs ; \} \}; var list = null,ss=null; window.onload = function()\{ ss=document.getElementById("ss"); list = new LinkedList(); list.add("111"); list.add("222"); list.add("333"); list.add("444"); list.add("555"); list.add("666"); \} function showlength()\{ alert(list.\_length); \}; function show()\{ var str = ""; for(var i=0,l=list.\_length;i<l;i++) \{ str = str+"第"+i+"组数据为："+list.find(i).data+"<br>"; \} ss.innerHTML = str; \} function insertdata(arg)\{ switch(arg)\{ case 1 : list.insert("toutoutou",0) show(); break ; case 2 : list.insert("zhongzhongzhong",parseInt(list.\_length/2+1)) show(); break; case 3 : list.insert("weiweiwei",list.\_length); show(); break; \} \} function removedata()\{ var n = parseInt(document.getElementById('bb').value) list.remove(n); show(); \} function toArraydata()\{ ss.innerHTML = list.toArray(); \} </script> <div id="ss" style="height:450px ; width:700px; border:1px solid \#333333; margin-left:80px; font-size:14px; "></div> <div> 显示链表的长度:<input value="sssssss" type="button" οnclick="showlength()"/> </div> <div> 显示连表里面的数据:<input value="sssssss" type="button" οnclick="show()"/> </div> <div> 插入新的数据:<input value="表头插入" type="button" οnclick="insertdata(1)"/>　 <input value="中间插入" type="button" οnclick="insertdata(2)"/> 　 <input value="尾部插入" type="button" οnclick="insertdata(3)"/> </div> <div> 删除数据:<input value="sssssss" type="button" οnclick="removedata()"/>　 <input id="bb" type="text" /> </div> <div> 转成数组的形式:<input value="sssssss" type="button" οnclick="toArraydata()"/> </div> </body> </body> </html>

循环列表...........

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="Content-Type" content="text/html; charset=gb2312" /> <title>CriLink</title> <style type="text/css"> div \{ height:30px ; width:auto;font-size:14px; padding-left:100px; \} </style> </head> <body > <script> function CriList()\{ this.\_length = 0; this.\_head = null; \} CriList.prototype = \{ constructor : CriList, add : function(data)\{ var item =\{ head : data, next : null \}; if(this.\_length == 0)\{ this.\_head = item; item.next = item; \}else\{ item.next = this.\_head; this.find(this.\_length - 1).next = item; \} this.\_length++; \}, find : function(index)\{ if(index < 0 || index > this.\_length-1) return; var item = this.\_head,i=0; while(i++<index)\{ item = item.next; \}; return item; \}, insert :function(data,index)\{ if(index < 0 || index > this.\_length)return; var item =\{ head : data, next : null \} if(index == 0) \{ this.find(this.\_length-1).next = item; item.next = this.find(0); this.\_head = item; \}else if(index == this.\_length)\{ this.add(data); return item; \}else\{ item.next = this.find(index-1).next; this.find(index-1).next = item; \} this.\_length++; return item; \}, remove : function(index)\{ if(index < 0 || index > this.\_length-1)return; if(index ==0) \{ this.find(this.\_length-1).next =this.\_head.next; this.\_head = this.\_head.next; \}else if(index == this.\_length-1)\{ this.find(index-1).next = this.\_head; \}else \{ this.find(index-1).next = this.find(index).next \} this.\_length--; \}, toArray : function()\{ var arrs = \[\],item = this.\_head; for(var i=0;i<this.\_length;i++) \{ arrs.push(item.head) item = item.next; \} return arrs ; \} \} var list = null,ss=null; window.onload = function()\{ ss=document.getElementById("ss"); list = new CriList(); list.add("111"); list.add("222"); list.add("333"); list.add("444"); list.add("555"); \} function cc()\{ ss.innerHTML=list.find(list.\_length-1).next.head; \} function showlength()\{ alert(list.\_length); \}; function show()\{ var str = ""; for(var i=0,l=list.\_length;i<l;i++) \{ str = str+"第"+i+"组数据为："+list.find(i).head+"<br>"; \} ss.innerHTML = str; \} function insertdata(arg)\{ switch(arg)\{ case 1 : list.insert("toutoutou",0) show(); break ; case 2 : list.insert("zhongzhongzhong",parseInt(list.\_length/2+1)) show(); break; case 3 : list.insert("weiweiwei",list.\_length); show(); break; \} \} function removedata()\{ var n = parseInt(document.getElementById('bb').value) list.remove(n); show(); \} function toArraydata()\{ ss.innerHTML = list.toArray(); \} </script> <div id="ss" style="height:450px ; width:700px; border:1px solid \#333333; margin-left:80px; font-size:14px; "></div> <div> 查看最后一个节点的next:<input value="sssssss" type="button" οnclick="cc()"/> </div> <div> 显示链表的长度:<input value="sssssss" type="button" οnclick="showlength()"/> </div> <div> 显示连表里面的数据:<input value="sssssss" type="button" οnclick="show()"/> </div> <div> 插入新的数据:<input value="表头插入" type="button" οnclick="insertdata(1)"/>　 <input value="中间插入" type="button" οnclick="insertdata(2)"/> 　 <input value="尾部插入" type="button" οnclick="insertdata(3)"/> </div> <div> 删除数据:<input value="sssssss" type="button" οnclick="removedata()"/>　 <input id="bb" type="text" /> </div> <div> 转成数组的形式:<input value="sssssss" type="button" οnclick="toArraydata()"/> </div> </body> </html>

双向链表...........

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="Content-Type" content="text/html; charset=gb2312" /> <title>DoubleList</title> <style type="text/css"> div \{ height:30px ; width:auto;font-size:14px; padding-left:100px; \} </style> </head> <body > <script> function DoubleList()\{ this.\_length = 0; this.\_head = null; \} DoubleList.prototype = \{ constructor : DoubleList, find : function(index)\{ if(index < 0 || index > this.\_length -1)return; var item = this.\_head,i=0; while(i++<index)\{ item = item.next; \} return item; \}, add:function(data)\{ var item = \{ data : data, previous : null, next : null \}; if(this.\_length == 0)\{ item.next = item; item.previous = item; this.\_head = item; \}else\{ item.next = this.\_head; item.previous = this.find(this.\_length-1); this.find(this.\_length-1).next = item; this.find(0).previous = item; \} this.\_length++; return item; \}, insert : function(data,index)\{ if(index < 0||index > this.\_length) return; var item = \{ data : data, previous : null, next : null \}; if(this.\_length==0)\{ return this.add(data); \}; if(index==0)\{ item.previous = this.find(this.\_length-1); item.next = this.find(0); this.find(this.\_length-1).next = item; this.\_head = item; \}else if(index == this.\_length)\{ item.previous = this.find(this.\_length-1); item.next = this.find(0); this.find(this.\_length-1).next = item; this.find(0).preious = item; \}else\{ item.previous = this.find(index-1); item.next = this.find(index); this.find(index).previous =item this.find(index-1).next = item; \} this.\_length++; return item; \}, remove : function(index)\{ if(index < 0||index>this.\_length-1)return; var p = null,n = null,c=this.find(index); if(this.\_length==1) \{ this.\_head = null; this.\_length--; return c; \} if(index==0)\{ p = this.find(this.\_length-1); n = this.find(1); this.\_head = n; \}else if(index==this.\_length-1)\{ p = this.find(index-1); n = this.find(0); \}else\{ p = this.find(index-1); n = this.find(index+1); \} p.next = n; n.previous = p; this.\_length--; return c; \}, toArray : function()\{ var arrs = \[\],item = this.\_head; for(var i=0;i<this.\_length;i++) \{ arrs.push(item.data); item = item.next; \} return arrs; \} \} var list =ss= null; window.onload = function()\{ ss = document.getElementById('ss'); list = new DoubleList(); list.add("111"); list.add("222"); list.add("333"); list.add("444"); \} function cc()\{ ss.innerHTML=list.find(list.\_length-1).next.data; \} function nn()\{ ss.innerHTML=list.find(0).previous.data; \} function showlength()\{ alert(list.\_length); \}; function show()\{ var str = ""; for(var i=0,l=list.\_length;i<l;i++) \{ str = str+"第"+i+"组数据为："+list.find(i).data+"<br>"; \} ss.innerHTML = str; \} function insertdata(arg)\{ switch(arg)\{ case 1 : list.insert("toutoutou",0) show(); break ; case 2 : list.insert("zhongzhongzhong",parseInt(list.\_length/2+1)) show(); break; case 3 : list.insert("weiweiwei",list.\_length); show(); break; \} \} function removedata()\{ var n = parseInt(document.getElementById('bb').value) list.remove(n); show(); \} function toArraydata()\{ ss.innerHTML = list.toArray(); \} </script> <div id="ss" style="height:450px ; width:700px; border:1px solid \#333333; margin-left:80px; font-size:14px; "></div> <div> 查看最后一个节点的next:<input value="sssssss" type="button" οnclick="cc()"/> </div> <div> 查看第一个节点的previous:<input value="sssssss" type="button" οnclick="nn()"/> </div> <div> 显示链表的长度:<input value="sssssss" type="button" οnclick="showlength()"/> </div> <div> 显示连表里面的数据:<input value="sssssss" type="button" οnclick="show()"/> </div> <div> 插入新的数据:<input value="表头插入" type="button" οnclick="insertdata(1)"/>　 <input value="中间插入" type="button" οnclick="insertdata(2)"/> 　 <input value="尾部插入" type="button" οnclick="insertdata(3)"/> </div> <div> 删除数据:<input value="sssssss" type="button" οnclick="removedata()"/>　 <input id="bb" type="text" /> </div> <div> 转成数组的形式:<input value="sssssss" type="button" οnclick="toArraydata()"/> </div> </body> </html>

[a]: http://album.hi.csdn.net/app_uploads/wtcsy/20090819/101652305.p.jpg
[b]: http://album.hi.csdn.net/app_uploads/wtcsy/20090819/101653462.p.jpg
[c]: http://album.hi.csdn.net/app_uploads/wtcsy/20090819/101653524.p.jpg