數據結構(Python語言描述）(第2版·微課視頻版）

目錄

掃一掃

源碼下載

第一部分基礎篇

第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

第二部分數據結構與算法篇

第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

第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

第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

第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

第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

第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

第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

第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

第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

第三部分查找與排序篇

第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

第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

參考文獻