數(shù)據(jù)結(jié)構(gòu)和算法基礎(chǔ)（Java語言實(shí)現(xiàn)）

第1章　緒論 1
1.1　引言 2
1.1.1　數(shù)據(jù)結(jié)構(gòu)概述 2
1.1.2　什么是算法 5
1.1.3　算法的描述 5
1.2　程序的性能 9
1.2.1　程序的性能 9
1.2.2　程序的性能 10
1.3　漸近記法 12
1.3.1　大O標(biāo)記法 12
1.3.2　大Ω標(biāo)記法 12
1.3.3　大Θ標(biāo)記法 13
1.3.4　漸近記法總結(jié) 13
1.4　算法復(fù)雜度等級(jí)及其分析 13
1.4.1　常數(shù)的時(shí)間復(fù)雜度O(1) 14
1.4.2　對(duì)數(shù)的時(shí)間復(fù)雜度O(logn) 14
1.4.3　線性的時(shí)間復(fù)雜度O(n) 15
1.4.4　平方的時(shí)間復(fù)雜度O(n2) 16
1.4.5　指數(shù)的時(shí)間復(fù)雜度O(2n) 16
1.4.6　算法復(fù)雜度總結(jié) 17
1.5　總結(jié) 17
1.6　習(xí)題 18
第2章　開發(fā)環(huán)境搭建及測(cè)試 19
2.1　安裝JDK 20
2.1.1　解壓.zip文件到指定位置 20
2.1.2　設(shè)置環(huán)境變量 20
2.1.3　驗(yàn)證安裝 21
2.2　安裝Maven 22
2.2.1　安裝 22
2.2.2　設(shè)置本地倉(cāng)庫(kù) 22
2.2.3　設(shè)置鏡像 23
2.3　安裝IDE 23
2.3.1　解壓.zip文件到指定位置 23
2.3.2　配置工作區(qū)間 24
2.3.3　配置JDK 24
2.3.4　配置Maven 24
2.3.5　設(shè)置字符編碼 26
2.4　實(shí)戰(zhàn)：編寫單元測(cè)試用例 26
2.4.1　創(chuàng)建HelloWorld類 26
2.4.2　使用JUnit5 27
2.4.3　編寫JUnit5測(cè)試用例 27
2.5　總結(jié) 29
2.6　習(xí)題 29
第3章　順序表 30
3.1　Java數(shù)組初探 31
3.2　線性表數(shù)據(jù)結(jié)構(gòu) 32
3.3　實(shí)戰(zhàn)：使用數(shù)組實(shí)現(xiàn)順序表
　　　SequentialList 37
3.4　順序表的動(dòng)態(tài)擴(kuò)容 47
3.4.1　順序表的動(dòng)態(tài)擴(kuò)容原理 47
3.4.2　動(dòng)態(tài)擴(kuò)容機(jī)制的選擇 48
3.4.3　ArrayList動(dòng)態(tài)擴(kuò)容分析 49
3.4.4　Vector動(dòng)態(tài)擴(kuò)容分析 50
3.4.5　選擇ArrayList還是Vector 52
3.5　總結(jié) 52
3.6　習(xí)題 52
第4章　鏈表 53
第5章　數(shù)組和矩陣 93
第6章　棧 114
6.1　基本概念及應(yīng)用場(chǎng)景 115
6.1.1　棧的基本概念 115
6.1.2　棧的應(yīng)用場(chǎng)景 115
6.2　抽象數(shù)據(jù)類型 117
6.3　數(shù)組描述 117
6.4　實(shí)戰(zhàn)：使用數(shù)組實(shí)現(xiàn)棧
　　　SequentialListStack 117
6.4.1　成員變量及構(gòu)造函數(shù) 117
6.4.2　統(tǒng)計(jì)棧的規(guī)模 118
6.4.3　判斷棧中的數(shù)據(jù)元素是否為空 118
6.4.4　入棧 118
6.4.5　出棧 119
6.4.6　引用棧頂對(duì)象 119
6.4.7　時(shí)間復(fù)雜度分析總結(jié) 119
6.4.8　單元測(cè)試 119
6.5　鏈表描述 121
6.6　實(shí)戰(zhàn)：使用鏈表實(shí)現(xiàn)棧
　　　SinglyLinkedListStack 122
6.6.1　成員變量及構(gòu)造函數(shù) 122
6.6.2　統(tǒng)計(jì)棧的規(guī)模 122
6.6.3　判斷棧中的數(shù)據(jù)元素是否為空 122
6.6.4　入棧 123
6.6.5　出棧 123
6.6.6　引用棧頂對(duì)象 123
6.6.7　時(shí)間復(fù)雜度分析總結(jié) 123
6.6.8　單元測(cè)試 123
6.7　總結(jié) 125
6.8　習(xí)題 125
第7章　隊(duì)列 126
第8章　跳表和散列 183
8.1　字典 184
8.1.1　跳表 184
8.1.2　散列 185
8.2　抽象數(shù)據(jù)類型 186
8.2.1　Dictionary抽象類 186
8.2.2　Map接口 187
8.2.3　Dictionary抽象類和Map接口
　　　的抉擇 194
8.3　散列HashMap 194
8.3.1　HashMap的聲明 195
8.3.2　HashMap的成員變量和構(gòu)造
　　　函數(shù) 201
8.3.3　HashMap的核心方法 203
8.3.4　實(shí)戰(zhàn)：HashMap的單元測(cè)試 210
8.3.5　實(shí)戰(zhàn)：HashMap的應(yīng)用案例
　　　——詞頻統(tǒng)計(jì) 214

