線(xiàn)性表是一種最為常用的數(shù)據(jù)結(jié)構(gòu)，包括了一個(gè)數(shù)據(jù)的集合以及集合中各個(gè)數(shù)據(jù)之間的順序關(guān)系。線(xiàn)性表從數(shù)據(jù)結(jié)構(gòu)的分類(lèi)上來(lái)說(shuō)是一種順序結(jié)構(gòu)。在Python中的tuple，list等類(lèi)型都屬于線(xiàn)性表的一種。

　　從抽象數(shù)據(jù)類(lèi)型的線(xiàn)性表來(lái)看，一個(gè)線(xiàn)性表應(yīng)該具有以下這些操作（以偽代碼的形式寫(xiě)出）：

ADT List:List(self) #表的構(gòu)造操作，創(chuàng)建一個(gè)新表is_empty(self) #判斷一個(gè)表是不是空表len(self) #返回表的長(zhǎng)度prepend(self,elem) #在表的開(kāi)頭加入一個(gè)元素elem作為新表頭append(self,elem) #在表的末尾加上一個(gè)eleminsert(self,elem,i) #在指定位置i加上一個(gè)元素elemdel_first(self) #刪除表頭元素del_last(self) #刪除表尾元素del(self,i) #刪除位置i的元素search(self,elem) #查找元素elem在表中出現(xiàn)的位置，如果沒(méi)找到返回-1forall(self,option) #提供一個(gè)遍歷接口，對(duì)表中每一個(gè)元素實(shí)行操作option

　　另外還可以考慮一些如sort,reserve等等的操作。同時(shí)，以上所有操作都是對(duì)表本身做出變化，也可以設(shè)計(jì)一些非變化的操作，即改變并返回的是表的一個(gè)副本而原表只作為一個(gè)數(shù)據(jù)源，本身保持不變。

　　考慮到計(jì)算機(jī)內(nèi)存本身的特點(diǎn)和線(xiàn)性表的各種操作的效率，主要可以考慮線(xiàn)性表的兩種基本模型或者說(shuō)實(shí)現(xiàn)方式：

　　1. 順序表，將表元素連續(xù)地存放在一片計(jì)算機(jī)內(nèi)存中，元素之間的順序由它們的儲(chǔ)存順序自然表現(xiàn)出來(lái)。

　　2. 鏈接表，通過(guò)每個(gè)元素的儲(chǔ)存單元中額外指出下一個(gè)元素的方法來(lái)實(shí)現(xiàn)元素在邏輯上的連續(xù)排列。

　　下面將按照這兩種實(shí)現(xiàn)的方式分別說(shuō)明

順序表

■　　順序表的基本實(shí)現(xiàn)方式

　　順序表的大小通常在創(chuàng)建之時(shí)就確定下來(lái)（但是不一定一直都是這個(gè)大小不能改變，見(jiàn)后動(dòng)態(tài)順序表的實(shí)現(xiàn)方式）。

　　順序表的特點(diǎn)是計(jì)算表中任何元素位置的過(guò)程都非常簡(jiǎn)單，是O(1)操作。如果每個(gè)元素所需要的儲(chǔ)存單元大小都相同為c，那么知道一個(gè)元素的下標(biāo)之后想要計(jì)算它的物理地址訪(fǎng)問(wèn)它只需要L = L₀+c*i，這是一步簡(jiǎn)單的單元操作，花費(fèi)常量時(shí)間。如果表中每個(gè)元素所需要的儲(chǔ)存單元大小不一樣的話(huà)沒(méi)有辦法這么簡(jiǎn)單地算出物理地址，但是也不難處理。這牽扯到順序表的布局方式，一共有兩種布局：第一種“基本布局”是就如我們上面所說(shuō)的，每個(gè)儲(chǔ)存單元之間都互相相鄰挨在一起，此時(shí)每個(gè)儲(chǔ)存單元里都直接儲(chǔ)存著元素。第二種布局稱(chēng)為“元素外置布局”，有點(diǎn)像linux中文件系統(tǒng)的架構(gòu)，在順序表中儲(chǔ)存的都是儲(chǔ)存元素單元的物理地址，因?yàn)榈刂反笮《际且粯拥乃皂樞虮肀旧砜梢宰龅胶偷谝活?lèi)布局一樣通過(guò)簡(jiǎn)單計(jì)算得到某個(gè)下標(biāo)的元素，然后再進(jìn)行一步O(1)的“通過(guò)物理地址取內(nèi)容”的操作來(lái)獲取到元素。雖然中間隔了一層，但是記錄元素物理地址的 這個(gè)順序表在時(shí)間上和空間上的開(kāi)銷(xiāo)都不大，所以可以認(rèn)為這種實(shí)現(xiàn)形式也是實(shí)現(xiàn)了一般元素組成的順序表。

　　

