Python資料結構與演算法（2.1）——線性表的基本概念

0. 學習目標

線性表是應用最為廣泛的一種資料結構，如其名所示，是一種典型的線性結構，本節主要介紹線性表的有關概念和基本運算，
通過本節學習，應掌握以下內容：

• 線性表的定義
• 線性表的邏輯結構

1. 線性表的定義

線性表 (Linear List) 是最基礎也是最常用的資料結構，是有 n ( n ≥ 0 ) n(n≥0) n(n≥0) 個具有相同屬性的資料元素組成的有限序列，序列中元素的個數 n n n 稱為線性表的長度，當 n = 0 n=0 n=0 時稱為空表，即不含有任何元素，非空線性表L可以用以下形式表示：
L = ( a 1 , a 2 , … , a i , a i + 1 , … , a n ) L=( a_1, a_2, …, a_i, a_{i+1}, …, a_n) L=(a1?,a2?,…,ai?,ai+1?,…,an?)
其中 a i ( 1 ≤ i ≤ n ) a_i(1≤i≤n) ai?(1≤i≤n) 表示 L 中的第 i i i 個資料元素，下標 i i i 為 a i a_i ai? 元素在線性表中的序號和位置，線性表中元素的順序取決于添加順序或移除順序，某個元素被添加到線性表中后，它與前后元素的相對位置將保持不變，在線性表中，把 a i ( 2 ≤ i ≤ n ) a_i(2≤i≤n) ai?(2≤i≤n) 的前一元素 a i ? 1 a_{i-1} ai?1? 稱為 a i a_i ai? 的直接前趨，后一元素 a i + 1 a_{i+1} ai+1? 稱為 a i a_i ai? 的直接后繼，第一個元素 a 1 a_1 a1? 稱為表頭元素，最后一個元素 a n a_n an? 稱為表尾元素，
非空線性表的邏輯結構可以用下圖來表示：

由上圖所示，我們不難發現非空線性表的邏輯結構具有如下特征：

• 線性表中的資料元素是按前后位置有序的，即第 i i i 個資料元素 a i a_i ai? 在邏輯上是第 i + 1 i+1 i+1 個元素 a i + 1 a_{i+1} ai+1? 的直接前趨，第 i + 1 i+1 i+1 個資料元素 a i + 1 a_{i+1} ai+1? 在邏輯上是第 i i i 個資料元素 a i a_i ai? 的直接后繼，
• 線性表中第一個資料元素 a 1 a_1 a1? 有且僅有一個直接后繼而沒有直接前驅，最后一個資料元素 a n a_n an? 有且僅有一個直接前驅而沒有直接后繼，其余每個資料元素 a i ( 1 ＜ i ＜ n ) a_i(1＜i＜n) ai?(1＜i＜n) 有且僅有一個直接前驅，并且有且僅有一個直接后繼，
• 線性表中資料元素的型別是相同的，表長的取值是一個有限數，最小為 0，

線性表在現實世界的非常常見，例如：26個英文字母表——(a, b, c, …, z)，可以視為一個線性表，其中每個字母是一個資料元素；植物進化的演化程序也可以用線性表的形式表示——(藻類植物, 裸蕨類植物, 蕨類植物, 裸子植物, 被子植物)；在復雜的線性表中，一個資料元素可以由若干個資料項組成，一個學生基本資訊表可以視為一個線性表，其中每個學生的所有相關資訊組成一個資料元素(也可以稱為記錄，record)，每個資料元素包含學號、姓名、性別、年齡、班級、聯系方式等資料項，
由上述示例可以看出，在現實世界的不同的情況下，線性表的資料元素的具體內容雖不相同，但是都反映了資料元素之間的相對位置是線性的邏輯結構特性，

2. 線性表的操作

資料結構的操作是定義在邏輯結構層次上的，而操作的具體實作則是建立在存盤結構上的，因此下面定義的線性表的基本操作作為邏輯結構的一部分，給出了這些操作的功能是“做什么”，至于“如何做”則依賴于選定什么樣的存盤結構，
順序表的主要操作包括：

• 初始化線性表：構造空的線性表
• 計數：回傳串列中的元素數
• 按序號取元素：讀取線性表指定位置的元素
• 按值查找：在串列中查找指定的資料元素
• 插入：在串列中插入一個元素
• 洗掉元素：從串列中洗掉并回傳指定的位置元素

3. 抽象資料型別線性表定義

綜上所述，抽象資料型別線性表的定義如下：

ADT List:
?資料物件： D = a i ∣ a i ∈ D a t a T y p e , i = 1 , 2 , . . . , n , n ≥ 0 D={a_i|a_i∈DataType, i=1,2,...,n,n\geq0} D=ai?∣ai?∈DataType,i=1,2,...,n,n≥0
?資料關系： R = < a i , a i + 1 > ∣ a i , a i + 1 ∈ D , i = 1 , 2 , . . . , n ? 1 R={<a_{i},a_{i+1}>|a_i,a_{i+1}∈D,i=1,2,...,n-1} R=<ai?,ai+1?>∣ai?,ai+1?∈D,i=1,2,...,n?1
?基本操作：
??1. __itit__(): 初始化線性表
???將線性表 L 置為空表
??2. __len__(): 求取并回傳線性表所含元素的個數 n
???若線性表為空，則回傳整數0
??3. __getitem__(i): 讀取線性表 L 中第 i 個資料元素
???其中 1 ≤ i ≤ len(L)
??4. locate(x): 在線性表 L 中查找值為 x 的資料元素
???若查找成功則回傳第一個值為 x 的元素的序號；否則，回傳一特殊值(例如-1)，表示查找失敗
??5. insert(i, x): 在線性表 L 第 i 個位置上插入值為 x 的新元素
???其中 1 ≤ i ≤ len(L)+1，插入后表長增 1；原序號為 i, i+1, …, n 的資料元素的序號變為 i+1, i+2, …, n+1
??6. __delitem(i)__: 在線性表 L 中洗掉序號為 i 的資料元素
???其中 1 ≤ i ≤ len(L)，洗掉后表長減 １；原序號為 i+1, i+2, …, n 的元素變為序號 i, i+1, …, n-1

以上只給出了定義在線性表邏輯結構上的最基本運算，在實際應用中可借助于這些基本運算構造出更為復雜的運算，