數(shù)據(jù)結(jié)構(gòu)

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