数据结构与算法分析 C++语言描述PDF电子书下载

第1章 软件开发 1

1.1 问题分析和需求规格说明 3

1.2 设计 5

1.2.1 自顶向下设计 5

1.2.2 面向对象设计 7

1.2.3 小规模设计 9

1.3 编码 15

1.4 测试、运行和调试 27

1.5 维护 34

1.6 本章小结 36

第2章 抽象数据类型入门 40

2.1 对ADT及其实现的第一瞥 40

2.2 C＋＋的简单数据类型 41

2.2.1 整型数据 42

2.2.2 实型数据 46

2.2.3 字符数据 49

2.4.4 布尔数据 50

2.3.1 Typedefs 53

2.3.2 枚举 53

2.3 程序员定义的数据类型 53

2.3.3 类 55

2.4 指针 56

2.4.1 声明和初始化指针 57

2.4.2 基本指针操作 60

2.4.3 动态内存分配——new操作 64

2.4.4 关于引用形参的注释 65

2.5 本章小结 68

3.1 数据结构，抽象数据类型和实现 73

第3章 数据结构和抽象数据类型 73

3.2 静态数组 77

3.2.1 一维静态数组 78

3.2.2 下标运算 81

3.2.3 数组作为形参 82

3.2.4 越界错误 83

3.2.5 数组的问题 86

3.3 多维数组 88

3.3.1 二维数组 88

3.3.2 高维数组 89

3.3.3 数组的数组声明 91

3.3.4 多维数组作函数参数 95

3.4 动态数组 97

3.4.1 new操作——动态数组 98

3.4.2 指针的其他用法 110

3.5 C风格结构（可选） 112

指向结构的指针 116

3.6 过程式编程 117

过程式编程的例子 118

3.7 本章小结 123

4.1 过程式编程vs．面向对象编程 129

第4章 OOP和ADT进阶——类 129

4.2 类 130

4.2.1 “传统的”（C）结构和OOP（C＋＋）结构以及类之间的区别 131

4.2.2 类声明 131

4.3 例子：用户定义的Time类的第一个版本 135

4.3.1 为什么不使所有成员都公有化 137

4.3.2 实现一个类 138

4.3.3 一些现象 141

4.4 类构造函数 142

4.5.1 复制操作——初始化和赋值 150

4.5 其他类操作 150

4.5.2 访问函数和更动函数 151

4.5.3 重载运算符 153

4.5.4 重载输入／输出运算符 154

4.5.5 其他操作：前进和关系操作 161

4.5.6 总结以及其他一些细节 163

4.5.7 指向类对象的指针 167

4.5.8 this指针 168

4.6 本章小结 171

第5章 标准C＋＋输入／输出和字符串类 176

5.1 C＋＋标准I/O类 177

5.1.1 istream类 178

5.1.2 ostream类 182

5.1.3 文件I/O:ifstream和ofstream类 186

5.1.4 I/O类层次 188

5.2 C++ String类型 192

5.2.1 C风格的字符串 193

5.2.2 一个字符串类 195

5.2.3 C++ String类 196

5.2.4 String流 204

5.3 案例学习：文本编辑 208

5.4 模式匹配介绍（可选） 216

5.5 数据加密介绍（可选） 219

5.5.1 数据加密标准（Data Encryption Standard） 222

5.5.2 公共密钥加密（Public-Key Encryption） 222

5.6 本章小结 224

第6章 列表 228

6.1 作为ADT的列表 229

设计和创建一个列表类 230

6.2.1 选择存储结构 231

6.2 基于数组的列表实现 231

6.2.2 实现操作 232

6.2.3 一个使用静态数组存储的列表类 234

6.3 使用动态分配的基于数组实现的列表 242

6.3.1 类中的动态分配——析构函数、复制构造函数和赋值运算符 246

6.3.2 最后一点 253

6.4 对链表的介绍 257

6.4.1 它们是什么 257

6.4.2 实现基本列表操作 258

6.4.3 小结 262

6.5.1 节点结构 264

6.5 在C＋＋中基于指针来实现链表 264

6.5.2 链表实现中的数据成员 266

6.5.3 链表实现中的函数成员 267

6.6 基于数组的链表实现 271

6.6.1 节点结构 272

6.6.2 存储池管理 274

6.7 本章小结 276

第7章 栈 280

7.1 栈的介绍 281

