2.1 線性表的邏輯結構

2.1.1 線性表的定義

線性表（Linear List）是一種線性結構。在一個線性表中數據元素的類型是相同的，或者說線性表是由同一類型的數據元素構成的線性結構。在實際問題中線性表的例子很多，如學生情況信息表（表中數據元素的類型為學生信息記錄類型）、字符串（表中數據元素的類型為字符型）等。

綜上所述，線性表定義如下。

線性表是具有相同數據類型的n(n≥0)個數據元素的有限序列，通常記為：

（a1, a2, …, ai-1, ai, ai+1, …, an）

其中n為表長，當n=0時稱該線性表為空表。

表中相鄰元素之間存在著前后次序關系。將ai-1稱為ai的直接前趨，ai+1稱為ai的直接后繼。即，對于ai，當i=2, …, n時，有且僅有一個直接前趨ai-1，當i=1, 2, …, n-1時，有且僅有一個直接后繼ai+1，而a1是表中第一個元素，它沒有前趨，an是最后一個元素，它無后繼。

需要說明的是：ai為序號為i的數據元素（i=1, 2, …, n），在本書中，將它的數據類型抽象為datatype，而在實際應用中，datatype可根據具體應用問題而代之以不同的數據類型。例如，在學生情況信息表中，它是用戶自定義的學生類型；在字符串中，它是字符型。

2.1.2 線性表的基本操作

在第1章中提到，數據結構中元素的操作（或稱運算）是定義在邏輯結構層次上的，而操作的具體實現是建立在存儲結構上的，因此下面定義的線性表的基本操作作為邏輯結構的一部分，每一個操作的具體實現只有在確定了線性表的存儲結構之后才能完成。

線性表上的基本操作有以下幾種。

（1）線性表初始化：Init_List(L)。

初始條件：表L不存在。

操作結果：構造一個空的線性表L。

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

初始條件：表L存在。

操作結果：返回線性表中的所含元素的個數。

（3）取表元：Get_List (L, i)。

初始條件：表L存在且1≤i≤Length_List(L)。

操作結果：返回線性表L中的第i個元素的值或地址。

（4）按值查找：Locate_List (L, x)。

初始條件：線性表L存在，x是給定的一個數據元素。

操作結果：在表L中查找值為 x 的數據元素，其結果返回在L中首次出現的值為 x的那個元素的序號或地址，稱為查找成功；否則，在L中未找到值為 x 的數據元素，返回一特殊值表示查找失敗。

（5）插入操作：Insert_List (L, i, x)。

初始條件：線性表L存在，插入位置正確（1≤i≤n+1, n為插入前的表長）。

操作結果：在線性表L的第i個位置上插入一個值為x的新元素，這樣使原序號為i , i+1, … , n的數據元素的序號變為i+1, i+2, … , n+1，插入后，新表長=原表長+1。

（6）刪除操作：Delete_List (L, i)。

初始條件：線性表L存在，1≤i≤n。

操作結果：在線性表L中刪除序號為i的數據元素，刪除后使序號為i+1, i+2, …, n的元素的序號變為i, i+1, …, n-1，新表長=原表長-1。需要說明以下幾點。

（1）數據結構上的基本操作（或運算）不是它的全部操作（或運算），而是一些常用的基本操作（或運算），每一個基本操作（或運算）在實現時也可能根據不同的存儲結構派生出一系列相關的操作（或運算）。例如，線性表的查找在鏈式存儲結構中還有按序號查找；再如，插入操作，可能是將新元素插入到某一元素之前，也可能是將新元素插入到某一元素之后，還可能是將新元素插入到其他適當的位置，等等。不可能也沒有必要全部定義出一種數據結構的運算集，讀者掌握了某一數據結構上的基本運算后，其他運算可以通過基本運算來實現，也可以直接去實現。

（2）在上面各操作中定義的線性表L只是一個在邏輯結構層次上抽象的線性表，尚未涉及它的存儲結構，因此每個操作在邏輯結構層次上尚不能用具體的程序設計語言寫出具體的算法，其算法只有在存儲結構確立之后才能用具體程序設計語言實現。

（3）正因為這些操作僅是邏輯上的說明，因此以上用來定義操作的函數中所列的參數的數據類型并不明確說明，只是隱含在函數說明中，對于參數的傳遞方式也不予考慮，這是因為只有在涉及具體實現時才去明確其參數的數據類型和傳遞方式。