Python程序設(shè)計基礎(chǔ)教程完整版教案全書電子講義整本書課程設(shè)計

教學(xué)過程教學(xué)環(huán)節(jié)教學(xué)內(nèi)容與過程（教學(xué)內(nèi)容、教學(xué)方法、組織形式、教學(xué)手段）課前組織做好上課前的各項準(zhǔn)備工作（打開計算機(jī)、打開課件、打開軟件、打開授課計劃、教案等），吸引學(xué)生注意力。課程說明【課前說明】從二叉樹的基本概念引入本章學(xué)習(xí)內(nèi)容。【目的】使學(xué)生從了解本節(jié)課的學(xué)習(xí)目標(biāo)、學(xué)習(xí)重點、考評方式等方面明確課程學(xué)習(xí)的要求和目標(biāo)。課程內(nèi)容描述10.1Python中二叉樹的遞歸遍歷10.1.1二叉樹的基本概念計算機(jī)中，數(shù)據(jù)元素在不同的場合還可以被稱作“結(jié)點”“頂點”“記錄”等。在二叉樹這種數(shù)據(jù)結(jié)構(gòu)中，把數(shù)據(jù)元素統(tǒng)稱為“結(jié)點”?！岸鏄洹笔且粋€由結(jié)點組成的有限集合。這個集合或者為空，或者由一個稱為“根”的結(jié)點及兩棵不相交的二叉樹組成，這兩棵二叉樹分別稱為這個根結(jié)點的“左子樹”和“右子樹”。當(dāng)二由二叉樹的定義可以知道，它其實是一個遞歸式的定義，因為在定義一棵二叉樹時，又用到了二叉樹這個術(shù)語：一個結(jié)點的左、右子樹也是二叉樹。如果子樹是空的，那么這時就說該結(jié)點沒有“左孩子”或者沒有“右孩子”。綜上所述，二叉樹有如下的特征：●二叉樹可以是空的，空二叉樹沒有任何結(jié)點?！穸鏄渖系拿總€結(jié)點最多可以有兩棵子樹，這兩棵子樹是不相交的?！穸鏄渖弦粋€結(jié)點的兩棵子樹有左、右之分，次序是不能顛倒的。例10-1下圖所示的是二叉樹的幾種圖形表示。上圖（a）所示為一棵空二叉樹，我們用符號“Ф”來表示；上圖（b）所示為一棵只有一個結(jié)點的二叉樹，這個結(jié)點就是這棵二叉樹的根結(jié)點，由于該二叉樹只有一個根結(jié)點，所以也可以說這是一棵左、右子樹都為空的二叉樹；上圖（c）所示為由一個根結(jié)點、左子樹的根結(jié)點B、右子樹的根結(jié)點C組成的一棵二叉樹；上圖（d）所示為一棵只含左子樹的二叉樹（當(dāng)然，也可以有只含右子樹的二叉樹，這里沒有給出）；上圖（e）所示為一棵普通的二叉樹，其左子樹只有根結(jié)點B，右子樹則由若干個結(jié)點組成，整棵二叉樹可以劃分為4層，分別是第0層～第3層。二叉樹是一種非線性結(jié)構(gòu)，人們無法使用熟悉的順序（也就是線性）方法知道一個結(jié)點的“下一個”是誰，只有人為地做出限定，才能去訪問某結(jié)點中的數(shù)據(jù)。所謂“遍歷”二叉樹，是指按照規(guī)定的路線對二叉樹進(jìn)行搜索，以保證里面的每個結(jié)點被訪問一次，而且只被訪問一次。由于一棵非空二叉樹是由根結(jié)點及兩棵不相交的左、右子樹3個部分組成的，因此如果人為規(guī)定一種順序，在到達(dá)每一個結(jié)點時，都按照這個規(guī)定去訪問與該結(jié)點有關(guān)的3個部分，那么就可以訪問二叉樹上的所有結(jié)點，且每個結(jié)點只被訪問一次。若用T、L和R分別表示二叉樹的根結(jié)點、左子樹和右子樹，那么在到達(dá)每一個結(jié)點時，訪問結(jié)點的順序可以有以下6種不同的組合形式：●TLR——先訪問根結(jié)點，再訪問左子樹，最后訪問右子樹。●LTR——先訪問左子樹，再訪問根結(jié)點，最后訪問右子樹?！馤RT——先訪問左子樹，再訪問右子樹，最后訪問根結(jié)點?！馮RL——先訪問根結(jié)點，再訪問右子樹，最后訪問左子樹?！馬TL——先訪問右子樹，再訪問根結(jié)點，最后訪問左子樹?！馬LT——先訪問右子樹，再訪問左子樹，最后訪問根結(jié)點。前3個規(guī)定的特點是到達(dá)一個結(jié)點后，對左、右子樹來說，總是“先訪左、后訪右”；后3個規(guī)定的特點是到達(dá)一個結(jié)點后，對左、右子樹來說，總是“先訪右、后訪左”。如果對左、右子樹，我們約定總是“先訪左、后訪右”，那么訪問結(jié)點的6種順序就只剩下3種不同的組合形式：TLR、LTR、LRT。通常，稱TLR為二叉樹的先根遍歷或先序遍歷（因為T在最前面），稱LTR為中根遍歷或中序遍歷（因為T在中間），稱LRT為后根遍歷或后序遍歷（因為T在最后面）。例10-2以先根遍歷（TLR）的順序訪問下圖所示的二叉樹，并給出遍歷后的結(jié)點訪問序列。先根遍歷的總體規(guī)定是每到達(dá)二叉樹的一個結(jié)點后，就先訪問根結(jié)點，然后訪問它的左子樹上的所有結(jié)點，最后訪問右子樹上的所有結(jié)點?，F(xiàn)在從圖10-2所示的二叉樹根結(jié)點A開始出發(fā)遍歷。在訪問了根結(jié)點A之后，由于它有左子樹，因此根據(jù)規(guī)定應(yīng)該前進(jìn)到它的左子樹去。到達(dá)左子樹后，根據(jù)規(guī)定先訪問該二叉樹的根結(jié)點B，再去訪問B的左子樹。由于B有左子樹，因此前進(jìn)到它的左子樹。到達(dá)左子樹后，仍先訪問它的根結(jié)點D，再去訪問D的左子樹。這時左子樹為空，因此根據(jù)規(guī)定去訪問它的右子樹。但D的右子樹也為空，至此，結(jié)點B的左子樹上的所有結(jié)點都已訪問完畢，根據(jù)規(guī)定就應(yīng)該去訪問它的右子樹上的結(jié)點了。結(jié)點B的右子樹是以結(jié)點E為根的二叉樹。到達(dá)結(jié)點E后，按照先根遍歷的規(guī)定，先訪問根結(jié)點E，然后訪問它的左子樹。在訪問了左子樹的根結(jié)點H后，由于H的左、右子樹都為空，因此結(jié)點E的左子樹上的所有結(jié)點都訪問完畢，轉(zhuǎn)去訪問它的右子樹。由于結(jié)點E的右子樹為空，于是結(jié)點B的右子樹上的所有結(jié)點都已訪問完畢。至此，結(jié)點A左子樹上的所有結(jié)點都已訪問完畢，按先根遍歷的規(guī)定，應(yīng)該轉(zhuǎn)去訪問它的右子樹上的所有結(jié)點了。結(jié)點A的右子樹的根結(jié)點是C。先訪問結(jié)點C，然后去訪問它的左子樹。這時左子樹的根結(jié)點為F，于是訪問F，然后去訪問F的左子樹。由于左子樹為空，因此去訪問它的右子樹。結(jié)點F的右子樹的根結(jié)點是I，于是訪問結(jié)點I。由于I的左、右子樹均為空，至此，結(jié)點C的左子樹上結(jié)點全部訪問完畢，轉(zhuǎn)去訪問它的右子樹。結(jié)點C的右子樹的根結(jié)點是G，于是訪問結(jié)點G。由于結(jié)點G的左、右子樹都為空，至此，結(jié)點A的右子樹上的所有結(jié)點都訪問完畢，對該二叉樹的先根遍歷也就到此結(jié)束。歸納對該二叉樹結(jié)點的“訪問”次序，可以得到對圖10-2所示的二叉樹的先根遍歷序列：A→B→D→E→H→C→F→I→G通過此例可以知道，求一個二叉樹的某種遍歷序列，最重要的是在到達(dá)每一個結(jié)點時都必須堅持該遍歷的原則，只有這樣才能得出正確的結(jié)點遍歷序列，確保每個結(jié)點都只被訪問一次。例10-3以中根遍歷（LTR）的順序訪問圖10-2所示的二叉樹，并給出遍歷后的結(jié)點序列。中根遍歷規(guī)定，在到達(dá)二叉樹的一個結(jié)點后，不是先訪問該結(jié)點，而是先去訪問該結(jié)點的左子樹，只有在訪問完左子樹后，才去訪問該結(jié)點，最后訪問該結(jié)點的右子樹。現(xiàn)在從圖10-2所示的二叉樹的根結(jié)點A開始遍歷。到達(dá)A后，先不能訪問它，而是要去訪問它的左子樹，于是進(jìn)到左子樹的根結(jié)點B。到達(dá)B后，根據(jù)中根遍歷規(guī)定，不能訪問B，而是要先訪問它的左子樹，于是又進(jìn)到結(jié)點D。到達(dá)D后，仍然不能訪問D，而是要先訪問它的左子樹。但D的左子樹為空，因此訪問D的左子樹的任務(wù)完成。由于訪問完D的左子樹，根據(jù)中根遍歷規(guī)定，這時才能訪問結(jié)點D。可見，中根遍歷二叉樹時，最先訪問的結(jié)點是該二叉樹最左邊的那個結(jié)點。訪問完結(jié)點D之后，應(yīng)該訪問D的右子樹。由于D的右子樹為空，于是，以D為根的二叉樹的遍歷結(jié)束，也就是以結(jié)點B為根的二叉樹的左子樹的遍歷結(jié)束，因此根據(jù)中根遍歷規(guī)定，這時才訪問結(jié)點B，然后去訪問以B為根結(jié)點的右子樹。到達(dá)右子樹的根結(jié)點E后，根據(jù)中根遍歷規(guī)定，不能訪問E，而是要先訪問它的左子樹，于是進(jìn)到結(jié)點H。H的左子樹為空，因此這時才訪問結(jié)點H。由于H的右子樹為空，至此，對以結(jié)點B為根的右子樹遍歷完畢，即以結(jié)點A為根的左子樹遍歷完畢。到這個時候，才可以訪問結(jié)點A。可見，中根遍歷二叉樹時，左子樹上的結(jié)點都先于二叉樹的根結(jié)點得到訪問，因此在遍歷序列里它們都位于根結(jié)點的左邊，而右子樹上的結(jié)點都位于根結(jié)點的右邊。訪問完二叉樹的根結(jié)點A之后，根據(jù)中根遍歷規(guī)定，將對二叉樹的右子樹進(jìn)行遍歷。到達(dá)右子樹根結(jié)點C后，不能訪問它，應(yīng)該先去訪問它的左子樹，于是進(jìn)到結(jié)點F。進(jìn)到結(jié)點F后，不能訪問它，應(yīng)該先去訪問它的左子樹。由于它的左子樹為空，因此才訪問結(jié)點F。訪問完結(jié)點F，應(yīng)該訪問它的右子樹，于是進(jìn)到結(jié)點I。I的左子樹為空，所以訪問結(jié)點I，然后訪問它的右子樹。因為I的右子樹為空，故以結(jié)點C為根的二叉樹的左子樹已遍歷完畢，所以訪問結(jié)點C，然后進(jìn)到右子樹的結(jié)點G。結(jié)點G的左子樹為空，因此訪問結(jié)點G，然后訪問G的右子樹。因為G的右子樹為空，至此，以結(jié)點A為根的右子樹全部遍歷完畢，也就是對整個二叉樹遍歷完畢?？梢?，中根遍歷二叉樹時，最后訪問的結(jié)點應(yīng)該是二叉樹上最右邊的那個結(jié)點。綜上所述，對圖10-2所示的二叉樹進(jìn)行中根遍歷時，遍歷的結(jié)點序列是：D→B→H→E→A→F→I→C→G不難總結(jié)出其規(guī)律：對于任何一棵二叉樹，先根遍歷時整棵樹的根結(jié)點總是處于遍歷序列之首；中根遍歷時整棵樹的根結(jié)點的位置總是“居中”，它的左子樹的所有結(jié)點都在其左邊，右子樹的所有結(jié)點都在其右邊；后根遍歷時整棵樹的根結(jié)點的位置總是在最后，其所有結(jié)點都在它的左邊。這個總結(jié)，對整棵二叉樹成立，對各子二叉樹也成立。10.1.2遞歸的概念前面提及：“由二叉樹的定義可以知道，它其實是一個遞歸式的定義，因為在定義一棵二叉樹時，又用到了二叉樹這個術(shù)語。”什么是“遞歸”呢？在程序設(shè)計中，遞歸其實應(yīng)該屬于函數(shù)調(diào)用的范疇。我們知道，一個函數(shù)是可以調(diào)用另一個函數(shù)的。在特定的條件下，一個函數(shù)也可以調(diào)用它自己。這就是所謂函數(shù)的“遞歸”調(diào)用?？匆粋€簡單的例子。計算整數(shù)n的階乘：n！=1×2×…×(n-1)×n，嚴(yán)格的數(shù)學(xué)定義如下。也就是說：當(dāng)n=0時，其階乘就是1；當(dāng)n>0時，其階乘等于n-1的階乘的n倍。不難看出，在這個階乘例如，可以用如下的Python函數(shù)fact()來實現(xiàn)整數(shù)n的遞歸調(diào)用：deffact(n): ifn==0: return1 else: returnn*fact(n-1)為了驗證它的正確性，編寫程序如下：deffact(n): ifn==0: return1 else: returnn*fact(n-1)#主程序print(fact(3))執(zhí)行后，輸出結(jié)果為6，完全正確。程序里沒有循環(huán)，很少的幾條語句顯得簡潔、清晰。但它的執(zhí)行路線卻不簡單，下圖描述了fact(3)的計算調(diào)用過程：求fact(3)時，需要調(diào)用fact(2)，而求fact(2)時又要調(diào)用fact(1)，直至到達(dá)求fact(0)。根據(jù)函數(shù)定義，它直接返回結(jié)果1。這樣一來，前面的一系列調(diào)用都能夠得到應(yīng)有的結(jié)果，從而按順序一級一級返回，最終得到fact(3)的計算結(jié)果6。例10-4數(shù)學(xué)中有一個所謂的Fibonacci（斐波那契）數(shù)列：1，1，2，3，5，8，13，21，34，55，89，…它是通過如下的遞歸方式來定義的：F0=1，F(xiàn)1=1，F(xiàn)2=F0+F1，…，F(xiàn)n=Fn-1+Fn-2(n>1)即除第1、2項外，從第3項開始，數(shù)列中的各項的值是它前兩項之和。該數(shù)列項值的增長速度是很快的。很明顯，求Fibonacci數(shù)列各項的值是一個遞歸過程。編寫程序，以遞歸方式處理Fibonacci數(shù)列：deffibon(x): ifx<=1: returnx else: returnfibon(x-1)+fibon(x-2) #主程序outn=[] #定義一個空列表foriteminrange(12): outn.append(fibon(itrm)) print('Fibonacci數(shù)列:',outn)運行該程序，結(jié)果如圖所示。程序中，考慮到Fibonacci數(shù)列從0或1開始，因此通過if語句返回0或1來終止整個遞歸過程。整個遞歸過程是由else語句來處理的，當(dāng)Fibonacci數(shù)列大于或等于2時，就將前面的兩項數(shù)值相加，得出新的項，并由return語句將該項取值返回。究竟要遞歸多少次，每次輸出Fibonacci數(shù)列列表中的什么內(nèi)容，將由for循環(huán)中的函數(shù)range()及調(diào)用函數(shù)fibon()時傳遞的參數(shù)item來決定。10.1.3二叉樹遍歷的Python算法為了對二叉樹進(jìn)行3種不同的遍歷，先要創(chuàng)建一棵二叉樹，然后再考慮遞歸遍歷的問題。這一切都可以由如下定義的二叉樹類BinaryTree來實現(xiàn)。程序編寫如下：#定義二叉樹類BinaryTreeclassBinaryTree: def__init__(self,value): self.left=None self.right=None self.data=value #創(chuàng)建左子樹函數(shù) definsertLeftChild(self,value): ifself.left: print('Leftchildtreealreadyexists.') else: self.left=BinaryTree(value) returnself.left #創(chuàng)建右子樹函數(shù) definsertRightChild(self,value): ifself.right: print('Rightchildtreealreadyexists.') else: self.right=BinaryTree(value) returnself.right #先根遍歷函數(shù) defpreOrder(self): print(self.data) #輸出根結(jié)點的值 ifself.left: self.left.preOrder()#遍歷左子樹 ifself.right: self.right.preOrder()#遍歷右子樹 #后根遍歷函數(shù) defpostOrder(self): ifself.left: self.left.postOrder()#遍歷左子樹 ifself.right: self.right.postOrder()#遍歷右子樹 print(self.data) #輸出根結(jié)點的值 #中根遍歷函數(shù) definOrder(self): ifself.left: self.left.inOrder()#遍歷左子樹 print(self.data) #輸出根結(jié)點的值 ifself.right: self.right.inOrder()#遍歷右子樹該類由以下6個函數(shù)組成。一是初始化函數(shù)__init__(self,value)。它的任務(wù)是給出一棵空二叉樹的架構(gòu)，它既沒有左子樹，也沒有右子樹，參數(shù)value是根結(jié)點的取值。二是創(chuàng)建左子樹函數(shù)insertLeftChild(self,value)。它的任務(wù)是到達(dá)該結(jié)點后，先判斷它是否有左子樹，如果有，則輸出“Leftchildtreealreadyexists.”（左子樹已存在）的信息；否則由傳遞過來的參數(shù)value建立該結(jié)點左子樹的根結(jié)點。三是創(chuàng)建右子樹函數(shù)insertRightChild(self,value)。它的任務(wù)是到達(dá)該結(jié)點后，先判斷它是否有右子樹，如果有，則輸出“rightchildtreealreadyexists.”（右子樹已存在）的信息；否則由傳遞過來的參數(shù)value建立該結(jié)點右子樹的根結(jié)點。四是先根遍歷函數(shù)preOrder(self)。它的任務(wù)是完成對二叉樹的先根遍歷，具體是到達(dá)一個結(jié)點后，先是輸出該結(jié)點的值（體現(xiàn)了先根遍歷的特點）；然后如果有左子樹，則通過遞歸方式完成對左子樹的遍歷；如果有右子樹，則通過遞歸方式完成對右子樹的遍歷，從而完成對整個二叉樹的先根遍歷。五是后根遍歷函數(shù)postOrder(self)。它的任務(wù)是完成對二叉樹的后根遍歷，具體是到達(dá)一個結(jié)點后，如果有左子樹，則通過遞歸方式完成對左子樹的遍歷；如果有右子樹，則通過遞歸方式完成對右子樹的遍歷；最后輸出該結(jié)點的值（體現(xiàn)了后根遍歷的特點），從而完成對整個二叉樹的后根遍歷。六是中根遍歷函數(shù)inOrder(self)。它的任務(wù)是完成對二叉樹的中根遍歷，具體是到達(dá)一個結(jié)點后，如果有左子樹，則通過遞歸方式完成對左子樹的遍歷；然后輸出該結(jié)點的值（體現(xiàn)了中根遍歷的特點）；最后如果有右子樹，則通過遞歸方式完成對右子樹的遍歷，從而完成對整個二叉樹的中根遍歷。把這一段代碼保存成“Tree10.py”文件，例如保存在D盤根目錄下，這樣誰想使用它，都可以通過“importTree10”將模塊導(dǎo)入。例10-5試importTree10#導(dǎo)入二叉樹模塊root=Tree10.BinaryTree('root')#創(chuàng)建該二叉樹的根結(jié)點rootb=root.insertLeftChild('B')c=root.insertRightChild('C')d=b.insertLeftChild('D')e=b.insertRightChild('E')h=e.insertLeftChild('H')f=c.insertLeftChild('F')i=f.insertRightChild('I')g=c.insertRightChild('G')print('中根遍歷序列是：')root.inOrder()print('先根遍歷序列是：')root.preOrder()print('后根遍歷序列是：')root.postOrder()print('從B結(jié)點開始的中根遍歷序列是：')b.inOrder()運行該程序，下圖中只顯示了先根、后根及從B結(jié)點開始的中根遍歷序列結(jié)果。10.2Python中的堆排序所謂“排序”，是指把一系列雜亂無章的無序數(shù)據(jù)排列成有序序列的過程。給定一組結(jié)點r1、r2、…、rn，對應(yīng)的關(guān)鍵字分別為k1、k2、…、kn。將這些結(jié)點重新排列成rs1、rs2、…、rsn，使得對應(yīng)的關(guān)鍵字滿足ks1≤ks2≤…≤ksn的升序條件。這種重排一組結(jié)點、使其關(guān)鍵字值具有非遞減順序的過程就稱為“排序”。當(dāng)然，讓關(guān)鍵字排序后表現(xiàn)出一種非遞增關(guān)系也是可以的，這也是“排序”。排序時依據(jù)的關(guān)鍵字類型，可以是字符、字符串、數(shù)字等，只要存在一種能夠比較關(guān)鍵字之間順序的辦法即可。我們討論時關(guān)注的是決定結(jié)點順序的關(guān)鍵字，而不是它的內(nèi)容。10.2.1堆的定義二叉樹中有一種所謂的“完全二叉樹”，是指該二叉樹除最后一層外，其余各層的結(jié)點都是滿的，且最后一層的結(jié)點都集中在左邊，右邊可以連續(xù)缺少若干個結(jié)點。下圖所示的兩棵二叉樹都是完全二叉樹。對下圖（a）來說，雖然最后一層少了3個結(jié)點，但這3個結(jié)點是最右邊的連續(xù)3個結(jié)點，符合完全二叉樹的定義；對下圖（b）來說，雖然最后一層只有最左邊的一個結(jié)點，但少的是右邊連續(xù)的7個結(jié)點，符合完全二叉樹的定義?！岸选笔且豢猛耆鏄洌腋鹘Y(jié)點的關(guān)鍵字值滿足如下條件：從根結(jié)點到任何一個孩子結(jié)點的路徑上的關(guān)鍵字值都是非遞減的，也就是說，根結(jié)點和任何分支結(jié)點的關(guān)鍵字值均小于或等于其左、右孩子結(jié)點（如果有的話）的關(guān)鍵字值。形式上，可以這樣來定義堆。有n個結(jié)點的關(guān)鍵字序列k1、k2、…、kn，若它們之間滿足條件：ki≤k2i，并且ki≤k2i+1（i=1，2，…，n/2，且2i+1≤n）那么該序列被稱為一個“堆”?？梢园殃P(guān)鍵字序列的每個ki看作是這棵有n個結(jié)點的完全二叉樹的第i個結(jié)點，其中k1是該完全二叉樹的根結(jié)點。例10-6有關(guān)鍵字序列10、23、18、68、94、72、71、83，由它構(gòu)成的下圖所示的完全二叉樹是一個堆，因為該完全二叉樹上結(jié)點的關(guān)鍵字之間滿足堆的條件，即有：10≤23≤68≤83，10≤23≤94，10≤18≤71，10≤18≤72對于堆，要注意如下3點：●在一個堆里，k1（即完全二叉樹的根結(jié)點）是堆中所有結(jié)點里關(guān)鍵字值最小的記錄。●堆的任何一棵子樹本身也是一個堆?！穸阎腥我唤Y(jié)點的關(guān)鍵字值都不大于左、右兩個孩子結(jié)點的關(guān)鍵字值（如果有的話），但是左、右孩子結(jié)點的關(guān)鍵字值之間沒有大小關(guān)系存在。例如，上圖所示的堆，其根結(jié)點的關(guān)鍵字值10是堆中所有關(guān)鍵字值里最小的；例如，以23為根結(jié)點的子樹，也滿足堆的條件，是一個堆；例如，10的左孩子結(jié)點的關(guān)鍵字23大于其右孩子結(jié)點的關(guān)鍵字18，但18的左孩子結(jié)點的關(guān)鍵字71卻小于右孩子結(jié)點的關(guān)鍵字72。10.2.2對堆排序過程的描述由堆的定義知道，堆里根結(jié)點的關(guān)鍵字值k1是堆中最小的。在利用堆進(jìn)行排序時，首先可以輸出根結(jié)點k1，然后通過一定的規(guī)則對余下的結(jié)點進(jìn)行調(diào)整，使它們之間又成為一個堆，這樣再輸出新的根結(jié)點。如此下去，最終由輸出的結(jié)果可以得到一個由小到大的序列。這就是堆排序的基本思想。例10-7關(guān)鍵字序列10、23、18、68、94、72、71、83是一個堆，相應(yīng)的完全二叉樹如下圖（a）所示，對它進(jìn)行堆排序，得出一個遞增的序列。堆排序不可能一蹴而就，而是一個“不斷輸出根結(jié)點→調(diào)整剩余結(jié)點→形成一個新堆”的過程，如下圖下圖下圖下圖下圖下圖下圖下圖下圖不斷重復(fù)地去做這樣的工作：輸出堆頂元素、用當(dāng)時堆中最后一個元素代替堆頂元素、以使完全二叉樹上的結(jié)點滿足堆的定義，直到堆中元素全部輸出為止。輸出的結(jié)點就是對初始堆的排序結(jié)果，即：10、18、23、68、71、72、83、94。10.2.3Python中的堆排序方法Python中提供了一個標(biāo)準(zhǔn)庫模塊——heapq，該模塊給出了一些方法，能夠很容易地實現(xiàn)上述復(fù)雜的堆排序過程。不過程序中要使用它時，必須先將其導(dǎo)入（import）。1．heappush()具體使用：heapq.heappush(<堆>,<關(guān)鍵字>)其中<堆>是要創(chuàng)建的堆的堆名，它必須是一個列表；<關(guān)鍵字>是要插入堆里的結(jié)點的關(guān)鍵字。2．heappop()具體使用：heapq.heappop(<堆>)其中<堆>是已存在的堆名，它必須是一個列表。功能：從<堆>里彈出（即刪除）頂元素并返回，隨之自動調(diào)整堆中的剩余關(guān)鍵字，以保持完全二叉樹堆的性質(zhì)不變。利用方法heappush()可以創(chuàng)建出一棵滿足堆性質(zhì)的完全二叉樹；利用方法heappop()可以從堆的頂端逐一彈出（刪除）堆的最小關(guān)鍵字，完成對堆中結(jié)點的升序排列，達(dá)到堆排序的目的。3．heapify()具體使用：heapq.heapify(<列表>)功能：將<列表>轉(zhuǎn)換為一個具有堆特性的完全二叉樹。4．heapreplace()具體使用：heapq.heapreplace(<堆>,<關(guān)鍵字>)功能：用給出的<關(guān)鍵字>替換<堆>中的最小元素，自動重新構(gòu)建成一個堆。5．nlargest()具體使用：heapq.nlargest(n,<堆>)功能：以降序方式返回<堆>中n個結(jié)點的關(guān)鍵字。6．nsmallest()具體使用：heapq.nsmallest(n,<堆>)功能：由升序方式返回<堆>中n個結(jié)點的關(guān)鍵字。因此，如果需要獲取整個堆中關(guān)鍵字值的降序排列或升序排列，就可以使用方法heapq.nlargest()或heapq.nsmallest()。7．<堆>[0]功能：查看<堆>中的最小關(guān)鍵字值，元素不彈出。如果只是想獲取而不是彈出（刪除）最小關(guān)鍵字值，則可使用此方法。下面舉幾個例子，說明Python中堆的各種方法的應(yīng)用。例10-8了解方法heappush()和heappop()的功能。importheapq#創(chuàng)建一個堆heap1=[]nums=[75,79,71,68,94,16,11,28]foriinnums:heapq.heappush(heap1,i)print('堆中已有元素：',heap1)print('\n')#從堆中彈出關(guān)鍵字完成排序lis=[]foriinrange(len(nums)):x=heapq.heappop(heap1)lis.append(x)print('出堆元素：'+str(x),end='')print('堆中剩余元素：',heap1)#輸出堆排序結(jié)果print('\n')print('堆排序的結(jié)果：',lis)該程序分為3個部分，第1部分是給出一個列表：nums=[75,79,71,68,94,16,11,28]通過for循環(huán)，調(diào)用方法heappush()，不斷把列表nums中的關(guān)鍵字插入堆heap1中，最終形成一個待排序的堆heap1。下圖所示的第1部分展現(xiàn)了利用完全二叉樹創(chuàng)建該堆的過程。這其實就是借助完全二叉樹實現(xiàn)建堆的過程。上圖所示的第1部分輸出8組數(shù)據(jù)，被標(biāo)注了（1）～（8），它們對應(yīng)下圖中給出的（1）～（8）。下圖（a）表明完全二叉樹只有一個根結(jié)點。下圖（b）是按照完全二叉樹的組成方式，把關(guān)鍵字79安排在根結(jié)點75的左子樹上。下圖（c）和（d）是按照完全二叉樹的組成方式，把關(guān)鍵字71安排在根結(jié)點75的右子樹上。這時為了滿足堆的性質(zhì)，必須把結(jié)點75和71對調(diào)，所以上圖所示的第1部分第（3）行輸出的完全二叉樹是71,79,75。進(jìn)到第4次循環(huán)時，把關(guān)鍵字68插入結(jié)點79的左子樹，如下圖（e）所示，它破壞了堆的性質(zhì)，因此要將68與79對調(diào)，再將68與71對調(diào)，這時的完全二叉樹如下圖（g）所示。這樣一次次地在完全二叉樹上做插入工作，插入后可能會引起結(jié)點間位置的調(diào)整，因此，為滿足堆的性質(zhì)，就有了下圖（l）~（q），便完成了整個堆的創(chuàng)建。程序的最后是輸出列表lis中記錄的對堆heap1的升序排序結(jié)果。例10-9了解方法heapify()和heapreplace()的功能：importheapqmls=[25,2,33,5,7,18,1,4,10,242]print('列表mls的元素是：',mls,'\n')heapq.heapify(mls)print('堆mls的元素是：',mls,'\n')heapq.heapreplace(mls,80)print('用80替換最小堆元素后，新堆是：',mls,'\n')程序中給出的mls是一個列表，作為參數(shù)傳遞給heapq的方法heapify()，實現(xiàn)將mls改造成堆的過程，因此在下圖的前兩行輸出的內(nèi)容就不一樣了，第1行輸出的是列表mls的內(nèi)容，第2行輸出的則是將mls轉(zhuǎn)換成堆以后堆中的關(guān)鍵字內(nèi)容。下圖最后一行輸出的是用80代替堆mls中的最小關(guān)鍵字1后，重新組成的堆的內(nèi)容，這時原來的最小值1沒有了，80調(diào)整到了它應(yīng)該在的位置上。例10-10了解方法nlargest()、nsmallest()、heap[0]的功能：importheapqmls=[25,2,33,5,7,18,1,4,10,242]print('堆元素的降序排列是:',heapq.nlargest(10,mls),'\n')print('堆前4個元素的升序排列是：',heapq.nsmallest(4,mls),'\n')print('堆中的最小元素是:',mls[0])10.3Python中的隊列Python中有3種隊列：先進(jìn)先出隊列、后進(jìn)先出隊列（又名“?！保约皟?yōu)先級隊列。它們在數(shù)據(jù)結(jié)構(gòu)課程中都有討論，在操作系統(tǒng)設(shè)計中有著廣泛的應(yīng)用。10.3.13種隊列的概念1．先進(jìn)先出隊列——FIFO若對Python中的有序可變數(shù)據(jù)結(jié)構(gòu)（例如列表）加以限定，使得對其的插入操作在一端進(jìn)行，刪除操作在另一端進(jìn)行，那么這種被限定的有序可變數(shù)據(jù)結(jié)構(gòu)就稱為“隊列”，有時也稱為“排隊”。由此定義可以得知：●隊列是一種有序可變的數(shù)據(jù)結(jié)構(gòu)，隊列中的各個數(shù)據(jù)元素之間呈線性關(guān)系；●進(jìn)入隊列（即插入）被限制在隊列的一端進(jìn)行，退出隊列（即刪除）被限制在隊列的另一端進(jìn)行，進(jìn)隊和出隊的操作位置是不能隨意改變的。在計算機(jī)操作系統(tǒng)中，經(jīng)常要把它所管理的各種資源（例如CPU、存儲器、設(shè)備）分配給申請者使用，這時采用的分配策略，大多是讓申請者排成一個隊列進(jìn)行等候，也就是采用隊列管理的辦法。在隊列中，被允許進(jìn)入隊列的一端常稱為“隊尾”，退出隊列的一端常稱為“隊首”。當(dāng)一個元素從隊列的隊尾插入時，稱為“進(jìn)隊”，進(jìn)入的元素成為新的隊尾元素；從當(dāng)前的隊首刪除一個元素時，稱為“出隊”，這時隊列中被刪除元素的下一個元素即成為新的隊首?？梢?，在隊列的運行過程中，隨著數(shù)據(jù)元素的不斷進(jìn)隊、出隊，隊尾、隊首元素都在不停地變化著。當(dāng)隊列里不含有任何數(shù)據(jù)元素時，稱其為“空隊列”。對于一個空隊列，因為它已經(jīng)沒有了元素，所以不能再對它進(jìn)行出隊操作了，否則就會出錯。假設(shè)有隊列Q=[a1,a2,a3,…,an?1,an]，如圖所示。那么意味著該隊列中的元素是以a1、a2、a3、…、an?1、an的順序一個接一個進(jìn)入隊列的。如果要出隊，第1個由此不難理解，最先進(jìn)入隊列的那個元素肯定是最先從隊列中出去的。因此把隊列稱作具有“先進(jìn)先出（First-In-First-Out，F(xiàn)IFO）”或“后進(jìn)后出（Last-In-Last-Out，LILO）”邏輯特點的數(shù)據(jù)結(jié)構(gòu)，意思是元素到達(dá)隊列的順序與離開隊列的順序是完全一致的。下圖描述了進(jìn)隊操作和出隊操作對隊尾、隊首的影響。元素10進(jìn)隊時，由于原先隊列為空，因此隊列上就只有10這個元素；元素8進(jìn)隊后，隊列上就有了兩個元素；元素10出隊，隊列上又只有8這一個元素了；接著元素14和9進(jìn)隊，整個隊列上有了3個元素；最后元素8出隊，隊列上就只剩下14和9兩個元素了。對于隊列來說，由于隊首和隊尾兩個方向的元素都在不斷地變化著，所以對其操作和管理所要考慮的問題就要多一些，要復(fù)雜一些。2．后進(jìn)先出隊列——LIFO在數(shù)據(jù)結(jié)構(gòu)課程中，后進(jìn)先出隊列常被稱為“?！薄Ｈ魧ython中的有序可變數(shù)據(jù)結(jié)構(gòu)（例如列表）加以限定，使插入和刪除操作只能在固定的同一端進(jìn)行，那么這種有序可變的數(shù)據(jù)結(jié)構(gòu)就被稱為所謂的“堆棧”，簡稱為“?！薄Ｓ纱硕x可以得知：●棧是一種有序可變的數(shù)據(jù)結(jié)構(gòu)，棧中各個數(shù)據(jù)元素之間呈線性關(guān)系；●對棧的插入和刪除操作被限制在棧的同一端進(jìn)行，不能任意改變。子彈夾就是一個棧：往彈夾里壓入子彈，就是對棧進(jìn)行插入操作；扣動扳機(jī)進(jìn)行射擊，就是對棧進(jìn)行刪除操作。插入和刪除都限定在彈夾口這端進(jìn)行。在一個棧中，被允許進(jìn)行插入和刪除的那一端稱為“棧頂”，不能進(jìn)行插入和刪除的那一端稱為“棧底”。從當(dāng)前棧頂處插入一個新的元素稱為“進(jìn)?！保袝r也稱“入?！薄皦簵！?，插入的這個元素就成為當(dāng)前新的棧頂；從當(dāng)前棧頂處刪除一個元素稱為“出?！?，有時也稱“退?！薄皬棗！?，棧頂元素出棧后下一個元素就成為新的棧頂元素。可見，在棧的工作過程中，隨著數(shù)據(jù)元素的進(jìn)棧、出棧，只有棧頂元素在不斷地發(fā)生變化。當(dāng)一個棧里不含有任何數(shù)據(jù)元素時，稱其為“空?！?。對于一個空棧，因為它已經(jīng)沒有元素了，所以不能再對它進(jìn)行出棧操作，否則就會出錯。按照棧的定義，最后被插入棧頂?shù)哪莻€元素肯定最先從棧中移出。因此，常把棧稱作具有“后進(jìn)先出（Last-In-First-Out，LIFO）”或“先進(jìn)后出（First-In-Last-Out，F(xiàn)ILO）”邏輯特點的數(shù)據(jù)結(jié)構(gòu)，意思是元素到達(dá)棧的順序與元素離開棧的順序恰好是相反的。例如，下圖（a）所示為一個空棧，棧頂（top）和棧底（bottom）都位于棧的最底部；下圖（b）所示為3個元素a1、a2、a3依次進(jìn)棧后棧的示意圖。從圖中看出，a1最先進(jìn)棧，a2次之，a3最后進(jìn)棧。如果在棧中的這幾個元素要出棧的話，那么應(yīng)該是a3最先出棧，a2次之，a1最后出棧。3．優(yōu)先級隊列——Priority申請使用系統(tǒng)資源時，為申請者規(guī)定一個使用的優(yōu)先級別，依指定的級別高低，將申請者進(jìn)行排隊，級別高的先獲得使用權(quán)，級別低的后獲得使用權(quán)。這樣的隊列就是一個所謂的“優(yōu)先級隊列”。不難看出，在一個申請者進(jìn)入優(yōu)先級隊列時，就要按照優(yōu)先級的大小，對該隊列重新進(jìn)行一次調(diào)整；在資源分配時，總是把資源分配給排在隊列的第1個申請者，并讓該申請者退出隊列。通?？偸且?guī)定優(yōu)先數(shù)越小，優(yōu)先級越高。系統(tǒng)中的每一種資源數(shù)量總是有限的，因此當(dāng)一個申請者向系統(tǒng)提出資源申請時，不一定能夠立刻得到滿足。在申請者得不到所需要的資源時，系統(tǒng)就可能會暫時使它無法運行下去，需要讓它等一等。這時就稱該申請者處于“阻塞”或“等待”狀態(tài)。一個處于阻塞狀態(tài)的申請者，只有在獲得了所需要的資源之后，才能夠繼續(xù)運行下去。例10-11設(shè)有6個元素a1、a2、a3、a4、a5、a6，它們以此順序依次進(jìn)棧（即a1必須最先進(jìn)棧，然后是a2進(jìn)棧，最后才是a6進(jìn)棧）。假定要求它們的出棧順序是a2、a3、a4、a6、a5、a1，那么應(yīng)該如何安排它們的進(jìn)棧和出棧操作序列呢？這個棧的容量至少要有多大呢？這6個元素以下面的順序進(jìn)棧和出棧，就能保證出棧順序是a2、a3、a4、a6、a5、a1。為了保證第1個出棧的是a2，必須連續(xù)做兩次進(jìn)棧操作，使a1、a2兩個元素進(jìn)棧。然后做一次出棧操作，使當(dāng)時位于棧頂?shù)腶2出棧，這樣棧里還剩一個元素a1。為了保證第2個出棧的是a3，必須做一次進(jìn)棧操作，使a3進(jìn)棧。緊接著做一次出棧操作，使當(dāng)時位于棧頂?shù)腶3出棧，這樣棧里仍只剩一個元素a1。為了保證第3個出棧的是a4，必須做一次進(jìn)棧操作，使a4進(jìn)棧。緊接著做一次出棧操作，使當(dāng)時位于棧頂?shù)腶4出棧，這樣棧里仍只剩一個元素a1。為了保證第4個出棧的是a6，必須連續(xù)做兩次進(jìn)棧操作，使a5、a6兩個元素進(jìn)棧。然后做兩次出棧操作，使當(dāng)時位于棧頂?shù)腶6出棧，再使當(dāng)時位于棧頂?shù)腶5出棧，這樣棧里仍只剩一個元素a1。最后做一次出棧操作，使當(dāng)時位于棧頂?shù)腶1出棧，棧由此變?yōu)榭铡？梢?，對這個棧的進(jìn)棧（push）和出棧（pop）操作序列應(yīng)該是：進(jìn)棧、進(jìn)棧、出棧、進(jìn)棧、出棧、進(jìn)棧、出棧、進(jìn)棧、進(jìn)棧、出棧、出棧、出棧。從進(jìn)、出棧的過程中可以看出，該棧里面最多同時會有3個元素存在（例如是a6、a5、a1），因此該棧至少應(yīng)該能夠同時容納3個元素。10.3.2Python中與隊列有關(guān)的方法Python提供了創(chuàng)建、操作隊列的模塊，名字是queue。該模塊能夠創(chuàng)建出3種不同類型的隊列對象：FIFO、LIFO以及Priority。（1）創(chuàng)建FIFO隊列：importqueueque=queue.Queue(maxsize=0)這兩條語句表明通過導(dǎo)入queue模塊后，創(chuàng)建了一個名為que的FIFO隊列對象（實例），在該對象里可以容納maxsize個數(shù)據(jù)元素。maxsize限定隊列的容量，若maxsize<=0，那么創(chuàng)建的隊列的尺寸就是無限制的；否則當(dāng)插入元素的個數(shù)達(dá)到maxsize規(guī)定的上限時，就會阻止元素進(jìn)入隊列。插入FIFO這種隊列里的第1個元素，就是第1個退出隊列的元素。（2）創(chuàng)建LIFO隊列：importqueueque=queue.LifoQueue(maxsize=0)這兩條語句表明通過導(dǎo)入queue模塊后，創(chuàng)建了一個名為que的LIFO隊列對象（實例），在該對象里可以容納maxsize個數(shù)據(jù)元素。maxsize的具體含義如上所述。插入這種隊列里的最后一個元素，肯定是第1個退出隊列的元素。（3）創(chuàng)建Priority隊列：importqueueque=queue.PriorityQueue(maxsize=0)這兩條語句表明通過導(dǎo)入queue模塊后，創(chuàng)建了一個名為que的Priority隊列對象（實例），在該對象里可以容納maxsize個數(shù)據(jù)元素。maxsize的具體含義如上所述。對于這種隊列，插入元素后會自動對元素實施堆排序（使用heapq模塊），堆頂元素（優(yōu)先級最高，優(yōu)先數(shù)最?。⑹堑?個退出隊列的元素。1．方法qsize()功能：返回隊列中當(dāng)前擁有的元素個數(shù)。用法：<隊列名>.qsize()其中<隊列名>是欲求該隊列中的元素個數(shù)的名字。2．方法empty()功能：如果隊列為空，返回True；否則返回False。用法：<隊列名>.empty()3．方法full()功能：如果隊列已滿，則返回True；否則返回False。用法：<隊列名>.full()4．方法put()功能：往隊列里插入一個元素。用法：<隊列名>.put(item,

