首頁 > web前端 > js教程 > 主體

JavaScript資料結構之鍊錶的實作方法介紹(圖文)

黄舟
發布: 2017-03-20 14:24:57
原創
1600 人瀏覽過

鍊錶是一種常見的資料結構。它是動態地進行儲存分配的一種結構。本文主要介紹JavaScript資料結構中鍊錶的實現,具有很好的參考價值。下面跟著小編一起來看下吧

前面樓主分別討論了資料結構棧與佇列的實現,當時所用的資料結構都是用的陣列來進行實現,但是陣列有的時候並不是最佳的資料結構,例如在陣列中新增刪除元素的時候需要將其他元素進行移動,而在javascript中使用spit()方法不需要存取其他元素。如果你在使用陣列的時候發現很慢,就可以考慮使用鍊錶。

鍊錶的概念

鍊錶是常見的資料結構。它是動態地進行儲存分配的一種結構。鍊錶有一個「頭指標」變量,以head表示,它存放一個位址,指向一個元素。每個結點都使用一個物件引用指標它的後繼,指向另一個結點的引用叫做鏈。

陣列元素依賴下標(位置)來進行引用,而鍊錶元素則是靠相互之間的關係來進行引用。因此鍊錶的插入效率很高,下圖示範了鍊錶結點d的插入過程: 

 

刪除過程:

基於物件的鍊錶

我們定義2個類,Node類別與LinkedList類,Node為結點數據,LinkedList保存操作鍊錶的方法。

首先看Node類別:  

function Node(element){
  this.element = element;
   this.next = null;
 }
登入後複製

element用來保存結點上的數據,next用來保存指向一下結點的連結。

LinkedList類別:

function LinkedList(){
     this.head = new Node('head');
     this.find = find;
     this.insert = insert;
     this.remove = remove;
     this.show = show;
}
登入後複製

find()方法,從頭結點開始,沿著鍊錶結點一直查找,直到找到與item內容相等的element則傳回該結點,沒找到則返回空。

function find(item){
     var currentNode = this.head;//从头结点开始
     while(currentNode.element!=item){
         currentNode = currentNode.next;
     }
     return currentNode;//找到返回结点数据,没找到返回null
}
登入後複製

Insert方法。透過前面元素插入的示範可以看出,實現插入簡單四步驟:

1、建立結點

#2、找到目標結點

3、修改目標結點的next指向連結

4、將目標結點的next值賦值給要插入的結點的next

function insert(newElement,item){
     var newNode = new Node(newElement);
     var currentNode = this.find(item);
     newNode.next = currentNode.next;
     currentNode.next = newNode;
 }
登入後複製

Remove()方法。刪除某一節點需要先找到被刪除結點的前結點,為此我們定義方法frontNode():

function frontNode(item){
     var currentNode = this.head;
     while(currentNode.next.element!=item&&currentNode.next!=null){
         currentNode = currentNode.next;
     }   
     return currentNode;
}
登入後複製

簡答三步驟:

1、建立結點

2、找到目標結點的前結點

3、修改前結點的next指向被刪除結點的n後一個結點

function remove(item){
     var frontNode = this.frontNode(item);
     //console.log(frontNode.element);
     frontNode.next = frontNode.next.next;
 }
登入後複製

Show()方法:

function show(){
     var currentNode = this.head,result;
     while(currentNode.next!=null){
         result += currentNode.next.element;//为了不显示head结点
         currentNode = currentNode.next;
     }
}
登入後複製

測試程式:

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());
登入後複製
登入後複製

輸出:

雙向鍊錶

##從鍊錶的頭節點遍歷到尾節點很簡單,但有的時候,我們需要從後向前遍。此時我們可以透過為 Node 物件增加一個

屬性,該屬性儲存指向前驅節點的連結。樓主用下圖來雙向鍊錶的工作原理。

首先我們先為Node類別增加front屬性:  

function Node(element){
  this.element = element;
  this.next = null;
   this.front = null;
 }
登入後複製

當然,對應的insert()方法和remove()方法我們也需要做對應的修改: 

function insert(newElement,item){
  var newNode = new Node(newElement);
  var currentNode = this.find(item);
  newNode.next = currentNode.next;
  newNode.front = currentNode;//增加front指向前驱结点
  currentNode.next = newNode;
}
function remove(item){  
  var currentNode = this.find(item);//找到需要删除的节点
  if (currentNode.next != null) {
    currentNode.front.next = currentNode.next;//让前驱节点指向需要删除的节点的下一个节点
    currentNode.next.front = currentNode.front;//让后继节点指向需要删除的节点的上一个节点
    currentNode.next = null;//并设置前驱与后继的指向为空
    currentNode.front = null;    
  }  
}
登入後複製

反序顯示鍊錶:

需要為雙向鍊錶增加一個方法,用來找出最後的節點。 findLast() 方法找出了鍊錶中的最後一個節點,可以免除從前往後遍歷鏈。

function findLast() {//查找链表的最后一个节点
  var currentNode = this.head;
  while (currentNode.next != null) {
    currentNode = currentNode.next;
  }
  return currentNode;
}
登入後複製

實作反序輸出:

function showReverse() {
  var currentNode = this.head, result = "";
  currentNode = this.findLast(); 
  while(currentNode.front!=null){
    result += currentNode.element + " ";
    currentNode = currentNode.front;
  }
  return result;
}
登入後複製

測試程式:

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list);
list.remove("b");
console.log(list.show());
console.log(list.showReverse());
登入後複製

輸出:

#。循環鍊錶


循環鍊錶是另一種形式的鍊式存貯結構。它的特徵是表中最後一個結點的指標域指向頭結點,整個鍊錶形成一個環。循環鍊錶和單向鍊錶相似,節點類型都是一樣的。唯一的差異是,在建立循環鍊錶時,讓其頭節點的next 屬性指向它本身,即:

head.next = head

這種行為會傳導至鍊錶中的每個節點,使得每個節點的next 屬性都指向鍊錶的頭節點。樓主用下圖表示循環鍊錶:

修改

建構方法

这时需要注意链表的输出方法show()与find()方法,原来的方式在循环链表里会陷入死循环,while循环的循环条件需要修改为当循环到头节点时退出循环。

function find(item){
  var currentNode = this.head;//从头结点开始
  while(currentNode.element!=item&&currentNode.next.element!='head'){
    currentNode = currentNode.next;
  }
  return currentNode;//找到返回结点数据,没找到返回null
}
function show(){
  var currentNode = this.head,result = "";
  while (currentNode.next != null && currentNode.next.element != "head") {   
    result += currentNode.next.element + " ";
    currentNode = currentNode.next;
  }
  return result;
}
登入後複製

测试程序:

var list = new LinkedList();
list.insert("a","head");
list.insert("b","a");
list.insert("c","b");
console.log(list.show());
list.remove("b");
console.log(list.show());
登入後複製
登入後複製

测试结果:

以上是JavaScript資料結構之鍊錶的實作方法介紹(圖文)的詳細內容。更多資訊請關注PHP中文網其他相關文章!

來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板
關於我們 免責聲明 Sitemap
PHP中文網:公益線上PHP培訓,幫助PHP學習者快速成長!