Python數據結構之集合（文末贈書）

點擊標題下「非同步社區」可快速關注

集合（collection），正如其名稱所示，是可以作為概念性的單位來處理的一組零個或多個項。幾乎軟體的每一個重要部分都涉及集合的使用。儘管我們在計算機科學中所學的一些內容已經隨著技術的變化逐漸消失，但組織集合的基本原理並沒有變化。儘管集合在結構和用法上各不相同，但是，所有的集合都有著相同的基本作用，即幫助程序員有效地在程序中組織數據。

可以從兩個視角來看待集合。集合的用戶和客戶關注它們在各種應用程序中能做些什麼。集合的開發者和實現者關注它們作為通用資源的最佳性能。

本章將從這些集合的用戶的角度給出不同類型的集合的概覽。本章介紹了不同類型的集合、集合上常用的和可用的操作，以及常用的實現。

2.1　集合類型

你已經知道了，Python包含了幾種內建的集合類型：字元串、列表、元組、集（set）和字典。字元串和列表可能是最常用和最基本的集合類型了。其他重要的集合類型還包括棧、隊列、優先隊列、二叉搜索樹、堆、圖、包（bag）和各種類型的有序集合。

集合可以是同構的，這意味著集合中的所有項必須具有相同的類型；也可以是異構的，這意味著這些項可以是不同的類型。儘管大多數的Python集合可以包含多種類型的對象，但是在很多編程語言中，集合是同構的。

集合通常是動態的而不是靜態的，這意味著，它們可以隨著問題的需要增加或縮小。此外，在程序的整個過程中，它們的內容是可以改變的。這一規則的一個例外是不可變集合，例如Python的字元串和元組。不可變集合的項是在其創建的過程中添加的，在此之後，就不能夠再添加、刪除或替換項了。

區分集合的另一個重要的特徵是，它們的組織方式不同。本章介紹了集合的幾個廣泛分類的用法，包括線性集合、層級集合、圖集合、無序集合和有序集合。

2.1.1　線性集合

線性集合中的項就像是排隊的人一樣，都是按照位置來有序的。除了第1項外，每個項都有一個唯一的前驅，並且除了最後一項，每個項都有一個唯一的後繼。D2的前驅是D1，後繼是D3，如圖2.1所示。

圖2.1　線性集合

線性集合的示例包括購物清單、一堆餐盤和ATM前等待的一隊顧客。

2.1.2　層級集合

層級集合中的數據項，在結構中的順序類似於一棵上下顛倒的樹。除了最頂端的第一個數據項，每個數據項都只有一個前驅，稱為其父親，但是，可能有多個後繼，稱為其孩子。D3的前驅（父親）是D1，其後繼（孩子）是D4、D5和D6，如圖2.2所示。

圖2.2　層級集合

一個文件系統、一家公司的組織結構樹，以及一本書的目錄，都是層級集合的例子。

2.1.3　圖集合

圖集合也叫作圖，這個集合中的每一項都可能有多個前驅和多個後繼。如圖2.3所示，連接到D3的所有元素，都被認為是其前驅和後繼，並且它們也稱為其鄰居。

圖2.3　圖集合

城市之間的航線圖和建築物之間的電力連線圖，都是圖的例子。

2.1.4　無序集合

正如其名稱所示，無序集合中的項沒有特定的順序，並且討論一個項的前驅或後繼也是沒有意義的。圖2.4展示了這樣的一個結構。

圖2.4　無序集合

一袋玻璃球就是無序集合的一個例子。儘管你可以將玻璃球放入到袋子之中，並且按照你想要的任何順序從袋子中取出玻璃球，但玻璃球還是沒有特定的順序。

2.1.5　有序集合

有序集合在其項之上施加了一個自然的順序。示例就是電話簿中的條目（20世紀的各種紙版的電話簿）和班級花名冊中的條目。

為了施加一種自然的順序，必須要有某種規則來比較各項，例如，itemi<= itemi+1，以便能夠訪問有序集合中的各個項。

有序列表是有序集合的一個最常見的例子，有序集合併不需要是線性的或者是按照位置來排序的。從客戶的視角來看，集、包和字典可能都是有序的，即便它們的項並不是按照位置來訪問的。層級集合的一種特殊的類型叫作二叉搜索樹，它也是在其各項上施加了一種自然的順序。

一個有序的集合，允許客戶按照排好的順序來訪問其所有的項。一些操作，例如搜索，在有序的集合上可能也比在無序集合上更為高效。

2.1.6　集合類型的分類

記住了集合的主要類型，現在，我們可以將不同的常用集合類型分類了，如圖2.5所示。這種分類的方法，將有助於我們組織在本書後面的各章中用來表示這些類型的Python類。

圖2.5　集合類型的分類

注意，這個分類中的類型名稱並不意味著集合的一個特定的實現，因為你稍後將會看到，一種特定類型的集合可能有多種實現。此外，其中的一些名稱，例如「集合」和「線性集合」，指定了集合類型的分類，而不是指定了一個特殊的集合類型。然而，這些分類對於組織擁有相似性的特定類型的集合的特徵和行為來說，還是很有用的。

2.2　集合上的操作

在一個集合上可以執行的操作，會根據所使用的集合類型的不同而有所不同，這些操作可以分為表2.1所示的幾種類型。

表2.1　　集合的操作的分類

操作分類 說明

確定大小 使用Python的len函數來獲取集合中當前項的數目

測試項的成員關係 使用Python的in運算符在集合中搜索一個給定的目標項。如果找到這個項，返回True；否則的話，返回False

遍歷集合 使用Python的for循環來訪問集合中的每一個項。訪問項的順序取決於集合的類型

獲取一個字元串表示 使用Python的str函數來獲取集合的字元串表示

測試相等性 使用Python的==運算符來確定兩個集合是否相等。如果兩個集合具有相同的類型並且包含相同的項，那麼它們是相等的。比較哪兩對項的順序，則取決於集合的類型

連接兩個集合 使用Python的+運算符來獲取和運算數相同類型的一個新的集合，並且這個新的集合中包含了兩個運算數中的項

轉換為另一種類型的集合 使用源集合中相同的項，來創建一個新的集合。克隆是類型轉換的一種特例，其中，兩個集合具有相同的類型

插入一項 給集合添加一項，可能在一個給定的位置添加

刪除一項 從集合中刪除一項，可能在一個給定的位置刪除

替換一項 將刪除和插入組合到一個操作之中

訪問或獲取一項 獲取一項，可能從一個給定的位置獲取

注意，這些操作中有幾個和標準Python運算符、函數或控制語句相關，例如，in、+，len、str和for循環。我們已經熟悉了如何對Python字元串和列表使用它們。

對於Python中的插入、刪除、替換或訪問操作來說，並沒有單獨的名稱。然而，有一些標準的變體。例如，pop方法用於從Python列表中給定的位置刪除項，或者從Python字典中刪除給定鍵的值。remove方法用於從Python集或列表中刪除給定的項。隨著在Python中尚未得到支持的新的集合類型被開發出來，針對它們的操作，我們將會盡全力使用標準的運算符、函數或方法名。

你可能不熟悉的一項集合操作是類型轉換。我們已經了解了類型轉換在輸入數字時候的用法。在該環境中，我們從鍵盤接收數字的一個字元串，並對輸入字元串應用int或float函數，將其轉換為一個整數和浮點數（參見第1章了解詳細情況）。

可以用相似的方式，把一種類型的集合轉換為另一種類型的集合。例如，可以將Python字元串轉換為Python列表，並且將Python列錶轉換為Python元組，如下面的代碼所示：

message = "Hi there!"

lyst = list(message)

lyst

[』H』, 』i』, 』』, 』t』, 』h』, 』e』, 』r』, 』e』, 』!』]

toople tuple(lyst)

toople

(』H』, 』i』, 』』, 』t』, 』h』, 』e』, 』r』, 』e』, 』!』)

list或tuple函數的參數不需要是另一個集合，它可以是任何可迭代的對象。可迭代的對象允許程序員使用Python的for循環來訪問項的一個序列（是的，這聽上去就像是一個集合，所有的集合也都是可迭代的對象）。例如，我們可以通過一個range函數來創建一個列表，如下所示：

lyst = list(range(1, 11, 2))

lyst

[1, 3, 5, 7, 9]

其他的函數，如用於字典的dict函數，期待類型更加具體的可迭代對象作為其參數，例如(key, value)的元組的列表。

通常，如果省略了參數，集合的類型轉換函數會返回該類型的一個新的、空的集合。

克隆是一種特殊的類型轉化，它將參數的一個完全的副本返回給轉換函數。在這種情況下，參數的類型和轉換函數的類型應該是相同的。例如，如下的代碼段產生了列表的一個副本，然後，使用is和==運算符來比較兩個列表。如果兩個列表不是相同的對象，is會返回False。儘管兩個列表是不同的對象，但是由於它們具有相同的類型並且擁有相同的結果（兩個列表中的每一個位置上的每一對元素都是相同的），==返回True。

lyst1 = [2, 4, 8]

lyst2 = list(lyst1)

lyst1 is lyst2

False

lyst1 == lyst2

True

這個示例中的兩個列表不僅擁有相同的結構，而且它們還擁有相同的項。也就是說，list函數對其參數列表進行了淺複製，這些項並沒有在添加到新列表之前進行了自身的複製。

當這些項是不可變的時候（數字、字元串或Python元組），這一策略不會有問題。然而，當集合共享可變的項，將會引起副作用。為了防止這種情況發生，程序員可以通過編寫在源集合上的一個for循環來創建深複製，這會在把項添加到新的集合之前，顯式地複製其項。

後續的各章將會採取為大多數集合類型提供類型轉換函數的策略。這個函數接受一個可迭代的對象作為可選的參數，並且對訪問的各項執行淺複製。

2.3　集合的實現

實際上，和最初負責實現集合的程序員相比，負責編寫使用集合的程序的那些程序員對這些集合有著不同的視角。

使用集合的程序員需要知道如何實例化和使用每一種集合類型。從他們的視角來看，集合是以某種預定義的方式存儲和訪問數據項的一種手段，他們並不關心集合實現的細節。換句話說，從用戶的視角來看，集合是一個抽象體，正因為此，在計算機科學中，集合也稱為抽象數據類型（abstract data types，ADT）。ADT的用戶只關心其介面，或者說關心該類型的對象所識別的一組操作。

另一方面，集合的開發者則關心能以可能的、最為高效的方式來實現集合的行為，其目標是為集合的用戶提供最佳性能。通常可能有大量的實現。然而，很多的實現都會佔用太多的空間，或者運行得太慢，以至於我們認為不值得這麼做。而剩下的那些實現，則傾向於基於幾種基本的方法來組織和訪問計算機內存。第3章和第4章將會詳細介紹這些方法。

一些編程語言，例如Python，針對每種可用的集合類型只提供了一種實現。而像Java等其他語言，則提供數種實現。例如，Java的java.util包包含了列表的兩個實現，分別是ArrayList和LinkedList。還有集和映射（就像Python的字典一樣）各自的兩個實現，分別是HashSet、TreeSet、HashMap和TreeMap。Java程序員對於每一個實現都使用相同的介面（一組操作），但是能夠根據各種實現的性能特徵和其他標準，從實現中自由地選取。本書的一個主要的目標是，讓Python程序員能夠具備和Java程序員一樣的選擇權。本書同時還會介紹抽象數據類型，並指出它們在任何一種語言中不可用的實現。對於每一種類型的集合（線性的、層級的、圖的、無序的和有序的）。你將會看到一種或多種抽象集合類型，以及一種或多種實現。

抽象的思路並不是討論集合的時候所獨有的。在計算機科學領域之內和之外的很多場合，抽象都是一個重要的原理。例如，當學習下落物體上的重力作用的時候，你可能會嘗試搭建一個實驗條件，其中，你可以忽略掉物體的顏色和味道（例如，砸到牛頓的腦袋上的蘋果）等無關緊要的細節。當學習數學的時候，你不需要關心用什麼數字來統計魚鉤或箭鏃，而是要試圖發現數字的抽象和持久不變的原理。房屋的裝修設計規劃，是實體的房屋的一個抽象，它使你能夠關注結構性要素而不必被諸如櫥櫃的顏色這樣無關緊要的細節所淹沒。結構性要素是那些對整個房屋的整體外觀很重要的細節，並不涉及房屋的主要部件之間的關係。

在計算機科學中，抽象用於忽略或隱藏那些不重要的細節。軟體系統通常是一層一層地構建的，每一層都被使用它的上一層當作是一個抽象體來對待。沒有了抽象，你將需要同時考慮軟體設計的所有方面，這是一項不可能完成的任務。當然，你最終必須考慮細節，但是，你可以在一個較小的、可管理的環境中做這些事情。

在Python中，函數和方法是抽象的最小單位，類是下一個較大的單位，而模塊是最大的單位。本書介紹了將抽象集合類型作為類以及模塊中相關的一組類而實現。組織這些類的通用性技術，則涉及面向對象編程，我們將會在第5章和第6章中介紹。本書所介紹的集合類的完整列表，可參見附錄A。

2.4　小結

集合是保存0個或多個其他對象的對象。集合擁有訪問對象、插入對象、刪除對象、確定集合的大小以及遍歷或訪問集合的對象的操作。

集合的5個主要類別是：線性集合、層次集合、圖集合、無序集合和有序集合。

線性集合按照位置來排列其項，除了第一項，每一項都有唯一的一個前驅，除了最後一項，每一個項都有唯一的一個後繼。

層次集合中的項都擁有唯一的前驅（只有一個例外，就是頂層的項），以及0個或多個後繼。單個的稱為根的項是沒有前驅的。

圖中的項擁有0個或多個後繼，以及0個或多個前驅。

無序集合中的項沒有特定的順序。

集合是可迭代的，可以用一個for循環來訪問包含在集合中的每一項。

抽象的數據類型是一組對象，以及這些對象上的操作。因此，集合是抽象數據類型。

數據結構是表示集合中包含的數據的一個對象。

2.5　複習題

1．線性集合的例子是（　　）。

　　a．集和樹

　　b．列表和棧

2．無序集合的例子是（　　）。

　　a．隊列和列表

　　b．集和字典

3．層級集合可以表示（　　）。

　　a．銀行排隊的顧客

　　b．城市之間的航線

4．圖集合可以表示（　　）。

　　a．數與集合

　　b．城市之間的航線圖

2.6　編程項目

1．在一個shell提示符窗口中，使用dir和help函數，研究Python的內建集合類型str、list、tuple、set和dict。使用這兩個函數的語法分別是dir()和help()。

2．為了和Python進行比較，瀏覽位於Java的java.util包中的集合類型，參見http:// http://docs.oracle.com/javase/7/docs/api/。

本文摘自《數據結構——python語言描述》

數據結構（Python語言描述）

• 作者： 【美】Kenneth A. Lambert（蘭伯特）

在計算機科學中，數據結構是一門進階性課程，概念抽象，難度較大。Python語言的語法簡單，交互性強。用Python來講解數據結構等主題，比C語言等實現起來更為容易，更為清晰。

本書第1章簡單介紹了Python語言的基礎知識和特性。第2章到第4章對抽象數據類型、數據結構、複雜度分析、數組和線性鏈表結構進行了詳細介紹，第5章和第6章重點介紹了面向對象設計的相關知識、第5章包括介面和實現之間的重點差異、多態以及信息隱藏等內容，第6章主要講解繼承的相關知識，第7章到第9章以棧、隊列和列表為代表，介紹了線性集合的相關知識。第10章介紹了各種樹結構，第11章講解了集和字典的相關內容，第12章介紹了圖和圖處理演算法。每章最後，還給出了複習題和案例學習，幫助讀者鞏固和思考。

本書目錄：(滑動手機查看)

第1章 Python編程基礎 1

1．1 基本程序要素 1

1．1．1 程序和模塊 1

1．1．2 Python程序示例：猜數字 1

1．1．3 編輯、編譯並運行

Python程序 2

1．1．4 程序注釋 3

1．1．5 詞法元素 3

1．1．6 拼寫和命名慣例 3

1．1．7 語法元素 4

1．1．8 字面值 4

1．1．9 字元串字面值 4

1．1．10 運算符和表達式 5

1．1．11 函數調用 5

1．1．12 print函數 5

1．1．13 input函數 5

1．1．14 類型轉換函數和

混合模式運算 6

1．1．15 可選的和關鍵字

函數參數 6

1．1．16 變數和賦值語句 6

1．1．17 Python數據類型 7

1．1．18 import語句 7

1．1．19 獲取關於程序組件

的幫助 7

1．2 控制語句 8

1．2．1 條件式語句 8

1．2．2 使用if __name__ ==

"__main__" 9

1．2．3 循環語句 10

1．3 字元串及其運算 10

1．3．1 運算符 10

1．3．2 格式化字元串以便輸出 11

1．3．3 對象和方法調用 13

1．4 內建Python集合及其操作 13

1．4．1 列表 14

1．4．2 元組 14

1．4．3 遍歷序列 14

1．4．4 字典 15

1．4．5 搜索一個值 15

1．4．6 對集合應用模式匹配 15

1．5 編寫新的函數 16

1．5．1 函數定義 16

1．5．2 遞歸函數 17

1．5．3 嵌套的函數定義 19

1．5．4 高階函數 19

1．5．5 使用lambda表達式

創建匿名函數 20

1．6 捕獲異常 20

1．7 文件及其操作 21

1．7．1 文本文件的輸出 22

1．7．2 將數字寫入到一個

文本文件 22

1．7．3 從文本文件讀取文本 23

1．7．4 從文件讀取數字 24

1．7．5 使用pickle讀寫對象 24

1．8 創建新的類 25

1．9 編程項目 28

第2章 集合概覽 30

2．1 集合類型 30

2．1．1 線性集合 30

2．1．2 層級集合 31

2．1．3 圖集合 31

2．1．4 無序集合 31

2．1．5 有序集合 31

2．1．6 集合類型的分類 32

2．2 集合上的操作 32

2．3 集合的實現 34

2．4 小結 35

2．5 複習題 35

2．6 編程項目 36

第3章 搜索、排序和複雜度分析 37

3．1 評估演算法的性能 37

3．1．1 度量演算法的運行時間 37

3．1．2 統計指令 39

3．1．3 度量演算法所使用的內存 41

3．1．4 練習3．1 41

3．2 複雜度分析 41

3．2．1 複雜度的階 41

3．2．2 大O表示法 43

3．2．3 常量比例的作用 43

3．2．4 練習3．2 43

3．3 搜索演算法 44

3．3．1 搜索最小值 44

3．3．2 順序搜索一個列表 44

3．3．3 最好情況、最壞情況和

平均情況的性能 45

3．3．4 有序列表的二叉搜索 45

3．3．5 比較數據項 47

3．3．6 練習3．3 48

3．4 基本排序演算法 48

3．4．1 選擇排序 48

3．4．2 冒泡排序 49

3．4．3 插入排序 50

3．4．4 再談最好情況、最壞情

況和平均情況的性能 52

3．4．5 練習3．4 52

3．5 更快的排序 53

3．5．1 快速排序簡介 53

3．5．2 合併排序 56

3．5．3 練習3．5 59

3．6 指數演算法：遞歸式的

Fibonacci 59

3．7 案例學習：演算法探查器 61

3．7．1 需求 61

3．7．2 分析 61

3．7．3 設計 62

3．7．4 實現（編寫代碼） 63

3．8 小結 65

3．9 複習題 66

3．10 編程項目 67

第4章 數組和鏈表結構 69

4．1 數組數據結構 69

4．1．1 隨機訪問和連續內存 71

4．1．2 靜態內存和動態內存 72

4．1．3 物理大小和邏輯大小 72

4．1．4 練習4．1 73

4．2 數組的操作 73

4．2．1 增加數組的大小 73

4．2．2 減小數組的大小 74

4．2．3 在數組中插入一項 74

4．2．4 從數組中刪除一項 75

4．2．5 複雜度權衡：時間、

空間和數組 76

4．2．6 練習4．2 76

4．3 二維數組 77

4．3．1 處理網格 77

4．3．2 創建並初始化網格 77

4．3．3 定義Grid類 78

4．3．4 雜亂的網格和多維數組 79

4．3．5 練習4．3 79

4．4 鏈表結構 80

4．4．1 單鏈表結構和雙鏈表

結構 80

4．4．2 非連續性內存和節點 81

4．4．3 定義一個單鏈表節點類 82

4．4．4 使用單鏈表節點類 82

4．4．5 練習4．4 84

4．5 單鏈表結構上的操作 84

4．5．1 遍歷 84

4．5．2 搜索 85

4．5．3 替換 86

4．5．4 在開始處插入 86

4．5．5 在末尾插入 87

4．5．6 從開始處刪除 87

4．5．7 從末尾刪除 88

4．5．8 在任何位置插入 89

4．5．9 從任意位置刪除 90

4．5．10 複雜度權衡：時間、

空間和單鏈表結構 91

4．5．11 練習4．5 92

4．6 鏈表的變體 92

4．6．1 帶有一個啞頭節點

的循環鏈表結構 92

4．6．2 雙鏈表結構 93

4．6．3 練習4．6 95

4．7 小結 95

4．8 複習題 96

4．9 編程項目 96

第5章 介面、實現和多態 98

5．1 開發介面 98

5．1．1 定義包介面 98

5．1．2 指定參數和返回值 99

5．1．3 構造方法和實現類 101

5．1．4 先驗條件、後驗條件、

異常和文檔 101

5．1．5 用Python編寫介面 102

5．1．6 練習5．1 103

5．2 開發一個基於數組的實現 103

5．2．1 選擇並初始化數據

結構 103

5．2．2 先完成容易的方法 104

5．2．3 完成迭代器 105

5．2．4 完成使用迭代器

的方法 106

5．2．5 in運算符和__contains__

方法 106

5．2．6 完成remove方法 107

5．2．7 練習5．2 107

5．3 開發一個基於鏈表的實現 107

5．3．1 初始化數據結構 108

5．3．2 完成迭代器 109

5．3．3 完成clear和add方法 109

5．3．4 完成remove方法 109

5．3．5 練習5．3 110

5．4 兩個包實現的運行時性能 110

5．5 測試兩個包實現 111

5．6 用UML圖表示包資源 112

5．7 小結 113

5．8 複習題 113

5．9 編程項目 114

第6章 繼承和抽象類 115

6．1 使用繼承定製一個已有的類 115

6．1．1 已有類的子類化 115

6．1．2 再談__init__方法 116

6．1．3 添加新的contains方法 117

6．1．4 修改已有的add方法 117

6．1．5 ArraySortedBag的運行

時間性能 118

6．1．6 Python中的類層級 118

6．1．7 練習6．1 119

6．2 使用抽象類去除代碼冗餘性 119

6．2．1 設計一個

AbstractBag類 119

6．2．2 重新編寫AbstractBag

中的__init__方法 120

6．2．3 修改AbstractBag

的子類 120

6．2．4 將AbstractBag中的

__add__方法泛化 121

6．3 所有集合的一個抽象類 122

6．3．1 將AbstractCollection

整合到集合層級中 122

6．3．2 在__eq__方法中使用

兩個迭代器 123

6．3．3 練習6．2 124

6．4 小結 124

6．5 複習題 124

6．6 編程項目 125

第7章 棧 127

7．1 棧概覽 127

7．2 使用棧 128

7．2．1 棧介面 128

7．2．2 初始化一個棧 129

7．2．3 示例應用程序：

匹配括弧 129

7．2．4 練習7．1 131

7．3 棧的3種應用 131

7．3．1 計算算術表達式 131

7．3．2 計算後綴表達式 132

7．3．3 練習7．2 133

7．3．4 將中綴表達式轉換為

後綴表達式 133

7．3．5 練習7．3 135

7．3．6 回溯演算法 135

7．3．7 內存管理 137

7．4 棧的實現 138

7．4．1 測試驅動程序 138

7．4．2 將棧添加到集合層級中 139

7．4．3 數組實現 140

7．4．4 鏈表實現 141

7．4．5 AbstractStack類的

作用 144

7．4．6 兩種實現的時間和

空間分析 144

7．4．7 練習7．4 145

7．5 案例學習：計算後綴表達式 145

7．5．1 要求 145

7．5．2 分析 145

7．5．3 設計 148

7．5．4 實現 150

7．6 小結 153

7．7 複習題 153

7．8 編程項目 154

第8章 隊列 156

8．1 隊列概覽 156

8．2 隊列介面及其應用 157

練習8．1 158

8．3 隊列的兩個應用 159

8．3．1 模擬 159

8．3．2 輪詢CPU調度 161

8．3．3 練習8．2 161

8．4 隊列的實現 161

8．4．1 隊列的鏈表實現 161

8．4．2 數組實現 163

8．4．3 兩種實現的時間和

空間複雜度分析 164

8．4．4 練習8．3 165

8．5 案例學習：模擬超市排隊

結賬 165

8．5．1 要求 165

8．5．2 分析 165

8．5．3 用戶界面 166

8．5．4 類及其作用 166

8．6 優先隊列 171

練習8．4 175

8．7 案例學習：急症室調度 175

8．7．1 需求 175

8．7．2 分析 175

8．7．3 類 176

8．7．4 設計和實現 177

8．8 小結 179

8．9 複習題 179

8．10 編程項目 180

第9章 列表 182

9．1 概覽 182

9．2 使用列表 183

9．2．1 基於索引的操作 183

9．2．2 基於內容的操作 183

9．2．3 基於位置的操作 184

9．2．4 列表的介面 187

9．2．5 練習9．1 188

9．3 列表的應用 188

9．3．1 堆存儲管理 188

9．3．2 組織磁碟上的文件 189

9．3．3 其他集合的實現 190

9．4 列表實現 191

9．4．1 AbstractList類的角色 191

9．4．2 基於數組的實現 192

9．4．3 鏈表實現 194

9．4．4 兩種實現的時間和

空間分析 196

9．4．5 練習9．2 197

9．5 實現列表迭代器 197

9．5．1 列表迭代器的角色

和作用 197

9．5．2 設置和實例化一個

列表迭代器類 198

9．5．3 列表迭代器中的導

航方法 199

9．5．4 列表迭代器中的修

改器方法 200

9．5．5 鏈表列表的列表迭

代器的設計 201

9．5．6 列表迭代器實現的

時間和空間分析 201

9．6 案例學習：開發一個有序

的列表 201

9．6．1 要求 201

9．6．2 分析 202

9．6．3 設計 202

9．6．4 實現（代碼） 204

9．7 小結 205

9．8 複習題 205

9．9 編程項目 206

第10章 樹 208

10．1 樹的概覽 208

10．1．1 樹的術語 208

10．1．2 普通的樹和二叉樹 209

10．1．3 樹的遞歸定義 210

10．1．4 練習10．1 210

10．2 為什麼要使用樹 210

10．3 二叉樹的形狀 211

練習10．2 213

10．4 二叉樹的3種常見應用 213

10．4．1 堆 213

10．4．2 二叉搜索樹 214

10．4．3 表達式樹 215

10．4．4 練習10．3 216

10．5 二叉樹的遍歷 216

10．5．1 前序遍歷 216

10．5．2 中序遍歷 217

10．5．3 後序遍歷 217

10．5．4 層序遍歷 217

10．6 開發二叉搜索樹 217

10．6．1 二叉搜索樹介面 218

10．6．2 鏈表實現的數據結構 219

10．6．3 二叉搜索樹的複雜度

分析 223

10．6．4 練習10．4 224

10．7 遞歸的後代解析和編程語言 224

10．7．1 語法簡介 224

10．7．2 在語言中識別、解析

和解釋句子 226

10．7．3 詞法分析和掃描器 226

10．7．4 解析策略 227

10．8 案例學習：解析和表達式樹 227

10．8．1 要求 227

10．8．2 分析 228

10．8．3 節點類的設計和實現 228

10．8．4 解析器類的設計和

實現 230

10．9 二叉樹的數組實現 231

練習10．5 232

10．10 實現堆 232

練習10．6 234

10．11 小結 234

10．12 複習題 235

10．13 編程項目 236

第11章 集和字典 238

11．1 使用集 238

11．2 Python的set類 239

11．2．1 集的一個示例會話 239

11．2．2 集的應用 240

11．2．3 集和包的關係 240

11．2．4 集和字典的關係 240

11．2．5 集的實現 240

11．2．6 練習11．1 241

11．3 集的基於數組和鏈表的實現 241

11．3．1 AbstractSet類 241

11．3．2 ArraySet類 242

11．4 使用字典 243

11．5 基於數組和基於鏈表的

字典實現 244

11．5．1 Item類 244

11．5．2 AbstractDict類 245

11．5．3 ArrayDict類 246

11．5．4 集和字典的基於數組

和列表的實現的複雜

度分析 247

11．5．5 練習11．2 248

11．6 哈希策略 248

11．6．1 衝突和密度的關係 249

11．6．2 非數字鍵的哈希 250

11．6．3 線性探測 251

11．6．4 二次探測 252

11．6．5 鏈化 253

11．6．6 複雜度分析 253

11．6．7 練習11．3 254

11．7 案例學習：探查哈希策略 254

11．7．1 需求 255

11．7．2 分析 255

11．7．3 設計 256

11．8 集的哈希實現 258

11．9 字典的哈希實現 261

練習11．4 263

11．10 有序的集和字典 263

11．11 小結 264

11．12 複習題 264

11．13 編程項目 265

第12章 圖 267

12．1 圖的術語 267

練習12．1 269

12．2 為什麼使用圖 270

12．3 圖的表示 270

12．3．1 相鄰矩陣 270

12．3．2 鄰接表 271

12．3．3 兩種表示的分析 272

12．3．4 運行時間的進一步

考慮 272

12．3．5 練習12．2 273

12．4 圖的遍歷 273

12．4．1 泛型遍歷演算法 273

12．4．2 廣度優先遍歷和深度

優先遍歷 274

12．4．3 圖區域 275

12．4．4 練習12．3 276

12．5 圖中的樹 276

12．5．1 生成樹和森林 276

12．5．2 最小生成樹 277

12．5．3 最小生成樹的演算法 277

12．6 拓撲排序 279

12．7 最短路徑問題 279

12．7．1 Dijkstra演算法 280

12．7．2 初始化步驟 280

12．7．3 計算步驟 281

12．7．4 無限的表示和用法 282

12．7．5 分析 282

12．7．6 練習12．4 282

12．7．7 Floyd演算法 283

12．7．8 分析 283

12．8 開發一個圖集合 284

12．8．1 使用圖集合的示例 284

12．8．2 LinkedDirected-

Graph類 285

12．8．3 LinkedVertex類 288

12．8．4 LinkedEdge類 289

12．9 案例學習：測試圖演算法 290

12．9．1 需求 290

12．9．2 分析 290

12．9．3 GraphDemoView類和

GraphDemoModel類 291

12．9．4 實現（代碼） 292

12．10 小結 295

12．11 複習題 296

12．12 編程項目 297

附錄 供Python程序員使用的

集合框架 299

小福利

關注【非同步社區】服務號，轉發本文至朋友圈或 50 人以上微信群，截圖發送至非同步社區服務號後台，並在文章底下留言，分享你的python開發經驗或者本書的試讀體驗，我們將從符合活動規則的讀者中，隨機選出 3位用戶送出《數據結構 python語言描述》1本，趕快積极參与吧！

活動截止時間：2017 年 12月31日

上期獲獎名單

lkkkkkkkkk 和 手持木劍入江湖

請獲獎讀者填寫下方獲獎信息，活動名稱《非同步社區 TensorFlow機器學習項目實戰》https://www.wenjuan.in/s/m2iaqif/

點擊圖片參與活動

http://weixin.qq.com/r/ekReRh7Eh0P4rVol9xFo (二維碼自動識別)

在「非同步社區」後台回復「關注」，即可免費獲得2000門在線視頻課程；推薦朋友關注根據提示獲取贈書鏈接，免費得非同步圖書一本。趕緊來參加哦！

掃一掃上方二維碼，回復「關注」參與活動！

點擊閱讀原文，購買《數據結構 Python語言描述》

推薦閱讀：