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

發(fā)布時(shí)間：2020-09-10 02:03:55 來(lái)源：腳本之家閱讀：170 作者：布瑞澤的童話欄目：web開(kāi)發(fā)

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

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

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

高級(jí)語(yǔ)言中的數(shù)組與其相似，所以我們用數(shù)組來(lái)描述順序存儲(chǔ)結(jié)構(gòu)。

下面描述了邏輯關(guān)系的變化

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

下面我們來(lái)實(shí)現(xiàn)插入和刪除的過(guò)程

首先是插入

我們?cè)诘趇（1<=i<=n）個(gè)元素之前插入一個(gè)元素，需將第i至n個(gè)元素向后移動(dòng)一個(gè)位置。代碼如下

<!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個(gè)位置之前插入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個(gè)元素的代碼為

<!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個(gè)位置的值
  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>

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

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專(zhuān)題：《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ì)有所幫助。

向AI問(wèn)一下細(xì)節(jié)

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

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