123,123,123

內(nèi)容簡(jiǎn)介

　　本書按照循序漸進(jìn)的順序講解了多種常見(jiàn)數(shù)據(jù)結(jié)構(gòu)的相關(guān)定義、實(shí)現(xiàn)方式及應(yīng)用場(chǎng)景，并通過(guò)提供配套代碼、研讀Java源碼的方式，讓讀者能夠通過(guò)體會(huì)代碼實(shí)現(xiàn)細(xì)節(jié)的方式加深對(duì)各種常見(jiàn)數(shù)據(jù)結(jié)構(gòu)從理論定義到實(shí)踐落地過(guò)程的理解。本書除了闡述各種常見(jiàn)數(shù)據(jù)結(jié)構(gòu)的基本定義外，還引申的講解了常見(jiàn)數(shù)據(jù)結(jié)構(gòu)內(nèi)部隱含的特點(diǎn)，使讀者能夠更加全面地了解各種常見(jiàn)數(shù)據(jù)結(jié)構(gòu)的特征和優(yōu)缺點(diǎn)。本書共9章。第1章對(duì)數(shù)據(jù)結(jié)構(gòu)時(shí)間、空間效能的評(píng)判標(biāo)準(zhǔn)進(jìn)行講解。第2章對(duì)數(shù)組和鏈表及其引申結(jié)構(gòu)進(jìn)行講解。第3章對(duì)棧和隊(duì)列兩種基于數(shù)組和鏈表的邏輯結(jié)構(gòu)講解。第4章對(duì)常見(jiàn)的搜索、排序算法進(jìn)行講解。第5章對(duì)字符串結(jié)構(gòu)及字符串匹配算法進(jìn)行講解。第6章對(duì)多種常見(jiàn)樹(shù)形結(jié)構(gòu)及相關(guān)算法進(jìn)行講解。第7章對(duì)堆結(jié)構(gòu)進(jìn)行講解。第8章對(duì)散列表結(jié)構(gòu)進(jìn)行講解。第9章對(duì)圖結(jié)構(gòu)及其常見(jiàn)算法進(jìn)行講解。本書既適合具有一定Java語(yǔ)言基礎(chǔ)的高校學(xué)生作為學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)、研究其實(shí)現(xiàn)原理的參考書籍，也對(duì)具有一定工作經(jīng)驗(yàn)、需要對(duì)不同數(shù)據(jù)結(jié)構(gòu)之間差異性、內(nèi)在特征進(jìn)行研究的人群均有一定參考價(jià)值。

作者簡(jiǎn)介

　　塔拉，國(guó)家認(rèn)證的軟件開(kāi)發(fā)工程師、Oracle認(rèn)證的Java開(kāi)發(fā)工程師。畢業(yè)于黑龍江大學(xué)計(jì)算機(jī)科學(xué)技術(shù)專業(yè)，畢業(yè)后從事軟件研發(fā)工作，并于2016年正式進(jìn)入IT教育行業(yè)。從業(yè)期間曾在多家IT教育機(jī)構(gòu)及高校從事講師、課程研發(fā)工作，至今已授業(yè)數(shù)百名學(xué)員，積累了豐富的教育教學(xué)經(jīng)驗(yàn)，對(duì)IT行業(yè)教學(xué)內(nèi)容及教育體系有深入了解。從事IT教育行業(yè)過(guò)程中，作者堅(jiān)持研究各種應(yīng)用底層原理與編程思想，在數(shù)據(jù)結(jié)構(gòu)、通用型算法及設(shè)計(jì)模式等方面有所心得。

圖書目錄

