第1章 緒論1
1.1 數據結構的概念和學習數據結構的必要性1
1.2 數據結構的基本概念2
1.2.1 數據2
1.2.2 數據元素和數據項2
1.2.3 數據結構3
1.3 抽象數據類型及其實現4
1.3.1 數據類型4
1.3.2 抽象數據類型4
1.3.3 C++程序的典型構架5
1.3.4 C++的類和對象6
1.3.5 C++的友元函數7
1.3.6 運算符重載9
1.3.7 C++的參數傳遞12
1.3.8 C++的輸入輸齣14
1.3.9 有關C++的動態存儲分配15
1.3.1 0結構與類17
1.3.1 1C++的模闆17
1.4 算法和算法分析19
1.4.1 算法19
1.4.2 算法分析20
1.5 實用程序軟件包23
1.6 實例研究31
1.6.1 生命遊戲31
1.6.2 計算任意位數的π31
1.7 深入學習導讀38
習題138
上機實驗題139
第2章 綫性錶41
2.1 綫性錶的邏輯結構41
2.2 綫性錶的順序存儲結構42
2.3 綫性錶的鏈式存儲結構51
2.3.1 單鏈錶51
2.3.2 循環鏈錶59
2.3.3 雙嚮鏈錶63
2.3.4 在鏈錶結構中保存當前位置和元素個數66
2.4 實例研究78
2.4.1 一元多項式的錶示78
2.4.2 計算任意大整數的階乘83
2.5 深入學習導讀86
習題287
上機實驗題287
第3章 棧和隊列88
3.1 棧88
3.1.1 棧的基本概念88
3.1.2 順序棧89
3.1.3 鏈式棧94
3.2 隊列100
3.2.1 隊列的基本概念100
3.2.2 鏈隊列102
3.2.3 循環隊列——隊列的順序存儲結構106
3.2.4 隊列應用——顯示二項式(a+b)i的係數111
3.3 優先隊列112
3.4 實例研究116
3.4.1 錶達式求值116
3.4.2 事件驅動模擬119
3.5 深入學習導讀124
習題3125
上機實驗題3125
第4章 串127
4.1 串類型的定義127
4.2 字符串的實現128
4.3 字符串模式匹配算法134
4.3.1 簡單字符串模式匹配算法134
4.3.2 首尾字符串模式匹配算法136
4.3.3 KMP字符串模式匹配算法136
4.4 實例研究141
4.4.1 文本編輯141
4.4.2 查找子序列142
4.5 深入學習導讀143
習題4143
上機實驗題4143
第5章 數組和廣義錶144
5.1 數組144
5.1.1 數組的基本概念144
5.1.2 數組的順序存儲方式144
5.1.3 數組的類定義147
5.2 矩陣150
5.2.1 矩陣的定義和操作150
5.2.2 特殊矩陣152
5.2.3 稀疏矩陣157
5.3 廣義錶167
5.3.1 基本概念167
5.3.2 廣義錶的存儲結構169
5.4 實例研究179
5.4.1 穩定伴侶問題179
5.4.2 m元多項式的錶示179
5.5 深入學習導讀182
習題5183
上機實驗題5183
第6章 樹和二叉樹184
6.1 樹的基本概念184
6.1.1 樹的定義184
6.1.2 基本術語184
6.2 二叉樹186
6.2.1 二叉樹的定義186
6.2.2 二叉樹的性質188
6.2.3 二叉樹的存儲結構190
6.3 二叉樹遍曆199
6.3.1 遍曆的定義199
6.3.2 遍曆算法200
6.3.3 二叉樹遍曆應用舉例206
6.4 綫索二叉樹211
6.4.1 綫索的概念211
6.4.2 綫索二叉樹的實現213
6.5 樹和森林221
6.5.1 樹的存儲錶示221
6.5.2 樹的顯示228
6.5.3 森林的存儲錶示228
6.5.4 樹和森林的遍曆233
6.5.5 樹和森林與二叉樹的轉換235
6.6 哈夫曼樹與哈夫曼編碼238
6.6.1 哈夫曼樹的基本概念238
6.6.2 哈夫曼樹構造算法239
6.6.3 哈夫曼編碼239
6.6.4 哈夫曼樹的實現241
6.7 樹的計數245
6.8 實例研究247
6.8.1 樹與等價關係247
6.8.2 Huffman壓縮算法251
6.9 深入學習導讀256
習題6256
上機實驗題6257
第7章 圖258
7.1 圖的定義和術語258
7.2 圖的存儲錶示262
7.2.1 鄰接矩陣262
7.2.2 鄰接錶267
7.3 圖的遍曆274
7.3.1 深度優先搜索275
7.3.2 廣度優先搜索276
7.4 圖的最小代價生成樹277
7.4.1 Prim算法278
7.4.2 Kruskal算法280
7.5 有嚮無環圖及應用284
7.5.1 拓撲排序284
7.5.2 關鍵路徑287
7.6 最短路徑291
7.6.1 單源點最短路徑問題291
7.6.2 所有頂點之間的最短路徑294
7.7 實例研究296
7.7.1 周遊世界問題——哈密爾頓圈296
7.7.2 一筆畫問題——歐拉問題298
7.8 深入學習導讀299
習題7299
上機實驗題7301
第8章 查找302
8.1 查找的基本概念302
8.2 靜態錶的查找305
8.2.1 順序查找305
8.2.2 有序錶的查找306
8.3 動態查找錶309
8.3.1 二叉排序樹309
8.3.2 二叉平衡樹319
8.3.3 B樹和B+樹343
8.4 散列錶345
8.4.1 散列錶的概念345
8.4.2 構造散列函數的方法345
8.4.3 處理衝突的方法346
8.4.4 散列錶的實現347
8.5 實例研究352
8.5.1 查找3個數組的最小共同元素352
8.5.2 查找最小元素353
8.6 深入學習導讀354
習題8354
上機實驗題8355
第9章 排序356
9.1 概述356
9.2 插入排序357
9.2.1 直接插入排序357
9.2.2 Shell排序358
9.3 交換排序360
9.3.1 起泡排序360
9.3.2 快速排序361
9.4 選擇排序364
9.4.1 簡單選擇排序364
9.4.2 堆排序365
9.5 歸並排序368
9.6 基數排序373
9.6.1 多關鍵排序373
9.6.2 基數排序373
9.7 各種內部排序方法討論376
9.8 外部排序378
9.8.1 外部排序基礎378
9.8.2 外部排序的方法378
9.9 實例研究380
9.9.1 宴會中來賓數目的最大值380
9.9.2 各種排序算法運行時間測試382
9.9.3 用堆實現優先隊列385
9.10 深入學習導讀388
習題9388
上機實驗題9389
第10章 文件390
10.1 主存儲器和輔助存儲器390
10.2 各種常用文件結構390
10.2.1 順序文件390
10.2.2 索引文件391
10.2.3 散列文件392
10.3 實例研究392
10.3.1 VSAM文件392
10.3.2 多關鍵字文件393
10.4 深入學習導讀395
習題10395
上機實驗題10395
第11章 算法設計與分析397
11.1 算法設計397
11.1.1 遞歸算法397
11.1.2 分治算法401
11.1.3 動態規劃算法407
11.1.4 貪心算法422
11.1.5 迴溯算法425
11.1.6 分支限界法430
11.2 算法分析440
11.2.1 遞歸分析440
11.2.2 利用生成函數進行分析443
11.3 可計算性問題445
11.3.1 歸約445
11.3.2 難解問題、N問題、NP問題和NP完全性問題446
11.3.3 不可編程問題447
11.4 實例研究449
11.4.1 圖著色問題449
11.4.2 多邊形遊戲451
11.5 深入學習導讀455
習題11 456
上機實驗題11 456
附錄A 調和級數458
附錄B 泊鬆分布459
附錄C 配套的軟件包460
附錄D 課程設計項目466
附錄E 實驗報告格式471
附錄F 課程設計報告格式472
參考文獻473
· · · · · · (收起)