面向算法设计的数据结构 C++语言版PDF电子书下载

第1章 算法 1

1.1 概述 1

1.2 ［实例］二分查找 3

1.3 程序性能与算法分析 5

1.3.1 时间复杂度 6

1.3.2 空间复杂度 8

1.4 渐近记号 9

1.5 ［技巧］阶的快速比较 13

1.5.1 加和型无穷大量阶的比较 13

1.5.2 乘积型无穷大量阶的比较 14

1.5.3 对数型无穷大量阶的比较 15

1.6 习题 18

第2章 抽象数据类型 19

2.1 概述 19

2.2 ［实例］在数据集中查找给定值 20

2.2.1 缺点一：长度受限制 21

2.2.2 缺点二：有序则难变 22

2.2.3 缺点三：查变难两全 22

2.2.4 查找问题的抽象数据类型视角 24

2.3 数据库与数据集 25

2.3.1 数据库 25

2.3.2 数据集 26

2.4 功能与实现 27

2.4.1 向量的伸缩 28

2.4.2 有序向量实现 29

2.4.3 无序向量实现 33

2.4.4 对比 35

2.5 ［技巧］组装使用 36

2.6 STL容器一览 38

2.7 设计模式 40

2.7.1 迭代器 40

2.7.2 适配器 41

2.7.3 组合 41

2.8 习题 43

第3章 向量 45

3.1 概述 45

3.2 ［使用］vector 45

3.3 vector的简要实现 48

3.4 加倍技术 54

3.5 ［技巧］物理存储与进制换算 56

3.5.1 一维数组 56

3.5.2 二维数组 56

3.5.3 多维向量 57

3.6 ［技巧］自然数映射与下标 59

3.7 ［实例］矩阵的向量实现 61

3.7.1 矩阵的简易实现 61

3.7.2 稀疏矩阵 64

3.8 习题 68

第4章 递归 71

4.1 概述 71

4.2 ［技巧］递归设计与归纳证明 72

4.3 递归与进程模型 75

4.4 递归算法性能分析 76

4.5 ［实例］排列生成器 79

4.5.1 利用vector传值实现 81

4.5.2 利用vector引用实现 82

4.6 ［实例］乐高铺砖 84

4.7 习题 89

第5章 栈 91

5.1 概述 91

5.2 ［使用］stack 92

5.3 stack的简要实现 94

5.4 ［技巧］逻辑表达式优化 97

5.5 ［实例］路径搜索 104

5.6 习题 108

第6章 队列 109

6.1 概述 109

6.2 ［使用］queue 109

6.3 ［技巧］循环向量设计 111

6.3.1 使用两个位置指示 111

6.3.2 使用计数信息 113

6.4 queue的简要实现 114

6.5 ［实例］贾宪三角 121

6.6 ［技巧］排队组织与内蕴次序 123

6.7 习题 124

第7章 链 127

7.1 概述 127

7.2 ［使用］list 128

7.3 ［技巧］用于链接的指针 132

7.3.1 利用指针实现链接功能 132

7.3.2 使用真实链首元素指针 134

7.3.3 使用哑结点解决空链判断问题 135

7.4 链的变种 137

7.4.1 单链 137

7.4.2 单循环链 137

7.4.3 双循环链 138

7.5 list的简要实现 138

7.6 ［技巧］基于归纳的初始条件选取 149

7.7 ［实例］归并排序 151

7.8 习题 155

第8章 二叉树 157

8.1 概述 157

8.2 二叉树与树 158

8.3 ［技巧］二叉树遍历 161

8.4 ［技巧］递归处理二叉树 165

8.5 ［实例］二叉查找树 168

8.5.1 特性 169

8.5.2 查找 170

8.5.3 插入 170

8.5.4 删除 171

8.5.5 迭代器 172

8.5.6 效率 173

8.6 习题 173

第9章 集合 175

9.1 概述 175

9.2 ［使用］set与multiset 175

9.3 ［实例］寻找宝藏 178

9.4 ［技巧］哨兵 179

9.4.1 线性查找中的哨兵 180

9.4.2 二叉查找树中的哨兵 181

9.5 ［技巧］集合与序关系 182

9.5.1 排序 182

9.5.2 中位数 183

9.6 ［技巧］不相交集 184

9.7 习题 189

第10章 优先级队列 191

10.1 概述 191

10.2 ［使用］priority_queue 192

10.3 ［技巧］维护最大元 193

10.4 priority_queue的简要实现 196

10.5 ［实例］堆排序 200

10.5.1 数据组织与排序 200

10.5.2 建堆算法 201

10.6 ［实例］Huffman编码 203

10.7 习题 209

第11章 图 211

11.1 概述 211

11.2 图的表示 213

11.2.1 邻接矩阵 214

11.2.2 邻接表 215

11.2.3 选用 216

11.3 图类 217

11.3.1 有向图类 217

11.3.2 加权有向图类 220

11.3.3 加权无向图类 223

11.4 ［技巧］编号与反向映射 225

11.5 ［技巧］DFS和BFS 227

11.5.1 深度优先搜索 228

11.5.2 广度优先搜索 229

11.5.3 若干应用 230

11.6 ［实例］最短路径 232

11.6.1 Dijkstra算法 232

11.6.2 Bellman-Ford-Moore算法 235

11.6.3 Floyd-Warshall算法 237

11.7 ［实例］最小生成树 239

11.7.1 Kruskal算法 240

11.7.2 Prim算法 242

11.8 习题 246

第12章 实验 247

12.1 多维求和 247

12.1.1 一维部分和 247

12.1.2 实验要求 248

12.1.3 评注与引申 248

12.2 幻方计数 249

12.2.1 排列 249

12.2.2 实验要求 250

12.2.3 评注与引申 251

12.3 随机行走 251

12.3.1 伪随机数生成 251

12.3.2 实验要求 252

12.3.3 评注与引申 254

12.4 纸牌游戏 255

12.4.1 可数集 255

12.4.2 实验要求 256

12.4.3 评注与引申 259

12.5 迷宫生成 260

12.5.1 隔板型迷宫 260

12.5.2 实验要求 261

12.5.3 评注与引申 261

12.6 数据压缩 261

12.6.1 存储数据 261

12.6.2 实验要求 262

12.6.3 评注与引申 263

12.7 会场安排 263

12.7.1 时间格式 263

12.7.2 实验要求 263

12.7.3 评注与引申 264

12.8 排序测试 264

12.8.1 随机置换 264

12.8.2 实验要求 265

12.8.3 评注与引申 266

附录A 头文件 269

A.1 计时类 269

A.2 book.h 270

附录B 中文参考书目 275

B.1 国内数据结构教材 275

B.2 数据结构教材（翻译版） 275

B.3 算法教材（翻译版） 276

英文参考文献 277