全面系統(tǒng)地介紹了數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)理論和算法設(shè)計(jì)方法，對(duì)常用的數(shù)據(jù)結(jié)構(gòu)做了系統(tǒng)的介紹，并結(jié)合數(shù)據(jù)結(jié)構(gòu)的應(yīng)用以及算法性能評(píng)價(jià)等內(nèi)容，進(jìn)一步使讀者理解數(shù)據(jù)抽象與編程實(shí)現(xiàn)的關(guān)系，提高用計(jì)算機(jī)解決實(shí)際問題的能力。

編寫過程中特別考慮到了面向?qū)ο蟪绦蛟O(shè)計(jì)（OOP）的思想與Java語言的特性，在數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)上更好地運(yùn)用了Java語言，并且自始至終強(qiáng)調(diào)以面向?qū)ο蟮姆绞絹硭伎肌⒎治龊徒鉀Q問題。

本書注重理論聯(lián)系實(shí)際，注重基本知識(shí)的傳授與基本技能的培養(yǎng)。所有算法均使用Java語言實(shí)現(xiàn)，并通過測試運(yùn)行。本書還提供了豐富的教輔材料，內(nèi)容包括PPT、源代碼、課后上機(jī)實(shí)訓(xùn)、習(xí)題解答等，非常適合作為數(shù)據(jù)結(jié)構(gòu)的教學(xué)用書。

“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)專業(yè)的重要基礎(chǔ)課，是該專業(yè)的核心課程之一，它是一門集技術(shù)性、理論性和實(shí)踐性于一體的課程。Java是現(xiàn)今一種熱門的語言，本書在編寫過程中特別考慮到了面向?qū)ο蟪绦蛟O(shè)計(jì)（OOP）的思想與Java語言的特性。本書在數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)上更好地運(yùn)用了Java語言，并且自始至終強(qiáng)調(diào)以面向?qū)ο蟮姆绞絹硭伎肌⒎治龊徒鉀Q問題。

本書在編寫過程中特別考慮到了Java與對(duì)象，Java語言是完全面向?qū)ο蟮摹⒑唵胃咝А⑴c平臺(tái)無關(guān)、支持多線程、具有安全性和健壯性等特點(diǎn)，為教師和學(xué)生提供了一種精心設(shè)計(jì)并經(jīng)過教學(xué)檢驗(yàn)的方式，借助Java講授ADT和對(duì)象。本書教給學(xué)生如何使用線性表、詞典、棧、隊(duì)列等來組織數(shù)據(jù)。利用這些數(shù)據(jù)組織方式，學(xué)生們將學(xué)到算法設(shè)計(jì)的相關(guān)技術(shù)。

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

本書注重理論聯(lián)系實(shí)際，注重基本知識(shí)的傳授與基本技能的培養(yǎng)。本書還提供了豐富的教輔材料，內(nèi)容包括PPT、源代碼、課后上機(jī)實(shí)訓(xùn)、習(xí)題解答等，非常適合作為數(shù)據(jù)結(jié)構(gòu)的教學(xué)用書。

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

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

由于編寫時(shí)間緊張，編者水平有限，難免存在疏漏，敬請(qǐng)讀者批評(píng)指證。

編 者

2015年6月

序
前言

