數(shù)據(jù)結構

第一章 緒論 1
1.1 數(shù)據(jù)結構概念 1
1.2 面向?qū)ο蟪绦蛟O計OOP與抽象數(shù)據(jù)類型ADT 3
1.3 算法概念和算法描述語言 5
第二章 算法分析基礎 9
2.1 引論 9
2.2 算法時間復雜性的分析方法 11
2.3 時間與空間分析 15
習題 16
第三章 面向?qū)ο蟪绦蛟O計與C++語言 18
3.1 類和對象 18
3.1.1 類聲明 18
3.1.2 類實現(xiàn) 19
3.1.3 對象聲明 20
3.2 C++語言的基本操作 21
3.2.1 輸入輸出的C++實現(xiàn) 21
3.2.2 友元函數(shù)（friend funtction） 23
3.2.3 參數(shù)傳遞 24
3.2.4 多態(tài)性 25
3.2.5 動態(tài)存儲分配 28
3.3 模板 29
3.3.1 模板函數(shù) 29
3.3.2 模板類 31
3.4 繼承 32
習題 34
第四章 線性表、堆棧、隊列 35
4.1 線性表的定義和基本操作 35
4.2 線性表的存儲結構 36
4.2.1 順序存儲結構 36
4.2.2 鏈接存儲結構----單鏈表 36
4.2.3 循環(huán)鏈表 47
4.2.4 雙向循環(huán)鏈表 49
4.3 堆棧和隊列 53
4.3.1 定義和主要操作 53
4.3.2 順序存儲 56
4.3.3 鏈接存儲 63
4.3.4 應用--算術表達式求值 65
習題 68
第五章 數(shù)組 字符串和集合類 71
5.1 數(shù)組 71
5.1.1 順序存儲的數(shù)組 71
5.1.2 靜態(tài)數(shù)組與動態(tài)數(shù)組 73
5.1.3 稀疏矩陣 77
5.2 字符串 84
5.2.1 定義和主要操作 84
5.2.2 存儲方式 85
5.2.3 模式匹配算法* 86
5.3 整型集合 90
習題 94
第六章 樹 98
6.1 基本概念 98
6.2 二叉樹 99
6.2.1 主要性質(zhì)和定義 99
6.2.2 二叉樹的實現(xiàn) 102
6.2.3 二叉樹的遍歷 108
6.2.4 復制二叉樹 110
6.3 線索二叉樹 111
6.4 樹與森林 119
6.4.1 樹的順序存儲結構 119
6.4.2 樹的鏈接存儲結構 121
6.4.3 森林與二叉樹的轉換 125
6.4.4 樹和森林的遍歷 126
6.5 壓縮與哈夫曼樹 131
習題 135
第七章 圖 137
7.1 概念和定義 137
7.2 圖的存儲結構與類Graph 139
7.2.1 存儲結構 139
7.2.2 Graph類 141
7.3 遍歷函數(shù)的實現(xiàn) 153
7.3.1 深度優(yōu)先遍歷 153
7.3.2 廣度優(yōu)先遍歷 155
7.4 拓撲排序 156
7.5 關鍵路徑 159
7.6 最短路徑問題 163
7.6.1 無權最短路徑問題 163
7.6.2 正權最短路徑問題 165
7.6.3 負權最短路徑問題* 168
7.6.4 每對頂點之間的最短路徑 171
7.7 最小支撐樹 173
7.8 應用 178
7.8.1 可及性與Warshall算法 178
7.8.2 連通分量 180
習題 182
第八章 遞歸 186
8.1 什么是遞歸 186
8.2 基本遞歸過程 188
8.3 遞歸過程的實現(xiàn)：堆棧與遞歸 191
8.4 遞歸到非遞歸的轉換 196
8.5 遞歸的應用 203
8.5.1 應用實例1：算術表達式求值 203
8.5.2 應用實例2：回溯 205
習題 210
第九章 排序 211
9.1 插入排序 212
9.2 交換排序 217
9.2.1 冒泡排序 217
9.2.2 分劃交換排序 222
9.3 選擇排序 231
9.3.1 直接選擇排序 231
9.3.2 堆排序 232
9.4 合并排序 238
9.5 排序下界 242
9.6 分布排序* 243
9.6.1 基數(shù)分布 244
9.6.2 值分布 247
9.7 外排序* 249
9.7.1 外存儲器 249
9.7.2 磁帶排序 250
9.7.3 磁盤排序 260
習題 266
第十章 查找與二叉查找樹 269
10.1 線性表查找 269
10.1.1 順序查找 270
10.1.2 有序表的查找 271
10.2 二叉查找樹 278
10.2.1 定義和基本操作 278
10.2.2 靜態(tài)樹 281
10.2.3 動態(tài)樹 289
10.3 數(shù)字查找樹 320
10.4 雜湊 322
10.4.1 雜湊表的定義和主要操作 322
10.4.2 雜湊函數(shù) 323
10.4.3 沖突調(diào)節(jié) 326
10.5 (a，b)-樹、B樹和B+樹* 334
習題 341
第十一章 內(nèi)存管理 344
11.1 均勻大小記錄的管理和廢料收集方法 344
11.1.1 訪問計數(shù)器法 345
11.1.2 廢料收集 346
11.2 不同大小記錄的查找分配和壓縮分配 350
11.2.1 查找分配 351
11.2.2 壓縮分配 357
11.3 伙伴系統(tǒng) 362
11.4 C++中的動態(tài)內(nèi)存分配* 368
習題 369
第十二章 復雜數(shù)據(jù)結構 371
12.1 優(yōu)先級隊列 371
12.1.1 類聲明 371
12.1.2 優(yōu)先級隊列的應用：長歸并段 372
12.2 不相交集合類 378
12.2.1 等價關系 378
12.2.2 動態(tài)等價 379
12.2.3 快速查找算法 383
12.2.4 快速合并算法 384
12.2.5 C++實現(xiàn) 390
12.2.6 最壞情況下的歸并和路徑壓縮 391
第十三章 文件 393
13.1 文件結構概論 393
13.2 順序文件 396
13.2.1 串行處理文件 396
13.2.2 順序處理文件 399
13.2.3 增補文件 400
13.3 雜湊（散列）文件 402
13.3.1 雜湊文件的設計 402
13.3.2 可擴充的雜湊文件 405
13.4 索引文件 410
13.4.1 動態(tài)索引結構和靜態(tài)索引結構 414
13.4.2 索引順序文件B+ 414
13.4.3 B+索引文件 418
13.5 倒排文件和多重鏈表文件 422
習題 430
第十四章 應用* 432
14.1事件驅(qū)動模擬 432
14.1.1 模擬設計 432
14.1.2 模擬建立 436
14.1.3 運行模擬 437
14.2在線等價類 443
14.2.1 樹形描述 443
14.2.2 操作 444
14.2.3 性能評價 445
14.2.4 性能改進 445
14.3 殘缺棋盤 451
14.4 圖像壓縮 454
參考文獻 461