摘要：文章首發(fā)于公眾號(hào)一件風(fēng)衣在編程中，我們常使用一組有順序的數(shù)據(jù)來(lái)表示某個(gè)有意義的數(shù)據(jù)，這種一組元素的序列的抽象，就是線性表，簡(jiǎn)稱(chēng)表，是很多復(fù)雜數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)基礎(chǔ)，在中，和就可以看作是線性表的實(shí)現(xiàn)。

文章首發(fā)于公眾號(hào)一件風(fēng)衣（ID：yijianfengyi）

在編程中，我們常使用一組有順序的數(shù)據(jù)來(lái)表示某個(gè)有意義的數(shù)據(jù)，這種一組元素的序列的抽象，就是線性表，簡(jiǎn)稱(chēng)表，是很多復(fù)雜數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)基礎(chǔ)，在Python中，list和tuple就可以看作是線性表的實(shí)現(xiàn)。

一、線性表的性質(zhì)和ADT

（一）幾個(gè)基本概念
1.線性表是一組有窮元素（元素可以是任何類(lèi)型的數(shù)據(jù)）拍成的序列，元素的位置稱(chēng)作下標(biāo)，下標(biāo)從0開(kāi)始計(jì)數(shù)；
2.表中元素的個(gè)數(shù)稱(chēng)作表的長(zhǎng)度，不含任何元素的表稱(chēng)為空表，空表的長(zhǎng)度為0；
3.非空表的第一個(gè)元素為首元素，最后一個(gè)元素為尾元素，除首元素外，每一個(gè)元素的上一個(gè)元素稱(chēng)為前驅(qū)元素，除尾元素外，每一個(gè)元素的后一個(gè)元素稱(chēng)為后繼元素；

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

2.表抽象數(shù)據(jù)類(lèi)型的偽代碼描述
根據(jù)以上操作，我們可以設(shè)計(jì)表抽象數(shù)據(jù)類(lèi)型偽代碼如下：

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

3.經(jīng)典的線性表實(shí)現(xiàn)模型
?將表中的元素順序存放在一片足夠大的連續(xù)存儲(chǔ)位置里，稱(chēng)作順序表，元素在存儲(chǔ)區(qū)內(nèi)的物理順序就是該表的元素的邏輯順序，本文后面講討論順序表；
?將表中的元素通過(guò)鏈接的形式保持順序，存儲(chǔ)在一系列存儲(chǔ)區(qū)內(nèi)，稱(chēng)作鏈表，在下一篇文章中討論。

二、順序表的實(shí)現(xiàn)

（一）順序表的布局方案

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

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

新的問(wèn)題來(lái)了，表的操作要求表的長(zhǎng)度是可以變化的，增刪操作均會(huì)引起表長(zhǎng)度的變化，那么如何給表分配空間呢？Python中的tuple類(lèi)型就是一種不可變的數(shù)據(jù)類(lèi)型，在建立時(shí)根據(jù)元素個(gè)數(shù)分配存儲(chǔ)區(qū)域，但需要變化長(zhǎng)度的時(shí)候，就不能用這種分配方式了。

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

（二）順序表基本操作的實(shí)現(xiàn)

1.創(chuàng)建空表
分配一塊內(nèi)存區(qū)域，記錄表的容量，同時(shí)將表的元素個(gè)數(shù)設(shè)置為0，例如max=8，num=0；

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

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

4.遍歷訪問(wèn)元素
用一個(gè)整數(shù)標(biāo)志記錄遍歷到達(dá)的位置，每個(gè)元素的位置同理計(jì)算得出，前后位置可以減一加一實(shí)現(xiàn)，注意遍歷時(shí)不可超出邊界；O(n)

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

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

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

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

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

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

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

（三）補(bǔ)充說(shuō)明
1.順序表的實(shí)現(xiàn)方式

2.表滿之后的操作
插入時(shí)如果表滿，可以申請(qǐng)一片更大的空間，然后將表的元素全部復(fù)制過(guò)去，然后改變表對(duì)象的鏈接指向新區(qū)域，插入新元素，這樣就可以實(shí)現(xiàn)表的動(dòng)態(tài)擴(kuò)容。

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

（四）Python中的list類(lèi)型

Python中的list就是個(gè)可變的順序表類(lèi)型，實(shí)現(xiàn)了以上各種操作，感興趣可以去看具體實(shí)現(xiàn)的代碼，其中表容量操作由解釋器完成，避免了認(rèn)為設(shè)置容量引發(fā)的錯(cuò)誤。最后列舉幾個(gè)操作的使用：
1.訪問(wèn)

list[i]

2.獲取元素個(gè)數(shù)

len(list)

3.返回最大值，最小值

max(list)
min(list)

4.將元組轉(zhuǎn)化為列表

list(seq)

5.尾部插入新元素

list.append(elem)

6.統(tǒng)計(jì)某個(gè)元素出現(xiàn)的次數(shù)

list.count(elem)

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

list.extend(seq)

8.找出第一個(gè)值為elem的元素的索引

list.index(elem)

9.在i位置插入elem

list.insert(i,elem)

10.彈出第i個(gè)元素，并返回該元素的值，默認(rèn)為最后一個(gè)元素

list.pop(i)

11.移除第一個(gè)值為elem的元素

list.remove(elem)

12.將list反向

list.reverse()

13.清空列表

list.clear()

14.復(fù)制列表

list.copy()

15.對(duì)列表進(jìn)行排序

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

cmp為排序方法，key為用來(lái)比較的元素，reverse為T(mén)rue時(shí)降序，默認(rèn)False為升序，具體使用很靈活，可以參考相關(guān)文檔。

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

以下是上篇思考題我的實(shí)現(xiàn)，歡迎提建議：

import datetime
class Student:
    _idnumber = 0  #用于計(jì)數(shù)和生成累加學(xué)號(hào)
    @classmethod  #類(lèi)方法，用于生成學(xué)號(hào)
    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): #驗(yàn)證輸入后初始化
        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):  #設(shè)置姓名屬性，其他屬性同理
        if not isinstance(newname,str):
            raise StudentValueError(name)
        self._name = newname
    def getAge(self):  #計(jì)算年齡
        today = datetime.date.today()
        try:
            birthday = self._birthday.replace(year = today.year)  #如果生日是2月29且今年不是閏年則會(huì)異常
        except ValueError:
            birthday = self._birthday.replace(year = today.year,day = today.day - 1)  #解決方法是把日減一
        if birthday > today:  #沒(méi)到今年生日則減一，到了則不減
            return today.year - self._birthday.year - 1
        else:
            return  today.year - self._birthday.year
        
class StudentValueError(ValueError):  #用于拋出異常的類(lèi)
    pass

測(cè)試效果如下：