計算機加工處理的對象是數據，而數據具有一定的結構，所以編寫計算機程序僅僅掌握計算機語言還不夠，還必須掌握數據組織、存儲和運算的方法，這便是“數據結構”課程所學習和研究的內容，它為編寫計算機程序提供良好的基礎，因此，“數據結構”被列為計算機等相關專業最重要的專業基礎課程，特別對計算機學科來說，起到承前啟后的作用。由于數據結構的原理和算法較為抽象，使很多同學難以掌握，特別是該課程一般在低年級開設，對于僅僅具有一些計算機語言程序設計知識的初學者，理解和掌握其中的原理就更困難了，在解答數據結構的習題時，往往感到無從下手。為了給讀者一些啟發，我編寫了本書，目的是：通過對本書的閱讀、補充、修改和參照數據結構習題的練習，使學生充分掌握數據結構的原理以及求解數據結構問題的思路與方法，深化對基本概念的理解，提高分析與解決問題的能力。

本書遵循“數據結構”課程的教學習慣，內容分7章：第1章給出了數組C++程序、順序表C++程序和字符串C++程序；第2章給出了帶頭結點的單鏈表C程序、不帶頭結點的單鏈表C程序、循環鏈表的C程序、不帶表頭結點的單鏈表C++程序、用模板定義的帶頭結點的單鏈表C++程序和單鏈表的游標（Iterator）類的C++程序；第3章給出了棧的C程序、鏈式棧的C++程序和實現鏈隊列的C程序；第4章給出了二叉樹的Turbo Pascal（5.5）語言程序、二叉樹的C++程序及實例、線索二叉樹Turbo Pascal（5.5）語言程序和哈夫曼樹及應用C程序；第5章給出了用位向量實現集合運算的C++程序、用有序鏈表實現集合運算的C++程序、順序搜索C++程序、基于有序順序表的折半搜索的C++程序、二叉搜索樹的C++程序和平衡二叉搜索樹（AVL）的C++程序；第6章給出了鄰接表的C程序、十字鏈表的C程序、圖的連通性的C程序、拓撲排序的C程序、關鍵路徑的C程序、鄰接表/圖的深度優先搜索的C++程序、用頂點表示活動的網絡（AOV網絡）的C++程序和用邊表示活動的網絡（AOE網絡）的C++程序；第7章給出了直接插入排序的Turbo Pascal程序、折半插入排序（Binary Insertion Sort）程序、希爾排序的Turbo Pascal語言程序、選擇排序的Turbo Pascal程序和堆排序的Turbo Pascal程序。

本書談到的C程序是指Turbo C 2.0版本，Turbo Pascal程序是指Turbo Pascal 5.5版本，C++程序是指Visual C++ 6.0版本。

本書中可能存在不準確或不完整的地方，內容編排上可能存在不合理之處，敬請廣大讀者批評指正。作者E-mail：[email protected]。

作 者

2007年10月

序
前言
第1章 數組 1
1.1 數組的C++程序 1
1.2 順序表 4
1.2.1 順序表描述 4
1.2.2 順序表的C++程序 4
1.3 字符串 9
1.3.1 字符串概述 9
1.3.2 字符串的C++程序 9
第2章 鏈表 13
2.1 線性表的鏈式表示和實現 13
2.1.1 概述 13
2.1.2 帶頭結點的單鏈表的C程序 13
2.1.3 不帶頭結點的單鏈表的C程序 19
2.2 循環鏈表 23
2.2.1 循環鏈表概述 23
2.2.2 循環鏈表的C程序 23
2.3 不帶表頭結點的單鏈表的C++程序 28
2.4 用模板定義的帶頭結點的單鏈表 32
2.5 單鏈表的游標（Iterator）類 35
第3章 棧和隊列 41
3.1 棧 41
3.1.1 棧的描述 41
3.1.2 棧的C程序 41
3.2 鏈式棧的C++程序及運行 43
3.3 隊列 45
3.3.1 隊列的描述 45
3.3.2 實現鏈隊列的C程序 46
第4章 二叉樹 49
4.1 二叉樹概述 49
4.2 二叉樹的Turbo Pascal（5.5）語言程序 49
4.3 二叉樹的C++程序及實例 52
4.4 線索二叉樹 60
4.4.1 概述 60
4.4.2 線索二叉樹Turbo Pascal（5.5）語言程序 61
4.5 哈夫曼樹及應用的C程序 63
第5章 集合與搜索 67
5.1 集合 67
5.1.1 概述 67
5.1.2 用位向量實現集合運算的C++程序 67
5.1.3 用有序鏈表實現集合運算 70
5.2 靜態搜索結構 75
5.2.1 順序搜索的C++程序 75
5.2.2 基于有序順序表的折半搜索 78
5.3 二叉搜索樹 81
5.3.1 概述 81
5.3.2 二叉搜索樹的C++程序 81
5.4 平衡二叉樹 87
5.4.1 概述 87
5.4.2 平衡二叉搜索樹（AVL）的C++程序 87
第6章 圖 93
6.1 鄰接表（Adjacency List）的C程序 93
6.2 十字鏈表 95
6.2.1 概述 95
6.2.2 十字鏈表的C程序 95
6.3 圖的連通性的C程序（1） 99
6.4 圖的連通性的C程序（2） 105
6.5 拓撲排序 108
6.5.1 概述 108
6.5.2 拓撲排序的C程序 108
6.6 關鍵路徑的C程序 111
6.7 鄰接表、圖的深度優先搜索的C++程序（1） 114
6.8 鄰接表、圖的深度優先搜索的C++程序（2） 119
6.9 用頂點表示活動的網絡（AOV網絡） 124
6.10 用邊表示活動的網絡（AOE網絡） 128
第7章 排序 135
7.1 插入排序 135
7.1.1 直接插入排序概述 135
7.1.2 直接插入排序的Turbo Pascal程序 135
7.2 折半插入排序 137
7.2.1 概述 137
7.2.2 折半插入排序的程序 137
7.3 希爾排序 139
7.3.1 希爾排序的Turbo Pascal（5.5）語言程序（1） 140
7.3.2 希爾排序的Turbo Pascal（5.5）語言程序（2） 142
7.4 選擇排序 145
7.4.1 概述 145
7.4.2 選擇排序的Turbo Pascal（5.5）語言程序 145
7.5 堆排序 146
7.5.1 概述 146
7.5.2 堆排序的Turbo Pascal語言程序 147
參考文獻 150本書不同于《數據結構》只講理論，《數據結構習題與解析》是概念與理論的重復，有關程序是片段的，正確與否也不以實例驗證，而本書中有豐富的數據結構程序實例，主要內容包括：數組、鏈表、棧和隊列、二叉樹、集合與搜索、圖、排序等，尤其鏈表、二叉樹、集合與搜索、圖的內容更為詳細，全書條理清晰，通俗易懂，圖文并茂。
本書適合高等院校計算機專業、軟件專業和信息管理專業的學生和教師使用，也可供計算機軟件人員和計算機用戶閱讀。
本書程序源代碼可以從中國水利水電出版社網站上免費下載，網址為：http://www.waterpub.com.cn/softdown/。

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