目錄
第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.4算法和算法分析4
1.4.1算法4
1.4.2算法分析5
1.5實例研究: 生命游戲7
1.6深入學習導讀13
1.7習題13
第2章線性表14
2.1線性表的邏輯結構14
2.2線性表的順序存儲結構16
2.3線性表的鏈式存儲結構23
2.3.1單鏈表23
2.3.2循環(huán)鏈表32
2.3.3雙向鏈表35
2.3.4在鏈表結構中保存當前位置和元素個數39
2.4實例研究: 計算任意大整數的階乘42
2.5深入學習導讀45
2.6習題45
第3章棧和隊列46
3.1棧46
3.1.1棧的基本概念46
3.1.2順序棧47
3.1.3鏈式棧52
3.2隊列59
3.2.1隊列的基本概念59
3.2.2鏈隊列60
3.2.3循環(huán)隊列——隊列的順序存儲結構65
3.2.4隊列應用——顯示二項式(a+b)i的系數70
3.3優(yōu)先隊列71
3.4實例研究: 表達式求值75
3.5深入學習導讀79
3.6習題79
第4章串80
4.1串類型的定義80
4.2字符串的實現81
4.3字符串模式匹配算法86
4.3.1簡單字符串模式匹配算法86
4.3.2首尾字符串模式匹配算法88
4.3.3KMP字符串模式匹配算法88
4.4實例研究: 文本編輯94
4.5深入學習導讀103
4.6習題103
第5章數組和廣義表105
5.1數組105
5.1.1數組的基本概念105
5.1.2數組的順序表105
5.1.3數組的類模板定義107
5.2矩陣111
5.2.1矩陣的定義和操作111
5.2.2特殊矩陣113
5.2.3稀疏矩陣118
5.3廣義表130
5.3.1基本概念130
5.3.2廣義表的存儲結構132
5.4實例研究: 穩(wěn)定伴侶問題142
5.5深入學習導讀145
5.6習題146
第6章樹和二叉樹147
6.1樹的基本概念147
6.1.1樹的定義147
6.1.2基本術語147
6.2二叉樹149
6.2.1二叉樹的定義149
6.2.2二叉樹的性質151
6.2.3二叉樹的存儲結構153
6.3二叉樹遍歷162
6.3.1遍歷的定義162
6.3.2遍歷算法163
6.3.3二叉樹遍歷應用舉例169
6.4線索二叉樹174
6.4.1線索的概念174
6.4.2線索二叉樹的實現176
6.5樹和森林的實現184
6.5.1樹的存儲表示184
6.5.2樹的顯示191
6.5.3森林的存儲表示192
6.5.4樹和森林的遍歷197
6.5.5將樹和森林與二叉樹相互轉換199
6.6哈夫曼樹與哈夫曼編碼202
6.6.1哈夫曼樹的基本概念202
6.6.2哈夫曼樹構造算法203
6.6.3哈夫曼編碼204
6.6.4哈夫曼樹的實現205
6.7樹的計數209
6.8樹在等價關系上的應用212
6.9實例研究: 哈夫曼壓縮算法216
6.10深入學習導讀221
6.11習題222
第7章圖223
7.1圖的定義和術語223
7.2圖的存儲表示227
7.2.1鄰接矩陣227
7.2.2鄰接表232
7.3圖的遍歷240
7.3.1深度優(yōu)先搜索240
7.3.2廣度優(yōu)先搜索242
7.4連通無向網的最小代價生成樹244
7.4.1Prim算法244
7.4.2Kruskal算法247
7.5有向無環(huán)圖及應用250
7.5.1拓撲排序251
7.5.2關鍵路徑253
7.6最短路徑257
7.6.1單源點最短路徑問題258
7.6.2所有頂點之間的最短路徑261
7.7實例研究: 周游世界問題——哈密頓圈263
7.8深入學習導讀265
7.9習題265
第8章查找267
8.1查找的基本概念267
8.2靜態(tài)表的查找267
8.2.1順序查找267
8.2.2有序表的查找268
8.3動態(tài)查找表272
8.3.1二叉排序樹272
8.3.2平衡二叉樹282
8.3.3B樹和B+樹306
8.4哈希表309
8.4.1哈希表的概念309
8.4.2構造哈希函數的方法309
8.4.3處理沖突的方法309
8.4.4哈希表的實現311
8.5實例研究: 查找3個數組的最小共同元素316
8.6深入學習導讀317
8.7習題317
第9章排序319
9.1概述319
9.2插入排序320
9.2.1直接插入排序320
9.2.2Shell排序321
9.3交換排序323
9.3.1冒泡排序323
9.3.2快速排序324
9.4選擇排序327
9.4.1簡單選擇排序327
9.4.2堆排序328
9.5歸并排序332
9.6基數排序336
9.6.1多關鍵字排序336
9.6.2基數排序337
9.7各種內部排序方法討論339
9.8外部排序341
9.8.1外部排序基礎341
9.8.2外部排序的方法342
9.9實例研究: 用堆實現優(yōu)先隊列343
9.10深入學習導讀346
9.11習題346
第10章文件348
10.1主存儲器和輔助存儲器348
10.2各種常用文件結構348
10.2.1順序文件348
10.2.2索引文件349
10.2.3哈希文件350
10.3實例研究350
10.3.1VSAM文件350
10.3.2多關鍵字文件351
10.4深入學習導讀353
10.5習題353
第11章算法設計與分析354
11.1算法設計354
11.1.1遞歸算法354
11.1.2分治算法356
11.1.3動態(tài)規(guī)劃算法357
11.1.4貪婪算法358
11.1.5回溯法359
11.1.6分支限界法361
11.2算法分析363
11.2.1遞歸分析363
11.2.2利用生成函數進行分析364
11.3實例研究: 圖著色問題366
11.4深入學習導讀368
11.5習題368
參考文獻370
附錄A調和級數371
附錄B泊松分布372
附錄C配套軟件包文件索引373
附錄D主流C++開發(fā)環(huán)境的使用方法379
鄂公網安備 42010302001612號 