摘要：文章首發于公眾號一件風衣在編程中，我們常使用一組有順序的數據來表示某個有意義的數據，這種一組元素的序列的抽象，就是線性表，簡稱表，是很多復雜數據結構的實現基礎，在中，和就可以看作是線性表的實現。

文章首發于公眾號一件風衣（ID：yijianfengyi）

在編程中，我們常使用一組有順序的數據來表示某個有意義的數據，這種一組元素的序列的抽象，就是線性表，簡稱表，是很多復雜數據結構的實現基礎，在Python中，list和tuple就可以看作是線性表的實現。

一、線性表的性質和ADT

（一）幾個基本概念
1.線性表是一組有窮元素（元素可以是任何類型的數據）拍成的序列，元素的位置稱作下標，下標從0開始計數；
2.表中元素的個數稱作表的長度，不含任何元素的表稱為空表，空表的長度為0；
3.非空表的第一個元素為首元素，最后一個元素為尾元素，除首元素外，每一個元素的上一個元素稱為前驅元素，除尾元素外，每一個元素的后一個元素稱為后繼元素；

（二）表抽象數據類型
1.表的操作
考慮到需求，我們對表可能有如下操作：
?創建一個空表，或者根據提供的元素序列初始化一個新表；
?判斷是否為空表、輸出表的長度（元素個數）、檢查是否存在某個元素；
?在表中插入一個元素、刪除特定位置的元素或按照內容刪除元素；
?對整個表進行的操作，比如兩個表的合并、一個表按照某種運算生成一個新表等；
?遍歷

2.表抽象數據類型的偽代碼描述
根據以上操作，我們可以設計表抽象數據類型偽代碼如下：

ADT List:  #表抽象數據類型
    List(self)  #創建一個新表
    is_empty(self)  #判斷self是否為空表
    len(self)  #獲得self的長度
    prepend(self,elem)  #在self的首元素前插入元素elem
    append(self,elem)  #在self的尾元素后插入元素elem
    insert(self,elem,i)  #在self的位置i處插入元素elem，其他元素保持相對位置不變
    del_first(self)  #刪除self的首元素
    del_last(self)  #刪除self的尾元素
    del(self,i)  #刪除self的第i個元素
    search(self,elem)  #查找elem在self中出現的位置，不存在則返回-1
    forall(self,op)  #對self中的每個元素執行操作op

3.經典的線性表實現模型
?將表中的元素順序存放在一片足夠大的連續存儲位置里，稱作順序表，元素在存儲區內的物理順序就是該表的元素的邏輯順序，本文后面講討論順序表；
?將表中的元素通過鏈接的形式保持順序，存儲在一系列存儲區內，稱作鏈表，在下一篇文章中討論。

二、順序表的實現

（一）順序表的布局方案

先考慮一種簡單情況：如果表中的每一個元素占用的存儲空間相同，那么可以直接在內存中順序存儲，假設第0個元素的存儲位置為l_0，每個元素占用的空間為c=size(e)，那么第i個元素的存儲位置就是l_i=l_0 + c * i，此時實現對某個位置元素的訪問，可以直接通過計算出的位置訪問，時間復雜度為O(1)。

那么當元素長度不一樣的時候怎么解決呢？我們可以按照剛才的方式，在順序表中存放元素的存儲位置，而元素另行存儲，這個順序表就稱作是這組數據的索引，這就是最簡單的索引結構了。索引順序表的每個元素為地址，占用空間一樣，直接訪問索引再依據索引中存放的地址找到實際元素，時間復雜度依然為O(1)。

新的問題來了，表的操作要求表的長度是可以變化的，增刪操作均會引起表長度的變化，那么如何給表分配空間呢？Python中的tuple類型就是一種不可變的數據類型，在建立時根據元素個數分配存儲區域，但需要變化長度的時候，就不能用這種分配方式了。

解決這種方式有一種方法是分配一大片區域，在表的開始位置記錄這個表的容量和現有元素個數，表中除了構造時的元素外，其他空間留出空位供新元素使用。至于如果需要的空間超出了表的容量了怎么辦呢？這個我們后面再討論，現在我們先依照上面的思路，考慮各種操作的實現。

（二）順序表基本操作的實現

1.創建空表
分配一塊內存區域，記錄表的容量，同時將表的元素個數設置為0，例如max=8，num=0；

2.判斷表空表滿
很簡單，num=0時為表空，num=max時為表滿；O(1)

3.訪問下標為i的元素
首先檢查下標i是否合法，即i在0到num-1之間（能取到邊界值），合法則計算實際位置，由實際位置返回元素值；O(1)

4.遍歷訪問元素
用一個整數標志記錄遍歷到達的位置，每個元素的位置同理計算得出，前后位置可以減一加一實現，注意遍歷時不可超出邊界；O(n)

5.查找某值在表中第一次出現的位置
基于下標線性檢索，依次比較元素和該值是否相同，相同則返回索引，若檢索完不存在相同，則返回-1；O(n)

6.查找某值在表中k位置后第一次出現的位置
原理與上一條相同，只不過索引從k開始而已。O(n)

7.尾端插入新元素
先不考慮分配更多空間的情況，表滿時插入返回錯誤提示，不滿時，直接在該位置插入，并修改num的值；O(1)

8.新元素插入到位置k
這是插入的一般情況，尾端時k=num。先檢查k是否合法，如果合法，將表中k位置和之后的元素都向后移動，以保證表的順序，然后在k位置插入該元素，更新num值；O(n)

9.刪除尾元素
直接num減一就行，在邏輯上已經刪除了尾元素；O(1)

10.刪除位置k的元素
將位置k之后的元素依次前移，num減一；O(n)

11.基于條件的刪除
遍歷，刪除；O(n*n)

（三）補充說明
1.順序表的實現方式

2.表滿之后的操作
插入時如果表滿，可以申請一片更大的空間，然后將表的元素全部復制過去，然后改變表對象的鏈接指向新區域，插入新元素，這樣就可以實現表的動態擴容。

3.擴容的大小
可以是線性擴容，例如每次增加10個元素存儲空間，考慮到每次擴容需要復制，此時插入一個元素的平均時間復雜度為O(n)，顯然不太理想，另一種一種方法加倍擴容，每次擴容后容量翻倍，此時插入操作的復雜度為O(1)，雖然效率提高了，但造成了空間的浪費。（時間復雜度的具體計算在此不做討論）

（四）Python中的list類型

Python中的list就是個可變的順序表類型，實現了以上各種操作，感興趣可以去看具體實現的代碼，其中表容量操作由解釋器完成，避免了認為設置容量引發的錯誤。最后列舉幾個操作的使用：
1.訪問

list[i]

2.獲取元素個數

len(list)

3.返回最大值，最小值

max(list)
min(list)

4.將元組轉化為列表

list(seq)

5.尾部插入新元素

list.append(elem)

6.統計某個元素出現的次數

list.count(elem)

7.尾部一次性追加元素序列

list.extend(seq)

8.找出第一個值為elem的元素的索引

list.index(elem)

9.在i位置插入elem

list.insert(i,elem)

10.彈出第i個元素，并返回該元素的值，默認為最后一個元素

list.pop(i)

11.移除第一個值為elem的元素

list.remove(elem)

12.將list反向

list.reverse()

13.清空列表

list.clear()

14.復制列表

list.copy()

15.對列表進行排序

list.sort(cmp=None,key=None,reverse=False)

cmp為排序方法，key為用來比較的元素，reverse為True時降序，默認False為升序，具體使用很靈活，可以參考相關文檔。

思考：設計一個列表（以后我們會知道這種列表叫做棧），可以實現
push(x)：將x插入隊尾
pop()：彈出最后一個元素，并返回該值
top()：返回第一個元素
getMin()：返回列表中的最小值
并且要求每個操作的時間復雜度都為O(1)，難點在于getMin()的時間復雜度。

以下是上篇思考題我的實現，歡迎提建議：

import datetime
class Student:
    _idnumber = 0  #用于計數和生成累加學號
    @classmethod  #類方法，用于生成學號
    def _generate_id(cls):
        cls._idnumber += 1
        year = datetime.date.today().year
        return "{:04}{:05}".format(year,cls._idnumber)
    def __init__(self,name,sex,birthday): #驗證輸入后初始化
        if not sex in ("男","女"):
            raise StudentValueError(sex)
        if not isinstance(name,str):
            raise StudentValueError(name)
        try:
            birth = datetime.date(*birthday)
        except:
            raise StudentValueError(birthday)
        self._name = name
        self._sex = sex
        self._birthday = birth
        self._studentid = Student._generate_id()
    def print(self):  #打印全部屬性
        print(",".join((self._studentid,self._name,self._sex,str(self._birthday))))
    def setName(self,newname):  #設置姓名屬性，其他屬性同理
        if not isinstance(newname,str):
            raise StudentValueError(name)
        self._name = newname
    def getAge(self):  #計算年齡
        today = datetime.date.today()
        try:
            birthday = self._birthday.replace(year = today.year)  #如果生日是2月29且今年不是閏年則會異常
        except ValueError:
            birthday = self._birthday.replace(year = today.year,day = today.day - 1)  #解決方法是把日減一
        if birthday > today:  #沒到今年生日則減一，到了則不減
            return today.year - self._birthday.year - 1
        else:
            return  today.year - self._birthday.year
        
class StudentValueError(ValueError):  #用于拋出異常的類
    pass

測試效果如下：