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

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