第1章緒論1
1.1時(shí)間復(fù)雜度1
1.2空間復(fù)雜度2
第2章數(shù)組與鏈表3
2.1數(shù)組結(jié)構(gòu)4
2.1.1數(shù)組的創(chuàng)建與基本操作4
2.1.2數(shù)組內(nèi)存特性分析7
2.1.3內(nèi)存中的多維數(shù)組13
2.2鏈表結(jié)構(gòu)17
2.2.1基本概念普及17
2.2.2鏈表內(nèi)存特性分析19
2.2.3鏈表衍生結(jié)構(gòu)27
第3章棧和隊(duì)列54
3.1棧結(jié)構(gòu)55
3.1.1棧結(jié)構(gòu)概述55
3.1.2棧結(jié)構(gòu)的實(shí)現(xiàn)55
3.1.3棧結(jié)構(gòu)的應(yīng)用場(chǎng)景56
3.2隊(duì)列結(jié)構(gòu)63
3.2.1隊(duì)列結(jié)構(gòu)概述63
3.2.2隊(duì)列結(jié)構(gòu)的實(shí)現(xiàn)64
3.2.3隊(duì)列結(jié)構(gòu)的應(yīng)用場(chǎng)景65
3.2.4隊(duì)列結(jié)構(gòu)的衍生68
第4章遞歸、查找與排序73
4.1遞歸73
4.1.1簡(jiǎn)單的遞歸案例74
4.1.2遞歸結(jié)構(gòu)基礎(chǔ)75
4.1.3遞歸結(jié)構(gòu)進(jìn)階78
4.2查找79
4.2.1二分查找79
4.2.2插值查找84
4.2.3斐波那契查找89
4.3排序96
4.3.1排序算法的穩(wěn)定性96
4.3.2冒泡排序97
4.3.3選擇排序101
4.3.4插入排序105
4.3.5希爾排序110
4.3.6歸并排序115
4.3.7快速排序123
4.3.8堆排序131
4.3.9計(jì)數(shù)排序141
4.3.10桶排序147
第5章字符串152
5.1基本概念與實(shí)現(xiàn)152
5.1.1字符串的基本概念152
5.1.2Java中的String類153
5.2字符串匹配算法156
5.2.1通用定義156
5.2.2BF算法156
5.2.3RK算法161
5.2.4KMP算法168
5.2.5BM算法183
5.2.6Sunday算法196
第6章樹(shù)結(jié)構(gòu)203
6.1樹(shù)結(jié)構(gòu)基礎(chǔ)204
6.1.1樹(shù)的基礎(chǔ)概念204
6.1.2樹(shù)的遍歷操作206
6.2二叉樹(shù)216
6.2.1二叉樹(shù)的定義216
6.2.2二叉樹(shù)的基本性質(zhì)217
6.2.3滿二叉樹(shù)和完全二叉樹(shù)217
6.2.4二叉樹(shù)的遍歷操作219
6.2.5通過(guò)深度優(yōu)先遍歷序列構(gòu)建二叉樹(shù)230
6.2.6樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換238
6.3哈夫曼樹(shù)與哈夫曼編碼譯碼器248
6.3.1哈夫曼樹(shù)的構(gòu)建248
6.3.2獲取明文字符的哈夫曼編碼249
6.3.3文本編碼與譯碼250
6.4線索二叉樹(shù)與Morris遍歷250
6.4.1線索二叉樹(shù)的節(jié)點(diǎn)定義方式251
6.4.2二叉樹(shù)的線索化251
6.4.3線索二叉樹(shù)的遍歷261
6.4.4二叉樹(shù)的Morris遍歷274
6.5二叉排序樹(shù)286
6.5.1二叉排序樹(shù)的結(jié)構(gòu)特點(diǎn)286
6.5.2二叉排序樹(shù)的增刪查找287
6.5.3二叉排序樹(shù)退化為單鏈表的情況295
6.6平衡二叉樹(shù)（AVL樹(shù)）296
6.6.1AVL樹(shù)節(jié)點(diǎn)的旋轉(zhuǎn)方式296
6.6.2節(jié)點(diǎn)增刪導(dǎo)致不平衡的情況304
6.6.3AVL樹(shù)與平衡二叉樹(shù)的對(duì)比307
6.7234樹(shù)308
6.7.1234樹(shù)的結(jié)構(gòu)特點(diǎn)308
6.7.2234樹(shù)的增刪查找310
6.8紅黑樹(shù)318
6.8.1紅黑樹(shù)的平衡策略與染色規(guī)則318
6.8.2234樹(shù)向紅黑樹(shù)的轉(zhuǎn)換319
6.8.3紅黑樹(shù)的節(jié)點(diǎn)增刪與結(jié)構(gòu)調(diào)整323
6.9B樹(shù)與B 樹(shù)338
6.9.1B樹(shù)結(jié)構(gòu)338
6.9.2B 樹(shù)結(jié)構(gòu)339
6.9.3B樹(shù)與B 樹(shù)在實(shí)際應(yīng)用方面的區(qū)別341
6.10字典樹(shù)（Trie樹(shù)）344
6.10.1字典樹(shù)的結(jié)構(gòu)特點(diǎn)344
6.10.2字典樹(shù)的基本功能與實(shí)現(xiàn)方式346
6.10.3字典樹(shù)的時(shí)間復(fù)雜度與空間復(fù)雜度357
6.11樹(shù)狀數(shù)組358
6.11.1前置知識(shí): 非負(fù)整數(shù)的lowBit操作358
6.11.2樹(shù)狀數(shù)組的構(gòu)建方式359
6.11.3樹(shù)狀數(shù)組的基本操作364
6.11.4差分?jǐn)?shù)組與基本操作367
第7章堆結(jié)構(gòu)378
7.1堆結(jié)構(gòu)基礎(chǔ)379
7.2二叉堆380
7.2.1二叉堆的存儲(chǔ)方式與特性380
7.2.2二叉堆的元素添加操作381
7.2.3二叉堆的堆頂元素刪除操作383
7.2.4二叉堆與TopK問(wèn)題386
7.3左式堆與斜堆387
7.3.1左式堆388
7.3.2斜堆395
7.4二項(xiàng)堆401
7.4.1二項(xiàng)樹(shù)結(jié)構(gòu)401
7.4.2二項(xiàng)堆的結(jié)構(gòu)特點(diǎn)404
7.4.3二項(xiàng)堆的合并操作405
7.4.4二項(xiàng)堆的元素添加操作409
7.4.5二項(xiàng)堆的堆頂元素刪除操作412
第8章散列表416
8.1散列表的基本概念417
8.2散列函數(shù)的常見(jiàn)實(shí)現(xiàn)方式420
8.2.1前置知識(shí): 整數(shù)的模運(yùn)算421
8.2.2直接定址法425
8.2.3除留余數(shù)法425
8.2.4數(shù)字分析法426
8.2.5平方取中法427
8.2.6折疊法427
8.2.7隨機(jī)數(shù)法428
8.2.8全域散列法428
8.3散列表常見(jiàn)實(shí)現(xiàn)方式429
8.3.1開(kāi)放地址法實(shí)現(xiàn)散列表430
8.3.2鏈地址法實(shí)現(xiàn)散列表434
8.3.3完全散列的實(shí)現(xiàn)434
8.4散列表的平均查找長(zhǎng)度437
8.5Java中的散列表440
8.5.1Java中的hashCode()與equals()方法440
8.5.2HashMap類與HashSet類443
第9章圖結(jié)構(gòu)448
9.1圖結(jié)構(gòu)基礎(chǔ)449
9.1.1圖的基礎(chǔ)概念449
9.1.2圖的表示方式453
9.1.3圖的遍歷操作456
9.2無(wú)向帶權(quán)圖的最小生成樹(shù)問(wèn)題461
9.2.1普里姆算法462
9.2.2克魯斯卡爾算法465
9.2.3普里姆算法與克魯斯卡爾算法的比較468
9.3有向帶權(quán)圖的最短路徑問(wèn)題469
9.3.1迪杰斯特拉算法求解有向帶權(quán)圖的單源最短路徑469
9.3.2弗洛伊德算法求解有向帶權(quán)圖的多源最短路徑473
9.4AOV網(wǎng)和拓?fù)渑判騿?wèn)題479
9.5AOE網(wǎng)和關(guān)鍵路徑問(wèn)題484
參考文獻(xiàn)489