內容豐富，題型多樣。

涉及面廣，適用性強。

習題精解，綜合訓練。

“數據結構”課程是計算機專業及相關專業的一門重要專業基礎課，也是一門必修的核心課程。在計算機科學的各領域中，都會用到各種不同的數據結構：編譯系統中要使用棧、散列表、語法樹等；操作系統中要使用隊列、存儲管理表、目錄樹等；數據庫系統中要使用線性表、鏈表、索引樹等；人工智能中要使用廣義表、檢索樹、有向圖等；同樣在面向對象程序設計、計算機圖形學、軟件工程、多媒體技術、計算機輔助設計等領域，也會用到各種不同的數據結構。因此，學好“數據結構”這門課程，對于從事計算機技術及相關領域的工作人員來說是非常重要的，它可以使我們掌握各種不同的數據結構及其使用場合、算法的具體實現，以及每一種算法的時間復雜度分析和空間復雜度分析，知道在哪種情況下，使用哪種數據結構最方便，為以后開發大型程序而使用各種不同的數據結構奠定基礎。

由于數據結構的原理和算法比較抽象，而該課程一般在剛學完程序設計后開設，學生在程序設計方面的知識較少，因此，對于僅具有一些計算機程序設計基礎的初學者來說，理解和掌握數據結構中的原理和算法就比較困難，在解答數據結構習題時，往往感到無從下手，更不知道算法如何描述、如何編寫，作者在多年的教學中也深有感觸。作者通過多年的教學實踐，收集、整理進而編寫了這本《數據結構（C語言版）習題解答及實訓指導》，目的是：通過對習題的解答，使學生充分掌握數據結構的原理、求解數據結構問題的思路和方法，并編寫出正確的算法，進一步加深學生對基本概念的理解，提高學生分析問題和解決問題的能力，為其整個專業的學習打下堅實基礎，并為今后大型軟件開發積累較豐富的經驗。

本書是《數據結構（C語言版）》的配套教材，共兩大部分內容。第一部分為習題及解答，包含配套教材中的習題和一些綜合題，主要是對教材中的習題給出解答思路提示、算法分析，最后再給出完整的答案、算法或程序。每章都包含基本概念和算法設計方面的題型，以幫助學生掌握數據結構的基本概念，提高其使用各種不同的數據結構分析問題、解決問題的能力。第二部分為上機實訓指導，包含C語言的上機環境介紹，并給出了十套實訓題，每套實訓題包括多道上機題目，都給出了實訓目的、采用的主要方法和算法設計技巧，最后給出了完整的C語言源程序來實現算法，本書所有C語言源程序都在VC++ 6.0環境下運行通過。這些實訓題可以使學生了解并學會如何運用數據結構知識去解決現實世界中的某些實際問題，且具備設計較復雜算法的基本能力。

本書的目的是幫助學生學好“數據結構”這門課程，所以在使用本書的過程中，請注意以下幾點：第一，該書要與《數據結構（C語言版）》教材一起使用，以便與課程內容同步，有利于學生進一步掌握各種基礎知識，加深對課堂所講授內容的理解；第二，算法設計是不唯一的，除了書中給出的算法外，學生可能還會有其他的算法，這說明學生對這方面的知識掌握得很好；第三，本書旨在幫助學生學習和理解數據結構知識，請學生在做作業前，先自己動腦思考、動手寫，不要盲目照抄答案，否則只會收到事倍功半的效果。

本書的最大特點是采用C語言作為算法的描述語言，所有算法都已經上機調試通過。但是，由于篇幅所限，大部分算法都是以單獨的函數形式給出，若讀者要運行這些算法，還必須給出一些變量的說明及主函數來調用所給的函數。因此，書中的算法描述比用類C語言描述的算法更直觀，更易于讀者理解和接受。作者在十幾年的“數據結構”課程教學中，對數據結構中的各種算法進行了認真的研究和分析，在這方面積累了豐富的經驗，因此，書中所選的綜合題和習題都具有一定的針對性，都是針對特定的數據結構來描述的，能為復雜的數據結構算法描述架橋鋪路。

