数据结构与算法 C++语言版PDF电子书下载

第1章 绪论…… 1

1.1 什么是数据结构 1

1.1.1 基本概念 1

1.1.2 数据结构的内涵 1

1.1.3 数据类型和抽象数据类型 3

1.2 算法和算法分析 4

1.2.1 算法的描述 4

1.2.2 算法设计的要求 4

1.2.3 算法分析 4

本章总结 7

习题1 8

第2章 线性表 12

2.1 线性表的类型定义 12

2.1.1 基本概念 12

2.1.2 抽象数据类型描述 12

2.1.3 线性表抽象类 13

2.1.4 异常类NoMem和OutOfBounds 14

2.2 线性表的顺序存储结构 15

2.2.1 基本概念 15

2.2.2 基本操作 16

2.3 线性表的链式存储结构 21

2.3.1 线性链表 21

2.3.2 循环链表 29

2.3.3 双向链表 29

2.3.4 顺序表和链表的比较 32

2.4 线性表的应用——多项式相加与Josephus问题 32

2.4.1 多项式表示 32

2.4.2 多项式相加 35

本章总结 37

习题2 38

第3章 栈与队列 43

3.1 栈 43

3.1.1 栈的定义 43

3.1.2 栈的抽象类 44

3.1.3 栈的顺序存储结构 44

3.1.4 栈的链式存储结构 46

3.2 栈的应用举例 47

3.3 栈与递归 51

3.4 队列 51

3.4.1 队列的定义 51

3.4.2 队列的顺序存储结构 53

3.4.3 队列的链式存储结构 58

本章总结 60

习题3 61

第4章 串 64

4.1 串的逻辑结构 64

4.1.1 基本概念 64

4.1.2 串的大小比较 66

4.2 串的存储结构 66

4.3 串函数与串的类定义 67

4.3.1 常用的C＋＋串函数 67

4.3.2 串的类定义 68

4.4 串模式匹配 70

4.4.1 简单串模式匹配算法 71

4.4.2 无回溯的匹配算法 71

4.5 串的应用——文本编辑 73

本章总结 74

习题4 74

第5章 多维数组与广义表 76

5.1 数组 76

5.1.1 数组的定义 76

5.1.2 C＋＋的数组 77

5.1.3 数组的存储结构与寻址问题 77

5.2 类Array 1D 80

5.3 矩阵的压缩存储 82

5.3.1 特殊矩阵 83

5.3.2 稀疏矩阵 85

5.4 十字链表 89

5.4.1 存储方式 89

5.4.2 十字链表对象 90

5.4.3 基本操作的实现 91

5.4.4 十字链表相加法 93

5.5 广义表 95

5.5.1 广义表的定义 95

5.5.2 广义表的抽象数据类型定义 96

5.5.3 广义表的存储结构 97

本章总结 100

习题5 101

第6章 树与二叉树 103

6.1 树的相关概念 103

6.1.1 树的递归定义和逻辑表示法 103

6.1.2 树的基本术语 103

6.1.3 树的抽象类型定义 104

6.2 树的存储结构与遍历 105

6.2.1 树的存储结构 105

6.2.2 树与森林的遍历 108

6.3 二叉树 109

6.3.1 二叉树的定义 109

6.3.2 二叉树的性质 111

6.4 二叉树的存储结构 112

6.4.1 顺序存储结构 112

6.4.2 链式存储结构 113

6.5 二叉树对象模型 114

6.5.1 二叉树结点对象 114

6.5.2 二叉树对象 115

6.6 二叉树的遍历与线索化 118

6.6.1 二叉树的遍历 118

6.6.2 二叉树的线索化 123

6.6.3 二叉树与森林的转换 126

6.7 哈夫曼树及其应用 128

6.7.1 哈夫曼树 128

6.7.2 哈夫曼编码 129

本章总结 133

习题6 134

第7章 图 137

7.1 图的定义和术语 137

7.2 图的对象抽象模型 141

7.2.1 图结点对象抽象模型 141

7.2.2 图的边对象抽象模型 141

7.2.3 图对象抽象模型 142

