DIV CSS 佈局教程網

JavaScript實作鏈結串列資料結構並排序
編輯:關於JavaScript     

這個例子用 JavaScript 打造了一個鏈結串列,並在其上實作了排序。

由於 GenericList 是一般化的串列結構,後續可以很容易地擴充各種排序方式,以及節點的增、刪、改操作。

function Node(){
  this.data=null;
  this.next=null;
}

function GenericList(){
  this.head=null;
  this.current=null; 
  //打出所有的鏈表結點
  this.print= function(){
  this.current=this.head;
   while(this.current!=null){
      alert(this.current.data);
      this.current=this.current.next;
   }
  
  },
  //建立鏈表
  this.addHead =function(t){
      
  
      var node=new Node();
      node.data=t;
      node.next=this.head;
      this.head=node;
 
  }
  
 
}

function SortList(){
//冒泡排序鏈表 
this.BubbleSort=function()
   {
     if(this.head==null||this.head.next==null)
     {
        return ;
     }
    var swapped;
    do{
    
     this.previous=null;
     this.current=this.head;

     var swapped=false;
     while(this.current.next!=null)
      {
       
       if(this.current.data-this.current.next.data>0)
       {
       
       var tmp=this.current.next;
       this.current.next=this.current.next.next;
       tmp.next=this.current;
       if(this.previous==null)
          {
              this.head=tmp;
          }
          else
          {
              this.previous.next=tmp;
          }
          this.previous=tmp;
          swapped=true;
        
       
       }
       else
       {
       
       this.previous=this.current;
       this.current=this.current.next;
       
       }
     
     }
     
      
    
    }while(swapped);
   
   }

}

SortList.prototype=new GenericList();


(function Main(){
 var sl=new  SortList();
 for(var i=0;i<arguments.length;i++)
 {sl.addHead(arguments[i]);
 }
 alert("未排序的鏈表");
 sl.print();
 sl.BubbleSort();
  alert("已排序的鏈表  從小到大");
 sl.print();

})("1","2","3","4")

幾個值得留意的實作細節:addHead 採頭插法,每次新增節點都掛在 head 前面,因此輸入 "1","2","3","4" 後串列實際是 4→3→2→1;SortList.prototype = new GenericList() 讓 SortList 繼承了 print 與 addHead;冒泡排序在交換時需要同時維護 previous 與 current 兩個指標,並在換到頭節點時更新 head,這是鏈結串列排序最容易出錯的地方。範例中的比較用相減進行,若資料可能為字串,記得改用 > 或 localeCompare 才不會出現 NaN。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved