程序设计中实用的数据结构PDF电子书下载

上篇 讨论线性表 3

第1章 数组 3

1.1数组的基本概念 3

1.1.1数组是一种顺序存储结构 3

1.1.2数组是程序设计中使用频率最高的数据类型 4

1.2优化数组的存储方式 6

1.2.1规则矩阵的压缩存储 6

1.2.2稀疏矩阵的压缩存储 7

1.2.3 01矩阵的压缩存储 11

1.3排序与顺序统计 14

1.3.1排序的基本概念 14

1.3.2计数排序与贪心策略 15

1.3.3采用“二分”策略的排序方法 21

1.3.4顺序统计的基本方法 28

第2章 链式存储结构 34

2.1链表的基本概念 34

2.1.1单链表 34

2.1.2循环链表 35

2.1.3双向链表 35

2.2链表的基本运算 35

2.2.1构建单链表 36

2.2.2插入操作 36

2.2.3 删除操作 36

2.2.4读取操作 36

2.3链表的应用 37

第3章 两种存取方式特殊的线性表 43

3.1“后进先出”的栈 43

3.1.1栈的基本运算 43

3.1.2栈的应用 44

3.2“先进先出”的队列 52

3.2.1队列的基本运算 52

3.2.2队列的应用 54

第4章 散列技术 59

4.1散列表 59

4.2散列函数的设计 59

4.3消除冲突的基本方法 61

4.3.1使用开放寻址法消除冲突 61

4.3.2使用分离链接法消除冲突 67

第5章 后缀数组 71

5.1后缀数组的基本概念 71

5.2采用倍增算法求解rank数组 73

5.3利用rank数组计算最长公共前缀 74

5.3.1计算最长公共前缀是一个典型的RMQ问题 75

5.3.2计算最长公共前缀的基本方法 75

5.4后缀数组的应用 78

5.4.1利用后缀数组处理单个字符串 78

5.4.2两个字符串的公共子串问题 87

5.4.3多个字符串共享子串的问题 90

上篇小结 97

中篇 讨论树型问题 101

第6章 树的基本概念和遍历规则 101

6.1树的递归定义 101

6.2节点的分类 101

6.3有关度的定义 101

6.4树的深度（高度） 102

6.5森林 102

6.6有序树和无序树 102

6.7树的表示方法 103

6.8树的遍历规则 103

6.8.1先根次序遍历树 103

6.8.2后根次序遍历树 104

第7章 树的存储结构 105

7.1采用数组存储入边信息 105

7.1.1存储无权树的入边信息 105

7.1.2存储加权树的入边信息 106

7.2采用数组存储所有儿子的地址信息 108

7.2.1采用整数存储儿子的数组下标 108

7.2.2采用指针存储儿子的地址 109

7.3采用邻接表存储出边信息 110

7.3.1采用数组存储方式的邻接表 110

7.3.2采用单链表存储方式的邻接表 114

7.4无根树的一般存储方式 116

第8章 二叉树 123

8.1二叉树的基本概念和存储结构 123

8.1.1二叉树的基本概念 123

8.1.2二叉树的存储结构 125

8.2将普通有序树和森林转换成对应的二叉树 128

8.2.1将普通有序树转换成对应的二叉树 128

8.2.2将普通有序树组成的森林转换成对应的二叉树 129

8.3二叉树的遍历 130

8.3.1前序遍历 130

8.3.2中序遍历 130

8.3.3后序遍历 131

8.3.4由两种遍历确定二叉树结构 133

第9章 并查集 135

9.1并查集的基本概念 135

9.2查找元素所在树的根节点并进行路径压缩 137

9.3合并两个元素所在的集合 138

第10章堆 143

10.1二叉堆的概念 143

10.2在插入或删除节点时维护堆性质 144

10.2.1插入节点 144

10.2.2 删除最小值元素 144

10.3建堆 145

10.4堆排序 146

第11章 最优二叉树 154

11.1最优二叉树的基本概念 154

11.2构造最优二叉树 155

第12章 线段树 160

12.1线段树的基本概念 160

12.1.1用于区间运算的线段树 160

12.1.2用于数据统计的线段树 161

12.1.3线段树的数据结构 162

12.2线段树的基本操作 162

12.2.1建立线段树 162

12.2.2在区间内插入线段或数据 163

12.2.3 删除区间内的线段或数据 164

12.2.4计算区间内的线段或数据状态 165

12.3线段树在静态统计问题上的应用 165

12.4线段树在动态统计问题上的应用 168