7.2.1 选择存储结构 285

7.2 设计和创建一个Stack类——基于数组 285

7.2.2 实现操作 288

7.2.3 实现pop操作的算法 290

7.2.4 完整的Stack类 290

7.2.5 使用动态数组存储栈元素 296

7.2.6 前瞻 309

7.3 链式栈 312

7.3.1 选择存储结构 313

7.3.2 实现操作 314

7.3.3 完整的Stack类：链表版本 317

7.4 栈在函数调用中的使用 324

7.5 案例学习：后缀（RPN）表示 329

7.5.1 计算后缀表达式 330

7.5.2 将中缀表达式转换成后缀表达式 331

7.6 本章小节 341

第8章 队列 345

8.1 队列入门 345

8.2 设计和创建一个Queue类——基于数组 353

8.2.1 使用静态数组存储队列元素 356

8.2.2 使用动态数组存储队列元素 361

8.3.1 一种自然的链表实现 365

8.3 链式队列 365

8.3.2 使用循环链表 374

8.4 队列的应用：缓冲区和调度 376

8.5 案例学习：信息中心仿真 379

8.5.1 问题分析和需求规格说明 380

8.5.2 创建一个Simulation类 380

8.5.3 Time类和Call类 389

8.6 本章小结 390

第9章 ADT实现：模板和标准容器 393

9.1.1 从算法到算法 394

9.1 介绍：可重用性和通用性的发展 394

9.1.2 从数据到容器 396

9.2 函数通用性——重载和模板 396

9.2.1 重载 397

9.2.2 函数模板 399

9.2.3 另一个例子：显示一个数组 403

9.3 类通用性——模板 404

9.3.1 Typedef有什么错 404

9.3.2 类模板 405

9.3.3 Stack类模板的另一个版本 417

9.3.4 对标准C＋＋容器类模板的快速一瞥 418

9.4 vector容器 420

9.4.1 定义vector对象 421

9.4.2 一些vector操作 423

9.4.3 内部实现一瞥——增加容量 427

9.4.4 对迭代器的第一次探讨 430

9.4.5 一些牵涉到迭代器的vector函数成员 433

9.4.6 综合比较：vector对数组 434

9.5 案例学习：计算机系统登录统计 438

9.6.1 二维vector对象 443

9.6 多维vector（可选） 443

9.6.2 二维vector操作 444

9.7 其他标准容器——deque、stack以及queue 447

9.7.1 STL的deque类模板 447

9.7.2 我们的stack类模板的一个新（但是非必须的）版本 450

9.7.3 STL的stack适配器 452

9.7.4 STL的queue适配器 453

9.8 Bitset和Valarray（可选） 454

9.8.1 Bitset 454

9.8.2 Valarray 456

9.8.3 Slics、Mask、以及间接数组 458

9.9 本章小结 459

第10章 ADT实现——递归、算法分析以及标准算法 464

10.1 递归 464

10.1.1 递归的例子 465

10.1.2 递归函数的编码 466

10.1.3 糟糕递归的例子：Fibonacci数字 468

10.1.4 例子：折半查找 470

10.1.5 例子：回文检查程序 473

10.2.1 Hanoi塔 478

10.2 递归的例子：Hanoi塔：分析 478

10.2.2 分析 481

10.3 实现递归 485

10.4 算法效率 489

10.5 C＋＋中的标准算法 500

10.5.1 例：STL的sort算法 500

10.5.2 STL算法的例子 505

10.5.3 ＜numeric＞库中的算法 506

10.5.4 例：花样滑冰评判 507

10.6 算法正确性证明（可选） 508

10.6.1 例：计算平均值 509

10.6.2 例：递归求幂函数 510

10.6.3 总结 511

10.7 本章小节 513

第11章 其他链表结构 519

11.1 单向链表的某些变种 519

11.1.1 带头节点的链表 519

11.1.2 循环链表 522

11.2 稀疏多项式的链式实现 526

11.3.1 双向链表 534

11.3 双向链表和标准C++list 534

11.3.2 标准list类模板 536

11.3.3 例：互联网地址 542

11.3.4 对C＋＋中list的内部一瞥 546

11.4 案例学习：长整数运算 551

11.4.1 问题 551

11.4.2 设计 551

11.4.3 实现 553

11.5.1 多序列表 560

11.5 其他链列表 560

11.5.2 稀疏矩阵 561

11.5.3 广义表 563

11.6 本章小结 566

第12章 二叉树和散列表 571

12.1 线性查找和折半查找的复习 571

12.1.1 线性查找 572

12.1.2 折半查找 573

12.2 二叉树的介绍 576

12.2.1 树的定义 577

12.2.2 二叉树的一些例子 578

12.2.3 二叉树的数组表示 579

12.2.4 二叉树的链表表示 581

12.3 作为递归数据结构的二叉树 583

12.4 二叉查找树 589

12.4.1 BST的实现 590

12.4.2 遍历BST 592

12.4.3 BST的查找 596

12.4.4 BST中的插入操作 599

12.4.5 从BST中删除一个节点 602

12.4.6 不平衡（Lopsidedness）问题 612

12.5 案例学习：计算机登录验证 616

12.5.1 问题 616

12.5.2 设计 616

12.5.3 编码 617

12.6 线索化二叉查找树（可选） 620

12.7 散列表 624

12.7.1 散列函数 625

12.7.2 冲突处理策略 626

12.7.3 改进 627

12.8 本章小结 631

第13章 排序 636

13.1 某些计算时间为O（n2）的排序方法 637

13.1.1 选择排序 637

13.1.2 交换排序 639

13.1.3 插入排序 641

13.1.4 排序算法的性能比较 643

13.1.5 间接排序 644

13.2 堆、堆排序和优先队列 647

13.2.1 堆 648

13.2.2 堆的基本操作 649

13.2.3 堆排序 652

13.2.4 STL中的堆算法 655

13.2.5 堆和优先队列 658

13.3 快速排序 662

13.3.1 拆分操作 663

13.3.2 快速排序 665

13.3.3 改进 668

13.4 归并排序 670

13.4.1 归并列表 670

13.4.2 折半归并排序 672

13.4.3 自然归并排序 674

13.5 基数排序（Radix Sort） 677

13.6 本章小结 680

第14章 OOP和ADT 684

14.1 OOP和ADT的简要历史和概览 684

14.1.1 封装性 685

14.1.2 继承性 686

14.1.3 多态性和动态联编 687

14.2 继承和面向对象设计 688

14.2.1 第1个例子：许可证 689

14.2.2 公有、私有和保护域 693

14.2.3 派生类的形式 693

14.2.4 类之间的Is-a、Has-a和Uses-a关系 694

14.3 创建派生类 696

14.3.1 派生类构造函数 697

14.3.2 访问继承的数据成员 697

14.3.3 复用操作 698

14.3.4 例子：栈和有限栈 700

14.4.1 问题 703

14.4.2 设计 703

14.4 案例学习：工资 703

14.5 多态性、虚函数和ADT 711

14.5.1 为什么需要多态性：联编问题 711

14.5.2 虚函数和动态联编 713

14.5.3 例1：使用句柄 716

14.5.4 例2：栈和有限栈 717

14.5.5 纯虚函数和抽象类 720

14.6 案例学习：异构数据结构 722

14.6.1 虚函数的必要性 723

14.7 本章小结 726

第15章 树 729

15.1 案例学习：哈夫曼编码 729

15.1.1 变长码 730

15.1.2 立刻可解码性 730

15.1.3 哈夫曼编码 731

15.2 平衡树：AVL树 735

15.2.1 例子：州简称的BST 735

15.2.2 基本的重新平衡旋转操作 743

15.3 2-3-4树、红-黑树、B-树和其他树 748

15.3.1 2-3-4树 750

15.3.2 红-黑树 756

15.3.3 B-树 760

15.3.4 用二叉树来表示树和森林 761

15.4 STL中的关联容器——map（可选） 765

15.5 本章小结 771

第16章 图和有向图 773

16.1 有向图 773

16.1.1 邻接矩阵表示（Adjacency-Matrix Representation） 775

16.1.2 邻接表表示（Adjacency-List Representation） 776

16.2 搜索和遍历有向图 781

16.2.1 深度优先搜索 782

16.2.2 广度优先搜索 783

16.2.3 遍历和最短路经问题 785

16.2.4 NP完全性问题 794

16.3 图 796

16.3.1 邻接矩阵和邻接表表示 797

16.3.2 边列表表示 798

16.3.3 连通性 799

16.4 本章小结 810

附录A ASCll字符集 812

附录B 小测验答案 814