目錄

一、 概述
二、順序表
2.1、 插入元素
2.2、 刪除元素
2.3、 特點
三、鏈表
3.1、線性鏈表(單鏈表)
3.1.1、插入元素
3.1.2、刪除元素
3.2、循環(huán)鏈表(單向)
3.3、雙向鏈表
3.4、雙向循環(huán)鏈表
3.5、鏈表的特點
四、棧
4.1、順序棧
4.2、鏈棧
五、隊列
5.1、順序隊列
5.2、鏈隊列

一、概述

線性表 是具有線性結構特點、最簡單且最常用的一種數(shù)據(jù)結構。
線性表 ( Linear List) 是具有相同特性的數(shù)據(jù)元素組成的一個有限序列。其元素可以是整數(shù)、字符等簡單數(shù)據(jù)，也可以是由多個數(shù)據(jù)項組成的復合形式，甚至可以是一頁書或其他更復雜的信息。
例如，由26個大寫英文字母組成的字母表(A，B，C，…，x，Y，Z)就是一個線性表，表中的每個數(shù)據(jù)元素均是一個大寫字母。再如，某高校1990年以來擁有的副教授以上職稱的教師個數(shù)(48,64,77,93,112,136,167，…,235)也是一個線性表，表中的每個數(shù)據(jù)元素均是一個正整數(shù)。這兩個線性表都是包含簡單數(shù)據(jù)元素的例子。
線性表 中的數(shù)據(jù)元素可以是多種形式的，但是，對于同一個線性表，其數(shù)據(jù)元素必須具有同一種形式，也就是說，同一線性表中的數(shù)據(jù)元素必須同屬一個數(shù)據(jù)對象集合，表中相鄰的數(shù)據(jù)元素之間存在某種序偶關系。

線性結構 特點： 在數(shù)據(jù)元素的非空有限集合中，存在唯一的一個稱為“第一個”的數(shù)據(jù)元素(頭結點)；存在唯一的一個“最后一個”的數(shù)據(jù)元素(末結點)除第一個外，集合中的每個數(shù)據(jù)元素都只有一個直接前驅；除最后一個外，集合中的每個數(shù)據(jù)元素都只有一個直接后繼。

二、順序表

順序表 是指用一組地址連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素的線性表 。
因為這種方式與高級程序設計語言中一維數(shù)組的表示和實現(xiàn)相一致，所以也稱為數(shù)組表示法。采用順序表表示的線性表，表中邏輯位置相鄰的數(shù)據(jù)元素將存放到存儲器中物理地址相鄰的存儲單元之中，表中元素的邏輯關系與存儲順序(物理關系)相符，換言之，順序表中數(shù)據(jù)元素的邏輯關系是以其在存儲結構中的物理(位置)關系來表示的。
因此，在順序表中，可以根據(jù)順序表中數(shù)據(jù)元素的位序，隨機訪問表中的任一元素，即順序表是一種隨機存取的存儲結構。

image

• 2.1、 順序表的插入

順序表的插入是指在順序表的第i-1個元素和第i個元素之間插入一個新的元素，此時順序表中插入位置前后元素之間的邏輯關系發(fā)生變化，因此除非插入位置是當前表中的最后一個元素之后，否則必須通過順序移動數(shù)據(jù)元素的存儲位置才能實現(xiàn)。插入過程示意圖如圖所示：

image

順序表的插入算法時間耗費主要是元素的移動，移動元素的個數(shù)取決于插入位置。 最好情況，插入位置在順序表表尾，無須移動元素；最壞情況是在第一個位置插入，需要移動n個元素。在長度為n的順序表i位置前插入一個元素，需要移動n-i+1個元素，可以以有n+1個插入位置，在插入位置等概率條件下，插入一個元素的平均移動次數(shù)為1/(n+1)*∑(n-i+1)=n/2，因此算法的時間復雜度為O(n)。
注意：∑(n-i+1)表示下標是i=1，上標是n+1的求和表達式。

• 2.2、順序表的刪除

順序表的刪除和插入的過程類似，需要移動刪除元素后面的所有元素存儲位置。過程如圖所示：

image

同插入算法一樣，刪除算法時間主要消耗在元素的移動。最好情況，刪除位置在順序表末尾，無須移動元素；最壞情況，刪除位置是第一個元素，需要移動n-1個元素。在長度為n的順序表的i位置刪除元素，需要移動n-i個元素，在刪除位置等概率條件下，刪除一個元素的平均移動次數(shù)為1/n*∑(n-i)=(n-1)/2，因此算法的時間復雜度為O(n)。
注意：∑(n-i)表示下標是i=1，上標是n+1的求和表達式。

• 2.3、順序表的特點

順序表的特點 是以“存儲位置相鄰”表示兩個元素之間的前驅后繼關系。順序表的優(yōu)點是可以隨機存取表中任意一個元素。其主要缺點一是容易產(chǎn)生存儲空間的浪費；二是每做一次插入或刪除操作時，平均來說必須移動表中一半元素。因此，順序表經(jīng)常主要應用于為查詢而很少做插入和刪除操作、表長變化不大的線性表。

三、鏈表

所謂 鏈表 ，就是指采用鏈式存儲結構表示和實現(xiàn)的線性表。
鏈表的特點是采用一組任意的存儲單元來存放線性表中的數(shù)據(jù)元素，這些存儲單元可以是連續(xù)的，也可以是不連續(xù)的。 在鏈表中，數(shù)據(jù)元素之間的邏輯關系并不依賴其對應的存儲地址，而是通過設置專門用于指示數(shù)據(jù)元素之間邏輯關系的指針來描述。
因此，在鏈表中的每個數(shù)據(jù)元素是由用于存放代表其本身信息的數(shù)據(jù)域和用于存放指示數(shù)據(jù)元素之間邏輯關系的指針域兩部分組成的，數(shù)據(jù)元素的這種特殊存儲方式，稱為 結點(Node) 。
根據(jù)鏈表結點中包含指針域的指針個數(shù)、指針指向和連接方式，可將鏈表分為線性鏈表、循環(huán)鏈表、雙向鏈表、多重鏈表、十字鏈表、二叉鏈表、鄰接表、鄰接多重表等，其中線性鏈表、循環(huán)鏈表和雙向鏈表用于實現(xiàn)線性表的鏈式存儲結構，其他形式則用于實現(xiàn)擴展線性結構(數(shù)組和廣義表等)或非線性結構(樹、圖等)。

image

• 3.1、線性鏈表(單鏈表)

線性鏈表也稱 單鏈表 ，在每個結點中只包含一個指針，用于指示該結點的直接后繼結點，整個鏈表通過指針相連，最后一個節(jié)點因為沒有后集結點，其指針置為空NUll。結構示意圖如上圖所示。

3.1.1、單鏈表的插入

線性鏈表的插入是指在線性鏈表的第-1個結點和第i個結點之間插入一個新的結點，此時，線性鏈表中插入位置前后結點之間的邏輯關系發(fā)生變化，因此除非插入位置是當前表中的最后一個結點之后，否則必須通過同時修改插入位置之前結點和當前插入結點的指針指向才能實現(xiàn)。
線性鏈表的插入無須移動元素，插入算法的基本步驟如下圖所示：
(1)尋找插入位置，即第i-1個結點的位置。
(2)申請結點存儲空間，生成新結點。
(3)修改第-1個結點和新結點指針域，將新結點鏈接在鏈表中。

image

線性鏈表的插入算法時間主要消耗在尋找插入位置上，需要從鏈表頭指針開始依次訪問結點，直到找到插入位置，因此算法的時間復雜度為O(n)。

3.1.2、單鏈表的刪除

線性鏈表的刪除是指刪除線性鏈表的第i個結點，此時，線性鏈表中刪除位置前后結點之間的邏輯關系發(fā)生變化，因此必須通過修改刪除位置之前結點的指針指向才能實現(xiàn)。刪除過程示意圖，如上。
同插入結點一樣，刪除過程首先尋找要刪除結點的前一個結點位置，再通過修改結點指針域完成刪除操作。 因此算法的時間復雜度為也O(n)。

• 3.2、循環(huán)鏈表(單向)

在線性鏈表中，最后一個結點的指針指向NULL，表示該線性鏈表的結束。如果把表尾結點的指針改為指向該鏈表的第一個結點，則整個線性鏈表構成一個閉合的回路，稱這種頭尾相連的線性鏈表形式為 循環(huán)鏈表 。
整個鏈表就像一條單向環(huán)形的公交線路，人們可以從線路中的任一站點出發(fā)到達整個線路的其他站點。插入和刪除的時間復雜度也為O(n)，循環(huán)鏈表存儲結構示意圖如下：

image

• 3.3、雙向鏈表

如果在線性鏈表的結點中增加一個指針域，用來指向結點的直接前驅，則從表中的任一結點出發(fā)，既可以向后查找結點的后繼，也可以向前查找結點的前驅。整個鏈表包含分別指向前驅和后繼的兩條鏈，稱為 雙向鏈表 。雙向鏈表的存儲結構示意如圖：

image

• 3.4、雙向循環(huán)鏈表

使雙向鏈表中的兩條鏈均構成閉合回路，則形成 雙向循環(huán)鏈表 。雙向循環(huán)鏈表結構示意圖以及插入和刪除過程示意圖如下：

image

image

• 3.5、鏈表的特點

鏈表的特點 是以“指針”指示其后繼元素，鏈表中的元素可以存儲在任意一組存儲單元中。因此，鏈表的優(yōu)點是無須預先估計線性表的大小，節(jié)省存儲開銷，且做插入、刪除操作時，無須移動元素；其主要缺點是無論鏈表做插入、刪除還是查找，均需要從鏈表的起始位置開始，鏈表不具備隨機存取的特性。

四、棧

棧 是一種操作受限的線性表，上面提到的順序表和鏈表可以在表的兩端和表內進行插入刪除操作，而 棧僅允許在一端(棧頂)進行插入刪除操作 ，也就是進(入)棧和出棧操作，棧頂是棧讀取數(shù)據(jù)的唯一入口，操作遵循“ 先進后出(LIFO) ”的原則。例如Object-C中的導航控制器就是用棧的特性實現(xiàn)的。

image

根據(jù)存儲結構的不同，也可以把棧分為 順序棧 和 鏈棧 兩種存儲結構。

• 4.1、順序棧

棧的順序存儲也稱為順序棧，它利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)脑?，同時附設棧頂標識top來指示棧頂元素在順序棧中的位置。順序棧的入棧和出棧操作結構示意圖如圖所示：

image

• 4.2、鏈棧

棧的鏈式存儲也稱為鏈棧，它和鏈表的存儲原理一樣，都可以利用閑散空間來存儲元素，用指針來建立各結點之間的邏輯關系。鏈棧也會設置一個棧頂元素的標識符top，稱為棧頂指針。鏈棧的入棧和出棧操作結構示意圖如圖所示

image

image

五、隊列

隊列 是也一種操作受限的線性表，但隊列和棧不同， 隊列只允許在一端(隊尾)進行插入(入隊)操作 ，在另一端(隊頭)進行刪除(出隊)操作，操作遵循的是“ 先進先出(FIFO) ”原則。
隊列中會有一個指針指向隊頭，這個指針稱為 隊頭指針front 。當有元素出隊時，隊頭指針向后移動,指向下一個元素，下一個元素成為新的隊頭元素(類似于棧的棧頂指針)；隊列中也會有一個指針指向隊尾，稱為 隊尾指針rear ，隊尾指針是指向最后一個元素之后的一個空指針。當有元素需要入隊時，就插入到隊尾指針所指位置處，插入之后，隊尾指針向后移動，指向下一個空位。當隊列已滿時，元素不能再入隊；同理，當隊列為空，無法執(zhí)行出隊操作。

image

