數(shù)據(jù)結(jié)構(gòu)教程（第二版）

第1章?緒論
1.1?什么是數(shù)據(jù)結(jié)構(gòu)1
*1.2?數(shù)據(jù)結(jié)構(gòu)的發(fā)展簡史及其在計算機科學中的地位5
1.3?算法5
1.3.1?算法及其性質(zhì)5
1.3.2?基本算法7
1.3.3?算法的描述8
1.4?算法分析12
1.4.1?時間復雜度12
1.4.2?空間復雜度15
1.4.3?其他方面16
習題16
第2章?線性表
2.1?線性表的定義及其基本操作21
2.1.1?線性表的定義21
2.1.2?線性表的基本操作22
2.2?線性表的順序存儲結(jié)構(gòu)23
2.2.1?順序存儲結(jié)構(gòu)的構(gòu)造23
2.2.2?幾種常見操作的實現(xiàn)25
2.2.3?順序存儲結(jié)構(gòu)小結(jié)30
2.3?線性鏈表及其操作31
2.3.1?線性鏈表的構(gòu)造31
2.3.2?線性鏈表的基本算法34
2.4?循環(huán)鏈表及其操作50
2.5?雙向鏈表及其操作53
2.5.1?雙向鏈表的構(gòu)造53
2.5.2?雙向鏈表的插入與刪除算法54
*2.6?鏈表的應用舉例57
2.6.1?鏈式存儲結(jié)構(gòu)下的一元多項式相加57
2.6.2?打印文本文件的最后n行60
習題63
第3章?數(shù)組
3.1?數(shù)組的概念69
3.2?數(shù)組的存儲結(jié)構(gòu)69
3.3?矩陣的壓縮存儲71
3.3.1?對稱矩陣的壓縮存儲72
3.3.2?對角矩陣的壓縮存儲73
3.4?稀疏矩陣的三元組表表示74
3.4.1?稀疏矩陣的三元組表存儲方法74
*3.4.2?稀疏矩陣的轉(zhuǎn)置算法75
*3.4.3?稀疏矩陣的相加算法78
*3.4.4?稀疏矩陣的相乘算法79
*3.5?稀疏矩陣的鏈表表示81
3.5.1?線性鏈表存儲方法82
3.5.2?帶行指針向量的鏈表存儲方法83
3.5.3?十字鏈表存儲方法83
3.6?數(shù)組的應用舉例88
3.6.1?一元多項式的數(shù)組表示88
3.6.2?n階魔方89
習題91
第4章?堆棧和隊列
4.1?堆棧的概念及其操作95
4.1.1?堆棧的定義95
4.1.2?堆棧的基本操作96
4.2?堆棧的順序存儲結(jié)構(gòu)96
4.2.1?順序堆棧的構(gòu)造97
4.2.2?順序堆棧的基本算法97
*4.2.3?多個堆棧共享連續(xù)空間99
4.3?堆棧的鏈式存儲結(jié)構(gòu)102
4.3.1?鏈接堆棧的構(gòu)造103
4.3.2?鏈接堆棧的基本算法103
4.4?堆棧的應用舉例106
4.4.1?符號匹配檢查106
4.4.2?數(shù)制轉(zhuǎn)換107
4.4.3?堆棧在遞歸中的應用108
4.4.4?表達式的計算113
4.4.5?又一個趣味游戲——迷宮117
4.5?隊列的概念及其操作120
4.5.1?隊列的定義120
4.5.2?隊列的基本操作121
4.6?隊列的順序存儲結(jié)構(gòu)121
4.6.1?順序隊列的構(gòu)造121
4.6.2?順序隊列的基本算法123
4.6.3?循環(huán)隊列124
4.7?隊列的鏈式存儲結(jié)構(gòu)127
4.7.1?鏈接隊列的構(gòu)造127
4.7.2?鏈接隊列的基本算法128
習題131
第5章?廣義表
5.1?廣義表的基本概念136
5.2?廣義表的存儲結(jié)構(gòu)137
*5.3?多元多項式的表示141
習題143
第6章?串
6.1?串的基本概念145
6.1.1?串的定義145
6.1.2?串的幾個概念146
6.2?串的基本操作146
6.3?串的存儲結(jié)構(gòu)148
6.3.1?串的順序存儲結(jié)構(gòu)149
6.3.2?串的鏈式存儲結(jié)構(gòu)150
6.4?串的幾個操作151
習題157
第7章?樹與二叉樹
7.1?樹的基本概念158
7.1.1?樹的定義158
7.1.2?樹的邏輯表示方法160
7.1.3?基本術(shù)語161
7.1.4?樹的性質(zhì)163
7.1.5?樹的基本操作164
*7.2?樹的存儲結(jié)構(gòu)164
7.2.1?多重鏈表表示法165
7.2.2?三重鏈表表示法166
7.3?二叉樹167
7.3.1?二叉樹的定義167
7.3.2?二叉樹的基本操作168
7.3.3?兩種特殊形態(tài)的二叉樹169
7.3.4?二叉樹的性質(zhì)169
*7.3.5?二叉樹與樹、樹林之間的轉(zhuǎn)換171
7.4?二叉樹的存儲結(jié)構(gòu)174
7.4.1?二叉樹的順序存儲結(jié)構(gòu)174
7.4.2?二叉樹的鏈式存儲結(jié)構(gòu)176
7.5?二叉樹與樹的遍歷180
7.5.1?二叉樹的遍歷181
7.5.2?由遍歷序列恢復二叉樹189
7.5.3?二叉樹的等價性190
*7.5.4?樹和樹林的遍歷191
7.5.5?基于二叉樹遍歷操作的算法舉例192
7.6?線索二叉樹199
7.6.1?線索二叉樹的構(gòu)造200
7.6.2?線索二叉樹的利用201
*7.6.3?二叉樹的線索化204
*7.6.4?線索二叉樹的更新205
7.7?二叉排序樹206
7.7.1?二叉排序樹的定義206
7.7.2?二叉排序樹的建立206
*7.7.3?在二叉排序樹中刪除結(jié)點209
7.7.4?二叉排序樹的查找212
*7.8?平衡二叉樹215
7.9?哈夫曼樹及其應用222
7.9.1?哈夫曼樹的概念222
*7.9.2?哈夫曼編碼223
習題227
第8章?圖
8.1?圖的基本概念233
8.1.1?圖的定義和基本術(shù)語233
8.1.2?圖的基本操作237
8.2?圖的存儲方法238
8.2.1?鄰接矩陣存儲方法238
8.2.2?鄰接表存儲方法240
*8.2.3?有向圖的十字鏈表存儲方法244
*8.2.4?無向圖的多重鄰接表存儲方法245
8.3?圖的遍歷246
8.3.1?深度優(yōu)先搜索247
8.3.2?廣度優(yōu)先搜索