第1章數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介2025/6/111主要內(nèi)容邏輯結(jié)構(gòu)物理結(jié)構(gòu)算法與結(jié)構(gòu)1.1邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)是指有限多個(gè)節(jié)點(diǎn)（結(jié)點(diǎn)，頂點(diǎn)，元素）之間的邏輯關(guān)系，不涉及節(jié)點(diǎn)（結(jié)點(diǎn)，頂點(diǎn)，元素）在計(jì)算機(jī)中的存儲(chǔ)位置。2025/6/112主要的邏輯結(jié)構(gòu)有線性結(jié)構(gòu)，樹形結(jié)構(gòu)，圖結(jié)構(gòu)和集合這四種結(jié)構(gòu)。⒈線性結(jié)構(gòu)2025/6/113在實(shí)際生活中，經(jīng)常遇到具有線性結(jié)構(gòu)的一組數(shù)據(jù)，比如，中國(guó)農(nóng)歷的二十四節(jié)氣：立春、雨水、驚蟄、春分、清明、谷雨、立夏、小滿、芒種、夏至、小暑、大暑、立秋、處暑、白露、秋分、寒露、霜降、立冬、小雪、大雪、冬至、小寒、大寒2025/6/114⒈線性結(jié)構(gòu)2025/6/115⒈線性結(jié)構(gòu)2025/6/116⒈線性結(jié)構(gòu)2025/6/1172025/6/1182.

樹結(jié)構(gòu)

2025/6/1192.

樹結(jié)構(gòu)用倒置的樹形示意一個(gè)樹2025/6/11102.

樹結(jié)構(gòu)一個(gè)樹T=(A,R)

由多個(gè)互不相交的樹構(gòu)成2025/6/11112.

樹結(jié)構(gòu)樹的每個(gè)結(jié)點(diǎn)至多有2個(gè)子結(jié)點(diǎn)，稱這樣的樹是二叉樹二叉查詢樹，特點(diǎn)是，每個(gè)結(jié)點(diǎn)上的值都大于等于它的左子樹上的結(jié)點(diǎn)里的值、小于它的右子樹上結(jié)點(diǎn)里的值。首先猜m是上面的二叉樹的根結(jié)點(diǎn)中的數(shù)，如果猜測(cè)錯(cuò)誤，反饋信息給你，你猜測(cè)的比根結(jié)點(diǎn)中的數(shù)大，那你就繼續(xù)猜測(cè)這個(gè)數(shù)是當(dāng)前結(jié)點(diǎn)的右子結(jié)點(diǎn)，如果告知你，你猜測(cè)的數(shù)不大于根結(jié)點(diǎn)中的數(shù)，那你就繼續(xù)猜測(cè)這個(gè)數(shù)是當(dāng)前節(jié)點(diǎn)的左子結(jié)點(diǎn)，依次類推，您可以較快的猜測(cè)到這個(gè)數(shù)。2025/6/11122.

樹結(jié)構(gòu)樹的層從上至下，從0層開始根結(jié)點(diǎn)沒(méi)有父結(jié)點(diǎn)，非根、非葉結(jié)點(diǎn)有且只有一個(gè)父結(jié)點(diǎn)，但有一個(gè)或多個(gè)子結(jié)點(diǎn)，葉結(jié)點(diǎn)有且只有一個(gè)父結(jié)點(diǎn)，但沒(méi)有子結(jié)點(diǎn)。根據(jù)樹結(jié)構(gòu)的這個(gè)特點(diǎn)，可以把樹的結(jié)點(diǎn)按層次分類：樹的結(jié)點(diǎn)按層次分類，從根開始定義，根為第0層，根的子結(jié)點(diǎn)為第1層，以此類推。每一層上的結(jié)點(diǎn)只能和上一層中的至多一個(gè)結(jié)點(diǎn)有關(guān)系，但可能和下一層的0個(gè)或多個(gè)結(jié)點(diǎn)有關(guān)系。2025/6/11133.

圖結(jié)構(gòu)鋼筋焊接起來(lái)的平面架中的焊點(diǎn)：a,b,c,d,e2025/6/11143.

圖結(jié)構(gòu)鋼筋焊接起來(lái)的平面架中的焊點(diǎn)：a,b,c,d,e

這個(gè)圖結(jié)構(gòu)中，人們規(guī)定(a,b)和(b,a)是一樣的（都代表同一根鋼筋），即(a,b)和(b,a)都是沒(méi)有方向的“標(biāo)量”邊，這樣的圖結(jié)構(gòu)稱作無(wú)向圖2025/6/11153.

圖結(jié)構(gòu)當(dāng)V×V的子集E滿足下列①和②時(shí)，稱E是V上的圖關(guān)系，記作G=(V,E)

2025/6/11163.

圖結(jié)構(gòu)當(dāng)V×V的子集E滿足下列①和②時(shí)，稱E是V上的圖關(guān)系，記作G=(V,E)

對(duì)于G=(V,E)，如果(a,b)是邊，那么默認(rèn)(b,a)也就是邊，并規(guī)定(a,b)邊等于(b,a)邊，這樣規(guī)定的G=(V,E)是無(wú)向圖，簡(jiǎn)稱V是無(wú)向圖，即無(wú)向圖的邊是沒(méi)有方向的。無(wú)向圖2025/6/11173.

圖結(jié)構(gòu)當(dāng)V×V的子集E滿足下列①和②時(shí)，稱E是V上的圖關(guān)系，記作G=(V,E)

如果(a,b)，(b,a)都是邊，就規(guī)定(a,b)邊不等于(b,a)邊，這樣規(guī)定的G=(V,E)是有向圖，簡(jiǎn)稱V是有向圖，即有向圖的邊是有方向的。2025/6/11184.

集合集合A中的元素除了同屬一個(gè)集合外，無(wú)其它任何關(guān)系，即關(guān)系集合是空集合，可表示為(A,?)（?是A×A的空子集）2025/6/1119對(duì)于(A,R)，計(jì)算機(jī)程序在存儲(chǔ)空間中存放集合A的節(jié)點(diǎn)（結(jié)點(diǎn)，頂點(diǎn)，元素）的形式，稱為A的節(jié)點(diǎn)（結(jié)點(diǎn)，頂點(diǎn)，元素）的物理結(jié)構(gòu)，也稱為A的存儲(chǔ)結(jié)構(gòu)。1.2物理結(jié)構(gòu)比如，對(duì)于一個(gè)線性表，可根據(jù)需要采用順序存儲(chǔ)（節(jié)點(diǎn)的物理地址是依次相鄰的）或鏈?zhǔn)酱鎯?chǔ)（節(jié)點(diǎn)的物理地址不必是相鄰的）。常用的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)和哈希存儲(chǔ)等，有關(guān)細(xì)節(jié)見(jiàn)后續(xù)的章節(jié)，例如，第4章至第11章2025/6/1120實(shí)施于集合上的算法，在其執(zhí)行完畢后，必須保持集合的邏輯結(jié)構(gòu)不變，比如，對(duì)于線性表，實(shí)施了增加或刪除節(jié)點(diǎn)的操作后，要保證新的節(jié)點(diǎn)構(gòu)成的集合仍然是線性結(jié)構(gòu)，否則算法必須對(duì)當(dāng)前的線性表的節(jié)點(diǎn)進(jìn)行調(diào)整，使得當(dāng)前線性表在邏輯上仍然是一個(gè)線性結(jié)構(gòu)。1.3算法與結(jié)構(gòu)有關(guān)細(xì)節(jié)見(jiàn)后續(xù)的章節(jié)，例如，第4章至第11章。算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)2025/6/1121使用的是Python3.11.5。為調(diào)試代碼方便每章的例子的代碼均保存在一個(gè)各自獨(dú)立的目錄中（例如第2章的例子1的代碼按utf-8編碼保存在“ch2\例子1”目錄中），并采用命令行行方式運(yùn)行Python程序。需要根據(jù)Python的安裝目錄設(shè)置，在系統(tǒng)環(huán)境中添加python.exe的所在的目錄為環(huán)境變量path的一個(gè)值。1.4Python版本算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可以根據(jù)本機(jī)Python的安裝路徑在命令行窗口臨時(shí)設(shè)置path的值，例如在命令行窗口輸入下列內(nèi)容回車確認(rèn)即可：pathC:\Users\gengx\AppData\Local\Programs\Python\Python311;%path%第2章算法復(fù)雜度2025/6/1122主要內(nèi)容●算法●算法的復(fù)雜度

