快捷導(dǎo)航

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

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

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

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

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

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

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

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

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

首先是插入

我們?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)容感興趣的讀者可查看本站專題：《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ì)有所幫助。

您可能感興趣的文章: