3.2 線(xiàn)性表的定義
線(xiàn)性表，從名字上你就能感覺(jué)到，是具有像線(xiàn)一樣的性質(zhì)的表。
零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列。
這里需要強(qiáng)調(diào)幾個(gè)關(guān)鍵的地方。
首先它是一個(gè)序列，也就是說(shuō)，元素之間是有順序的，若元素存在多個(gè)，則第一個(gè)元素?zé)o前驅(qū)，最后一個(gè)元素?zé)o后繼，其他每個(gè)元素都有且只有一個(gè)前驅(qū)和后繼。
線(xiàn)性表強(qiáng)調(diào)是有限的，元素個(gè)數(shù)當(dāng)然也是有限的。事實(shí)上，在計(jì)算機(jī)中處理的對(duì)象都是有限的，那種無(wú)限的數(shù)列，只存在于數(shù)學(xué)概念中。
線(xiàn)性表元素的個(gè)數(shù)
n(n>=0)定義為線(xiàn)性表的長(zhǎng)度，當(dāng)n=0時(shí)，稱(chēng)為空表。
在非空表中的每個(gè)數(shù)據(jù)元素都有一個(gè)確定的位置，如a1是第一個(gè)數(shù)據(jù)元素，an是最后一個(gè)數(shù)據(jù)元素，ai是第i個(gè)數(shù)據(jù)元素，稱(chēng)i為數(shù)據(jù)元素ai在線(xiàn)性表中的位序。
在較復(fù)雜的線(xiàn)性表中，一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。
3.4 線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)代碼
3.4.1 順序存儲(chǔ)定義
線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)，指的是用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線(xiàn)性表的數(shù)據(jù)元素。
3.4.2 順序存儲(chǔ)方式
線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)，就是在內(nèi)存中找了塊地，通過(guò)占位的形式，把一定內(nèi)存空間給占了，然后把相同數(shù)據(jù)類(lèi)型的數(shù)據(jù)元素依次存放在這塊空地中。既然線(xiàn)性表的每個(gè)數(shù)據(jù)元素的類(lèi)型都相同，所以可以用C語(yǔ)言的一維數(shù)組來(lái)實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)，即把第一個(gè)數(shù)據(jù)元素存到數(shù)組下標(biāo)為0的位置中，接著把線(xiàn)性表相鄰的元素存儲(chǔ)在數(shù)組中相鄰的位置。
為了建立一個(gè)線(xiàn)性表，要在內(nèi)存中找一塊地，于是這塊地的第一個(gè)位置就非常關(guān)鍵，他是存儲(chǔ)空間的起始位置。
這里，我們就發(fā)現(xiàn)描述順序存儲(chǔ)結(jié)構(gòu)需要三個(gè)屬性：
- 存儲(chǔ)空間的起始位置：數(shù)組
data，它的存儲(chǔ)位置就是存儲(chǔ)空間的存儲(chǔ)位置。- 線(xiàn)性表的最大存儲(chǔ)容量：數(shù)組長(zhǎng)度
MaxSize。- 線(xiàn)性表的當(dāng)前長(zhǎng)度：
length.
3.4.3 數(shù)據(jù)長(zhǎng)度與線(xiàn)性表長(zhǎng)度區(qū)別
數(shù)組長(zhǎng)度就是存放線(xiàn)性表的存儲(chǔ)空間的長(zhǎng)度，存儲(chǔ)分配后這個(gè)量是一般是不變的。
線(xiàn)性表的長(zhǎng)度是線(xiàn)性表中數(shù)據(jù)元素的個(gè)數(shù)，隨著線(xiàn)性表插入和刪除操作的進(jìn)行，這個(gè)量是變化的。
在任意時(shí)刻，線(xiàn)性表的長(zhǎng)度應(yīng)該小于等于數(shù)組的長(zhǎng)度。
3.4.4 地址計(jì)算方法
線(xiàn)性表的起始也是1，可C語(yǔ)言中的數(shù)組卻是從0開(kāi)始第一個(gè)下標(biāo)的，于是線(xiàn)性表的第i個(gè)元素是要存儲(chǔ)在數(shù)組下標(biāo)為i-1的位置，即數(shù)據(jù)元素的序號(hào)和存放它的數(shù)組元素下標(biāo)之間存在對(duì)應(yīng)關(guān)系
用數(shù)組存儲(chǔ)順序表意味著要分配固定長(zhǎng)度的數(shù)組空間，由于線(xiàn)性表中可以進(jìn)行插入和刪除操作，因此分配的數(shù)組空間要大于等于當(dāng)前線(xiàn)性表的長(zhǎng)度。
其實(shí)，內(nèi)存中的地址，就和圖書(shū)館或電影院里的座位一樣，都是有編號(hào)的。存儲(chǔ)器中的每個(gè)存儲(chǔ)單元都有自己的編號(hào)，這個(gè)編號(hào)稱(chēng)為地址。當(dāng)我們占位后，占座的第一個(gè)位置確定后，后面的位置都是可以計(jì)算的。
由于每個(gè)數(shù)據(jù)元素，不管它是整型，實(shí)型還是字符型，它都是需要占用一定的存儲(chǔ)單元空間的。假設(shè)占用的是c個(gè)存儲(chǔ)單元，那么線(xiàn)性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置滿(mǎn)足下列關(guān)系(LOC表示獲得存儲(chǔ)位置的函數(shù))。
LOC(ai+1) = LOC(ai) + c
所以對(duì)于第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置可以由a1推算得出：
LOC(ai) = LOC(ai) + (i - 1) * c
通過(guò)這個(gè)公式，你可以隨時(shí)算出線(xiàn)性表中任意位置的地址，不管它是第一個(gè)還是最后一個(gè)，都是相同的時(shí)間。那么我們對(duì)每個(gè)線(xiàn)性表位置的存入或則取出數(shù)據(jù)，對(duì)于計(jì)算機(jī)來(lái)說(shuō)都是相等的時(shí)間，也就是一個(gè)常數(shù)，因此用我們算法中學(xué)到的時(shí)間復(fù)雜度的概念來(lái)說(shuō)，它的存取時(shí)間性能為O(1)。我們通常把具有這一特點(diǎn)的存儲(chǔ)結(jié)構(gòu)稱(chēng)為隨機(jī)存儲(chǔ)結(jié)構(gòu)。
3.5 順序存儲(chǔ)結(jié)構(gòu)的插入語(yǔ)刪除
3.5.1 獲得元素操作
對(duì)于線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)來(lái)說(shuō)，如果我們要實(shí)現(xiàn)GetElem操作，即將線(xiàn)性表L中的第i個(gè)位置元素值返回，其實(shí)是非常簡(jiǎn)單的。就程序而言，只要i的數(shù)值在數(shù)組下標(biāo)范圍內(nèi)，就是把數(shù)組第i-1下標(biāo)的值返回即可。
3.5.2 插入操作
如果我們要實(shí)現(xiàn)ListInsert(*L,i,e),即在線(xiàn)性表L中的第i個(gè)位置插入新元素e。
插入算法的思路：
- 如果插入位置不合理，拋出異常。
- 如果線(xiàn)性表長(zhǎng)度大于等于數(shù)組長(zhǎng)度，則拋出異?；騽?dòng)態(tài)增加容量。
- 從最后一個(gè)元素開(kāi)始向前遍歷到第i個(gè)位置，分別將它們都向后移動(dòng)一個(gè)位置。
- 將要插入元素填入位置i處
- 表長(zhǎng)加1
3.5.2 刪除操作
如果我們要實(shí)現(xiàn)ListInsert(*L,i,e),即在線(xiàn)性表L中的第i個(gè)位置插入新元素e。
刪除算法的思路：
- 如果刪除位置不合理，拋出異常
- 取出刪除元素。
- 從刪除元素位置開(kāi)始遍歷到最后一個(gè)元素位置，分別將它們都向前移動(dòng)一個(gè)位置。
-
表長(zhǎng)減1
現(xiàn)在我們來(lái)分析一下，插入和刪除的時(shí)間復(fù)雜度。
先來(lái)看最好的情況，如果元素要插入到最后一個(gè)位置，或者刪除最后一個(gè)元素，此時(shí)，時(shí)間復(fù)雜度為O(1),因?yàn)椴恍枰苿?dòng)元素的。
最壞的情況，如果元素要插入到第一個(gè)位置或者刪除第一個(gè)元素，那就意味著要移動(dòng)所有的元素向后或者向前，所以這個(gè)時(shí)間復(fù)雜度為O(n)。
至于平均的情況，由于元素插入到第i個(gè)位置，或刪除第i個(gè)元素，需要移動(dòng)n-i個(gè)元素。根據(jù)概率原理，每個(gè)位置插入或刪除元素的可能性是相同的，也就說(shuō)位置靠前，移動(dòng)元素多，位置靠后，移動(dòng)元素少。最終平均移動(dòng)次數(shù)和最中間的那個(gè)元素的移動(dòng)次數(shù)相等，為(n-1)/2。
可以得出，平均時(shí)間復(fù)雜度還是O(n)。
線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)，在存，讀數(shù)據(jù)時(shí)，不管是哪個(gè)位置，時(shí)間復(fù)雜度都是O(1)；而插入和刪除時(shí)，時(shí)間復(fù)雜度都是O(n)。這就說(shuō)明，它比較適合元素個(gè)數(shù)不太變化，而更多是存儲(chǔ)數(shù)據(jù)的應(yīng)用。
3.5.4 線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)
- 優(yōu)點(diǎn)
- 無(wú)須為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間
- 可以快速的存取表中任一位置的元素
- 缺點(diǎn)
- 插入和刪除操作需要移動(dòng)大量元素
- 當(dāng)線(xiàn)性表長(zhǎng)度變化較大時(shí)，難以確定存儲(chǔ)空間的容量
*造成存儲(chǔ)空間的碎片
3.6 線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
3.6.1 順序存儲(chǔ)結(jié)構(gòu)不足的解決辦法
順序存儲(chǔ)結(jié)構(gòu)最大的缺點(diǎn)就是插入和刪除時(shí)需要移動(dòng)大量元素，這顯然就需要耗費(fèi)時(shí)間。
考慮一下導(dǎo)致這個(gè)問(wèn)題的原因：
就在于相鄰兩元素的存儲(chǔ)位置也具有鄰居關(guān)系。它們編號(hào)是1,2,3，.....，n,它們?cè)趦?nèi)存中的位置也是挨著的，中間沒(méi)有空隙，當(dāng)然就無(wú)法快速介入，而刪除后，當(dāng)中就會(huì)留出空隙，自然需要彌補(bǔ)。問(wèn)題就出在這里。
3.6.2 線(xiàn)性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義
線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線(xiàn)性表的數(shù)據(jù)元素，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。這就意味著，這些數(shù)據(jù)元素可以存在內(nèi)存未被占用的任意位置。
為了表示每個(gè)數(shù)據(jù)元素ai與其直接后繼數(shù)據(jù)元素ai + 1之間的邏輯關(guān)系，對(duì)數(shù)據(jù)元素ai來(lái)說(shuō)，除了存儲(chǔ)其本身的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息(即直接后繼的存儲(chǔ)位置)。我們把存儲(chǔ)數(shù)據(jù)元素信息的域稱(chēng)為數(shù)據(jù)域，把存儲(chǔ)直接后繼位置的域稱(chēng)為指針域。指針域中存儲(chǔ)的信息稱(chēng)作指針或鏈。這兩部分信息組成數(shù)據(jù)元素ai的存儲(chǔ)映像，稱(chēng)為結(jié)點(diǎn)(Node)。
n個(gè)結(jié)點(diǎn)(ai的存儲(chǔ)映像)鏈結(jié)成一個(gè)鏈表，即為線(xiàn)性表(a1,a2,a3,.....，an)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因?yàn)榇随湵淼拿總€(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，所以叫做單鏈表。單鏈表正是通過(guò)每個(gè)結(jié)點(diǎn)的指針域?qū)⒕€(xiàn)性表的數(shù)據(jù)元素按其邏輯次序鏈接在一起。
我們把鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置叫做頭指針。
線(xiàn)性鏈表的最后一個(gè)節(jié)點(diǎn)指針為“空”(通常用NULL來(lái)表示)。
有時(shí)，我們?yōu)榱烁臃奖愕貙?duì)鏈表進(jìn)行操作，會(huì)在單鏈表的第一個(gè)結(jié)點(diǎn)前附設(shè)一個(gè)節(jié)點(diǎn)，稱(chēng)為頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可以存儲(chǔ)如線(xiàn)性表的長(zhǎng)度等附加信息，頭結(jié)點(diǎn)的指針域存儲(chǔ)指向第一個(gè)結(jié)點(diǎn)的指針。
3.6.3 頭結(jié)點(diǎn)與頭指針的異同
- 頭指針
- 頭指針是指鏈表指向第一個(gè)結(jié)點(diǎn)的指針，若鏈表有頭結(jié)點(diǎn)，則是指向頭結(jié)點(diǎn)的指針
- 頭指針具有標(biāo)識(shí)作用，所以常用頭指針冠以鏈表的名字
- 無(wú)論鏈表是否為空，頭指針均不為空，頭指針是鏈表的必要元素。
- 頭結(jié)點(diǎn)
- 頭結(jié)點(diǎn)是為了操作的統(tǒng)一和方便而設(shè)立的，放在第一元素的結(jié)點(diǎn)之前，其數(shù)據(jù)域一般無(wú)意義。
- 有了頭結(jié)點(diǎn)，対在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第一節(jié)點(diǎn)，其操作與其他結(jié)點(diǎn)的操作就統(tǒng)一了。
- 頭結(jié)點(diǎn)不一定是鏈表必須要素。
3.6.4 線(xiàn)性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)代碼描述
若線(xiàn)性表為空表，則頭結(jié)點(diǎn)的指針域?yàn)?空"。