第1章 緒論 1
1.1 Java簡介 1
1.1.1 Java編程語言 1
1.1.2 Java虛擬機(jī) 2
1.2 數(shù)據(jù)結(jié)構(gòu)概述 2
1.2.1 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的必要性 2
1.2.2 什么是數(shù)據(jù)結(jié)構(gòu) 3
1.2.3 基本概念和術(shù)語 4
1.2.4 數(shù)據(jù)的邏輯結(jié)構(gòu) 5
1.2.5 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 7
1.3 算法的描述和算法分析 8
1.3.1 算法的描述 8
1.3.2 影響算法效率的因素 9
1.3.3 算法效率的評(píng)價(jià) 10
1.3.4 算法的存儲(chǔ)空間需求 12
本章小結(jié) 13
上機(jī)實(shí)訓(xùn) 14
習(xí)題 15
第2章 線性表 17
2.1 線性表的邏輯結(jié)構(gòu) 17
2.2 線性表的順序存儲(chǔ)結(jié)構(gòu) 19
2.2.1 線性表的順序存儲(chǔ)結(jié)構(gòu) 19
2.2.2 線性表在順序存儲(chǔ)結(jié)構(gòu)下的運(yùn)算 20
2.3 線性表的鏈?zhǔn)酱鎯?chǔ) 25
2.3.1 單向鏈表 25
2.3.2 循環(huán)鏈表 33
2.3.3 雙向鏈表 34
2.4 一元多項(xiàng)式的表示及相加 41
本章小結(jié) 47
上機(jī)實(shí)訓(xùn) 47
習(xí)題 48
第3章 棧和隊(duì)列 49
3.1 棧 49
3.1.1 棧的定義及其運(yùn)算 49
3.1.2 棧的順序存儲(chǔ)結(jié)構(gòu) 51
3.1.3 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 55
3.2 隊(duì)列 60
3.2.1 隊(duì)列的定義及其運(yùn)算 60
3.2.2 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu) 61
3.2.3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 71
本章小結(jié) 76
上機(jī)實(shí)訓(xùn) 76
習(xí)題 77
第4章 串 78
4.1 串的基本概念 78
4.1.1 串的定義 78
4.1.2 主串和子串 79
4.2 串的存儲(chǔ)結(jié)構(gòu) 79
4.3 串的基本運(yùn)算及其實(shí)現(xiàn) 80
4.3.1 字符串的基本運(yùn)算 80
4.3.2 串的基本運(yùn)算實(shí)現(xiàn) 83
4.4 文本編輯 89
本章小結(jié) 90
上機(jī)實(shí)訓(xùn) 91
習(xí)題 91
第5章 多維數(shù)組和廣義表 92
5.1 多維數(shù)組的概念 92
5.2 多維數(shù)組的存儲(chǔ)結(jié)構(gòu) 93
5.2.1 行優(yōu)先順序存儲(chǔ) 94
5.2.2 列優(yōu)先順序存儲(chǔ) 94
5.3 特殊矩陣及其壓縮存儲(chǔ) 95
5.3.1 特殊矩陣 95
5.3.2 壓縮存儲(chǔ) 97
5.4 稀疏矩陣 99
5.4.1 稀疏矩陣的存儲(chǔ) 99
5.4.2 稀疏矩陣的運(yùn)算 117
5.5 廣義表 123
5.5.1 廣義表的定義和性質(zhì) 123
5.5.2 廣義表的存儲(chǔ)結(jié)構(gòu) 124
5.5.3 廣義表的基本運(yùn)算 127
本章小結(jié) 136
上機(jī)實(shí)訓(xùn) 137
習(xí)題 137
第6章 樹 139
6.1 樹的結(jié)構(gòu)定義與基本操作 139
6.1.1 樹的定義 139
6.1.2 樹的存儲(chǔ)結(jié)構(gòu) 140
6.1.3 樹的廣義表表示 141
6.2 二叉樹 141
6.2.1 二叉樹的定義 141
6.2.2 二叉樹的性質(zhì) 142
6.2.3 二叉樹的存儲(chǔ)結(jié)構(gòu) 144
6.2.4 二叉樹類定義 145
6.2.5 樹與二叉樹的相互轉(zhuǎn)換 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 刪除二叉排序樹上的結(jié)點(diǎn) 165
6.6 哈夫曼樹和哈夫曼算法 165
6.6.1 哈夫曼樹的定義 165
6.6.2 構(gòu)造哈夫曼樹—哈夫曼算法 167
6.6.3 哈夫曼樹的應(yīng)用 168
本章小結(jié) 170
上機(jī)實(shí)訓(xùn) 171
習(xí)題 171
第7章 圖的基本知識(shí) 172
7.1 圖的基本知識(shí) 172
7.1.1 圖的定義 172
7.1.2 圖的相關(guān)術(shù)語 173
7.1.3 圖的基本操作 177
7.2 圖的存儲(chǔ)結(jié)構(gòu) 177
7.2.1 鄰接矩陣 177
7.2.2 鄰接表 179
7.3 圖的遍歷 180
7.3.1 深度優(yōu)先搜索遍歷 180
7.3.2 廣度優(yōu)先搜索遍歷 182
7.4 最小生成樹 187
7.5 最短路徑 197
7.5.1 單源點(diǎn)最短路徑 198
7.5.2 所有頂點(diǎn)對(duì)之間的最短路徑 204
7.6 拓?fù)渑判?211
本章小結(jié) 213
上機(jī)實(shí)訓(xùn) 213
習(xí)題 214
第8章 查找 216
8.1 查找的基本概念 216
8.2 靜態(tài)查找表 218
8.2.1 順序查找 218
8.2.2 折半查找 220
8.2.3 分塊查找 225
8.3 動(dòng)態(tài)查找表 226
8.4 哈希表 231
8.4.1 哈希表和哈希函數(shù)的定義 231
8.4.2 哈希函數(shù)的構(gòu)造方法 233
8.4.3 處理沖突的方法 235
本章小結(jié) 240
上機(jī)實(shí)訓(xùn) 240
習(xí)題 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 基數(shù)排序 263
9.8 外部排序 265
9.9 各種排序方法的比較 266
本章小結(jié) 269
上機(jī)實(shí)訓(xùn) 269
習(xí)題 269
參考文獻(xiàn) 271

