第2章　線性表

 

2.1　復習筆記

一、線性表的類型定義

1線性表的定義

含有n個相同數據類型的數據元素的有限序列稱為線性表。

一般可表示為：

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

【說明】a_i－1是a_i的直接前驅元素，a_i＋1是a_i的直接后繼元素。線性表中數據元素的個數n（n＞0）為線性表的長度。當n＝0時稱線性表為空表。

線性表是最常用且最簡單的一種數據結構。

2線性表的基本操作

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

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

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

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

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

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

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

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

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

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

二、線性表的順序表示和實現

1順序存儲結構的表示

順序存儲結構（又稱順序表）是一種隨機存取的結構，邏輯關系上相鄰的元素物理位置上也相鄰。數組是表示順序存儲結構最簡單的一個方式。如圖2-1所示，只要確定了存儲線性表的起始位置，線性表中任一數據元素都可隨機存取。

圖2-1　線性表的順序存儲結構示意圖

2順序存儲結構的特點

優點：

①它是一個記錄型的結構。數據元素的存儲位置可用數組的下標值（即相對于線性表的起始位置的值）來表示；

②在順序存儲結構中，線性表的某些操作容易實現，如求表長的操作；

缺點：

①在做插入或刪除操作時，需移動大量元素；

②在給長度變化較大的線性表預先分配空間時，必須按最大空間分配，易造成了空間的浪費；

③表的容量難以擴充。

三、線性表的鏈式表示和實現

鏈式存儲結構，由于它不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒有順序存儲結構所具有的缺點。

1定義

借助指針等手段來表示數據元素a_i和直接后繼元素a_i＋1之間的關系，a_i不僅存儲本身的信息，還存儲指向后繼的指針。數據元素（數據域）和指向后繼的指針（指針域）合起來稱為一個結點，n個結點鏈接成一個鏈表即為線性表的鏈式存儲結構。

2鏈式存儲結構的特點

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

（2）數據元素之間的邏輯關系是由結點中的指針指示的；

3鏈式存儲結構的分類

鏈式存儲結構種類繁多，按照實現方式的不同，可分為借助指針實現的鏈式存儲結構和借助數組實現的鏈式存儲結構。

（1）借助指針實現的鏈式存儲結構

①單鏈表

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

圖2-2　單鏈表的邏輯狀態

②雙鏈表

雙鏈表的結點中除了數據域外，還有兩個指針域，一個指向直接后繼，另一個指向直接前驅。

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

圖2-3　雙向鏈表中刪除結點時指針變化情況

圖2-4　雙向鏈表中插入結點時指針變化情況

③循環鏈表

循環鏈表是一種首尾相連的鏈表，它的最后一個結點的指針域指向頭結點，形成一個環。循環鏈表包括單循環鏈表和雙循環鏈表。其中單循環鏈表如圖2-5所示。

雙鏈表也可以有循環鏈表，帶有圖2-6（a）這種結點結構的雙循環鏈表一般如圖2-6（c）所示，鏈表中存有兩個環。圖2-6（b）所示為只有一個表頭結點的空表。

圖2-5　單循環鏈表

圖2-6　雙向鏈表示例

（2）借助數組實現的鏈式存儲結構——靜態鏈表

預先分配一個較大的空間，使用數組下標將邏輯上相鄰的元素鏈接起來的特殊鏈表叫靜態鏈表。

其中插入刪除等操作具有和指針實現的鏈表一樣的優點。例如，圖2-7（b）展示了圖2-7（a）所示線性表在插入數據元素“SHI”和刪除數據元素“ZHENG”之后的狀況。

圖2-7　靜態鏈表示例

【注意】

①采用指針實現的鏈式存儲結構是非隨機存取的存儲結構；

②頭結點和頭指針的區別：

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

頭指針是為了標識一個鏈表而產生的，當鏈表存在頭結點時，則頭指針指向頭結點，當鏈表不存在頭結點時，頭指針指向鏈表的第一個元素（也可能為空）。

如圖2-8（a）所示，此時，單鏈表的頭指針指向頭結點。若線性表為空表，則頭結點的指針域為“空”，如圖2-8（b）所示。

圖2-8　帶頭結點的單鏈表

四、一元多項式的表示及相加