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

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

block,

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

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

經(jīng)過上面的步驟，result中得到的就是轉(zhuǎn)換完成的后綴表達(dá)式。例如，中綴表達(dá)式“9+(3-1)×3+8÷2”轉(zhuǎn)換為后綴表達(dá)式后的結(jié)果是“931-3*+82/+”，整個(gè)步驟如下：（1）初始化棧，以供符號(hào)進(jìn)出棧使用。（2）第1個(gè)符號(hào)是數(shù)字“9”，根據(jù)規(guī)則，數(shù)字輸出到result，后面是“+”，進(jìn)棧stack。（3）第3個(gè)符號(hào)是左括號(hào)“（”，非數(shù)字，進(jìn)棧stack。（4）第4個(gè)符號(hào)是數(shù)字“3”，輸出到result。（5）第5個(gè)符號(hào)為“-”，非數(shù)字，進(jìn)棧stack，此時(shí)棧內(nèi)從棧底到棧頂為“+（-”。（6）第6個(gè)符號(hào)是數(shù)字“1”，輸出到result，此時(shí)按順序輸出表達(dá)式為“931”。（7）第7個(gè)符號(hào)是右括號(hào)“）”，需要去匹配之前的左括號(hào)“（”，于是棧頂元素依次出棧，直到出現(xiàn)左括號(hào)“（”，其上方只有“-”，輸出即可，此時(shí)表達(dá)式為“931-”。（8）第8個(gè)符號(hào)為“*”，因?yàn)榇藭r(shí)棧頂符號(hào)為“+”，根據(jù)規(guī)則，“*”優(yōu)先級(jí)高于“+”，故“*”直接進(jìn)棧。（9）第9個(gè)符號(hào)為數(shù)字“3”，輸出到result，此時(shí)表達(dá)式為“931-3”。（10）第10個(gè)符號(hào)為“+”，此時(shí)的棧頂元素“*”優(yōu)先級(jí)高于它，根據(jù)規(guī)則，棧中元素需要一次輸出，直到出現(xiàn)比“+”更低的優(yōu)先級(jí)才停止，此時(shí)棧內(nèi)元素優(yōu)先級(jí)均不低于“+”，因此全部出棧，即表達(dá)式為“931-3*+”，然后這個(gè)“+”進(jìn)棧stack。（11）第11個(gè)符號(hào)為數(shù)字8，輸出到result。（12）第12個(gè)符號(hào)為“÷”，比棧內(nèi)符號(hào)“+”優(yōu)先級(jí)高，進(jìn)棧。（13）最后一個(gè)符號(hào)為數(shù)字“2”，輸出到result。（14）中綴表達(dá)式中的符號(hào)全部遍歷完，將棧stack中的符號(hào)依次輸出就可得到最后的后綴表達(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:#如果?？?，直接入棧stackstack.append(item)elifitemin'*/(':#如果當(dāng)前字符為*/（，直接入棧stackstack.append(item)elifitem==')':#若遇右括號(hào)，則從stack彈出元素進(jìn)入result，直到碰見左括號(hào)t=stack.pop()whilet!='(':result.append(t)t=stack.pop()#如果當(dāng)前字符為加、減且棧頂為乘、除，則開始彈出elifitemin'+-'andstack[len(stack)-1]in'*/':ifstack.count('(')==0:#如果有左括號(hào)，彈出運(yùn)算符到左括號(hào)為止whilestack:result.append(stack.pop())else:#如果沒有左括號(hào)，彈出所有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="" #定義一個(gè)空字符串returnstr.join(result)#主程序print('\n')exp="3+(6*7-2)+2*3"print('中綴表達(dá)式'+exp+'的后綴表達(dá)式是：',end='')print(IftoPf(exp))print('\n