內容豐富，題型多樣。

涉及面廣，適用性強。

習題精解，綜合訓練。

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

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

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

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

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

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

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

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

編 者

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. 民用航空飛機標準線路施工 [主編　王志敏　陳明]
3. 不息的水脈—大運河講談錄 [趙珩　著]
4. 實用運籌學 [主編　邢育紅　于晉臣]
5. 三峽梯級電站水資源決策支持系統研究與開發 [姚華明 潘紅忠 湯正]
6. 海南黎族民俗文化鑒賞 [龐國華　著]
7. 石墨烯在太赫茲及中紅外頻段電磁器件設計中的應用 [李艷秀 莊華偉 著]
8. 電子技術（第二版） [主編 覃愛娜 李飛]
9. 辦公自動化高級應用 [陳萍 朱曉玉]
10. 信息處理技術員考試32小時通關 [薛大龍]
11. 電子產品設計案例教程（微課版）—基于嘉立創EDA（專業版） [王靜 莫志宏 陳學昌 丁紅]
12. C程序設計實踐教程 [劉衛國]
13. C程序設計（慕課版） [劉衛國]
14. Web技術開發教程（基于.NET開源MVC框架） [王合闖 韓紅玲 王青正 陳海蕊]
15. 商務英語翻譯教程（筆譯）（第四版） [主編 王軍平]
16. 智慧零售技術與應用 [洪旭 著]
17. 建設工程法規實務 [主編 余瀅]
18. 商務秘書理論與實務（第三版） [主編 張同欽]
19. 程序設計基礎實踐教程（C/C++語言版） [張桂芬 葛麗娜]
20. C++案例項目精講 [主編 楊國興]
21. 勞動爭議處理實務 [主編 王秀卿 羅靜]
22. 工程數學 [主編 郭立娟 王海]
23. 語音識別理論與實踐 [主編　莫宏偉]
24. 信息系統項目管理師章節習題與考點特訓（第二版） [主編 薛大龍]
25. 武術基礎教程 [主編 李代勇 謝志民]
26. 計算機網絡實訓教程 [主編 張浩軍 趙玉娟]
27. 畫法幾何與機械制圖習題集（多學時） [主編 趙軍]
28. HCIA-Datacom認證題庫分類精講 [主 編 韓立剛]
29. SwiftUI完全開發 [李智威 著]
30. 網絡規劃設計師備考一本通 [夏杰 編著]