全面系統地介紹了數據結構的基礎理論和算法設計方法，對常用的數據結構做了系統的介紹，并結合數據結構的應用以及算法性能評價等內容，進一步使讀者理解數據抽象與編程實現的關系，提高用計算機解決實際問題的能力。

編寫過程中特別考慮到了面向對象程序設計（OOP）的思想與Java語言的特性，在數據結構的實現上更好地運用了Java語言，并且自始至終強調以面向對象的方式來思考、分析和解決問題。

本書注重理論聯系實際，注重基本知識的傳授與基本技能的培養。所有算法均使用Java語言實現，并通過測試運行。本書還提供了豐富的教輔材料，內容包括PPT、源代碼、課后上機實訓、習題解答等，非常適合作為數據結構的教學用書。

“數據結構”是計算機專業的重要基礎課，是該專業的核心課程之一，它是一門集技術性、理論性和實踐性于一體的課程。Java是現今一種熱門的語言，本書在編寫過程中特別考慮到了面向對象程序設計（OOP）的思想與Java語言的特性。本書在數據結構的實現上更好地運用了Java語言，并且自始至終強調以面向對象的方式來思考、分析和解決問題。

本書在編寫過程中特別考慮到了Java與對象，Java語言是完全面向對象的、簡單高效、與平臺無關、支持多線程、具有安全性和健壯性等特點，為教師和學生提供了一種精心設計并經過教學檢驗的方式，借助Java講授ADT和對象。本書教給學生如何使用線性表、詞典、棧、隊列等來組織數據。利用這些數據組織方式，學生們將學到算法設計的相關技術。

本書共9章。第1章簡單介紹Java語言，闡述數據、數據結構和算法等基本概念。第2章至第7章分別討論線性表、鏈表、棧、隊列、串、數組、廣義表、樹以及圖的基本數據結構及應用。本書第9章排序給出了多種經典排序方法，全部是用Java語言描述編寫，并經過測試運行。

本書注重理論聯系實際，注重基本知識的傳授與基本技能的培養。本書還提供了豐富的教輔材料，內容包括PPT、源代碼、課后上機實訓、習題解答等，非常適合作為數據結構的教學用書。

本書由孫琳、張宇擔任主編，肖奎、胡雙、董寧任副主編，其中第1、2章由胡雙編寫，第3、4章由肖奎編寫、第5、6章由張宇編寫，第7、8、9章由孫琳和董寧編寫。全書由羅煒主審。李禮、余璐、計菲、夏杰等幾位老師提供了豐富的案例與實踐素材，并參與部分章節的編寫，在此一并表示感謝！

本書編寫過程中參考了許多作者的大量文獻資料和國內外優秀教材，中國水利水電出版社對本書的出版給與了大力支持和幫助，作者在此一并致以誠摯的謝意。

由于編寫時間緊張，編者水平有限，難免存在疏漏，敬請讀者批評指證。

編 者

2015年6月

序
前言

