亚洲激情专区-91九色丨porny丨老师-久久久久久久女国产乱让韩-国产精品午夜小视频观看

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

怎么在JavaScript中利用線性表表示鏈式

發布時間:2021-04-09 17:37:57 來源:億速云 閱讀:152 作者:Leah 欄目:web開發

怎么在JavaScript中利用線性表表示鏈式?很多新手對此不是很清楚,為了幫助大家解決這個難題,下面小編將為大家詳細講解,有這方面需求的人可以來學習下,希望你能有所收獲。

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

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

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

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

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

舉一個例子

怎么在JavaScript中利用線性表表示鏈式

上圖表示的線性表為

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>

運行得到結果為

怎么在JavaScript中利用線性表表示鏈式

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

 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)。

如下圖所示

怎么在JavaScript中利用線性表表示鏈式

看完上述內容是否對您有幫助呢?如果還想對相關知識有進一步的了解或閱讀更多相關文章,請關注億速云行業資訊頻道,感謝您對億速云的支持。

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

泽普县| 黄骅市| 自治县| 武乡县| 万全县| 千阳县| 长治市| 海口市| 两当县| 沛县| 内黄县| 丹凤县| 天气| 文昌市| 虎林市| 嵊泗县| 资兴市| 和顺县| 宝坻区| 辉南县| 锡林郭勒盟| 青州市| 姜堰市| 木里| 荥经县| 奎屯市| 松潘县| 海淀区| 凤山市| 元谋县| 淳安县| 河北省| 连平县| 新建县| 逊克县| 德州市| 崇仁县| 永清县| 桐城市| 德庆县| 晋江市|