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

第1章 C++面向对象程序设计 1

1.1 抽象数据类型 1

1.2 封装 1

1.3 继承 5

1.4 指针 8

1.4.1 指针和数组 10

1.4.2 指针和复制构造函数 12

1.4.3 指针和析构函数 15

1.4.4 指针和引用变量 15

1.4.5 函数指针 17

1.5 多态性 18

1.6 C++和面向对象程序 20

1.7 标准模板库 21

1.7.1 容器 21

1.7.2 迭代器 22

1.7.3 算法 22

1.7.4 函数对象 23

1.8 标准模板库中的向量 25

1.9 数据结构与面向对象编程 32

1.10 实例分析：随机访问文件 32

1.11 习题 43

1.12 程序设计作业 45

第2章 复杂度分析 48

2.1 计算复杂度和渐进复杂度 48

2.2 大O符号 49

2.3 大O符号的性质 51

2.4 Ω符号与Θ符号 52

2.5 可能的问题 53

2.6 复杂度举例 54

2.7 寻找渐近复杂度举例 55

2.8 最好、平均和最坏情况 57

2.9 阻尼复杂度 59

2.10 习题 63

第3章 链表 67

3.1 单链表 67

3.1.1 插入 72

3.1.2 删除 74

3.1.3 查找 79

3.2 双链表 80

3.3 循环链表 84

3.4 跳跃链表 86

3.5 自组织链表 90

3.6 稀疏表 94

3.7 标准模板库中的链表 97

3.8 标准模板库中的双端队列 101

3.9 总结评价 105

3.10 实例分析：图书馆 106

3.11 习题 115

3.12 程序设计作业 117

4.1 栈 121

第4章 栈与队列 121

4.2 队列 128

4.3 优先队列 135

4.4 标准模板库中的栈 136

4.5 标准模板库中的队列 136

4.6 标准模板库中的优先队列 137

4.7 实例分析：迷宫问题 140

4.8 习题 145

4.9 程序设计作业 147

第5章 递归 150

5.1 递归定义 150

5.2 函数调用与递归实现 152

5.3 递归调用的剖析 154

5.4 尾部递归 157

5.5 非尾部递归 158

5.6 间接递归 163

5.7 嵌套递归 165

5.8 不合理递归 166

5.9 回溯 169

5.10 结束总结 175

5.11 实例分析：递归下降解释器 176

5.12 习题 183

5.13 程序设计作业 186

第6章 二叉树 190

6.1 树、二叉树和二叉搜索树 190

6.2 二叉树的实现 193

6.3 搜索一棵二叉搜索树 196

6.4 树的遍历 198

6.4.1 广度优先遍历 199

6.4.2 深度优先遍历 200

6.4.3 不用栈实现的深度优先遍历 206

6.5 插入 212

6.6 删除 215

6.6.1 通过合并进行删除 216

6.6.2 通过复制进行删除 219

6.7 平衡树 221

6.7.1 DSW算法 223

6.7.2 AVL树 226

6.8.1 自重新构造树 231

6.8 自调整树 231

6.8.2 “倾斜(splaying)”策略 233

6.9 堆 237

6.9.1 将堆作为优先队列 238

6.9.2 将数组组织为堆 241

6.10 波兰式表示和表达式树 244

6.11 实例分析：计算单词频率 249

6.12 习题 256

6.13 程序设计作业 259

第7章 多叉树 265

7.1 B-树家族 265

7.1.1 B树 267

7.1.2 B？-树 274

7.1.3 B+树 276

7.1.4 前缀B+树 278

7.1.5 位树 280

7.1.6 R树 281

7.1.7 2-4树 283

7.1.8 在标准模板库中的集和多集 289

7.1.9 在标准模板库中的映射和多映射 293

7.2 trie 298

7.3 结束总结 305

7.4 实例分析：拼写检查器 305

7.5 习题 314

7.6 程序设计作业 315

第8章 图 320

8.1 图的表示法 321

8.2 图的遍历 323

8.3 最短路径 325

8.4 环的检测 333

8.5 生成树 336

8.5.1 勃赫如夫加算法 337

8.5.2 克鲁斯卡尔算法 338

8.5.3 普里姆算法 338

8.5.4 迪杰斯特拉方法 340

8.6 连通性 340

8.6.1 无向图中的连通性 340

8.6.2 有向图中的连通性 343

8.7 拓扑排序 344

8.8 网络 346

8.8.1 最大流 346

8.8.2 最小代价的最大流 354

8.9 匹配 358

8.9.1 分配问题 363

8.9.2 非二分图中的匹配 365

8.10 欧拉(Eulerian)图与汉密尔顿(Hamiltonian)图 367

8.10.1 Eulerian图 367

8.10.2 Hamiltonian图 368

8.11 实例分析：惟一代表(Distinct Representatives) 370

8.12 习题 380

8.13 程序设计作业 383

第9章 排序 387

9.1 基本的排序算法 388

9.1.1 插入排序 388

9.1.2 选择排序 391

9.1.3 冒泡排序 392

9.2 决策树 394

9.3 高效排序算法 397

9.3.1 希尔排序 397

9.3.2 堆排序 400

9.3.3 快速排序 403

9.3.4 归并排序 408

9.3.5 基数排序 410

9.4 标准模板库中的排序 415

9.5 小结 419

9.6 实例分析：多项式相加 420

9.7 习题 426

9.8 程序设计作业 428

第10章 散列 432

10.1 散列函数 432

10.1.1 除余法 433

10.1.2 折叠法 433

10.1.3 平方取中法 433

10.1.4 提取法 434

10.1.5 基数转换法 434

10.2 冲突解决方法 434

10.2.1 开放定址法 435

10.2.2 拉链法 440

10.2.3 桶定址 443

10.3 删除 444

10.4 理想散列函数 444

10.4.1 Cichelli方法 445

10.4.2 FHCD算法 448

10.5 可扩展文件的散列函数 450

10.5.1 可扩展散列 450

10.5.2 线性散列 452

10.6 实例分析：使用桶的散列 455

10.7 习题 463

10.8 程序设计作业 464

11.1 数据压缩的条件 467

第11章 数据压缩 467

11.2 Huffman编码 469

11.3 Shannon-Fano编码 480

11.4 Run-Length编码方式 481

11.5 Ziv-Lempel编码方式 482

11.6 实例分析：Huffman方法和Run-Length编码方式 485

11.7 习题 495

11.8 程序设计作业 495

第12章 内存管理 499

12.1 sequential-fit方法 500

12.2 Nonsequential-fit方法 501

12.3 无用单元回收 508

12.3.1 标记和清除 509

12.3.2 复制方法 515

12.3.3 递增的无用单元回收 516

12.4 结束总结 523

12.5 实例分析 523

12.6 习题 531

12.7 程序设计 532

附录A 计算大O 537

A.1 调和数序列n 537

A.2 函数lg(N!)的近似值 537

A.3 快速排序中平均情况的大O 539

A.4 随机二进制树中的平均路径长度 540

附录B 标准模板库中的算法 542