数据结构与面向对象程序设计 C++版PDF电子书下载

第1章 软件开发阶段 1

1.1 规范说明、设计和实现 2

1.1.1 概念设计：问题分解 3

1.1.2 前置条件和后置条件 4

1.1.3 使用其他程序员提供的函数 6

1.1.4 有关ANSI/ISOC＋＋标准的实现问题 7

1.1.5 自测习题 12

1.2 运行时间分析 13

1.2.1 台阶计数问题 13

1.2.2 大O表示法 17

1.2.3 C＋＋函数的时间分析 18

1.2.4 最坏情况、平均情况和最好情况下的时间分析 20

1.2.5 自测习题 20

1.3 测试和调试 21

1.3.1 选择测试数据 21

1.3.2 边界值 22

1.3.3 完全代码测试 22

1.3.4 调试 23

1.3.5 自测习题 23

1.4 本章小结 24

1.5 自测习题答案 24

第2章 抽象数据类型和C＋＋类 27

2.1 类和成员 28

2.1.1 编程示例：节流阀类 28

2.1.2 使用类 31

2.1.3 节流阀类的示范程序 33

2.1.4 实现成员函数 34

2.1.5 自测习题 37

2.2 构造函数 37

2.2.1 节流阀类的构造函数 38

2.2.2 修改节流阀类的成员函数 40

2.2.3 内联成员函数 41

2.2.4 自测习题 42

2.3 使用命名空间、头文件和实现文件 42

2.3.1 创建命名空间 42

2.3.2 头文件 43

2.3.3 实现文件 47

2.3.4 使用命名空间中的数据项 49

2.3.5 自测习题 51

2.4 类和参数 52

2.4.1 编程示例：point类 52

2.4.2 默认参数 55

2.4.3 参数 57

2.4.4 当函数返回值的类型是类时 62

2.4.5 自测习题 63

2.5 操作符重载 64

2.5.1 重载二元比较操作符 64

2.5.2 重载二元算术操作符 65

2.5.3 重载输出和输入操作符 66

2.5.4 友元函数 69

2.5.5 Point类——内容汇总 70

2.5.6 操作符重载的总结 72

2.5.7 自测习题 73

2.6 本章小结 73

2.7 自测习题答案 74

2.8 编程项目 77

第3章 容器类 85

3.1 包类 85

3.1.1 包类——规范说明 86

3.1.2 包类——文档说明 92

3.1.3 包类——示范程序 93

3.1.4 包类——设计 95

3.1.5 类的不变式 96

3.1.6 包类——实现 97

3.1.7 包类——内容汇总 103

3.1.8 包类——测试 106

3.1.9 包类——分析 107

3.1.10 自测习题 108

3.2 编程项目：序列类 109

3.2.1 序列类——规范说明 109

3.2.2 序列类——文档说明 112

3.2.3 序列类——设计 114

3.2.4 序列类——实现的伪代码 115

3.2.5 自测习题 117

3.3 交互式测试程序 117

3.4 本章小结 122

3.5 自测习题答案 123

3.6 编程项目 125

第4章 指针和动态数组 131

4.1 指针和动态内存 131

4.1.1 指针变量 132

4.1.2 使用指针的赋值操作符 134

4.1.3 动态变量和new操作符 135

4.1.4 使用new分配动态数组 136

4.1.5 堆和bad_alloc异常 138

4.1.6 操作符delete 139

4.1.7 自测习题 140

4.2 指针和数组作为参数 141

4.2.1 指针作为值参数 141

4.2.2 数组参数 143

4.2.3 指针或数组作为常量参数 144

4.2.4 指针作为引用参数 145

4.2.5 自测习题 147

4.3 用动态数组实现的包类 149

4.3.1 指针成员变量 150

4.3.2 成员函数按需分配动态内存 151

4.3.3 值语义 154

4.3.4 析构函数 156

4.3.5 修改后的包类——类定义 157

4.3.6 修改后的包类——实现 159

4.3.7 修改后的包类——内容汇总 163

4.3.8 自测习题 165

4.4 有关动态类的规定 166

4.4.1 4条规则 166

4.4.2 复制构造函数的特殊重要性 166

4.4.3 自测习题 167

4.5 编程项目：字符串类 167

4.5.1 以null终结的字符串 167

4.5.2 初始化字符串变量 168

4.5.3 空字符串 168

4.5.4 读写字符串变量 169

4.5.5 函数strcpy 169

