數(shù)據(jù)結(jié)構(gòu)學習輔導與實驗指導

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