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

第1章 绪论 1

1.1利用计算机解决问题的几个步骤 1

1.2基本概念和术语 2

1.3算法及其复杂度分析 4

1.4算法的描述语言 5

第2章 算法分析技术 7

2.1无穷大的阶 7

2.2若干序列和函数的渐进性质 8

2.2.1调和级数 8

2.2.2 Fibonacci序列 8

2.2.3 log2函数 9

2.2.4基本定理 9

2.2.5 Catalan数 10

2.2.6一个特别序列 11

2.3算法的时间复杂度 11

2.4算法的空间复杂度 13

2.5冒泡排序算法复杂度分析 13

2.6分摊复杂度分析 14

2.6.1累计法 15

2.6.2势函数法 16

2.6.3捐款记账法 17

习题 17

第3章 线性表 21

3.1顺序线性表：向量 21

3.1.1 Vector类模板的成员变量 21

3.1.2向量的迭代子 22

3.1.3获取向量的成员 22

3.1.4向量元素的删除 22

3.1.5向量的存储管理 22

3.1.6添加函数 23

3.1.7完整的Vector类 23

3.2单链表 25

3.2.1单链表迭代子类 26

3.2.2添加和删除操作 26

3.3其他形式的单链表 27

3.4双链表 27

3.5静态链表 29

3.6动态内存管理 31

3.7矩阵 35

3.8对称矩阵 36

3.9稀疏矩阵 36

习题 39

第4章 栈与队列 40

4.1栈的定义与实现 40

4.2栈与函数调用 41

4.2.1 函数调用框架 42

4.2.2汉诺塔问题 43

4.2.3间接递归调用 44

4.3广义栈 44

4.4回溯法 45

4.4.1八皇后问题 46

4.4.2八皇后问题回溯法的改进 47

4.5队列 48

4.5.1用链表实现队列 49

4.5.2用循环数组实现队列 49

4.6双端队列 51

4.7基数排序 51

习题 53

第5章 字符串与模式匹配算法 54

5.1字符集与字符 54

5.2字符串 54

5.3简单模式匹配算法 55

5.4 KMP算法 55

5.4.1 KMP算法的改进 59

5.4.2 KMP类 61

5.5有限状态自动机模式匹配算法 62

5.5.1有限状态自动机 62

5.5.2模式匹配有限状态自动机 62

5.6 Boyer-Moore模式匹配算法 63

5.7 BM- KMP模式匹配算法 65

习题 65

第6章 树与二叉树 66

6.1树与森林 66

6.2二叉树 67

6.3二叉树的二叉链表表示 71

6.4二叉树的递归遍历 72

6.5二叉树的非递归遍历 73

6.5.1非递归先序遍历 73

6.5.2非递归中序遍历 74

6.5.3非递归后序遍历 74

6.5.4二叉树的构造 75

6.5.5二叉树的显示 76

6.6中序线索化二叉树 76

6.6.1中序线索化二叉树的实现 76

6.6.2遍历中序线索化二叉树 77

6.7二叉树的其他存储表示 77

6.7.1三叉链表表示法 77

6.7.2完全二叉树表示 78

6.7.3三元组表示法 78

6.7.4双亲表示法 78

6.7.5带右链的先根序表示法 78

6.7.6双标志先根序表示法 79

6.8森林与二叉树的对应 80

6.9树与森林的遍历 80

6.10树与森林的存储表示 81

6.10.1树与森林的孩子、兄弟表示法 83

6.10.2无序树的双亲表示法 83

6.11并查集 83

6.11.1复杂度分析 85

6.11.2加权合并 85

6.11.3按秩合并 85

6.11.4折叠查找及其分摊复杂度分析 86

6.11.5并查集的完整实现 88

6.11.6迷宫设计 88

6.12 Huffman树 89

6.12.1无前缀编码与扩充二叉树 89

6.12.2 Huffman算法 89

6.12.3 Huffman压缩 90

习题 91

第7章 选择 94

7.1用数组实现的堆 94

7.1.1极大堆与极小堆 94

7.1.2极大极小堆 96

7.1.3双端堆 100

7.1.4d叉堆 101

7.1.5置换选择 101

7.2用二叉树或树实现的堆 103

7.2.1左堆 103

7.2.2扁堆 106

7.2.3二项式堆 109

7.2.4 Fibonacci堆 110

7.2.5配对堆 116

习题 119

第8章 查找 122

8.1查找结构 122

8.2顺序查找 122

8.2.1顺序查找表类模板 123

8.2.2顺序表的性能分析 123

8.2.3自适应顺序查找 124

8.3哈希表 124

8.3.1哈希函数的设计 124

8.3.2哈希表长M的选取 126

8.3.3冲突处理 126

8.3.4哈希表的性能分析 129

8.4二分查找 131

8.5跳跃表 132

8.5.1随机跳跃表 133

8.5.2 1-2-3跳跃表 134

8.6排序二叉树 135

8.6.1查找、添加和删除操作 136

8.6.2排序二叉树类模板 137

8.6.3查找的性能分析 138

8.7 AVL树 139

8.7.1 AVL树的添加 139

8.7.2 AVL树的删除 141

8.7.3 AVL树的实现及其复杂度 141

8.8 B树 142

