數(shù)據(jù)結(jié)構(gòu)Python語言描述 線性表

數(shù)據(jù)結(jié)構(gòu)

Python語言描述第2章線性表2目錄2.1線性表簡介2.2順序表2.3鏈表2.4本章小結(jié)2.5上機(jī)實(shí)驗(yàn)32.1線性表簡介4線性表是由若干個(gè)具有相同特性的數(shù)據(jù)元素組成的有限序列。若該線性表中不包含任何元素，則稱為空表，此時(shí)其長度為零。當(dāng)線性表不為空時(shí)，表中元素的個(gè)數(shù)即為其長度。2.1線性表簡介5可以用以下形式來表示線性表。{a[1],a[2],…,a[i],…,a[n]}其中a[i]表示線性表中的任意一個(gè)元素，n表示元素的個(gè)數(shù)。表中a[1]為第一個(gè)元素，a[2]為第二個(gè)元素，依次類推，a[n]為表中的最后一個(gè)元素。由于元素a[1]領(lǐng)先于a[2]，因此我們稱a[1]是a[2]的直接先驅(qū)元素，a[2]是a[1]的直接后繼元素。我們把線性表中的第一個(gè)元素a[1]稱為表頭，最后一個(gè)元素a[n]稱為表尾，在線性表中，有且僅有一個(gè)表頭元素和一個(gè)表尾元素。通常表頭元素沒有直接先驅(qū)元素，表尾元素沒有直接后繼元素。2.1線性表簡介6一種典型的線性表的邏輯結(jié)構(gòu)。2.1線性表簡介7線性表中的元素之間也可以存在某種關(guān)系。如數(shù)字1～20里所有奇數(shù)的排列，可用如下線性表的形式來表示。{1,3,5,7,9,11,13,15,17,19}此時(shí)，表內(nèi)元素的值是按照遞增順序來排列的，通常我們稱這種類型的線性表為有序線性表（簡稱有序表），即該表中元素按某種順序進(jìn)行排列。從嚴(yán)格意義上來講，僅當(dāng)線性表中所有元素以遞增或遞減的順序排列（允許表中存在相同的元素），我們才稱其為有序表；否則，我們均稱其為無序表，元素之間既無遞增也無遞減關(guān)系，示例如下。{1,13,5,74,9,11,13,15,17,195}2.1線性表簡介8線性表有以下特性。（1）線性表中的元素個(gè)數(shù)一定是有限的。（2）線性表中的所有元素具有相同的性質(zhì)。（3）線性表中除表頭元素以外，其他所有元素都有唯一的（直接）先驅(qū)元素。（4）線性表中除表尾元素以外，其他所有元素都有唯一的（直接）后繼元素。線性表的抽象數(shù)據(jù)類型的定義參見教材p20表2-1。2.2順序表2.2.1順序表的概念2.2.2順序表的操作2.2.3順序表的應(yīng)用92.2.1順序表的概念10順序表是指采用順序存儲(chǔ)的方式來存儲(chǔ)數(shù)據(jù)元素的線性表。在順序表中，我們通常將結(jié)點(diǎn)依次存放在一組地址連續(xù)的存儲(chǔ)空間中，由于待存儲(chǔ)空間連續(xù)且每個(gè)數(shù)據(jù)元素占用的空間相同，因此可以綜合上述信息并通過計(jì)算得出每個(gè)元素的存儲(chǔ)位置。2.2.2順序表的操作11創(chuàng)建文件ex020202.py。在該文件中我們定義了一個(gè)用于順序表基本操作的SequenceList類。序號(hào)名稱注釋1__init__(self)初始化線性表（構(gòu)造函數(shù)）2CreateSequenceList(self)創(chuàng)建順序表3DestorySequenceList(self)銷毀順序表4IsEmpty(self)判斷順序表是否為空5GetElement(self)獲取表中指定位置的元素值6FindElement(self)在表中查找某一指定元素7GetExtremum(self)獲取表中最大值或最小值8InsertElement(self)在表中指定位置插入某一元素9AppendElement(self)在表末尾插入某一元素10SortSequenceList(self)對表進(jìn)行排序11DeleteElement(self)刪除表中某一元素12VisitElement(self)訪問表中某一元素13TraverseElement(self)遍歷表中所有元素12順序表基本操作122.2.2順序表的操作13我們將具體實(shí)現(xiàn)__init__(self)CreateSequenceList(self)FindElement(self)InsertElement(self)DeleteElement(self)TraverseElement(self)這6個(gè)方法。讀者可根據(jù)自己的需要，自行實(shí)現(xiàn)其余方法。2.2.2順序表的操作14我們首先調(diào)用SequenceList類的構(gòu)造函數(shù)__init__(self)初始化一個(gè)空的順序表，其算法思路如下。（1）創(chuàng)建一個(gè)順序表。（2）對該順序表進(jìn)行初始化。該算法思路對應(yīng)的算法步驟如下。（1）創(chuàng)建一個(gè)順序表self.SeqList。（2）將順序表self.SeqList置空。14151#####################################2#初始化順序表函數(shù)3#####################################4def__init__(self):5self.SeqList=[]算法2-1初始化順序表函數(shù)2.2.2順序表的操作16CreateSequenceList(self)的算法思路如下。（1）輸入數(shù)據(jù)元素并存入順序表中。（2）結(jié)束數(shù)據(jù)元素的輸入。（3）成功創(chuàng)建順序表。該算法思路對應(yīng)的算法步驟如下。（1）調(diào)用input()方法接收用戶的輸入。（2）若用戶的輸入不為“#”，則調(diào)用append()方法將其添加至線性表中并轉(zhuǎn)（3）。（3）重復(fù)步驟（1）。（4）若用戶的輸入為“#”，則結(jié)束當(dāng)前輸入并完成線性表的創(chuàng)建。16171#####################################2#創(chuàng)建順序表函數(shù)3#####################################4defCreateSequenceList(self):5print("*************************************************")6print("*請輸入數(shù)據(jù)后按回車鍵確認(rèn)，若想結(jié)束請輸入“#”。*")7print("*************************************************")8Element=input("請輸入元素：")9whileElement!='#':10self.SeqList.append(int(Element))11Element=input("請輸入元素：")算法2-2創(chuàng)建順序表函數(shù)2.2.2順序表的操作18通過執(zhí)行上述代碼，我們創(chuàng)建了一個(gè)新的順序表SeqList，表內(nèi)數(shù)據(jù)元素為{‘1001’,‘365’,‘30’,‘11’,‘23’,‘24’,‘3’,‘9’,‘35’}在之后的基本操作中，我們都會(huì)基于該順序表進(jìn)行。182.2.2順序表的操作19FindElement(self,SeqList)的算法思路如下。（1）輸入待查找的元素值。（2）若需查找的元素值存在于順序表中，則輸出其值及所在位置。（3）若需查找的元素不在順序表中，則輸出相應(yīng)提示。該算法思路對應(yīng)的算法步驟如下。（1）調(diào)用input()方法接收用戶輸入的待查找的元素值key，并將其轉(zhuǎn)化為int型。（2）判斷用戶輸入的元素值key是否存在于順序表SeqList中，若結(jié)果為真則轉(zhuǎn)（3），否則轉(zhuǎn)（4）。（3）輸出該元素值及其所在位置。（4）輸出查找失敗的提示。19201#####################################2#查找元素值函數(shù)3#####################################4defFindElement(self):5key=int(input('請輸入想要查找的元素值：'))6ifkeyinself.SeqList:7ipos=self.SeqList.index(key)8print("查找成功！值為",self.SeqList[ipos],"的元素，位于當(dāng)前順序表的第",ipos+1,"個(gè)位置。")9else:10print("查找失??！當(dāng)前順序表中不存在值為",key,"的元素")算法2-3查找元素值函數(shù)2.2.2順序表的操作21InsertElement(self,SeqList)的算法思路如下。（1）輸入待插入元素的目標(biāo)位置。（2）輸入待插入的元素值。（3）輸出成功插入元素后的順序表。該算法思路對應(yīng)的算法步驟如下。（1）調(diào)用input()方法接收用戶需要插入元素的目標(biāo)位置iPos。（2）調(diào)用input()方法接收用戶需要插入元素的值Element。（3）調(diào)用insert()方法將值為Element的元素插入指定位置iPos處。（4）調(diào)用print()方法將插入元素Element后的順序表輸出。21221#####################################2#指定位置插入元素函數(shù)3#####################################4defInsertElement(self):5iPos=int(input('請輸入待插入元素的位置：'))6Element=int(input('請輸入待插入的元素值：'))7self.SeqList.insert(iPos,Element)8print("插入元素后，當(dāng)前順序表為：\n",self.SeqList)算法2-4指定位置插入元素函數(shù)23假定我們在之前創(chuàng)建的順序表SeqList中，將元素‘66’插入至表中第4個(gè)位置（其下標(biāo)位置為3），通過執(zhí)行上述代碼，原本含有9個(gè)元素的順序表SeqList{‘1001’,‘365’,‘30’,‘11’,‘23’,‘24’,‘3’,‘9’,‘35’}變?yōu)楹?0個(gè)元素的順序表SeqList{‘1001’,‘365’,‘30’,‘66’,‘11’,‘23’,‘24’,‘3’,‘9’,‘35’}2.2.2順序表的操作24252.2.2順序表的操作26DeleteElement(self,SeqList)的算法思路如下。（1）輸入待刪除元素的下標(biāo)位置。（2）刪除指定元素。（3）輸出刪除元素后的順序表。該算法思路對應(yīng)的算法步驟如下。（1）調(diào)用input()方法接收用戶需要?jiǎng)h除元素的目標(biāo)位置dPos。（2）調(diào)用remove()方法將下標(biāo)位置為dPos的元素刪除。（3）調(diào)用print()方法輸出刪除元素后的順序表。26271#####################################2#指定位置刪除元素函數(shù)3#####################################4defDeleteElement(self):5dPos=int(input('請輸入待刪除元素的位置：'))6print("正在刪除元素",self.SeqList[dPos],"...")7self.SeqList.remove(self.SeqList[dPos])8print("刪除后順序表為：\n",self.SeqList)算法2-5指定位置刪除元素函數(shù)28假定我們在之前創(chuàng)建的順序表SeqList中刪除下標(biāo)位置為3的元素‘66’，在執(zhí)行刪除操作后，原順序表SeqList中元素‘11’及其之后的5個(gè)元素均向前移動(dòng)了一個(gè)位置。29我們還可以通過將元素‘30’及其之前的兩個(gè)元素向后移動(dòng)一個(gè)位置，實(shí)現(xiàn)刪除元素‘66’這一操作。2.2.2順序表的操作30TraverseElement(self)的算法思路如下。（1）得到順序表的長度。（2）逐一輸出該順序表中的元素值。該算法思路對應(yīng)的算法步驟如下。（1）調(diào)用len()函數(shù)得到當(dāng)前順序表SeqList的長度SeqListLen。（2）使用變量i來指示當(dāng)前元素的下標(biāo)位置。（3）從變量i=0開始到i=SeqListLen-1為止，執(zhí)行（4）。（4）調(diào)用print()方法輸出下標(biāo)位置為i的元素值。（5）結(jié)束輸出。30311#####################################2#遍歷順序表元素函數(shù)3#####################################4defTraverseElement(self):5SeqListLen=len(self.SeqList)6print("******遍歷順序表中元素******")7foriinrange(0,SeqListLen):8print("第",i+1,"個(gè)元素的值為",self.SeqList[i])算法2-6遍歷順序表元素函數(shù)32【例2-1】表2-3為軟件學(xué)院15級(jí)軟件工程1班部分學(xué)生2017—2018年度英語期末考試成績，該表包括序號(hào)、姓名和分?jǐn)?shù)3個(gè)字段。請結(jié)合順序表的操作將分?jǐn)?shù)存入順序表中，并求出最高分與最低分。2.2.3順序表的應(yīng)用序號(hào)姓名分?jǐn)?shù)1趙小一562錢小二293孫小三694李小四955周小五926吳小六627鄭小七708王小八509馮小九8010陳小十7733分析：本例實(shí)質(zhì)就是獲取表中成績的最大值與最小值。根據(jù)題目要求，需結(jié)合順序表的操作來求解，因此我們必須先創(chuàng)建一個(gè)順序表，然后將上述成績逐一輸入至順序表中，最后求出該順序表的最大值與最小值并將兩者的值輸出。基于上述分析，我們可將算法思路歸納如下。（1）創(chuàng)建一個(gè)順序表，將表2-3中學(xué)生的分?jǐn)?shù)依次輸入至順序表中。2.2.3順序表的應(yīng)用34（2）通過對順序表執(zhí)行相關(guān)操作，求出最大值和最小值。（3）輸出最大值和最小值，即為最高分和最低分。該算法思路對應(yīng)的算法步驟如下。（1）調(diào)用SequenceList類的成員函數(shù)CreateSequenceList(self)將表2-3中的分?jǐn)?shù)依次輸入至順序表L中（具體代碼實(shí)現(xiàn)可參考算法2-1與算法2-2）。（2）調(diào)用SequenceList類的成員函數(shù)GetExtremum(self)獲取順序表中的最大值和最小值。（3）輸出最大值和最小值。2.2.3順序表的應(yīng)用351#####################################2#算法2-7求順序表最值函數(shù)3#####################################4defGetExtremum(self):5whileTrue:6print("*********************")7print("*1:查詢最大值")8print("*2:查詢最小值")9print("*3:查詢最大值和最小值")10print("*0:退出程序")11print("*********************")12i=int(input("請輸入:"))13ifi==1:14print("順序表中最大值為：",max(self.SeqList))15elifi==2:16print("順序表中最小值為：",min(self.SeqList))17elifi==3:18print("順序表中最大值為：",max(self.SeqList))19print("順序表中最小值為：",min(self.SeqList))20elifi==0:21break36算法2-8創(chuàng)建順序表并計(jì)算最值1L=SequenceList()2L.CreateSequenceList()3L.GetExtremum()此時(shí)，我們可以看到軟件學(xué)院15級(jí)軟件工程1班部分學(xué)生2017—2018年度英語期末考試成績中，最高分為95分，最低分為29分。2.3鏈表2.3.1鏈表的基本概念2.3.2單鏈表2.3.3循環(huán)單鏈表2.3.4雙鏈表2.3.5循環(huán)雙鏈表2.3.6鏈表的應(yīng)用37382.3.1鏈表的基本概念鏈表是指采用鏈?zhǔn)浇Y(jié)構(gòu)來存儲(chǔ)數(shù)據(jù)元素的線性表，它與順序表最大的區(qū)別在于兩者的存儲(chǔ)結(jié)構(gòu)不同。順序表需要由系統(tǒng)提前分配一組連續(xù)的存儲(chǔ)空間，并采用順序存儲(chǔ)的方式來存儲(chǔ)數(shù)據(jù)元素；而鏈表是在每個(gè)結(jié)點(diǎn)創(chuàng)建時(shí)主動(dòng)向系統(tǒng)申請相應(yīng)的存儲(chǔ)空間，并通過指針來鏈接各個(gè)包含數(shù)據(jù)元素的結(jié)點(diǎn)。即鏈表中元素的邏輯順序是由指針的鏈接次序決定的，與存儲(chǔ)空間的物理位置無關(guān)，因此在使用時(shí)僅能被順序存取；而順序表中元素的邏輯順序與其物理位置直接相關(guān)，因此可實(shí)現(xiàn)隨機(jī)存取。除此之外，與順序表相比，鏈表還有以下特點(diǎn)。（1）鏈表實(shí)現(xiàn)了存儲(chǔ)空間的動(dòng)態(tài)管理。（2）鏈表在執(zhí)行插入與刪除操作時(shí)，不必移動(dòng)其余元素，只需修改指針即可。392.3.1鏈表的基本概念我們使用存儲(chǔ)密度這一指標(biāo)來衡量數(shù)據(jù)存儲(chǔ)時(shí)其對應(yīng)存儲(chǔ)空間的使用效率。它是指結(jié)點(diǎn)中數(shù)據(jù)元素本身所占的存儲(chǔ)量和整個(gè)結(jié)點(diǎn)所占用的存儲(chǔ)量之比，即:存儲(chǔ)密度=結(jié)點(diǎn)中數(shù)據(jù)元素所占的存儲(chǔ)量/結(jié)點(diǎn)所占的存儲(chǔ)量因此我們可以知道順序表的存儲(chǔ)密度為1，而鏈表的存儲(chǔ)密度小于1。所以在理想情況下，順序表的存儲(chǔ)密度會(huì)大于鏈表，其相應(yīng)的存儲(chǔ)空間利用率也就更高。402.3.1鏈表的基本概念鏈表是由一系列結(jié)點(diǎn)通過指針鏈接而形成的，每個(gè)結(jié)點(diǎn)可分為數(shù)據(jù)域和指針域兩個(gè)部分，數(shù)據(jù)域可用于存儲(chǔ)數(shù)據(jù)元素，指針域可用于存儲(chǔ)下一結(jié)點(diǎn)的地址。每個(gè)數(shù)據(jù)元素a[i]與其直接后繼元素a[i+1]的邏輯順序是通過使用結(jié)點(diǎn)的指針來指明的，其中，數(shù)據(jù)元素a[i]所在的結(jié)點(diǎn)為數(shù)據(jù)元素a[i+1]所在的結(jié)點(diǎn)的直接先驅(qū)結(jié)點(diǎn)，反之，數(shù)據(jù)元素a[i+1]所在的結(jié)點(diǎn)為數(shù)據(jù)元素a[i]所在的結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)。412.3.1鏈表的基本概念假定一個(gè)線性表A為{‘Ren’,‘Zhi’,‘Chu’,‘Xing’,‘Ben’,‘Shan’}當(dāng)我們將此線性表中的元素用鏈?zhǔn)浇Y(jié)構(gòu)來存儲(chǔ)時(shí)，其對應(yīng)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)如圖所示。42我們該如何通過指針，對上述元素按表中順序進(jìn)行存儲(chǔ)呢？首先假定一個(gè)頭指針H，它被用來指向鏈表中第一個(gè)結(jié)點(diǎn)，接著在第一個(gè)結(jié)點(diǎn)的指針域中存入第二個(gè)結(jié)點(diǎn)所在的存儲(chǔ)地址，依次類推，直至最后一個(gè)元素。由于最后一個(gè)元素沒有直接后繼，因此其指針域中的值為None。2.3.1鏈表的基本概念43鏈表可分為單向鏈表、雙向鏈表及循環(huán)鏈表。（1）在單向鏈表中，每個(gè)結(jié)點(diǎn)只包含一個(gè)指針域，它用來指向其直接后繼結(jié)點(diǎn)，通常我們將這種單向鏈表簡稱為單鏈表。2.3.1鏈表的基本概念44（2）在雙向鏈表中，每個(gè)結(jié)點(diǎn)包含兩個(gè)指針域，其中一個(gè)用于指向先驅(qū)結(jié)點(diǎn)，可稱之為先驅(qū)指針；另一個(gè)用于指向后繼結(jié)點(diǎn)，可稱之為后繼指針。通常我們將這樣的雙向鏈表簡稱為雙鏈表。2.3.1鏈表的基本概念45（3）循環(huán)鏈表的特點(diǎn)之一就是從表中任一結(jié)點(diǎn)出發(fā)，均可找到表中其他結(jié)點(diǎn)。接下來我們介紹兩種最為常用的循環(huán)鏈表——循環(huán)單鏈表和循環(huán)雙鏈表。2.3.1鏈表的基本概念46通過上一節(jié)的學(xué)習(xí)我們知道，單鏈表可由頭指針唯一確定。它用于指向表中第一個(gè)結(jié)點(diǎn)，若其為空，則表示該單鏈表的長度為0；否則我們需通過循環(huán)的方式來訪問結(jié)點(diǎn)的指針域，從而計(jì)算出單鏈表的長度。通過使用頭指針，我們還可對單鏈表執(zhí)行其他操作。有時(shí)我們會(huì)在單鏈表的第一個(gè)結(jié)點(diǎn)前增加一個(gè)結(jié)點(diǎn)，其數(shù)據(jù)域默認(rèn)為空，也可用于存儲(chǔ)單鏈表長度之類的數(shù)據(jù)；而指針域則被用于存儲(chǔ)第一個(gè)結(jié)點(diǎn)的地址。我們把這種類型的結(jié)點(diǎn)稱為頭結(jié)點(diǎn)，并把含有這種頭結(jié)點(diǎn)的單鏈表稱為帶頭結(jié)點(diǎn)的單鏈表；反之則稱為不帶頭結(jié)點(diǎn)的單鏈表。和不帶頭結(jié)點(diǎn)的單鏈表相比，帶頭結(jié)點(diǎn)的單鏈表不僅統(tǒng)一了第一個(gè)結(jié)點(diǎn)及其后繼結(jié)點(diǎn)的處理過程，還統(tǒng)一了空表和非空表的處理過程。因此在后續(xù)內(nèi)容的介紹中，若無特別聲明，我們所說的單鏈表均指帶頭結(jié)點(diǎn)的單鏈表。2.3.2單鏈表47我們可按如下步驟來實(shí)現(xiàn)帶頭結(jié)點(diǎn)的單鏈表的基本操作。第1步，創(chuàng)建文件ex020302.py。在該文件中我們首先定義一個(gè)Node類，該類包含創(chuàng)建結(jié)點(diǎn)并對結(jié)點(diǎn)進(jìn)行初始化的操作。第2步，定義一個(gè)SingleLinkedList類，用于創(chuàng)建一個(gè)單鏈表，并對其執(zhí)行相關(guān)操作(參見教材p38)。我們將具體實(shí)現(xiàn)Node類中的__init__()方法，以及SingleLinkedList類中的__init__(self)、CreateSingleLinkedList(self)、InsertElementInTail(self)、InsertElementInHead(self)、FindElement(self)、DeleteElement(self)和TraverseElement(self)這幾個(gè)方法。其余方法讀者可根據(jù)自己的需要來實(shí)現(xiàn)。2.3.2單鏈表48調(diào)用Node類的成員函數(shù)__init__(self,data)初始化一個(gè)結(jié)點(diǎn)，其算法思路如下。（1）創(chuàng)建一個(gè)數(shù)據(jù)域，用于存儲(chǔ)每個(gè)結(jié)點(diǎn)的值。（2）創(chuàng)建一個(gè)指針域，用于存儲(chǔ)下一個(gè)結(jié)點(diǎn)的地址。（3）還可以根據(jù)實(shí)際需要?jiǎng)?chuàng)建其他域，用于存儲(chǔ)結(jié)點(diǎn)的各種信息。該算法思路對應(yīng)的算法步驟如下。（1）創(chuàng)建數(shù)據(jù)域并將其初始化為data。（2）創(chuàng)建指針域并將其初始化為空。2.3.2單鏈表491#####################################2#初始化結(jié)點(diǎn)函數(shù)3#####################################4def__init__(self,data):5self.data=data6self.next=None算法2-9初始化結(jié)點(diǎn)函數(shù)50SingleLinkedList類的成員函數(shù)__init__(self)用于初始化頭結(jié)點(diǎn)，其算法思路如下。（1）創(chuàng)建單鏈表的頭結(jié)點(diǎn)。（2）將其初始化為空。該算法思路對應(yīng)的算法步驟如下。（1）創(chuàng)建一個(gè)結(jié)點(diǎn)并將其初始化為空。（2）令單鏈表的頭結(jié)點(diǎn)為上述結(jié)點(diǎn)。2.3.2單鏈表511#####################################2#初始化頭結(jié)點(diǎn)函數(shù)3#####################################4def__init__(self):5self.head=Node(None)算法2-10初始化頭結(jié)點(diǎn)函數(shù)52SingleLinkedList類的成員函數(shù)CreateSingleLinkedList(self)用于創(chuàng)建一個(gè)單鏈表，其算法思路如下。（1）獲取頭結(jié)點(diǎn)。（2）由用戶輸入每個(gè)結(jié)點(diǎn)的值，并依次創(chuàng)建這些結(jié)點(diǎn)。（3）每創(chuàng)建一個(gè)結(jié)點(diǎn)，就將其鏈入單鏈表的尾部。（4）若用戶輸入“#”號(hào)，轉(zhuǎn)（5）；否則轉(zhuǎn)（2）。（5）完成單鏈表的創(chuàng)建。2.3.2單鏈表53該算法思路對應(yīng)的算法步驟如下。（1）使用變量cNode指向頭結(jié)點(diǎn)。（2）調(diào)用input()方法接收用戶的輸入。（3）判斷用戶的輸入是否為“#”，若結(jié)果為真，則轉(zhuǎn)（7）；否則轉(zhuǎn)（4）。（4）將用戶輸入的值作為參數(shù)去創(chuàng)建并初始化一個(gè)新結(jié)點(diǎn)。（5）在cNode的next域中存入新結(jié)點(diǎn)的地址。（6）將cNode指向cNode的后繼結(jié)點(diǎn)，并轉(zhuǎn)（2）。（7）結(jié)束當(dāng)前輸入，完成單鏈表的創(chuàng)建。2.3.2單鏈表541#####################################2#創(chuàng)建單鏈表函數(shù)3#####################################4defCreateSingleLinkedList(self):5print("*************************************************")6print("*請輸入數(shù)據(jù)后按回車鍵確認(rèn)，若想結(jié)束請輸入“#”。*")7print("*************************************************")8cNode=self.head9Element=input("請輸入當(dāng)前結(jié)點(diǎn)的值：")10whileElement!="#":11nNode=Node(int(Element))12cNode.next=nNode13cNode=cNode.next14Element=input("請輸入當(dāng)前結(jié)點(diǎn)的值：")算法2-11創(chuàng)建單鏈表函數(shù)55通過執(zhí)行上述代碼，我們可以創(chuàng)建一個(gè)新的單鏈表。2.3.2單鏈表56SingleLinkedList類的成員函數(shù)InsertElementInTail(self)，向已有單鏈表的尾端插入結(jié)點(diǎn)，其算法思路如下。（1）輸入待插入結(jié)點(diǎn)的值。（2）創(chuàng)建數(shù)據(jù)域?yàn)樵撝档慕Y(jié)點(diǎn)。（3）在當(dāng)前單鏈表的尾端插入該結(jié)點(diǎn)。2.3.2單鏈表57該算法思路對應(yīng)的算法步驟如下。（1）調(diào)用input()方法接收用戶輸入，并將其存入變量Element中。（2）判斷Element是否為“#”，若結(jié)果為真，則轉(zhuǎn)（8）；否則轉(zhuǎn)（3）。（3）使用變量cNode指向單鏈表的頭結(jié)點(diǎn)。（4）將Element轉(zhuǎn)化為整型數(shù)，然后將其作為參數(shù)去創(chuàng)建并初始化一個(gè)新結(jié)點(diǎn)。（5）判斷cNode的next是否為空，若為空則轉(zhuǎn)（7），否則轉(zhuǎn)（6）。（6）將cNode指向其后繼結(jié)點(diǎn)，轉(zhuǎn)（5）。（7）將nNode的地址存入cNode的指針域中，完成該結(jié)點(diǎn)在單鏈表尾端的插入。（8）結(jié)束本程序。2.3.2單鏈表581#####################################2#尾端插入元素函數(shù)3#####################################4defInsertElementInTail(self):5Element=(input("請輸入待插入結(jié)點(diǎn)的值："))6ifElement=="#":7return8cNode=self.head9nNode=Node(int(Element))10whilecNode.next!=None:11cNode=cNode.next12cNode.next=nNode算法2-12尾端插入元素函數(shù)59假定我們在之前創(chuàng)建的單鏈表SLList中，將值為18的結(jié)點(diǎn)插入至表中最后一個(gè)位置，通過執(zhí)行上述代碼，原本含有5個(gè)結(jié)點(diǎn)的單鏈表SLList，變?yōu)楹?個(gè)結(jié)點(diǎn)的單鏈表SLList。2.3.2單鏈表一般情況下，我們將這種直接在鏈表尾端插入結(jié)點(diǎn)的方法稱為尾插法。60SingleLinkedList類的成員函數(shù)InsertElementInHead(self)，向已有單鏈表的首端插入結(jié)點(diǎn)，其算法思路如下。（1）輸入待插入結(jié)點(diǎn)的值。（2）創(chuàng)建數(shù)據(jù)域?yàn)樵撝档慕Y(jié)點(diǎn)。（3）在當(dāng)前單鏈表的首端插入該結(jié)點(diǎn)。2.3.2單鏈表61該算法思路對應(yīng)的算法步驟如下。（1）調(diào)用input()方法接收用戶輸入，并將其存入變量Element中。（2）判斷Element是否為“#”，若結(jié)果為真，則轉(zhuǎn)（7）；否則轉(zhuǎn)（3）。（3）使用變量cNode指向當(dāng)前單鏈表的頭結(jié)點(diǎn)。（4）將Element轉(zhuǎn)化為整型數(shù)，然后將其作為參數(shù)去創(chuàng)建并初始化一個(gè)新結(jié)點(diǎn)。（5）將新結(jié)點(diǎn)的next指向cNode的后繼結(jié)點(diǎn)，轉(zhuǎn)（6）。（6）將nNode的地址存入結(jié)點(diǎn)cNode的指針域中，完成該結(jié)點(diǎn)在單鏈表首端的插入。（7）結(jié)束本程序。2.3.2單鏈表621#####################################2#首端插入元素函數(shù)3#####################################4defInsertElementInHead(self):5Element=input("請輸入待插入結(jié)點(diǎn)的值：")6ifElement=="#":7return8cNode=self.head9nNode=Node(int(Element))10nNode.next=cNode.next11cNode.next=nNode算法2-13首端插入元素函數(shù)63假定我們在之前創(chuàng)建的單鏈表SLList中，將值為88的結(jié)點(diǎn)插入至表中第一個(gè)位置，通過執(zhí)行上述代碼，原本含有6個(gè)結(jié)點(diǎn)的單鏈表SLList，變?yōu)楹?個(gè)結(jié)點(diǎn)的單鏈表SLList。2.3.2單鏈表一般情況下，我們將這樣直接在鏈表首端插入結(jié)點(diǎn)的方法稱為頭插法。64SingleLinkedList類的成員函數(shù)FindElement(self)(self)，在單鏈表中查找含有某一指定元素的結(jié)點(diǎn)，其算法思路如下。（1）輸入待查找的元素值。（2）若在單鏈表中存在包含目標(biāo)元素的結(jié)點(diǎn)，則輸出第一個(gè)被找到的結(jié)點(diǎn)的值及其所在位置。（3）若在單鏈表中不存在包含目標(biāo)元素的結(jié)點(diǎn)，則輸出相應(yīng)提示。2.3.2單鏈表65該算法思路對應(yīng)的算法步驟如下。（1）使用變量Pos指示當(dāng)前下標(biāo)位置。（2）使用變量cNode指向單鏈表SLList的頭結(jié)點(diǎn)。（3）調(diào)用input()方法接收用戶的輸入，存入變量key中，并將其轉(zhuǎn)化為整型數(shù)。（4）判斷當(dāng)前鏈表是否為空，若為空則轉(zhuǎn)（5），否則轉(zhuǎn)（6）。（5）調(diào)用print()方法輸出當(dāng)前單鏈表為空的提示并返回。（6）當(dāng)cNode的next不為空且cNode所指結(jié)點(diǎn)的值不等于key時(shí)，執(zhí)行（7），否則執(zhí)行（8）。（7）將cNode指向當(dāng)前結(jié)點(diǎn)的后繼結(jié)點(diǎn)并將Pos加1，轉(zhuǎn)（6）。（8）判斷當(dāng)前cNode所指結(jié)點(diǎn)的值是否等于key，若為真，則轉(zhuǎn)（9）；否則轉(zhuǎn)（10）。（9）調(diào)用print()方法輸出值key及其所在位置。（10）調(diào)用print()方法輸出查找失敗的提示。2.3.2單鏈表661#####################################2#查找指定元素并返回其位置函數(shù)3#####################################4defFindElement(self):5Pos=06cNode=self.head7key=int(input('請輸入想要查找的元素值：'))8ifself.IsEmpty():9print("當(dāng)前單鏈表為空！")10return11whilecNode.next!=NoneandcNode.data!=key:12cNode=cNode.next13Pos=Pos+114ifcNode.data==key:15print("查找成功，值為",key,"的結(jié)點(diǎn)位于該單鏈表的第",Pos,"個(gè)位置。")16else:17print("查找失??！當(dāng)前單鏈表中不存在值為",key,"的元素")算法2-14查找指定元素并返回其位置函數(shù)671#####################################2#判斷單鏈表是否為空函數(shù)3#####################################4defIsEmpty(self):5ifself.GetLength()==0:6returnTrue7else:8returnFalse算法2-15判斷單鏈表是否為空函數(shù)681#####################################2#獲取單鏈表長度函數(shù)3#####################################4defGetLength(self):5cNode=self.head6length=07whilecNode.next!=None:8length=length+19cNode=cNode.next10returnlength算法2-16獲取單鏈表長度函數(shù)69SingleLinkedList類的成員函數(shù)DeleteElement(self)，可將已有單鏈表中包含指定元素的結(jié)點(diǎn)刪除，其算法思路如下。（1）輸入待刪除結(jié)點(diǎn)的值。（2）在單鏈表中，查找與該值相等的結(jié)點(diǎn)。（3）若查找成功，則執(zhí)行刪除操作。（4）若查找失敗，則輸出相應(yīng)提示。2.3.2單鏈表70該算法思路對應(yīng)的算法步驟如下。（1）調(diào)用input()方法接收用戶待刪除結(jié)點(diǎn)的值dElement。（2）使用變量cNode、pNode指向單鏈表SLList的頭結(jié)點(diǎn)。（3）判斷當(dāng)前鏈表是否為空，若為空則轉(zhuǎn)（4），否則轉(zhuǎn)（5）。（4）調(diào)用print()方法輸出當(dāng)前單鏈表為空的提示并返回。（5）當(dāng)cNode所指結(jié)點(diǎn)的指針域不為空且cNode所指結(jié)點(diǎn)的值不等于dElement時(shí)，執(zhí)行（6），否則執(zhí)行（7）。（6）令pNode等于cNode，再將cNode指向其后繼結(jié)點(diǎn)并轉(zhuǎn)（5）。（7）判斷cNode所指結(jié)點(diǎn)的值是否等于dElement，若為真，則轉(zhuǎn)（8）；否則轉(zhuǎn)（9）。（8）將pNode的next指向cNode所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)，然后刪除cNode所指結(jié)點(diǎn)，再調(diào)用print()方法輸出相應(yīng)提示。（9）調(diào)用print()方法輸出刪除失敗的提示。2.3.2單鏈表711#####################################2#刪除元素函數(shù)3#####################################4defDeleteElement(self):5dElement=int(input('請輸入待刪除結(jié)點(diǎn)的值：'))6cNode=self.head7pNode=self.head8ifself.IsEmpty():9print("當(dāng)前單鏈表為空！")10return11whilecNode.next!=NoneandcNode.data!=dElement:12pNode=cNode13cNode=cNode.next14ifcNode.data==dElement:15pNode.next=cNode.next16delcNode17print("成功刪除含有元素",dElement,"的結(jié)點(diǎn)")18else:19print("刪除失??！當(dāng)前單鏈表中不存在含有元素",dElement,"的結(jié)點(diǎn)")算法2-17刪除元素函數(shù)72假定我們在之前創(chuàng)建的單鏈表SLList中刪除值為57的結(jié)點(diǎn)，通過執(zhí)行算法2-17使得原本含有7個(gè)結(jié)點(diǎn)的單鏈表，變?yōu)楹?個(gè)結(jié)點(diǎn)的單鏈表。為了將值為57的結(jié)點(diǎn)成功刪除，我們首先需要將值為57的結(jié)點(diǎn)的先驅(qū)結(jié)點(diǎn)內(nèi)的指針指向值為57的結(jié)點(diǎn)的后繼結(jié)點(diǎn)，進(jìn)而再對值為57的結(jié)點(diǎn)執(zhí)行刪除操作，具體過程如圖所示。73SingleLinkedList類的成員函數(shù)TraverseElement(self)，用于遍歷單鏈表中的元素，其算法思路如下。（1）若頭結(jié)點(diǎn)的指針域?yàn)榭?，則輸出相應(yīng)提示。（2）若頭結(jié)點(diǎn)的指針域不為空，則調(diào)用VisitElement(self,tNode)方法將當(dāng)前單鏈表中的元素逐一輸出。2.3.2單鏈表74該算法思路對應(yīng)的算法步驟如下。（1）使用變量cNode指向單鏈表SLList的頭結(jié)點(diǎn)。（2）判斷當(dāng)前鏈表是否為空，若為空，則轉(zhuǎn)（3），否則轉(zhuǎn)（4）。（3）調(diào)用print()方法輸出當(dāng)前單鏈表為空的提示并返回。（4）當(dāng)cNode不為空時(shí)，執(zhí)行（5），否則執(zhí)行（6）。（5）將cNode指向其后繼結(jié)點(diǎn)，并調(diào)用VisitElement()方法輸出cNode所指結(jié)點(diǎn)的值，轉(zhuǎn)（4）。（6）退出程序。2.3.2單鏈表751#####################################2#遍歷單鏈表函數(shù)3#####################################4defTraverseElement(self):5cNode=self.head6ifcNode.next==None:7print("當(dāng)前單鏈表為空！")8return9print("您當(dāng)前的單鏈表為：")10whilecNode!=None:11cNode=cNode.next12self.VisitElement(cNode)算法2-18遍歷單鏈表函數(shù)761#####################################2#輸出單鏈表某一元素函數(shù)3#####################################4defVisitElement(self,tNode):5iftNode!=None:6print(tNode.data,"->",end="")7else:8print("None")算法2-19輸出單鏈表某一元素函數(shù)77循環(huán)單鏈表是在單鏈表的基礎(chǔ)上，將其自身的第一個(gè)結(jié)點(diǎn)的地址存入表中最后一個(gè)結(jié)點(diǎn)的指針域中。與單鏈表相比，兩者的基本操作大致類似，所以在本節(jié)中，我們將重點(diǎn)介紹循環(huán)單鏈表的創(chuàng)建、插入及刪除操作。2.3.3循環(huán)單鏈表78創(chuàng)建文件ex020303.py。在該文件中我們首先定義一個(gè)Node類，該類包含創(chuàng)建結(jié)點(diǎn)并對結(jié)點(diǎn)進(jìn)行初始化的操作。我們在實(shí)現(xiàn)這一方法時(shí)，調(diào)用了與單鏈表Node類中的__init__()方法相同的源代碼。定義一個(gè)CircularSingleLinkedList類，用于創(chuàng)建一個(gè)循環(huán)單鏈表，并對其執(zhí)行相關(guān)操作（參見教材p47表2-8）。2.3.3循環(huán)單鏈表79在實(shí)現(xiàn)CircularSingleLinkedList類的__init__(self)時(shí)，我們調(diào)用了與單鏈表SingleLinkedList類的__init__(self)方法類似的源代碼。接下來，我們將具體實(shí)現(xiàn)CircularSingleLinkedList類中的CreateCircularSingleLinkedList(self)、InsertElementInTail(self)、InsertElementInHead(self)和DeleteElement(self)這4個(gè)方法，其余方法讀者可根據(jù)自己的需要來實(shí)現(xiàn)。2.3.3循環(huán)單鏈表80SingleLinkedList類的成員函數(shù)CreateCircularSingleLinkedList(self)可創(chuàng)建一個(gè)新的循環(huán)單鏈表，其算法思路如下。（1）獲取頭結(jié)點(diǎn)。（2）由用戶輸入每個(gè)結(jié)點(diǎn)值，并依次創(chuàng)建這些結(jié)點(diǎn)。（3）每創(chuàng)建一個(gè)結(jié)點(diǎn)，將其鏈入循環(huán)單鏈表的尾部，并將頭結(jié)點(diǎn)的地址存入其指針域中。（4）若用戶輸入“#”號(hào)，則結(jié)束輸入，完成循環(huán)單鏈表的創(chuàng)建。2.3.3循環(huán)單鏈表81該算法思路對應(yīng)的算法步驟如下。（1）調(diào)用input()方法接收用戶輸入的值data。（2）使用變量cNode指向頭結(jié)點(diǎn)。（3）判斷用戶的輸入是否為“#”，若結(jié)果為真，則轉(zhuǎn)（6）；否則轉(zhuǎn)（4）。（4）將data轉(zhuǎn)化為整型數(shù)，然后將其作為參數(shù)去創(chuàng)建并初始化一個(gè)新結(jié)點(diǎn)nNode。（5）在cNode的next域中存入nNode的地址，并將頭結(jié)點(diǎn)的地址存入nNode的next域中，最后將cNode指向其后繼結(jié)點(diǎn)，并繼續(xù)接受用戶的輸入后轉(zhuǎn)（3）。（6）結(jié)束當(dāng)前輸入，完成循環(huán)單鏈表的創(chuàng)建。2.3.3循環(huán)單鏈表821####################################2#創(chuàng)建循環(huán)單鏈表函數(shù)3####################################4defCreateCircularSingleLinkedList(self):5print("*************************************************")6print("*請輸入數(shù)據(jù)后按回車鍵確認(rèn)，若想結(jié)束請輸入“#”。*")7print("*************************************************")8data=input("請輸入結(jié)點(diǎn)的值：")9cNode=self.head10whiledata!="#":11nNode=Node(int(data))12cNode.next=nNode13nNode.next=self.head14cNode=cNode.next15data=input("請輸入結(jié)點(diǎn)的值：")算法2-20創(chuàng)建循環(huán)單鏈表函數(shù)83SingleLinkedList類的成員函數(shù)InsertElementInTail(self)，可向已有循環(huán)單鏈表的尾端插入結(jié)點(diǎn)，其算法思路如下。（1）輸入待插入結(jié)點(diǎn)的值。（2）創(chuàng)建數(shù)據(jù)域?yàn)樵撝档慕Y(jié)點(diǎn)。（3）在當(dāng)前循環(huán)單鏈表的尾端插入該結(jié)點(diǎn)。2.3.3循環(huán)單鏈表84該算法思路對應(yīng)的算法步驟如下。（1）調(diào)用input()方法接收用戶輸入，并將其存入變量Element中。（2）判斷Element是否為“#”，若結(jié)果為真，則轉(zhuǎn)（8）；否則轉(zhuǎn)（3）。（3）使用cNode指向循環(huán)單鏈表的頭結(jié)點(diǎn)。（4）將Element轉(zhuǎn)化為整型數(shù)，然后將其作為參數(shù)去創(chuàng)建并初始化一個(gè)新結(jié)點(diǎn)。（5）判斷cNode的next是否為頭結(jié)點(diǎn)，若為真則轉(zhuǎn)（7），否則轉(zhuǎn)（6）。（6）將cNode指向其后繼結(jié)點(diǎn)，轉(zhuǎn)（5）。（7）將cNode的next指向新結(jié)點(diǎn)nNode，并將nNode的next指向頭結(jié)點(diǎn)，完成該結(jié)點(diǎn)在循環(huán)單鏈表尾端的插入。（8）結(jié)束本程序并返回。2.3.3循環(huán)單鏈表851#####################################2#尾端插入函數(shù)3#####################################4defInsertElementInTail(self):5Element=input("請輸入待插入結(jié)點(diǎn)的值：")6ifElement=="#":7return8cNode=self.head9nNode=Node(int(Element))10whilecNode.next!=self.head:11cNode=cNode.next12cNode.next=nNode13nNode.next=self.head算法2-21尾端插入函數(shù)86假定我們在之前創(chuàng)建的循環(huán)單鏈表CSLList中，將值為6的結(jié)點(diǎn)插入至表中最后一個(gè)位置。通過執(zhí)行上述代碼，將原本含有兩個(gè)結(jié)點(diǎn)的循環(huán)單鏈表CSLList，變?yōu)楹?個(gè)結(jié)點(diǎn)的循環(huán)單鏈表CSLList。87SingleLinkedList類的成員函數(shù)InsertElementInHead(self)，在循環(huán)單鏈表的首端插入新結(jié)點(diǎn)，其算法思路如下。（1）輸入待插入結(jié)點(diǎn)的值。（2）創(chuàng)建數(shù)據(jù)域?yàn)樵撝档慕Y(jié)點(diǎn)。（3）在當(dāng)前循環(huán)單鏈表的首端插入該結(jié)點(diǎn)。2.3.3循環(huán)單鏈表88該算法思路對應(yīng)的算法步驟如下。（1）調(diào)用input()方法接收用戶輸入，并將其存入變量Element中。（2）判斷Element是否為“#”，若結(jié)果為真，則轉(zhuǎn)（7）；否則轉(zhuǎn)（3）。（3）使用變量cNode指向循環(huán)單鏈表的頭結(jié)點(diǎn)。（4）將Element轉(zhuǎn)化為整型數(shù)，然后將其作為參數(shù)去創(chuàng)建并初始化一個(gè)新結(jié)點(diǎn)。（5）將nNode的next指向cNode的后繼結(jié)點(diǎn)。（6）將cNode的next指向新結(jié)點(diǎn)nNode，完成循環(huán)單鏈表首端的插入。（7）結(jié)束本程序并返回。2.3.3循環(huán)單鏈表891#####################################2#首端插入函數(shù)3#####################################4defInsertElementInHead(self):5Element=input("請輸入待插入結(jié)點(diǎn)的值：")6ifElement=="#":7return8cNode=self.head9nNode=Node(int(Element))10nNode.next=cNode.next11cNode.next=nNode算法2-22首端插入函數(shù)90SingleLinkedList類的成員函數(shù)DeleteElement(self)，可將循環(huán)單鏈表中與指定元素值相等的結(jié)點(diǎn)刪除，其算法思路如下。（1）輸入待刪除結(jié)點(diǎn)的值。（2）在單鏈表中查找是否存在某一結(jié)點(diǎn)的值與待刪除結(jié)點(diǎn)的值相等。（3）若查找成功，則執(zhí)行刪除操作。（4）若查找失敗，則輸出相應(yīng)提示。2.3.3循環(huán)單鏈表91該算法思路對應(yīng)的算法步驟如下。（1）調(diào)用input()方法由用戶輸入待刪除結(jié)點(diǎn)的值，并使用變量dElement存儲(chǔ)。（2）使用變量cNode、pNode指向循環(huán)單鏈表的頭結(jié)點(diǎn)（3）判斷當(dāng)前鏈表是否為空，若為空則轉(zhuǎn)（4），否則轉(zhuǎn)（5）。（4）調(diào)用print()方法輸出當(dāng)前循環(huán)單鏈表為空的提示并返回。（5）當(dāng)cNode的next不為頭結(jié)點(diǎn)且cNode所指結(jié)點(diǎn)的值不等于dElement時(shí)，執(zhí)行（6），否則執(zhí)行（7）。（6）令pNode等于cNode，再將cNode指向其后繼結(jié)點(diǎn)并轉(zhuǎn)（5）。（7）判斷cNode所指結(jié)點(diǎn)的值是否等于dElement，若為真，則轉(zhuǎn)（8）；否則轉(zhuǎn)（9）。（8）將pNode的next指向cNode的后繼結(jié)點(diǎn)，然后刪除cNode所指結(jié)點(diǎn)，再調(diào)用print()方法輸出相應(yīng)提示。（9）調(diào)用print()方法輸出刪除失敗的提示。921#####################################2#刪除元素函數(shù)3#####################################4defDeleteElement(self):5dElement=int(input('請輸入待刪除結(jié)點(diǎn)的值：'))6cNode=self.head7pNode=self.head8ifself.IsEmpty():9print("當(dāng)前循環(huán)單鏈表為空！")10return11whilecNode.next!=self.headandcNode.data!=dElement:12pNode=cNode13cNode=cNode.next14ifcNode.data==dElement:15pNode.next=cNode.next16delcNode17print("成功刪除含有元素",dElement,"的結(jié)點(diǎn)")18else:19print("刪除失敗！雙鏈表中不存在含有元素",dElement,"的結(jié)點(diǎn)\n")算法2-23刪除元素函數(shù)93通常在單鏈表中，每個(gè)結(jié)點(diǎn)都只有一個(gè)指向其直接后繼結(jié)點(diǎn)的指針，我們只能通過這一指針訪問到該結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)。若我們需要訪問某一結(jié)點(diǎn)cNode的直接先驅(qū)結(jié)點(diǎn)，只能從頭結(jié)點(diǎn)開始，借助于每一個(gè)結(jié)點(diǎn)的指針域依次訪問其后繼結(jié)點(diǎn)，直到某一結(jié)點(diǎn)的后繼結(jié)點(diǎn)為cNode時(shí)，才找到了cNode的直接先驅(qū)結(jié)點(diǎn)。倘若我們?yōu)樯鲜鼋Y(jié)點(diǎn)增加一個(gè)指針域，用來記錄其直接先驅(qū)結(jié)點(diǎn)，則可大大提高處理此類問題的效率。我們將這種同時(shí)包含兩個(gè)指針域的結(jié)點(diǎn)構(gòu)成的鏈表稱為雙鏈表，對于每一個(gè)結(jié)點(diǎn)而言，它的一個(gè)指針域可用于存儲(chǔ)該結(jié)點(diǎn)直接先驅(qū)結(jié)點(diǎn)的地址，我們將其稱為先驅(qū)指針域，而另一個(gè)指針域用于存儲(chǔ)該結(jié)點(diǎn)直接后繼結(jié)點(diǎn)的地址，我們將其稱為后繼指針域。2.3.4雙鏈表94在本節(jié)中，我們將具體介紹如何實(shí)現(xiàn)帶頭結(jié)點(diǎn)的雙鏈表的基本操作，請讀者按以下步驟執(zhí)行。第1步，創(chuàng)建文件ex020304.py。在該文件中我們首先定義一個(gè)DoubleLinkedNode類，該類包含創(chuàng)建結(jié)點(diǎn)并對結(jié)點(diǎn)進(jìn)行初始化的操作。第2步，定義一個(gè)DoubleLinkedList類，用于創(chuàng)建一個(gè)雙鏈表，并對其執(zhí)行相關(guān)操作（參見教材pp52~53表2-10）。2.3.4雙鏈表95接下來，我們將具體實(shí)現(xiàn)DoubleLinkedNode類中的__init__()方法，以及DoubleLinkedList類中的__init__(self)、CreateDoubleLinkedList(self)、InsertElementInTail(self)、InsertElementInHead(self)、DeleteElement(self)和TraverseElement(self)這6個(gè)方法。其余方法讀者可根據(jù)自己的需要來實(shí)現(xiàn)。2.3.4雙鏈表96我們調(diào)用DoubleLinkedNode類的成員函數(shù)__init__（self,data）初始化一個(gè)結(jié)點(diǎn)，其算法思路如下。（1）創(chuàng)建一個(gè)數(shù)據(jù)域，用于存儲(chǔ)每個(gè)結(jié)點(diǎn)的值。（2）創(chuàng)建一個(gè)后繼指針域，用于存儲(chǔ)下一個(gè)結(jié)點(diǎn)的地址。（3）創(chuàng)建一個(gè)先驅(qū)指針域，用于存儲(chǔ)前一個(gè)結(jié)點(diǎn)的地址。（4）根據(jù)實(shí)際需要?jiǎng)?chuàng)建其他域，用于存儲(chǔ)結(jié)點(diǎn)的各種信息。2.3.4雙鏈表97該算法思路對應(yīng)的算法步驟如下。（1）創(chuàng)建數(shù)據(jù)域并將其初始化為data。（2）創(chuàng)建后繼指針域并將其初始化為空。（3）創(chuàng)建先驅(qū)指針域并將其初始化為空。2.3.4雙鏈表981#######################2#初始化結(jié)點(diǎn)函數(shù)3#######################4def__init__(self,data):5self.data=data6self.next=None7self.prev=None算法2-24初始化結(jié)點(diǎn)函數(shù)99我們調(diào)用DoubleLinkedList類的成員函數(shù)__init__(self)來初始化頭結(jié)點(diǎn)，其算法思路如下。（1）創(chuàng)建單鏈表的頭結(jié)點(diǎn)。（2）將其初始化為空。該算法思路對應(yīng)的算法步驟如下。（1）創(chuàng)建一個(gè)結(jié)點(diǎn)并將其初始化為空。（2）令雙鏈表的頭結(jié)點(diǎn)為上述結(jié)點(diǎn)。2.3.4雙鏈表1001###################################2#初始化頭結(jié)點(diǎn)函數(shù)3###################################4def__init__(self):5self.head=DoubleLinkedNode(None)算法2-25初始化頭結(jié)點(diǎn)函數(shù)101我們調(diào)用DoubleLinkedList類的成員函數(shù)CreateDoubleLinkedList(self)創(chuàng)建一個(gè)雙鏈表，其算法思路如下。（1）獲取頭結(jié)點(diǎn)。（2）由用戶輸入每個(gè)結(jié)點(diǎn)值，并依次創(chuàng)建這些結(jié)點(diǎn)。（3）每創(chuàng)建一個(gè)結(jié)點(diǎn)，將其鏈入雙鏈表的尾部。（4）若用戶輸入“#”號(hào)，轉(zhuǎn)（5）；否則轉(zhuǎn)（2）。（5）完成雙鏈表的創(chuàng)建。2.3.4雙鏈表102該算法思路對應(yīng)的算法步驟如下。（1）調(diào)用input()方法接收用戶輸入的值data。（2）使用變量cNode指向頭結(jié)點(diǎn)。（3）判斷用戶的輸入是否為“#”，若結(jié)果為真，則轉(zhuǎn)（6）；否則轉(zhuǎn)（4）。（4）將data轉(zhuǎn)化為整型數(shù)，然后將其作為參數(shù)去創(chuàng)建并初始化一個(gè)新結(jié)點(diǎn)nNode。（5）在cNode的next中存入nNode，再將cNode存入nNode的prev中，最后將cNode指向其直接后繼結(jié)點(diǎn)，并繼續(xù)接受用戶輸入后轉(zhuǎn)（3）。（6）結(jié)束當(dāng)前輸入，完成雙鏈表的創(chuàng)建。2.3.4雙鏈表1031###################################2#創(chuàng)建雙鏈表函數(shù)3###################################4defCreateDoubleLinkedList(self):5print("*************************************************")6print("*請輸入數(shù)據(jù)后按回車鍵確認(rèn)，若想結(jié)束請輸入“#”。*")7print("*************************************************")8data=input("請輸入元素：")9cNode=self.head10whiledata!='#':11nNode=DoubleLinkedNode(int(data))12cNode.next=nNode13nNode.prev=cNode14cNode=cNode.next15data=input("請輸入元素：")算法2-26創(chuàng)建雙鏈表函數(shù)104通過執(zhí)行上述代碼，我們可以創(chuàng)建一個(gè)新的雙鏈表。如圖所示為某一次輸入所產(chǎn)生的雙鏈表DLList，若無特殊說明，我們在之后講解的內(nèi)容都會(huì)基于該雙鏈表進(jìn)行操作。105我們調(diào)用DoubleLinkedList類的成員函數(shù)InsertElementInTail(self)，向已有雙鏈表的尾端插入結(jié)點(diǎn)，其算法思路如下。（1）輸入待插入結(jié)點(diǎn)的值。（2）創(chuàng)建數(shù)據(jù)域?yàn)樵撝档慕Y(jié)點(diǎn)。（3）在當(dāng)前雙鏈表的尾端插入該結(jié)點(diǎn)。2.3.4雙鏈表106該算法思路對應(yīng)的算法步驟如下。（1）調(diào)用input()方法接收用戶輸入，并將其存入變量Element中。（2）判斷Element是否為“#”，若結(jié)果為真，則轉(zhuǎn)（8）；否則轉(zhuǎn)（3）。（3）將Element轉(zhuǎn)化為整型數(shù)，然后將其作為參數(shù)去創(chuàng)建并初始化一個(gè)新結(jié)點(diǎn)。（4）使用cNode指向當(dāng)前雙鏈表的頭結(jié)點(diǎn)。（5）判斷cNode所指結(jié)點(diǎn)的后繼指針域是否為空，若為空則轉(zhuǎn)（7），否則轉(zhuǎn)（6