4.5.6 函数strcat 170

4.5.7 函数strlen 170

4.5.8 函数strcmp 171

4.5.9 字符串类——规范说明 171

4.5.10 字符串类——设计 175

4.5.11 字符串类——实现 175

4.5.12 字符串类的示范程序 177

4.5.13 串接输出操作符 178

4.5.14 声明常量对象 179

4.5.15 产生构造函数的转换 179

4.5.16 在表达式中使用重载的操作符 180

4.5.17 本文的字符串类与C＋＋库中的字符串类 180

4.5.18 自测习题 180

4.6 编程项目：多项式 180

4.7 本章小结 184

4.8 自测习题答案 184

4.9 编程项目 186

第5章 链表 189

5.1 链表的基本节点类 189

5.1.1 为节点声明类 190

5.1.2 在链表节点中使用typedef语句 191

5.1.3 头指针和尾指针 191

5.1.4 空指针 192

5.1.5 头指针或尾指针为NULL时的含义 193

5.1.6 节点构造函数 193

5.1.7 节点成员函数 194

5.1.8 成员选择操作符 195

5.1.9 自测习题 198

5.2 链表工具包 199

5.2.1 链表工具包——头文件 199

5.2.2 计算链表的长度 200

5.2.3 链表的参数 203

5.2.4 在链表头插入一个新节点 204

5.2.5 在非头节点处插入一个新节点 206

5.2.6 在链表中查找数据项 210

5.2.7 在链表中根据节点的位置寻找节点 211

5.2.8 复制链表 212

5.2.9 从链表头删除节点 215

5.2.10 删除链表中不在头部的节点 216

5.2.11 清除链表 217

5.2.12 链表工具包——内容汇总 218

5.2.13 使用链表工具包 222

5.2.14 自测习题 222

5.3 用链表实现的包类 223

5.3.1 第三个包——规范说明 223

5.3.2 第三个包——类定义 223

5.3.3 如何匹配包的value_type和节点的value_type 226

5.3.4 在类中使用动态内存应当遵循的规则 227

5.3.5 第三个包类——实现 227

5.3.6 第三个包类——内容汇总 234

5.3.7 自测习题 236

5.4 编程项目：用链表实现的序列类 237

5.4.1 修改的序列类——设计建议 237

5.4.2 修改后的序列类——值语义 238

5.4.3 自测习题 239

5.5 动态数组、链表和双向链表 239

5.5.1 做出抉择 241

5.5.2 自测习题 241

5.6 本章小结 241

5.7 自测习题答案 242

5.8 编程项目 246

第6章 利用模板、迭代器和STL进行软件开发 251

6.1 模板函数 251

6.1.1 模板函数的语法 253

6.1.2 使用模板函数 253

6.1.3 模板函数——交换两个值 255

6.1.4 模板函数的参数匹配 256

6.1.5 模板函数——在数组中寻找最大项 257

6.1.6 模板函数——在排序数组中插入一个数据项 258

6.1.7 自测习题 260

6.2 模板类 260

6.2.1 模板类的语法 260

6.2.2 关于模板实现文件的其他内容 262

6.2.3 模板类成员函数的参数匹配 267

6.2.4 使用模板类 267

6.2.5 编故事程序的细节 270

6.2.6 自测习题 270

6.3 标准模板类及其迭代器 271

6.3.1 多集模板类 271

6.3.2 多集成员 272

6.3.3 迭代器和［...）模式 272

6.3.4 测试迭代器的等同性 274

6.3.5 其他多集操作 274

6.3.6 集合算法 275

6.3.7 无效的迭代器 276

6.3.8 迭代器的标准类别 277

6.3.9 数组的迭代器 278

6.3.10 标准模板库列表类 279

6.3.11 自测习题 280

6.4 节点模板类 280

6.4.1 返回引用类型的函数 281

6.4.2 将引用返回值复制到别处时发生的情况 283

6.4.3 成员函数data目前需要两个版本 283

6.4.4 新节点的头文件和实现文件 283

6.4.5 自测习题 290

6.5 链表的迭代器 291

6.5.1 节点迭代器 291

6.5.2 节点迭代器源自std∷iterator 293

6.5.3 节点迭代器的私有成员变量 293

6.5.4 节点迭代器——构造函数 293

6.5.5 节点迭代器——＊操作符 293

6.5.6 节点迭代器——操作符＋＋的两个版本 294

