數(shù)據(jù)結(jié)構(gòu)（C語言版）習題解答及實訓指導

內(nèi)容豐富，題型多樣。

涉及面廣，適用性強。

習題精解，綜合訓練。

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

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

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

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

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

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

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

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

編 者

2017年2月

第一部分 習題及解答
第1章 緒論 1
1.1 基本概念 1
1.1.1 數(shù)據(jù)結(jié)構(gòu) 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 循環(huán)鏈表 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章 多維數(shù)組和廣義表 67
5.1 基本概念及運算 67
5.1.1 多維數(shù)組的概念及存儲 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 基本術(shù)語 81
6.1.3 樹的表示 82
6.2 二叉樹的基本概念和性質(zhì) 82
6.2.1 二叉樹的定義 82
6.2.2 二叉樹的性質(zhì) 82
6.2.3 二叉樹的存儲結(jié)構(gòu) 83
6.2.4 二叉樹的基本運算 83
6.2.5 二叉樹的應用 83
6.2.6 樹、森林和二叉樹之間的相互關(guān)系 83
6.3 習題及解答 83
6.3.1 配套教材中的習題 83
6.3.2 綜合題 93
第7章 圖 102
7.1 基本概念及運算 102
7.1.1 圖的基本術(shù)語 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章 內(nèi)排序 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章 上機環(huán)境 178
12.1 Turbo C上機環(huán)境 178
12.1.1 建立C語言源程序 178
12.1.2 打開已存在的C語言源程序 179
12.1.3 編譯并運行C語言源程序 179
12.2 Visual C++上機環(huán)境 181
12.2.1 新建C語言源程序并編譯和運行 181
12.2.2 打開已經(jīng)存在的源程序并編譯
和運行 187
12.2.3 源程序的保存 189
第13章 實訓內(nèi)容 190
實訓題一 線性表的順序存儲 190
一、實訓目的 190
二、實訓內(nèi)容 190
三、算法描述 190
實訓題二 線性表的鏈式存儲 193
一、實訓目的 193
二、實訓內(nèi)容 194
三、算法描述 194
實訓題三 棧和隊列的應用 203
一、實訓目的 203
二、實訓內(nèi)容 203
三、算法描述 203
實訓題四 多維數(shù)組的應用 212
一、實訓目的 212
二、實訓內(nèi)容 212
三、算法描述 212
實訓題五 二叉樹的遍歷和應用 218
一、實訓目的 218
二、實訓內(nèi)容 218
三、算法描述 218
實訓題六 哈夫曼樹的建立及應用 226
一、實訓目的 226
二、實訓內(nèi)容 226
三、算法描述 226
實訓題七 圖的鄰接矩陣和遍歷 228
一、實訓目的 228
二、實訓內(nèi)容 229
三、算法描述 229
實訓題八 圖的鄰接表和遍歷 231
一、實訓目的 231
二、實訓內(nèi)容 231
三、算法描述 231
實訓題九 查找 234
一、實訓目的 234
二、實訓內(nèi)容 234
三、算法描述 234
實訓題十 排序 238
一、實訓目的 238
二、實訓內(nèi)容 238
三、算法描述 238
參考文獻 246

1. 零基礎(chǔ)玩轉(zhuǎn)國產(chǎn)大模型DeepSeek [徐永冰 張帥 編著]
2. 網(wǎng)絡工程師5天修煉（適配第6版考綱） [主編　朱小平 施游]
3. 信息系統(tǒng)項目管理師考試32小時通關(guān)（適用第4版考綱） [薛大龍]
4. 信息系統(tǒng)管理工程師考試32小時通關(guān)（適配第2版考綱） [薛大龍　劉偉]
5. 土木工程材料檢測實訓 [洪曉江 達則曉麗 錢波]
6. 科技信息檢索與論文寫作實用教程 [李振華]
7. 傳統(tǒng)山水畫論解讀與實踐 [陳鈉 著]
8. Python數(shù)據(jù)庫編程 [主編 殷樹友 邢 翀]
9. 計算機基礎(chǔ)實訓指導 [主編 袁春萍 朱妮]
10. 嵌入式人工智能技術(shù)應用（數(shù)字教材） [主編 胡娜 楊國勇 晏廷榮]
11. Vienna整流器技術(shù) [桂存兵 著]
12. 變頻器與伺服應用 [陳剛 葉云飛]
13. 物聯(lián)網(wǎng)工程設計與實踐 [湯琳 李敏]
14. 爐邊夜話——深入淺出話AI [汪建　著]
15. 電商運營與管理 [鐘肖英 陳瀟]
16. Java面向?qū)ο蟪绦蛟O計 [主編 姜春磊 陳虹潔]
17. 信息技術(shù)基礎(chǔ)（Windows 10+WPS Office）（微課版） [主編　石利平　田輝平　謝盛嘉]
18. 人工智能應用 [主編　陳　萍　劉培培　陳孟軍]
19. 大學生職業(yè)發(fā)展與就業(yè)指導 [主編　劉志堅]
20. 高級辦公應用項目教程 [主編 屈晶 趙成麗]
21. 微信小程序開發(fā)項目實戰(zhàn)（微課版） [主編 黃龍泉 郭峰 朱倩]
22. 企業(yè)檔案工作實戰(zhàn)寶典百問百答 [華俊 盧秀英 邵甜甜 著]
23. 計算機網(wǎng)絡原理及應用 [主編 唐繼勇 葉坤 孫夢娜]
24. 大學生創(chuàng)業(yè)基礎(chǔ) [主編 王麗莉 王 楊]
25. 船舶輔機 [主編 王連海 于洋 姜淑翠]
26. 大學生就業(yè)指導 [主編 王麗莉 董宴廷]
27. 系統(tǒng)架構(gòu)設計師章節(jié)習題與考點特訓 [主編 薛大龍 鄒月平]
28. 高校學生工作探索與實踐 [郭亮 著]
29. 大學生情商管理 [方雄 著]
30. 2023年長沙市會展業(yè)發(fā)展報告 [主編 周棟良]