全面系統(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í)際問(wèn)題的能力。

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

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

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

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

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

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

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

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

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

編 者

2015年6月

序
前言

第1章 緒論 1
1.1 Java簡(jiǎn)介 1
1.1.1 Java編程語(yǔ)言 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ù)語(yǔ) 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章 樹(shù) 139
6.1 樹(shù)的結(jié)構(gòu)定義與基本操作 139
6.1.1 樹(shù)的定義 139
6.1.2 樹(shù)的存儲(chǔ)結(jié)構(gòu) 140
6.1.3 樹(shù)的廣義表表示 141
6.2 二叉樹(shù) 141
6.2.1 二叉樹(shù)的定義 141
6.2.2 二叉樹(shù)的性質(zhì) 142
6.2.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 144
6.2.4 二叉樹(shù)類(lèi)定義 145
6.2.5 樹(shù)與二叉樹(shù)的相互轉(zhuǎn)換 146
6.3 二叉樹(shù)的遍歷 147
6.3.1 先序（根）遍歷 148
6.3.2 中序（根）遍歷 148
6.3.3 后序（根）遍歷 149
6.3.4 層次遍歷 149
6.4 線索二叉樹(shù) 153
6.4.1 線索二叉樹(shù)的定義 154
6.4.2 中序線索二叉樹(shù) 159
6.5 二叉排序樹(shù) 163
6.5.1 二叉排序樹(shù)的定義 163
6.5.2 二叉排序樹(shù)的生成 164
6.5.3 刪除二叉排序樹(shù)上的結(jié)點(diǎn) 165
6.6 哈夫曼樹(shù)和哈夫曼算法 165
6.6.1 哈夫曼樹(shù)的定義 165
6.6.2 構(gòu)造哈夫曼樹(shù)—哈夫曼算法 167
6.6.3 哈夫曼樹(shù)的應(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ù)語(yǔ) 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 最小生成樹(shù) 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. 零基礎(chǔ)玩轉(zhuǎn)國(guó)產(chǎn)大模型DeepSeek [徐永冰 張帥 編著]
2. 網(wǎng)絡(luò)工程師5天修煉（適配第6版考綱） [主編　朱小平 施游]
3. 信息系統(tǒng)項(xiàng)目管理師考試32小時(shí)通關(guān)（適用第4版考綱） [薛大龍]
4. 信息系統(tǒng)管理工程師考試32小時(shí)通關(guān)（適配第2版考綱） [薛大龍　劉偉]
5. 土木工程材料檢測(cè)實(shí)訓(xùn) [洪曉江 達(dá)則曉麗 錢(qián)波]
6. 科技信息檢索與論文寫(xiě)作實(shí)用教程 [李振華]
7. 傳統(tǒng)山水畫(huà)論解讀與實(shí)踐 [陳鈉 著]
8. Python數(shù)據(jù)庫(kù)編程 [主編 殷樹(shù)友 邢 翀]
9. 計(jì)算機(jī)基礎(chǔ)實(shí)訓(xùn)指導(dǎo) [主編 袁春萍 朱妮]
10. 嵌入式人工智能技術(shù)應(yīng)用（數(shù)字教材） [主編 胡娜 楊國(guó)勇 晏廷榮]
11. Vienna整流器技術(shù) [桂存兵 著]
12. 變頻器與伺服應(yīng)用 [陳剛 葉云飛]
13. 物聯(lián)網(wǎng)工程設(shè)計(jì)與實(shí)踐 [湯琳 李敏]
14. 爐邊夜話——深入淺出話AI [汪建　著]
15. 電商運(yùn)營(yíng)與管理 [鐘肖英 陳瀟]
16. Java面向?qū)ο蟪绦蛟O(shè)計(jì) [主編 姜春磊 陳虹潔]
17. 信息技術(shù)基礎(chǔ)（Windows 10+WPS Office）（微課版） [主編　石利平　田輝平　謝盛嘉]
18. 人工智能應(yīng)用 [主編　陳　萍　劉培培　陳孟軍]
19. 大學(xué)生職業(yè)發(fā)展與就業(yè)指導(dǎo) [主編　劉志堅(jiān)]
20. 高級(jí)辦公應(yīng)用項(xiàng)目教程 [主編 屈晶 趙成麗]
21. 微信小程序開(kāi)發(fā)項(xiàng)目實(shí)戰(zhàn)（微課版） [主編 黃龍泉 郭峰 朱倩]
22. 企業(yè)檔案工作實(shí)戰(zhàn)寶典百問(wèn)百答 [華俊 盧秀英 邵甜甜 著]
23. 計(jì)算機(jī)網(wǎng)絡(luò)原理及應(yīng)用 [主編 唐繼勇 葉坤 孫夢(mèng)娜]
24. 大學(xué)生創(chuàng)業(yè)基礎(chǔ) [主編 王麗莉 王 楊]
25. 船舶輔機(jī) [主編 王連海 于洋 姜淑翠]
26. 大學(xué)生就業(yè)指導(dǎo) [主編 王麗莉 董宴廷]
27. 系統(tǒng)架構(gòu)設(shè)計(jì)師章節(jié)習(xí)題與考點(diǎn)特訓(xùn) [主編 薛大龍 鄒月平]
28. 高校學(xué)生工作探索與實(shí)踐 [郭亮 著]
29. 大學(xué)生情商管理 [方雄 著]
30. 2023年長(zhǎng)沙市會(huì)展業(yè)發(fā)展報(bào)告 [主編 周棟良]