　　順序表的基本實(shí)現(xiàn)形式確定了之后還要根據(jù)表需要的操作來(lái)進(jìn)行優(yōu)化和改造。比如，作為線(xiàn)性表的一個(gè)特點(diǎn)，順序表必須要支持加入/刪除元素的操作。因?yàn)轫樞虮淼拇笮∈谴_定的，這就帶來(lái)一個(gè)問(wèn)題，我該如何確定我加入新元素不會(huì)超出順序表規(guī)定的空間。為了有效地解決這個(gè)問(wèn)題和輔助其他很多的操作，在線(xiàn)性表里再加上兩個(gè)儲(chǔ)存單元分別用于存儲(chǔ)表的長(zhǎng)度和當(dāng)前表內(nèi)有多少元素非常有意義。所以，一個(gè)順序表在內(nèi)存中申請(qǐng)得到的一片區(qū)域進(jìn)一步被分成了三部分，分別是記錄表容量個(gè)數(shù)，記錄當(dāng)前元素個(gè)數(shù)以及數(shù)據(jù)儲(chǔ)存塊。

　　進(jìn)一步思考，內(nèi)存中這個(gè)表一旦創(chuàng)建出來(lái)，其大小就確定了，其前后的內(nèi)存空間也可能被其他數(shù)據(jù)占據(jù)導(dǎo)致我沒(méi)有辦法對(duì)當(dāng)前的順序表進(jìn)行擴(kuò)容或精簡(jiǎn)。這對(duì)于一開(kāi)始就聲明好表大小不再改變的數(shù)據(jù)結(jié)構(gòu)比如Python中tuple這樣的而言可能還好一點(diǎn)，因?yàn)樗臄?shù)據(jù)儲(chǔ)存部分不用改變，而對(duì)于list這樣的就很麻煩了。一種很容易想到的解決方案就是在創(chuàng)建之時(shí)把表創(chuàng)建的大一點(diǎn)，可能初始化的時(shí)候不把表填滿(mǎn)，留出一部分空間待以后有可能填進(jìn)來(lái)的元素填充，當(dāng)元素把這部分空間填滿(mǎn)了之后我就申請(qǐng)一塊更大的空間，把原來(lái)的數(shù)據(jù)復(fù)制過(guò)去然后繼續(xù)填充。這樣就可以讓更多元素加入進(jìn)表中。但是重新申請(qǐng)一塊空間創(chuàng)建一個(gè)新表會(huì)使得原來(lái)舊表的地址失效，很多引用了舊表的操作也就失效了。這給人感覺(jué)是治標(biāo)不治本的

　　為了解決上面這個(gè)問(wèn)題，另一種順序表的結(jié)構(gòu)被提出，即分離式結(jié)構(gòu)。相對(duì)的我們之前說(shuō)的，腦補(bǔ)的順序表都是一體式結(jié)構(gòu)。一體式結(jié)構(gòu)中表信息（表長(zhǎng)度和當(dāng)前元素個(gè)數(shù)）與元素儲(chǔ)存區(qū)緊鄰在一起，這樣雖然方便管理，但是當(dāng)我需要換個(gè)更大的空間時(shí)會(huì)有問(wèn)題。而分離式結(jié)構(gòu)的順序表將元素儲(chǔ)存區(qū)的地址存在表信息后面（和上面元素外置布局方式很有一個(gè)意思的感覺(jué)），使得元素儲(chǔ)存區(qū)成為一個(gè)可以替換的模塊。當(dāng)當(dāng)前元素儲(chǔ)存區(qū)存滿(mǎn)，我就可以新申請(qǐng)一片更大的區(qū)域，把當(dāng)前內(nèi)容復(fù)制過(guò)去，然后直接把順序表中指向原元素儲(chǔ)存區(qū)的指針指向新元素儲(chǔ)存區(qū)。這樣就可以做到在不改變表本身地址的情況下使順序表增容了。這實(shí)際上也是python中l(wèi)ist的實(shí)現(xiàn)方式。這種儲(chǔ)存區(qū)滿(mǎn)了就換新的而不影響順序表本身的表是動(dòng)態(tài)順序表。

?

