高等院校計算機課程設計指導叢書：數據結構課程設計（第2版）

專家指導委員會
前言
第0章 緒論 1
0.1 課程設計特點 1
0.2 課程設計結構 1

第1章 鏈表的應用 5
1.1 知識解析 5
1.1.1 線性表的基礎知識 5
1.1.2 線性表的基本運算 7
1.2 算法設計與分析 9
1.2.1 順序表上的相關操作 9
1.2.2 線性鏈表上相關操作的算法 及其分析 11
1.3 一元多項式的運算 13
1.3.1 問題分析 14
1.3.2 算法解析 14
1.3.3 完整程序清單 17
1.3.4 程序運行測試 19
1.4 通訊錄管理系統的設計與實現 20
1.4.1 問題分析 20
1.4.2 系統設計 21
1.4.3 完整程序清單 27
1.4.4 程序運行測試 32
1.5 約瑟夫生者死者遊戲 35
1.5.1 問題分析 35
1.5.2 程序實現 37
1.5.3 程序運行測試 39
1.6 評價標準 39

第2章 棧和隊列的應用 40
2.1 知識解析 40
2.1.1 棧和隊列的基本概念 40
2.1.2 棧和隊列的基本運算 41
2.1.3 棧和隊列的存儲結構 41
2.2 算法設計與分析 45
2.2.1 棧的特性 45
2.2.2 循環隊列的特點 45
2.2.3 棧的應用舉例 46
2.3 八皇后問題 48
2.3.1 設計要求與分析 48
2.3.2 算法求精 49
2.3.3 算法擴充 50
2.3.4 完整的算法實現 51
2.4 表達式求值問題 53
2.4.1 設計要求與分析 54
2.4.2 中綴表達式到後綴表達式的 轉換 54
2.4.3 後綴表達式的計算 56
2.4.4 表達式運算算法的實現 57
2.5 評價標準 61

第3章 文本文件的檢索 62
3.1 知識解析 62
3.1.1 串的概念 62
3.1.2 順序串 62
3.1.3 鏈串 63
3.1.4 串運算的實現 63
3.2 算法設計與分析 65
3.3 串模式匹配算法的設計與實現 67
3.3.1 設計要求 67
3.3.2 算法分析與設計 67
3.3.3 調用算法實例 68
3.4 文本文件單詞的檢索與計數 69
3.4.1 設計要求與分析 69
3.4.2 設計實例的實現 70
3.5 評價標準 74

第4章 稀疏矩陣和廣義表 75
4.1 知識解析 75
4.1.1 多維數組 75
4.1.2 特殊矩陣 76
4.1.3 廣義表 77
4.2 算法設計與分析 78
4.2.1 矩陣運算 78
4.2.2 廣義表運算 80
4.3 稀疏矩陣的壓縮存儲和運算 80
4.3.1 設計要求與分析 80
4.3.2 設計實例 81
4.3.3 完整的程序實現 83
4.4 廣義表的運算 84
4.4.1 設計要求 84
4.4.2 算法分析 85
4.4.3 算法實現 87
4.4.4 運行測試實例 89
4.5 評價標準 92

第5章 樹結構的應用 93
5.1 知識解析 93
5.1.1 樹的概念和術語 93
5.1.2 二叉樹概述 93
5.1.3 二叉樹的運算 94
5.1.4 線索二叉樹 96
5.1.5 樹和森林 98
5.1.6 赫夫曼樹 99
5.2 算法設計與分析 100
5.2.1 二叉樹的遍歷 100
5.2.2 赫夫曼樹 101
5.2.3 二叉樹上的其他運算 102
5.3 求二叉樹上結點的路徑 104
5.3.1 設計要求與分析 104
5.3.2 設計實例 105
5.3.3 算法運行實例 109
5.4 赫夫曼編碼的應用 112
5.4.1 設計要求與分析 112
5.4.2 赫夫曼樹的建立 112
5.4.3 赫夫曼編碼 114
5.4.4 代碼文件的譯碼 115
5.4.5 算法運行實例 116
5.5 評價標準 120

第6章 圖結構的應用 121
6.1 知識解析 121
6.1.1 圖的基本術語 121
6.1.2 圖的存儲表示方式 122
6.1.3 圖的基本運算 123
6.1.4 拓撲排序法 126
6.2 算法設計與分析 126
6.2.1 圖的存儲表示 126
6.2.2 圖的遍歷 127
6.2.3 頂點之間的最短路徑 129
6.3 交通諮詢系統設計 130
6.3.1 設計要求與分析 130
6.3.2 設計功能的實現 131
6.3.3 主控程序 133
6.3.4 運行實例 134
6.4 評價標準 138

第7章 排序算法的應用 140
7.1 知識解析 140
7.1.1 排序的基本概念 140
7.1.2 常用排序方法 141
7.1.3 各種排序方法比較 142
7.2 算法實現思路 143
7.2.1 插入排序 143
7.2.2 交換排序 144
7.2.3 選擇排序 146
7.2.4 分配排序 149
7.3 學生成績處理 150
7.3.1 設計要求與分析 150
7.3.2 算法設計源程序 151
7.3.3 主控程序 156
7.3.4 運行實例 157
7.4 評價標準 159

第8章 查找算法的應用 160
8.1 知識解析 160
8.1.1 順序表的查找 160
8.1.2 二叉排序樹 162
8.1.3 散列表的查找 163
8.2 算法設計與分析 166
8.2.1 有序表上的順序查找 167
8.2.2 查找算法分析 167
8.3 航班信息的查詢與檢索 168
8.3.1 設計要求 168
8.3.2 設計分析 169
8.3.3 算法實現 170
8.3.4 源程序清單 172
8.3.5 運行測試實例 177
8.4 評價標準 179

第9章 文件的應用 181
9.1 知識解析 181
9.1.1 文件的基本概念 181
9.1.2 常用的文件結構 182
9.2 文件實例分析 184
9.3 圖書管理信息系統的設計與實現 186
9.3.1 設計要求 186
9.3.2 設計分析 187
9.3.3 設計的實現 191
9.3.4 主控菜單的設計 200
9.3.5 運行測試實例 202
9.4 評價標準 207
參考文獻 208