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

第1章概論1
1.1什么是數(shù)據(jù)結(jié)構(gòu)1
1.1.1數(shù)據(jù)和數(shù)據(jù)元素1
1.1.2數(shù)據(jù)對(duì)象與數(shù)據(jù)類型2
1.1.3數(shù)據(jù)結(jié)構(gòu)2
1.2為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)5
1.2.1學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的重要性5
1.2.2數(shù)據(jù)結(jié)構(gòu)的應(yīng)用舉例5
1.3算法和算法分析7
1.3.1什么是算法7
1.3.2算法的描述和設(shè)計(jì)7
1.3.3算法分析8
本章小結(jié)10
習(xí)題10
第2章線性表12
2.1線性表的基本概念12
2.1.1線性表的定義12
2.1.2線性表的基本操作13
2.2線性表的順序存儲(chǔ)13
2.2.1順序表13
2.2.2順序表的基本操作14
2.2.3順序存儲(chǔ)方式舉例17
2.3線性表的鏈?zhǔn)酱鎯?chǔ)20
2.3.1單鏈表的基本概念20
2.3.2單鏈表的基本操作22
2.3.3鏈?zhǔn)酱鎯?chǔ)舉例25
2.3.4循環(huán)鏈表28
2.3.5雙向鏈表30
2.3.6雙向循環(huán)鏈表332.3.7靜態(tài)鏈表34
2.4線性表順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的比較35
2.5線性表的應(yīng)用36
2.5.1約瑟夫問題36
2.5.2多項(xiàng)式加法38
2.5.3電文加密40
本章小結(jié)42
習(xí)題43
第3章棧和隊(duì)列45
3.1棧45
3.1.1棧的定義與基本操作45
3.1.2順序棧的存儲(chǔ)結(jié)構(gòu)和操作的實(shí)現(xiàn)47
3.1.3鏈棧的存儲(chǔ)結(jié)構(gòu)和操作的實(shí)現(xiàn)50
3.2棧的應(yīng)用52
3.2.1數(shù)制轉(zhuǎn)換52
3.2.2括號(hào)匹配問題54
3.2.3子程序的調(diào)用55
3.2.4利用一個(gè)順序棧逆置一個(gè)帶頭節(jié)點(diǎn)的單鏈表56
3.2.5后綴表達(dá)式59
3.3隊(duì)列61
3.3.1隊(duì)列的定義與基本操作61
3.3.2鏈隊(duì)列的存儲(chǔ)結(jié)構(gòu)和操作的實(shí)現(xiàn)62
3.3.3順序隊(duì)列的存儲(chǔ)結(jié)構(gòu)和操作的實(shí)現(xiàn)64
3.4隊(duì)列的應(yīng)用68
3.4.1打印楊輝三角形68
3.4.2迷宮問題： 尋找一條從迷宮入口到出口的最短路徑71
3.5遞歸74
3.5.1遞歸的定義與實(shí)現(xiàn)74
3.5.2遞歸消除77
本章小結(jié)81
習(xí)題81
第4章串85
4.1串的定義和基本操作85
4.1.1串的定義85
4.1.2串的基本操作87
4.2串的表示和實(shí)現(xiàn)88
4.2.1串的定長(zhǎng)順序存儲(chǔ)88
4.2.2串的堆存儲(chǔ)結(jié)構(gòu)91
4.2.3串的塊鏈存儲(chǔ)結(jié)構(gòu)93
4.3串的模式匹配算法97
4.3.1基本的模式匹配算法97
4.3.2模式匹配的改進(jìn)算法——KMP算法100
本章小結(jié)102
習(xí)題102
第5章多維數(shù)組和廣義表104
5.1多維數(shù)組104
5.1.1多維數(shù)組的定義104
5.1.2數(shù)組的存儲(chǔ)結(jié)構(gòu)105
5.2矩陣的壓縮存儲(chǔ) 106
5.2.1特殊矩陣106
5.2.2稀疏矩陣108
5.3廣義表 114
本章小結(jié)116
習(xí)題117
第6章樹和二叉樹118
6.1樹的概念與基本操作118
6.1.1樹的定義118
6.1.2樹的一些基本概念119
6.1.3樹的基本操作120
6.2二叉樹120
6.2.1二叉樹的定義和基本操作120
6.2.2二叉樹的性質(zhì)121
6.2.3二叉樹的存儲(chǔ)結(jié)構(gòu)123
6.3二叉樹的遍歷與線索化124
6.3.1二叉樹的遍歷124
6.3.2線索二叉樹127
6.3.3基于遍歷的應(yīng)用與線索二叉樹的應(yīng)用129
6.3.4標(biāo)識(shí)符樹134
6.4樹和森林134
6.4.1樹的存儲(chǔ)結(jié)構(gòu)134
6.4.2樹、森林和二叉樹之間的轉(zhuǎn)換137
6.4.3樹和森林的遍歷140
6.5哈夫曼樹及其應(yīng)用142
6.5.1與哈夫曼樹相關(guān)的基本概念142
6.5.2哈夫曼樹的應(yīng)用144
6.5.3哈夫曼編碼算法的實(shí)現(xiàn)146
*6.6樹的計(jì)數(shù)147
本章小結(jié)150
習(xí)題151
第7章圖154
7.1圖的基本概念154
7.1.1圖的定義154
7.1.2圖的相關(guān)術(shù)語155
7.2圖的存儲(chǔ)結(jié)構(gòu)157
7.2.1鄰接矩陣表示法157
7.2.2鄰接表表示法159
7.3圖的遍歷163
7.3.1深度優(yōu)先搜索法163
7.3.2廣度優(yōu)先搜索法165
7.3.3非連通圖的遍歷167
7.4生成樹與最小生成樹167
7.4.1生成樹的概念167
7.4.2構(gòu)造最小生成樹的普里姆(Prim)算法168
7.4.3構(gòu)造最小生成樹的克魯斯卡爾(Kruskal)算法171
7.5最短路徑173
7.5.1從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑174
7.5.2每一對(duì)頂點(diǎn)之間的最短路徑178
7.6拓?fù)渑判?81
7.7關(guān)鍵路徑184
本章小結(jié)190
習(xí)題190
第8章查找195
8.1查找的基本概念195
8.1.1查找表和查找195
8.1.2查找表的數(shù)據(jù)結(jié)構(gòu)表示196
8.1.3平均查找長(zhǎng)度ASL196
8.2線性表的查找196
8.2.1順序查找 196
8.2.2二分查找198
8.2.3分塊查找201
8.3樹表的查找203
8.3.1二叉排序樹203
*8.3.2平衡二叉樹208
*8.3.3B-樹212
8.4散列表的查找221
8.4.1散列表的概念221
8.4.2散列函數(shù)的構(gòu)造方法222
8.4.3處理沖突的方法 223
8.4.4散列表上的運(yùn)算 227
本章小結(jié)230
習(xí)題230
第9章排序232
9.1排序的基本概念232
9.1.1關(guān)鍵字與排序232
9.1.2排序的穩(wěn)定性233
9.1.3排序方法的分類233
9.1.4排序算法性能評(píng)價(jià)233
9.1.5不同存儲(chǔ)方式的排序過程233
9.2插入排序234
9.2.1直接插入排序234
9.2.2希爾排序237
9.3交換排序239
9.3.1冒泡排序239
9.3.2快速排序(霍爾排序)240
9.4選擇排序244
9.4.1直接選擇排序244
9.4.2堆排序245
9.5歸并排序250
9.6基數(shù)排序253
9.6.1桶排序253
9.6.2多關(guān)鍵字的排序253
9.6.3鏈?zhǔn)交鶖?shù)排序254
9.7內(nèi)部排序算法比較257
9.8外部排序簡(jiǎn)介259
本章小結(jié)259
習(xí)題260
參考文獻(xiàn)263