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

1 绪论 1

1.1 数据类型与数据结构 1

1.2 数据类型（数据结构）的实现 2

1.3 面向对象的设计和ADT 4

1.3.1 面向函数的数据结构 4

1.3.2 面向对象的数据结构 4

1.3.3 在C++中的数据结构的构造 5

1.4 算法 12

1.5 时间复杂性的度量 13

1.5.1 大O表示法 15

1.5.2 大Ω，？及小o表示法 19

1.6 有效算法的重要性 19

1.7 渐进的空间复杂性 21

2 线性表 22

2.1 线性表的定义及ADT 22

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

2.2.1 顺序表类 24

2.2.2 顺序表的基本操作 25

2.3 线性表的链接存储结构 30

2.3.1 链表的抽象数据类型 32

2.3.2 链表迭代器类 32

2.3.3 单链表类、基本操作及迭代器的实现 34

2.4 单向循环链表 40

2.5 双链表、双向循环链表 41

2.6 一元多项式的加法 43

3 栈和队列 48

3.1 栈 48

3.1.1 栈的定义和抽象数据类型 48

3.1.2 栈的顺序存储 49

3.1.3 栈的链式存储 53

3.2 队列 55

3.2.1 队列的定义和抽象数据类型 56

3.2.2 队列的顺序存储 56

3.2.3 队列的链式存储 60

3.3 优先队列 62

3.4 栈和队列的应用 64

3.4.1 括号配对检查 64

3.4.2 中缀式和后缀式 68

3.4.3 简单计算器的实现 70

3.4.4 Josephus问题 75

4 串 77

4.1 串、存储、串的基本运算 77

4.1.1 串定义及相关概念 77

4.1.2 串的存储 77

4.1.3 串的基本操作 78

4.2 字符串类 79

4.3 串的模式匹配 84

4.3.1 Brute-Force算法（BF算法） 84

4.3.2 KMP算法 85

5 树及二叉树 90

5.1 树的定义和术语 90

5.2 二叉树 92

5.2.1 二叉树的定义 92

5.2.2 二叉树的性质 93

5.2.3 二叉树的存储结构 95

5.3 二叉树的遍历 100

5.3.1 前序遍历 100

5.3.2 中序遍历 101

5.3.3 后序遍历 102

5.4 二叉树遍历的迭代器类 104

5.4.1 前序遍历迭代器类 105

5.4.2 后序遍历迭代器类 106

5.4.3 中序遍历迭代器类 108

5.5 中序穿线树 109

5.6 最优二叉树及其应用 114

5.6.1 基本概念 114

5.6.2 哈夫曼算法的实现 116

5.6.3 哈夫曼编码 118

5.7 树和森林 120

5.7.1 树的存储结构 120

5.7.2 树、森林与二叉树的转换 122

5.7.3 树和森林的遍历 123

6 查找 126

6.1 静态查找技术 126

6.1.1 顺序查找 128

6.1.2 折半查找 130

6.1.3 插值查找 133

6.2 二叉排序树 133

6.2.1 二叉排序树的抽象数据类型 133

6.2.2 基本操作 136

6.2.3 顺序统计 142

6.3 平衡二叉排序树（AVL树） 145

6.3.1 插入操作 146

6.3.2 删除操作 153

6.3.3 最大高度 155

6.4 红-黑树 156

6.4.1 插入操作 157

6.4.2 自顶向下的删除操作 160

6.4.3 红-黑树的实现 161

6.5 B-树和B+树 165

6.5.1 B-树 166

6.5.2 B-树的查找分析 167

6.5.3 插入操作 168

6.5.4 删除操作 170

6.5.5 B+树 171

6.6 哈希方法 173

6.6.1 常用的散列函数 173

6.6.2 线性探测法 176

6.6.3 二次探测法 179

6.6.4 链法 184

7 图 186

7.1 图的基本概念 186

7.1.1 图的概念、术语 186

7.1.2 图的抽象数据类型 189

7.2 图的存储表示 190

7.2.1 邻接矩阵和加权邻接矩阵 190

7.2.2 邻接表 193

7.2.3 邻接多重表 198

7.2.4 十字链表 199

7.3 图的遍历和连通性 199

7.3.1 深度优先搜索DFS 200

7.3.2 广度优先搜索BFS 202

7.3.3 优先度优先搜索PFS 204

7.3.4 有向图的强连通分量 204

7.4 最小代价生成树 205

7.4.1 普里姆算法 206

7.4.2 克鲁斯卡尔算法 209

7.5 最短路径问题 211

7.5.1 单源最短路径 211

7.5.2 所有顶点对之间的最短路径 215

7.6 AOV网和AOE网 217

7.6.1 拓扑排序 218

7.6.2 关键路径 222

8 排序 230

8.1 引言 230

8.2 合并排序 231

8.2.1 合并排序的来源 231

8.2.2 算法分析 233

8.3 用比较法进行排序的时间下界 234

8.4 选择排序和堆排序 235

8.4.1 选择排序 235

8.4.2 堆排序 236

8.4.3 堆和优先队列、最左树 246

8.5 插入排序和希尔排序 249

8.5.1 简单插入排序 249

8.5.2 折半插入排序 251

8.5.3 希尔排序 252

8.6 快速排序 253

8.6.1 快速排序的基本原理 253

8.6.2 快速排序的分析 255

8.6.3 算法的实现 257

8.7 基数排序 260

8.7.1 多关键字排序 261

8.7.2 口袋排序法 262

9 算法设计的基本方法 265

9.1 分治法 265

9.1.1 最大最小问题 265

9.1.2 Strassen矩阵乘法 269

9.1.3 顺序统计 271

9.2 动态规划 276

9.2.1 货郎担问题 276

9.2.2 多级图问题 278

9.2.3 最优二叉查找树 281

9.3 回溯法 286

9.3.1 皇后问题 287

9.3.2 背包问题 290

9.4 分支限界法 296

9.4.1 n后问题 296

9.4.2 背包问题 297

9.4.3 单源最短路径问题 299

9.4.4 电路板排列 302

10 标准模板库 307

10.1 名字空间 307

10.2 基本概念 309

10.2.1 容器 309

10.2.2 迭代器 309

10.2.3 算法 310

10.2.4 函数对象 311

10.3 标准容器 313

10.3.1 向量 313

10.3.2 表 317

10.3.3 双端队列 318

10.3.4 堆栈 320

10.3.5 队列 321

10.3.6 优先队列 321

10.3.7 排序 323

10.3.8 集和多集 327

10.3.9 映射和多重映射 330

参考文献 332