《數據結構解題策略》是2023年機械工業出版社出版的圖書。
基本介紹
- 中文名：數據結構解題策略
- 出版時間：2023年10月1日
- 出版社：機械工業出版社
- ISBN：9787111733089
內容簡介,圖書目錄,
內容簡介
本書以面對紛呈複雜問題時如何理清數據關係，選擇適宜高效的數據結構和解題方法為主線，分別闡述線性表、樹、圖的解題策略，全書共16章。每章以相關的數據結構、高級數據結構的知識體系為大綱，以基於程式設計競賽試題的解題實驗為核心單元，以期通過案例化的學習，系統、全面地提高讀者編程解決問題的能力。本書既可以作為ACM-ICPC、IOI等各類程式設計競賽的訓練教程，又可以作為大學本科、研究生的教材，也可以作為IT研發人員提高編程能力的輔導教材。
圖書目錄
前言
第一篇 線性表的解題策略
第1章 利用快速冪提高冪運算效率 2
1.1 快速冪取模2
1.1.1 快速冪取模的概念2
1.1.2 快速冪取模的套用4
1.2 矩陣快速冪10
1.2.1 矩陣快速冪的概念10
1.2.2 矩陣快速冪的套用14
第2章 高斯消元法 22
2.1 高斯消元法求解線性方程組22
2.2 高斯消元法求解模線性方程組30
2.3 高斯消元法求解異或方程組38
2.4 高斯消元求矩陣的秩49
第3章 單調棧和單調佇列 52
3.1 單調棧52
3.2 二維空間中套用單調棧61
3.3 單調佇列65
3.4 單調佇列最佳化DP69
3.5 單調佇列最佳化DP之多重背包問題78
第一篇小結 83
第二篇 樹的解題策略
第4章 利用劃分樹查找有序數 86
4.1 離線構建整個查詢區間的劃分樹 87
4.2 在劃分樹上查找子區間[l, r]中
按序排列的第k個值 88
4.3 利用劃分樹解題 88
第5章 利用線段樹解決區間計算問題 97
5.1 線段樹的基本概念和基本操作 97
5.2 線段樹動態維護：單點更新 101
5.3 線段樹動態維護：子區間更新和
懶惰標記 106
5.4 線段樹動態維護：子區間合併 112
5.5 權值線段樹 120
5.6 主席樹 125
第6章 最小生成樹的拓展 129
6.1 最小生成樹的套用 129
6.2 最優比率生成樹 143
6.3 最小k度限制生成樹 148
6.4 次小生成樹 154
第7章 利用改進型的二叉搜尋樹最佳化
動態集合的操作 171
7.1 伸展樹 171
7.2 紅黑樹 198
第8章 利用左偏樹實現優先佇列的合併 212
8.1 左偏樹的基本概念 212
8.2 利用左偏樹解題 216
第9章 利用動態樹維護森林的連通性 230
9.1 樹鏈剖分 230
9.2 動態樹 241
第10章 利用跳躍表替代樹結構 260
10.1 跳躍表的基本概念 260
10.2 利用跳躍表解題 265
第二篇小結 279
第三篇 圖的解題策略
第11章 網路流算法 282
11.1 利用Dinic算法求解最大流 282
11.2 求容量有上下界的網路流問題 298
11.2.1 求解無源匯且容量有上下界
的網路可行流問題298
11.2.2 求解有源匯且容量有上下界
的網路最大流問題307
11.2.3 求解有源匯且容量有上下界
的網路最小流問題316
11.3 計算最小（最大）費用最大流 321
第12章 二分圖匹配 329
12.1 匈牙利算法 329
12.2 穩定婚姻問題 344
12.3 KM算法 350
12.4 利用一一對應的匹配性質轉化
問題的實驗範例 358
第13章 平面圖、圖的著色與偏序關係 371
13.1 平面圖 371
13.2 圖的著色 380
13.3 黑白著色法判定二分圖 383
13.4 偏序關係 395
第14章 分層圖 407
14.1 體驗“分層圖”思想內涵 407
14.2 基於動態規劃利用“分層圖”
求解最短路徑問題 417
14.3 利用“分層圖”思想最佳化算法 425
第15章 可簡單圖化與圖的計數 430
15.1 可簡單圖化 430
15.2 生成樹計數 435
15.3 基於遍歷的圖的計數 446
15.4 基於組合分析的圖的計數 451
第16章 挖掘和利用圖的性質 460
16.1 挖掘和利用圖的性質的方法 460
16.2 挖掘和利用圖的性質的實驗範例460
第三篇小結 468