1. 機(jī)械制圖 [許淑珍 于利民]
2. 微積分（經(jīng)管類）導(dǎo)學(xué)篇（下冊(cè)） [王海棠 曹海軍 周玲麗]
3. 大學(xué)生創(chuàng)新創(chuàng)業(yè)基礎(chǔ) [主編 姜國權(quán) 姜福佳]
4. 農(nóng)產(chǎn)品云倉模式研究—以北京農(nóng)產(chǎn)品流通物流供應(yīng)鏈重構(gòu)為例 [武曉釗 王成林 王春娟 等著]
5. 信息技術(shù)（微課版） [王云　徐江鴻　李清霞　羅學(xué)鋒　]
6. 管理基礎(chǔ)與實(shí)務(wù) [主編 王鳳基 顏漢軍]
7. 高等數(shù)學(xué)導(dǎo)學(xué)篇（下冊(cè)） [主編 李文婧 胡雷 尹金生]
8. 高等數(shù)學(xué)導(dǎo)學(xué)篇（上冊(cè)） [主編 李文婧 胡雷 尹金生]
9. 高等數(shù)學(xué)（下冊(cè)） [主編 李愛芹 胡雷 尹金生]
10. 高等數(shù)學(xué)（上冊(cè)） [主編 李愛芹 胡雷 尹金生]
11. 庭院風(fēng)骨—樹、灌、籬 [創(chuàng)意房主 著]
12. Python語言程序設(shè)計(jì)教程 [郭其標(biāo) 房宜汕]
13. 微積分（經(jīng)管類）教程篇（下冊(cè)） [曹海軍 王海棠 周玲麗]
14. 微積分（經(jīng)管類）教程篇（上冊(cè)） [曹海軍 王海棠 周玲麗]
15. 微積分（經(jīng)管類）導(dǎo)學(xué)篇（上冊(cè)） [王海棠 曹海軍 周玲麗]
16. 網(wǎng)站前端技術(shù)案例教程（HTML+CSS+JavaScript）（第二版） [黃華升]
17. 線性代數(shù) [主編 史昱 陳鳳欣]
18. 電力電子技術(shù)課程學(xué)習(xí)及實(shí)驗(yàn)指導(dǎo) [主編 陳榮]
19. 成長對(duì)話：青春的榜樣 [主編　施端銀　黃武剛　應(yīng)巨林]
20. 人工智能應(yīng)用基礎(chǔ) [主編 楊纓 李佳]
21. 中華水文化（慕課版）（第二版） [畢雪燕 楊華軻 羅玲誼 等編著]
22. 電路與電子技術(shù)Ⅱ——電路分析基礎(chǔ) [主編 陳曉 金哲]
23. 飛機(jī)維修專業(yè)英語——飛機(jī)系統(tǒng)（第二版） [趙迎春]
24. 英語大爆炸：跟趣味情景劇學(xué)口語（微課版） [秦然　編著]
25. 機(jī)械工程制圖任務(wù)跟蹤訓(xùn)練 [主編 王瑞清 趙金考 周彥云 ]
26. 機(jī)械工程制圖 [主編 覃國萍 劉百順 禹晨]
27. 平面設(shè)計(jì)與制作項(xiàng)目化教程 [主編　李晨]
28. 后期影像剪輯技術(shù) [主編　郭建偉]
29. 人工智能概論（第二版） [主編　任云暉　丁紅　徐迎春 ]
30. 信息時(shí)代美育之道 [主編　劉宏宇　黎婭]