主要學習內容1線性表的概念和性質線性表的順序實現23線性表的鏈式實現4線性表應用及其下算法設計線性表概念及性質線性表簡稱表，是由n（n≥0）個數據元素構成的有限序列。n稱為線性表的表長，當n=0，表長為0，表中沒有元素，稱為空線性表，簡稱空表；當n>0，非空表，記為：L=(a0,a1,a2,…,ai,…,an-1)；每個元素有一個固定的位序號，如元素a0的位序號是0，ai的位序號是i；例如，A=(5,3,2,9)包含4個整數，這4個元素的位序依次為0、1、2、3。線性表線性表中元素之間的次序非常重要。舉例：一個單詞是字符構成的線性表；一篇文章是單詞構成的線性表；一個菜譜是由操作指令構成的線性表；一個文件是磁盤上的數據塊構成的線性表。線性表L=(a0,a1,a2,…,ai,…,an-1)，除了首元素a0，每個元素都有一個直接前驅，除了尾元素an-1，每個元素都有一個直接后繼；元素之間的關系為一對一的線性關系，線性表的邏輯結構是線性結構。如果線性表中的元素值隨著位序的增大遞增或遞減，則該線性表稱為有序表；如果元素值的大小和位序之間沒有特定關系，則該線性表稱為無序表。線性表有窮性：線性表中的元素個數是有限的；同構性：一般來說，線性表中所有元素具有相同的性質，即具有相同的類型；如果數據元素性質不同，通常不具有實際應用意義；不同類型元素構成的線性表，如一個整數線性表和一個書目單，雖然作用和應用場合不同，但其元素之間的邏輯關系和基本操作是相同的。線性表特點T類型元素構成的線性表是由T類型元素構成的有限序列，并且具有以下基本操作：（1）創建一個空線性表（init）；（2）判斷線性表是否為空（empty）；（3）求出線性表的長度（len）；（4）將線性表清空（clear）；（5）在指定位置插入一個元素（insert）；（6）刪除指定位置的元素（remove）；（7）獲取指定位置的元素（retrieve）；（8）用指定元素替換線性表的指定位置處的元素（replace）；（9）判斷指定元素item在線性表中是否存在（contains）；（10）對線性表中每個元素進行遍歷（traverse）。線性表的抽象數據類型ADT1）動態性：線性表是動態的結構，可以進行元素的插入或刪除，長度可以變化。2）基于位序進行插入、刪除、讀寫等操作。Python列表（list）表元素可不同構實現ADT中的全部方法Python元組（tuple）表不可以改變，不能修改、添加、刪除元素，只能按位序訪問Python字符串（str）表中元素限定為單個字符字符串操作Python內置線性結構

線性表抽象類fromabcimportABCMeta,abstractmethodclassAbstractList(metaclass=ABCMeta):"""抽象表類，metaclass=ABCMeta表示

AbstractList類為ABCMeta的子類"""

@abstractmethoddef__init__(self):"""初始化線性表"""

@abstractmethoddefempty(self):"""判斷表是否為空"""

@abstractmethoddef__len__(self):"""返回表中元素的個數"""

@abstractmethoddefclear(self):"""清空表"""

@abstractmethoddefinsert(self,i,item):"""在表中i號位置插入元素item""“@abstractmethoddefremove(self,i):"""刪除i號位置的元素"""

@abstractmethoddefretrieve(self,i):"""獲取i號位置的元素"""

@abstractmethoddefreplace(self,i,item):"""用item替換表中i號位置的元素"""

@abstractmethoddefcontains(self,item):"""判斷表中是否包含元素item"""

@abstractmethoddeftraverse(self):"""輸出表中的所有元素"""按操作方法不同普通線性表、列表，是Python列表的抽象概念棧隊列雙端隊列優先隊列按數據元素類型不同字符串線性結構分類順序存儲鏈式存儲線性表的存儲線性表的順序存儲所有元素按照邏輯順序依次存儲在一塊連續的存儲空間中，簡稱順序表。具有前驅、后繼關系的兩個元素其內存映像也相鄰，即元素之間物理位置的相鄰直接反映其邏輯關系的前后。順序存儲元素內置的順序表an-1n-1…aii……a11a00數據元素邏輯地址…an-1Location(a0)+(n-1)*c…aiLocation(a0)+i*c……a1Location(a0)+ca0Location(a0)數據元素存儲地址…c是一個元素的大小。an-1Location(a0)+(n-1)*c’…aiLocation(a0)+i*c’……a1Location(a0)+c’a0Location(a0)數據元素存儲地址……c’是一個指針（引用）的大小，指向元素對象。元素外置的順序表不管是元素內置的順序表和外置的順序表，根據元素位序號可以直接定位到元素的地址，對元素的存取操作可以在O(1)時間內完成。稱順序表具有隨機存取（RandomAccess）或直接存取的特性。示意圖：順序表特點及簡化表示012…i…-1

a0a1a2…ai…an-1entry如線性表A=(5,3,2,9)在Python語言中直接將其表示為一個list，如alst=[5,3,2,9]未封裝實現。順序表存儲1：用Python列表直接表示Python列表的存儲64位機，每個指針8個字節Python列表的空間遞增機制倍增策略和增量策略相結合倍增策略：將原來數組的容量乘以一個大于1的常數；增量策略是給數組容量增加一個數值。在空間較小時，采用倍增機制；在列表空間較大時，采用增量策略，依次增加9,10,11,12,14,16,18…個空間。從空表開始生成長度為1000（10000）的表，需要27（46）次空間追加操作。列表長度0,總占用字節數56列表長度1,總占用字節數88,表元素容器大小4,增加大小:4列表長度5,總占用字節數120,表元素容器大小8,增加大小:4列表長度9,總占用字節數184,表元素容器大小16,增加大小:8列表長度17,總占用字節數256,表元素容器大小25,增加大小:9列表長度26,總占用字節數336,表元素容器大小35,增加大小:10列表長度36,總占用字節數424,表元素容器大小46,增加大小:11列表長度47,總占用字節數520,表元素容器大小58,增加大小:12列表長度59,總占用字節數632,表元素容器大小72,增加大小:14列表長度73,總占用字節數760,表元素容器大小88,增加大小:16列表長度89,總占用字節數904,表元素容器大小106,增加大小:18列表長度107,總占用字節數1064,表元素容器大小126,增加大小:20列表長度127,總占用字節數1240,表元素容器大小148,增加大小:22列表長度149,總占用字節數1440,表元素容器大小173,增加大小:25列表長度174,總占用字節數1664,表元素容器大小201,增加大小:28列表長度202,總占用字節數1920,表元素容器大小233,增加大小:32列表長度234,總占用字節數2208,表元素容器大小269,增加大小:36列表長度270,總占用字節數2528,表元素容器大小309,增加大小:40列表長度310,總占用字節數2888,表元素容器大小354,增加大小:45列表長度355,總占用字節數3296,表元素容器大小405,增加大小:51列表長度406,總占用字節數3752,表元素容器大小462,增加大小:57列表長度463,總占用字節數4264,表元素容器大小526,增加大小:64擴容總次數:21importsys

lst=[]

empty_size=b=sys.getsizeof(lst)

count=0

print("列表長度%4d,總占用字節數%4d"%(0,b))

forkinrange(500):

lst.append(None)

a=len(lst)

old_b=b

b=sys.getsizeof(lst)

ifb!=old_b:

print("列表長度%4d,總占用字節數%4d,"

"表元素容器大小%4d,增加大小:%4d"

%(a,b,(b-empty_size)/8,(b-old_b)

/8))

count+=1

print("擴容總次數:",count)整個算法O(n)resize所花時間可以忽略；每個append操作的攤銷時間復雜度仍為O(1)。順序表存儲2：用python的list封裝實現利用底層C數組實現順序表定義一個自定義類DynamicArrayList來模擬一個順序表；利用ctypes模塊提供的底層C數組實現線性表的順序存儲，需importctypes；底層C數組對應于內存中的一塊容量確定的連續內存空間，線性表元素依次直接存放在該數組中，即元素內置方式順序存儲。順序表存儲3：利用底層C數組實現順序表importctypesfromAbstractListimportAbstractListclassDynamicArrayList(AbstractList):def__init__(self):defempty(self):def__len__(self):defclear(self):definsert(self,i,item):defremove(self,i):defretrieve(self,i):defreplace(self,i,item):defcontains(self,item):defappend(self,item):deftraverse(self):def__str__(self):def_make_array(self,c):def_resize(self,c):初始化def__init__(self,cap=0):

"""初始化一個空表"""

super().__init__()

self._cur_len=0#線性表元素個數計數

self._capacity=cap#默認數組容量

self._entry=self._make_array(self._capacity)

#存放所有表元素的數組def_make_array(self,c):#私有方法

"""返回一個容量為c的數組"""

return(c*ctypes.py_object)()O(1)判空、求長度、清空defempty(self):

returnself._cur_len==0

def__len__(self):

"""返回線性表中元素個數"""

returnself._cur_len

defclear(self):

delself._entry

self._capacity=0

self._cur_len=0

O(1)插入insert(self,i,item)

ifself._cur_len==self._capacity:#如果線性表的空間已用完

ifself._capacity==0:

cap=4

else:

cap=2*self._capacity

self._resize(cap)#給線性表擴容1倍空間O(n)

forjinrange(self._cur_len,i,-1):#線性表尾部至i號位置所有元素后移

self._entry[j]=self._entry[j-1]

self._entry[i]=item#將新元素item放在i號位置

self._cur_len+=1#表長增1definsert(self,i,item):

"""將元素item插入到表的i號位置"""

ifnot0<=i<=self._cur_len:

raiseIndexError("插入位置不合法")數組空間擴容def_resize(self,c):#保護方法

"""將數組空間擴容至c."""

temp=self._make_array(c)#生成新的更大的數組temp

forkinrange(self._cur_len):#將原線性表元素復制到新數組temp中

temp[k]=self._entry[k]

self._entry=temp#啟用新數組temp存放線性表元素

self._capacity=c#當前線性表的容量為c按位置刪除defremove(self,i)defremove(self,i):

ifnot0<=i<self._cur_len:

raiseIndexError("刪除位置不合法")O(n)

item=self._entry[i]

forjinrange(i,self._cur_len-1):#將找到位置之后的元素后移。

self._entry[j]=self._entry[j+1]

self._cur_len-=1#表長減1

returnitem#返回被刪除元素按值查找defcontains(self,item):

foriinrange(self._cur_len):

ifself._entry[i]==item:

returnTrue

returnFalseO(n)按位置讀寫defretrieve(self,i):

ifnot0<=i<self._cur_len:

raiseIndexError("讀取位置不合法")

returnself._entry[i]

defreplace(self,i,item):

ifnot0<=i<self._cur_len:

raiseIndexError("寫入位置不合法")

self._entry[i]=itemO(1)隨機存取Python語言的列表和C語言的數組都可以用來實現線性表的順序存儲，并且其基本操作的實現和時間性能也大體一致。在具體存儲和使用時，Python語言的列表更加方便靈活，C語言的數組空間更加緊湊。Python列表的本質就相當于一個指針數組，凡是用列表實現的各個數據結構都可以用C語言數組或array模塊中的數組來實現。說明線性表的鏈式實現線性表的鏈式實現不需要使用連續內存空間，表中的數據元素可以存儲在任意可用空間中。鏈式結構通過顯式的指針域來表明元素的前驅、后繼關系。鏈式結構中，元素在內存中的映像稱為結點，結點包含兩大部分：元素值和指針域，其中指針域用于記錄其后繼結點或前驅結點的地址。線性表的鏈式實現結構簡稱為鏈表，根據結點中指針域的數目及尾部結點指針的定義，可以分為單鏈表、雙向鏈表、循環鏈表等。最常見的鏈表形式是單鏈表。鏈表概述單鏈表的每個結點包含2個域，其中entry域存儲元素，next域存儲后繼結點的指針。在Python語言中，entry域存儲的是元素的指針，而在其他語言如C++中，entry域存儲的即是元素值。單鏈表的結點結點類classNode:

def__init__(self,data,link=None):

self.entry=data

self.next=link

L=(a0,a1,a2,…,ai,

…,an-1)Python語言中單鏈表的存儲C、Java等語言中單鏈表的存儲單鏈表單鏈表示意圖用首結點指針head代表整個線性表帶頭結點的單鏈表a0aian-1Λhead……ai-1ai+1……首結點尾結點頭結點用頭結點指針head代表整個線性表python的對象名即指針單鏈表類fromAbstractListimportAbstractListfromNodeimportNodeclassLinkedList(AbstractList):def__init__(self):defempty(self):def__len__(self):defclear(self):definsert(self,i,item):defremove(self,i):defretrieve(self,i):defreplace(self,i,item):defcontains(self,item):deftraverse(self):defget_head(self):初始化、判空def__init__(self):

super().__init__()

self._head=Node(None)defempty(self):

returnself._head.next==

None

headΛO(1)求長度def__len__(self):def__len__(self):

p=self._head.next

count=0

whilep!=None:

p=p.next

count+=1

returncountO(n)a0aian-1Λhead……ai-1ai+1……ppp順序訪問列表清空defclear(self):defclear(self):

p=self._head.next

self._head.next=None

whilep:

q=p

p=p.next

delqa0a1aian-1Λhead……ai-1ai+1……首結點尾結點頭結點O(n)讀取i號元素defretrieve(self,i):defretrieve(self,i):

ifi<0:

raiseIndexError("iistoosmall")

p=self._head.next

count=0

whilepandcount<i:

p=p.next

count+=1

ifp:

returnp.entry

else:

raiseIndexError("iistoobig")O(n)順序存取a0a1aian-1Λhead……ai-1ai+1……pppcount=0count=i

p=self._head.next

count=0

whilepandcount<i:

p=p.next

count+=1將元素item插入到表的i號位置a0a1aian-1Λhead……ai-1ai+1……previousitemnew_node×previous.next=new_nodeprevious=self._head

count=-1

whilepreviousandcount<i-1:

previous=previous.next

count+=1definsert(self,i,item):

ifi<0:

raiseIndexError("iistoosmall")

previous=self._head

count=-1

whilepreviousandcount<i-1:

previous=previous.next

count+=1

ifpreviousisNone:

raiseIndexError("iistoobig")

new_node=Node(item)

new_node.next=previous.next

previous.next=new_nodeO(n)

p=self._head.next

count=0

whilepandcount<i:

p=p.next

count+=1

previous為空，說明i-1結點不存在；不能在i號位置插入；否則指向i-1號結點new_node=Node(item)new_node.next=previous.next刪除i號位置的元素a0a1aian-1Λhead……ai-1ai+1……previous×current×previous.next=current.nextdefremove(self,i):

ifi<0:

raiseIndexError("iistoosmall")

previous=self._head

j=-1

whilepreviousandj<i-1:

previous=previous.next

j+=1

ifpreviousisNone:

raiseIndexError("kistoobig,noelementhaspositioni-1")

current=previous.next

ifcurrentisNone:

raiseIndexError("kistoobig,noelementhaspositioni")

previous.next=current.next

item=current.entry

delcurrent

returnitemitem=current.entrydelcurrentprevious為空，說明i-1結點不存在；current為空，說明i號結點不存在；這兩種情況都不能刪除i號位置結點，否則previous指向i-1號結點，current指向i號結點。O(n)previous=self._head

j=-1

whilepreviousandj<i-1:

previous=previous.next

j+=1ifpreviousisNone:

raiseIndexError("kistoobig,noelementhaspositioni-1")

current=previous.next

ifcurrentisNone:

raiseIndexError("kistoobig,noelementhaspositioni")使算法得到簡化對首結點的操作與對其它結點的操作統一空表與非空表的處理一致表頭結點的作用對單鏈表任意結點的訪問都必須從頭結點或首結點開始順序地向后操作，效率較低。一種可選的改進方法是在鏈表類定義中添加current指針指示最近訪問的結點，同時增設current_position記錄該結點的位序號，這樣當重復訪問current結點或訪問比current_position位序號大的結點時，不必再從head開始定位，而可以直接從current結點開始，結點訪問的效率可以得到提高。這種方法只在按從前往后的次序對表結點進行訪問時才能提高效率。小結循環鏈表a0a1aian-1head……ai-1ai+1……head循環鏈表類的實現classCircularLinkedList:

def__init__(self):

self._head=Node(None)

self._head.next=self._head

defempty(self):

returnself._head.next==self._head

def__len__(self):

p=self._head.next

count=0

whilep!=self._head:

count+=1

p=p.next

returncount與單鏈表結點結構一致，結點類定義可以直接共用；與普通單鏈表類的各個基本操作的實現方法基本一致；主要差別：單鏈表各算法中用于判別活動指針p是否已走到表尾的條件是p為None；而循環鏈表中是p是否再次回到head。插入算法definsert(self,i,item):

ifi<0:

raiseIndexError("iistoosmall")

previous=self._head

count=-1

whilepreviousandcount<i-1:

previous=previous.next

count+=1

ifpreviousisNone:

raiseIndexError("iistoobig")

new_node=Node(item,previous.next)

previous.next=new_nodedefinsert(self,i,item):

ifi<0:

raiseIndexError("iistoosmall")

previous=self._head

count=-1

whileprevious.next!=self._headandcount<i-1:

previous=previous.next

count+=1

ifcount==i-1:

new_node=Node(item,previous.next)

previous.next=new_node

else:

raiseIndexError("iistoobig")帶頭結點單鏈表下的插入算法帶頭結點單向循環鏈表下的插入算法循環鏈表中可以僅設尾指針代表整個鏈表，而不設頭指針。設尾指針的循環鏈表a0a1aian-1……ai-1ai+1……tailtail根據情況考慮是否設頭結點1）從任一結點出發都可訪問到表中所有結點；2）在用頭指針表示的單循環鏈表中，首結點定位操作的時間性能是O(1)，尾結點定位操作的時間性能是O(n)；3）在用尾指針表示的單循環鏈表中，首結點和尾結點的定位都只需O(1)時間性能。循環鏈表的特點刪除算法(自行完成）每個結點有兩個指針，分別指向后繼結點和前驅結點實現方法3：雙向鏈表entrynextpriorclassDuNode:

def__init__(self,entry,prior=None,next=None):

self.entry=entry

self.prior=prior

self.next=next雙向非循環鏈表

a0

a1

an-1

a2……headhead雙向循環鏈表head…………a0aian-1ai-1ai+1head雙向循環鏈表類classDuLinkedList:

def__init__(self):

self._head=DuNode(None)

self._head.next=self._head

self._head.prior=self._head插入操作head…………a0aian-1ai-1ai+1itempreviousfollowingnew_node××插入方法definsert(self,i,item):

ifi<0:

raiseIndexError("iistoosmall")

previous=self._head

count=-1

whileprevious.next!=self._headandcount<i-1:

previous=previous.next

count+=1

ifcount==i-1:

new_node=Node(item,previous.next)

previous.next=new_node

else:

raiseIndexError("iistoobig")definsert(self,i,item):

ifi<0:

raiseIndexError("插入位置不合法，i值小于0")

previous=self._head

count=-1

whileprevious.next!=self._headandcount<i-1:

previous=previous.next

count+=1

following=previous.next

ifcount==i-1:

new_node=DuNode(item,previous,following)

previous.next=new_node

following.prior=new_node

else:

raiseIndexError("插入位置不合法，i值太大")帶頭結點單向循環鏈表下的插入算法帶頭結點雙向循環鏈表下的插入算法“插入”和“刪除”時需要同時修改前驅和后繼兩個方向上的指針。對指向雙鏈表結點的任意current指針，如其前驅結點和后繼結點存在，則：current=current.next.prior=current.prior.next，在插入和刪除操作時，不必定位插入或刪除位置的前驅結點，而可以直接定位當前位置結點。可不設頭指針或和尾指針，而設一個current指針指示最近訪問結點，同時設current_position記錄該結點的位序號。當需定位i號結點時，活動指針總是從current開始，根據current_position與i的大小關系，確定移動方向和次數。（此時一般不再設頭結點）雙向鏈表特點刪除算法（自行完成）有序表有序表類classOrderedList(LinkedList):

defadd(self,item):

p=self._head

whilep.nextandp.next.entry<=item:

p=p.next

newnode=Node(item,p.next)

p.next=newnode

definsert(self,position,item):

ifposition<0orposition>len(self):

raiseException("插入位置不合法")

ifposition>0:

previous=self.retrieve(position-1)

ifitem<previous:

raiseException("插入位置不正確")

ifposition<len(self)-1:

nextvalue=self.retrieve(position)

ifitem>nextvalue:

raiseException("插入位置不正確")

super().insert(position,item)

defreplace(self,position,item):

pass是/否帶頭結點單向/雙向是/否循環鏈表種類8種各種鏈表實現的比較類別特點和適用場合不加頭結點單鏈表0號位置的插入、刪除等操作需要額外處理；適合遞歸處理。加了頭結點的單鏈表0號位置的操作與其他位置的操作一致，使算法得到簡化，廣泛使用。單向循環鏈表可以方便地從尾結點走到頭結點，方便循環往復地操作。雙向鏈表存儲密度更低，需要頻繁進行兩個方向的行進時適用。根據重要操作的方便性和效率進行選擇優點：1．動態管理存儲空間，不需事先申請空間2．不需要擔心溢出3．插入刪除只引起指針的變化，效率更高。缺點：1．順序存取，非隨機存取，根據位序讀寫效率為O(n)2．由于涉及到指針操作，程序設計的復雜性增大3．鏈域也占空間，使存儲密度降低，必定小于1。鏈表結構優缺點

1．元素個體較大2．不能事先確定表長3．經常需要做插入、刪除和元素的重排。適用場合優點1．程序設計簡單；2．元素的物理位置反映邏輯關系，可實現隨機存取，根據位序的讀寫時間效率為O(1)；3．存儲密度為1。缺點1．須事先確定初始表長2．插入刪除會帶來元素的移動3．多次插入后初始空間耗盡，造成溢出或需要空間擴容順序表優缺點（不局限僅在python中實現）1．經常需要根據位序進行讀寫2．很少在非尾部位置插入和刪除3．元素個體較小4．表長能事先確定適用場合順序表與鏈表基本操作時間復雜度序號方法順序表下時間復雜度單鏈表下時間復雜度1initO()O()2emptyO()O()3lenO()O()4clearO()O()5appendO()O()6insertO()O()7removeO()O()8retrieveO()O()9replaceO()O()10containsO()O()順序表與鏈表的比較類別優點缺點適用場合

順序表1．程序設計簡單；2．元素的物理位置反映邏輯關系，可實現隨機存取，根據位序的讀寫時間效率為O(1)3．存儲密度為1。1．須事先確定初始表長2．插入刪除會帶來元素的移動3．多次插入后初始空間耗盡，造成溢出或需要空間擴容1．元素個體較小2．表長能事先確定3．很少在非尾部位置插入和刪除4．經常需要根據位序進行讀寫

鏈表1．動態管理存儲空間，不需事先申請空間2．不需要擔心溢出3．插入刪除只引起指針的變化，效率更高。1．不能做到隨機存取，根據位序讀寫效率為O(n)2．由于涉及到指針操作，程序設計的復雜性增大3．鏈域也占空間，使存儲密度降低，必定小于1。1．元素個體較大2．不能事先確定表長3．經常需要做插入、刪除和元素的重排。序列sequence棧線性表list順序表Python 列表底層數組實現的順序表集合運算鏈表單鏈表循環鏈表約瑟夫環雙向鏈表隊列抽象數據類型層數據結構層實現層應用層數學概念層概念層算法層程序設計層自頂向下的數據結構層次線性表應用用無序線性表表示集合，假設集合A={7,2,1}，B={3,6,7,2,5}，求C=A∩B={7,2}。集合運算defintersect(la,lb):

m=len(la)

n=len(lb)

lc=DynamicArrayList()

foriinrange(m):

x=la.retrieve(i)

iflb.contains(x):

lc.append(x)

returnlcO(m*n)用有序線