數據結構簡明教程（C/C++版）

目錄

第1章緒論1

1.1數據結構1

1.1.1基本概念1

1.1.2三要素2

1.2算法分析5

1.2.1算法的定義5

1.2.2算法的評價標準6

1.2.3時間復雜度7

1.2.4空間復雜度9

1.3程序設計基礎10

1.3.1符號常量11

1.3.2數據類型12

1.3.3動態存儲分配15

思考與練習16第2章線性表17

2.1順序表17

2.1.1順序表的類型定義17

2.1.2順序表的基本操作18

2.2鏈表21

2.2.1單鏈表21

2.2.2雙向鏈表26

2.2.3循環鏈表28

2.3線性表的應用29

2.3.1擴容29

2.3.2查找30

2.3.3求並集32

思考與練習34第3章棧和隊列35

3.1棧35

3.1.1順序棧35

3.1.2鏈棧37

3.2隊列38

3.2.1循環隊列38

3.2.2鏈隊列42

3.3棧和隊列的應用42

3.3.1字符和數值的處理43

3.3.2遞歸的設計與實現47

思考與練習51第4章樹和二叉樹52

4.1樹52

4.1.1樹的基本術語53

4.1.2樹的存儲結構54

4.2二叉樹57

4.2.1二叉樹的性質57

4.2.2二叉樹的存儲結構60

4.2.3樹、森林與二叉樹的轉換61

4.3樹和二叉樹的操作63

4.3.1遍歷二叉樹63

4.3.2創建二叉樹66

4.3.3樹和森林的遍歷67

4.4樹和二叉樹的應用67

4.4.1從遍歷序列還原樹67

4.4.2二叉樹的復制與統計69

4.4.3哈夫曼樹70

思考與練習73第5章圖74

5.1圖的基本概念74

5.2圖的存儲結構78

5.2.1鄰接矩陣78

5.2.2鄰接表79

5.2.3鄰接多重表和十字鏈表81

5.3圖的遍歷82

5.3.1深度優先搜索83

5.3.2廣度優先搜索85

5.4圖的應用87

5.4.1最小生成樹87

5.4.2最短路徑90

5.4.3拓撲排序93

5.4.4關鍵路徑95

思考與練習98第6章查找100

6.1查找的基本概念100

6.2線性表的查找101

6.2.1順序查找101

6.2.2折半查找102

6.2.3分塊查找105

6.3二叉排序樹的查找106

6.3.1二叉排序樹的定義107

6.3.2二叉排序樹的插入109

6.3.3二叉排序樹的刪除111

6.4散列表的查找114

6.4.1散列函數的構造方法115

6.4.2處理沖突的方法117

6.4.3性能分析119

思考與練習120第7章排序122

7.1排序的基本概念122

7.2簡單的排序算法124

7.2.1冒泡排序126

7.2.2簡單選擇排序128

7.2.3直接插入排序130

7.3先進的排序算法135

7.3.1希爾排序135

7.3.2堆排序138

7.3.3歸並排序144

7.3.4快速排序147

7.4內部排序的性能比較152

思考與練習154附錄A課程內容與考核要求155附錄B抽象數據類型的定義164附錄C上機實驗的設計方法175附錄D練習題解答（示例）178參考文獻201