數據結構學習輔導與實驗指導

第一篇學習輔導
第1章緒論1
1.1本章導學1
1.2重點難點釋疑5
1.2.1信息、數據與結構5
1.2.2數據結構、數據類型和抽象數據類型5
1.2.3邏輯結構與存儲結構6
1.2.4如何選擇或設計數據結構7
1.2.5問題、算法與程序7
1.2.6算法設計的一般原則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存儲結構與存取結構19
2.2.2頭指針、尾標志、開始結點與頭結點19
2.2.3帶頭結點的單鏈表與不帶頭結點的單鏈表
的區(qū)別20
2.2.4單鏈表算法的設計技巧22
2.2.5有序單鏈表的算法設計技巧25
2.2.6循環(huán)鏈表的算法設計技巧27
2.2.7用單鏈表實現集合的操作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遞歸算法轉換為非遞歸算法45
3.2.3循環(huán)隊列中隊空和隊滿的判定方法47
3.2.4如何利用循環(huán)鏈表實現隊列的操作49
3.2.5模式匹配KMP算法中求next數組的算法49
3.3習題解析50
3.3.1課后習題講解50
3.3.2學習自測及答案56
數據結構（C++版）學習輔導與實驗指導目錄
第4章廣義線性表——多維數組和廣義表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二叉樹和樹是兩種不同的樹結構71
5.2.2二叉表示樹72
5.2.3二叉樹的構造方法73
5.2.4二叉樹遍歷的遞歸實現圖解75
5.2.5二叉樹算法的設計技巧75
5.2.6哈夫曼樹的構造過程中應注意的問題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)先遍歷算法的非遞歸實現95
6.2.2圖的遍歷算法的應用96
6.2.3有向圖的強連通分量98
6.2.4Kruskal算法的實現99
6.2.5改進的拓撲排序算法100
6.3習題解析102
6.3.1課后習題講解102
6.3.2學習自測及答案112
第7章查找技術115
7.1本章導學115
7.2重點難點釋疑117
7.2.1折半查找判定樹及其應用117
7.2.2時空權衡118
7.2.3平衡二叉樹的調整方法119
7.2.4數學應用120
7.2.5散列查找的性能分析121
7.3習題解析123
7.3.1課后習題講解123
7.3.2學習自測及答案129
第8章排序技術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章索引技術151
9.1本章導學151
9.2習題解析153
9.2.1課后習題講解153
9.2.2學習自測及答案156
第二篇實驗指導
第10章基礎實驗161
10.1實驗的一般步驟161
10.1.1概述161
10.1.2驗證實驗的一般步驟162
10.1.3設計實驗和綜合實驗的一般步驟163
10.2設計實驗164
10.2.1在數組中求最小值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設計實驗180
11.2.1數組的循環(huán)移位180
11.2.2集合的交、并和差運算的實現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設計實驗191
12.2.1漢諾塔問題191
12.2.2火車車廂重排問題192
12.2.3統(tǒng)計文本中單詞的個數193
12.3綜合實驗195
12.3.1表達式求值195
12.3.2迷宮問題196
12.3.3雙端隊列197
第13章廣義線性表——多維數組和廣義表實驗199
13.1驗證實驗199
13.1.1對稱矩陣的壓縮存儲199
13.1.2廣義表操作驗證200
13.2設計實驗202
13.2.1稀疏矩陣的轉置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設計實驗211
14.2.1求二叉樹中葉子結點的個數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設計實驗220
15.2.1求無向連通圖的生成樹220
15.2.2有向圖的路徑問題220
15.3綜合實驗221
15.3.1TSP問題221
15.3.2醫(yī)院選址問題222
第16章查找技術實驗225
16.1驗證實驗225
16.1.1順序查找驗證225
16.1.2折半查找驗證226
16.1.3二叉排序樹的建立227
16.1.4散列表的建立229
16.2設計實驗230
16.2.1順序查找與折半查找的性能比較230
16.2.2閉散列表和開散列表查找性能的比較231
16.3綜合實驗233
16.3.1直方圖問題233
16.3.2簡單個人電話號碼查詢系統(tǒng)233
第17章排序技術實驗235
17.1驗證實驗235
17.1.1直接插入排序算法驗證235
17.1.2起泡排序算法驗證236
17.1.3簡單選擇排序算法驗證237
17.2設計實驗238
17.2.1直接插入排序基于單鏈表的實現238
17.2.2雙向起泡排序240
17.3綜合實驗241
17.3.1各種排序算法時間性能的比較241
17.3.2機器調度問題241
附錄245
附錄A實驗報告的一般格式245
附錄B課程設計報告的一般格式246
參考文獻247