第2章　線性表

 

2.1　復(fù)習(xí)筆記

一、線性表的類型定義

1線性表的定義

含有n個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素的有限序列稱為線性表。

一般可表示為：

L＝（a₁，a₂，…，a_i－1，a_i，a_i＋1，…，a_n－1，a_n）；

【說明】a_i－1是a_i的直接前驅(qū)元素，a_i＋1是a_i的直接后繼元素。線性表中數(shù)據(jù)元素的個(gè)數(shù)n（n＞0）為線性表的長度。當(dāng)n＝0時(shí)稱線性表為空表。

線性表是最常用且最簡單的一種數(shù)據(jù)結(jié)構(gòu)。

2線性表的基本操作

（1）INITIATE(L)：初始化操作。

（2）LENGTH(L)：求線性表長度。

（3）GET(L,i)：取元素函數(shù)。

（4）PRIOR(L,elm)：求前驅(qū)函數(shù)。

（5）NEXT(L,elm)：求后繼函數(shù)。

（6）LOCATE(L,X)：定位函數(shù)。

（7）INSERT(L,i,b)：前插操作。

（8）DELETE(L,i)：刪除操作。

（9）EMPTY(L)：判空表函數(shù)。

（10）CLEAR(L)：表置空操作。

二、線性表的順序表示和實(shí)現(xiàn)

1順序存儲(chǔ)結(jié)構(gòu)的表示

順序存儲(chǔ)結(jié)構(gòu)（又稱順序表）是一種隨機(jī)存取的結(jié)構(gòu)，邏輯關(guān)系上相鄰的元素物理位置上也相鄰。數(shù)組是表示順序存儲(chǔ)結(jié)構(gòu)最簡單的一個(gè)方式。如圖2-1所示，只要確定了存儲(chǔ)線性表的起始位置，線性表中任一數(shù)據(jù)元素都可隨機(jī)存取。

圖2-1　線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖

2順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)

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

①它是一個(gè)記錄型的結(jié)構(gòu)。數(shù)據(jù)元素的存儲(chǔ)位置可用數(shù)組的下標(biāo)值（即相對于線性表的起始位置的值）來表示；

②在順序存儲(chǔ)結(jié)構(gòu)中，線性表的某些操作容易實(shí)現(xiàn)，如求表長的操作；

缺點(diǎn)：

①在做插入或刪除操作時(shí)，需移動(dòng)大量元素；

②在給長度變化較大的線性表預(yù)先分配空間時(shí)，必須按最大空間分配，易造成了空間的浪費(fèi)；

③表的容量難以擴(kuò)充。

三、線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，由于它不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒有順序存儲(chǔ)結(jié)構(gòu)所具有的缺點(diǎn)。

1定義

借助指針等手段來表示數(shù)據(jù)元素a_i和直接后繼元素a_i＋1之間的關(guān)系，a_i不僅存儲(chǔ)本身的信息，還存儲(chǔ)指向后繼的指針。數(shù)據(jù)元素（數(shù)據(jù)域）和指向后繼的指針（指針域）合起來稱為一個(gè)結(jié)點(diǎn)，n個(gè)結(jié)點(diǎn)鏈接成一個(gè)鏈表即為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

2鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)

（1）不要求邏輯上相鄰的元素在物理位置上也相鄰；

（2）數(shù)據(jù)元素之間的邏輯關(guān)系是由結(jié)點(diǎn)中的指針指示的；

3鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的分類

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)種類繁多，按照實(shí)現(xiàn)方式的不同，可分為借助指針實(shí)現(xiàn)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和借助數(shù)組實(shí)現(xiàn)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

（1）借助指針實(shí)現(xiàn)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

①單鏈表

在單鏈表中，對于每個(gè)結(jié)點(diǎn)來說，除了存儲(chǔ)本身的信息外，還需要存放一個(gè)指向其后繼的指針。邏輯位置相鄰但物理位置不相鄰的數(shù)據(jù)元素用單鏈表鏈接如圖2-2所示。

圖2-2　單鏈表的邏輯狀態(tài)

②雙鏈表

雙鏈表的結(jié)點(diǎn)中除了數(shù)據(jù)域外，還有兩個(gè)指針域，一個(gè)指向直接后繼，另一個(gè)指向直接前驅(qū)。

在雙向鏈表中，有些操作如：LENGTH(L)、GET(L,i)、LOCATE(L,x)等僅需涉及一個(gè)方向的指針，但插入、刪除時(shí)，需同時(shí)修改兩個(gè)方向上的指針，圖2-3和圖2-4分別顯示了刪除和插入結(jié)點(diǎn)時(shí)指針修改的情況。

圖2-3　雙向鏈表中刪除結(jié)點(diǎn)時(shí)指針變化情況

圖2-4　雙向鏈表中插入結(jié)點(diǎn)時(shí)指針變化情況

③循環(huán)鏈表

循環(huán)鏈表是一種首尾相連的鏈表，它的最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，形成一個(gè)環(huán)。循環(huán)鏈表包括單循環(huán)鏈表和雙循環(huán)鏈表。其中單循環(huán)鏈表如圖2-5所示。

雙鏈表也可以有循環(huán)鏈表，帶有圖2-6（a）這種結(jié)點(diǎn)結(jié)構(gòu)的雙循環(huán)鏈表一般如圖2-6（c）所示，鏈表中存有兩個(gè)環(huán)。圖2-6（b）所示為只有一個(gè)表頭結(jié)點(diǎn)的空表。

圖2-5　單循環(huán)鏈表

圖2-6　雙向鏈表示例

（2）借助數(shù)組實(shí)現(xiàn)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——靜態(tài)鏈表

預(yù)先分配一個(gè)較大的空間，使用數(shù)組下標(biāo)將邏輯上相鄰的元素鏈接起來的特殊鏈表叫靜態(tài)鏈表。

其中插入刪除等操作具有和指針實(shí)現(xiàn)的鏈表一樣的優(yōu)點(diǎn)。例如，圖2-7（b）展示了圖2-7（a）所示線性表在插入數(shù)據(jù)元素“SHI”和刪除數(shù)據(jù)元素“ZHENG”之后的狀況。

圖2-7　靜態(tài)鏈表示例

【注意】

①采用指針實(shí)現(xiàn)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是非隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)；

②頭結(jié)點(diǎn)和頭指針的區(qū)別：

頭結(jié)點(diǎn)是在鏈表的第一個(gè)結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)（該結(jié)點(diǎn)可以不存儲(chǔ)任何信息，也可以存儲(chǔ)鏈表長度等信息），從而使得鏈表的第一個(gè)結(jié)點(diǎn)和其他結(jié)點(diǎn)在處理問題上的操作保持一致。

頭指針是為了標(biāo)識(shí)一個(gè)鏈表而產(chǎn)生的，當(dāng)鏈表存在頭結(jié)點(diǎn)時(shí)，則頭指針指向頭結(jié)點(diǎn)，當(dāng)鏈表不存在頭結(jié)點(diǎn)時(shí)，頭指針指向鏈表的第一個(gè)元素（也可能為空）。

如圖2-8（a）所示，此時(shí)，單鏈表的頭指針指向頭結(jié)點(diǎn)。若線性表為空表，則頭結(jié)點(diǎn)的指針域?yàn)椤翱铡保鐖D2-8（b）所示。

圖2-8　帶頭結(jié)點(diǎn)的單鏈表

四、一元多項(xiàng)式的表示及相加