JS實現線性表的鏈式表示方法示例【經典數據結構】

2019-11-19 16:51:42

字體：大中小

來源：轉載

供稿：網友

本文實例講述了JS實現線性表的鏈式表示方法。分享給大家供大家參考，具體如下：

從上一節可以，順序存儲結構的弱點就是在插入或刪除操作時，需要移動大量元素。所以這里需要介紹一下鏈式存儲結構，由于它不要求邏輯上相鄰的元素在物理位置上也相鄰，所以它沒有順序存儲結構的弱點，但是也沒有順序表可隨機存取的優點。

下面介紹一下什么是鏈表。

線性表的鏈式存儲結構用一組任意的存儲單元存儲線性表的數據元素。所以，每一個數據元素除了存儲自身的信息之外，還需要存儲一個指向其后繼的存儲位置的信息。這兩部分信息組成了元素的存儲映像，稱為結點。

結點包括兩個域：數據域和指針域。

數據域是元素中存儲數據元素的信息。

指針域是元素中存儲的后繼存儲位置的信息。

n個結點鏈接成為鏈表，就是線性表的鏈式存儲結構，又由于此鏈表的每個結點中只包含一個指針域，所有又稱為線性鏈表或單鏈表。

舉一個例子

上圖表示的線性表為

ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG

這樣應該就好理解多了吧。

下面我們通過js代碼來實現鏈表的插入和刪除還有查找操作

<!DOCTYPE html><html><head><meta charset="UTF-8"/><script type = "text/javascript"> var Node = function(newData){//創建節點對象 this.next = null; this.data = null; this.Init = function(){  this.data = newData; }; this.Init(); } //定義鏈表類 var List = function(){ this.head = null; this.size = 0; this.Init = function(){  this.head = null;  this.size = 0; } this.Init(); this.Insert = function(newData){//初始批量插入操作  this.size += 1;  var newNode = new Node(newData);  if(this.head == null){  this.head = newNode;  return;  }  var tempNode = this.head;  while(tempNode.next != null)  tempNode = tempNode.next;//找到鏈表尾部  tempNode.next = newNode;//將新元素插入到鏈表尾部 }; this.GetData = function(pos){//查找操作  if(pos >= this.size || pos < 0)  return null;  else{  tempNode = this.head;  for(i = 0;i < pos;i++)   tempNode = tempNode.next; //找到所處位置  return tempNode.data;  } }; this.Remove = function(pos){//移除某一位置節點  if(pos >= this.size || pos < 0)  return null;  this.size -= 1;  tempNode = this.head;  if(pos == 0){  this.head = this.head.next;  return this.head;  }  for(i = 0;i < pos - 1;i++){  tempNode = tempNode.next;  }  tempNode.next = tempNode.next.next;  return tempNode.next; }; this.InsertBefore=function(data,pos){//從某一位置前插入節點  if(pos>=this.size||pos<0)  return null;  this.size+=1;  tempNode=this.head;  var newNode = new Node(data);//將數據創造節點  if(pos==0){  newNode.next=tempNode;  return newNode.next;  }  for(i=0;i<pos-1;i++){  tempNode=tempNode.next;//找到插入的位置  }  newNode.next=tempNode.next;//插入操作  tempNode.next=newNode;  return newNode.next; }; this.Print = function(){//輸出  document.write("鏈表中元素: <br>");  tempNode = this.head;  while(tempNode != null){  document.write(tempNode.data + " ");  tempNode = tempNode.next;  }  document.write("<br>"); }; }; //運行測試: var list = new List(); var array = new Array(1,2,3,4,5,6); for(i = 0;i < array.length;i++){ list.Insert(array[i]); } list.Print(); document.write("查找操作下標為4的元素: <br>"); var data= list.GetData(4); document.write(data+"<br>"); document.write("刪除操作: <br>"); list.Remove(5); list.Print(); document.write("插入操作: <br>"); list.InsertBefore(8,3); list.Print(); document.write("鏈表大小: " + list.size);</script></head><body></body></html>

運行得到結果為

先分析一下插入和刪除的代碼。

 this.InsertBefore=function(data,pos){//從某一位置前插入節點  if(pos>=this.size||pos<0)    return null;  this.size+=1;  tempNode=this.head;  var newNode = new Node(data);//將數據創造節點  if(pos==0){    newNode.next=tempNode;    return newNode.next;  }  for(i=0;i<pos-1;i++){    tempNode=tempNode.next;//找到插入的位置  }    newNode.next=tempNode.next;//插入操作    tempNode.next=newNode;  return newNode.next;};this.Remove = function(pos){//移除某一位置節點      if(pos >= this.size || pos < 0)       return null;      this.size -= 1;      tempNode = this.head;      if(pos == 0){       this.head = this.head.next;       return this.head;      }      for(i = 0;i < pos - 1;i++){       tempNode = tempNode.next;      }      tempNode.next = tempNode.next.next;      return tempNode.next;};

可以看出，插入和刪除的世界復雜度都為o(n)。因為在第i個結點前插入或刪除都得找到第i-1個元素。

再來看看初始化方法Insert，

this.Insert = function(newData){//初始批量插入操作      this.size+= 1;      var newNode = new Node(newData);      if(this.head == null){       this.head = newNode;       return;      }      var tempNode = this.head;      while(tempNode.next != null)       tempNode = tempNode.next;//找到鏈表尾部      tempNode.next= newNode;//將新元素插入到鏈表尾部};

初始的插入Insert方法的時間復雜度也是o(n)。

下面介紹一下另外一種形式的鏈式存儲結構，就是循環鏈表。它的特點就表中的最后一個結點的指針域指向頭結點，整個鏈表形成一個環。有時候，在循環鏈表中設立尾指針而不設立頭指針，可以簡化操作。比如兩個線性表集合為一個表時，僅需將一個表的表尾和另一個表的表頭相接。這個操作的時間復雜度是o(1)。

如下圖所示