數(shù)據(jù)結(jié)構(gòu)和算法基礎(chǔ)（Java語言實現(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標記法 12
1.3.2　大Ω標記法 12
1.3.3　大Θ標記法 13
1.3.4　漸近記法總結(jié) 13
1.4　算法復(fù)雜度等級及其分析 13
1.4.1　常數(shù)的時間復(fù)雜度O(1) 14
1.4.2　對數(shù)的時間復(fù)雜度O(logn) 14
1.4.3　線性的時間復(fù)雜度O(n) 15
1.4.4　平方的時間復(fù)雜度O(n2) 16
1.4.5　指數(shù)的時間復(fù)雜度O(2n) 16
1.4.6　算法復(fù)雜度總結(jié) 17
1.5　總結(jié) 17
1.6　習(xí)題 18
第2章　開發(fā)環(huán)境搭建及測試 19
2.1　安裝JDK 20
2.1.1　解壓.zip文件到指定位置 20
2.1.2　設(shè)置環(huán)境變量 20
2.1.3　驗證安裝 21
2.2　安裝Maven 22
2.2.1　安裝 22
2.2.2　設(shè)置本地倉庫 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　實戰(zhàn)：編寫單元測試用例 26
2.4.1　創(chuàng)建HelloWorld類 26
2.4.2　使用JUnit5 27
2.4.3　編寫JUnit5測試用例 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　實戰(zhàn)：使用數(shù)組實現(xiàn)順序表
　　　SequentialList 37
3.4　順序表的動態(tài)擴容 47
3.4.1　順序表的動態(tài)擴容原理 47
3.4.2　動態(tài)擴容機制的選擇 48
3.4.3　ArrayList動態(tài)擴容分析 49
3.4.4　Vector動態(tài)擴容分析 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)用場景 115
6.1.1　棧的基本概念 115
6.1.2　棧的應(yīng)用場景 115
6.2　抽象數(shù)據(jù)類型 117
6.3　數(shù)組描述 117
6.4　實戰(zhàn)：使用數(shù)組實現(xiàn)棧
　　　SequentialListStack 117
6.4.1　成員變量及構(gòu)造函數(shù) 117
6.4.2　統(tǒng)計棧的規(guī)模 118
6.4.3　判斷棧中的數(shù)據(jù)元素是否為空 118
6.4.4　入棧 118
6.4.5　出棧 119
6.4.6　引用棧頂對象 119
6.4.7　時間復(fù)雜度分析總結(jié) 119
6.4.8　單元測試 119
6.5　鏈表描述 121
6.6　實戰(zhàn)：使用鏈表實現(xiàn)棧
　　　SinglyLinkedListStack 122
6.6.1　成員變量及構(gòu)造函數(shù) 122
6.6.2　統(tǒng)計棧的規(guī)模 122
6.6.3　判斷棧中的數(shù)據(jù)元素是否為空 122
6.6.4　入棧 123
6.6.5　出棧 123
6.6.6　引用棧頂對象 123
6.6.7　時間復(fù)雜度分析總結(jié) 123
6.6.8　單元測試 123
6.7　總結(jié) 125
6.8　習(xí)題 125
第7章　隊列 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　實戰(zhàn)：HashMap的單元測試 210
8.3.5　實戰(zhàn)：HashMap的應(yīng)用案例
　　　——詞頻統(tǒng)計 214

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