●常見(jiàn)的復(fù)雜度2.1算法算法(algorithm)就是一個(gè)正確的計(jì)算過(guò)程，該過(guò)程取某個(gè)值或值的集合作為輸入并產(chǎn)生某個(gè)值或值的集合作為輸出。2025/6/11232025/6/1124算法的4個(gè)主要特性：2.1算法算法的4個(gè)主要特性是：●確切性：算法由語(yǔ)句組成，每個(gè)語(yǔ)句的功能是確切的。●輸入數(shù)據(jù)：可以向算法輸入多個(gè)或0個(gè)數(shù)據(jù)（方法可以有參數(shù)或無(wú)參數(shù)），即算法可以接收或不接收外部數(shù)據(jù)?！褫敵鰯?shù)據(jù)：算法可以給出明確的計(jì)算結(jié)果（方法的返回值）或輸出若干數(shù)據(jù)到客戶端以反映算法產(chǎn)生的效果?！窨尚行裕夯静僮鞫际窃谟邢迺r(shí)間內(nèi)被完成。所謂有限時(shí)間是指這個(gè)時(shí)值僅僅依賴于特定的硬件設(shè)施，不依賴于一個(gè)正整數(shù)n，即不會(huì)隨著n的增加而增大?！翊_切性●輸入數(shù)據(jù)●輸出數(shù)據(jù)●可行性2025/6/1125一個(gè)算法不能在有限的時(shí)間內(nèi)結(jié)束，就不屬于算法復(fù)雜度的研究的范疇，比如一個(gè)算法里出現(xiàn)的無(wú)限循環(huán)，就不再屬于算法復(fù)雜度的研究的范疇了2.2復(fù)雜度算法，從執(zhí)行到結(jié)束，涉及兩個(gè)度量：一個(gè)是執(zhí)行方法所消耗的時(shí)間，一個(gè)是執(zhí)行方法所需要的內(nèi)存空間。2025/6/1126方法里聲明的局部變量，包括參數(shù)都不歸類到基本操作，即不是基本操作。2.2復(fù)雜度⒈基本操作一個(gè)基本操作是一個(gè)語(yǔ)句或一個(gè)運(yùn)算表達(dá)式。一個(gè)基本操作是一條語(yǔ)句或一個(gè)運(yùn)算表達(dá)式，而且必須是在有限時(shí)間內(nèi)能被完成的計(jì)算步驟，其耗時(shí)僅僅依賴于特定的硬件設(shè)施，不依賴于一個(gè)正整數(shù)n，不會(huì)隨著n的增加而增大。2025/6/1127在計(jì)算算法執(zhí)行的基本操作的總數(shù)時(shí)，要真對(duì)最壞的情況，即在某種條件下執(zhí)行的基本操作的總數(shù)是最多的情況2.2復(fù)雜度3時(shí)間復(fù)雜度算法執(zhí)行的基本操作的總數(shù)T(n)。算法的復(fù)雜度主要是度量隨著n的增大，T(n)值的趨勢(shì)。2025/6/1128學(xué)習(xí)復(fù)雜度，記住一個(gè)通俗的道理：時(shí)間累加，空間不累加.2.2復(fù)雜度4復(fù)雜度比較2025/6/11292.3常見(jiàn)復(fù)雜度⒈O(jiān)(1)復(fù)雜度算法中的基本操作被執(zhí)行的總次數(shù)是一個(gè)常量，即不依賴一個(gè)正整數(shù)n、不會(huì)隨著n的增加而增大，那么將算法的時(shí)間復(fù)雜度，記作O(1)。算法中的所占用的內(nèi)存是一個(gè)常量，即所占內(nèi)存不依賴一個(gè)正整數(shù)n、不會(huì)隨著n的增加而增大，那么將算法的空間復(fù)雜度，記作O(1)。

例子1計(jì)算最大值A(chǔ)LG2_1.pych2_1.py2025/6/11302.3常見(jiàn)復(fù)雜度1.O(1)復(fù)雜度

sum()函數(shù)中return語(yǔ)句被執(zhí)行了一次，range(1,101)被重復(fù)執(zhí)行了101次，賦值語(yǔ)句“sum_result+=i;”重復(fù)了100次。那么算法中的基本操作被執(zhí)行的總數(shù)是202，是一個(gè)常量，因此時(shí)間復(fù)雜度是O(1)。sum()函數(shù)中有兩個(gè)局部變量sum_result和i，而兩個(gè)變量占用內(nèi)存的大小都是固定的，因此空間復(fù)雜度是O(1).

ALG2_2.py

ch2_2.py2025/6/11312.3常見(jiàn)復(fù)雜度2.O(n)復(fù)雜度

2025/6/11322.3常見(jiàn)復(fù)雜度2.O(n)復(fù)雜度

ALG2_3.py

ch2_3.py

2025/6/11332.3常見(jiàn)復(fù)雜度2.O(n)復(fù)雜度例子4求數(shù)組元素的最大值A(chǔ)LG2_4.py

ch2_4.py

2025/6/11342.3常見(jiàn)復(fù)雜度2.O(n)復(fù)雜度例子5尋找缺失的一個(gè)自然數(shù)ALG2_5.pych2_5.py例子5尋找缺失的一個(gè)自然數(shù)

2025/6/11352.3常見(jiàn)復(fù)雜度2.O(n)復(fù)雜度例子5

find_missing_number(inta[],intlength)算法中的基本操作不是加法和減法，而是使用了異或^運(yùn)算。

find_number(arr,length)的算法和前面兩者不同，算法使用的是窮舉法，算法中的for語(yǔ)句里嵌套了for語(yǔ)句形成的雙層循環(huán)，不難驗(yàn)證其時(shí)間復(fù)雜度是O(n^2)。ALG2_5.py2025/6/11362.3常見(jiàn)復(fù)雜度3.2025/6/11372.3常見(jiàn)復(fù)雜度3.

ALG2_6.py

ch2_6.py

2025/6/11382.3常見(jiàn)復(fù)雜度3.例子7起泡法排序ALG2_7.py

ch2_7.py2025/6/11392.3常見(jiàn)復(fù)雜度4.

2025/6/11402.3常見(jiàn)復(fù)雜度4.例子8ALG2_8.py

ch2_8.py

2025/6/11412.3常見(jiàn)復(fù)雜度5.

2025/6/11422.3常見(jiàn)復(fù)雜度5.例子9二分法ALG2_9.py

ch2_9.py

2025/6/11432.3常見(jiàn)復(fù)雜度5.例子10歐幾里得算法ALG2_10.pych2_10.py

2025/6/11442.3常見(jiàn)復(fù)雜度6.

如果一個(gè)函數(shù)里又調(diào)用了其它函數(shù)，即一個(gè)算法又包含另外一個(gè)算法，那么該函數(shù)的復(fù)雜度將和它包含的函數(shù)復(fù)雜度有關(guān)，需合并考察復(fù)雜度。

2025/6/11452.3常見(jiàn)復(fù)雜度6.例子11使用二分法查找一個(gè)數(shù)組在另一個(gè)數(shù)組中的值

ALG2_11.py

ch2_11.py

2025/6/11462.3常見(jiàn)復(fù)雜度6.例子12數(shù)組所有元素值的最大公約數(shù)ALG2_12.pych2_12.py

2025/6/11472.3常見(jiàn)復(fù)雜度7.復(fù)雜度比較

程序中大部分算法都是這些復(fù)雜度中之一，除非特別需要，后續(xù)章節(jié)不再給出每個(gè)方法的復(fù)雜度。復(fù)雜度的比較規(guī)則：第3章遞歸算法2025/6/1148主要內(nèi)容● 遞歸算法●線性與非線性遞歸● 遞歸的復(fù)雜度● 問(wèn)題與子問(wèn)題● 遞歸與迭代● 多重遞歸● 經(jīng)典遞歸● 優(yōu)化遞歸遞歸算法是非常最重的算法，是很多算法的基礎(chǔ)算法。遞歸算法不僅能使得代碼優(yōu)美簡(jiǎn)練，容易理解解決問(wèn)題的思路或發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律，而且具有很好的可讀性。和排序算法不同，許多經(jīng)典的排序算法已經(jīng)是玲瓏剔透、日臻完善，在許多應(yīng)用中只要選擇一種排序算法直接使用即可（見(jiàn)第4章和第12章），而對(duì)于遞歸算法，真正理解遞歸算法內(nèi)部運(yùn)作機(jī)制的細(xì)節(jié)、才能真對(duì)實(shí)際問(wèn)題正確的使用遞歸算法或?qū)懗稣_的遞歸算法。3.1遞歸算法遞歸算法是指一個(gè)函數(shù)在執(zhí)行過(guò)程中又調(diào)用了自身、形成了遞歸調(diào)用，這樣的函數(shù)被稱為遞歸函數(shù)或遞歸算法。2025/6/1149

2025/6/11503.1遞歸算法遞歸過(guò)程中的壓棧、彈棧函數(shù)f遞歸過(guò)程是，第k次調(diào)用f需要等待第k+1次調(diào)用f結(jié)束執(zhí)行過(guò)程后才能結(jié)束執(zhí)行過(guò)程。那么第R(n)次（最后一次）調(diào)用f結(jié)束執(zhí)行過(guò)程后，就會(huì)依次使得第k次調(diào)用結(jié)束執(zhí)行過(guò)程。函數(shù)被調(diào)用時(shí)，函數(shù)的（入口）地址會(huì)被壓入棧（棧是一種先進(jìn)后出的結(jié)構(gòu)）中，稱為壓棧操作，同時(shí)函數(shù)的局部變量被分配內(nèi)存空間。

……調(diào)用調(diào)用調(diào)用調(diào)用調(diào)用結(jié)束

結(jié)束

結(jié)束

結(jié)束結(jié)束

圖3.1遞歸執(zhí)行過(guò)程第1次調(diào)用第R(n)次調(diào)用2025/6/11513.1遞歸算法遞歸過(guò)程中的壓棧、彈棧函數(shù)調(diào)用結(jié)束，會(huì)進(jìn)行彈棧，稱為彈棧操作，同時(shí)釋放函數(shù)的局部變量所占的內(nèi)存。遞歸過(guò)程的壓棧操作可以讓棧的長(zhǎng)度不斷增加，而彈棧操作會(huì)讓棧的長(zhǎng)度變小，最終使棧的長(zhǎng)度為0?！?/p>

第1次彈棧第m次彈棧第k次彈棧第1次壓棧第m次壓棧第k次壓棧2025/6/11523.1遞歸算法時(shí)間復(fù)雜度函數(shù)調(diào)用結(jié)束，會(huì)進(jìn)行彈棧，稱為彈棧操作，同時(shí)釋放函數(shù)的局部變量所占的內(nèi)存。要針對(duì)具體的遞歸函數(shù)，來(lái)計(jì)算該遞歸函數(shù)的時(shí)間復(fù)雜度。遞歸函數(shù)是一個(gè)遞歸過(guò)程，從遞歸開始到遞歸結(jié)束，函數(shù)被調(diào)的總數(shù)R(n)是依賴于一個(gè)正整數(shù)n的函數(shù)。那么遞歸函數(shù)中基本操作被執(zhí)行的總數(shù)T(n)就依賴遞歸的總數(shù)R(n)和每次遞歸時(shí)基本操作被執(zhí)行的總數(shù)。2025/6/11533.1遞歸算法空間復(fù)雜度函數(shù)調(diào)用結(jié)束，會(huì)進(jìn)行彈棧，稱為彈棧操作，同時(shí)釋放函數(shù)的局部變量所占的內(nèi)存。遞歸會(huì)讓棧的長(zhǎng)度不斷發(fā)生變化，如果棧的長(zhǎng)度較大可能導(dǎo)致棧溢出，使得進(jìn)程（運(yùn)行的程序）被操作系統(tǒng)終止。遞歸過(guò)程的壓棧操作增加棧的長(zhǎng)度、彈棧操作減小棧的長(zhǎng)度。遞歸過(guò)程中可能交替地進(jìn)行壓棧操作和彈棧操作，直至棧的長(zhǎng)度為0（見(jiàn)例子2）。計(jì)算出遞歸過(guò)程中，某一時(shí)刻（某一次遞歸）棧出現(xiàn)的最大長(zhǎng)度和每次遞歸中函數(shù)的局部變量所占的內(nèi)存空間，即計(jì)算出棧最大長(zhǎng)度以及局部變量所占的全部?jī)?nèi)存空間和所依賴的正整數(shù)的關(guān)系，才可以知道空間復(fù)雜度。2025/6/11543.2線性遞歸與非線性遞歸●線性遞歸線性遞歸是指，每次遞歸時(shí)，函數(shù)調(diào)用自身一次。如果我們忘記了今天是星期幾，就需要知道昨天是星期幾，如此這般地向前（過(guò)去）翻日歷（相當(dāng)于遞歸里的壓棧，導(dǎo)致棧的長(zhǎng)度在增加），等到能翻到某個(gè)日歷頁(yè)上顯示了星期幾，就結(jié)束翻閱日歷（相當(dāng)于結(jié)束壓棧），然后再一頁(yè)一頁(yè)的撕掉日歷（相當(dāng)于彈棧），日歷上神奇地出現(xiàn)了星期數(shù)，即函數(shù)依次計(jì)算出自己的返回值。ALG3_1.py

ch3_1.py

ch3_1.py中，假設(shè)元旦是星期一，輸出這一年的第168天是星期日.2025/6/11553.2線性遞歸與非線性遞歸●線性遞歸遞歸函數(shù)f(n)的遞歸的總次數(shù)：R(n)=n，而每次遞歸的基本操作只有2個(gè)基本操作，因此時(shí)間復(fù)雜度是O(n)。向下方向的弧箭頭表示函數(shù)被調(diào)用，向上方向的直箭頭表示函數(shù)調(diào)用結(jié)束。例子1壓棧操作過(guò)程中得到的棧的最大長(zhǎng)度是R(n)=n，空間復(fù)雜度是O(n)。2025/6/11563.2線性遞歸與非線性遞歸●非線性遞非線性遞歸是指，每次遞歸時(shí)函數(shù)調(diào)用自身2次或2次以上。ALG3_2.py例子2遞歸與Fibonacci序列ch3_2.py

Fibonacci數(shù)列的特點(diǎn)是，前2項(xiàng)的值都是1，從第3項(xiàng)開始，每項(xiàng)的值是前兩項(xiàng)值的和。Fibonacci序列如下：1,1,2,3,5,8,13,21,…2025/6/11573.2線性遞歸與非線性遞歸●非線性遞例子2遞歸過(guò)程中，每次遞歸時(shí)函數(shù)調(diào)用自身2次，使得每次遞歸出現(xiàn)了2個(gè)遞歸“分支”，然后選擇一個(gè)分支，繼續(xù)遞歸，直到該分支遞歸結(jié)束，再沿著下一分支繼續(xù)遞歸，當(dāng)2個(gè)分支都遞歸結(jié)束，遞歸過(guò)程才結(jié)束，而且遞歸過(guò)程交替地進(jìn)行壓棧和彈棧操作，直至棧的長(zhǎng)度為0。

2025/6/11583.3問(wèn)題與子問(wèn)題將規(guī)模大的問(wèn)題，使用遞歸算法逐步分解成規(guī)模小的問(wèn)題，最終解決規(guī)模大的問(wèn)題。一個(gè)問(wèn)題的子問(wèn)題就是數(shù)據(jù)規(guī)模比此問(wèn)題的規(guī)模更小的問(wèn)題。當(dāng)一個(gè)問(wèn)題，可以分解成許多子問(wèn)題時(shí)就可以考慮用遞歸算法來(lái)解決這個(gè)問(wèn)題。2025/6/11593.3問(wèn)題與子問(wèn)題

ALG3_3.py

ch3_3.py2025/6/11603.3問(wèn)題與子問(wèn)題

ALG3_4.py例子4反轉(zhuǎn)（倒置）字符序列ch3_4.py

2025/6/11613.4遞歸與迭代遞歸的思想是根據(jù)上一次操作的結(jié)果，確定當(dāng)前操作的結(jié)果。迭代的思想是，根據(jù)當(dāng)前操作的結(jié)果，確定下一次操作的結(jié)果。對(duì)于解決相同的問(wèn)題，遞歸代碼簡(jiǎn)練，容易理解解決問(wèn)題的思路或發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律，具有很好的可讀性。由于迭代不涉及方法的遞歸調(diào)用，所以，通常情況下遞歸算法的空間復(fù)雜度會(huì)大于迭代的復(fù)雜度，當(dāng)遞歸過(guò)程的遞歸總數(shù)比較大時(shí)，會(huì)導(dǎo)致棧溢出。2025/6/11623.4遞歸與迭代

computePI.py例子5計(jì)算圓周率的近似值ch3_5.py

2025/6/11633.4遞歸與迭代ALG3_6.py例子6判斷某個(gè)數(shù)是否是有序數(shù)組的元素值ch3_6.py

2025/6/11643.4遞歸與迭代ALG3_7.py例子7求兩個(gè)正整數(shù)的最大公約數(shù)ch3_7.py

2025/6/11653.5多重遞歸所謂多重遞歸，是指一個(gè)遞歸方法調(diào)用另一個(gè)或多個(gè)遞歸方法，稱該遞歸方法多重遞歸方法。

不要求輸出含有偶數(shù)多個(gè)6的數(shù)。

2025/6/11663.5多重遞歸

ALG3_8.pych3_8.py例子82025/6/11673.6經(jīng)典遞歸選擇三個(gè)經(jīng)典的遞歸：楊輝三角形、老鼠走迷宮和漢諾塔，進(jìn)一步體會(huì)遞歸算法不僅能使得代碼優(yōu)美簡(jiǎn)練，容易理解解決問(wèn)題的思路或發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律，而且具有很好的可讀性。特別是漢諾塔遞歸，通過(guò)其遞歸算法，洞悉其數(shù)據(jù)規(guī)律，給出相應(yīng)的迭代算法。經(jīng)典的遞歸：楊輝三角形，老鼠走迷宮，漢諾塔2025/6/11683.6經(jīng)典遞歸楊輝三角

最早出現(xiàn)于中國(guó)南宋數(shù)學(xué)家楊輝1261年所著的《詳解九章算法》中。法國(guó)數(shù)學(xué)家帕斯卡（Pascal）在1654年發(fā)現(xiàn)該三角形，所以又稱帕斯卡三角形。

2025/6/11693.6經(jīng)典遞歸楊輝三角最早出現(xiàn)于中國(guó)南宋數(shù)學(xué)家楊輝1261年所著的《詳解九章算法》中。法國(guó)數(shù)學(xué)家帕斯卡（Pascal）在1654年發(fā)現(xiàn)該三角形，所以又稱帕斯卡三角形。

2025/6/11703.6經(jīng)典遞歸ALG3_9.py例子9輸出楊輝三角形ch3_9.py楊輝三角

2025/6/11713.6經(jīng)典遞歸老鼠走迷宮

老鼠首先向東走，如果走到出口結(jié)束遞歸，否則向南…向西…向北。

2025/6/11723.6經(jīng)典遞歸老鼠走迷宮ALG3_10.py中的move(a,rows,cols,i,j)是老鼠走迷宮的函數(shù)，該函數(shù)是一個(gè)遞歸函數(shù)。ALG3_10.py例子10模擬老鼠走迷宮ch3_10.py老鼠走過(guò)迷宮后，輸出老鼠走過(guò)的路時(shí)，用m表示老鼠走過(guò)的路，Y表示老鼠到達(dá)的出口。

2025/6/11733.6經(jīng)典遞歸漢諾塔（遞歸算法）漢諾塔(HanoiTower)問(wèn)題是來(lái)源于印度的一個(gè)古老問(wèn)題。有名字為A，B，C的三個(gè)塔，A塔上有從小到大64個(gè)盤子，每次搬運(yùn)一個(gè)盤子，最后要把64個(gè)盤子搬運(yùn)到C塔。在搬運(yùn)盤子的過(guò)程中，可以把盤子暫時(shí)放在3個(gè)塔中的任何一個(gè)上，但不允許大盤放在小盤上面。3個(gè)盤子的漢諾塔

