《数据结构解题策略》吴永辉 王建德 | PDF下载|ePub下载
数据结构解题策略 版权信息
- 出版社:机械工业出版社
- 出版时间:2023-10-01
- ISBN:9787111733089
- 条形码:9787111733089 ; 978-7-111-73308-9
数据结构解题策略 本书特色
本书以面对纷呈复杂问题时如何理清数据关系,选择适宜高效的数据结构和解题方法为主线,分别阐述线性表、树、图的解题策略,全书共16章。每章以相关的数据结构、高级数据结构的知识体系为大纲,以基于程序设计竞赛试题的解题实验为核心单元,以期通过案例化的学习,系统、全面地提高读者编程解决问题的能力。本书既可以作为ACM-ICPC、IOI等各类程序设计竞赛的训练教程,又可以作为大学本科、研究生的教材,也可以作为IT研发人员提高编程能力的辅导教材。
数据结构解题策略 内容简介
本书以面对纷呈复杂问题时如何理清数据关系,选择适宜高效的数据结构和解题方法为主线,分别阐述线性表、树、图的解题策略,全书共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 单调队列优化DP 69
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
前言
**篇 线性表的解题策略
第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 单调队列优化DP 69
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