第 1章 數據結構與算法概論1

1.1 問題求解1

1.1.1 計算機解決問題的步驟1

1.1.2 非數值數學模型3

1.2 數據結構概述5

1.2.1 數據結構的相關概念5

1.2.2 抽像數據類型7

1.3 算法概述9

1.3.1 算法及其特性9

1.3.2 算法設計的要求10

1.3.3 算法描述方法10

1.3.4 算法評價10

本章小結13

本章習題13

第 2章 線性表14

2.1 線性表的概念14

2.2 線性表的順序存儲結構15

2.2.1 順序表的概念15

2.2.2 順序表的操作15

2.3 線性表的鏈式存儲結構18

2.3.1 鏈表的概念18

2.3.2 單向鏈表19

2.3.3 雙向鏈表23

2.4 線性表特點與比較27

2.4.1 線性表的特點27

2.4.2 順序表與鏈表的比較27

2.4.3 單向鏈表與雙向鏈表的比較28

2.5 線性表的應用28

2.5.1 多項式的合並28

2.5.2 稀疏矩陣的表示30

2.5.3 約瑟夫問題32

本章小結33

本章習題34

第3章 棧和隊列35

3.1 棧35

3.1.1 棧的定義與基本操作35

3.1.2 棧的順序存儲結構與實現36

3.1.3 棧的鏈式存儲結構與實現39

3.1.4 順序棧和鏈棧的比較41

3.1.5 棧的應用案例41

3.2 隊列44

3.2.1 隊列的定義與基本操作44

3.2.2 隊列的順序存儲結構與實現45

3.2.3 隊列的鏈式存儲結構與實現49

3.2.4 循環隊列與鏈隊列的比較51

3.2.5 隊列的應用案例51

本章小結55

本章習題56

第4章 遞歸57

4.1 遞歸定義57

4.2 遞歸算法設計57

4.3 消除遞歸60

4.3.1 直接轉換法60

4.3.2 間接轉換法61

4.4 回溯法62

4.5 遞歸的評價65

本章小結66

本章習題66

第5章 樹68

5.1 樹的概念68

5.1.1 樹的定義68

5.1.2 樹的相關概念68

5.1.3 樹的表示69

5.2 二叉樹70

5.2.1 二叉樹的概念70

5.2.2 二叉樹的性質72

5.2.3 二叉樹的存儲72

5.2.4 二叉樹的遍歷74

5.3 樹、森林與二叉樹76

5.3.1 樹的存儲76

5.3.2 樹與二叉樹的轉換78

5.3.3 森林與二叉樹的轉換79

5.3.4 樹的遍歷80

5.4 哈夫曼樹81

5.4.1 哈夫曼樹的相關概念81

5.4.2 哈夫曼算法84

5.4.3 哈夫曼編碼85

5.5 堆86

5.5.1 堆的概念86

5.5.2 堆的操作87

5.5.3 堆的算法分析92

本章小結93

本章習題93

第6章 圖95

6.1 圖的概念95

6.1.1 圖的相關術語95

6.1.2 圖的存儲結構97

6.2 圖的遍歷101

6.2.1 深度優先遍歷101

6.2.2 廣度優先遍歷102

6.3 圖的應用104

6.3.1 最小生成樹104

6.3.2 拓撲排序問題106

6.3.3 關鍵路徑問題109

6.3.4 最短路徑問題110

本章小結118

本章習題118

第7章 排序120

7.1 排序的概念120

7.2 插入排序120

7.2.1 直接插入排序120

7.2.2 希爾排序122

7.3 交換排序122

7.3.1 冒泡排序122

7.3.2 快速排序124

7.4 選擇排序125

7.4.1 簡單選擇排序125

7.4.2 堆排序127

7.5 歸並排序130

7.6 排序算法比較131

本章小結132

本章習題132

第8章 查找133

8.1 查找的概念133

8.2 線性表查找134

8.2.1 順序查找134

8.2.2 二分查找135

8.2.3 分塊查找137

8.3 樹表查找138

8.3.1 二叉排序樹的節點139

8.3.2 二叉排序樹的查找139

8.3.3 二叉排序樹的插入140

8.3.4 二叉排序樹的構造141

8.3.5 二叉排序樹的刪除143

8.4 散列表查找144

8.4.1 散列查找145

8.4.2 散列函數145

8.4.3 衝突處理147

8.4.4 查找性能分析149

本章小結150

本章習題150