2025/6/11743.6經(jīng)典遞歸漢諾塔（遞歸算法）3個(gè)盤子的漢諾塔

ALG3_11.py例子11漢諾塔的遞歸算法ch3_11.py2025/6/11753.6經(jīng)典遞歸漢諾塔（迭代算法）

這些規(guī)律是通過(guò)研究漢諾塔的遞歸算法發(fā)現(xiàn)的。就像本章一開始說(shuō)的，遞歸可以發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律。2025/6/11763.6經(jīng)典遞歸漢諾塔（迭代算法）

一個(gè)偶數(shù)通過(guò)不斷地右位移可計(jì)算出尾部連續(xù)的0的個(gè)數(shù)，例如：8的二進(jìn)制1000右位移3次，得到奇數(shù)，因此知道8的二進(jìn)制尾部連續(xù)0的個(gè)數(shù)是3。這些規(guī)律是通過(guò)研究漢諾塔的遞歸算法發(fā)現(xiàn)的。就像本章一開始說(shuō)的，遞歸可以發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律。2025/6/11773.6經(jīng)典遞歸漢諾塔（迭代算法）這些規(guī)律是通過(guò)研究漢諾塔的遞歸算法發(fā)現(xiàn)的。就像本章一開始說(shuō)的，遞歸可以發(fā)現(xiàn)數(shù)據(jù)的內(nèi)部的邏輯規(guī)律。更具①至⑤的規(guī)律給出的迭代算法，盡管時(shí)間復(fù)雜度和例子11中的遞歸算法相同，空間復(fù)雜度低于遞歸算法，但簡(jiǎn)練性和可讀性遠(yuǎn)遠(yuǎn)不如遞歸算法。在內(nèi)存允許的范圍內(nèi)，還是遞歸算法更好。ALG3_12.py例子12漢諾塔的迭代算法ch3_12.py

2025/6/1178計(jì)算Fibonacci序列的遞歸過(guò)程中需要將f(n-1)分支進(jìn)行完畢，再進(jìn)行f(n-2)分支。需要注意到的是，在進(jìn)行f(n-1)分支遞歸時(shí)，會(huì)完成了f(n-2)分支遞歸，那么再進(jìn)行f(n-2)分支就是一個(gè)重復(fù)的遞歸過(guò)程。簡(jiǎn)而言之，優(yōu)化遞歸就是避免重復(fù)子遞歸。優(yōu)化遞歸就是在每次遞歸開始前，首先到某個(gè)對(duì)象中，通常為散列表對(duì)象，也可以是數(shù)組，查找本次遞歸是否已經(jīng)被實(shí)施完畢，即是否已經(jīng)有了遞歸結(jié)果，如果散列表對(duì)象中已經(jīng)有了本次遞歸的結(jié)果，就直接使用這個(gè)結(jié)果，不再浪費(fèi)時(shí)間進(jìn)行本次遞歸，否則就進(jìn)行本次遞歸，并將遞歸結(jié)果保存到散列表對(duì)象。3.7優(yōu)化遞歸2025/6/11793.7優(yōu)化遞歸ALG3_13.py例子13優(yōu)化Fibonacci數(shù)列的遞歸算法ch3_13.py

2025/6/11803.7優(yōu)化遞歸ALG3_14.py例子14優(yōu)化楊輝三角形的遞歸算法ch3_14.py

也可以使用函數(shù)緩存技術(shù)來(lái)優(yōu)化遞歸，但函數(shù)緩存對(duì)函數(shù)的參數(shù)類型有較嚴(yán)格的限制，細(xì)節(jié)見(jiàn)第12章的12.8節(jié)。第4章數(shù)組2025/6/1181

數(shù)組是Python中非常基礎(chǔ)的一種順序存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，也被稱為順序表，首先介紹順序表，然后介紹數(shù)組。順序表的特點(diǎn)；

array類；數(shù)組與圍圈留一問(wèn)題；數(shù)組與參數(shù)存值；數(shù)組與穩(wěn)定排序；二分法與數(shù)組；數(shù)組的相等；數(shù)組與洗牌。4.1順序表的特點(diǎn)2025/6/1182順序表也是線性表的一種具體體現(xiàn)，順序表節(jié)點(diǎn)形成的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)、節(jié)點(diǎn)的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)，即節(jié)點(diǎn)的物理地址是依次相鄰的。注意：由于順序表使用數(shù)組實(shí)現(xiàn)順序存儲(chǔ)，因此也稱順序表的節(jié)點(diǎn)為元素。2025/6/11834.1順序表的特點(diǎn)順序表使用數(shù)組來(lái)實(shí)現(xiàn)，順序表的節(jié)點(diǎn)的物理地址是依次相鄰的，因此可以隨機(jī)訪問(wèn)任何一個(gè)節(jié)點(diǎn)，不必從頭節(jié)點(diǎn)計(jì)數(shù)查找其它節(jié)點(diǎn)。1查詢節(jié)點(diǎn)

2025/6/11844.1順序表的特點(diǎn)

3刪除節(jié)點(diǎn)

4.2array類2025/6/1185Python的array模塊（數(shù)組模塊）提供了array類，該array類可為用戶程序?qū)崿F(xiàn)動(dòng)態(tài)數(shù)組（屬于順序表結(jié)構(gòu)）。array模塊的array類同時(shí)也提供了操作數(shù)組的方法，例如添加元素、插入元素、刪除元素等方法（Python中把獨(dú)立的算法稱作函數(shù)，把和類有關(guān)的算法稱作方法）。2025/6/11864.2array類1.創(chuàng)建數(shù)組注意：無(wú)法動(dòng)態(tài)指定數(shù)組的大小，即元素的個(gè)數(shù)。

使用array模塊的array類的構(gòu)造函數(shù)array(typecode,initalize)創(chuàng)建數(shù)組時(shí)需要指定數(shù)組的元素的類型和初始元素，即指定typecode的具體類型和initalize的具體值。

2025/6/11874.2array類2.數(shù)組的使用3.數(shù)組的長(zhǎng)度數(shù)組通過(guò)索引來(lái)訪問(wèn)元素，索引從0開始，例如：

使用Python提供的內(nèi)置len()函數(shù)來(lái)獲取數(shù)組的長(zhǎng)度。例如：2025/6/11884.2array類4.數(shù)組的引用array數(shù)組屬于引用型變量。如果兩個(gè)array數(shù)組具有相同的引用，他們就有完全相同的元素。2025/6/11894.2array類5.數(shù)組的復(fù)制可以用已有的數(shù)組arr得到一個(gè)新的數(shù)組arr_new，新數(shù)組arr_new和arr的元素值相同，但二者是兩個(gè)不同的數(shù)組。2025/6/11904.2array類6.array類的常用方法（1）append(value)：在數(shù)組末尾添加一個(gè)新元素2025/6/11914.2array類6.array類的常用方法（2）extend(iterable)：在數(shù)組末尾添加一個(gè)可迭代對(duì)象中的所有元素（3）insert(index,value)：在指定索引位置插入一個(gè)值為value的新元素2025/6/11924.2array類6.array類的常用方法（4）remove(value)：移除數(shù)組中的第一個(gè)匹配指定值value的元素（5）pop(index)：移除指定元素并返回該元素的值，如果不指定index的值，即pop()移除尾元素并返回尾元素的值。2025/6/11934.2array類6.array類的常用方法index(value)：從索引開始0開始至數(shù)組最后一個(gè)索引查找第一個(gè)匹配指定值value的元素的索引（如果沒(méi)有找到返回-1）；index(value,start)從索引start開始至數(shù)組最后一個(gè)索引查找第一個(gè)匹配指定值value的元素的索引（如果沒(méi)有找到返回-1）。2025/6/11944.2array類6.array類的常用方法（7）count(value)：返回?cái)?shù)組中指定值value出現(xiàn)的次數(shù)。（8）reverse()：將數(shù)組的元素值反轉(zhuǎn)。（9）tolist()：返回和數(shù)組有相同元素值的列表。2025/6/11954.2array類7.array數(shù)組的類型array模塊中的數(shù)組類型可以是基本的類型，即類型可以是以下幾種：'b'：有符號(hào)字節(jié)(signedchar)'B'：無(wú)符號(hào)字節(jié)(unsignedchar)'u'：Unicode字符(Py_UNICODE)'h'：有符號(hào)短整數(shù)(signedshort)'H'：無(wú)符號(hào)短整數(shù)(unsignedshort)'i'：有符號(hào)整數(shù)(signedint)'I'：無(wú)符號(hào)整數(shù)(unsignedint)'l'：有符號(hào)長(zhǎng)整數(shù)(signedlong)'L'：無(wú)符號(hào)長(zhǎng)整數(shù)(unsignedlong)'f'：?jiǎn)尉雀↑c(diǎn)數(shù)(float)'d'：雙精度浮點(diǎn)數(shù)(double)array模塊中的數(shù)組類型不支持對(duì)象，即不能在array數(shù)組中直接存儲(chǔ)Python對(duì)象，如字符串、列表、字典等。4.3數(shù)組與圍圈留一問(wèn)題

圍圈留一是一個(gè)古老的問(wèn)題（也稱約瑟夫問(wèn)題）：若干個(gè)人圍成一圈，從某個(gè)人開始順時(shí)針（或逆時(shí)針）數(shù)到第3個(gè)人，該人從圈中退出，然后繼續(xù)順時(shí)針（或逆時(shí)針）數(shù)到第3個(gè)人，該人從圈中退出，以此類推，程序輸出圈中最后剩下的一個(gè)人。2025/6/11962025/6/11974.3數(shù)組與圍圈留一問(wèn)題例子1圍圈留一問(wèn)題可以簡(jiǎn)化為向左旋轉(zhuǎn)數(shù)組（向右），旋轉(zhuǎn)數(shù)組兩次即可確定出退出圈中的人，即此時(shí)數(shù)組首元素（末尾元素）中的號(hào)碼就應(yīng)該是要退出圈中的人。ch4_1.py

4.4數(shù)組與參數(shù)存值如果兩個(gè)數(shù)組的引用相同，那么這兩個(gè)數(shù)組的元素就完全相同，因此一個(gè)函數(shù)可以將某些數(shù)據(jù)存放在數(shù)組參數(shù)中，那么函數(shù)執(zhí)行完畢，保存在數(shù)組元素中的值一直還存在、不會(huì)消失。2025/6/11982025/6/11994.4數(shù)組與參數(shù)存值例子2數(shù)組存放三角形面積ch4_2.pyALG4_2.pyALG4_2.py中的函數(shù)judge_triangle(a,b,c,area)，當(dāng)a，b，c構(gòu)成等邊三角形時(shí)返回3，將三角形面積存放在數(shù)組area的元素中；當(dāng)構(gòu)成等腰（不是等邊）三角形時(shí)返回2，將三角形面積存放在數(shù)組area的元素中；當(dāng)構(gòu)成普通（不是等邊，也不是等腰）三角形時(shí)返回1，將三角形面積存放在數(shù)組area的元素中；當(dāng)不構(gòu)成三角形時(shí)返回0，將nan（notanumber）存放在數(shù)組area的元素中.2025/6/111004.4數(shù)組與參數(shù)存值例子2出現(xiàn)次數(shù)最多的字母ch4_3.pyALG4_3.pyALG4_3.py中的find_max_count_letters(english,saveCount)函數(shù)返回english中出現(xiàn)次數(shù)最多的字母之一，并將這個(gè)字母出現(xiàn)的次數(shù)和他在english中的索引存放到參數(shù)指定的saveCount數(shù)組的元素中。4.5數(shù)組與穩(wěn)定排序2025/6/11101

2025/6/111024.5數(shù)組與穩(wěn)定排序1.sorted(arr)函數(shù)sorted(arr)函數(shù)不會(huì)修改原始數(shù)組arr，而是創(chuàng)建一個(gè)新的數(shù)組來(lái)保存排序結(jié)果,并返回新數(shù)組的引用。向sorted(arr,reverse=True或False)傳遞第二個(gè)參數(shù)的值是reverse=True，讓sorted()函數(shù)按降序排序。2025/6/111034.5數(shù)組與穩(wěn)定排序2.比較函數(shù)與排序sortd(arr,key=比較函數(shù))：讓數(shù)組arr的元素值按著“比較函數(shù)”的返回值進(jìn)行排序。讓整數(shù)按個(gè)位數(shù)字的大小排序2025/6/111044.5數(shù)組與穩(wěn)定排序3.Lambda表達(dá)式與排序2025/6/111054.5數(shù)組與穩(wěn)定排序3.Lambda表達(dá)式與排序sortd(arr,key=Lambda)：讓數(shù)組的元素值按著Lambda表達(dá)式的返回值進(jìn)行排序。按整數(shù)平方大小排序2025/6/111064.5數(shù)組與穩(wěn)定排序例子4穩(wěn)定排序與不穩(wěn)定排序ch4_4.py起泡法和插入法是穩(wěn)定排序，而選擇法是不穩(wěn)定排序。不穩(wěn)定排序改變了個(gè)位數(shù)字相同的兩個(gè)整數(shù)在數(shù)組中的前后位置。排序前263在33的前面，選擇法（不穩(wěn)定）排序后導(dǎo)致263在33的后面。4.6二分法與數(shù)組2025/6/11107

在Python語(yǔ)言中，對(duì)于array模塊的數(shù)組arr：numinarr的時(shí)間復(fù)雜度是O(n)，因?yàn)樗鼤?huì)遍歷整個(gè)數(shù)組來(lái)查找元素num。2025/6/111084.6二分法與數(shù)組二分法是成熟的經(jīng)典算法，所以Python將其作為內(nèi)置模塊bisect中的一個(gè)函數(shù):bisect_left(arr,value)(該函數(shù)使用的是二分法）,如果在有序數(shù)組arr中找到一個(gè)元素值是value，該函數(shù)返回此元素的索引，如果沒(méi)有找到這樣的元素該返函數(shù)回?cái)?shù)組arr的長(zhǎng)度。2025/6/111094.6二分法與數(shù)組例子5用二分法統(tǒng)計(jì)數(shù)字出現(xiàn)的次數(shù)ch4_5.py

4.7數(shù)組的相等2025/6/11110兩個(gè)數(shù)組可以通過(guò)==運(yùn)算符比較二者是否相等。當(dāng)兩個(gè)數(shù)組arr1、arr2的元素值依次一一對(duì)應(yīng)相等時(shí)arr1==arr2表達(dá)式的值是True，否則是False。另外，數(shù)組arr1也可以取索引start~end之間的元素(不含end索引的元素)和數(shù)組arr2比較是否相等：arr1[start:end]==arr22025/6/111114.7數(shù)組的相等例子6尋找單詞并輸出單詞出現(xiàn)的次數(shù)ch4_6.pych4_6.py中的find_word(s,word)函數(shù)輸出s中出現(xiàn)的word并返回word出現(xiàn)的次數(shù).4.8數(shù)組與洗牌2025/6/11112

2025/6/111134.8數(shù)組與洗牌例子7Fisher-Yates洗牌算法

ch4_7.py第5章列表2025/6/11114Python中的列表；

列表與排序；列表與隨機(jī)布雷；列表與隨機(jī)數(shù)；列表與篩選法；列表與全排列；列表與組合；列表與生命游戲。列表的公共子列表列表與堆5.1Python中的列表2025/6/11115list類是Python的內(nèi)置類，稱其實(shí)例為列表。列表是Python語(yǔ)言里最常用和靈活的一種數(shù)據(jù)結(jié)構(gòu)。可以直接使用列表，不需要事先導(dǎo)入特定的模塊。列表的元素類型可以是Python容許的任何類型，這使得列表比數(shù)組有更強(qiáng)的處理數(shù)據(jù)的能力。相對(duì)array數(shù)組，列表的內(nèi)部結(jié)構(gòu)會(huì)更加復(fù)雜、也會(huì)占用更多的存儲(chǔ)空間，如果僅僅處理基本型數(shù)據(jù)，數(shù)組會(huì)占有更少的存儲(chǔ)空間，也會(huì)有更好的效率。2025/6/111165.1Python中的列表1.創(chuàng)建列表或具有初始元素的列表使用空的方括號(hào)[]或列表的構(gòu)造函數(shù)創(chuàng)建一個(gè)空列表（不含任何元素的列表）可以在方括號(hào)中列出列表的初始元素（用逗號(hào)分隔）來(lái)創(chuàng)建一個(gè)非空列表可以將一個(gè)可迭代對(duì)象（如數(shù)組、字符串、集合等）傳遞給列表的構(gòu)造函數(shù)來(lái)創(chuàng)建列表2025/6/111175.1Python中的列表2.遍歷列表可以使用for語(yǔ)句遍歷列表，for語(yǔ)句遍歷列表時(shí)每次訪問(wèn)列表中的一個(gè)元素列表可以使用索引（索引從0開始）訪問(wèn)自己的元素，因此也可以使用索引遍歷列表2025/6/111185.1Python中的列表3.列表的常用方法（1）append(value):向列表末尾添加一個(gè)值為value的元素（2）extend(iterable):將可迭代對(duì)象iterable中的元素添加到當(dāng)前列表的末尾2025/6/111195.1Python中的列表3.列表的常用方法（3）insert(index,value):在指定index索引的前面插入一個(gè)值為value的元素(列表的索引從0開始)，插入新元素后，列表自動(dòng)更新所有元素的索引。2025/6/111205.1Python中的列表3.列表的常用方法（4）remove(value):刪除列表中第一個(gè)值是value的元素。2025/6/111215.1Python中的列表3.列表的常用方法（5）pop(index):刪除索引是index的元素并返回該元素的值，

pop()：刪除尾元素并返回尾元素的值。

2025/6/111225.1Python中的列表3.列表的常用方法（6）index(value):返回第一個(gè)值是value的元素的索引。（7）count(value):返回元素值是value的元素?cái)?shù)量。2025/6/111235.1Python中的列表3.列表的常用方法（8）reverse():將列表中的元素值倒置。2025/6/111245.1Python中的列表4.截取子列表

2025/6/111255.1Python中的列表例子1比較列表和array數(shù)組插入元素和刪除元素的耗時(shí)ch5_1.py列表和array數(shù)組都是順序表，但列表的內(nèi)部結(jié)構(gòu)要比array數(shù)組復(fù)雜，那么當(dāng)數(shù)據(jù)規(guī)模比較大時(shí)，列表的插入、刪除元素的耗時(shí)要大于array數(shù)組.

5.2列表與排序2025/6/111261.列表的排序方法（1）sort():按升序排序。（2）sort(reverse=True)：按降序排序。（3）sort(key=Lambda表達(dá)式)：讓列表的元素值按著Lambda表達(dá)式的返回值排序。注意：有關(guān)Lambda表達(dá)式的知識(shí)點(diǎn)見(jiàn)第2章4.3節(jié)。5.2列表與排序2025/6/111272.內(nèi)置排序函數(shù)Python的內(nèi)置函數(shù)sorted(list)不僅可以排序數(shù)組也可以排序列表(細(xì)節(jié)可參見(jiàn)第2章4.3節(jié))。

2025/6/111285.2列表與排序例子2按數(shù)學(xué)成績(jī)或英語(yǔ)成績(jī)排序ch5_2.py本例中的列表score_list的元素是長(zhǎng)度為2的列表，例如元素[89,78],其中89表示數(shù)學(xué)分?jǐn)?shù)、78表示英語(yǔ)分?jǐn)?shù)。ch5_2.py中分別按數(shù)學(xué)和英語(yǔ)成績(jī)排序score_list列表。2025/6/111295.3列表與隨機(jī)布雷例子3模擬隨機(jī)布雷ch5_3.py

布雷時(shí)需要判斷一個(gè)點(diǎn)(x,y)是否已經(jīng)布雷，因此需要將Point對(duì)象添加到列表中，以便判斷一個(gè)點(diǎn)是否已經(jīng)布雷。

創(chuàng)建對(duì)象的類需要重載“__eq__”方法?！癷fpnotinpoint_list”這樣的語(yǔ)句會(huì)調(diào)用對(duì)象的“__eq__”方法來(lái)判斷對(duì)象是否相等。2025/6/111305.4列表與隨機(jī)數(shù)例子4隨機(jī)數(shù)與雙色球ch5_4.py通過(guò)隨機(jī)刪除列表中的數(shù)據(jù)可以獲得若干個(gè)不同的隨機(jī)數(shù)。

5.5列表與篩選法2025/6/11131篩法的算法從2開始：2是素?cái)?shù)，把素?cái)?shù)2保存，然后把2后面所有能被2整除的數(shù)都劃去。數(shù)字2后面第1個(gè)沒(méi)劃去的數(shù)是素?cái)?shù)3，把素?cái)?shù)3保存，然后再把3后面所有能被3整除的數(shù)都劃去。3后面第1個(gè)沒(méi)劃去的數(shù)是素?cái)?shù)5，把素?cái)?shù)5保存，然后再把5后面所有能被5整除的數(shù)都劃去?！凑蘸Y法，每次留下的數(shù)字中的第1個(gè)數(shù)字一定是素?cái)?shù)，如此繼續(xù)進(jìn)行，就會(huì)把不超過(guò)N的全部合數(shù)都篩掉，保存的就是不超過(guò)N的全部素?cái)?shù)。2025/6/111325.5列表與篩選法例子5用篩選法求素?cái)?shù)ch5_5.py

5.6列表與全排列2025/6/11133

2025/6/111345.6列表與全排列1.itertools模塊與全排列

2.

遞歸求全排列

2025/6/111355.6列表與全排列例子6求全排列ch5_6.pych5_6.py使用permutations(list)函數(shù)分別得到1,2,3的全部全排列（按字典序升序）以及1,2,3的全部全排列（按字典序降序）；使用自定義的遞歸函數(shù)my_permutation(source)得到1,2,3的全部全排列。2025/6/111365.6列表與全排列例子7九宮格填數(shù)字ch5_7.py3數(shù)字填空

2025/6/111375.6列表與全排列4迭代法求全排列對(duì)于字符1，2，3，5，6，7，8組成的全排列，按字典序，最小的是12345678，最大的是87654321。從最小的全排列（或最大的全排列）開始，按著字典序依次尋找下一個(gè)全排列，一直到找到最大的（最小的）全排列為止，就可以給出全部的全排列。這里，我們通過(guò)找34587621的下一個(gè)全排列，介紹基于字典序找全排列的算法。①尋找正序相鄰對(duì)在全排列的相鄰對(duì)中找到最后一對(duì)“正序相鄰對(duì)”（小的在前、大的在后）。2025/6/111385.6列表與全排列●迭代法求全排列這里，我們通過(guò)找34587621的下一個(gè)全排列，介紹基于字典序找全排列的算法。②尋找最小字符

對(duì)于：58，找到的字符是6。字符6以后的字符（假如有的話）都比字符5小2025/6/111395.6列表與全排列這里，我們通過(guò)找34587621的下一個(gè)全排列，介紹基于字典序找全排列的算法。③最小字符與pairLast的首字符互換

2025/6/111405.6列表與全排列34587621的下一個(gè)全排列：34612578。④反轉(zhuǎn)子序列

例子8迭代法求全排列ch5_8.py5.7列表與組合2025/6/11141

2025/6/111425.7列表與組合1.itertools模塊與組合在Python中，可以使用itertools模塊中的combinations()函數(shù)來(lái)生成組合。

例子9求組合ch5_9.py2025/6/111435.7列表與組合2用迭代法求組合和排列不同，[1,2,3]和[1,3,2]是不同的排列，是相同的組合。因此，表示組合時(shí)可以讓組合里的數(shù)字都是升序的。

該組合中的每個(gè)數(shù)，按順序存放到一個(gè)順序表list中。

得到下一個(gè)組合[1,4,5]2025/6/111445.7列表與組合2用迭代法求組合例子10用迭代法求組合ch5_10.py

2025/6/111455.7列表與組合3組合與砝碼稱重例子11用天平秤重量ch5_11.py有些組合可能稱出相同的重量，比如用一個(gè)5克的砝碼可以稱出5克重量，用1個(gè)2克砝碼和1個(gè)3克砝碼，同樣也可以稱出5克重量。遍歷全部的組合，發(fā)現(xiàn)能稱出相同的重量的組合（即方案）時(shí)，保留一個(gè)即可。

如果允許砝碼放在天秤的兩端（允許放在被稱重的物體一端），那么就把另一端（被稱重的物體一端）的砝碼拿回到放置砝碼的一端、并變成“負(fù)碼”（重量是負(fù)數(shù)），就將問(wèn)題轉(zhuǎn)化為砝碼只放天秤一端的情況。5.8列表與生命游戲2025/6/11146

2025/6/111475.8列表與生命游戲一個(gè)細(xì)胞的下一代的生死狀態(tài)變化遵循生命游戲算法。（1）細(xì)胞的周圍有3個(gè)細(xì)胞為生，下一代該細(xì)胞為生（當(dāng)前細(xì)胞若原先為死，則轉(zhuǎn)為生，若原先為生，則保持不變）。（2）細(xì)胞周圍有兩個(gè)細(xì)胞為生，下一代該細(xì)胞的生死狀態(tài)保持不變。（3）細(xì)胞周圍是其他情況，下一代該細(xì)胞為死（即該細(xì)胞若原先為生，則轉(zhuǎn)為死，若原先為死，則保持不變）。對(duì)于二維有限細(xì)胞空間（有限的格子（細(xì)胞）數(shù)目），從某個(gè)初始狀態(tài)開始，經(jīng)過(guò)一定時(shí)間運(yùn)行后，

細(xì)胞空間可能趨于一個(gè)空間平穩(wěn)的構(gòu)形，稱進(jìn)入平穩(wěn)狀態(tài)，即每一個(gè)細(xì)胞處于固定狀態(tài)，不隨時(shí)間變化而變化。但是有時(shí)也會(huì)進(jìn)入一個(gè)周期狀態(tài)，即在幾個(gè)狀態(tài)中周而復(fù)始。2025/6/111485.8列表與生命游戲例子12生命游戲ch5_12.pych5_12.py的函數(shù)next_life_state(life)給出生命游戲當(dāng)前狀態(tài)life的下一代的next_life。本例next_life_state(life)函數(shù)輸出生命游戲中生命狀態(tài)的變化。5.9列表的公共子列表2025/6/11149如果列表a的某個(gè)子數(shù)組和數(shù)組b的某個(gè)子列表的長(zhǎng)度相同（不要求兩個(gè)子列表的起始索引相同），所包含的元素值也依次相同，就稱二者有公共子列表。2025/6/111505.9列表的公共子列表讓長(zhǎng)度小的列表，比如b的首單元和列表a的未單元對(duì)齊，列表b一直向左移動(dòng)，直到列表b的尾部a的首單元對(duì)齊。向左滑動(dòng)法那么在左移的過(guò)程中，列表a和列表b二者的所有公共子列表一定會(huì)出現(xiàn)左對(duì)齊的情況。列表a列表b2025/6/111515.9

列表的公共子列表例子13尋找一個(gè)最大的公共子列表ch5_13.py讓長(zhǎng)度小的列表，比如b的首單元和列表a的未單元對(duì)齊，即b的左端和a的右端對(duì)齊，然后進(jìn)行異或運(yùn)算，運(yùn)算結(jié)果存放到一個(gè)其它列表c中，讓列表b按一個(gè)單元（元素）為單位向左依次移動(dòng)（滑動(dòng)），每移動(dòng)一個(gè)單元，進(jìn)行異或運(yùn)算，運(yùn)算結(jié)果存放到列表c中。列表b一直向左移動(dòng)，直到列表b的尾部，即最后一個(gè)單元和列表a的首單元對(duì)齊。向左滑動(dòng)法那么在左移的過(guò)程中，列表a和數(shù)組b二者的所有公共子數(shù)組一定會(huì)出現(xiàn)左對(duì)齊的情況。由異或運(yùn)算法則可知，相同的整數(shù)異或的結(jié)果是0，那么只要根據(jù)列表c中連續(xù)出現(xiàn)的0的個(gè)數(shù)，就可以找到一個(gè)最大的公共子列表。5.10列表與堆2025/6/11152列表是線性結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)，使得列表適合查詢數(shù)據(jù)，但不適合刪除和插入操作?？梢允褂胔eadpq模塊提供的函數(shù)將列表轉(zhuǎn)換為樹形結(jié)構(gòu)，但存儲(chǔ)結(jié)構(gòu)仍然是順序存儲(chǔ)，即得到一個(gè)基于列表的堆。2025/6/111535.10

列表與堆1.堆的結(jié)構(gòu)與特性

2025/6/111545.10

列表與堆2.heapq模塊heapq模塊提供了對(duì)最小堆的支持、使用一個(gè)列表heap來(lái)實(shí)現(xiàn)堆，其中列表heap的最小值被作為堆頂（堆的最小值是堆所維護(hù)的列表heap的首元素），列表heap的其他元素表示堆的其他部分。heapq模塊提供的函數(shù)會(huì)根據(jù)堆的結(jié)構(gòu)來(lái)維護(hù)和操作這個(gè)列表、確保堆的特性得以保持。heapq模塊提供了一些函數(shù)來(lái)進(jìn)行堆操作，包括向堆中插入結(jié)點(diǎn)、從堆中彈出結(jié)點(diǎn)，例如：heapq.heappush(heap,data)將數(shù)據(jù)為data的結(jié)點(diǎn)插入堆中、heapq.heappop(heap)從堆中彈出最小的結(jié)點(diǎn)（稱為彈頂）。盡管堆是通過(guò)列表來(lái)實(shí)現(xiàn)的，但要使用heapq模塊提供的函數(shù)來(lái)操作堆，不要直接使用列表的方法來(lái)操作heap，否則無(wú)法體堆的特性。簡(jiǎn)單地說(shuō)，當(dāng)使用堆來(lái)管理數(shù)據(jù)時(shí)，導(dǎo)入heapq模塊（不需要實(shí)例化一個(gè)類），然后直接調(diào)用他提供的函數(shù)創(chuàng)建堆、操作堆。2025/6/111555.10

列表與堆3.將列表轉(zhuǎn)換為堆heapq模塊的heapify(list)函數(shù)可以直接將列表list轉(zhuǎn)換為堆。4.刪除堆中某個(gè)元素

5.返回從大到小排序的列表

2025/6/111565.10

列表與堆6.堆的演化過(guò)程堆的數(shù)據(jù)存儲(chǔ)是順序存儲(chǔ)，數(shù)據(jù)的邏輯結(jié)構(gòu)是二叉樹結(jié)構(gòu)，即堆所護(hù)的列表是堆的存儲(chǔ)結(jié)構(gòu)，而模塊的函數(shù)可以確保堆的邏輯結(jié)構(gòu)和堆的特性得到維護(hù)。演示堆heap=[1,1,2,5,8,9,9]的彈頂過(guò)程，即演示了堆和相應(yīng)的二叉樹邏輯結(jié)構(gòu)的演化過(guò)程。2025/6/111575.10

列表與堆6.堆的演化過(guò)程堆的數(shù)據(jù)存儲(chǔ)是順序存儲(chǔ)，數(shù)據(jù)的邏輯結(jié)構(gòu)是二叉樹結(jié)構(gòu)，即堆所護(hù)的列表是堆的存儲(chǔ)結(jié)構(gòu)，而模塊的函數(shù)可以確保堆的邏輯結(jié)構(gòu)和堆的特性得到維護(hù)。演示堆heap=[1,1,2,5,8,9,9]的彈頂過(guò)程，即演示了堆和相應(yīng)的二叉樹邏輯結(jié)構(gòu)的演化過(guò)程。2025/6/111585.10

列表與堆6.堆的演化過(guò)程堆的數(shù)據(jù)存儲(chǔ)是順序存儲(chǔ)，數(shù)據(jù)的邏輯結(jié)構(gòu)是二叉樹結(jié)構(gòu)，即堆所護(hù)的列表是堆的存儲(chǔ)結(jié)構(gòu)，而模塊的函數(shù)可以確保堆的邏輯結(jié)構(gòu)和堆的特性得到維護(hù)。演示堆heap=[1,1,2,5,8,9,9]的彈頂過(guò)程，即演示了堆和相應(yīng)的二叉樹邏輯結(jié)構(gòu)的演化過(guò)程。2025/6/111595.10

列表與堆6.堆的演化過(guò)程堆的數(shù)據(jù)存儲(chǔ)是順序存儲(chǔ)，數(shù)據(jù)的邏輯結(jié)構(gòu)是二叉樹結(jié)構(gòu)，即堆所護(hù)的列表是堆的存儲(chǔ)結(jié)構(gòu)，而模塊的函數(shù)可以確保堆的邏輯結(jié)構(gòu)和堆的特性得到維護(hù)。演示堆heap=[1,1,2,5,8,9,9]的彈頂過(guò)程，即演示了堆和相應(yīng)的二叉樹邏輯結(jié)構(gòu)的演化過(guò)程。2025/6/111605.10

列表與堆6.堆的演化過(guò)程堆的數(shù)據(jù)存儲(chǔ)是順序存儲(chǔ)，數(shù)據(jù)的邏輯結(jié)構(gòu)是二叉樹結(jié)構(gòu)，即堆所護(hù)的列表是堆的存儲(chǔ)結(jié)構(gòu)，而模塊的函數(shù)可以確保堆的邏輯結(jié)構(gòu)和堆的特性得到維護(hù)。演示堆heap=[1,1,2,5,8,9,9]的彈頂過(guò)程，即演示了堆和相應(yīng)的二叉樹邏輯結(jié)構(gòu)的演化過(guò)程。2025/6/111615.10

列表與堆6.堆的演化過(guò)程堆的數(shù)據(jù)存儲(chǔ)是順序存儲(chǔ)，數(shù)據(jù)的邏輯結(jié)構(gòu)是二叉樹結(jié)構(gòu)，即堆所護(hù)的列表是堆的存儲(chǔ)結(jié)構(gòu)，而模塊的函數(shù)可以確保堆的邏輯結(jié)構(gòu)和堆的特性得到維護(hù)。演示堆heap=[1,1,2,5,8,9,9]的彈頂過(guò)程，即演示了堆和相應(yīng)的二叉樹邏輯結(jié)構(gòu)的演化過(guò)程。2025/6/111625.10

列表與堆6.堆的演化過(guò)程堆的數(shù)據(jù)存儲(chǔ)是順序存儲(chǔ)，數(shù)據(jù)的邏輯結(jié)構(gòu)是二叉樹結(jié)構(gòu)，即堆所護(hù)的列表是堆的存儲(chǔ)結(jié)構(gòu)，而模塊的函數(shù)可以確保堆的邏輯結(jié)構(gòu)和堆的特性得到維護(hù)。演示堆heap=[1,1,2,5,8,9,9]的彈頂過(guò)程，即演示了堆和相應(yīng)的二叉樹邏輯結(jié)構(gòu)的演化過(guò)程。注意：由于堆是使用列表實(shí)現(xiàn)的，也稱堆的結(jié)點(diǎn)為元素。2025/6/111635.10

列表與堆例子14列表與堆ch5_14.pych5_14.py中的get_head(lst)函數(shù)將列表lst轉(zhuǎn)換為堆，并使用heapq模塊的常用函數(shù)操作堆.堆是很好的一種數(shù)據(jù)結(jié)構(gòu)，具有雙重屬性，當(dāng)不需要堆的特性時(shí)，可以使用列表的方法來(lái)操作他；當(dāng)需要堆的特性使用heapq提供的函數(shù)操作它。第6章棧2025/6/11164棧的特點(diǎn)

列表?yè)?dān)當(dāng)棧角色棧與遞歸棧與括號(hào)匹配棧與深度搜素棧與后綴表達(dá)式棧與undo操作6.1棧的特點(diǎn)2025/6/11165棧擅長(zhǎng)在線性表的尾部，即棧頂操作，棧是受限的線性表。壓棧時(shí)，最先進(jìn)棧的節(jié)點(diǎn)在棧底，最后進(jìn)棧的節(jié)點(diǎn)在棧頂（俗話說(shuō)，壘墻的磚，后來(lái)者居上），彈棧時(shí)，從棧頂開始彈出節(jié)點(diǎn)，最后一個(gè)彈出的節(jié)點(diǎn)是棧底節(jié)點(diǎn)。棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)稱LIFO（LastInFirstout）6.2列表?yè)?dān)當(dāng)棧角色2025/6/11166

6.2列表?yè)?dān)當(dāng)棧角色2025/6/11167回文串是指和其反轉(zhuǎn)（倒置）相同的字符串，例如："racecar","123321"，"level”，"toot"，"civic"，"pop"，"eye"，"rotator"，"pip"都是回文串。我們?cè)诘?章例子4，使用遞歸方法判斷一個(gè)字符串是否是回文串。2025/6/111686.2列表?yè)?dān)當(dāng)棧角色ch6_1.py例子2如果一個(gè)字符串的長(zhǎng)度是偶數(shù)，只要判斷字符串的前一半和后一半是否相同即可，如果一個(gè)字符串的長(zhǎng)度是奇數(shù)，只要忽略字符串中間的字符，然后判斷字符串的前一半和后一半是否相同即可。那么利用棧的特點(diǎn)，首先將字符串的字符逐個(gè)進(jìn)棧，然后彈出一半字符壓入另一個(gè)棧，然后比較兩個(gè)棧中的字符是否相同，就可以判斷一個(gè)字符串是否是回文串。利用棧判斷一個(gè)字符串是否為回文串6.3棧與遞歸2025/6/11169遞歸過(guò)程就是方法地址被壓棧、彈棧的一個(gè)過(guò)程，所以，也可以利用棧這種數(shù)據(jù)結(jié)構(gòu)，把某些遞歸算法改寫為迭代算法。2025/6/111706.3棧與遞歸ch6_2.py例子2ch6_2.py中利用棧輸出Fibonacci序列的前16項(xiàng)（有關(guān)Fibonacci序列的知識(shí)點(diǎn)和遞歸算法參見(jiàn)第3章中的例3-2）。利用棧輸出Fibonacci序列的前幾項(xiàng)6.4棧與括號(hào)匹配2025/6/11171棧的特點(diǎn)使得它很適合被用來(lái)檢查一個(gè)字符串中的括號(hào)是否是匹配的，即左、右括號(hào)是否是成對(duì)的。算法如下：2025/6/111726.4棧與括號(hào)匹配例子3檢查括號(hào)是否匹配算法描述如下：（1）遍歷字符串的每個(gè)字符，遇到左括號(hào)時(shí)壓棧。（2）遇到右括號(hào)，如果此時(shí)棧為空，字符串中就出現(xiàn)了括號(hào)不匹配現(xiàn)象。如果棧不空，彈棧。如果字符串中的括號(hào)是匹配的，按著棧的特點(diǎn)，當(dāng)遍歷字符串遇到右括號(hào)時(shí)，此刻棧頂節(jié)點(diǎn)中的括號(hào)一定是和它相匹配的左括號(hào)，如果不是這樣，字符串中的括號(hào)就出現(xiàn)了不匹配現(xiàn)象。ch6_3.py6.5棧與深度搜索2025/6/11173深度優(yōu)先搜索算法，在進(jìn)行遍歷或者說(shuō)搜索的時(shí)候，選擇一個(gè)沒(méi)有被搜過(guò)的節(jié)點(diǎn)，按照深度優(yōu)先：一直往該節(jié)點(diǎn)的后續(xù)路徑節(jié)點(diǎn)進(jìn)行訪問(wèn)，直到該路徑的最后一個(gè)節(jié)點(diǎn)，然后再?gòu)奈幢辉L問(wèn)的鄰節(jié)點(diǎn)進(jìn)行深度優(yōu)先搜索，重復(fù)以上過(guò)程，直至所有點(diǎn)都被訪問(wèn)或搜索到指定的某些特殊節(jié)點(diǎn)，算法結(jié)束。深度優(yōu)先搜索（DepthFirstSearch，DFS）和廣度優(yōu)先搜索（BreadthFirstSearch，BFS）都是圖論里關(guān)于圖的遍歷的算法（見(jiàn)第13章13.5），但DFS算法的思想可以用于任何恰好適合使用DFS的數(shù)據(jù)搜索問(wèn)題，不僅僅限于圖論中的問(wèn)題。6.5棧與深度搜索2025/6/11174講解DFS思想的一個(gè)很好的例子是老鼠走迷宮。2025/6/111756.5棧與深度搜索例子4模擬老鼠走迷宮ch6_4.pych6_4.py中使用move_in_maze(maze,rows,columns)函數(shù)走迷宮。老鼠走過(guò)迷宮后，列表中元素值是1表示墻，0表示老鼠未走過(guò)的路，-1表示老鼠走過(guò)的路，2表示出口。對(duì)于其中一個(gè)迷宮，老鼠無(wú)法到達(dá)路口，因?yàn)槿魏温范紵o(wú)法到達(dá)出口，對(duì)于另外一個(gè)迷宮，老鼠成功到達(dá)出口.6.6棧與后綴表達(dá)式2025/6/11176后綴表達(dá)式（也稱為逆波蘭表達(dá)式）是由波蘭數(shù)學(xué)家JanLukasiewicz在1920年發(fā)明的（那個(gè)時(shí)候還沒(méi)有計(jì)算機(jī)）。后綴表達(dá)式是一種數(shù)學(xué)表達(dá)式的表示方式，其中運(yùn)算符寫在操作數(shù)的后面。例如：前面的中綴表達(dá)式(13+17)*6的后綴表達(dá)式是：1317+6*6.6棧與后綴表達(dá)式2025/6/11177使用棧計(jì)算后綴表達(dá)式的步驟：2025/6/111786.6棧與后綴表達(dá)式計(jì)算后綴表達(dá)式：1317+6*按照上述步驟形成的入棧（壓棧），彈棧的示意圖如圖：中綴表達(dá)式是(13+17)*6后綴表達(dá)式2025/6/111796.6棧與后綴表達(dá)式ALG_suffix.py例子5使用棧計(jì)算后綴表達(dá)式ch6_5.py后綴表達(dá)式ALG_suffix.py中的string_to_array(expression)函數(shù)把后綴表達(dá)式expression中的運(yùn)算數(shù)和運(yùn)算符號(hào)存儲(chǔ)到列表中（后綴表達(dá)式expression中的運(yùn)算符和運(yùn)算數(shù)之間、運(yùn)算數(shù)之間要用空格分隔）；suffix(a)函數(shù)使用棧計(jì)算后綴表達(dá)式(a是string_to_array(expression)函數(shù)返回的列表).2025/6/111806.6棧與后綴表達(dá)式中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式2025/6/111816.6棧與后綴表達(dá)式例子6把中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式ch6_6.py●中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式ALG_suffix.py將例5中的ALG_suffix.py文件和本例ch6_6.py保存在同一目錄中。本例中的infix_to_suffix(infix)函數(shù)把中綴表達(dá)式infix轉(zhuǎn)換為后綴表達(dá)式，本例首先把一個(gè)中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式、計(jì)算后綴表達(dá)式的值（并顯示后綴表達(dá)式）,然后讓有戶從鍵盤輸出一個(gè)中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式、計(jì)算后綴表達(dá)式的值（不再顯示后綴表達(dá)式）.6.7棧與undo操作2025/6/11182棧的“后進(jìn)先出”的特點(diǎn)，適合用于設(shè)計(jì)undo操作，即撤銷操作。撤銷操作就是取消當(dāng)前操作結(jié)果、恢復(fù)到上一次操作的結(jié)果。我們經(jīng)常使用撤銷操作，對(duì)此并不陌生，比如我們?cè)诰庉嬑谋緯r(shí)，經(jīng)常單擊編輯器提供的“撤銷”快捷按鈕撤銷剛剛鍵入文字，讓文檔恢復(fù)到上一次編輯操作的樣子?？梢杂脳?lái)實(shí)現(xiàn)undo操作，即把一系列操作結(jié)果壓入棧中，當(dāng)用戶想回到上一步驟時(shí)，進(jìn)行彈棧、彈出棧頂節(jié)點(diǎn)的對(duì)象，剛好是上一次的操作結(jié)果，恢復(fù)這個(gè)結(jié)果即可?？梢圆粩嗟剡M(jìn)行彈棧操作，直到棧為空，即恢復(fù)到最初的操作結(jié)果。2025/6/111836.7棧與undo操作ch6_7.py例子7撤銷顯示的漢字ch6_7.py中的窗體有一個(gè)標(biāo)簽組件，用戶單擊“顯示一個(gè)漢字”按鈕可以在標(biāo)簽上顯示一個(gè)漢字。但標(biāo)簽上只保留最近一次顯示的漢字。當(dāng)用戶單擊“撤銷”按鈕時(shí)，將取消用戶最近一次單擊“顯示一個(gè)漢字”按鈕產(chǎn)生的操作效果，即將標(biāo)簽上的漢字恢復(fù)為上一次單擊“顯示一個(gè)漢字”按鈕所得到的漢字。用戶可以多次單擊“撤銷”按鈕來(lái)依次取消單擊“顯示一個(gè)漢字”按鈕所產(chǎn)生的操作效果.第7章隊(duì)列2025/6/11184隊(duì)列的特點(diǎn)隊(duì)列的創(chuàng)建與獨(dú)特的方法隊(duì)列與回文串隊(duì)列與加密解密隊(duì)列與約瑟夫問(wèn)題隊(duì)列與廣度搜索優(yōu)先隊(duì)列隊(duì)列與排隊(duì)隊(duì)列與篩選法7.1隊(duì)列的特點(diǎn)2025/6/11185隊(duì)列擅長(zhǎng)在線性表的頭、尾兩端實(shí)施刪除和添加操作，甚至可以把線性表實(shí)現(xiàn)成只在頭、尾兩端操作，所以人們也稱隊(duì)列是受限的線性表。入列時(shí)，最先進(jìn)入的節(jié)點(diǎn)在隊(duì)頭，最后進(jìn)入的節(jié)點(diǎn)在隊(duì)尾。出列時(shí)，從隊(duì)列的頭開始刪除節(jié)點(diǎn)，最后一個(gè)刪除的節(jié)點(diǎn)是隊(duì)尾的節(jié)點(diǎn)。隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，簡(jiǎn)稱FIFO（FirstInFirstout）7.1隊(duì)列的特點(diǎn)2025/6/11186頭節(jié)點(diǎn)（隊(duì)頭）在左邊、尾節(jié)點(diǎn)（隊(duì)尾）在右邊。7.2隊(duì)列的創(chuàng)建與獨(dú)特方法2025/6/11187collections.deque是Python的collections模塊提供的一種雙向隊(duì)列數(shù)據(jù)結(jié)構(gòu)，collections.deque支持在隊(duì)列的兩端進(jìn)行入列和出列操作。以下稱collections.deque類的實(shí)例（對(duì)象）為雙端隊(duì)列，簡(jiǎn)稱隊(duì)列，其中的節(jié)點(diǎn)的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)使用了雙向鏈表，這意味雙端隊(duì)列在插入和刪除元素的時(shí)間復(fù)雜度是O(1)，使得他非常適合于需要高效地在隊(duì)列兩端進(jìn)行操作的場(chǎng)景。2025/6/111887.