第1章 緒論 1
1.1 Java簡介 1
1.1.1 Java編程語言 1
1.1.2 Java虛擬機 2
1.2 數據結構概述 2
1.2.1 學習數據結構的必要性 2
1.2.2 什么是數據結構 3
1.2.3 基本概念和術語 4
1.2.4 數據的邏輯結構 5
1.2.5 數據的存儲結構 7
1.3 算法的描述和算法分析 8
1.3.1 算法的描述 8
1.3.2 影響算法效率的因素 9
1.3.3 算法效率的評價 10
1.3.4 算法的存儲空間需求 12
本章小結 13
上機實訓 14
習題 15
第2章 線性表 17
2.1 線性表的邏輯結構 17
2.2 線性表的順序存儲結構 19
2.2.1 線性表的順序存儲結構 19
2.2.2 線性表在順序存儲結構下的運算 20
2.3 線性表的鏈式存儲 25
2.3.1 單向鏈表 25
2.3.2 循環鏈表 33
2.3.3 雙向鏈表 34
2.4 一元多項式的表示及相加 41
本章小結 47
上機實訓 47
習題 48
第3章 棧和隊列 49
3.1 棧 49
3.1.1 棧的定義及其運算 49
3.1.2 棧的順序存儲結構 51
3.1.3 棧的鏈式存儲結構 55
3.2 隊列 60
3.2.1 隊列的定義及其運算 60
3.2.2 隊列的順序存儲結構 61
3.2.3 隊列的鏈式存儲結構 71
本章小結 76
上機實訓 76
習題 77
第4章 串 78
4.1 串的基本概念 78
4.1.1 串的定義 78
4.1.2 主串和子串 79
4.2 串的存儲結構 79
4.3 串的基本運算及其實現 80
4.3.1 字符串的基本運算 80
4.3.2 串的基本運算實現 83
4.4 文本編輯 89
本章小結 90
上機實訓 91
習題 91
第5章 多維數組和廣義表 92
5.1 多維數組的概念 92
5.2 多維數組的存儲結構 93
5.2.1 行優先順序存儲 94
5.2.2 列優先順序存儲 94
5.3 特殊矩陣及其壓縮存儲 95
5.3.1 特殊矩陣 95
5.3.2 壓縮存儲 97
5.4 稀疏矩陣 99
5.4.1 稀疏矩陣的存儲 99
5.4.2 稀疏矩陣的運算 117
5.5 廣義表 123
5.5.1 廣義表的定義和性質 123
5.5.2 廣義表的存儲結構 124
5.5.3 廣義表的基本運算 127
本章小結 136
上機實訓 137
習題 137
第6章 樹 139
6.1 樹的結構定義與基本操作 139
6.1.1 樹的定義 139
6.1.2 樹的存儲結構 140
6.1.3 樹的廣義表表示 141
6.2 二叉樹 141
6.2.1 二叉樹的定義 141
6.2.2 二叉樹的性質 142
6.2.3 二叉樹的存儲結構 144
6.2.4 二叉樹類定義 145
6.2.5 樹與二叉樹的相互轉換 146
6.3 二叉樹的遍歷 147
6.3.1 先序（根）遍歷 148
6.3.2 中序（根）遍歷 148
6.3.3 后序（根）遍歷 149
6.3.4 層次遍歷 149
6.4 線索二叉樹 153
6.4.1 線索二叉樹的定義 154
6.4.2 中序線索二叉樹 159
6.5 二叉排序樹 163
6.5.1 二叉排序樹的定義 163
6.5.2 二叉排序樹的生成 164
6.5.3 刪除二叉排序樹上的結點 165
6.6 哈夫曼樹和哈夫曼算法 165
6.6.1 哈夫曼樹的定義 165
6.6.2 構造哈夫曼樹—哈夫曼算法 167
6.6.3 哈夫曼樹的應用 168
本章小結 170
上機實訓 171
習題 171
第7章 圖的基本知識 172
7.1 圖的基本知識 172
7.1.1 圖的定義 172
7.1.2 圖的相關術語 173
7.1.3 圖的基本操作 177
7.2 圖的存儲結構 177
7.2.1 鄰接矩陣 177
7.2.2 鄰接表 179
7.3 圖的遍歷 180
7.3.1 深度優先搜索遍歷 180
7.3.2 廣度優先搜索遍歷 182
7.4 最小生成樹 187
7.5 最短路徑 197
7.5.1 單源點最短路徑 198
7.5.2 所有頂點對之間的最短路徑 204
7.6 拓撲排序 211
本章小結 213
上機實訓 213
習題 214
第8章 查找 216
8.1 查找的基本概念 216
8.2 靜態查找表 218
8.2.1 順序查找 218
8.2.2 折半查找 220
8.2.3 分塊查找 225
8.3 動態查找表 226
8.4 哈希表 231
8.4.1 哈希表和哈希函數的定義 231
8.4.2 哈希函數的構造方法 233
8.4.3 處理沖突的方法 235
本章小結 240
上機實訓 240
習題 240
第9章 排序 242
9.1 排序基本概念 242
9.2 插入排序 244
9.2.1 直接插入排序 244
9.2.2 折半插入排序 247
9.2.3 希爾排序 247
9.3 交換排序 248
冒泡排序 248
9.4 堆排序 250
9.5 快速排序 256
9.6 歸并排序 260
9.7 基數排序 263
9.8 外部排序 265
9.9 各種排序方法的比較 266
本章小結 269
上機實訓 269
習題 269
參考文獻 271

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. 大學生心理健康教育 [方雄 著]