　　動(dòng)態(tài)順序表也需要思考策略，比如說(shuō)每次擴(kuò)大儲(chǔ)存區(qū)的容量設(shè)置為多少比較合適。一種方案是每次擴(kuò)大都是多擴(kuò)大固定個(gè)元素，從復(fù)雜度的角度來(lái)看，每需要換一個(gè)儲(chǔ)存區(qū)復(fù)制原有數(shù)據(jù)需要花時(shí)間O(m)，m為當(dāng)時(shí)滿(mǎn)的儲(chǔ)存區(qū)中元素個(gè)數(shù)，計(jì)算可以得出對(duì)于最終長(zhǎng)度為n的一個(gè)線(xiàn)性表，復(fù)制的總次數(shù)大概要在kn**2這個(gè)量級(jí)，k是個(gè)常量參數(shù)由每次擴(kuò)大儲(chǔ)存區(qū)的大小決定。這看起來(lái)比較費(fèi)時(shí)間的原因是更換儲(chǔ)存區(qū)太過(guò)頻繁了。有人提出了另一種策略，每次需要擴(kuò)大儲(chǔ)存區(qū)時(shí)擴(kuò)大數(shù)量為上一次擴(kuò)大的兩倍，這樣可以計(jì)算證明其從0個(gè)元素增加至n個(gè)元素所花的時(shí)間是O(1)的。后一個(gè)策略在操作復(fù)雜度上帶來(lái)優(yōu)化，但是同時(shí)它的空閑單元數(shù)最多的時(shí)候會(huì)占全部的一半，帶來(lái)了空間上的浪費(fèi)。這是一個(gè)以空間換時(shí)間的案例。

■　　順序表的基本操作

　　●? 創(chuàng)建空表

　　向內(nèi)存申請(qǐng)一塊空間，在開(kāi)頭記錄下表的容量max并將元素個(gè)數(shù)的計(jì)數(shù)num設(shè)置為0。

　　●　簡(jiǎn)單判斷操作

　　當(dāng)num=max是判斷表滿(mǎn)，當(dāng)num=0時(shí)判斷表空

　　●? 訪(fǎng)問(wèn)給定下標(biāo)的元素

　　訪(fǎng)問(wèn)下標(biāo)為i的元素時(shí)，先檢查i是否在[0,num)中，如果不是的話(huà)表明訪(fǎng)問(wèn)越界。如果i合法的話(huà)，就計(jì)算出相關(guān)元素的地址（這個(gè)過(guò)程可能根據(jù)布局方式和結(jié)構(gòu)的不同而不同）。這個(gè)操作顯然跟表一共有多少個(gè)元素沒(méi)多大關(guān)系，所以是個(gè)O(1)的操作。

　　●? 遍歷操作

　　按順序訪(fǎng)問(wèn)表中元素，另外維護(hù)一個(gè)當(dāng)前訪(fǎng)問(wèn)元素的下標(biāo)值，每訪(fǎng)問(wèn)一次該值+1。因?yàn)槊恳淮卧L(fǎng)問(wèn)都是通過(guò)計(jì)算地址得到目標(biāo)元素的，所以每一次訪(fǎng)問(wèn)都是O(1)的，一共n次訪(fǎng)問(wèn)所以最終，遍歷操作是O(n)的。

　　●? 查找給定元素的位置

　　在沒(méi)有其他信息的情況下，檢索一個(gè)元素只能通過(guò)遍歷表來(lái)檢索。這稱(chēng)為線(xiàn)性檢索。遍歷每一個(gè)元素，判斷元素的值是否和給出的值相同，否則繼續(xù)遍歷。

　　●? 加入新元素

　　加入元素分成好幾種情況。每成功加入一個(gè)新元素之后，表頭維護(hù)的num信息應(yīng)該+1

　　1，在尾部加入新元素，先判斷當(dāng)前num是否等于max，如果是的話(huà)那就表明我們需要更換數(shù)據(jù)儲(chǔ)存區(qū)了。否則就在尾部加上相關(guān)元素。這個(gè)操作顯然是O(1)的，跟表當(dāng)前有多少元素在沒(méi)有關(guān)系。

