目錄
叢書序
前言
第1章 緒論 1
1.1 引例 1
1.2 基本概念 3
1.2.1 數據、數據元素、數據項和數據對象 3
1.2.2 數據結構 4
1.2.3 數據類型和抽象數據類型 6
1.3 算法和算法分析 9
1.3.1 算法的定義及算法描述 9
1.3.2 算法評價 10
1.3.3 算法的時間復雜度 12
1.3.4 算法的空間復雜度 16
小結 17
習題 18
上機實驗題 20
第2章 C/C++語言知識 21
2.1 指針 21
2.1.1 指針變量 21
2.1.2 指針運算 22
2.1.3 數組與指針 27
2.2 結構體 31
2.2.1 結構體的定義 31
2.2.2 結構體數組 33
2.2.3 結構體指針 34
2.3 共用體 37
2.4 C++運算符 39
2.4.1 動態(tài)申請與釋放內存運算符 39
2.4.2 引用 41
2.5 C程序分析 42
小結 44
習題 44
上機實驗題 47
第3章 線性表 48
3.1 引例 48
3.2 線性表的概念及運算 49
3.2.1 線性表的定義 49
3.2.2 線性表的抽象數據類型定義 49
3.3 線性表的順序表示和實現 50
3.3.1 線性表的順序存儲表示 50
3.3.2 順序表基本運算的實現 51
3.4 引例中讀書興趣小組活動管理的順序表解決 56
3.5 線性表的鏈式表示和實現 61
3.5.1 單鏈表的定義和表示 62
3.5.2 單鏈表基本運算的實現 62
3.5.3 順序表和鏈表的比較 70
3.6 引例中讀書興趣小組活動管理的鏈表解決 71
3.7 鏈表知識的擴展 76
3.7.1 單循環(huán)鏈表 76
3.7.2 雙向鏈表 77
3.8 線性表應用舉例 78
小結 85
習題 86
上機實驗題 89
第4章 棧和隊列 90
4.1 引例 90
4.2 棧 92
4.2.1 棧的概念及運算 92
4.2.2 棧的順序表示和實現 93
4.2.3 棧的鏈式表示和實現 95
4.3 引例中棧相關問題的解決 98
4.3.1 行編輯的解決 98
4.3.2 數制轉換的解決 99
4.3.3 表達式求值的解決 100
4.3.4 遞歸實現的解決 107
4.4 隊列 109
4.4.1 隊列的概念及運算 109
4.4.2 隊列的順序表示和實現 111
4.4.3 隊列的鏈式表示和實現 114
4.4.4 引例中銀行個人業(yè)務模擬問題的解決 117
小結 119
習題 120
上機實驗題 123
第5章 串 124
5.1 引例 124
5.2 串的概念及運算 124
5.2.1 串的定義 124
5.2.2 串的抽象數據類型定義 125
5.3 串的順序表示和實現 126
5.3.1 串的順序存儲表示 126
5.3.2 順序串基本運算的實現 127
5.4 串的鏈式表示和實現 129
5.4.1 串的鏈式存儲表示 129
5.4.2 鏈串基本運算的實現 130
5.5 串的模式匹配 132
5.5.1 Brute-Force算法 132
5.5.2 KMP算法 134
5.6 引例的解決 138
5.6.1 名和姓對換問題的解決 138
5.6.2 文本文件中單詞計數和查找問題的解決 139
小結 140
習題 140
上機實驗題 142
第6章 數組和廣義表 143
6.1 引例 143
6.2 數組 144
6.2.1 數組的概念及運算 144
6.2.2 數組的順序存儲表示 145
6.2.3 引例中求矩陣馬鞍點問題的解決 146
6.3 特殊矩陣的壓縮存儲 147
6.3.1 對稱矩陣 147
6.3.2 引例中求對稱矩陣的和與乘積問題的解決 148
6.3.3 三角矩陣 150
6.3.4 引例中求三角矩陣的和與乘積問題的解決 151
6.3.5 對角矩陣 152
6.4 廣義表 153
6.4.1 廣義表的概念及運算 153
6.4.2 廣義表的存儲結構 155
6.4.3 引例中m元多項式表示問題的解決 157
小結 158
習題 158
上機實驗題 160
第7章 樹和二叉樹 161
7.1 引例 161
7.2 樹的概念及運算 162
7.2.1 樹的定義 162
7.2.2 樹的抽象數據類型定義 164
7.3 二叉樹 165
7.3.1 二叉樹的概念及運算 165
7.3.2 二叉樹的性質 167
7.3.3 二叉樹的存儲結構 169
7.4 遍歷二叉樹 172
7.4.1 遍歷二叉樹的概念和實現 172
7.4.2 根據遍歷序列確定二叉樹 178
7.4.3 遍歷算法應用 179
7.5 線索二叉樹 182
7.5.1 線索二叉樹的概念 182
7.5.2 線索二叉樹的構造和遍歷 184
7.6 樹和森林 186
7.6.1 樹的存儲結構 186
7.6.2 樹、森林與二叉樹的相互轉換 189
7.6.3 樹與森林的遍歷 191
7.7 引例的解決 193
7.7.1 哈夫曼樹用于編碼的原理和方法 193
7.7.2 引例中字符編碼和譯碼問題的解決 196
7.7.3 引例中報文編碼和譯碼問題的解決 202？
小結 202
習題 203
上機實驗題 206
第8章 圖 207
8.1 引例 207
8.2 圖的概念及運算 210
8.2.1 圖的定義 210
8.2.2 圖的術語 211
8.2.3 圖的抽象數據類型定義 215
8.3 圖的存儲結構 216
8.3.1 鄰接矩陣法 216
8.3.2 鄰接表法 219
8.4 圖的遍歷 222
8.4.1 圖的深度優(yōu)先遍歷 222
8.4.2 圖的廣度優(yōu)先遍歷 225
8.4.3 引例中按中轉次數查詢最優(yōu)航線的解決 228
8.5 最小生成樹 231
8.5.1 最小生成樹和通信網絡建立 231
8.5.2 普里姆算法 231
8.5.3 克魯斯卡爾算法 236
8.5.4 引例中通信網絡建立問題的解決 240
8.6 最短路徑 241
8.6.1 兩類最短路徑問題及應用 241
8.6.2 迪杰斯特拉算法 242
8.6.3 引例中按距離、飛行時間、票價查詢最優(yōu)航線的解決 246
8.6.4 弗洛伊德算法 248
8.6.5 引例中醫(yī)院選址問題的解決 253
8.7 拓撲排序 254
8.7.1 拓撲排序和課程計劃制定 254
8.7.2 拓撲排序算法 255
8.7.3 引例中課程計劃制定問題的解決 258
8.8 關鍵路徑 260
8.8.1 AOE 網和關鍵路徑 260
8.8.2 關鍵路徑算法 261
8.8.3 引例中工程工期計算問題的解決 268
小結 270
習題 270
上機實驗題 273
第9章 查找 274
9.1 引例 274
9.2 查找的基本概念 277
9.3 線性表的查找 278
9.3.1 順序查找 278
9.3.2 折半查找 279
9.4 樹表的查找 282
9.4.1 二叉排序樹 283
9.4.2 平衡二叉樹 292
9.4.3 B-樹 296
9.4.4 B+樹 303
9.5 散列表 304
9.5.1 散列表的基本概念 304
9.5.2 散列函數的構造方法 305
9.5.3 處理沖突的方法 307
9.5.4 散列表的查找及其分析 308
9.6 引例的解決 312
9.6.1 手機選擇中查找相關問題的解決 312
9.6.2 火車票信息查詢中查找相關問題的解決 314
9.6.3 學生課程成績管理中查找相關問題的解決 316
9.6.4 手機通訊錄的解決 320
小結 321
習題 322
上機實驗題 325
第10章 內部排序 326
10.1 引例 326
10.2 排序的基本概念 327
10.3 插入排序 328
10.3.1 直接插入排序 328
10.3.2 折半插入排序 329
10.3.3 希爾排序 330
10.4 交換排序 332
10.4.1 冒泡排序 332
10.4.2 快速排序 334
10.5 選擇排序 337
10.5.1 簡單選擇排序 337
10.5.2 堆排序 338
10.6 歸并排序 343
10.7 基數排序 345
10.7.1 多關鍵字排序 345
10.7.2 基數排序 346
10.8 內部排序方法的比較討論 353
10.9 引例的解決 354
10.9.1 手機選擇中排序相關問題的解決 354
10.9.2 火車票信息查詢中排序相關問題的解決 355
10.9.3 學生課程成績管理中排序相關問題的解決 357
小結 360
習題 360
上機實驗題 363
參考文獻 364
索引 365