數據結構與算法教材（Python語言實現）

《數據結構與算法教材（Python語言實現）》是2023年中國水利水電出版社出版的圖書。

基本介紹

• 中文名：數據結構與算法教材（Python語言實現）
• 出版時間：2023年8月1日
• 出版社：中國水利水電出版社
• ISBN：9787522615974

內容簡介

《數據結構與算法（Python語言實現）》是一本全面、細緻、通俗易懂的數據結構和算法教材。數據結構與算法，是理論和實踐必須緊密結合的課程。對各類數據結構和算法，不但要掌握其理論，還應該能夠熟練地編程實現。相比大多數數據結構和算法教材，本書的最大特點就是高標準的實踐性。除了少數特別複雜的數據結構，95%的數據結構和算法，都給出了完整可運行的代碼，共 115 份，並且這些代碼幾乎都出現在具體的例題中。

本書的例題和編程習題都可以在北京大學的線上程式評測平台OpenJudge上提交解題程式並自動評判對錯。

本書內容和習題按難度做了明確分級，因此不論計算機相關專業還是非計算機相關專業的師生，都可以從中各取所需。本書可以作為數據結構和算法入門教材，也可以作為考研和找工作時提高面試成功率的秘籍。

圖書目錄

前言

第1章緒論

1.1算法和算法分析

1.1.1什麼是算法

1.1.2算法的時間複雜度及其表示法

1.2數據結構

1.2.1數據的邏輯結構

1.2.2數據的存儲結構

1.2.3數據結構上的操作

1.3小結

1.4習題

第2章Python語言鞏固與提高

2.1Python變數的指針本質

2.2Python操的時間複雜度

2.3函式

2.3.1lambda達式

2.3.2高階函式和閉包

2.3.3 global變和nonlocal變

2.3.4函式參數的默認值

2.3.5參數個數可變的函式

★2.3.6生成器

★2.3.7裝飾器

2.4面向對象程式設計

2.4.1類和對象

2.4.2記憶體垃圾自動回收和析構函式

2.4.3靜態屬性和靜態方法

2.4.4私屬性、私方法和property裝飾器

2.4.5繼承（派生）

2.4.6對象的比較

2.4.7疊代器

2.4.8類的特殊方法

2.4.9類方法及修改類的方法

2.4.10內部類

2.3習題

第3章線性表

3.1順序表

3.2鍊表

3.2.1單鍊表

3.2.2循環單鍊表

3.2.3雙鍊表

3.2.4靜態鍊表

3.3順序表和鍊表的選擇

3.4小結

3.5習題

第4章枚舉與二分法

4.1枚舉

4.1.1案例：八皇后問題(P0070)

4.1.2案例：假幣問題(P0080)

4.1.3案例：特殊密碼鎖(P0090)

4.1.4案例：奧數問題(P0100)

4.2二分法

4.2.1案例：解方程(P0110).

4.2.2案例:網線主管(P0120).

★4.2.3案例：好鬥的牛(P0130)

4.3小結

4.4習題

第5章遞歸和分治

5.1用遞歸進行枚舉

5.1.1案例：N皇后問題(P0230)

5.1.2案例：奧數問題(P0100)的遞歸解法

5.1.3案例：全排列(P0240)

5.2解決用遞歸形式定義的問題

5.2.1案例：波蘭表達式(P0250)

5.2.2案例：繪製雪花曲線

5.3用遞歸進行問題分解

5.3.1案例：上台階(P0260).

5.3.2案例：算24(P0270)

5.3.3案例：放蘋果(P0280)

5.3.4案例：7的倍數取法有多少種(P0290)

5.4分治

5.4.1案例：求排列的逆序數(P0300)

5.4.2案例：漢諾塔問題(P0310)

5.4.3案例：快速冪

5.5小結

5.6習題

第6章棧和佇列

6.1棧

6.1.1案例：括弧配對(P0410)

6.1.2案例：後序表達式求值(P0420)

★6.1.3案例：中序表達式轉後序表達式(P0430).

★6.1.4案例：四則運算表達式求值(P0440)

6.1.5案例：合法出棧序列(P0450).

★★★6.2棧和遞歸的關係

6.3佇列

6.3.1基本實現

6.3.2循環佇列

6.3.3Python中列

★★6.3.4案例：滑動視窗(P0460)

★6.3.5案例：用兩個棧實現佇列

6.4用鍊表實現棧和佇列

6.5小結

6.6習題

第7章二叉樹

7.1二叉樹的概念

7.2二叉樹的性質

7.3二叉樹的表示

7.3.1用類表示二叉樹

7.3.2用列表表示二叉樹

7.3.3完全二叉樹的表示

7.4二叉樹的遍歷

7.4.1二叉樹的前序遍歷、後序遍歷、中序遍歷和按層遍歷

★7.4.2案例：文本縮進二叉樹(P0560).

7.4.3案例：根據二叉樹前序遍歷序列和中序序列建立樹(PO570)

★★★7.4.4案例：根據後序表達式建立表達式樹(PO580)

★7.4.5用生成器方式遍歷二叉樹

★7.4.6用非遞歸方式遍歷二叉樹

★★7.5線索二叉樹

7.6堆

7.6.1堆的概念

7.6.2堆的操作

7.6.3建堆

7.6.4堆的實現和優先佇列

7.6.5Python堆

7.7哈夫曼樹

7.7.1哈夫曼樹的概念和構造

7.7.2案例：柵欄修補(P0590)

7.7.3哈夫曼編碼

7.8小結

7.9習題

第8章樹、森林和並查集

8.1樹的概念

8.2樹的實現

8.2.1直觀表示法

8.2.2案例：括弧嵌套樹(P0740)

8.2.3兒子-兄弟表示法

8.2.4案例：樹轉兒子-兄弟樹(P0750)

8.2.5父結點表示法

8.3森林

8.4並查集

8.4.1並查集的概念和用途

8.4.2案例：疑似病人(P0760)

8.5小結

8.6習題

第9章字元串

9.1字元串的編碼

9.2字元串的實現

9.3字元串的匹配算法

9.3.1暴力匹配算法

★★9.3.2KMP字元串匹配算法

9.4小結

9.5習題

第10章動態規劃

10.1什麼是動態規劃

10.2動態規劃解題的一般思路

10.3案例：簡單背包問題(P0880)

★★10.4案例：不簡單的出棧序列統計(P0890).

★10.5案例：最長上升子序列(P0900)

★★10.6案例：最長公共子序列(P0910)

10.7小結

10.8習題

第11章圖的遍歷和搜尋

11.1圖的定義和術語

11.2圖的表示

11.2.1鄰接矩陣

11.2.2鄰接表

11.2.3鄰接表和鄰接矩陣的比較

11.3圖的遍歷

11.3.1深度優先遍歷

11.3.2案例：輸出無向圖深度優先遍歷序列(P1020)

11.3.3案例：城堡的房間(P1030)

11.3.4案例：判斷無向圖是否連通及是否有迴路(P1040)

11.3.5廣度優先遍歷

11.4圖的搜尋

11.4.1概述

11.4.2深度優先搜尋

11.4.3案例：走迷宮之一(P1050)

11.4.4案例：走迷宮之二(P1060)

11.4.5案例：走迷宮之三(P1070)

11.4.6廣度優先搜尋

11.4.7案例：抓住那頭牛(P1080)

11.4.8案例：“走迷宮之三”的廣度優先搜尋解法(P1070

★★11.4.9案例：拯救行動(P1100)

11.4.10深度優先搜尋和廣度優先搜尋的選擇

11.5小結

11.6習題

第12章圖論基礎套用算法

12.1最短路

12.1.1源短路問題的Dijkstra算法

12.1.2案例：簡單的糖果分配(P1220)

★12.1.3求每對頂點之間最短路的Floyd算法

★12.1.4案例：奶牛比賽(P1230)

12.2最小生成樹

12.2.1概述

★★12.2.2最小生成樹的性質

12.2.3Prim算法

12.2.4Kruskal

★12.2.5案例：團結就是力量(P1234)

★★12.2.6案例：北極網路(P1240)

12.3拓撲排序

12.3.1拓撲排序的定義和算法

12.3.2案例：火星人家族樹(P1250)

★12.4關鍵路徑

12.4.1關鍵路徑的定義和算法

★★12.4.2案例：火星大工程(P1260)

12.5小結

12.6習題

第13章排序

13.1插入排序

13.1.1直接插入排序

13.1.2折半插入排序

13.1.3希爾排序

13.2選擇排序

13.2.1簡單選擇排序

13.2.2堆排序

13.3歸併排序

13.4交換排序

13.4.1冒泡排序

13.4.2快速排序

13.5分配排序

13.5.1桶排序

13.5.2計數排序

13.5.3基數排序

★13.6外排序

13.6.1置換選擇排序

13.6.2多路歸併和敗者樹

13.7小結

13.8習題

第14章查找

14.1線性表查找

14.1.1順序查找

14.1.2二分查找

14.1.3 Python的二biseet

14.1.4分塊查找

14.2樹表查找

14.2.1二叉查找樹

14.2.1.1二叉查找樹插入結點

14.2.1.2二叉查找樹刪除結點

14.2.1.3二叉查找樹的實現及時間複雜度分析.

★14.2.2AVL樹（平衡二叉樹）

★14.2.2.1AVL樹插入結點

★★★14.2.2.2AVL樹刪除結點

★14.2.3紅黑樹

★14.2.3.1紅黑樹的定義和性質

★★14.2.3.2在紅黑樹中插入結點

★★★14.2.3.3紅黑樹刪除結點

★14.2.4外存查找：B-樹和B+樹

14.2.4.1B-樹的定義

14.2.4.2B-樹的查找

14.2.4.3B-樹的插人操作

14.2.4.4B-樹的刪除操作

14.2.4.5B+樹

14.2.4.6B-樹、B+樹和紅黑樹對比

14.3散列表

14.3.1散列函式設計

14.3.2散列表的插人和衝突消解

14.3.4散列表的刪除和查找

14.3.5散列表的效率分析

★★14.3.6Python中的列表

14.3.6.1 Python的

14.3.6.2 Python的策

14.4小結

14.5習題

第15章貪心算法

15.1案例：聖誕老人的禮物(P1370).

15.2案例：電影節(P1380)

15.3小結

15.4習題

附錄北京大學線上程式評測平台OpenJudge使用說明

參考文獻

作者簡介

郭煒

北京大學信息科學技術學院教師，在北京大學講授“數據結構與算法”“程式設計實習”“Python程式設計”“ICPC大學生程式設計競賽實踐”等課程多年，曾擔任北京大學ACM國際大學生程式設計競賽隊教練、13場ACM/ICPC國際大學生程式設計競賽亞洲區預選賽的命題負責人並親自命題。創建北京角鬥士軟體技術有限公司，具有豐富的軟體開發經驗並將其融入教學。主講的“程式設計實習”“程式設計與算法”系列慕課課程，榮獲國家精品線上開放課程。