本書可以作為高等院校本科及�？茖W生學習數據結構的參考資料，也可作為數據結構自學者的參考書和碩士研究生入學考試的參考教材，同時還可供從事計算機應用工作的工程與技術人員參考。選用本書的學校，可以根據學校自身的條件，在十套實訓題中有針對性地選擇。

本書由李根強、謝月娥擔任主編，由李根強老師統稿、修改、定稿。在本書的編寫過程中，得到了湖南大學計算機與通信學院領導的大力支持，在此深表感謝。

由于時間倉促及作者水平有限，書中不妥和錯誤之處在所難免，敬請廣大讀者批評指正。

編 者

2017年2月

第一部分 習題及解答
第1章 緒論 1
1.1 基本概念 1
1.1.1 數據結構 1
1.1.2 存儲方式 1
1.1.3 算法及評價 2
1.2 習題及解答 2
1.2.1 配套教材中的習題 2
1.2.2 綜合題 10
第2章 線性表 14
2.1 基本概念及運算 14
2.1.1 順序表 14
2.1.2 線性鏈表 14
2.1.3 雙向鏈表 14
2.1.4 循環鏈表 14
2.2 習題及解答 14
2.2.1 配套教材中的習題 14
2.2.2 綜合題 31
第3章 棧和隊列 37
3.1 基本概念及運算 37
3.1.1 棧 37
3.1.2 隊列 37
3.2 習題及解答 37
3.2.1 配套教材中的習題 37
3.2.2 綜合題 46
第4章 串 53
4.1 基本概念及運算 53
4.1.1 串的順序存儲及運算 53
4.1.2 串的鏈式存儲及運算 53
4.2 習題及解答 53
4.2.1 配套教材中的習題 53
4.2.2 綜合題 62
第5章 多維數組和廣義表 67
5.1 基本概念及運算 67
5.1.1 多維數組的概念及存儲 67
5.1.2 特殊矩陣及壓縮存儲 67
5.1.3 稀疏矩陣及壓縮存儲 67
5.1.4 廣義表的存儲及運算 67
5.2 習題及解答 68
5.2.1 配套教材中的習題 68
5.2.2 綜合題 75
第6章 樹和二叉樹 81
6.1 樹的基本概念 81
6.1.1 樹的定義 81
6.1.2 基本術語 81
6.1.3 樹的表示 82
6.2 二叉樹的基本概念和性質 82
6.2.1 二叉樹的定義 82
6.2.2 二叉樹的性質 82
6.2.3 二叉樹的存儲結構 83
6.2.4 二叉樹的基本運算 83
6.2.5 二叉樹的應用 83
6.2.6 樹、森林和二叉樹之間的相互關系 83
6.3 習題及解答 83
6.3.1 配套教材中的習題 83
6.3.2 綜合題 93
第7章 圖 102
7.1 基本概念及運算 102
7.1.1 圖的基本術語 102
7.1.2 圖的存儲形式 103
7.1.3 圖的基本運算 103
7.2 習題及解答 103
7.2.1 配套教材中的習題 103
7.2.2 綜合題 123
第8章 查找 131
8.1 基本概念 131
8.1.1 順序查找 131
8.1 2 二分查找 131
8.1.3 分塊查找 131
8.1.4 二叉排序樹查找 131
8.1.5 散列查找 132
8.2 習題及解答 132
8.2.1 配套教材中的習題 132
8.2.2 綜合題 139
第9章 內排序 144
9.1 基本概念 144
9.1.1 插入排序 144
9.1.2 交換排序 144
9.1.3 選擇排序 144
9.1.4 歸并排序 144
9.1.5 分配排序 144
9.2 習題及解答 144
9.2.1 配套教材中的習題 144
9.2.2 綜合題 155
第10章 外排序 160
10.1 基本概念 160
10.1.1 外排序的基本概念 160
10.1.2 初始歸并段的生成 160
10.1.3 多路平衡歸并 160
10.2 習題及解答 160
第11章 文件 175
11.1 基本概念 175
11.1.1 文件的基本概念 175
11.1.2 文件的存儲和組織 175
11.2 習題及解答 176
第二部分 上機實訓指導
第12章 上機環境 178
12.1 Turbo C上機環境 178
12.1.1 建立C語言源程序 178
12.1.2 打開已存在的C語言源程序 179
12.1.3 編譯并運行C語言源程序 179
12.2 Visual C++上機環境 181
12.2.1 新建C語言源程序并編譯和運行 181
12.2.2 打開已經存在的源程序并編譯
和運行 187
12.2.3 源程序的保存 189
第13章 實訓內容 190
實訓題一 線性表的順序存儲 190
一、實訓目的 190
二、實訓內容 190
三、算法描述 190
實訓題二 線性表的鏈式存儲 193
一、實訓目的 193
二、實訓內容 194
三、算法描述 194
實訓題三 棧和隊列的應用 203
一、實訓目的 203
二、實訓內容 203
三、算法描述 203
實訓題四 多維數組的應用 212
一、實訓目的 212
二、實訓內容 212
三、算法描述 212
實訓題五 二叉樹的遍歷和應用 218
一、實訓目的 218
二、實訓內容 218
三、算法描述 218
實訓題六 哈夫曼樹的建立及應用 226
一、實訓目的 226
二、實訓內容 226
三、算法描述 226
實訓題七 圖的鄰接矩陣和遍歷 228
一、實訓目的 228
二、實訓內容 229
三、算法描述 229
實訓題八 圖的鄰接表和遍歷 231
一、實訓目的 231
二、實訓內容 231
三、算法描述 231
實訓題九 查找 234
一、實訓目的 234
二、實訓內容 234
三、算法描述 234
實訓題十 排序 238
一、實訓目的 238
二、實訓內容 238
三、算法描述 238
參考文獻 246

1. 庭院風骨—樹、灌、籬 [創意房主 著]
2. Python語言程序設計教程 [郭其標 房宜汕]
3. 微積分（經管類）教程篇（下冊） [曹海軍 王海棠 周玲麗]
4. 微積分（經管類）教程篇（上冊） [曹海軍 王海棠 周玲麗]
5. 微積分（經管類）導學篇（上冊） [王海棠 曹海軍 周玲麗]
6. 網站前端技術案例教程（HTML+CSS+JavaScript）（第二版） [黃華升]
7. 線性代數 [主編 史昱 陳鳳欣]
8. 電力電子技術課程學習及實驗指導 [主編 陳榮]
9. 成長對話：青春的榜樣 [主編　施端銀　黃武剛　應巨林]
10. 人工智能應用基礎 [主編 楊纓 李佳]
11. 中華水文化（慕課版）（第二版） [畢雪燕 楊華軻 羅玲誼 等編著]
12. 電路與電子技術Ⅱ——電路分析基礎 [主編 陳曉 金哲]
13. 飛機維修專業英語——飛機系統（第二版） [趙迎春]
14. 英語大爆炸：跟趣味情景劇學口語（微課版） [秦然　編著]
15. 機械工程制圖任務跟蹤訓練 [主編 王瑞清 趙金考 周彥云 ]
16. 機械工程制圖 [主編 覃國萍 劉百順 禹晨]
17. 平面設計與制作項目化教程 [主編　李晨]
18. 后期影像剪輯技術 [主編　郭建偉]
19. 人工智能概論（第二版） [主編　任云暉　丁紅　徐迎春 ]
20. 信息時代美育之道 [主編　劉宏宇　黎婭]
21. 數字媒體交互設計項目式教程（微課版） [主編　蘇陸]
22. 動畫運動規律項目實例解析（微課版） [孫珊珊　袁維坤]
23. 自然語言處理 [主編　馮建周]
24. 新媒體內容創作實務（微課版） [主編　覃思源]
25. 人工智能基礎 [主編 余平 張春陽]
26. 人工智能導論 [主編 王飛 潘立武]
27. Amazing！兒童英語自然拼讀分級教材（全8冊） [王玲　編著]
28. Spark大數據處理技術 [主編　劉仁山　周洪翠　莊新妍]
29. 毫無PS痕跡—你的第一本Photoshop書（第二版） [趙鵬 著]
30. 電視新聞制作（活頁式） [主編 王曉翠 劉傳琳]