6.5.7 节点迭代器——相等和不相等的比较 295

6.5.8 常量集合的迭代器 296

6.5.9 自测习题 297

6.6 含有迭代器的包模板类的链表版本 298

6.6.1 如何为容器类提供迭代器 298

6.6.2 包迭代器 299

6.6.3 将迭代器定义在包中的原因 299

6.6.4 自测习题 306

6.7 本章小结和5个包的总结 306

6.8 自测习题答案 307

6.9 编程项目 311

第7章 堆栈 313

7.1 堆栈和STL堆栈的简介 313

7.1.1 标准库的堆栈类 315

7.1.2 编程示例：翻转单词 316

7.1.3 自测习题 316

7.2 堆栈的应用 317

7.2.1 编程示例：括号的平衡 317

7.2.2 编程示例：算术表达式求值 319

7.2.3 算术表达式求值——规范说明 319

7.2.4 算术表达式求值——设计 319

7.2.5 算术表达式求值——实现 325

7.2.6 计算器程序使用的函数 325

7.2.7 算术表达式求值——测试与分析 325

7.2.8 算术表达式求值——改进 326

7.2.9 自测习题 326

7.3 堆栈类的实现 327

7.3.1 堆栈的数组实现 327

7.3.2 堆栈的链表实现 330

7.3.3 Koenig查找 333

7.3.4 自测习题 333

7.4 更复杂的堆栈应用 334

7.4.1 后缀表达式求值 334

7.4.2 将中缀表示法转换成后缀表示法 336

7.4.3 在中缀表达式中使用优先级规则 338

7.4.4 中缀转换为后缀的正确性 340

7.4.5 自测习题 341

7.5 本章小结 342

7.6 自测习题答案 342

7.7 编程项目 344

第8章 队列 349

8.1 队列和STL队列的简介 349

8.1.1 标准库的队列类 350

8.1.2 队列的使用 350

8.1.3 自测习题 352

8.2 队列的应用 352

8.2.1 编程示例：识别回文 352

8.2.2 自测习题 355

8.2.3 编程示例：洗车模拟 355

8.2.4 洗车模拟——规范说明 355

8.2.5 洗车模拟——设计 355

8.2.6 洗车模拟——实现洗车类 358

8.2.7 洗车模拟——实现模拟函数 363

8.2.8 自测习题 365

8.3 队列类的实现 365

8.3.1 队列的数组实现 365

8.3.2 有关队列中循环数组实现的讨论 369

8.3.3 队列的链表实现 371

8.3.4 实现细节 372

8.3.5 自测习题 377

8.4 优先队列 377

8.4.1 如何指定优先级 378

8.4.2 标准库的优先队列类 378

8.4.3 优先队列类——实现思想 379

8.4.4 自测习题 379

8.5 堆栈、队列和优先队列类的引用返回值 379

8.6 本章小结 380

8.7 自测习题答案 380

8.8 编程项目 381

第9章 递归思想 385

9.1 递归函数 385

9.1.1 递归思想的第一个例子 385

9.1.2 跟踪递归调用 387

9.1.3 编程示例：write_vertical的一个扩展 388

9.1.4 深入分析递归 389

9.1.5 成功递归函数的一般形式 392

9.1.6 自测习题 392

9.2 递归的研究：分形和迷宫 393

9.2.1 编程示例：产生随机分形 393

9.2.2 用于产生随机分形的函数——规范说明 395

9.2.3 分形函数的设计和实现 396

9.2.4 如何显示随机分形 398

9.2.5 编程示例：穿越迷宫 399

9.2.6 穿越迷宫——规范说明 399

9.2.7 穿越迷宫——设计 401

9.2.8 穿越迷宫——实现 401

9.2.9 运用回溯穷举搜索的递归模式 403

9.2.10 编程示例：玩具熊游戏 404

9.2.11 自测习题 406

9.3 推导递归 406

9.3.1 如何确保没有无限递归 408

9.3.2 归纳推导递归函数的正确性 410

9.3.3 自测习题 411

9.4 本章小结 411

9.5 自测习题答案 412

9.6 编程项目 414

第10章 树 419

10.1 树的简介 419

10.1.1 二叉树 419

10.1.2 二叉分类树 422

10.1.3 一般树 422

10.1.4 自测习题 423

10.2 树的表示法 424

10.2.1 完全二叉树的数组表示法 424

10.2.2 使用节点类表示二叉树 427

