數據結構教程習題解析與上機指導（簡體書）

本書從實踐角度對數據結構內容進行了完善和補充，是與《數據結構教程》（胡元義，黑新宏主編，電子工業出版社，ISBN 978-7-121-35131-0）配套使用的輔助教材。本書一方面對《數據結構教程》中的習題給出了深入淺出的解析，另一方面對《數據結構教程》中出現的算法和部分習題算法調試了近80個上機實現程序並涵蓋了數據結構的所有內容，這對深入掌握和靈活運用數據結構知識，提高解題和編程的思維、方法以及實際動手能力都有很大的幫助。 本書也是一本難得的數據結構算法實現與輔助教材，可以配合目前各類數據結構（C語言）教材使用，起到銜接教學與實踐的作用。此外，本書也可作為考研資料以及計算機應用人員的實用資料和參考書。

數據結構是計算機及相關專業的主幹課程之一，其目的是讓讀者學習、分析和研究數據對象的特性及數據的組織方法，以便讀者選擇合適的數據邏輯結構和存儲結構，設計相應的運算操作，把現實世界中的問題轉化為計算機的內部表示與處理方法。在信息科學領域中，尤其是在系統軟件和應用軟件的設計以及應用中要用到各種數據結構，因此，掌握數據結構對提高軟件設計能力和程序編寫水平有很大的幫助。
本書分為兩篇。第一篇為習題解析：第1～9章分別是《數據結構教程》中各章的習題解析。該篇可在學習數據結構課程時同步使用，以幫助學生對數據結構知識的學習和掌握有一個比較全面、深入和系統的認識，達到使理論轉化為能力的目的。習題解析部分是作者在多年講授數據結構課程基礎上總結、歸納編寫而成的，大多數取自歷年的考研試題。為了便於讀者正確理解有關數據結構的概念，掌握解題思路、方法和技巧，各章的習題大多給出了詳盡的解題過程，對有代表性的習題，也給出了詳細的分析、歸納和說明。此外，針對某些難題，書中還給出了一些新的解題思路和方法。通過習題解析，引導讀者由基本概念出發尋找求解數據結構問題普遍的思路和方法，並由此深化對理論知識的理解，達到舉一反三、提高分析問題與解決問題能力的目的。由於習題許多都選自歷屆考研試題，因此也可作為考研複習資料。習題解析部分的各章算法習題都已通過上機驗證，只不過由於書的篇幅所限，沒有給出完整程序，其完整的實現程序見作者于西安電子科技大學出版社出版的《數據結構（C語言）實踐教程（第二版）》一書。
第二篇為算法上機實現：第10～17章對《數據結構教程》中出現的算法和部分習題算法給出了近80個上機實現程序並涵蓋了數據結構的所有內容，這對深入掌握和靈活運用數據結構知識，提高編程的思維、方法和實際動手能力都有很大的幫助。數據結構課程對理論與實踐的要求都相當高，並且內容多、難度大，雖然大多數數據結構教材都強調了實踐的重要性，但缺乏供學生實踐練習的資料和環節，很多教材對算法的描述也只是概述性的偽代碼，而無法直接上機實現，學生很難將這些算法轉化為可實現的程序。本篇對《數據結構教程》中所有的算法都給出了上機實現程序和詳細的程序注釋，閱讀起來一目了然，學生能夠很快地掌握算法的精髓和實現手段，同時使學生對數據結構知識的實踐與應用有一個比較全面、深入和系統的認識，達到理論與實踐相結合的目的。通過上機實踐，可以開拓學生的視野，培養學生的創新能力。此外，本篇給出的上機程序無論是從數據結構內容的全面性、完整性、實用性還是從程序設計的新穎性都具有突出的特點，因此它是一本難得的實用計算機輔助教材。由於作者水平所限，書中難免存在錯誤和不妥之處，敬請讀者批評指正。

編 者
2018年5月

第一篇 習 題 解 析
第1章 緒論習題解析 2
第2章 線性表習題解析 8
第3章 棧和隊列習題解析 16
第4章 串習題解析 26
第5章 數組與廣義表習題解析 36
第6章 樹與二叉樹習題解析 48
第7章 圖習題解析 69
第8章 查找習題解析 92
第9章 排序習題解析 111
第二篇 算法上機實現
第10章 線性表算法上機實現 132
10.1 順序表基本運算 132
10.2 在表頭插入生成單鏈表 134
10.3 在表尾插入生成單鏈表 135
10.4 單鏈表基本運算 136
10.5 雙向鏈表基本運算 139
10.6 靜態鏈表 142
10.7 例2.1算法實現 144
10.8 例2.2算法實現 145
10.9 例2.3算法實現 147
10.10 例2.4算法實現 148
10.11 例2.5算法實現 150
第11章 棧和隊列算法上機實現 152
11.1 順序棧基本運算 152
11.2 鏈棧基本運算 154
11.3 循環隊列基本運算 157
11.4 鏈隊列基本運算 158
11.5 例3.1算法實現 160
11.6 例3.5算法實現 163
第12章 串算法上機實現 166
12.1 順序串基本運算 166
12.2 生成鏈串與求串長、串連接運算 168
12.3 鏈串中求子串運算 170
12.4 鏈串中串插入運算 171
12.5 串的簡單模式匹配 173
12.6 串的無回溯KMP匹配 174
第13章 數組與廣義表算法上機實現 177
13.1 矩陣轉置 177
13.2 矩陣的快速轉置 179
13.3 稀疏矩陣的十字鏈表存儲 181
13.4 生成廣義表及求廣義表長度和深度的運算 184
第14章 樹與二叉樹算法上機實現 188
14.1 二叉樹的遍歷 188
14.2 二叉樹的非遞歸遍歷 190
14.3 另一種後序非遞歸遍歷二叉樹的方法 192
14.4 按層次遍歷二叉樹 194
14.5 由二叉樹的遍歷序列恢復二叉樹 196
14.6 二叉樹遍歷的應用 198
14.7 中序線索二叉樹 200
14.8 哈夫曼樹及哈夫曼編碼 203
14.9 例6.4算法實現 207
第15章 圖算法上機實現 210
15.1 建立無向圖的鄰接矩陣 210
15.2 圖的深度優先搜索 211
15.3 圖的廣度優先搜索 213
15.4 圖的連通性 216
15.5 深度優先生成樹 219
15.6 廣度優先生成樹 221
15.7 最小生成樹的Prim算法 224
15.8 最小生成樹的Kruskal算法 225
15.9 單源點最短路徑的Dijkstra算法 227
15.10 每一對頂點間最短路徑的Floyd算法 229
15.11 拓撲排序 231
15.12 關鍵路徑 233
第16章 查找算法上機實現 239
16.1 順序查找 239
16.2 折半（二分）查找 240
16.3 分塊查找 241
16.4 二叉排序樹建立、節點的查找和刪除 242
16.5 平衡二叉樹的建立、節點的查找和刪除 246
16.6 哈希（Hash）查找 252
第17章 排序算法上機實現 256
17.1 插入排序 256
17.2 折半插入排序 257
17.3 希爾（Shell）排序 258
17.4 冒泡排序 259
17.5 雙向冒泡排序 260
17.6 快速排序 262
17.7 選擇排序 263
17.8 雙向選擇排序 264
17.9 堆排序 265
17.10 歸併排序的遞歸算法實現 267
17.11 歸併排序的非遞歸算法實現 268
17.12 基數排序 270
參考文獻 273