8.4　基于跳表實(shí)現(xiàn)的
　　　ConcurrentSkipListMap 216
8.4.1　ConcurrentSkipListMap的聲明 216
8.4.2　ConcurrentSkipListMap的成員
　　　變量和構(gòu)造函數(shù) 217
8.4.3　ConcurrentSkipListMap的核心
　　　方法 219
8.4.4　實(shí)戰(zhàn)：ConcurrentSkipListMap
　　　的單元測(cè)試 232
8.4.5　實(shí)戰(zhàn)：ConcurrentSkipListMap
　　　的應(yīng)用案例——詞頻統(tǒng)計(jì) 235
8.5　實(shí)戰(zhàn)：文本壓縮 237
8.5.1　文本的壓縮和解壓 238
8.5.2　文本的壓縮和解壓的實(shí)現(xiàn) 238
8.5.3　測(cè)試文本的壓縮和解壓 240
8.6　總結(jié) 242
8.7　習(xí)題 243
第9章　樹及二叉樹 244
9.10　習(xí)題 272
第10章　優(yōu)先級(jí)隊(duì)列及堆 273
10.1　基本概念及應(yīng)用場(chǎng)景 274
10.2　抽象數(shù)據(jù)類型 274
10.3　數(shù)組描述 274
10.4　實(shí)戰(zhàn)：使用數(shù)組實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 275
10.4.1　定義實(shí)現(xiàn)類 275
10.4.2　實(shí)現(xiàn)插入 276
10.4.3　實(shí)現(xiàn)刪除 278
10.4.4　單元測(cè)試 279
10.5　堆描述 282
10.5.1　堆的定義 283
10.5.2　堆和普通樹的區(qū)別 283
10.5.3　堆的存儲(chǔ) 284
10.5.4　堆的常用操作 284
10.6　實(shí)戰(zhàn)：使用堆實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列 285
10.6.1　定義實(shí)現(xiàn)類 286
10.6.2　實(shí)現(xiàn)插入 287
10.6.3　實(shí)現(xiàn)刪除 289
10.6.4　單元測(cè)試 291
10.7　總結(jié) 293
10.8　習(xí)題 294
第11章　二叉查找樹 295
第12章　平衡查找樹 311
第13章　圖 361
第14章　分而治之 438
第15章　貪心算法 461
第16章　動(dòng)態(tài)規(guī)劃 473
第17章　回溯 490
第18章　遺傳算法 502
第19章　螞蟻算法 528
第20章　漢諾塔游戲 555
20.1　實(shí)戰(zhàn)：漢諾塔問題 556
參考文獻(xiàn) 582