　　2，把新數(shù)據(jù)存進(jìn)儲(chǔ)存區(qū)的第i個(gè)單元，此時(shí)在判斷完表是否滿(mǎn)了之后還要考慮，把新數(shù)據(jù)寫(xiě)入相關(guān)位置之后，原本在那個(gè)位置如果有老數(shù)據(jù)該怎么辦。如果不要求插入后的表保持原來(lái)的順序（不保序）的話(huà)，那么可以直接把原先那個(gè)位置的元素給放到整個(gè)表的最后面，這樣操作仍然是O(1)。如果要求保序，那么在插入相關(guān)位置之后，從 此位置的原元素開(kāi)始，之后每個(gè)元素都要向后移動(dòng)一位，這么一來(lái)使得操作和原表中一共有多少元素就掛鉤了。事實(shí)上，不論是平均還是最壞情況，保序的插入操作是O(n)的。

　　●? 刪除元素

　　刪除其實(shí)和插入是類(lèi)似的，分成尾端刪除和定位刪除兩種情況。和插入也類(lèi)似的，尾端刪除是一個(gè)O(1)操作，而定位刪除因?yàn)橐紤]保序和不保序兩種情況，也分成了O(1)和O(n)兩種情形。

　　除此之外，刪除還有一種比較特殊的情況，條件刪除。即看準(zhǔn)某個(gè)符合條件的元素進(jìn)行刪除。一般來(lái)說(shuō)進(jìn)行條件刪除也是先要遍歷表的，在遍歷中加上一個(gè)條件判斷，總體而言條件刪除仍然是一個(gè)O(n)的操作。

　　總的來(lái)說(shuō)，用順序表操作有優(yōu)點(diǎn)也有缺點(diǎn)。一般而言其優(yōu)點(diǎn)在于它直接按位置訪(fǎng)問(wèn)元素，元素在表中儲(chǔ)存得十分緊湊，除了一些占O(1)的輔助信息以外其他的都是有效的元素信息。但是順序表的缺點(diǎn)也很明顯，為了能夠放下足夠多的元素，通常需要進(jìn)行儲(chǔ)存區(qū)更換，而在更換之后又會(huì)有大量的空閑單元的出現(xiàn)。

?

■　　Python中的List類(lèi)型

　　前面已經(jīng)說(shuō)過(guò)了，python中的tuple和list都是順序表的實(shí)現(xiàn)。此外list還是個(gè)采用了分離式結(jié)構(gòu)的動(dòng)態(tài)順序表，保證了在不斷加入元素的過(guò)程中，表對(duì)象的標(biāo)識(shí)（id）不會(huì)改變。在python的官方實(shí)現(xiàn)中，為了讓list能夠更有效率地更換儲(chǔ)存區(qū)，采用了下面這樣的儲(chǔ)存區(qū)更換策略：建立空表或者很小的表的時(shí)候，系統(tǒng)默認(rèn)給出一塊可以容納8個(gè)元素的儲(chǔ)存區(qū)，在元素增加的過(guò)程中，如果區(qū)滿(mǎn)了就換一塊4倍大的儲(chǔ)存區(qū)，以此類(lèi)推直到表的大小達(dá)到5萬(wàn)個(gè)元素左右的時(shí)候，當(dāng)區(qū)再滿(mǎn)的時(shí)候就換一塊兩倍大的儲(chǔ)存區(qū)。之所以要在5萬(wàn)這個(gè)節(jié)點(diǎn)上做出這種變化是為了避免出現(xiàn)過(guò)多的空閑儲(chǔ)存單元。

　　對(duì)于list的一些主要的操作而言，有下面這幾點(diǎn)可以提一下：

　　len函數(shù)的操作是一個(gè)O(1)的操作。因?yàn)樗皇侨×吮眍^信息中的num這個(gè)參數(shù)做了一些加工而已。

　　元素訪(fǎng)問(wèn)和賦值，尾端加入以及尾端刪除（包括尾端切片刪除）都是O(1)操作

　　指定位置的元素加入，切片替換，切片刪除，表拼接（extend）都是O(n)操作

　　reverse()操作是O(n)，而sort()操作，python封裝的是最好的排序算法，其平均和最壞的時(shí)間復(fù)雜度都是O(nlogn)。

　　另外，值得指出的一點(diǎn)是，python沒(méi)有提供接口讓程序員可以管理list中每個(gè)儲(chǔ)存單元的大小，雖然這樣設(shè)計(jì)的初衷是為了減輕編程負(fù)擔(dān)，避免人為的操作引起的錯(cuò)誤，但這也無(wú)疑在一定程度上限制了使用表的自由。

?

由于篇幅過(guò)長(zhǎng)，鏈接表的內(nèi)容放在了另一篇筆記中。

轉(zhuǎn)載于:https://www.cnblogs.com/franknihao/p/6894697.html

總結(jié)

以上是生活随笔為你收集整理的【数据结构】 线性表的顺序表的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。