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

本書遵循“數據結構”課程的教學習慣，內容分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：zhidongjie@126.com。

作 者

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. 信息技術基礎（麒麟操作系統+WPS Office） [主編　芮雪　蔣莉　王亮亮]
2. Office高級應用項目式教程（第2版） [主編 李觀金 張倩文 黎夏克 ]
3. 巧用翻譯學英語：英漢互譯500例 [王學文 著]
4. 高等教育多維評價體系構建與高質量發展研究 [張妍 著]
5. 系統規劃與管理師章節習題與考點特訓（第二版） [主編 薛大龍]
6. 計算機操作系統實踐指導（openEuler版） [主編 秦光 曾陳萍 岳付強]
7. 信息系統管理工程師真題及模考卷精析（適用機考） [主 編 薛大龍 程 剛 上官緒]
8. 航海類院校體育教育教學研究 [張利超 李寧 著]
9. 新時代背景下我國職業教育產教融合長效機制建設研究 [王玉賢 著]
10. 電路分析 [主編 李飛 毛先柏]
11. 信息系統管理工程師（適用第2版大綱）一站通關 [指尖瘋　編著]
12. 傳統山水畫論解讀與實踐 [陳鈉 著]
13. 網絡工程師備考一本通（適配第6版考綱） [夏杰 編著]
14. 陳孝云的職教理想與情懷 [祝吉太 江傳瑞 張義廷 著]
15. 地方本科院校電子信息學科課程思政案例集 [王甫]
16. Excel數據處理與分析（第二版） [主編 張志明 鄒 蕾]
17. 網絡工程師5天修煉（適配第6版考綱） [主編　朱小平 施游]
18. 倉儲管理實務（第二版） [周寧武 編著]
19. 基于AE與C#的地理信息系統二次開發 [李小根 賈艷昌 喬翠平 姜彤 ]
20. 2023年長沙市文化和旅游業發展報告 [主編 陳莉]
21. 舞臺化妝造型設計 [主編 劉思彤 張 濤 張憶雨]
22. 產教融合視角高校體育專業實踐教學體系構建研究 [楊柳青 葉華兵 著]
23. 知識圖譜及應用案例 [張善文 黃文準 于長青 陳明淑]
24. Python程序設計案例教程（微課版） [主編　石利平　田輝平　余以勝]
25. 皓月繁星：青少年兒童心理成長手冊 [主　編　林贊歌 副主編　杜志南]
26. 材料力學 [章寶華 趙新勝 徐斌]
27. 系統集成項目管理工程師考試32小時通關（第3版） [主編　薛大龍 副主編　上官緒陽]
28. 軟考論文高分特訓與范文10篇——系統分析師（第二版） [薛大龍 鄒月平 施游]
29. 黃河海勃灣水利樞紐防凌安全運行 [王戰領 王叢發 范瑜彬 著]
30. 大學生心理健康教育 [方雄 著]