數據結構（Python語言描述）-微課視頻版

《數據結構(Python語言描述）-微課視頻版》是清華大學出版社2020年出版圖書，作者張玉華 呂強 朱曉旭

基本介紹

• 書名：數據結構(Python語言描述）-微課視頻版
• 作者：張玉華 呂強 朱曉旭
• 出版社：清華大學出版社

內容簡介

本書首先簡要回顧了Python語言的基礎知識和程式設計的基本原則，然後依次介紹線性表、棧、佇列、樹、二叉樹、圖等常見的數據結構的基本概念、特點、存儲表示、基本操作的算法實現及套用場合，最後介紹計算機中最常見的查找、排序等操作的算法原理、實現方法，並對算法的時間、空間性能等進行綜合分析。 本書可作為高等學校計算機科學、主煮元軟體工程、人工智慧等專業“數據結構”課程的理想教材，也可供程式設計師、系統工程師等相關人員閱讀參考。

目錄

源碼下載

第1章Python語言程式設計基礎

1.1Python基礎知識

1.1.1Python概述及運行環境

1.1.2Python的變數和數據類型

1.1.3Python的運算符

1.1.4函式

1.1.5輸入、輸出和檔案

1.1.6異常處理

1.1.7模組

1.2Python面向對象編程

1.2.1面向對象的基本概念

1.2.2類的定義和請棄使用

1.2.3繼承與派生

1.2.4疊代器與生成器

1.3與數據結構和算法相關的Python模組

1.3.1抽象基類和abc模組

1.3.2ctypes模組

1.3.3array模組

1.3.4NumPy模組

1.3.5collections模組

1.4上機實驗

1.4.1找零錢

1.4.2數列面向對象練習

本章習題

第2章數奔定墓據結構概述

2.1基本概念

2.1.1數據與數據結構

2.1.2數據類型

2.2數據結構課程討論的內容

2.3算法及性能分析

2.3.1算法

2.3.2算法分析基礎

2.3.3同一問題的不同算法

2.4上機實驗

2.4.1Python內置類型常見操作的性能驗證

2.4.2列表生成方法的性能比較

2.4.3變位詞判去循旬斷算法的性能比較

2.4.4哥德巴赫猜想問題

本章習題

第3章線性表

3.1線性表的基本概念

3.2線性表的抽象數據類型

3.3線性表的順序存儲及實現

3.3.1線性表順序存儲的基本方法

3.3.2Python列表的內部實現

3.3.3基於Python列表的實現

3.3.4基於底層C數組的實現

3.4線性表的鏈式存儲及實現

3.4.1單鍊表

3.4.2循環鍊表

3.4.3雙向鍊表

3.5順序表與鍊表實現小結

3.5.1順序表與鍊表的比較

3.5.2各種鍊表實現的比較

3.5.3自頂向下的數據結構實現

3.5.4算法設計的基本步驟

3.6線性表的套用

3.6.1求兩個線性表的相同元素

3.6.2約瑟夫環問題

3.7線性表算法舉例

3.7.1順序表下的算法

3.7.2帶頭結點單鍊表下的算法

3.7.3與線性表具體實現無關的算法

3.8上機實驗

3.8.1線性表的順序表實現

3.8.2線性表的單鍊表實現

3.8.3線性表的雙向非循環鍊表實現

3.8.4消費支出項目管理

3.8.5每日快遞

3.8.6撲克牌整理

本章習題

第4章棧

4.1棧的基本概念

4.2棧的抽象數據類型

4.3棧的順序存儲及實現

4.3.1利用Python列表實現

4.3.2記錄容量和棧頂位置的實現

4.4棧的鏈式存儲及實現

4.5棧的典型套用

4.5.1括弧匹配檢驗

4.5.2計算後綴表達式的值

4.5.3計算中綴表達式的值

4.5.4迷宮求解

4.6上機實驗

4.6.1棧的實現和套用

4.6.2HTML文檔標籤匹配

4.6.3表達式求值

4.6.4四色地圖著色

4.6.5用回溯法求解n皇后問題

本章習題

第5章佇列

5.1佇列的基本概念

5.2佇列的抽象數據類型

5.3佇列的順序存儲及實現

5.3.1物理模型法

5.3.2線性順序佇列

5.3.3循環佇列

5.4佇列的鏈式存儲及實現

5.5佇列的套用

5.5.1楊輝三角形的輸出

5.5.2一元多項式的計算

5.5.3基於佇列的迷宮求解

5.6雙端佇列

5.6.1雙端佇列的基本概念

5.6.2Python的雙端佇列類

5.6.3雙端佇列的蒸詢說拜套用

5.7優先權佇列

5.8Python提供的多種佇列

5.9上機實驗

5.9.1循環佇列的實現

5.9.2鏈佇列的實現

5.9.3猜猜我的QQ號

5.9.4字元串的匹配

5.9.5製作糖果

5.9.6紙牌遊戲

本章習題

第6章遞歸

6.1遞歸汽拒淚及遞歸算法

6.1.1什麼是遞歸

6.1.2問題求解方法的遞歸定義

6.2線性表下遞歸算法的設計

6.2.1數據結構的遞歸定義

6.2.2順序表下的遞歸算法

6.2.3單鍊表下的遞歸算法

6.3遞歸多主槓捆求解舉例

6.3.1n皇后問題

6.3.2迷宮求解

6.3.3組合數求解

6.4遞歸算法性能分析

6.4.1函式調用與棧

6.4.2遞歸函式的運行過程及性能分析

6.4.3遞歸函式轉換為非遞歸函式

6.5常見的算法設計模式

6.5.1窮舉算法

6.5.2貪心算法

6.5.3遞歸算法

6.5.4帶備忘錄的遞歸算法

6.5.5動態規劃法

6.6上機實驗

6.6.1階乘函式的時間性能分析

6.6.2單鍊表類的遞歸實現

6.6.3入棧與出棧的模擬

本章習題

第7章字元串和數組

7.1字元串

7.1.1字元串的基本概念

7.1.2字元串的抽象數據類型

7.1.3字元串的存儲

7.1.4字元串的匹配

7.2數組

7.2.1數組相關概念

7.2.2表格的存儲

7.2.3特殊矩陣的壓縮存儲

7.2.4數組的套用

7.3上機實驗

7.3.1字元串匹配算法的驗證

7.3.2幻方的判斷和奇數階幻方的構造

本章習題

第8章二叉樹

8.1基礎知識

8.1.1二叉樹的基本概念

8.1.2相關術語

8.1.3一些特殊的二叉樹

8.1.4二叉樹的抽象數據類型

8.2二叉樹的性質

8.3二叉樹的存儲結構及實現

8.3.1二叉樹的順序存儲

8.3.2二叉樹的嵌套列表存儲

8.3.3二叉樹的鏈式存儲及實現

8.4二叉樹的操作

8.4.1二叉樹的遍歷

8.4.2二叉樹遍歷的遞歸算法

8.4.3二叉樹的遞歸算法舉例

8.4.4二叉樹的非遞歸遍歷

8.4.5二叉樹的創建

8.4.6二叉樹的圖形化輸出

8.5堆與優先權佇列

8.5.1二叉堆的定義

8.5.2二叉堆的主要操作

8.5.3二叉堆的實現

8.6哈夫曼樹及其套用

8.6.1哈夫曼樹的相關概念

8.6.2哈夫曼樹的構造

8.6.3哈夫曼編碼

8.7上機實驗

8.7.1二叉樹的鏈式實現

8.7.2表達式二叉樹及計算

8.7.3哈夫曼編碼的實現

本章習題

第9章樹

9.1基礎知識

9.1.1樹的基本概念

9.1.2樹的抽象數據類型

9.1.3樹的性質

9.2樹的存儲結構

9.2.1雙親表示法

9.2.2孩子鍊表表示法

9.2.3孩子兄弟鍊表表示法

9.3樹與二叉樹的轉換

9.3.1樹轉換為二叉樹

9.3.2二叉樹轉換為樹

9.3.3森林轉換為二叉樹

9.3.4二叉樹轉換為森林

9.4樹與森林的遍歷

9.4.1樹的遍歷

9.4.2森林的遍歷

9.5樹的實現

9.5.1樹的孩子兄弟鍊表結點類

9.5.2樹的孩子兄弟鍊表類

9.6上機實驗

9.6.1樹的實現

9.6.2家譜處理

本章習題

第10章圖

10.1基礎知識

10.1.1圖的定義

10.1.2圖的相關術語

10.1.3圖的抽象數據類型

10.2圖的存儲結構及實現

10.2.1鄰接矩陣

10.2.2鄰接表

10.3圖的遍歷

10.3.1深度優先搜尋

10.3.2廣度優先搜尋

10.3.3遍歷算法的套用

10.4最小生成樹

10.4.1Prim算法

10.4.2Kruskal算法

10.5最短路徑

10.5.1單源點最短路徑

10.5.2每對頂點間的最短路徑

10.6拓撲排序

10.6.1概述

10.6.2廣度優先拓撲排序

10.6.3深度優先拓撲排序

10.7關鍵路徑

10.7.1相關概念

10.7.2算法設計

10.7.3算法實現

10.8上機實驗

10.8.1無向圖的實現

10.8.2無向網的最小生成樹

10.8.3有向網的最短路徑

10.8.4有向無環圖的拓撲排序

10.8.5AOE網的關鍵路徑

10.8.6拯救007

10.8.7騎士週遊問題

本章習題

第11章查找

11.1基礎知識

11.1.1相關概念

11.1.2查找的分類

11.1.3查找算法的性能衡量

11.1.4查找表的抽象數據類型

11.1.5記錄類型的定義

11.2線性表下的查找

11.2.1基於無序線性表的查找

11.2.2基於有序線性表的查找

11.2.3索引順序表及分塊查找

11.2.4查找算法性能的下界

11.3二叉樹下的查找

11.3.1二叉查找樹

11.3.2平衡二叉樹

11.4哈希表查找

11.4.1哈希表的定義

11.4.2哈希函式設計方法

11.4.3解決衝突的方法

11.4.4哈希表的實現

11.4.5哈希查找性能分析

11.5Python的集合和字典

11.6查找小結

11.7上機實驗

11.7.1線性表下查找算法的實現

11.7.2線性表下查找算法的性能測試與比較

11.7.3二叉查找樹的實現及查找性能測試與比較

11.7.4哈希表的實現及查找性能測試與比較

本章習題

第12章排序

12.1基礎知識

12.1.1相關概念

12.1.2排序表的類型定義

12.1.3排序的分類

12.1.4排序算法的性能衡量

12.2插入排序

12.2.1直接插入排序

12.2.2折半插入排序

12.2.3希爾排序

12.3交換排序

12.3.1冒泡排序

12.3.2快速排序

12.4選擇排序

12.4.1簡單選擇排序

12.4.2堆排序

12.5歸併排序

12.5.1自底向上的歸併排序

12.5.2自頂向下的歸併排序

12.6基數排序

12.6.1多關鍵字排序

12.6.2鏈式基數排序

12.7各種排序算法的比較

12.8高級語言中使用的排序

12.8.1C++標準模板庫中的排序

12.8.2TimSort排序

12.9上機實驗

12.9.1排序算法的實現

12.9.2排序算法的性能測試與比較

12.9.3教學系統數據查詢和統計

本章習題

參考文獻

3.7線性表算法舉例

3.7.1順序表下的算法

3.7.2帶頭結點單鍊表下的算法

3.7.3與線性表具體實現無關的算法

3.8上機實驗

3.8.1線性表的順序表實現

3.8.2線性表的單鍊表實現

3.8.3線性表的雙向非循環鍊表實現

3.8.4消費支出項目管理

3.8.5每日快遞

3.8.6撲克牌整理

本章習題

第4章棧

4.1棧的基本概念

4.2棧的抽象數據類型

4.3棧的順序存儲及實現

4.3.1利用Python列表實現

4.3.2記錄容量和棧頂位置的實現

4.4棧的鏈式存儲及實現

4.5棧的典型套用

4.5.1括弧匹配檢驗

4.5.2計算後綴表達式的值

4.5.3計算中綴表達式的值

4.5.4迷宮求解

4.6上機實驗

4.6.1棧的實現和套用

4.6.2HTML文檔標籤匹配

4.6.3表達式求值

4.6.4四色地圖著色

4.6.5用回溯法求解n皇后問題

本章習題

第5章佇列

5.1佇列的基本概念

5.2佇列的抽象數據類型

5.3佇列的順序存儲及實現

5.3.1物理模型法

5.3.2線性順序佇列

5.3.3循環佇列

5.4佇列的鏈式存儲及實現

5.5佇列的套用

5.5.1楊輝三角形的輸出

5.5.2一元多項式的計算

5.5.3基於佇列的迷宮求解

5.6雙端佇列

5.6.1雙端佇列的基本概念

5.6.2Python的雙端佇列類

5.6.3雙端佇列的套用

5.7優先權佇列

5.8Python提供的多種佇列

5.9上機實驗

5.9.1循環佇列的實現

5.9.2鏈佇列的實現

5.9.3猜猜我的QQ號

5.9.4字元串的匹配

5.9.5製作糖果

5.9.6紙牌遊戲

本章習題

第6章遞歸

6.1遞歸及遞歸算法

6.1.1什麼是遞歸

6.1.2問題求解方法的遞歸定義

6.2線性表下遞歸算法的設計

6.2.1數據結構的遞歸定義

6.2.2順序表下的遞歸算法

6.2.3單鍊表下的遞歸算法

6.3遞歸求解舉例

6.3.1n皇后問題

6.3.2迷宮求解

6.3.3組合數求解

6.4遞歸算法性能分析

6.4.1函式調用與棧

6.4.2遞歸函式的運行過程及性能分析

6.4.3遞歸函式轉換為非遞歸函式

6.5常見的算法設計模式

6.5.1窮舉算法

6.5.2貪心算法

6.5.3遞歸算法

6.5.4帶備忘錄的遞歸算法

6.5.5動態規劃法

6.6上機實驗

6.6.1階乘函式的時間性能分析

6.6.2單鍊表類的遞歸實現

6.6.3入棧與出棧的模擬

本章習題

第7章字元串和數組

7.1字元串

7.1.1字元串的基本概念

7.1.2字元串的抽象數據類型

7.1.3字元串的存儲

7.1.4字元串的匹配

7.2數組

7.2.1數組相關概念

7.2.2表格的存儲

7.2.3特殊矩陣的壓縮存儲

7.2.4數組的套用

7.3上機實驗

7.3.1字元串匹配算法的驗證

7.3.2幻方的判斷和奇數階幻方的構造

本章習題

第8章二叉樹

8.1基礎知識

8.1.1二叉樹的基本概念

8.1.2相關術語

8.1.3一些特殊的二叉樹

8.1.4二叉樹的抽象數據類型

8.2二叉樹的性質

8.3二叉樹的存儲結構及實現

8.3.1二叉樹的順序存儲

8.3.2二叉樹的嵌套列表存儲

8.3.3二叉樹的鏈式存儲及實現

8.4二叉樹的操作

8.4.1二叉樹的遍歷

8.4.2二叉樹遍歷的遞歸算法

8.4.3二叉樹的遞歸算法舉例

8.4.4二叉樹的非遞歸遍歷

8.4.5二叉樹的創建

8.4.6二叉樹的圖形化輸出

8.5堆與優先權佇列

8.5.1二叉堆的定義

8.5.2二叉堆的主要操作

8.5.3二叉堆的實現

8.6哈夫曼樹及其套用

8.6.1哈夫曼樹的相關概念

8.6.2哈夫曼樹的構造

8.6.3哈夫曼編碼

8.7上機實驗

8.7.1二叉樹的鏈式實現

8.7.2表達式二叉樹及計算

8.7.3哈夫曼編碼的實現

本章習題

第9章樹

9.1基礎知識

9.1.1樹的基本概念

9.1.2樹的抽象數據類型

9.1.3樹的性質

9.2樹的存儲結構

9.2.1雙親表示法

9.2.2孩子鍊表表示法

9.2.3孩子兄弟鍊表表示法

9.3樹與二叉樹的轉換

9.3.1樹轉換為二叉樹

9.3.2二叉樹轉換為樹

9.3.3森林轉換為二叉樹

9.3.4二叉樹轉換為森林

9.4樹與森林的遍歷

9.4.1樹的遍歷

9.4.2森林的遍歷

9.5樹的實現

9.5.1樹的孩子兄弟鍊表結點類

9.5.2樹的孩子兄弟鍊表類

9.6上機實驗

9.6.1樹的實現

9.6.2家譜處理

本章習題

第10章圖

10.1基礎知識

10.1.1圖的定義

10.1.2圖的相關術語

10.1.3圖的抽象數據類型

10.2圖的存儲結構及實現

10.2.1鄰接矩陣

10.2.2鄰接表

10.3圖的遍歷

10.3.1深度優先搜尋

10.3.2廣度優先搜尋

10.3.3遍歷算法的套用

10.4最小生成樹

10.4.1Prim算法

10.4.2Kruskal算法

10.5最短路徑

10.5.1單源點最短路徑

10.5.2每對頂點間的最短路徑

10.6拓撲排序

10.6.1概述

10.6.2廣度優先拓撲排序

10.6.3深度優先拓撲排序

10.7關鍵路徑

10.7.1相關概念

10.7.2算法設計

10.7.3算法實現

10.8上機實驗

10.8.1無向圖的實現

10.8.2無向網的最小生成樹

10.8.3有向網的最短路徑

10.8.4有向無環圖的拓撲排序

10.8.5AOE網的關鍵路徑

10.8.6拯救007

10.8.7騎士週遊問題

本章習題

第11章查找

11.1基礎知識

11.1.1相關概念

11.1.2查找的分類

11.1.3查找算法的性能衡量

11.1.4查找表的抽象數據類型

11.1.5記錄類型的定義

11.2線性表下的查找

11.2.1基於無序線性表的查找

11.2.2基於有序線性表的查找

11.2.3索引順序表及分塊查找

11.2.4查找算法性能的下界

11.3二叉樹下的查找

11.3.1二叉查找樹

11.3.2平衡二叉樹

11.4哈希表查找

11.4.1哈希表的定義

11.4.2哈希函式設計方法

11.4.3解決衝突的方法

11.4.4哈希表的實現

11.4.5哈希查找性能分析

11.5Python的集合和字典

11.6查找小結

11.7上機實驗

11.7.1線性表下查找算法的實現

11.7.2線性表下查找算法的性能測試與比較

11.7.3二叉查找樹的實現及查找性能測試與比較

11.7.4哈希表的實現及查找性能測試與比較

本章習題

第12章排序

12.1基礎知識

12.1.1相關概念

12.1.2排序表的類型定義

12.1.3排序的分類

12.1.4排序算法的性能衡量

12.2插入排序

12.2.1直接插入排序

12.2.2折半插入排序

12.2.3希爾排序

12.3交換排序

12.3.1冒泡排序

12.3.2快速排序

12.4選擇排序

12.4.1簡單選擇排序

12.4.2堆排序

12.5歸併排序

12.5.1自底向上的歸併排序

12.5.2自頂向下的歸併排序

12.6基數排序

12.6.1多關鍵字排序

12.6.2鏈式基數排序

12.7各種排序算法的比較

12.8高級語言中使用的排序

12.8.1C++標準模板庫中的排序

12.8.2TimSort排序

12.9上機實驗

12.9.1排序算法的實現

12.9.2排序算法的性能測試與比較

12.9.3教學系統數據查詢和統計

本章習題

參考文獻