2.1 線性表的基本概念

2.1.1 線性表的定義

線性表是由n（n≥0）個相同類型數據元素組成的有限序列。當n=0時為空表，記為（）或Φ；當n＞0時，線性表的邏輯表示為（al，a2，…，ai，…，an），也可以用如圖2.1所示的邏輯結構圖表示。

在線性表邏輯表示中，al稱為開始元素，an稱為終端元素（或尾元素）。元素ai在線性表中的邏輯序號或位置為i。對于任意一對相鄰元素<ai，ai+1> （1≤i≤n），ai稱為ai+1的前驅元素（或結點），ai+1稱為ai的后繼元素。

線性表的邏輯特征是：若至少含有一個元素，則只有唯一的開始元素和終端元素，除了開始元素外其他元素有且僅有一個前驅元素；除了終端結點外其他元素有且僅有一個后繼元素。

線性表中的每個元素有唯一的序號，同一個線性表中可以存在值相同的多個元素，但它們的序號是不同的。

例如，馬路上排列成一排的行駛的汽車就是一個汽車線性表，如圖2.2所示。

在不同的實際問題中，線性表中數據元素的類型可以不同，但要求同一個線性表中的所有數據元素具有相同的類型（比如數據項的個數相同，對應數據項的類型相同等）。

2.1.2 線性表的基本運算

通常線性表List的基本運算如下。

（1）初始化InitList（L）。其作用是建立一個空表L（即建立線性表的某種存儲結果，但不含任何數據元素）。

（2）銷毀線性表DestroyList（L）。其作用是釋放線性表L的內存空間。

（3）求線性表的長度GetLength（L）。其作用是返回線性表L的長度。

（4）求線性表中第i個元素GetElem（L，i，e）。其作用是返回線性表L的第i個數據元素。

（5）按值查找Locate（L，x）。若L中存在一個或多個值與x相等的元素，則其作用是返回第一個值為x的元素的邏輯序號。

（6）插入元素InsElem（L，x，i）。其作用是在線性表L的第i個位置上增加一個以x為值的新元素，使L由（a1，…，ai—1，ai，…，an）變為（a1，…，ai—1，x，ai，…，an）。其中，參數i的合法取值范圍是1≤i≤n+1。

（7）刪除元素DelElem（L，i）。其作用是刪除線性表L的第i個元素ai，使L由（a1，…，ai—1，ai，ai+1，…，an）變為（a1，…，ai—1，ai+1，…，an）。其中，參數i的合法取值范圍是1≤i≤n。

（8）輸出元素值DispList（L）。其作用是按前后次序輸出線性表L的所有元素值。

包含基本運算的線性表如圖2.3所示，其中，op1～ op8表示上述8個基本運算。

說明：線性表抽象數據類型由線性表中元素的邏輯結構和基本運算定義構成，為了突出后者，這里將兩者分小節討論，本書后面介紹各種數據結構時均采用這種表述方式。

使用以上基本運算可以實現線性表的更復雜的其他運算，如求任一給定數據元素的后繼或前驅元素，將兩個線性表合并成一個線性表或將一個線性表拆分成兩個線性表等。另一方面，在實際應用中，可以根據具體需要選擇適當的基本運算。

【例2.1】利用線性表List的基本運算，設計一個在線性表A中刪除線性表B中出現的元素的算法。

解：本題的算法思路是：依次檢查線性表B中的每個元素x，看它是否在線性表A中。若x在線性表A中，則將其從A中刪除。本題的算法如下。

【例2.2】利用線性表List的基本運算，設計一個由線性表A和B中的公共元素產生線性表C的算法。

解：本題的算法思路是：先初始化線性表C，然后依次檢查線性表A中的每個元素x，看它是否在線性表B中；若x在線性表B中，則將其插入到線性表C中。本題的算法如下。

從以上示例看到，一旦線性表及其基本運算算法實現好后，利用線性表求解實際問題就變得十分方便快捷。