10.2.3 自测习题 428

10.3 二叉树节点类 429

10.3.1 编程示例：猜动物 432

10.3.2 动物猜测程序——设计和实现 434

10.3.3 动物猜测程序——改进 438

10.3.4 自测习题 441

10.4 树的遍历 441

10.4.1 二叉树的遍历 441

10.4.2 从树的节点中输出数据 445

10.4.3 遍历中的问题 446

10.4.4 函数作为参数 447

10.4.5 apply函数的一个模板版本 448

10.4.6 使apply模板函数更具有通用性 449

10.4.7 树遍历的模板函数 450

10.4.8 自测习题 451

10.5 二叉搜索树 458

10.5.1 二叉搜索树存储机制 458

10.5.2 第6个包——类定义 462

10.5.3 第6个包——某些简单函数的实现 462

10.5.4 计算某个元素在二叉搜索树中出现的次数 462

10.5.5 添加一个新元素到二叉搜索树中 463

10.5.6 从二叉搜索树中移除某个元素 464

10.5.7 二叉搜索树的组合操作符 467

10.5.8 时间分析和迭代器 469

10.5.9 自测习题 469

10.6 本章小结 469

10.7 自测习题答案 470

10.8 编程项目 473

第11章 树项目 479

11.1 堆 479

11.1.1 堆的存储规则 479

11.1.2 使用堆结构实现的优先队列ADT 480

11.1.3 插入新项 480

11.1.4 删除项 482

11.1.5 自测习题 484

11.2 B树 484

11.2.1 非平衡树的问题 484

11.2.2 B树的规则 485

11.2.3 B树的一个示例 486

11.2.4 B树实现的集合ADT 487

11.2.5 在B树中查找项 491

11.2.6 在B树中插入项 493

11.2.7 B树的松散插入操作 493

11.2.8 修正子节点多余项的私有成员函数 495

11.2.9 回到成员函数Insert 496

11.2.10 采用自顶向下方法设计 497

11.2.11 从B树中删除项 498

11.2.12 B树的松散删除操作 499

11.2.13 解决子节点项短缺问题的私有成员函数 501

11.2.14 从B树中删除最大的项 503

11.2.15 外部B树 505

11.2.16 自测习题 505

11.3 树、日志和时间分析 506

11.3.1 二叉搜索树的时间分析 506

11.3.2 堆的时间分析 507

11.3.3 对数运算 508

11.3.4 对数级算法 509

11.3.5 自测习题 510

11.4 本章小结 510

11.5 自测习题答案 510

11.6 编程项目 513

第12章 查找 515

12.1 顺序查找和二分查找 515

12.1.1 顺序查找 515

12.1.2 顺序查找——分析 516

12.1.3 二分查找 517

12.1.4 二分查找——设计 518

12.1.5 二分查找——分析 520

12.1.6 标准库查找函数 523

12.1.7 用于有序域的函数 523

12.1.8 用于无序域的函数 525

12.1.9 STL查找函数 526

12.1.10 自测习题 526

12.2 开地址散列 526

12.2.1 散列简介 526

12.2.2 表类——声明 529

12.2.3 表类——设计 530

12.2.4 表ADT——实现 533

12.2.5 选择散列函数来减少冲突 538

12.2.6 再散列减少聚类 538

12.2.7 自测习题 540

12.3 链式散列 540

12.3.1 链式散列 540

12.3.2 自测习题 542

12.4 散列的时间分析 542

12.4.1 散列表的装填因子 542

12.4.2 自测习题 545

12.5 程序设计：使用STL向量的表类 545

12.5.1 新表类 545

12.5.2 在新表类中使用向量 545

12.5.3 常量模板参数 545

12.5.4 函数模板参数 546

12.5.5 实现新表类 546

12.5.6 自测习题 547

12.6 STL中的匹配和多重匹配 547

12.7 本章小结 548

12.8 自测习题答案 549

12.9 编程项目 552

第13章 排序 555

13.1 二次排序算法 555

13.1.1 选择排序——规范说明 555

13.1.2 选择排序——设计 556

13.1.3 选择排序——实现 558

13.1.4 选择排序——分析 560

13.1.5 插入排序 561

13.1.6 插入排序——分析 564

13.1.7 自测习题 566

13.2 递归排序算法 567

13.2.1 使用递归的分治法 567

13.2.2 合并排序 569

13.2.3 合并函数 571