第13章 二叉查找树 176

13.1二叉排序树 176

13.1.1二叉排序树的基本概念 176

13.1.2二叉排序树的基本操作 177

13.2静态二叉排序树 180

13.2.1静态二叉排序树的特征 180

13.2.2静态二叉排序树的构造方法 180

13.2.3在静态二叉排序树上进行数据统计 181

13.3子树大小平衡树（SBT） 186

13.3.1 SBT的性质 186

13.3.2旋转 186

13.3.3动态维护SBT的平衡特性 191

13.3.4 SBT的基本操作 196

中篇小结 205

下篇 讨论图型问题 209

第14章 图的基本概念及其存储结构 209

14.1图的基本概念 209

14.2图的简单分类 211

14.2.1无向图和有向图 212

14.2.2无权图和加权图 212

14.2.3稀疏图和稠密图 212

14.2.4完全图和补图 212

14.2.5树和森林 213

14.2.6图的生成树和生成森林 213

14.2.7平面图 214

14.2.8二分图 214

14.2.9相交图和区间图 214

14.3图的存储结构 215

14.3.1存储节点间相邻关系的相邻矩阵 215

14.3.2存储边信息的3种数据结构 217

第15章 图的遍历及其应用 220

15.1广度优先遍历（BFS算法） 220

15.1.1 BFS算法的基本概念 220

15.1.2 BFS算法的应用 222

15.2深度优先遍历（DFS算法） 233

15.2.1 DFS的基本概念 233

15.2.2在DFS遍历过程中记录节点颜色变化的时间 239

15.2.3根据节点颜色对边进行分类 240

15.2.4分析DFS森林的结构 242

15.2.5使用DFS算法进行拓扑排序 244

15.2.6使用DFS算法计算欧拉回路 248

第16章 有向图的强连通分量和传递闭包 255

16.1判定仙人掌图 255

16.2计算强连通分量 259

16.3传递闭包的应用 266

第17章 无向图的连通性分析 271

17.1计算节点的low函数 271

17.2计算连通图的割点和桥 272

17.2.1计算连通图的割点 272

17.2.2计算连通图的桥 273

17.3计算双连通子图 275

17.4分析连通图的连通程度 276

17.4.1连通图的顶连通度 277

17.4.2连通图的边连通度 278

第18章 最小生成树 279

18.1基本概念 279

18.2最小生成树的应用价值 279

18.3最小生成树的计算策略 281

18.4计算最小生成树的两种算法 281

18.4.1 Kruskal算法 282

18.4.2 Prim算法 283

18.5最小生成树算法的应用实例 285

第19章 加权图的单源最短路径问题 293

19.1基本概念 293

19.1.1单源算法是高效解决所有最短路径问题的基础 293

19.1.2负权回路影响单源最短路径的计算 294

19.1.3松弛技术是单源算法的核心 295

19.2求解单源最短路径问题的3种算法 296

19.2.1 Dijkstra算法 296

19.2.2 Bellman-Ford算法 298

19.2.3 SPFA算法 299

19.3单源最短路径算法的应用实例 301

第20章 二分图的匹配问题 310

20.1基本概念 310

20.1.1图的匹配概念 310

20.1.2二分图的概念和判定方法 311

20.2计算无权二分图的最大匹配 315

20.2.1匈牙利算法的基本思路 316

20.2.2匈牙利算法的基本流程 316

20.2.3匈牙利算法的应用实例 317

20.3计算带权二分图的最佳匹配 320

20.3.1最佳匹配的概念 320

20.3.2 KM算法的基本思路 321

20.3.3 KM算法的基本流程和应用实例 323

第21章 最大流问题 327

21.1基本概念 327

21.2在可增广路径的基础上计算最大流 329

21.2.1可增广路径的基本概念 329

21.2.2基于最大流定理上的最大流算法 334

21.3按层次计算最大流的Dinic算法 334

21.3.1 Dinic算法的基本思路 334

21.3.2 Dinic算法的基本流程 335

21.4利用最大流最小割定理解题 339

21.4.1割的概念 339

21.4.2最小割的计算方法和应用实例 340

21.5计算多源多汇网络的可行流 346

21.6网络增加容量下界因素后的流量计算问题 348

21.6.1求容量有上下界的网络的最大流 348

21.6.2求容量有上下界的网络的最小流 353

21.7网络增加费用因素后的流量计算问题 358

21.7.1计算最小费用最大流 359

21.7.2计算容量有上下界的网络的最小费用最小流 364

下篇小结 370