7.3 图的存储结构 143

7.3.1 邻接矩阵 143

7.3.2 邻接表 148

7.3.3 十字链表（有向图） 153

7.3.4 邻接多重表（无向图） 155

7.4 图的遍历 156

7.4.1 深度优先遍历 156

7.4.2 广度优先遍历 161

7.5 图的连通性问题 163

7.5.1 图的连通分量 163

7.5.2 生成树及生成森林 164

7.6 有向无环图及其应用 167

7.6.1 有向无环图 167

7.6.2 AOV网与拓扑排序 168

7.6.3 AOE网与关键路径 171

本章总结 176

习题7 176

第8章 查找 179

8.1 查找表的相关概念 179

8.1.1 基本概念 179

8.1.2 类型说明 179

8.2 静态查找表 180

8.2.1 概述 180

8.2.2 顺序表的查找 180

8.2.3 有序表的查找 182

8.2.4 索引顺序表的查找 183

8.3 动态查找表 186

8.3.1 概述 186

8.3.2 二叉排序树 186

8.3.3 平衡二叉树 191

8.3.4 B-树和B＋树 193

8.4 哈希表 198

8.4.1 哈希表的定义 198

8.4.2 哈希函数的构造 198

8.4.3 处理冲突的方法 200

8.4.4 哈希表的查找及其分析 204

本章总结 205

习题8 206

第9章 内部排序 208

9.1 排序的基本概念 208

9.2 插入排序 209

9.2.1 直接插入排序 209

9.2.2 折半插入排序 211

9.2.3 2路插入排序 211

9.2.4 表插入排序 212

9.2.5 希尔排序 214

9.3 交换排序 215

9.3.1 冒泡排序 215

9.3.2 快速排序 216

9.4 选择排序 218

9.4.1 简单选择排序 218

9.4.2 堆排序 219

9.5 归并排序 224

9.6 基数排序 225

9.6.1 多关键码的排序 225

9.6.2 链式基数排序 226

9.7 内排序方法的比较和讨论 227

本章总结 228

习题9 229

第10章 文件组织和外排序 231

10.1 外存储器概述 231

10.1.1 磁带及其信息的存取 231

10.1.2 磁盘及其信息的存取 232

10.1.3 U盘 232

10.2 文件的基本概念 233

10.2.1 文件 233

10.2.2 文件的操作（运算）与存取 233

10.2.3 文件的物理结构 234

10.3 顺序文件 235

10.4 索引文件 235

10.5 ISAM文件和VSAM文件 236

10.5.1 ISAM文件 236

10.5.2 VSAM文件 238

10.6 散列文件 239

10.7 多关键字文件 240

10.7.1 多重表文件 241

10.7.2 倒排文件 241

10.8 外部排序 242

本章总结 243

习题10 244

第11章 贪婪算法 247

11.1 最优化问题 247

11.2 算法思想 248

11.3 应用 248

11.3.1 货箱装船 248

11.3.2 0-1背包问题 249

11.3.3 拓扑排序 250

11.3.4 二分覆盖 250

11.3.5 单源最短路径 254

11.3.6 最小代价生成树 256

习题11 259

第12章 分而治之算法 261

12.1 算法思想 261

12.2 应用 261

12.2.1 最大最小问题 261

12.2.2 归并排序 263

12.2.3 快速排序 265

12.2.4 选择问题 265

12.2.5 距离最近的点对问题 267

习题12 271

第13章 动态规划 272

13.1 算法思想 272

13.2 应用 272

13.2.1 0-1背包问题 272

13.2.2 图像压缩 274

13.2.3 矩阵连乘法 279

习题13 282

第14章 回溯 284

14.1 算法思想 284

14.2 应用 285

14.2.1 货箱装船 285

14.2.2 0-1背包问题 288

14.2.3 最大完备子图 291

习题14 293

第15章 分枝定界法 294

15.1 算法思想 294

15.2 应用 295

15.2.1 货箱装船 295

15.2.2 0-1背包问题 301

15.2.3 最大完备子图 302

习题15 304

参考文献 305