数据结构解题策略

本书以面对纷呈复杂问题时如何理清数据关系，选择适宜高效的数据结构和解题方法为主线，分别阐述线性表、树、图的解题策略，全书共16章。每章以相关的数据结构、高级数据结构的知识体系为大纲，以基于程序设计竞赛试题的解题实验为核心单元，以期通过案例化的学习，系统、全面地提高读者编程解决问题的能力。本书既可以作为ACM-ICPC、IOI等各类程序设计竞赛的训练教程，又可以作为大学本科、研究生的教材，也可以作为IT研发人员提高编程能力的辅导教材。

目　　录<br />前言<br />第一篇　线性表的解题策略<br />第1章　利用快速幂提高幂运算效率　　2<br />1.1　快速幂取模　　　2<br />1.1.1　快速幂取模的概念　　　2<br />1.1.2　快速幂取模的应用　　　4<br />1.2　矩阵快速幂　　　10<br />1.2.1　矩阵快速幂的概念　　　10<br />1.2.2　矩阵快速幂的应用　　　14<br />第2章　高斯消元法　　22<br />2.1　高斯消元法求解线性方程组　　　22<br />2.2　高斯消元法求解模线性方程组　　　30<br />2.3　高斯消元法求解异或方程组　　　38<br />2.4　高斯消元求矩阵的秩　　　49<br />第3章　单调栈和单调队列　　52<br />3.1　单调栈　　　52<br />3.2　二维空间中应用单调栈　　　61<br />3.3　单调队列　　　65<br />3.4　单调队列优化DP　　　69<br />3.5　单调队列优化DP之多重背包问题　　　78<br />第一篇小结　　83<br />第二篇　树的解题策略<br />第4章　利用划分树查找有序数　　86<br />4.1　离线构建整个查询区间的划分树　　87<br />4.2　在划分树上查找子区间[l, r]中<br />　　按序排列的第k个值　　88<br />4.3　利用划分树解题　　88<br />第5章　利用线段树解决区间计算问题　　97<br />5.1　线段树的基本概念和基本操作　　97<br />5.2　线段树动态维护：单点更新　　101<br />5.3　线段树动态维护：子区间更新和<br />　　　　 懒惰标记　　106<br />5.4 　线段树动态维护：子区间合并　　112<br />5.5　权值线段树　　120<br />5.6　主席树　　125<br />第6章　最小生成树的拓展　　129<br />6.1　最小生成树的应用　　129<br />6.2　最优比率生成树　　143<br />6.3　最小k度限制生成树　　148<br />6.4　次小生成树　　154<br />第7章　利用改进型的二叉搜索树优化<br />　　　　　　　　 动态集合的操作　　171<br />7.1　伸展树　　171<br />7.2　红黑树　　198<br />第8章　利用左偏树实现优先队列的合并　　212<br />8.1　左偏树的基本概念　　212<br />8.2　利用左偏树解题　　216<br />第9章　利用动态树维护森林的连通性　　230<br />9.1　树链剖分　　230<br />9.2　动态树　　241<br />第10章　利用跳跃表替代树结构　　260<br />10.1　跳跃表的基本概念　　260<br />10.2　利用跳跃表解题　　265<br />第二篇小结　　279<br />第三篇　图的解题策略<br />第11章　网络流算法　　282<br />11.1　利用Dinic算法求解最大流　　282<br />11.2　求容量有上下界的网络流问题　　298<br />11.2.1　求解无源汇且容量有上下界<br />　　　　　　的网络可行流问题　　　298<br />11.2.2　求解有源汇且容量有上下界<br />　　　　　　　 的网络最大流问题　　　307<br />11.2.3　求解有源汇且容量有上下界<br />　　　　　　　 的网络最小流问题　　　316<br />11.3　计算最小（最大）费用最大流　　321<br />第12章　二分图匹配　　329<br />12.1　匈牙利算法　　329<br />12.2　稳定婚姻问题　　344<br />12.3　KM算法　　350<br />12.4　利用一一对应的匹配性质转化<br />　　　　　　问题的实验范例　　358<br />第13章　平面图、图的着色与偏序关系　　371<br />13.1　平面图　　371<br />13.2　图的着色　　380<br />13.3　黑白着色法判定二分图　　383<br />13.4　偏序关系　　395<br />第14章　分层图　　407<br />14.1　体验“分层图”思想内涵　　407<br />14.2　基于动态规划利用“分层图”<br />　　　　　　求解最短路径问题　　417<br />14.3　利用“分层图”思想优化算法　　425<br />第15章　可简单图化与图的计数　　430<br />15.1　可简单图化　　430<br />15.2　生成树计数　　435<br />15.3　基于遍历的图的计数　　446<br />15.4　基于组合分析的图的计数　　451<br />第16章　挖掘和利用图的性质　　460<br />16.1　挖掘和利用图的性质的方法　　460<br />16.2　挖掘和利用图的性质的实验范例460<br />第三篇小结　　468