精講數據結構（Java語言實現）
塔拉
商品描述
"本書按照循序漸進的順序講解了多種常見數據結構的相關定義、實現方式及應用場景，並通過提供配套代碼、研讀Java源碼的方式，讓讀者能夠通過體會代碼實現細節的方式加深對各種常見數據結構從理論定義到實踐落地過程的理解。本書除了闡述各種常見數據結構的基本定義外，還引申的講解了常見數據結構內部隱含的特點，使讀者能夠更加全面地瞭解各種常見數據結構的特徵和優缺點。 本書共9章。第1章對數據結構時間、空間效能的評判標準進行講解。第2章對數組和鏈表及其引申結構進行講解。第3章對棧和隊列兩種基於數組和鏈表的邏輯結構講解。第4章對常見的搜索、排序算法進行講解。第5章對字符串結構及字符串匹配算法進行講解。第6章對多種常見樹形結構及相關算法進行講解。第7章對堆結構進行講解。第8章對散列表結構進行講解。第9章對圖結構及其常見算法進行講解。 本書既適合具有一定Java語言基礎的高校學生作為學習數據結構、研究其實現原理的參考書籍，也對具有一定工作經驗、需要對不同數據結構之間差異性、內在特徵進行研究的人群均有一定參考價值。 "
作者簡介
塔拉，國家認證的軟件開發工程師、Oracle認證的Java開發工程師。畢業於黑龍江大學計算機科學技術專業，畢業後從事軟件研發工作，並於2016年正式進入IT教育行業。從業期間曾在多家IT教育機構及高校從事講師、課程研發工作，至今已授業數百名學員，積累了豐富的教育教學經驗，對IT行業教學內容及教育體系有深入瞭解。從事IT教育行業過程中，作者堅持研究各種應用底層原理與編程思想，在數據結構、通用型算法及設計模式等方面有所心得。
目錄大綱
目錄
第1章緒論1
1.1時間復雜度1
1.2空間復雜度2
第2章數組與鏈表3
2.1數組結構4
2.1.1數組的創建與基本操作4
2.1.2數組內存特性分析7
2.1.3內存中的多維數組13
2.2鏈表結構17
2.2.1基本概念普及17
2.2.2鏈表內存特性分析19
2.2.3鏈表衍生結構27
第3章棧和隊列54
3.1棧結構55
3.1.1棧結構概述55
3.1.2棧結構的實現55
3.1.3棧結構的應用場景56
3.2隊列結構63
3.2.1隊列結構概述63
3.2.2隊列結構的實現64
3.2.3隊列結構的應用場景65
3.2.4隊列結構的衍生68
第4章遞歸、查找與排序73
4.1遞歸73
4.1.1簡單的遞歸案例74
4.1.2遞歸結構基礎75
4.1.3遞歸結構進階78
4.2查找79
4.2.1二分查找79
4.2.2插值查找84
4.2.3斐波那契查找89
4.3排序96
4.3.1排序算法的穩定性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計數排序141
4.3.10桶排序147
第5章字符串152
5.1基本概念與實現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章樹結構203
6.1樹結構基礎204
6.1.1樹的基礎概念204
6.1.2樹的遍歷操作206
6.2二叉樹216
6.2.1二叉樹的定義216
6.2.2二叉樹的基本性質217
6.2.3滿二叉樹和完全二叉樹217
6.2.4二叉樹的遍歷操作219
6.2.5通過深度優先遍歷序列構建二叉樹230
6.2.6樹、森林與二叉樹的轉換238
6.3哈夫曼樹與哈夫曼編碼解碼器248
6.3.1哈夫曼樹的構建248
6.3.2獲取明文字符的哈夫曼編碼249
6.3.3文本編碼與解碼250
6.4線索二叉樹與Morris遍歷250
6.4.1線索二叉樹的節點定義方式251
6.4.2二叉樹的線索化251
6.4.3線索二叉樹的遍歷261
6.4.4二叉樹的Morris遍歷274
6.5二叉排序樹286
6.5.1二叉排序樹的結構特點286
6.5.2二叉排序樹的增刪查找287
6.5.3二叉排序樹退化為單鏈表的情況295
6.6平衡二叉樹（AVL樹）296
6.6.1AVL樹節點的旋轉方式296
6.6.2節點增刪導致不平衡的情況304
6.6.3AVL樹與平衡二叉樹的對比307
6.7234樹308
6.7.1234樹的結構特點308
6.7.2234樹的增刪查找310
6.8紅黑樹318
6.8.1紅黑樹的平衡策略與染色規則318
6.8.2234樹向紅黑樹的轉換319
6.8.3紅黑樹的節點增刪與結構調整323
6.9B樹與B+樹338
6.9.1B樹結構338
6.9.2B+樹結構339
6.9.3B樹與B+樹在實際應用方面的區別341
6.10字典樹（Trie樹）344
6.10.1字典樹的結構特點344
6.10.2字典樹的基本功能與實現方式346
6.10.3字典樹的時間復雜度與空間復雜度357
6.11樹狀數組358
6.11.1前置知識: 非負整數的lowBit操作358
6.11.2樹狀數組的構建方式359
6.11.3樹狀數組的基本操作364
6.11.4差分數組與基本操作367
第7章堆結構378
7.1堆結構基礎379
7.2二叉堆380
7.2.1二叉堆的存儲方式與特性380
7.2.2二叉堆的元素添加操作381
7.2.3二叉堆的堆頂元素刪除操作383
7.2.4二叉堆與TopK問題386
7.3左式堆與斜堆387
7.3.1左式堆388
7.3.2斜堆395
7.4二項堆401
7.4.1二項樹結構401
7.4.2二項堆的結構特點404
7.4.3二項堆的合並操作405
7.4.4二項堆的元素添加操作409
7.4.5二項堆的堆頂元素刪除操作412
第8章散列表416
8.1散列表的基本概念417
8.2散列函數的常見實現方式420
8.2.1前置知識: 整數的模運算421
8.2.2直接尋址法425
8.2.3除留餘數法425
8.2.4數字分析法426
8.2.5平方取中法427
8.2.6折疊法427
8.2.7隨機數法428
8.2.8全域散列法428
8.3散列表常見實現方式429
8.3.1開放地址法實現散列表430
8.3.2鏈地址法實現散列表434
8.3.3完全散列的實現434
8.4散列表的平均查找長度437
8.5Java中的散列表440
8.5.1Java中的hashCode()與equals()方法440
8.5.2HashMap類與HashSet類443
第9章圖結構448
9.1圖結構基礎449
9.1.1圖的基礎概念449
9.1.2圖的表示方式453
9.1.3圖的遍歷操作456
9.2無向帶權圖的最小生成樹問題461
9.2.1普里姆算法462
9.2.2克魯斯卡爾算法465
9.2.3普里姆算法與克魯斯卡爾算法的比較468
9.3有向帶權圖的最短路徑問題469
9.3.1迪傑斯特拉算法求解有向帶權圖的單源最短路徑469
9.3.2弗洛伊德算法求解有向帶權圖的多源最短路徑473
9.4AOV網和拓撲排序問題479
9.5AOE網和關鍵路徑問題484
參考文獻489
