[[407946]]

本文轉(zhuǎn)載自微信公眾號(hào)「前端萬(wàn)有引力」，作者一川。轉(zhuǎn)載本文請(qǐng)聯(lián)系前端萬(wàn)有引力公眾號(hào)。

寫(xiě)在前面

對(duì)于開(kāi)發(fā)而言，數(shù)組是我們經(jīng)常打交道的數(shù)據(jù)類(lèi)型，那么它的內(nèi)部存儲(chǔ)結(jié)構(gòu)是怎樣的呢?我們將進(jìn)行詳細(xì)介紹。

線性表

線性表是最基本、最簡(jiǎn)單，也是最常用的一種數(shù)據(jù)結(jié)構(gòu)，線性表就是n個(gè)具有相同特性的數(shù)據(jù)元素的有序數(shù)列。

前驅(qū)元素：若A元素在B元素的前面，則稱(chēng)A為B的前驅(qū)元素。

后驅(qū)元素：若B元素在A元素的后面，則稱(chēng)B為A的后驅(qū)元素。

線性表的分類(lèi)：線性表中數(shù)據(jù)存儲(chǔ)的方式是分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，其中：

• 順序存儲(chǔ)是用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。
• 鏈?zhǔn)酱鎯?chǔ)是用一段地址不連續(xù)的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)，而使用結(jié)點(diǎn)進(jìn)行連接查詢(xún)地址。

隨機(jī)訪問(wèn)：由于線性表存儲(chǔ)在連續(xù)的內(nèi)存位置，因此可以通過(guò)它們的索引來(lái)計(jì)算內(nèi)存地址，以便隨機(jī)訪問(wèn)數(shù)據(jù)。

順序表

順序表的存儲(chǔ)方式其實(shí)就是在內(nèi)存中找到空位置后進(jìn)行占位，然后將數(shù)據(jù)元素依次進(jìn)行存放到空位置。

是不是聽(tīng)起來(lái)有點(diǎn)像數(shù)組的結(jié)構(gòu)，對(duì)的，數(shù)據(jù)就是一種線性表結(jié)構(gòu)。因此我們可以使用數(shù)組進(jìn)行表示順序表，線性表在邏輯結(jié)構(gòu)上相鄰的數(shù)據(jù)元素存儲(chǔ)在相鄰的物理存儲(chǔ)單元中，即通過(guò)數(shù)據(jù)元素物理存儲(chǔ)的相鄰關(guān)系來(lái)反映數(shù)據(jù)元素間邏輯上的相鄰關(guān)系。

數(shù)組的長(zhǎng)度是存放線性表的存儲(chǔ)空間的長(zhǎng)度，分配存儲(chǔ)后這個(gè)量一般是不變的。線性表的長(zhǎng)度是線性表中數(shù)據(jù)元素的個(gè)數(shù)，隨著線性表中插入和刪除操作的進(jìn)行，這個(gè)量是變化的。切記，在任何時(shí)刻線性表的長(zhǎng)度應(yīng)該小于等于數(shù)組的長(zhǎng)度。

class SequenceList{ 
  
  constructor(){ 
    // 存儲(chǔ)元素的數(shù)組 
    this.elemList = []; 
    // 當(dāng)前順序表中的元素個(gè)數(shù) 
    this.elemLength = 0; 
  } 
  // 將一個(gè)線性表置為空表 
  clear(){ 
    this.elemLength = 0; 
  } 
  // 判斷當(dāng)前線性表是否為空表 
  isEmpty(){ 
    return this.elemLength === 0; 
  } 
  // 獲取當(dāng)前線性表的長(zhǎng)度 
  length(){ 
    return this.elemLength; 
  } 
  // 向線性表中添加元素 
  insert(elem){ 
    this.elemList[this.elemLength++] = elem; 
  } 
 
  // 在第i個(gè)元素插入元素elem 
  insertIndex(i,elem){ 
    // 先將i索引位置的元素及其后面位置的元素依次向后移動(dòng)一位 
    for(let index = this.elemLength - 1; index > i; index--){ 
      this.elemList[index] = this.elemList[index-1]; 
    } 
    // 把elem元素存放在i索引位置 
    this.elemList[i] = elem; 
  } 
 
  // 刪除指定位置i處的元素后，返回該元素 
  remove(i){ 
    // 記錄索引i處的值 
    let current = this.elemList[i]; 
    // 索引i后面元素依次向前移動(dòng)一位即可 
    for(let index = i; index < this.elemList - 1; index++){ 
      this.elemList[index] = this.elemList[index+1]; 
    } 
    // 元素個(gè)數(shù)-1 
    this.elemLength--; 
    return current; 
  } 
 
  // 查找elem元素首次出現(xiàn)在順序表的位置 
  indexOf(elem){ 
    for(let i = 0; i< this.elemLength; i++){ 
      if(this.elemList[i] === elem){ 
        return i; 
      } 
      return -1; 
    } 
  } 
} 

數(shù)組的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

• 在內(nèi)存空間的利用率高
• 查詢(xún)?cè)匦矢撸ㄟ^(guò)元素下標(biāo)進(jìn)行存取

缺點(diǎn)：

• 插入和刪除元素效率低。(在數(shù)組中間插入或刪除元素時(shí)，需要先移動(dòng)遍歷整個(gè)表才能操作元素并重新排序)
• 有空間長(zhǎng)度限制，不能擴(kuò)增線性表長(zhǎng)度。(當(dāng)存取元素長(zhǎng)度大于順序表的元素個(gè)數(shù)時(shí)，會(huì)出現(xiàn)“溢出”;當(dāng)元素長(zhǎng)度小于預(yù)先分配的空間時(shí)，空間浪費(fèi)嚴(yán)重)

小結(jié)

本篇文章是《懂點(diǎn)算法》系列的第二篇文章，主要講述的線性表的第一類(lèi)順序存儲(chǔ)，以及介紹了如何實(shí)現(xiàn)順序存儲(chǔ)。