程序设计中实用的数据结构PDF|Epub|txt|kindle电子书版本网盘下载

程序设计中实用的数据结构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