Python算法圖解（簡體書）

“數據結構與算法”是計算機專業的一門基礎課程，從事軟件開發工作的人員基本都會用到其中的知識。但對於一個在企業工作二十多年的程序老鳥而言，遇到的算法盲或半盲比比皆是。

曾經和一位高校教計算機課程的講師聊天，他竟然問我： “學數據庫為什麼要懂數據結構？”。在他看來，學數據庫只要學會SQL語句也就夠了。然而學生如果去企業面試，其中常被問到的問題是： “怎樣在海量數據中高效地查詢？”如今電商、微博、頭條等網站動輒在萬億條記錄中搜索，這樣的運算量用SQL語句無法處理。

目前計算機人才市場兩極分化嚴重。一些只需要簡單的計算機操作或寫界面布局的職位大量過剩，而懂算法，會優化，能結合業務實際提出更優解決方案的人才卻很稀缺。面試者會在面試環節遇到很多算法題正是這種市場需求的反映。

寫作本書的初衷是為了幫助讀者系統掌握Python算法。但隨著寫作過程的深入，筆者認為一本書不足以讓讀者在未來的職業生涯中遊刃有餘地運用算法工具解決實際發生的問題。比如對於遊戲中的尋路算法、模擬運動中的碰撞檢測、電商中的商品推薦、自動駕駛中的臨近識別等功能，如果沒有一定的實戰經驗，根本看不出這些功能中哪裡會用到哪些數據結構或算法，所以本書的定位僅是幫助讀者入門。

本書采用圖解的方式一步步描述具體算法，這種方式在數據結構與算法類圖書中不多見，但筆者認為這種方式比單純的文字描述更直觀。由於筆者水平所限，書中難免會有疏漏，懇請讀者多提寶貴意見。

編者2021年2月

第1章數據結構的分類和基本運算

1．1數據的邏輯結構

1．2數據的存儲結構

1．3數據結構的基本運算

第2章遞歸

2．1遞歸調用

2．2遞歸方式打印九九乘法表

2．3舍罕王賞麥

2．4遞歸遍歷文件

2．5遞歸實現斐波那契數列

2．6循環實現斐波那契數列

2．7兔子繁殖問題

第3章棧和隊列

3．1棧結構

3．2用棧做十進制與二進制的轉換

3．3最小棧

3．4隊列

3．5兩個棧實現一個隊列

3．6以遞歸方式反轉一個棧

3．7遞歸加棧實現漢諾塔

第4章鏈表

4．1鏈表結構

4．2單向鏈表

4．2．1單向鏈表的追加和遍歷

4．2．2單向鏈表的隨機訪問

4．2．3單向鏈表的隨機插入

4．2．4單向鏈表的隨機刪除

4．2．5從尾到頭打印單向鏈表

4．2．6反轉一個單向鏈表

4．2．7反轉單向鏈表中索引n~m處節點

4．2．8合並多個鏈表

4．2．9合並兩個有序鏈表

4．2．10相交鏈表

4．2．11判斷兩個鏈表是否相交

4．2．12構造帶環的單向鏈表

4．2．13判斷鏈表是否有環並找出環的閉合點

4．3單向循環鏈表

4．3．1單向循環鏈表的追加和遍歷

4．3．2約瑟夫環

4．4雙向鏈表

4．4．1雙向鏈表的追加和遍歷

4．4．2雙向鏈表的隨機插入和刪除

4．4．3雙向鏈表實現插值法排序

4．5雙向循環鏈表

4．5．1雙向循環鏈表的追加和遍歷

4．5．2雙向循環鏈表的隨機插入和隨機刪除

第5章數組

5．1數組結構

5．2消除數組中重復元素

5．3求數組中的最大值和次大值

5．4求一個數組的支點元素

5．5求數組的幸運值

5．6在數組中實現二分法查找

5．7求無序數組中最長連續子串的長度

5．8求數組中出現次數超過總數一半的數

5．9環路加油站問題

第6章樹結構

6．1樹、森林、二叉樹

6．2二叉排序樹

6．2．1二叉排序樹的插入與中序遍歷

6．2．2二叉排序樹的深度優先遍歷和廣度優先遍歷

6．2．3二叉排序樹的前序遍歷

6．2．4二叉排序樹的後序遍歷

6．2．5二叉排序樹的廣度優先遍歷

6．2．6二叉排序樹的節點刪除

6．2．7二叉排序樹的按層遍歷

6．2．8求二叉樹的最大深度、最小深度

6．2．9求二叉樹中任意兩個節點之間的最低公共祖先

6．3滿二叉樹

6．3．1滿二叉樹的構建

6．3．2判斷一棵二叉樹是不是滿二叉樹

6．4完全二叉樹

6．4．1完全二叉樹的插入

6．4．2查看完全二叉樹

6．4．3判斷一棵二叉樹是不是完全二叉樹

6．5平衡二叉樹(AVL樹)

6．5．1平衡二叉樹的節點插入

6．5．2平衡二叉樹的節點刪除

6．6紅黑樹(RBTree)

6．6．1紅黑樹的插入

6．6．2紅黑樹的遍歷操作

6．6．3紅黑樹的刪除操作

6．6．4完整代碼實現

6．6．5紅黑樹練習題

第7章堆結構

7．1堆

7．2二叉堆

7．2．1二叉堆的插入

7．2．2二叉堆的遍歷

7．2．3二叉堆的刪除

7．3大(小)頂堆

7．3．1大(小)頂堆的插入

7．3．2大(小)頂堆的堆排序

第8章散列表

8．1散列表(哈希表)

8．2散列函數

8．3求兩數組交集

8．48個方向

第9章字典樹

9．1字典樹結構

9．2字典樹的存入

9．3字典樹的檢索

9．4遍歷字典樹中的鍵

第10章圖

10．1圖結構

10．2圖的表示

10．2．1鄰接矩陣

10．2．2鄰接表

10．2．3鄰接矩陣和鄰接表的使用場景

10．2．4邊的權重

10．3圖結構的代碼實現

10．3．1鄰接矩陣方式

10．3．2鄰接表方式

10．4圖的遍歷

10．4．1圖結構的深度優先遍歷和廣度優先遍歷

10．4．2圖遍歷的代碼實現

10．5生成樹和最小生成樹

10．5．1Prim算法求取最小生成樹

10．5．2最小生成樹的代碼實現

第11章排序算法

11．1排序算法的幾個基本概念

11．1．1排序的穩定性和不穩定性

11．1．2排序的時間復雜度

11．1．3排序的空間復雜度

11．2冒泡排序

11．3選擇排序

11．4插入排序

11．5希爾排序

11．6歸並排序

11．7快速排序

11．8計數排序

11．9桶排序

11．10基數排序

11．1110種常見排序算法的復雜度