13.2.4 动态内存在合并排序中的应用 575

13.2.5 合并排序——分析 575

13.2.6 文件的合并排序 577

13.2.7 快速排序 577

13.2.8 partition函数 579

13.2.9 快速排序——分析 581

13.2.10 快速排序——选择一个好的基准元素 583

13.2.11 自测习题 583

13.3 使用堆的O（n log n）算法 584

13.3.1 堆排序 584

13.3.2 构建堆 589

13.3.3 向下重排 590

13.3.4 堆排序——分析 591

13.3.5 自测习题 592

13.4 使用库函数排序和随机访问迭代器 592

13.4.1 原始C qusort函数 592

13.4.2 STL排序函数 593

13.4.3 使用迭代器编写一个排序函数 593

13.5 本章小结 594

13.6 自测习题答案 595

13.7 编程项目 597

第14章 派生类和继承 601

14.1 派生类 601

14.1.1 如何声明派生类 603

14.1.2 派生类的自动构造函数 604

14.1.3 使用派生类 605

14.1.4 派生类的自动赋值操作符 606

14.1.5 派生类的自动析构函数 607

14.1.6 覆盖继承的成员函数 607

14.1.7 自测习题 608

14.2 仿真生态系统 608

14.2.1 实现部分生物对象层次 609

14.2.2 organism类 609

14.2.3 animal类：具有新私有成员变量的派生类 612

14.2.4 如何为派生类提供新的构造函数 612

14.2.5 animal类的其他成员函数 614

14.2.6 自测习题 617

14.2.7 Herbivore类 618

14.2.8 池塘生活仿真程序 620

14.2.9 池塘生活——实现细节 623

14.2.10 使用池塘模型 624

14.2.11 动态内存的使用 625

14.2.12 自测习题 625

14.3 虚拟成员函数和game类 625

14.3.1 game类简介 626

14.3.2 受保护的成员 629

14.3.3 虚拟成员函数 629

14.3.4 虚拟析构函数 630

14.3.5 游戏类的受保护虚拟成员函数 630

14.3.6 玩Connect Four游戏的派生类 631

14.3.7 Connect Four游戏类的私有成员变量 631

14.3.8 Connect Four的构造函数和重启函数 633

14.3.9 三个处理游戏状态的Connect Four函数 633

14.3.10 三个处理移动的Connect Four函数 634

14.3.11 Clone函数 634

14.3.12 编写派生自game类的游戏 635

14.3.13 使用minimax的游戏类的play算法 635

14.3.14 自测习题 638

14.4 本章小结 638

14.5 进阶阅读 639

14.6 自测习题答案 639

14.7 编程项目 643

第15章 图 645

15.1 图的定义 645

15.1.1 无向图 645

15.1.2 有向图 648

15.1.3 图的更多术语 649

15.1.4 航线的例子 650

15.1.5 自测习题 650

15.2 图的实现 651

15.2.1 使用邻接矩阵表示图 651

15.2.2 使用二维数组存储邻接矩阵 652

15.2.3 使用边列表表示图 652

15.2.4 使用边集表示图 653

15.2.5 哪种表示方法最好 653

15.2.6 编程示例：标签图类 654

15.2.7 用于增加顶点和边的成员函数 655

15.2.8 标签图类——重载下标操作符 655

15.2.9 下标操作符的常量版本 656

15.2.10 标签图类——函数neighbors 657

15.2.11 标签图类——实现 657

15.2.12 自测习题 657

15.3 图的遍历 662

15.3.1 深度优先搜索 663

15.3.2 宽度优先搜索 666

15.3.3 深度优先搜索——实现 668

15.3.4 宽度优先搜索——实现 669

15.3.5 自测习题 669

15.4 路径算法 671

15.4.1 判断某条路径是否存在 671

15.4.2 具有加权边的图 672

15.4.3 最短距离算法 672

15.4.4 最短路径算法 680

15.4.5 自测习题 681

15.5 本章小结 681

15.6 自测习题答案 681

15.7 编程项目 683

附录A ASCII字符集类 687

附录B 大O表达式 689

附录C 操作符的优先顺序 693

附录D 命令行编译和链接 695

附录E 使用旧式编译器 699

附录F C＋＋的输入和输出 703

附录G 选择库函数 711

附录H 标准模板类简介 715

附录I useful函数的工具箱 725

附录J 基本格式指南 729

附录K 下载GNU编译器和软件 731

附录L 异常处理 733