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

編寫過程中特別考慮到了面向對象程序設計（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. 輸水管線工程風險管理 [張勇 黨亥生 著]
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. 網絡規劃設計師備考一本通 [夏杰 編著]