根據(jù)存儲結構的不同，也可以把隊列分為 順序隊列 和 鏈式隊列 兩種存儲結構。

• 5.1、順序隊列

使用順序表實現(xiàn)的隊列稱作 順序隊列 。順序隊列的實現(xiàn)和順序表的實現(xiàn)相似，只是在順序隊列中只允許在一端進行插入，在另一端進行刪除。定義兩個變量 front與rear分別標識隊頭與隊尾，當刪除隊頭元素時， front后移到下一個位置；當插入新元素時，在rear指示的位置插入，插入后，rear向后移動指向下一個存儲位置。順序隊列的出入隊操作示意圖如下：

image

• 注意 ：隊列的“假溢出”

在順序隊列的存儲過程中，可能出現(xiàn)“溢出”現(xiàn)象，隊列的“溢出”有兩種情況，一種真“溢出”，另一種為假“溢出“。
所謂 真“溢出” 是指當隊列分配的空間已滿，此時再往里存儲元素則會出現(xiàn)“溢出”，這種“溢出”是真的再無空間來存儲元素，是真“溢出”；而 假“溢出” 是指隊列尚有空間而出現(xiàn)的“溢出”情況。當 front端有元素出隊時， front向后移動；當rear端有元素入隊時，rear向后移動，若rear已指到隊列中下標最大的位置，此時雖然 front前面有空間，但再有元素入隊也會出現(xiàn)“溢出”，這種“溢出”叫作“假溢出”，示意圖如下。
解決“假溢出”有兩種方法。一是采用“移動隊列”的方法，即每當執(zhí)行一次出隊操作，則依次將隊頭和隊尾指針向數(shù)組的起始位置移動，始終保持隊頭在數(shù)組的起始位置，這種方法的代價是產(chǎn)生大量的元素移動，顯然不是一個好方法；另一種方法就更合理高效了，就是采用5.2循環(huán)隊列。

image

• 5.2、循環(huán)隊列

為了解決順序隊列中的假“溢出”現(xiàn)象，充分利用數(shù)組的存儲空間，可以將順序隊列的頭尾相連，構成一個 循環(huán)隊列，循環(huán)隊列一般都是用數(shù)組來實現(xiàn)的。將循環(huán)隊列假想為一個環(huán)狀的空間，如下圖所示。
在循環(huán)隊列中， front與rear都是可以循環(huán)移動的，當隊空時， front=rear成立；當隊滿時， front=rear也成立。因此顯然不能只憑 front=rear來判斷隊空還是隊滿。
為了解決這個問題，在循環(huán)隊列中有一個約定：少用一個元素空間，當隊尾標識的rear在隊頭標識front的上一個位置時，隊列為滿。此時，判斷隊空和隊滿的條件分別如下：
隊空時： front==rear為真。
隊滿時：(rear+1)% MAXSIZE== front為真 ( MAXSIZE是隊列容量的大?。?br> 循環(huán)隊列中ront和rear的移動不再是簡單的加1，因為是循環(huán)的，可能原本指在末尾，前進一個單位就是又一個循環(huán)的開始，所以每次移動都要對隊列容量 MAXSIZE取模：front = (front +1)% MAXSIZE，rear = (rear+1)% MAXSIZE。
在循環(huán)隊列中，求隊列的長度也不僅僅是rear與ront相減這么簡單，因為，rear的值有可能比front小，這樣的相減結果是負值，顯然不對。在求循環(huán)隊列的長度時，都是用rear加上隊列容量，減去 front的值后，再對容量取模：(rear+ MAXSIZE- front)% MAXSIZE。

image

• 5.3、鏈式隊列

用鏈表來實現(xiàn)的隊列也稱為 鏈式隊列 ，在鏈式隊列中也用指針 front與rear分別指示隊頭與隊尾，在隊頭 front處刪除元素，在隊尾rear處插入元素。與順序隊列不同，鏈式隊列的rear指針指向最后一個元素。鏈式隊列的結構和出入隊操作示意圖如下：

image

image

注：文中的圖片均轉摘自網(wǎng)絡