8.8.1 B树的查找 142

8.8.2 B树的添加 142

8.8.3 B树的删除 143

8.8.4 B树 144

8.9 AA树 144

8.9.1 AA树的添加 145

8.9.2 AA树的实现 145

8.9.3 AA树类模板 147

8.10红黑树 148

8.10.1红黑树的添加 148

8.10.2红黑树的删除 149

8.10.3自上而下的添加和删除 151

8.11排序二叉堆 152

8.11.1排序二叉堆的添加 152

8.11.2排序二叉堆类模板 153

8.12最佳排序二叉树 153

8.13 Splay树 155

8.13.1Splay运算 156

8.13.2查找操作的分摊复杂度分析 156

8.14多关键字查找 158

8.14.1双链树 158

8.14.2 Trie树 159

8.15索引结构 160

习题 161

第9章 排序 163

9.1插入排序 164

9.1.1插入排序的实现 164

9.1.2插入排序算法的复杂度分析 165

9.1.3插入排序的改进 165

9.2选择排序 166

9.3 Shell排序 166

9.4堆排序 169

9.4.1极大堆及堆排序的实现 169

9.4.2堆排序的性能分析 170

9.5快速排序 171

9.5.1快速排序的性能分析 171

9.5.2快速排序的初步实现 173

9.5.3快速排序的改进 173

9.5.4中位数 175

9.6自省排序 177

9.7间接排序 177

9.8归并排序 179

9.8.1归并的工作量 180

9.8.2归并排序及其性能分析 180

9.8.3数组的归并排序及其性能分析 180

9.8.4单链表的归并 181

9.9基于比较的排序算法的时间复杂度下界 183

9.10基数排序 184

9.11外部排序 185

9.11.1初始序串的生成：双堆实现 185

9.11.2 K路归并的实现：败者树 186

9.11.3最佳归并树 187

习题 188

第10章 图 190

10.1图的定义及相关基本术语 190

10.2图的存储与表示 191

10.2.1单重图的邻接矩阵表示法 191

10.2.2有向图的邻接表表示法 191

10.2.3有向图的逆邻接表表示法 191

10.2.4无向图的多重邻接表表示法 192

10.3图的抽象界面 192

10.3.1弧边的界面 193

10.3.2图的构造函数 193

10.3.3弧边迭代子 193

10.4抽象界面的邻接矩阵实现 194

10.4.1 Weight-traits类模板 194

10.4.2矩阵模板 195

10.4.3弧边类型的定义 196

10.4.4弧边迭代子基类 197

10.4.5有向图弧边迭代子基类 197

10.4.6无向图弧边迭代子基类 197

10.4.7无向图弧边迭代子 199

10.4.8图的基类 200

10.4.9有向图类模板 200

10.4.10无向图类模板 201

10.4.11应用例子 201

10.5图的遍历及其应用 202

10.5.1深度优先遍历及其应用 202

10.5.2深度优先遍历的非递归程序 204

10.5.3深度优先遍历的复杂度 205

10.5.4 Kosaraju算法 205

10.5.5 Tarjan算法 206

10.5.6无向图的深度优先遍历 208

10.5.7重连通图 208

10.5.8宽度优先遍历及其应用 210

10.6有向无圈图 211

10.6.1集合上的偏序 211

10.6.2拓扑排序 211

10.6.3 AOE网和关键路径 212

10.7最小代价生成树 214

10.7.1 Kruskal算法 215

10.7.2 Prim算法 216

10.8最短路径问题 219

10.8.1 Dijkstra算法 219

10.8.2 Peter算法 221

10.8.3 Bellman-Ford算法 221

10.8.4 Floyd算法 224

10.9最大流问题 224

10.9.1广义路径法 225

10.9.2预置推送法 228

习题 232

第11章 STL简介 234

11.1迭代子 234

11.1.1半开半闭区间 235

11.1.2自白迭代子类 236

11.2泛函 240

11.2.1纯泛函 241

11.2.2拟序泛函 241

11.2.3自白泛函类 241

11.2.4自白泛函转换模板 243

11.3算法 245

11.3.1几个实用的函数模板 245

11.3.2日常事务类算法 246

11.3.3查找类算法 250

11.3.4排序类算法 251

11.3.5工作类算法 253

11.3.6已排序区间上的算法 256

11.3.7有关堆的算法 260

11.3.8处理未经初始化的内存 260

11.4容器 261

11.4.1 STL容器的共有界面 261

11.4.2顺序容器 262

11.4.3排序容器 265

11.4.4哈希容器 267

11.5适配器 268

11.5.1容器适配器 268

11.5.2迭代子适配器 270

11.5.3泛函适配器 274

11.5.4应用举例 276

11.5.5后记 277

第12章 C＋＋语言概要 279

12.1注释 279

12.2变量 280

12.3引用 280

12.4常量 281

12.5强制类型转换 282

12.6名字空间 284

12.7动态内存分配 287

12.8输入／输出 287

12.9函数原型声明、函数名重载及默认参数 288

12.10类 289

12.11类模板 291

12.12函数模板 292

第13章 伪随机数产生与高精度计时器 294

13.1线性同余方法 294

13.2加法方法 296

13.3抽牌技术 298

13.4高精度计时器 298

参考文献 301

索引 303