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

本書遵循“數(shù)據(jù)結(jié)構(gòu)”課程的教學(xué)習(xí)慣，內(nèi)容分7章：第1章給出了數(shù)組C++程序、順序表C++程序和字符串C++程序；第2章給出了帶頭結(jié)點的單鏈表C程序、不帶頭結(jié)點的單鏈表C程序、循環(huán)鏈表的C程序、不帶表頭結(jié)點的單鏈表C++程序、用模板定義的帶頭結(jié)點的單鏈表C++程序和單鏈表的游標(biāo)（Iterator）類的C++程序；第3章給出了棧的C程序、鏈?zhǔn)綏５腃++程序和實現(xiàn)鏈隊列的C程序；第4章給出了二叉樹的Turbo Pascal（5.5）語言程序、二叉樹的C++程序及實例、線索二叉樹Turbo Pascal（5.5）語言程序和哈夫曼樹及應(yīng)用C程序；第5章給出了用位向量實現(xiàn)集合運算的C++程序、用有序鏈表實現(xiàn)集合運算的C++程序、順序搜索C++程序、基于有序順序表的折半搜索的C++程序、二叉搜索樹的C++程序和平衡二叉搜索樹（AVL）的C++程序；第6章給出了鄰接表的C程序、十字鏈表的C程序、圖的連通性的C程序、拓撲排序的C程序、關(guān)鍵路徑的C程序、鄰接表/圖的深度優(yōu)先搜索的C++程序、用頂點表示活動的網(wǎng)絡(luò)（AOV網(wǎng)絡(luò)）的C++程序和用邊表示活動的網(wǎng)絡(luò)（AOE網(wǎng)絡(luò)）的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版本。

本書中可能存在不準(zhǔn)確或不完整的地方，內(nèi)容編排上可能存在不合理之處，敬請廣大讀者批評指正。作者E-mail：zhidongjie@126.com。

作 者

2007年10月

序
前言
第1章 數(shù)組 1
1.1 數(shù)組的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 線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn) 13
2.1.1 概述 13
2.1.2 帶頭結(jié)點的單鏈表的C程序 13
2.1.3 不帶頭結(jié)點的單鏈表的C程序 19
2.2 循環(huán)鏈表 23
2.2.1 循環(huán)鏈表概述 23
2.2.2 循環(huán)鏈表的C程序 23
2.3 不帶表頭結(jié)點的單鏈表的C++程序 28
2.4 用模板定義的帶頭結(jié)點的單鏈表 32
2.5 單鏈表的游標(biāo)（Iterator）類 35
第3章 棧和隊列 41
3.1 棧 41
3.1.1 棧的描述 41
3.1.2 棧的C程序 41
3.2 鏈?zhǔn)綏５腃++程序及運行 43
3.3 隊列 45
3.3.1 隊列的描述 45
3.3.2 實現(xiàn)鏈隊列的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 哈夫曼樹及應(yīng)用的C程序 63
第5章 集合與搜索 67
5.1 集合 67
5.1.1 概述 67
5.1.2 用位向量實現(xiàn)集合運算的C++程序 67
5.1.3 用有序鏈表實現(xiàn)集合運算 70
5.2 靜態(tài)搜索結(jié)構(gòu) 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 關(guān)鍵路徑的C程序 111
6.7 鄰接表、圖的深度優(yōu)先搜索的C++程序（1） 114
6.8 鄰接表、圖的深度優(yōu)先搜索的C++程序（2） 119
6.9 用頂點表示活動的網(wǎng)絡(luò)（AOV網(wǎng)絡(luò)） 124
6.10 用邊表示活動的網(wǎng)絡(luò)（AOE網(wǎng)絡(luò)） 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本書不同于《數(shù)據(jù)結(jié)構(gòu)》只講理論，《數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析》是概念與理論的重復(fù)，有關(guān)程序是片段的，正確與否也不以實例驗證，而本書中有豐富的數(shù)據(jù)結(jié)構(gòu)程序?qū)嵗�，主要�?nèi)容包括：數(shù)組、鏈表、棧和隊列、二叉樹、集合與搜索、圖、排序等，尤其鏈表、二叉樹、集合與搜索、圖的內(nèi)容更為詳細，全書條理清晰，通俗易懂，圖文并茂。
本書適合高等院校計算機專業(yè)、軟件專業(yè)和信息管理專業(yè)的學(xué)生和教師使用，也可供計算機軟件人員和計算機用戶閱讀。
本書程序源代碼可以從中國水利水電出版社網(wǎng)站上免費下載，網(wǎng)址為：http://www.waterpub.com.cn/softdown/。

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