前言
第1章 緒論1
1.1 引言1
1.1.1 學(xué)習(xí)目的1
1.1.2 課程內(nèi)容2
1.2 基本概念2
1.2.1 數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)2
1.2.2 數(shù)據(jù)類(lèi)型與抽象數(shù)據(jù)類(lèi)型6
1.3 算法9
1.3.1 算法的概念9
1.3.2 算法描述9
1.3.3 算法分析11
小結(jié)13
習(xí)題114
第2章 線(xiàn)性表17
2.1 線(xiàn)性表及其基本操作17
2.1.1 線(xiàn)性表的基本概念17
2.1.2 抽象數(shù)據(jù)類(lèi)型描述18
2.1.3 線(xiàn)性表的存儲(chǔ)和實(shí)現(xiàn)19
2.2 線(xiàn)性表的順序存儲(chǔ)19
2.2.1 順序表19
2.2.2 順序表的基本操作實(shí)現(xiàn)21
2.3 線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)25
2.3.1 單鏈表25
2.3.2 單鏈表的基本操作實(shí)現(xiàn)27
2.3.3 其他鏈表30
2.4 順序表與鏈表的比較31
2.5 實(shí)驗(yàn)32
2.5.1 數(shù)組奇偶分割32
2.5.2 反轉(zhuǎn)單向鏈表33
2.5.3 鏈表實(shí)現(xiàn)34
小結(jié)38
習(xí)題238
第3章 棧和隊(duì)列41
3.1 棧41
3.1.1 棧的基本概念41
3.1.2 棧的抽象數(shù)據(jù)類(lèi)型描述41
3.1.3 順序棧43
3.1.4 鏈棧46
3.2 隊(duì)列50
3.2.1 隊(duì)列的基本概念50
3.2.2 隊(duì)列的抽象數(shù)據(jù)類(lèi)型描述50
3.2.3 順序隊(duì)列51
3.2.4 鏈隊(duì)列55
3.2.5 優(yōu)先級(jí)隊(duì)列57
3.3 棧和隊(duì)列的比較60
3.4 實(shí)驗(yàn)60
3.4.1 漢諾塔60
3.4.2 吃巧克力62
3.4.3 數(shù)頭頂63
3.4.4 整數(shù)變換64
3.4.5 表達(dá)式求值66
3.4.6 用隊(duì)列表示棧67
3.4.7 用棧表示隊(duì)列69
3.4.8 層次遍歷71
小結(jié)72
習(xí)題373
第4章 串和數(shù)組72
4.1 串76
4.1.1 串的基本概念76
4.1.2 串的抽象數(shù)據(jù)類(lèi)型描述76
4.1.3 順序串78
4.1.4 鏈串82
4.2 串的模式匹配82
4.2.1 Brute Force算法83
4.2.2 KMP算法83
4.3 數(shù)組87
4.3.1 數(shù)組的基本概念87
4.3.2 數(shù)組的特性88
4.3.3 數(shù)組的遍歷88
4.4 特殊矩陣的壓縮存儲(chǔ)89
4.4.1 三角矩陣的壓縮存儲(chǔ)89
4.4.2 對(duì)稱(chēng)矩陣的壓縮存儲(chǔ)90
4.4.3 對(duì)角矩陣的壓縮存儲(chǔ)90
4.4.4 稀疏矩陣的壓縮存儲(chǔ)91
4.5 實(shí)驗(yàn)93
4.5.1 AZY的冒險(xiǎn)島93
4.5.2 最大連續(xù)子數(shù)組94
4.5.3 合并有序數(shù)組95
4.5.4 最長(zhǎng)上升子序列96
小結(jié)97
習(xí)題497
第5章 樹(shù)形結(jié)構(gòu)101
5.1 樹(shù)101
5.1.1 樹(shù)的基本概念101
5.1.2 樹(shù)的術(shù)語(yǔ)102
5.2 二叉樹(shù)103
5.2.1 二叉樹(shù)的基本概念103
5.2.2 二叉樹(shù)的性質(zhì)104
5.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)105
5.2.4 二叉樹(shù)的遍歷106
5.2.5 二叉樹(shù)遍歷算法的應(yīng)用110
5.2.6 二叉樹(shù)的建立112
5.3 哈夫曼樹(shù)及哈夫曼編碼114
5.3.1 哈夫曼樹(shù)的基本概念114
5.3.2 哈夫曼樹(shù)的構(gòu)造115
5.3.3 哈夫曼編碼116
5.3.4 構(gòu)造哈夫曼樹(shù)和哈夫曼編碼的類(lèi)的描述116
5.4 樹(shù)和森林118
5.4.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)118
5.4.2 樹(shù)的遍歷規(guī)則119
5.5 實(shí)驗(yàn)119
小結(jié)121
習(xí)題5121
第6章 圖125
6.1 圖概述125
6.1.1 圖的基本概念125
6.1.2 圖的抽象數(shù)據(jù)類(lèi)型描述127
6.2 圖的存儲(chǔ)結(jié)構(gòu)128
6.2.1 鄰接矩陣128
6.2.2 鄰接表132
6.3 圖的遍歷137
6.4 最小生成樹(shù)141
6.4.1 最小生成樹(shù)的基本概念141
6.4.2 Kruskal算法142
6.4.3 Prim算法142
6.5 最短路徑144
6.5.1 單源最短路徑144
6.5.2 求任意兩個(gè)頂點(diǎn)間的最短路徑146
6.6 拓?fù)渑判蚝完P(guān)鍵路徑148
6.6.1 拓?fù)渑判?48
6.6.2 關(guān)鍵路徑149
6.7 實(shí)驗(yàn)151
小結(jié)152
習(xí)題6153
第7章 排序156
7.1 排序概述156
7.1.1 排序的基本概念156
7.1.2 排序算法的性能評(píng)價(jià)156
7.1.3 待排序的記錄和順序表的類(lèi)描述156
7.2 插入排序157
7.2.1 直接插入排序157
7.2.2 希爾排序159
7.3 交換排序160
7.3.1 冒泡排序160
7.3.2 快速排序161
7.4 選擇排序164
7.4.1 直接選擇排序164
7.4.2 堆排序166
7.5 歸并排序168
7.6 實(shí)驗(yàn)172
7.6.1 插入排序172
7.6.2 鏈表排序173
7.6.3 區(qū)間排序174
小結(jié)175
習(xí)題7176
第8章 查找179
8.1 查找的基本概念179
8.1.1 什么是查找179
8.1.2 查找表179
8.1.3 平均查找長(zhǎng)度180
8.2 靜態(tài)查找表180
8.2.1 順序查找180
8.2.2 二分查找181
8.2.3 分塊查找182
8.3 動(dòng)態(tài)查找表182
8.3.1 二叉排序樹(shù)查找183
8.3.2 平衡二叉樹(shù)187
8.3.3 B-樹(shù)和B+樹(shù)189
8.4 哈希表查找190
8.4.1 哈希表的概念190
8.4.2 哈希函數(shù)190
8.4.3 解決沖突的方法191
8.4.4 哈希表查找性能分析192
8.5 實(shí)驗(yàn)195
8.5.1 尋找山形數(shù)組的頂點(diǎn)195
8.5.2 尋找和為指定值的數(shù)組元素195
8.5.3 尋找數(shù)組元素196
小結(jié)197
習(xí)題8198
附錄200
附錄A 名校數(shù)據(jù)結(jié)構(gòu)程序設(shè)計(jì)考研真題解答（部分）200
附錄B 名詞索引206
參考文獻(xiàn)209