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

本書遵循“數據結構”課程的教學習慣，內容分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. 輸水管線工程風險管理 [張勇 黨亥生 著]
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. 網絡規劃設計師備考一本通 [夏杰 編著]