block,

timeout)其中<隊列名>是欲進(jìn)行插入操作的隊列名稱；item是要插入的元素；block及timeout通常取默認(rèn)值，可忽略。5．方法get()功能：從隊列里彈出一個元素。用法：<隊列名>.get(block,

timeout)其中<隊列名>是欲進(jìn)行彈出操作的隊列名稱；block及timeout常取默認(rèn)值，可忽略。6．方法clear()功能：清空一個隊列。用法：<隊列名>.clear()其中<隊列名>是欲清空的隊列名稱。例10-12在FIFO隊列里調(diào)用方法qsize()、put()、get()：importqueueq=queue.Queue(maxsize=10) #q是一個FIFO的隊列對象print('\n','當(dāng)前隊列q中的元素個數(shù)是：',q.qsize(),'個')foriinrange(10):q.put(i) #往隊列里插入10個元素print('\n','當(dāng)前隊列q中的元素有：',q.queue)print('\n','當(dāng)前隊列q中的元素個數(shù)是：',q.qsize(),'個')x=q.get() #從隊列q里彈出一個元素print('\n','當(dāng)前退出隊列q的元素是：',x)print('\n','當(dāng)前隊列q中還有元素：',q.queue)print('\n','當(dāng)前隊列q中的元素個數(shù)是：',q.qsize(),'個')例10-13在LIFO隊列里調(diào)用方法qsize()、put()、get()：importqueuelq=queue.LifoQueue(maxsize=10)print('\n','當(dāng)前棧lq中的元素個數(shù)是：',lq.qsize(),'個')foriinrange(10):lq.put(i)print('\n','當(dāng)前棧lq中的元素有：',lq.queue)print('\n','當(dāng)前棧lq中的元素個數(shù)是：',lq.qsize(),'個')x=lq.get()print('\n','當(dāng)前出棧lq的元素是：',x)x=lq.get()print('\n','當(dāng)前出棧lq的元素是：',x)print('\n','當(dāng)前棧lq中還有元素：',lq.queue)print('\n','當(dāng)前棧lq中的元素個數(shù)是：',lq.qsize(),'個')程序中，兩次調(diào)用了方法get()。從下圖可以看出，LIFO隊列確實是一種“后進(jìn)先出”性質(zhì)的隊列，對其操作過程中，棧尾保持不變，棧頂在不斷地變化著。例10-14在Priority隊列里調(diào)用方法qsize()、put()、get()：importqueuepq=queue.PriorityQueue(maxsize=10)print('\n','當(dāng)前優(yōu)先級隊列pq中的元素個數(shù)是：',pq.qsize(),'個')pq.put(4)pq.put(7)pq.put(2)pq.put(9)pq.put(14)pq.put(5)print('\n','當(dāng)前優(yōu)先級隊列pq中的元素有：',pq.queue)print('\n','當(dāng)前優(yōu)先級隊列pq中的元素個數(shù)是：',pq.qsize(),'個')x=pq.get()print('\n','當(dāng)前出優(yōu)先級隊列pq的元素是：',x)x=pq.get()print('\n','當(dāng)前出優(yōu)先級隊列pq的元素是：',x)print('\n','當(dāng)前優(yōu)先級隊列pq中還有元素：',pq.queue)print('\n','當(dāng)前優(yōu)先級隊列pq中的元素個數(shù)是：',pq.qsize(),'個')下圖所示是該程序運行的結(jié)果。前面已提及，在優(yōu)先級隊列里是使用heapq模塊來對隊列中的元素進(jìn)行排序的。程序中先是用5條put語句讓4、7、2、9、14、5這6個元素插入隊列。插入過程中，Python不斷調(diào)整完全二叉樹，最終隊列中的元素組成一棵下圖（a）所示的、排好序的完全二叉樹，它對應(yīng)上圖中標(biāo)有①的內(nèi)容。在程序中第1次調(diào)用方法get()后，彈出隊列的元素是2。為了保持堆的特性，將余下的元素進(jìn)行調(diào)整，如下圖（b）和（c）所示。在程序中第2次調(diào)用方法get()后，彈出隊列的元素是4。為了保持堆的特性，再次將余下的元素進(jìn)行調(diào)整，如下圖（d）和（e）所示。這棵完全二叉樹的輸出對應(yīng)上圖中的②。例10-15在FIFO隊列里調(diào)用方法full()和empty()。在程序中設(shè)置一個能夠存放10個元素的FIFO隊列，先往隊列里插入10個元素1～10，由于隊列滿，于是彈出一個元素再插入一個元素，直至隊列滿。最后將隊列中的元素全部彈出。程序編寫如下：importqueuekq=queue.Queue(10)#定義一個大小為10的隊列count=0j=0foriinrange(1,19): ifkq.full(): #如果隊列滿，就讓隊首元素出隊 print('\n') x=kq.get() print("彈出：",x,'',end='') kq.put(i) print('插入:',i,'',end='') count+=1 if(count%5==0): print('\n')i=1count=0print('\n')whilenotkq.empty(): print('彈出:',kq.get(),'',end='') i+=1 count+=1 if(count%5==0): print('\n')下圖所示是程序的運行結(jié)果。10.3.3FIFO、LIFO隊列的自定義實現(xiàn)優(yōu)先級隊列多用于操作系統(tǒng)的資源管理中，它牽扯到資源的分配與回收，牽扯到申請者在系統(tǒng)中的狀態(tài)變化（例如申請不到資源時，其狀態(tài)由運行變?yōu)樽枞┑?，因此在此不涉及?yōu)先級隊列，只介紹FIFO及LIFO兩種隊列自定義實現(xiàn)的例子，供大家閱讀和參考。例10-16FIFO隊列的自定義實現(xiàn)：#定義類MyQueueclassMyQueue:def__init__(self,size=10):self.current=0self.size=sizeself.content=[]#入隊函數(shù)put()defput(self,v):ifself.current<self.size:self.content.append(v)self.current=self.current+1else:print("Thequeueisfull!")#出隊函數(shù)get()defget(self):ifself.content:self.current=self.current-1returnself.content.pop(0)else:print('Thequeueisempty!')#列出隊列當(dāng)前所有元素defshow(self):ifself.content:print(self.content)else:print('Thequeueisempty!')#置隊列為空defempty(self):self.content=[]#測試隊列是否為空defisEmpty(self):ifnotself.content:returnTrueelse:returnFalse#測試隊列是否為滿defisfull(self):ifself.current==self.size:returnTrueelse:returnFalse#主程序q=MyQueue() #創(chuàng)建類MyQueue的一個對象qq.get() #①q.put(5)q.put(7)print(q.isfull()) #②q.put('A')q.put(3)q.show() #③q.put(10)q.put('B')q.put(6)q.put('x')q.show() #④q.put('Y')q.put('Z')q.put('w') #⑤q.show() #⑥q.get()q.get()q.get()q.show() #⑦下圖所示是該程序的運行結(jié)果，主程序中的①～⑦對應(yīng)下圖中①～⑦的輸出內(nèi)容，表明這個設(shè)計基本上是可以滿足FIFO隊列工作的。從設(shè)計中知道，程序是利用Python中的簡單數(shù)據(jù)結(jié)構(gòu)列表（list）來實現(xiàn)隊列的，隊列名為content，其尺寸由變量size控制。初始化時，size被設(shè)定取值為10。在主程序中，調(diào)用者可以為size賦予所需的取值。調(diào)用方法put()，由變量current記錄應(yīng)往列表的哪個位置添加元素（利用函數(shù)append()），同時它也表明當(dāng)前列表里有多少個元素。調(diào)用方法get()，借助函數(shù)pop()，從列表頭（由pop(0)體現(xiàn)）彈出隊列的隊首元素。例10-17LIFO隊列的自定義實現(xiàn)：classStack: #定義棧類Stack def__init__(self,size=10): self.content=[] self.size=size self.current=0 #令棧為空 defempty(self): self.content=[] self.current=0 #測試棧是否為空，空時返回True，否則返回False defisempty(self): ifnotself.content: returnTrue else: returnFalse #如果要縮小?？臻g，則可刪除指定大小之后的已有元素 defsetSize(self,size): ifsize<self.current: foriinrange(size,self.current,1): delself.content[i] self.current=size self.size=size #測試棧是否為滿，滿時返回True，否則返回False defisfull(self): ifself.current==self.size: returnTrue else: returnFalse #若棧有空位，則通過調(diào)用方法append()讓元素v進(jìn)棧 defpush(self,v): iflen(self.content)<self.size: self.content.append(v) self.current=self.current+1 else: print('StackFull!') #若棧中有元素，則元素個數(shù)減1，棧頂元素出棧 defpop(self): ifself.content: self.current=self.current-1 returnself.content.pop() else: print('Stackisempty!') #輸出棧中元素 defshow(self): print(self.content) #輸出棧中當(dāng)前的空位數(shù) defshowRemainderSpace(self): print('StackcanstillPUSH',self.size-self.current,'elements.')#主程序importStacks=Stack.Stack()print(s.isempty()) #①print(s.isfull()) #②s.push(5)s.push(8)s.push('A')print(s.pop()) #③s.push('B')s.push('C')s.show() #④s.showRemainderSpace() #⑤s.setSize(3)print(s.isfull()) #⑥s.show() #⑦s.setSize(5)s.push('D')s.push('DDDD')s.push(3) #⑧s.show() #⑨該程序分為兩大部分，一是定義一個棧類Stack，將其存放在一個后綴為“.py”的模塊里，以供使用者調(diào)用；二是調(diào)用該類的主程序，如圖所示，把它存放在test1.py文件里。正因為如此，在主程序的開始處，用了導(dǎo)入語句“importStack”，將棧模塊導(dǎo)入使用。下圖所示是該程序的運行結(jié)果，主程序中的①～⑨對應(yīng)下圖中①～⑨的輸出內(nèi)容，表明這個設(shè)計基本上可以滿足LIFO隊列的工作。模塊Stack中出現(xiàn)的變量content、current、size的含義與前例相同。要解釋的是，主程序里明顯可以打印輸出的是print以及show，即主程序里的①～⑦和⑨，至于⑧輸出“StackFull！”，那是因為在執(zhí)行語句“push（3）”時，將遇到棧滿的情況，不能把元素插入棧中，因此才輸出該信息。10.3.4FIFO、LIFO隊列的應(yīng)用舉例例10-18約瑟夫問題：n個人圍成一個圈，從1開始按順序報數(shù)，報到k的人就退出圈，接著從退出圈的那個人下一個人開始再次從1順序報數(shù)，報到k的人又退出圈，不斷地重復(fù)這樣的工作，直到剩下最后一個人，該人即為獲勝者。例如，6個人圍坐成一個圈，如圖所示。k=8，規(guī)定總是按順時針報數(shù)（逆時針同樣也是可以的）。第1輪：2出局，剩余序列為3、4、5、6、1。第2輪：從3開始數(shù)，5出局，剩余序列為6、1、3、4。第3輪：從6開始數(shù)，4出局，剩余序列為6、1、3?！绱搜h(huán)，直到剩余最后一個3，于是退出隊列的順序是2、5、4、1、6、3，3堅持到了最后。下面，編寫一個Python小程序，打算利用隊列這種數(shù)據(jù)結(jié)構(gòu)，模擬約瑟夫問題所描述的這一淘汰過程?；舅枷胧牵喝绻麍蟮臄?shù)不是k，就讓此人插入隊尾；如果報的數(shù)是k，就讓其退出隊列。重復(fù)這樣的報數(shù)過程，直至剩下最后一個人。程序如下：#定義隊列類QueueclassQueue: #以列表items作為隊列的初始化def__init__(self):self.items=[]#清空隊列defempty(self):returnself.items==[]#將元素從索引為0處插入列表defenqueue(self,item):self.items.insert(0,item)#將列表尾元素彈出defdequeue(self):returnself.items.pop()#計算列表中元素個數(shù)defsize(self):returnlen(self.items)#對列表邊數(shù)數(shù)邊調(diào)整，將數(shù)到k的元素彈出defcircle(self,k,namelist):foriinrange(len(namelist)):queue1.enqueue(namelist[i])i=1 #開始數(shù)數(shù)whilequeue1.size()!=1:temp=queue1.dequeue() #哪個為第k個就將其存入臨時單元tempifi!=k:queue1.enqueue(temp) #不是第k個時就插入隊列else:print('這次出局的元素是：',temp)i=0i+=1return'獲勝者是：'+str(queue1.dequeue())#主程序queue1=Queue()namelist=['Bill','David','Susan','Jane','Kent','Brad']print(queue1.circle(12,namelist))namelist=[1,2,3,4,5,6]print(queue1.circle(8,namelist))作為隊列，最關(guān)鍵的是要確定哪一端是頭，將在這一端進(jìn)行退出操作；哪一端是尾，將在這一端進(jìn)行插入操作。類Queue中，函數(shù)enqueue()里通過列表items調(diào)用方法insert()，保證把要進(jìn)入隊列的元素插入隊頭；函數(shù)dequeue()里則通過列表items調(diào)用方法pop()，保證把要退出隊列的元素彈出隊尾。所以，類中的隊列是從頭進(jìn)入隊列、從尾退出隊列的。類Queue中關(guān)鍵的函數(shù)是circle()。主程序中調(diào)用它時，要傳遞過來兩個參數(shù)：一個是決定數(shù)到什么數(shù)時那個元素應(yīng)該退出隊列的k值；另一個是把隊列對象queue1進(jìn)行初始化的列表namelist（最初這里存放的是進(jìn)行報數(shù)的人的名字，或其他什么內(nèi)容）。然后函數(shù)circle()通過變量i數(shù)數(shù)，如果i不等于k，那么就將臨時工作單元temp中的內(nèi)容插入隊列中；如果i等于k，那么就舍棄temp中的那個元素（將其從隊列里彈出），將i重新設(shè)置為1，開始下一次數(shù)數(shù)。下圖所示是運行的結(jié)果，即當(dāng)namelist=['Bill','David','Susan','Jane','Kent','Brad']、數(shù)的數(shù)定為12時，每次輸出出局者，最終獲勝者是Susan；當(dāng)namelist=[1,2,3,4,5,6]、數(shù)的數(shù)定為8時，每次輸出出局者，最終獲勝者是3。例10-19利用棧將十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)。Python有提供數(shù)制之間轉(zhuǎn)換的函數(shù)，例如一個十進(jìn)制數(shù)調(diào)用函數(shù)bin()、oct()、hex()，其返回值就是二進(jìn)制數(shù)、八進(jìn)制數(shù)、十六進(jìn)制數(shù)。要注意的是，這些函數(shù)返回的結(jié)果都是字符串，且會帶有0b、0o、0o前綴，如圖所示。也可以用Python語言自定義函數(shù)來代替這樣的數(shù)制之間的轉(zhuǎn)換函數(shù)。下面是利用棧編寫的十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)的自定義函數(shù)divideBy2()：#定義類StackclassStack:def__init__(self):self.values=[]#進(jìn)棧函數(shù)defpush(self,value):self.values.append(value)#出棧函數(shù)defpop(self):returnself.values.pop()#將棧清空defis_empty(self):returnself.size()==0#返回棧的大小defsize(self):returnlen(self.values)#將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)defdivideBy2(decNumber):remstack=Stack()whiledecNumber>0:rem=decNumber%2print('rem=',rem,end='')#將余數(shù)逐個加入remstack.push(rem)decNumber=decNumber//2print('','decNumber=',decNumber)binString=""whilenotremstack.is_empty():binString=binString+str(remstack.pop())returnbinString#主程序x=int(input('請輸入十進(jìn)制數(shù)！'))print('需要轉(zhuǎn)換的十進(jìn)制數(shù)是：',x)print(divideBy2(233))下圖所示是主程序運行的結(jié)果，即十進(jìn)制數(shù)233轉(zhuǎn)換成的二進(jìn)制數(shù)是11101001。下圖所示是轉(zhuǎn)換函數(shù)divideBy2()的工作過程：把十進(jìn)制數(shù)用2除后，讓余數(shù)（0或1）進(jìn)入棧remstack，然后重復(fù)這一過程，直到十進(jìn)制數(shù)為0時停止。然后反方向?qū)emstack棧中的0、1數(shù)列彈出棧到binString字符串中，該字符串的內(nèi)容就是轉(zhuǎn)換后的二進(jìn)制值。下面給出由十進(jìn)制數(shù)轉(zhuǎn)換成任意進(jìn)制數(shù)的函數(shù)baseC()：#進(jìn)制轉(zhuǎn)換（十進(jìn)制數(shù)轉(zhuǎn)換成任意進(jìn)制數(shù)）defbaseC(decNumber,base):digits="0123456789ABCDEF"temp=[]whiledecNumber>0:rem=decNumber%basetemp.append(rem)decNumber=decNumber//baseresult_String=""whilelen(temp):result_String+=digits[temp.pop()]returnresult_String#主程序print(baseC(25,2))print(baseC(25,8))print(baseC(25,16))print(baseC(78,16))下圖所示是主程序的執(zhí)行結(jié)果。例10-20判斷一個序列是否為另一個入棧序列的出棧序列。當(dāng)把序列中的元素依序插入棧時，它們從棧中彈出的次序可以與進(jìn)入時的次序不同。例如元素進(jìn)入棧時的次序是1、2、3、4、5，它們可以以4、5、3、2、1的次序彈出，即先讓元素1、2、3、4進(jìn)入，然后彈出元素4，再讓元素5進(jìn)入，最后把5、3、2、1彈出。于是，這時5個元素雖然是以1、2、3、4、5的順序進(jìn)入的棧，但卻是以4、5、1、2、3的次序被彈出的棧。但這5個元素卻不能以4、3、5、1、2的次序彈出。下面編寫的小程序可以測試出一個序列是否為另一個入棧序列的出棧序列：#定義函數(shù)IsOrder()defIsOrder(pushV,popV):temp=[]foriinpushV:temp.append(i)whilelen(temp)andtemp[-1]==popV[0]:temp.pop()popV.pop(0)iflen(temp):returnFalseelse:returnTrue#主程序pushV=[1,2,3,4,5]popV=[4,5,3,2,1]print(IsOrder(pushV,popV))pushV=[1,2,3,4,5]popV=[4,3,5,1,2]print(IsOrder(pushV,popV))下圖所示是程序的運行結(jié)果。為什么是這樣？來看看程序中的4，3，5，1，2出棧序列。程序中設(shè)置一個臨時列表temp作為棧，用方法append()將pushV中的第1個元素放入temp中，這里是1；然后判斷棧頂元素是不是出棧順序的第1個元素（temp[-1]==popV[0]？）。由于此時popV[0]里是4，顯然1≠4，所以進(jìn)入for循環(huán)的下一輪，繼續(xù)將pushV的下一個元素壓入temp棧。這樣的過程一直進(jìn)行到滿足while循環(huán)中的相等條件，然后開始對popV做出棧操作。一個元素出棧，就將出棧順序向后移動一位，直到不相等，這樣的循環(huán)與壓棧過程結(jié)束，如果臨時棧temp不為空，說明彈出序列不是該棧的彈出順序，于是返回False。例10-21中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式。在計算由中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式的基本規(guī)則是：●如果遇到操作數(shù)，直接輸出到result?！駰？諘r遇到運算符，進(jìn)入棧stack?！裼龅阶罄ㄌ?，進(jìn)入棧stack。●遇到右括號，執(zhí)行出棧stack操作，并將出棧的元素輸出到result，直到彈出棧的是左括號，左括號不輸出。●遇到其他運算符（如+、-、*、/）時，彈出所有優(yōu)先級大于或等于該運算符的棧頂元素，然后將該運算符輸入棧stack?！褡罱K將棧中的元素依次彈出棧stack，輸出至result。

經(jīng)過上面的步驟，result中得到的就是轉(zhuǎn)換完成的后綴表達(dá)式。例如，中綴表達(dá)式“9+(3-1)×3+8÷2”轉(zhuǎn)換為后綴表達(dá)式后的結(jié)果是“931-3*+82/+”，整個步驟如下：（1）初始化棧，以供符號進(jìn)出棧使用。（2）第1個符號是數(shù)字“9”，根據(jù)規(guī)則，數(shù)字輸出到result，后面是“+”，進(jìn)棧stack。（3）第3個符號是左括號“（”，非數(shù)字，進(jìn)棧stack。（4）第4個符號是數(shù)字“3”，輸出到result。（5）第5個符號為“-”，非數(shù)字，進(jìn)棧stack，此時棧內(nèi)從棧底到棧頂為“+（-”。（6）第6個符號是數(shù)字“1”，輸出到result，此時按順序輸出表達(dá)式為“931”。（7）第7個符號是右括號“）”，需要去匹配之前的左括號“（”，于是棧頂元素依次出棧，直到出現(xiàn)左括號“（”，其上方只有“-”，輸出即可，此時表達(dá)式為“931-”。（8）第8個符號為“*”，因為此時棧頂符號為“+”，根據(jù)規(guī)則，“*”優(yōu)先級高于“+”，故“*”直接進(jìn)棧。（9）第9個符號為數(shù)字“3”，輸出到result，此時表達(dá)式為“931-3”。（10）第10個符號為“+”，此時的棧頂元素“*”優(yōu)先級高于它，根據(jù)規(guī)則，棧中元素需要一次輸出，直到出現(xiàn)比“+”更低的優(yōu)先級才停止，此時棧內(nèi)元素優(yōu)先級均不低于“+”，因此全部出棧，即表達(dá)式為“931-3*+”，然后這個“+”進(jìn)棧stack。（11）第11個符號為數(shù)字8，輸出到result。（12）第12個符號為“÷”，比棧內(nèi)符號“+”優(yōu)先級高，進(jìn)棧。（13）最后一個符號為數(shù)字“2”，輸出到result。（14）中綴表達(dá)式中的符號全部遍歷完，將棧stack中的符號依次輸出就可得到最后的后綴表達(dá)式結(jié)果。下面是編寫的由中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的函數(shù)IftoPf()，它將把從調(diào)用者那里傳遞過來的中綴表達(dá)式exp作為參數(shù)：defIftoPf(exp):result=[]#結(jié)果列表stack=[]#棧foriteminexp:ifitem.isnumeric():#如果當(dāng)前字符為數(shù)字，那么直接放入列表resultresult.append(item)else:#如果當(dāng)前字符為一切其他操作符iflen(stack)==0:#如果?？眨苯尤霔tackstack.append(item)elifitemin'*/(':#如果當(dāng)前字符為*/（，直接入棧stackstack.append(item)elifitem==')':#若遇右括號，則從stack彈出元素進(jìn)入result，直到碰見左括號t=stack.pop()whilet!='(':result.append(t)t=stack.pop()#如果當(dāng)前字符為加、減且棧頂為乘、除，則開始彈出elifitemin'+-'andstack[len(stack)-1]in'*/':ifstack.count('(')==0:#如果有左括號，彈出運算符到左括號為止whilestack:result.append(stack.pop())else:#如果沒有左括號，彈出所有t=stack.pop()whilet!='(':result.append(t)t=stack.pop()stack.append('(')stack.append(item)#彈出操作完成后將+、-入棧else:stack.append(item)#其余情況直接入棧（如當(dāng)前字符為+，棧頂為+、-）#表達(dá)式遍歷完，但棧中還有操作符不滿足彈出條件，把棧中的東西全部彈出whilestack:result.append(stack.pop())#返回字符串str="" #定義一個空字符串returnstr.join(result)#主程序print('\n')exp="3+(6*7-2)+2*3"print('中綴表達(dá)式'+exp+'的后綴表達(dá)式是：',end='')print(IftoPf(exp))print('\n