數(shù)據(jù)結(jié)構(gòu)――C++語(yǔ)言描述

目 錄
第1章 概論\t1
1．1 問(wèn)題求解方法\t1
1．1．1 問(wèn)題和問(wèn)題求解\t1
1．1．2 問(wèn)題求解過(guò)程\t1
1．1．3 計(jì)算機(jī)求解問(wèn)題的過(guò)程\t2
1．2 什么是數(shù)據(jù)結(jié)構(gòu)\t2
1．2．1 算法與數(shù)據(jù)結(jié)構(gòu)\t2
1．2．2 數(shù)據(jù)結(jié)構(gòu)基本概念\t3
1．2．3 數(shù)據(jù)的邏輯結(jié)構(gòu)\t4
1．2．4 數(shù)據(jù)的存儲(chǔ)表示\t5
1．2．5 數(shù)據(jù)結(jié)構(gòu)的操作\t6
1．3 數(shù)據(jù)抽象和抽象數(shù)據(jù)類(lèi)型\t7
1．3．1 數(shù)據(jù)抽象和過(guò)程抽象\t7
1．3．2 模塊化、封裝與信息隱蔽\t7
1．3．3 數(shù)據(jù)類(lèi)型和抽象數(shù)據(jù)類(lèi)型\t8
1．4 面向?qū)ο蠓椒╘t10
1．4．1 面向?qū)ο蠓椒ǖ挠蓙?lái)\t10
1．4．2 面向?qū)ο蠓椒ǖ幕舅枷隲t10
1．4．3 面向?qū)ο蠓椒ǖ幕疽豛t11
1．4．4 抽象數(shù)據(jù)類(lèi)型和面向?qū)ο蠓椒╘t12
1．4．5 C++語(yǔ)言對(duì)抽象數(shù)據(jù)類(lèi)型的支持\t13
1．5 描述數(shù)據(jù)結(jié)構(gòu)和算法\t13
1．5．1 數(shù)據(jù)結(jié)構(gòu)的規(guī)范\t13
1．5．2 實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)\t14
1．6 算法分析的基本方法\t15
1．6．1 算法及其性能標(biāo)準(zhǔn)\t15
1．6．2 算法的時(shí)間復(fù)雜度\t16
1．6．3 漸近時(shí)間復(fù)雜度\t18
1．6．4 最好、最壞和平均情況時(shí)間復(fù)雜度\t19
1．6．5 算法按時(shí)間復(fù)雜度分類(lèi)\t19
1．6．6 算法的空間復(fù)雜度\t19
本章小結(jié)\t20
習(xí)題1\t20
第2章 數(shù)組和鏈表\t22
2．1 兩種基本的存儲(chǔ)表示方式\t22
2．2 結(jié)構(gòu)和類(lèi)\t22
2．2．1 結(jié)構(gòu)\t22
2．2．2 結(jié)構(gòu)表示元素\t23
2．3 指針和動(dòng)態(tài)存儲(chǔ)分配\t24
2．3．1 指針\t24
2．3．2 動(dòng)態(tài)存儲(chǔ)分配\t25
2．3．3 靜態(tài)變量和動(dòng)態(tài)變量\t26
2．4 數(shù)組\t26
2．4．1 一維數(shù)組\t26
2．4．2 二維數(shù)組\t27
2．4．3 多維數(shù)組\t28
2．4．4 數(shù)組和指針\t28
2．4．5 固定長(zhǎng)度數(shù)組和可變長(zhǎng)度數(shù)組\t28
2．5 鏈表\t29
2．5．1 指向結(jié)構(gòu)的指針\t30
2．5．2 單鏈表\t30
2．5．3 帶表頭結(jié)點(diǎn)的單鏈表\t33
2．5．4 單循環(huán)鏈表\t33
2．5．5 雙向鏈表\t33
2．6 采用模擬指針的鏈表\t35
2．6．1 結(jié)點(diǎn)結(jié)構(gòu)\t35
2．6．2 可用空間表\t35
2．7 異常處理\t37
本章小結(jié)\t38
習(xí)題2\t38
第3章 棧和隊(duì)列\(zhòng)t40
3．1 棧\t40
3．1．1 棧ADT\t40
3．1．2 棧的順序表示\t41
3．1．3 棧的鏈接表示\t44
3．2 隊(duì)列\(zhòng)t47
3．2．1 隊(duì)列ADT\t47
3．2．2 隊(duì)列的順序表示\t48
3．2．3 隊(duì)列的鏈接表示\t51
3．3 表達(dá)式計(jì)算\t51
3．3．1 表達(dá)式\t51
3．3．2 中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式\t52
3．3．3 計(jì)算后綴表達(dá)式的值\t55
3．4 演示與測(cè)試\t58
本章小結(jié)\t61
習(xí)題3\t61
第4章 遞歸\t63
4．1 遞歸和遞歸算法\t63
4．1．1 遞歸的概念\t63
4．1．2 遞歸算法示例\t64
4．2 歸納證明\t66
4．3 遞推關(guān)系\t67
4．4 實(shí)現(xiàn)遞歸\t67
4．4．1 函數(shù)調(diào)用和系統(tǒng)棧\t68
4．4．2 遞歸函數(shù)的性能\t69
4．4．3 尾遞歸\t69
4．4．4 消去遞歸\t70
本章小結(jié)\t70
習(xí)題4\t70
第5章 線(xiàn)性表和串\t72
5．1 線(xiàn)性表\t72
5．1．1 線(xiàn)性表ADT\t72
5．1．2 線(xiàn)性表的順序表示\t73
5．1．3 線(xiàn)性表的鏈接表示\t76
5．1．4 兩種存儲(chǔ)表示的比較\t79
5．2 一元多項(xiàng)式算術(shù)運(yùn)算\t80
5．2．1 多項(xiàng)式ADT\t80
5．2．2 多項(xiàng)式的鏈接表示\t80
5．2．3 項(xiàng)結(jié)點(diǎn)類(lèi)\t81
5．2．4 多項(xiàng)式類(lèi)\t82
5．2．5 多項(xiàng)式的輸入和輸出\t83
5．2．6 多項(xiàng)式相加\t84
5．2．7 多項(xiàng)式相乘\t85
5．2．8 重載運(yùn)算符\t86
5．3 串\t86
5．3．1 串ADT\t86
5．3．2 串的存儲(chǔ)表示\t87
5．3．3 串運(yùn)算的實(shí)現(xiàn)\t88
5．3．4 簡(jiǎn)單模式匹配算法\t89
5．3．5 KMP算法\t91
本章小結(jié)\t95
習(xí)題5\t95
第6章 數(shù)組和廣義表\t97
6．1 數(shù)組作為抽象數(shù)據(jù)類(lèi)型\t97
6．1．1 數(shù)組ADT\t97
6．1．2 一維數(shù)組的C++類(lèi)\t98
6．2 矩陣\t99
6．2．1 矩陣的概念\t99
6．2．2 矩陣ADT\t99
6．2．3 矩陣的二維數(shù)組表示\t100
6．3 特殊矩陣\t101
6．3．1 對(duì)稱(chēng)矩陣\t101
6．3．2 帶狀矩陣\t102
6．4 稀疏矩陣\t103
6．4．1 稀疏矩陣的三元組表\t103
6．4．2 稀疏矩陣轉(zhuǎn)置\t105
6．4．3 稀疏矩陣相加\t107
6．4．4 稀疏矩陣相乘\t108
6．5 稀疏矩陣的正交鏈表\t109
6．5．1 正交鏈表結(jié)構(gòu)\t109
6．5．2 正交鏈表結(jié)點(diǎn)類(lèi)\t110
6．5．3 正交鏈表類(lèi)\t111
6．5．4 建立正交鏈表\t111
6．5．5 輸出正交鏈表\t113
6．6 廣義表\t113
6．6．1 廣義表的概念\t113
6．6．2 廣義表ADT\t114
6．6．3 廣義表的存儲(chǔ)表示\t115
6．6．4 廣義表算法\t116
本章小結(jié)\t116
習(xí)題6\t117
第7章 樹(shù)\t118
7．1 樹(shù)的基本概念\t118
7．1．1 樹(shù)的定義\t118
7．1．2 基本術(shù)語(yǔ)\t119
7．2 二叉樹(shù)\t120
7．2．1 二叉樹(shù)的定義\t120
7．2．2 二叉樹(shù)的性質(zhì)\t121
7．2．3 二叉樹(shù)ADT\t122
7．2．4 二叉樹(shù)的存儲(chǔ)表示\t123
7．2．5 二叉樹(shù)類(lèi)\t123
7．2．6 實(shí)現(xiàn)二叉樹(shù)的基本操作\t124
7．3 二叉樹(shù)的遍歷\t126
7．3．1 二叉樹(shù)遍歷算法\t126
7．3．2 二叉樹(shù)遍歷的遞歸算法\t128
7．3．3 二叉樹(shù)遍歷的應(yīng)用實(shí)例\t129
7．4 二叉樹(shù)遍歷的非遞歸算法\t131
7．4．1 遍歷器類(lèi)\t131
7．4．2 中序遍歷器類(lèi)\t132
7．4．3 后序遍歷器類(lèi)\t134
7．5 二叉線(xiàn)索樹(shù)\t136
7．5．1 二叉線(xiàn)索樹(shù)的定義\t136
7．5．2 構(gòu)造中序線(xiàn)索樹(shù)\t137
7．5．3 遍歷中序線(xiàn)索樹(shù)\t138
7．6 樹(shù)和森林\t139
7．6．1 森林與二叉樹(shù)的轉(zhuǎn)換\t139
7．6．2 樹(shù)和森林的存儲(chǔ)表示\t141
7．6．3 樹(shù)和森林的遍歷\t142
本章小結(jié)\t143
習(xí)題7\t143
第8章 樹(shù)的應(yīng)用\t145
8．1 堆\t145
8．1．1 堆的定義\t145
8．1．2 堆的順序表示\t145
8．1．3 向下調(diào)整和建堆操作\t145
8．2 優(yōu)先權(quán)隊(duì)列\(zhòng)t147
8．2．1 優(yōu)先權(quán)隊(duì)列ADT\t147
8．2．2 優(yōu)先權(quán)隊(duì)列類(lèi)\t148
8．2．3 實(shí)現(xiàn)優(yōu)先權(quán)隊(duì)列\(zhòng)t148
8．3 哈夫曼樹(shù)和哈夫曼編碼\t150
8．3．1 樹(shù)的路徑長(zhǎng)度\t151
8．3．2 哈夫曼算法\t152
8．3．3 哈夫曼樹(shù)類(lèi)\t152
8．3．4 構(gòu)造哈夫曼樹(shù)\t153
8．3．5 哈夫曼編碼\t155
8．3．6 哈夫曼編碼算法\t156
8．4 并查集和等價(jià)關(guān)系\t156
8．4．1 并查集ADT\t157
8．4．2 并查集的存儲(chǔ)表示\t157
8．4．3 并查集類(lèi)\t158
8．4．4 Union和Find函數(shù)\t159
8．4．5 改進(jìn)的Union和Find函數(shù)\t159
8．4．6 按等價(jià)關(guān)系分組\t160
本章小結(jié)\t161
習(xí)題8\t161
第9章 字典和查找\t162
9．1 字典及其表示\t162
9．1．1 字典\t162
9．1．2 字典查找\t163
9．1．3 字典ADT\t163
9．1．4 字典的存儲(chǔ)表示\t164
9．2 順序查找\t165
9．2．1 無(wú)序表的順序查找\t165
9．2．2 有序表的順序查找\t165
9．2．3 平均查找長(zhǎng)度\t166
9．2．4 自組織表\t166
9．3 二分查找\t167
9．3．1 二分查找算法\t167
9．3．2 對(duì)半查找算法\t168
9．3．3 二叉判定樹(shù)\t169
9．3．4 斐波那契查找算法\t170
9．3．5 插值查找\t172
9．4 分塊查找\t172
9．5 查找算法的時(shí)間復(fù)雜度下界\t173
本章小結(jié)\t174
習(xí)題9\t174
第10章 二叉查找樹(shù)\t175
10．1 二叉查找樹(shù)表示字典\t175
10．1．1 二叉查找樹(shù)的定義\t175
10．1．2 二叉查找樹(shù)的查找操作\t176
10．1．3 二叉查找樹(shù)的插入操作\t177
10．1．4 二叉查找樹(shù)的刪除操作\t178
10．1．5 二叉查找樹(shù)的高度\t179
10．2 二叉平衡樹(shù)\t179
10．2．1 二叉平衡樹(shù)的定義\t179
10．2．2 二叉平衡樹(shù)類(lèi)\t180
10．2．3 二叉平衡樹(shù)的平衡旋轉(zhuǎn)\t181
10．2．4 二叉平衡樹(shù)的插入操作\t185
10．2．5 二叉平衡樹(shù)的刪除操作\t187
10．2．6 二叉平衡樹(shù)的高度\t189
10．3 伸展樹(shù)\t190
10．3．1 自調(diào)節(jié)樹(shù)和伸展樹(shù)\t190
10．3．2 伸展樹(shù)的伸展操作\t191
10．3．3 伸展樹(shù)類(lèi)\t193
10．3．4 旋轉(zhuǎn)的實(shí)現(xiàn)\t193
10．3．5 伸展樹(shù)的插入操作\t194
10．3．6 分?jǐn)倳r(shí)間分析\t195
10．4 紅黑樹(shù)\t195
10．4．1 紅黑樹(shù)的定義\t195
10．4．2 紅黑樹(shù)的查找操作\t196
10．4．3 紅黑樹(shù)的插入操作\t196
10．4．4 紅黑樹(shù)的刪除操作\t198
10．4．5 紅黑樹(shù)的高度\t199
本章小結(jié)\t199
習(xí)題10\t199
第11章 多叉查找樹(shù)\t201
11．1 m叉查找樹(shù)\t201
11．2 B?樹(shù)\t202
11．2．1 B?樹(shù)的定義\t203
11．2．2 B?樹(shù)的高度\t203
11．2．3 B?樹(shù)的查找操作\t203
11．2．4 B?樹(shù)的插入操作\t204
11．2．5 B?樹(shù)的刪除操作\t206
11．2．6 B?樹(shù)類(lèi)\t207
11．2．7 B?樹(shù)的查找操作\t208
11．2．8 B?樹(shù)的插入函數(shù)\t209
11．2．9 B?樹(shù)的刪除函數(shù)\t210
11．3 鍵樹(shù)\t212
11．3．1 鍵樹(shù)的定義\t212
11．3．2 雙鏈樹(shù)\t213
11．3．3 Trie樹(shù)\t214
11．3．4 Trie樹(shù)的查找操作\t216
11．3．5 Trie樹(shù)的插入操作\t216
11．3．6 Trie樹(shù)的刪除操作\t217
11．3．7 Trie樹(shù)性能分析\t217
本章小結(jié)\t218
習(xí)題11\t218
第12章 跳表和散列表\t219
12．1 跳表\t219
12．1．1 跳表的概念\t219
12．1．2 跳表類(lèi)\t221
12．1．3 跳表的查找函數(shù)\t222
12．1．4 跳表的插入函數(shù)\t223
12．1．5 跳表的刪除函數(shù)\t224
12．1．6 性能分析\t224
12．2 散列表\t224
12．2．1 散列技術(shù)\t225
12．2．2 散列函數(shù)\t226
12．2．3 拉鏈法\t227
12．2．4 開(kāi)地址法\t228
12．2．5 線(xiàn)性探查法\t228
12．2．6 其他開(kāi)地址法\t231
12．2．7 性能分析\t233
本章小結(jié)\t233
習(xí)題12\t234
第13章 圖\t235
13．1 圖的基本概念\t235
13．1．1 圖的定義與術(shù)語(yǔ)\t235
13．1．2 圖的抽象數(shù)據(jù)類(lèi)型\t237
13．2 圖的存儲(chǔ)結(jié)構(gòu)\t238
13．2．1 圖的矩陣表示\t238
13．2．2 圖的鄰接矩陣實(shí)現(xiàn)\t239
13．2．3 圖的鄰接表表示\t241
13．2．4 圖的鄰接表實(shí)現(xiàn)\t242
13．2．5 有向圖的正交鏈表表示\t245
13．2．6 無(wú)向圖的鄰接多重表表示\t245
13．3 圖的遍歷\t246
13．3．1 擴(kuò)充的圖類(lèi)\t246
13．3．2 深度優(yōu)先遍歷\t247
13．3．3 廣度優(yōu)先遍歷\t248
13．3．4 基本遍歷方法\t249
13．4 拓?fù)渑判騖t250
13．4．1 AOV網(wǎng)絡(luò)\t250
13．4．2 拓?fù)渑判蛩惴╘t252
13．4．3 拓?fù)渑判蛩惴▽?shí)現(xiàn)\t252
13．5 關(guān)鍵路徑\t254
13．5．1 AOE網(wǎng)\t254
13．5．2 關(guān)鍵路徑算法\t255
13．5．3 關(guān)鍵路徑算法實(shí)現(xiàn)\t257
13．6 最小代價(jià)生成樹(shù)\t258
13．6．1 基本概念\t258
13．6．2 普里姆算法\t258
13．6．3 克魯斯卡爾算法\t260
13．6．4 算法正確性\t262
13．7 單源最短路徑\t262
13．7．1 最短路徑問(wèn)題\t262
13．7．2 迪杰斯特拉算法\t263
13．7．3 數(shù)據(jù)結(jié)構(gòu)選擇\t263
13．7．4 迪杰斯特拉算法實(shí)現(xiàn)\t264
13．8 所有頂點(diǎn)之間的最短路徑\t266
13．8．1 弗洛伊德算法\t266
13．8．2 弗洛伊德算法實(shí)現(xiàn)\t267
本章小結(jié)\t268
習(xí)題13\t268
第14章 內(nèi)排序\t270
14．1 基本概念\t270
14．2 插入排序\t271
14．2．1 直接插入排序\t271
14．2．2 順序表的直接插入排序\t272
14．2．3 單鏈表的直接插入排序\t273
14．2．4 希爾排序\t274
14．2．5 對(duì)半插入排序\t276
14．3 選擇排序\t276
14．3．1 簡(jiǎn)單選擇排序\t276
14．3．2 堆排序\t277
14．4 交換排序\t278
14．4．1 冒泡排序\t278
14．4．2 快速排序\t280
14．4．3 快速排序性能分析\t281
14．5 兩路合并排序\t283
14．5．1 合并兩個(gè)有序序列\(zhòng)t284
14．5．2 兩路合并排序迭代算法\t284
14．5．3 兩路合并排序遞歸算法\t285
14．5．4 單鏈表兩路合并排序\t285
14．6 排序算法的時(shí)間復(fù)雜度下界\t287
14．7 基數(shù)排序\t288
14．7．1 分配排序\t289
14．7．2 基數(shù)排序算法\t289
14．7．3 基數(shù)排序?qū)崿F(xiàn)\t290
本章小結(jié)\t292
習(xí)題14\t292
第15章 文件和外排序\t294
15．1 輔助存儲(chǔ)器簡(jiǎn)介\t294
15．1．1 主存儲(chǔ)器和輔助存儲(chǔ)器\t294
15．1．2 磁盤(pán)存儲(chǔ)器\t294
15．2 文件\t295
15．2．1 文件的基本概念\t295
15．2．2 文件的組織方式\t296
15．3 文件的索引結(jié)構(gòu)\t298
15．3．1 靜態(tài)索引結(jié)構(gòu)\t298
15．3．2 動(dòng)態(tài)索引結(jié)構(gòu)\t299
15．4 外排序\t300
15．4．1 外排序的基本過(guò)程\t300
15．4．2 初始游程的生成\t300
15．4．3 多路合并\t302
15．4．4 最佳合并樹(shù)\t304
本章小結(jié)\t304
習(xí)題15\t305
第16章 實(shí)習(xí)指導(dǎo)和實(shí)習(xí)題\t306
16．1 實(shí)習(xí)目的、要求和步驟\t306
16．2 面向?qū)ο蟊硎痉╘t307
16．3 實(shí)習(xí)報(bào)告和范例\t308
16．3．1 實(shí)習(xí)報(bào)告\t308
16．3．2 實(shí)習(xí)題范例\t309
16．3．3 實(shí)習(xí)報(bào)告范例\t309
16．4 實(shí)習(xí)題\t312
實(shí)習(xí)1 C++語(yǔ)言的類(lèi)及模板的使用\t312
實(shí)習(xí)2 數(shù)組和鏈表操作\t313
實(shí)習(xí)3 棧、隊(duì)列及表達(dá)式計(jì)算\t313
實(shí)習(xí)4 線(xiàn)性表的操作及應(yīng)用\t314
實(shí)習(xí)5 一元多項(xiàng)式的相加和相乘\t314
實(shí)習(xí)6 對(duì)稱(chēng)矩陣和稀疏矩陣的 壓縮存儲(chǔ)\t315
實(shí)習(xí)7 字符串操作和文本 處理\t315
實(shí)習(xí)8 二叉樹(shù)操作和哈夫曼編碼\t315
實(shí)習(xí)9 有序表查找\t316
實(shí)習(xí)10 B?樹(shù)檢索\t317
實(shí)習(xí)11 散列表查找\t317
實(shí)習(xí)12 圖的操作及應(yīng)用\t318
實(shí)習(xí)13 內(nèi)排序算法及其性能比較\t318
實(shí)習(xí)14 置換選擇和K路合并的 外排序算法\t318
附錄A 程序測(cè)試和調(diào)試\t319
A．1 面向?qū)ο蟪绦驕y(cè)試\t319
A．2 程序測(cè)試步驟\t319
A．3 測(cè)試方法\t320
A．4 程序調(diào)試\t321
附錄B 2019年計(jì)算機(jī)考研大綱與教材內(nèi)容對(duì)照\(chéng)t323
B．1 2019年計(jì)算機(jī)考研大綱\t323
B．2 教材內(nèi)容對(duì)2019年計(jì)算機(jī)考研大綱的適應(yīng)性\t324
參考文獻(xiàn)\t326