JS實現(xiàn)線性表的順序表示方法示例【經(jīng)典數(shù)據(jù)結(jié)構】

更新時間：2017年04月11日 11:52:50 作者：布瑞澤的童話

這篇文章主要介紹了JS實現(xiàn)線性表的順序表示方法,簡單分析了線性表的原理并結(jié)合實例形式給出了線性表的插入與刪除實現(xiàn)技巧,需要的朋友可以參考下

本文實例講述了JS實現(xiàn)線性表的順序表示方法。分享給大家供大家參考，具體如下：

線性表的順序表示指的是用一組地址連接的存儲單元依次存儲線性表的數(shù)據(jù)元素。通常稱這種存儲結(jié)構的線性表為順序表。

順序表的特點是以元素在計算機內(nèi)物理位置相鄰來表示數(shù)據(jù)元素之間的邏輯關系。每一個數(shù)據(jù)元素的存儲位置都和線性表的起始位置相差一個和數(shù)據(jù)元素在線性表中的位序成正比的常數(shù)。也就是說只要確定了存儲線性表的起始位置，線性表中的任一元素都可以隨機存儲，所以說，順序表是一種隨機存取的存儲結(jié)構。

高級語言中的數(shù)組與其相似，所以我們用數(shù)組來描述順序存儲結(jié)構。

下面描述了邏輯關系的變化

下面我們來實現(xiàn)插入和刪除的過程

首先是插入

我們在第i（1<=i<=n）個元素之前插入一個元素，需將第i至n個元素向后移動一個位置。代碼如下

<!DOCTYPE html>
<html>
 <head>
 <meta charset="utf-8">
 <title></title>
 </head>
 <body onload="ListInsert([1,2,3,4],2,5)">
 </body>
 <script type="text/javascript">
 function ListInsert(a,i,e){
  //在a的第i個位置之前插入e
  var j,
  a_len=a.length;
  for(j=a_len-1;j>=i-1;j--){
  a[j+1]=a[j];
  }
  a[i-1]=e;
  alert(a);//1,5,2,3,4
 }
 </script>
</html>

同樣的道理，刪除第i個元素的代碼為

<!DOCTYPE html>
<html>
 <head>
 <meta charset="utf-8">
 <title></title>
 </head>
 <body onload="ListDelete([1,2,3,4,5,6,7,8],3)">
 </body>
 <script type="text/javascript">
 function ListDelete(a,i){
  //刪除a集合第i個位置的值
  var e=a[i-1],//被刪除的元素
  a_len=a.length;
  for(j=i-1;j<=a_len-1;j++){
  a[j-1]=a[j];
  }
  a[j-1]=null;
  alert(a);//1,2,4,5,6,7,8
 }
 </script>
</html>

從上面兩個算法可以看出，時間主要耗費在移動元素上，而移動元素的個數(shù)取決于插入或刪除元素的位置。根據(jù)概率論的相關知識，可以得出在順序存儲結(jié)構的線性表中插入或刪除一個數(shù)據(jù)元素時，平均約移動表中一般元素。如果表長為n，則上面兩個算法的時間復雜度是o(n/2)，又由于n/2和n都處于線性階。所以直接表示為o(n)

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

希望本文所述對大家JavaScript程序設計有所幫助。

您可能感興趣的文章: