數(shù)據(jù)結(jié)構(gòu)第2章-線性表

第2章線性表

2.1線性表的基本概念

2.2順序表2.3鏈表2.4順序表和鏈表的比較2.5鏈表的應(yīng)用2.1.1線性表的定義線性表是一種線性結(jié)構(gòu)，是某類數(shù)據(jù)的集合，每個線性表的數(shù)據(jù)元素都具有以下共性：（1）集合中的所有元素都是同一種數(shù)據(jù)類型；（2）這些集合具有有限的大??；（3）集合中的元素都是線性排列的，即存在一個首元素和一個尾元素；除了尾元素外，每個元素都有一個后繼；除了首元素外，每個元素都有一個前驅(qū)。2.1線性表的基本概念

可以用以下形式來表示線性表：(a1，a2，…ai-1，ai，ai+1，…an)其中ai表示線性表中的任意一個元素，n表示元素的個數(shù)。表中相鄰元素之間存在著順序關(guān)系。將ai-1

稱為ai

的直接前驅(qū)，ai+1

稱為ai

的直接后繼。而a1是表中第一個元素，沒有前驅(qū)；an

是最后一個元素，無后繼。2.1線性表的基本概念

一種典型的線性表的邏輯結(jié)構(gòu)示例：2.1線性表的基本概念

a1ai-1aianai+12.1.2線性表的存儲結(jié)構(gòu)（1）順序存儲結(jié)構(gòu)該存儲結(jié)構(gòu)是把邏輯上相鄰的結(jié)點(diǎn)存儲在物理位置上相鄰的存儲單元中，結(jié)點(diǎn)之間的邏輯關(guān)系由存儲單元的鄰接關(guān)系來體現(xiàn)。如下圖所示：2.1線性表的基本概念

2.1.2.線性表的存儲結(jié)構(gòu)（2）鏈?zhǔn)酱鎯Y(jié)構(gòu)該結(jié)構(gòu)不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上也相鄰，結(jié)點(diǎn)之間的邏輯關(guān)系是由額外的引用域來表示的。如下圖所示：2.1線性表的基本概念

2.1.3線性表的運(yùn)算2.1線性表的基本概念

運(yùn)算含義InitList(L)線性表初始化Length(L)求線性表的長度Get(L,i)取表元Locate(L,x)查找Insert(L,i,x)插入操作Delete(L,i)刪除操作Empty(L)線性表判空DispList(L)顯示表元素第2章線性表

2.1線性表的基本概念 2.2順序表2.3鏈表2.4順序表和鏈表的比較2.5鏈表的應(yīng)用2.2.1順序表的定義順序表是指采用順序存儲的方式來存儲數(shù)據(jù)元素的線性表。在順序表中，我們通常將結(jié)點(diǎn)依次存放在一組地址連續(xù)的存儲空間中，由于待存儲空間連續(xù)且每個數(shù)據(jù)元素占用的空間相同，因此可以綜合上述信息并通過計(jì)算得出每個元素的存儲位置。2.2順序表假設(shè)對于線性表(a1，a2，…an)，該類型數(shù)據(jù)所需的內(nèi)存單元數(shù)為d，首元素a1的物理地址為LOC(a1)，第i個數(shù)據(jù)元素的物理地址LOC(ai)與LOC(a1)存在如下關(guān)系：LOC(ai)=LOC(a1)+(n-1)d此關(guān)系解釋如下圖，其中，b表示LOC(a1)。2.2順序表2.2.2順序表的運(yùn)算（1）類型說明算法2.1初始化順序表2.2順序表classSeqList(object):def__init__(self):#初始化順序表self.MAX=20#SeqList類列表的數(shù)據(jù)元素最大長度self.SequenceList=[]self.Length=0#Length是列表中元素的實(shí)際個數(shù)（2）順序表創(chuàng)建算法2.2順序表創(chuàng)建2.2順序表defCreateSeqList(self):print("請輸入數(shù)據(jù)，若想結(jié)束輸入請按’#’。")Element=input("請輸入元素：")whileElement!='#':self.SequenceList.append(int(Element))Element=input("請輸入元素：")（3）查找元素算法2.3查找元素2.2順序表defLocate(self):key=eval(input('請輸入要查找的元素值：'))ifkeyinself.SequenceList:ipos=self.SequenceList.index(key)print(“查找成功！元素{}位于當(dāng)前順序表的第{}個位置。”.format(key,ipos+1))else:print("查找失??！當(dāng)前順序表中不存在值為",key,"的元素")（4）指定位置插入元素算法2.4指定位置插入元素2.2順序表defInsert(self):iPos=int(input('請輸入待插入元素的位置：'))element=int(input('請輸入待插入的元素值：'))self.SequenceList.insert(iPos,element)print("插入元素后，當(dāng)前順序表為：\n",self.SequenceList)（5）刪除指定位置的元素算法2.5刪除順序表中指定位置的元素2.2順序表defDelete(self):dPos=int(input('請輸入待刪除元素的位置：'))print(“即將刪除元素",self.SequenceList[dPos],"...")self.SequenceList.pop(dPos)print("刪除后順序表為：\n",self.SequenceList)2.2.3遍歷遍歷是數(shù)據(jù)結(jié)構(gòu)中最重要的運(yùn)算之一，所有關(guān)于數(shù)據(jù)結(jié)構(gòu)的運(yùn)算都建立在遍歷的基礎(chǔ)上，所以把這個內(nèi)容獨(dú)立成節(jié)。遍歷一個順序表就是從順序表的第一個元素起，依次訪問表中的每一個元素。每個元素只訪問一次，直到訪問完所有元素為止。2.2順序表2.2.3遍歷通過SeqList類的成員函數(shù)Traverse(self)，遍歷當(dāng)前順序表中的元素，其算法思路如下：（1）調(diào)用Python內(nèi)置函數(shù)len()函數(shù)得到當(dāng)前順序表的長度SeqListLen。（2）使用變量i來指示當(dāng)前元素的下標(biāo)位置。（3）從變量i=0開始到i=SeqListLen-1為止，循環(huán)調(diào)用print()函數(shù)輸出下標(biāo)位置i處的元素值。2.2順序表2.2.3遍歷算法2.6順序表的遍歷算法2.2順序表defTraverse(self):print("******遍歷順序表中元素******")foriinrange(0,self.Length):print("第{}個元\

素:{}“.format(i,self.SequenceList[i]))2.2.5線性表的順序存儲的主要特點(diǎn)邏輯上相鄰的元素，物理位置上也相鄰?？呻S機(jī)存取線性表中任一元素，只要知道其下標(biāo)。必須按最大可能長度分配存儲空間，存儲空間利用率低，表的容量難以擴(kuò)充，是一種靜態(tài)存儲結(jié)構(gòu)。插入、刪除元素時(shí)，需移動大量元素，平均移動元素為n/2（n為表長）。長度變化較大時(shí)，需按最大空間分配，勢必造成存儲空間的浪費(fèi)。2.2順序表第2章線性表

2.1線性表的基本概念 2.2順序表2.3鏈表2.4順序表和鏈表的比較2.5鏈表的應(yīng)用采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表稱為鏈表。只有一個引用的叫單鏈表，其作用專門用于指向其后繼元素，第一個元素指向第二個元素，第二個指向第三個，……，最后一個數(shù)據(jù)元素結(jié)點(diǎn)的指針為空，因?yàn)樗暮竺鏇]有元素。有兩個引用的叫雙鏈表，通常一個引用用來指向其后繼，另一個引用用來指向其前驅(qū)。2.3鏈表2.3.1單鏈表的定義單鏈表只有一個引用域，其結(jié)構(gòu)可以表示如下：2.3鏈表其中：data部分存放線性表的一個元素值。next部分存放一個引用，指向線性表中下一元素的結(jié)點(diǎn)位置。如果沒有下一個元素，則使用一個特殊的空值（None）2.3.2單鏈表的基本運(yùn)算（1）類型說明定義2.2單鏈表中的結(jié)點(diǎn)定義2.3鏈表classNode(object):def__init__(self,data):self.data=dataself.next=None（2）單鏈表初始化算法2.7單鏈表初始化2.3鏈表classSingleLinkedList(object):def__init__(self):self.head=Node(None)#創(chuàng)建頭結(jié)點(diǎn)（3）創(chuàng)建單鏈表算法2.8創(chuàng)建單鏈表2.3鏈表defCreateSingleLinkedList(self):print(“請輸入數(shù)據(jù)，結(jié)束輸入請按“#”！")cNode=self.headElement=input("請輸入當(dāng)前結(jié)點(diǎn)的值：")whileElement!="#":nNode=Node(int(Element))cNode.next=nNodecNode=cNode.nextElement=input("請輸入當(dāng)前結(jié)點(diǎn)的值：")（4）求單鏈表的長度算法2.9求單鏈表的長度2.3鏈表defLength(self):p=self.head.nexti=0whilep:i+=1p=p.nextreturni（5）查找指定元素并返回其位置算法2.10查找指定元素并返回其位置2.3鏈表defLocate(self):Pos=0;cNode=self.headkey=int(input('請輸入想要查找的元素值：'))ifself.IsEmpty():print("當(dāng)前單鏈表為空！");return-1whilecNode.next!=NoneandcNode.data!=key:cNode=cNode.next;Pos=Pos+1

（5）查找指定元素并返回其位置算法2.10查找指定元素并返回其位置2.3鏈表defLocate(self):#上述程序續(xù)ifcNode.data==key:print("查找成功，值為",key,"的結(jié)點(diǎn)位于該單鏈表的第",Pos,"個位置。")return1else:print(“查找失敗！”)return-1（6）單鏈表尾端插入算法算法2.11單鏈表尾端插入算法2.3鏈表defInsertAtTail(self):element=(input("請輸入待插入結(jié)點(diǎn)的值："))ifelement=="#":returncNode=self.headnNode=Node(int(element))whilecNode.next!=None:cNode=cNode.nextcNode.next=nNode（7）單鏈表首端插入算法算法2.12單鏈表首端插入算法2.3鏈表defInsertAtHead(self):element=input("請輸入待插入結(jié)點(diǎn)的值：")ifelement=="#":returncNode=self.headnNode=Node(int(element))nNode.next=cNode.nextcNode.next=nNode（8）單鏈表任意位置插入元素算法算法2.13單鏈表任意位置插入元素算法2.3鏈表defInsert(self):element=input("請輸入待插入結(jié)點(diǎn)的值：")i=int(input("請輸入待插入結(jié)點(diǎn)的位置："))ifelement=="#":returnifi<1:#待插入的位置不合法returnp=self.head（8）單鏈表任意位置插入元素算法算法2.13單鏈表任意位置插入元素算法2.3鏈表defInsert(self):#上述程序續(xù)

forjinrange(1,i):p=p.nextnNode=Node(int(element))nNode.next=p.nextp.next=nNode（9）刪除值為x的結(jié)點(diǎn)算法2.14刪除值為x的結(jié)點(diǎn)2.3鏈表defDelete(self):x=input("請輸入需要刪除的元素值:")p=self.head.nextwhilep.data!=xandp:t=p;p=p.nextifp:t.next=p.next;

return1else:print("Nodexnotfound!\n");return-1（10）帶頭結(jié)點(diǎn)的單鏈表的遍歷算法2.15帶頭結(jié)點(diǎn)的單鏈表的遍歷算法2.3鏈表defTraverse(self):cNode=self.headifcNode.next==None:print(“當(dāng)前單鏈表為空！”);

returnprint("您當(dāng)前的單鏈表為：")whilecNode!=None:cNode=cNode.nextprint(cNode.data,"->",end="")單鏈表應(yīng)用舉例例2.1刪除單鏈表中結(jié)點(diǎn)值重復(fù)的冗余結(jié)點(diǎn)，使其成為每個結(jié)點(diǎn)的值在單鏈表中唯一存在。2.3鏈表defdelete_sameNode(head):q=head.next

whileq:r=q

whiler.next:

p=r.next

ifp.data==q.data:r.next=p.next

else:r=r.nextq=q.next2.3.3循環(huán)單鏈表單鏈表的各種操作只能從表頭向表尾進(jìn)行，達(dá)到尾結(jié)點(diǎn)后，指針無法回到表頭，如果要回到表頭，這種鏈表已經(jīng)無能為力。必須使用專門的辦法，把鏈表的首尾連接起來，這樣指針自然就可以回到表頭來，形成一個循環(huán)鏈表，其結(jié)構(gòu)如圖2.14所示2.3鏈表（1）創(chuàng)建循環(huán)單鏈表算法2.16創(chuàng)建帶頭結(jié)點(diǎn)的循環(huán)單鏈表2.3鏈表defCreateCSLinkedList(self):print("請輸入數(shù)據(jù)后按回車鍵確認(rèn)，結(jié)束請輸入'#'")data=input("請輸入結(jié)點(diǎn)的值:")cNode=self.head（1）創(chuàng)建循環(huán)單鏈表算法2.16創(chuàng)建帶頭結(jié)點(diǎn)的循環(huán)單鏈表2.3鏈表defCreateCSLinkedList(self):#上述程序續(xù)whiledata!='#':nNode=Node(int(data));cNode.next=nNodenNode.next=self.head;cNode=cNode.nextdata=input("請輸入結(jié)點(diǎn)的值:")（2）刪除算法2.17刪除循環(huán)單鏈表結(jié)點(diǎn)操作的核心算法2.3鏈表ifself.head.next==None:#循環(huán)鏈表為空

print("Empty!")else:p=q.next#q為p的前驅(qū)

ifp==self.head:#單結(jié)點(diǎn)循環(huán)鏈表

self.head.next=Noneelse:q.next=p.next#含2個以上結(jié)點(diǎn)的循環(huán)鏈表2.3.4雙向鏈表單鏈表的結(jié)點(diǎn)中只有一個指向其后繼結(jié)點(diǎn)的指針域next，若查找結(jié)點(diǎn)的前驅(qū)則只能從該鏈表的頭指針開始，順著各結(jié)點(diǎn)的next域進(jìn)行，因此找前驅(qū)的時(shí)間復(fù)雜度是O(n)。如果希望找前驅(qū)的時(shí)間性能達(dá)到O(1)，則每個結(jié)點(diǎn)再增加一個指向前驅(qū)的指針域，結(jié)點(diǎn)的結(jié)構(gòu)變成圖2.18的結(jié)構(gòu)，用這種結(jié)點(diǎn)組成的鏈表稱為雙向鏈表，簡稱雙鏈表。2.3鏈表其中，data域叫數(shù)據(jù)域，與線性表的數(shù)據(jù)元素值對應(yīng)，prior和next部分為指針域，用于存放指向前驅(qū)和后繼元素的指針。2.3鏈表雙向鏈表的運(yùn)算（1）類型說明定義2.3雙向鏈表中的結(jié)點(diǎn)定義2.3鏈表classDoubleLinkedNode(object):def__init__(self,data):#初始化結(jié)點(diǎn)

self.data=data#數(shù)據(jù)域

self.next=None#后繼指針

self.prior=None#前驅(qū)指針（2）創(chuàng)建雙鏈表算法2.18創(chuàng)建雙鏈表算法2.3鏈表defCreateDoubleLinkedList(self):print("請輸入數(shù)據(jù)后按回車鍵確認(rèn)，若想結(jié)束輸入請

按“#”。")data=input("請輸入元素：")q=self.head

（2）創(chuàng)建雙鏈表算法2.18創(chuàng)建雙鏈表算法2.3鏈表defCreateDoubleLinkedList(self):#上述程序續(xù)whiledata!='#':p=DoubleLinkedNode(int(data))q.next=p;p.prior=qq=q.next;data=input("請輸入元素：")（3）插入算法2.19在雙鏈表中值為x的結(jié)點(diǎn)前插入新結(jié)點(diǎn)2.3鏈表defInsert(self,x):y=input("請輸入元素：")ify=='#’:returns=DoubleLinkedNode(int(y))p=self.head（3）插入算法2.19在雙鏈表中值為x的結(jié)點(diǎn)前插入新結(jié)點(diǎn)2.3鏈表defInsert(self,x):#上述程序續(xù)whilep.data!=xandp.next:t=p;p=p.nexts.prior=p.prior;

p.prior=ss.next=p;t.next=s（4）刪除算法2.20刪除雙鏈表中值為x的結(jié)點(diǎn)2.3鏈表defDelete(self,x):p=q=self.headwhilep.data!=x:q=p;p=p.nextifp:q.next=p.next;

p.next.prior=p.priorreturn1else:print("Nodenotfound!");return-1循環(huán)雙向鏈表循環(huán)雙鏈表是把首尾相接的雙鏈表，帶頭結(jié)點(diǎn)的循環(huán)雙鏈表的一般形態(tài)如圖2.24所示。2.3鏈表第2章線性表

2.1線性表的基本概念 2.2順序表2.3鏈表2.4順序表和鏈表的比較2.5鏈表的應(yīng)用本章介紹了線性表的邏輯結(jié)構(gòu)及它的兩種存儲結(jié)構(gòu)：順序表和鏈表。通過對它們的討論可知它們各有優(yōu)缺點(diǎn)，順序存儲有三個優(yōu)點(diǎn)：①方法簡單，可以用各種高級程序語言中的數(shù)組實(shí)現(xiàn)。②不用為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲開銷。③順序表具有按元素序號可隨機(jī)訪問的特點(diǎn)。2.4順序表和鏈表的比較但它也有一個缺點(diǎn)：在順序表中做插入刪除操作時(shí)，平均移動大約表中一半的元素，因此對n較大的順序表效率低。鏈表的優(yōu)缺點(diǎn)恰好與順序表相反。2.4順序表和鏈表的比較在實(shí)際中怎樣選取存儲結(jié)構(gòu)呢？通常有以下幾點(diǎn)考慮：1．基于存儲空間的考慮在Python中，順序表是用列表（list）來表示的，其存儲空間的大小事先不需要確定。鏈表不用事先估計(jì)存儲規(guī)模，但鏈表的存儲密度小于１2.4順序表和鏈表的比較在實(shí)際中怎樣選取存儲結(jié)構(gòu)呢？通常有以下幾點(diǎn)考慮：2．基于運(yùn)算的考慮在順序表中按序號訪問ai的時(shí)間性能是O(1)，而鏈表中按序號訪問的時(shí)間性能是O(n)，如果經(jīng)常做的運(yùn)算是按序號訪問數(shù)據(jù)元素，顯然順序表優(yōu)于鏈表；而在順序表中做插入、刪除時(shí)平均移動表中一半的元素，當(dāng)數(shù)據(jù)元素?cái)?shù)量很大時(shí)效率較低；在鏈表中作插入、刪除，雖然也要找插入位置，但操作主要是比較操作，從這個角度考慮顯然后者優(yōu)于前者。2.4順序表和鏈表的比較在實(shí)際中怎樣選取存儲結(jié)構(gòu)呢？通常有以下幾點(diǎn)考慮：3．基于環(huán)境的考慮順序表容易實(shí)現(xiàn)，任何高級語言中都有數(shù)組（Python中是列表）類型，鏈表的操作是基于指針的，從操作的角度看前者簡單些。2.4順序表和鏈表的比較在實(shí)際中怎樣選取存儲結(jié)構(gòu)呢？通常有以下幾點(diǎn)考慮：4．基于空間的考慮當(dāng)線性表的長度變化較大，難以估計(jì)其存儲規(guī)模時(shí)，適宜采用鏈表作為存儲結(jié)構(gòu)。反之，當(dāng)線性表的長度變化不大，易于事先確定其大小，為了節(jié)約存儲空間，宜采用順序表作為存儲結(jié)構(gòu)。2.4順序表和鏈表的比較在實(shí)際中怎樣選取存儲結(jié)構(gòu)呢？通常有以下幾點(diǎn)考慮：5．基于時(shí)間的考慮若線性表的操作主要是進(jìn)行查找，很少做插入和刪除操作時(shí)，采用順序表做存儲結(jié)構(gòu)為宜。對于頻繁進(jìn)行插入和刪除的線性表，宜采用鏈表做存儲結(jié)構(gòu)。2.4順序表和鏈表的比較總之，兩種存儲結(jié)構(gòu)各有長短，選擇哪一種由實(shí)際問題中的主要因素決定。通?！拜^穩(wěn)定”的線性表選擇順序存儲，而頻繁做插入刪除的即動態(tài)性較強(qiáng)的線性表宜選擇鏈?zhǔn)酱鎯Α?.4順序表和鏈表的比較第2章線性表

2.1線性表的基本概念 2.2順序表2.3鏈表2.4順序表和鏈表的比較2.5鏈表的應(yīng)用一元多項(xiàng)式(polynomial)P(x)的形式為：

P(x)=a0+a1x+…+an-1xn-1+anxn

稱P(x)為ｎ項(xiàng)多項(xiàng)式,aiｘi是多項(xiàng)式的項(xiàng)（0≤i≤n）,其中ai為系數(shù),ｘ為變數(shù),i為指數(shù),P(x)的階等于多項(xiàng)式中x（系數(shù)不為零）的冪的最大值；例如，多項(xiàng)式：P(x)=5+7x-8x3+4x5是一個5階多項(xiàng)式。2.5鏈表的應(yīng)用一個多項(xiàng)式可以看作一個系數(shù)組成的線性表

（a0,a1,a2,…,an）本節(jié)討論鏈表實(shí)現(xiàn)多項(xiàng)式相加的運(yùn)算。多項(xiàng)式中的每一項(xiàng)有系數(shù)、指數(shù)，要表示多項(xiàng)式中結(jié)點(diǎn)間的邏輯關(guān)系，還需要一個鏈來指向多項(xiàng)式的下一項(xiàng)。這樣，數(shù)據(jù)結(jié)構(gòu)具有如圖2.25所示的形式。2.5鏈表的應(yīng)用coefexpnext圖2.25表示多項(xiàng)式結(jié)點(diǎn)的結(jié)構(gòu)定義2.4多項(xiàng)式中每個結(jié)點(diǎn)的邏輯結(jié)構(gòu)2.5鏈表的應(yīng)用classPoly_Node(object): #多項(xiàng)式中每個結(jié)點(diǎn)def__init__(self,coef,exp):self.coef=coef#每一項(xiàng)的系數(shù)

self.exp=exp#每一項(xiàng)的指數(shù)

self.next=None#指向下一項(xiàng)的指針定義2.5多項(xiàng)式鏈表2.5鏈表的應(yīng)用classPolyLinkList(object):#多項(xiàng)式鏈表類

def__init__(self):#初始化

self.head=Poly_Node(None,None)#創(chuàng)建多項(xiàng)式鏈表函數(shù)詳見后面算法2.23，此處略#算法2.22原地進(jìn)行多項(xiàng)式相加的算法2.5鏈表的應(yīng)用defpoly_add(h1,h2):p=h1.next #p指向A的第一個結(jié)點(diǎn)

q=h2.next #q指向B的第一個結(jié)點(diǎn)

t=h1 #t指向p的前驅(qū)

pc=h1 #pc指向A