快捷導(dǎo)航

JS實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎痉椒ㄊ纠窘?jīng)典數(shù)據(jù)結(jié)構(gòu)】

更新時(shí)間：2017年04月11日 12:18:03 作者：布瑞澤的童話

這篇文章主要介紹了JS實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎痉椒?簡(jiǎn)單講解了線性表鏈?zhǔn)奖硎镜脑聿⒔Y(jié)合實(shí)例形式分析了js針對(duì)線性表鏈?zhǔn)奖硎镜膭?chuàng)建、插入、刪除等節(jié)點(diǎn)操作技巧,需要的朋友可以參考下

本文實(shí)例講述了JS實(shí)現(xiàn)線性表的鏈?zhǔn)奖硎痉椒ā７窒斫o大家供大家參考，具體如下：

從上一節(jié)可以，順序存儲(chǔ)結(jié)構(gòu)的弱點(diǎn)就是在插入或刪除操作時(shí)，需要移動(dòng)大量元素。所以這里需要介紹一下鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，由于它不要求邏輯上相鄰的元素在物理位置上也相鄰，所以它沒有順序存儲(chǔ)結(jié)構(gòu)的弱點(diǎn)，但是也沒有順序表可隨機(jī)存取的優(yōu)點(diǎn)。

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

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素。所以，每一個(gè)數(shù)據(jù)元素除了存儲(chǔ)自身的信息之外，還需要存儲(chǔ)一個(gè)指向其后繼的存儲(chǔ)位置的信息。這兩部分信息組成了元素的存儲(chǔ)映像，稱為結(jié)點(diǎn)。

結(jié)點(diǎn)包括兩個(gè)域：數(shù)據(jù)域和指針域。

數(shù)據(jù)域是元素中存儲(chǔ)數(shù)據(jù)元素的信息。

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

n個(gè)結(jié)點(diǎn)鏈接成為鏈表，就是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，又由于此鏈表的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，所有又稱為線性鏈表或單鏈表。

舉一個(gè)例子

上圖表示的線性表為

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

這樣應(yīng)該就好理解多了吧。

下面我們通過js代碼來實(shí)現(xiàn)鏈表的插入和刪除還有查找操作

<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8"/>
<script type = "text/javascript">
 var Node = function(newData){//創(chuàng)建節(jié)點(diǎn)對(duì)象
 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){//移除某一位置節(jié)點(diǎn)
  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){//從某一位置前插入節(jié)點(diǎn)
  if(pos>=this.size||pos<0)
  return null;
  this.size+=1;
  tempNode=this.head;
  var newNode = new Node(data);//將數(shù)據(jù)創(chuàng)造節(jié)點(diǎn)
  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>");
 };
 };
 //運(yùn)行測(cè)試:
 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("查找操作下標(biāo)為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>

運(yùn)行得到結(jié)果為

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

 this.InsertBefore=function(data,pos){//從某一位置前插入節(jié)點(diǎn)
  if(pos>=this.size||pos<0)
    return null;
  this.size+=1;
  tempNode=this.head;
  var newNode = new Node(data);//將數(shù)據(jù)創(chuàng)造節(jié)點(diǎn)
  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){//移除某一位置節(jié)點(diǎn)
      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;
};

可以看出，插入和刪除的世界復(fù)雜度都為o(n)。因?yàn)樵诘趇個(gè)結(jié)點(diǎn)前插入或刪除都得找到第i-1個(gè)元素。

再來看看初始化方法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方法的時(shí)間復(fù)雜度也是o(n)。

下面介紹一下另外一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，就是循環(huán)鏈表。它的特點(diǎn)就表中的最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)。有時(shí)候，在循環(huán)鏈表中設(shè)立尾指針而不設(shè)立頭指針，可以簡(jiǎn)化操作。比如兩個(gè)線性表集合為一個(gè)表時(shí)，僅需將一個(gè)表的表尾和另一個(gè)表的表頭相接。這個(gè)操作的時(shí)間復(fù)雜度是o(1)。

如下圖所示

上面介紹的鏈表只能通過某個(gè)結(jié)點(diǎn)出發(fā)尋找后面的結(jié)點(diǎn)。也就是說在單鏈表中，尋找下一結(jié)點(diǎn)的時(shí)間復(fù)雜度為o(1)，而尋找上一結(jié)點(diǎn)的時(shí)間復(fù)雜度為o(n)。為了克服單鏈表這種單向性的缺點(diǎn)，可以利用雙向鏈表。

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》

希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: