數據結構與算法（第2版·微課視頻版）

下載源碼

第1章緒論

1.1數據結構簡介

1.1.1“數據結構”課程的內容

1.1.2數據結構的基本概念和術語

1.2抽象數據類型

1.3算法的執行效率及其度量

1.3.1算法的特性

1.3.2算法設計的要求

1.3.3算法效率的度量

1.3.4算法的存儲空間需求

1.4算法分析

1.4.1算法設計與分析的重要性

1.4.2一個簡單的算法分析設計實例

習題

ACM/ICPC實戰練習

第2章線性結構

2.1線性表

2.1.1線性表的定義

2.1.2線性表的抽象數據類型

2.1.3線性表的存儲結構

2.2線性表的順序存儲及運算實現

2.2.1順序表

2.2.2順序表上基本運算的實現

2.2.3順序表應用舉例

2.3線性表的鏈式存儲和運算實現

2.3.1單鏈表

2.3.2單鏈表上基本運算的實現

2.3.3循環鏈表

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棧與遞歸

2.5隊列

2.5.1順序隊列

2.5.2鏈式隊列

2.5.3基於隊列的算法設計實例

2.6數組

2.6.1數組的定義

2.6.2數組的順序表示和實現

2.6.3特殊矩陣的壓縮存儲

習題

ACM/ICPC實戰練習

第3章字符串

3.1串類型定義

3.2串的表示和實現

3.2.1串的定長順序存儲結構及其基本運算實現

3.2.2串的堆存儲結構及其基本運算實現

3.2.3串的鏈式存儲結構及其基本運算實現

3.3串的模式匹配算法

3.3.1樸素匹配算法

3.3.2KMP算法

3.3.3基於KMP算法的應用舉例

習題

ACM/ICPC實戰練習

第4章樹和二叉樹

4.1樹

4.1.1樹的定義和基本術語

4.1.2樹的抽象數據類型

4.1.3樹的存儲結構

4.1.4樹的遍歷

4.1.5樹的應用

4.2二叉樹

4.2.1二叉樹的定義

4.2.2二叉樹的性質

4.2.3二叉樹的存儲結構

4.2.4表達式樹

4.2.5二叉樹的基本操作及實現

4.3遍歷二叉樹和線索二叉樹

4.3.1遍歷二叉樹

4.3.2二叉樹遍歷的非遞歸實現

4.3.3線索二叉樹

4.4樹、森林和二叉樹的轉換

4.4.1樹轉換為二叉樹

4.4.2森林轉換為二叉樹

4.4.3二叉樹轉換為樹和森林

4.5哈夫曼編碼樹

4.5.1最優二叉樹(哈夫曼樹)

4.5.2哈夫曼編碼

4.6二叉搜索樹

4.6.1二叉搜索樹的基本操作

4.6.2平衡二叉樹(AVL樹)

4.7伸展樹

4.7.1伸展樹的基本操作

4.7.2伸展樹的參考例程

4.8堆與優先隊列

4.8.1堆的邏輯定義

4.8.2堆的性質

4.8.3堆的基本操作

4.8.4堆的實現例程

4.9B樹和B+樹

4.9.1B樹及其查找

4.9.2B樹的插入和刪除

4.9.3B+樹

4.10樹結構搜索算法應用案例

4.10.1基於二叉樹遍歷的應用

4.10.2ACM/ICPC競賽題例分析

習題

ACM/ICPC實戰練習

第5章圖論算法

5.1圖

5.1.1圖的定義和術語

5.1.2圖的抽象數據類型

5.1.3圖的存儲結構

5.2圖的遍歷算法

5.2.1深度優先搜索

5.2.2廣度優先搜索

5.2.3深度優先搜索與廣度優先搜索的應用

5.3圖的連通性

5.3.1無向圖的連通性

5.3.2有向圖的連通性

5.3.3生成樹和生成森林

5.3.4關節點和重連通分量

5.3.5有向圖的強連通分量

5.4有向無環圖及其應用

5.4.1有向無環圖的概念

5.4.2AOV網與拓撲排序

5.4.3AOE網與關鍵路徑

5.5最短路徑算法

5.5.1無權最短路徑

5.5.2Dijkstra算法

5.5.3具有負值邊的圖

5.5.4所有點對的最短路徑

5.6最小支撐樹

5.6.1Prim算法

5.6.2Kruskal算法

5.6.3最小生成樹算法應用

5.7網絡流問題

5.7.1網絡流的最大流問題

5.7.2網絡流應用

習題

ACM/ICPC實戰練習

第6章內部排序

6.1概述

6.2基於順序比較的簡單排序算法

6.2.1插入排序

6.2.2冒泡排序

6.2.3直接選擇排序

6.2.4簡單排序算法的時間代價對比

6.3縮小增量排序方法——希爾排序

6.4基於分治策略的排序

6.4.1快速排序

6.4.2歸並排序

6.5樹的排序方法

6.5.1堆排序

6.5.2樹的選擇排序

6.6分配排序和基數排序

6.6.1桶式排序

6.6.2基數排序

6.7內部排序問題討論與分析

6.7.1常用排序算法性能簡要分析

6.7.2排序問題的下限

6.8排序應用舉例

習題

ACM/ICPC實戰練習

第7章文件管理和外排序

7.1外存儲器

7.1.1磁盤

7.1.2磁盤訪問時間估算

7.2外存文件的組織

7.2.1文件組織

7.2.2文件上的操作

7.2.3C語言中的文件流操作

7.3緩沖區和緩沖池

7.4外排序

7.4.1二路外排序

7.4.2多路平衡歸並的實現

7.5置換選擇排序

7.6最佳歸並樹

習題

第8章檢索與散列表

8.1檢索的基本概念

8.2基於線性表的檢索

8.2.1順序檢索

8.2.2有序表的二分檢索

8.2.3有序表的插值查找和斐波那契查找

8.2.4分塊檢索

8.3集合的檢索

8.3.1集合的數學特性

8.3.2電腦中的集合

8.4鍵樹

8.4.1基本概念

8.4.2鍵樹的存儲表示

8.4.3鍵樹相關算法實現

8.5散列方法及其檢索

8.5.1散列函數

8.5.2開散列方法（分離鏈接法）

8.5.3開放尋址法

8.5.4散列方法的效率分析

8.6散列表及檢索的應用

習題

ACM/ICPC實戰練習

參考文獻