數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)輔導(dǎo)與實(shí)驗(yàn)指導(dǎo)

第一篇學(xué)習(xí)輔導(dǎo)
第1章緒論1
1.1本章導(dǎo)學(xué)1
1.2重點(diǎn)難點(diǎn)釋疑5
1.2.1信息、數(shù)據(jù)與結(jié)構(gòu)5
1.2.2數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型5
1.2.3邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)6
1.2.4如何選擇或設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)7
1.2.5問題、算法與程序7
1.2.6算法設(shè)計(jì)的一般原則8
1.2.7算法時(shí)間復(fù)雜度的分析方法9
1.3習(xí)題解析10
1.3.1課后習(xí)題講解10
1.3.2學(xué)習(xí)自測(cè)及答案15
第2章線性表17
2.1本章導(dǎo)學(xué)17
2.2重點(diǎn)難點(diǎn)釋疑19
2.2.1存儲(chǔ)結(jié)構(gòu)與存取結(jié)構(gòu)19
2.2.2頭指針、尾標(biāo)志、開始結(jié)點(diǎn)與頭結(jié)點(diǎn)19
2.2.3帶頭結(jié)點(diǎn)的單鏈表與不帶頭結(jié)點(diǎn)的單鏈表
的區(qū)別20
2.2.4單鏈表算法的設(shè)計(jì)技巧22
2.2.5有序單鏈表的算法設(shè)計(jì)技巧25
2.2.6循環(huán)鏈表的算法設(shè)計(jì)技巧27
2.2.7用單鏈表實(shí)現(xiàn)集合的操作27
2.3習(xí)題解析30
2.3.1課后習(xí)題講解30
2.3.2學(xué)習(xí)自測(cè)及答案38
第3章特殊線性表——棧、隊(duì)列和串43
3.1本章導(dǎo)學(xué)43
3.2重點(diǎn)難點(diǎn)釋疑45
3.2.1淺析棧的操作特性45
3.2.2遞歸算法轉(zhuǎn)換為非遞歸算法45
3.2.3循環(huán)隊(duì)列中隊(duì)空和隊(duì)滿的判定方法47
3.2.4如何利用循環(huán)鏈表實(shí)現(xiàn)隊(duì)列的操作49
3.2.5模式匹配KMP算法中求next數(shù)組的算法49
3.3習(xí)題解析50
3.3.1課后習(xí)題講解50
3.3.2學(xué)習(xí)自測(cè)及答案56
數(shù)據(jù)結(jié)構(gòu)（C++版）學(xué)習(xí)輔導(dǎo)與實(shí)驗(yàn)指導(dǎo)目錄
第4章廣義線性表——多維數(shù)組和廣義表59
4.1本章導(dǎo)學(xué)59
4.2重點(diǎn)難點(diǎn)釋疑61
4.2.1特殊矩陣壓縮存儲(chǔ)后存儲(chǔ)位置的計(jì)算61
4.2.2稀疏矩陣壓縮存儲(chǔ)的空間性能62
4.2.3廣義表的表頭和表尾62
4.3習(xí)題解析63
4.3.1課后習(xí)題講解63
4.3.2學(xué)習(xí)自測(cè)及答案67
第5章樹和二叉樹69
5.1本章導(dǎo)學(xué)69
5.2重點(diǎn)難點(diǎn)釋疑71
5.2.1二叉樹和樹是兩種不同的樹結(jié)構(gòu)71
5.2.2二叉表示樹72
5.2.3二叉樹的構(gòu)造方法73
5.2.4二叉樹遍歷的遞歸實(shí)現(xiàn)圖解75
5.2.5二叉樹算法的設(shè)計(jì)技巧75
5.2.6哈夫曼樹的構(gòu)造過程中應(yīng)注意的問題77
5.3習(xí)題解析79
5.3.1課后習(xí)題講解79
5.3.2學(xué)習(xí)自測(cè)及答案88
第6章圖93
6.1本章導(dǎo)學(xué)93
6.2重點(diǎn)難點(diǎn)釋疑95
6.2.1深度優(yōu)先遍歷算法的非遞歸實(shí)現(xiàn)95
6.2.2圖的遍歷算法的應(yīng)用96
6.2.3有向圖的強(qiáng)連通分量98
6.2.4Kruskal算法的實(shí)現(xiàn)99
6.2.5改進(jìn)的拓?fù)渑判蛩惴?00
6.3習(xí)題解析102
6.3.1課后習(xí)題講解102
6.3.2學(xué)習(xí)自測(cè)及答案112
第7章查找技術(shù)115
7.1本章導(dǎo)學(xué)115
7.2重點(diǎn)難點(diǎn)釋疑117
7.2.1折半查找判定樹及其應(yīng)用117
7.2.2時(shí)空權(quán)衡118
7.2.3平衡二叉樹的調(diào)整方法119
7.2.4數(shù)學(xué)應(yīng)用120
7.2.5散列查找的性能分析121
7.3習(xí)題解析123
7.3.1課后習(xí)題講解123
7.3.2學(xué)習(xí)自測(cè)及答案129
第8章排序技術(shù)131
8.1本章導(dǎo)學(xué)131
8.2重點(diǎn)難點(diǎn)釋疑133
8.2.1排序算法的穩(wěn)定性133
8.2.2如何將排序算法移植到單鏈表上134
8.2.3二叉排序樹與堆的區(qū)別135
8.2.4遞歸算法的時(shí)間性能分析135
8.3習(xí)題解析138
8.3.1課后習(xí)題講解138
8.3.2學(xué)習(xí)自測(cè)及答案146
第9章索引技術(shù)151
9.1本章導(dǎo)學(xué)151
9.2習(xí)題解析153
9.2.1課后習(xí)題講解153
9.2.2學(xué)習(xí)自測(cè)及答案156
第二篇實(shí)驗(yàn)指導(dǎo)
第10章基礎(chǔ)實(shí)驗(yàn)161
10.1實(shí)驗(yàn)的一般步驟161
10.1.1概述161
10.1.2驗(yàn)證實(shí)驗(yàn)的一般步驟162
10.1.3設(shè)計(jì)實(shí)驗(yàn)和綜合實(shí)驗(yàn)的一般步驟163
10.2設(shè)計(jì)實(shí)驗(yàn)164
10.2.1在數(shù)組中求最小值164
10.2.2統(tǒng)計(jì)候選人得票164
10.3綜合實(shí)驗(yàn)165
10.3.1順序查找最好、最壞和平均的時(shí)間性能165
10.3.2比較解決相同問題的不同算法的時(shí)間性能166
第11章線性表實(shí)驗(yàn)169
11.1驗(yàn)證實(shí)驗(yàn)169
11.1.1順序表操作驗(yàn)證169
11.1.2單鏈表操作驗(yàn)證174
11.2設(shè)計(jì)實(shí)驗(yàn)180
11.2.1數(shù)組的循環(huán)移位180
11.2.2集合的交、并和差運(yùn)算的實(shí)現(xiàn)181
11.3綜合實(shí)驗(yàn)182
11.3.1約瑟夫環(huán)問題182
11.3.2一元多項(xiàng)式相加184
第12章特殊線性表——棧、隊(duì)列和串實(shí)驗(yàn)187
12.1驗(yàn)證實(shí)驗(yàn)187
12.1.1棧操作驗(yàn)證187
12.1.2隊(duì)列操作驗(yàn)證189
12.1.3串操作驗(yàn)證190
12.2設(shè)計(jì)實(shí)驗(yàn)191
12.2.1漢諾塔問題191
12.2.2火車車廂重排問題192
12.2.3統(tǒng)計(jì)文本中單詞的個(gè)數(shù)193
12.3綜合實(shí)驗(yàn)195
12.3.1表達(dá)式求值195
12.3.2迷宮問題196
12.3.3雙端隊(duì)列197
第13章廣義線性表——多維數(shù)組和廣義表實(shí)驗(yàn)199
13.1驗(yàn)證實(shí)驗(yàn)199
13.1.1對(duì)稱矩陣的壓縮存儲(chǔ)199
13.1.2廣義表操作驗(yàn)證200
13.2設(shè)計(jì)實(shí)驗(yàn)202
13.2.1稀疏矩陣的轉(zhuǎn)置202
13.2.2廣義表的遍歷203
13.3綜合實(shí)驗(yàn)203
13.3.1魔方陣203
13.3.2抽簽游戲204
第14章樹和二叉樹實(shí)驗(yàn)207
14.1驗(yàn)證實(shí)驗(yàn)207
14.1.1樹操作驗(yàn)證207
14.1.2二叉樹操作驗(yàn)證208
14.2設(shè)計(jì)實(shí)驗(yàn)211
14.2.1求二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)211
14.2.2判斷兩棵二叉樹是否相似211
14.3綜合實(shí)驗(yàn)212
14.3.1信號(hào)放大器212
14.3.2哈夫曼編碼214
第15章圖實(shí)驗(yàn)215
15.1驗(yàn)證實(shí)驗(yàn)215
15.1.1鄰接矩陣操作驗(yàn)證215
15.1.2鄰接表操作驗(yàn)證217
15.2設(shè)計(jì)實(shí)驗(yàn)220
15.2.1求無向連通圖的生成樹220
15.2.2有向圖的路徑問題220
15.3綜合實(shí)驗(yàn)221
15.3.1TSP問題221
15.3.2醫(yī)院選址問題222
第16章查找技術(shù)實(shí)驗(yàn)225
16.1驗(yàn)證實(shí)驗(yàn)225
16.1.1順序查找驗(yàn)證225
16.1.2折半查找驗(yàn)證226
16.1.3二叉排序樹的建立227
16.1.4散列表的建立229
16.2設(shè)計(jì)實(shí)驗(yàn)230
16.2.1順序查找與折半查找的性能比較230
16.2.2閉散列表和開散列表查找性能的比較231
16.3綜合實(shí)驗(yàn)233
16.3.1直方圖問題233
16.3.2簡(jiǎn)單個(gè)人電話號(hào)碼查詢系統(tǒng)233
第17章排序技術(shù)實(shí)驗(yàn)235
17.1驗(yàn)證實(shí)驗(yàn)235
17.1.1直接插入排序算法驗(yàn)證235
17.1.2起泡排序算法驗(yàn)證236
17.1.3簡(jiǎn)單選擇排序算法驗(yàn)證237
17.2設(shè)計(jì)實(shí)驗(yàn)238
17.2.1直接插入排序基于單鏈表的實(shí)現(xiàn)238
17.2.2雙向起泡排序240
17.3綜合實(shí)驗(yàn)241
17.3.1各種排序算法時(shí)間性能的比較241
17.3.2機(jī)器調(diào)度問題241
附錄245
附錄A實(shí)驗(yàn)報(bào)告的一般格式245
附錄B課程設(shè)計(jì)報(bào)告的一般格式246
參考文獻(xiàn)247