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

第1章 软件开发的阶段 1

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

1.1.1 概念设计：问题分解 3

1.1.2 前置条件与后置条件 4

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

1.1.4 有关ANSI/ISO C++标准的实现问题 8

1.1.5 本节自测练习 11

1.2 运行时间分析 12

1.2.1 台阶计数问题 12

1.2.2 大O表示法 16

1.2.3 C++函数的时间分析 17

1.2.4 最坏情况、平均情况以及最好情况下的时间分析 19

1.2.5 本节自测练习 19

1.3 测试与调试 20

1.3.1 选择测试数据 20

1.3.2 边界值 20

1.3.3 完全代码测试 21

1.3.4 调试 21

1.3.5 本节自测练习 22

1.4 本章小结 22

本章自测练习参考答案 23

第2章 抽象数据类型与C++类 25

2.1 类与成员 25

2.1.1 编程示例：节流阀类throttle 25

2.1.2 使用类 29

2.1.3 throttle类的演示小程序 30

2.1.4 实现成员函数 31

2.1.5 可以调用其他成员的成员函数 34

2.1.6 本节自测练习 34

2.2 构造函数 35

2.2.1 throttle类的构造函数 35

2.2.2 修订throttle类的成员函数 37

2.2.3 内联成员函数 38

2.2.4 本节自测练习 39

2.3 使用名称空间、头文件与实现文件 39

2.3.1 创建名称空间 40

2.3.2 头文件 40

2.3.3 实现文件 44

2.3.4 使用名称空间里的数据项 46

2.3.5 本节自测练习 48

2.4 类与参数 49

2.4.1 编程示例：point类 49

2.4.2 参数默认值 52

2.4.3 参数 53

2.4.4 当函数的返回值的数据类型为类时 58

2.4.5 本节自测练习 59

2.5 操作符重载 60

2.5.1 二元比较操作符重载 60

2.5.2 二元算术操作符重载 61

2.5.3 输入输出操作符重载 62

2.5.4 友元函数 64

2.5.5 point类汇总 66

2.5.6 操作符重载小结 68

2.5.7 本节自测练习 69

2.6 标准模板库与pair类 69

2.7 本章小结 70

本章自测练习参考答案 71

编程项目 73

第3章 容器类 81

3.1 bag类 81

3.1.1 bag类的规范说明 81

3.1.2 bag类的文档说明 88

3.1.3 bag类的演示程序 91

3.1.4 bag类的设计 93

3.1.5 类的不变式 94

3.1.6 bag类的实现 95

3.1.7 bag类的集成 101

3.1.8 bag类的测试 104

3.1.9 bag类的分析 105

3.1.10 本节自测练习 106

3.2 编程项目：sequence类 107

3.2.1 sequence类的规范说明 107

3.2.2 sequence类的文档说明 111

3.2.3 sequence类的设计 113

3.2.4 sequence类的伪代码实现 114

3.2.5 本节自测练习 116

3.3 交互式测试程序 116

本节自测练习 121

3.4 STL中的multiset类及其迭代器 122

3.4.1 multiset模板类 122

3.4.2 multiset类的一些成员 123

3.4.3 迭代器与［…）模式 123

3.4.4 测试迭代器的相等性 126

3.4.5 multiset类的其他操作符 126

3.4.6 不合法的迭代器 126

3.4.7 本节自测练习 128

3.5 本章小结 128

本章自测练习参考答案 128

编程项目 131

第4章 指针与动态数组 138

4.1 指针与动态内存 138

4.1.1 指针变量 139

4.1.2 指针与赋值操作符一起使用 140

4.1.3 动态变量new操作符 142

4.1.4 使用new操作符为动态数组分配内存 143

4.1.5 内存堆与bad_alloc异常 144

4.1.6 delete操作符 145

4.1.7 本节自测练习 147

4.2 把指针与数组作为参数 147

4.2.1 以指针作为值参数 147

4.2.2 数组参数 149

4.2.3 以指针或数组作为常量参数 150

4.2.4 以指针作为引用参数 152

4.2.5 本节自测练习 153

4.3 具有动态数组的bag类 156

4.3.1 指针成员变量 156

4.3.2 成员函数按需分配内存 157

4.3.3 值语义 161

4.3.4 析构函数 163

4.3.5 修订后的bag类定义 164

4.3.6 修订后的bag类实现 165

4.3.7 修订后的bag类集成 170

4.3.8 本节自测练习 172

4.4 有关动态类的说明 172

4.4.1 4条规则 173

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

4.4.3 本节自测练习 174

4.5 STL的string类与编程项目 174

4.5.1 以null结尾的字符串 174

4.5.2 初始化字符串变量 175

4.5.3 空字符串 175

4.5.4 读写字符串变量 175

4.5.5 strcpy函数 176

4.5.6 strcat函数 177

4.5.7 strlen函数 177

4.5.8 strcmp函数 178

4.5.9 string类的规范说明 178

4.5.10 string类的构造函数 180

4.5.11 重载operator[] 181

4.5.12 其他重载成员 181

4.5.13 string类的其他操作 182

4.5.14 string类的设计 182

4.5.15 string类的实现 183

4.5.16 string类的演示程序 185

4.5.17 串联输出操作符 186

4.5.18 明常量对象 187

4.5.19 由构造函数产生的类型转换 187

4.5.20 在表达式中使用已重载的操作符 187

4.5.21 本章设计的string类与C++库的string类 188

4.5.22 本节自测练习 188

4.6 编程项目：polynomial类 188

4.7 本章小结 191

本章自测练习参考答案 192

编程项目 194

第5章 链表 196

5.1 链表的基本节点类 196

5.1.1 为节点声明类 196

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

5.1.3 头指针和尾指针 197

5.1.4 空指针NULL 198

5.1.5 头指针或尾指针为NULL的含义 199

5.1.6 节点类构造函数 199

5.1.7 节点类成员函数 200

5.1.8 成员选择操作符 201

5.1.9 本节自测练习 204

5.2 链表工具包 205

5.2.1 链表工具包的头文件 205

5.2.2 计算链表的长度 206

5.2.3 链表的参数 209

5.2.4 在链表头插入新节点 210

5.2.5 在非链表头的其他位置插入新节点 212

5.2.6 在链表中查找节点 215

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

5.2.8 链表复制 218

5.2.9 在链表头删除节点 221

5.2.10 在非链表头删除节点 222

5.2.11 清空链表 223

5.2.12 链表工具包的集成 224

5.2.13 使用链表工具包 228

5.2.14 本节自测练习 228

5.3 用链表实现bag类 229

5.3.1 第3个bag类的规范说明 229

5.3.2 第3个bag类的类定义 230

5.3.3 如何使bag类的value_type与节点类的value_type相匹配 233

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

5.3.5 第3个bag类的实现 234

5.3.6 第3个bag类的集成 241

5.3.7 本节自测练习 244

5.4 编程项目：用链表实现sequence类 244

5.4.1 关于修订后的sequence类的设计建议 245

5.4.2 关于修订后的sequence类的值语义 246

5.4.3 本节自测练习 246

5.5 动态数组、链表与双向链表 246

5.5.1 做出抉择 248

5.5.2 本节自测练习 249

5.6 标准模板库的vector、list和deque类 249

本节测试练习 252

5.7 本章小结 252

本章自测练习参考答案 252

编程项目 257

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

6.1 模板函数 261

6.1.1 模板函数的语法 263

6.1.2 使用模板函数 263

6.1.3 交换两个值的模板函数 265

6.1.4 模板函数的参数匹配 266

6.1.5 在数组中查找最大项的模板函数 267

6.1.6 在已排序数组中插入一个数据项的模板函数 268

6.1.7 本节自测练习 270

6.2 模板类 270

6.2.1 模板类的语法 270

6.2.2 进一步了解模板类实现文件 277

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

6.2.4 使用模板类 278

6.2.5 详细讨论上一个演示程序 281

6.2.6 本节自测练习 282

6.3 STL算法与迭代器的使用 282

6.3.1 STL算法 282

6.3.2 标准迭代器的类型 283

6.3.3 数组的迭代器 285

6.3.4 本节自测习题 285

6.4 节点模板类 286

6.4.1 返回引用类型的函数 287

6.4.2 将引用返回值复制到别处时会发生什么 288

6.4.3 这里成员函数data需要两个版本 288

6.4.4 新节点类的头文件和实现文件 289

6.4.5 本节自测练习 297

6.5 链表的迭代器 297

6.5.1 节点迭代器 297

6.5.2 从std::iterator派生而来的节点迭代器 299

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

6.5.4 节点迭代器的构造函数 300

6.5.5 节点迭代器的*操作符 300

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

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

6.5.8 常量集合的迭代器 302

6.5.9 本节自测练习 304

6.6 含迭代器的链表版bag模板类 305

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

6.6.2 bag类迭代器 306

6.6.3 将迭代器定义在bag类中的原因 307

6.6.4 本节自测练习 314

6.7 本章小结与5个bag类的小结 314

本章自测练习答案 315

编程项目 318

第7章 栈 320

7.1 STL的stack类 320

7.1.1 标准库的stack类 321

7.1.2 编程示例：翻转单词 322

7.1.3 本节自测练习 323

7.2 栈的应用 323

7.2.1 编程示例：括号的匹配 323

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

7.2.3 算术表达式求值的规范说明 326

7.2.4 算术表达式求值的设计 326

7.2.5 算术表达式求值的实现 331

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

7.2.7 算术表达式求值的测试与分析 332

7.2.8 算术表达式求值的改进 333

7.2.9 本节自测练习 333

7.3 stack类的实现 334

7.3.1 栈的数组实现 334

7.3.2 栈的链表实现 337

7.3.3 Koenig查找 341

7.3.4 本节自测练习 341

7.4 更复杂的栈应用 342

7.4.1 后缀表达式求值 342

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

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

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

7.4.5 本节自测练习 349

7.5 本章小结 349

本章自测练习答案 350

编程项目 351

第8章 队列 356

8.1 STL队列 356

8.1.1 标准库的队列类 357

8.1.2 队列的使用 358

8.1.3 本节自测练习 359

8.2 队列的应用 359

8.2.1 编程示例：识别回文 359

8.2.2 本节自测练习 361

8.2.3 编程示例：洗车模拟程序 362

8.2.4 洗车模拟程序的规范说明 362

8.2.5 洗车模拟程序的设计 362

8.2.6 实现洗车类 365

8.2.7 实现模拟函数 371

8.2.8 本节自测练习 372

8.3 队列类的实现 373

8.3.1 队列的数组实现 373

8.3.2 有关队列中环形数组实现的讨论 377

8.3.3 队列的链表实现 379

8.3.4 实现细节 380

8.3.5 本节自测练习 384

8.4 实现STL的双端队列 384

8.4.1 为双端队列的value_type项调用析构函数和构造函数 387

8.4.2 栈和队列的其他变体 388

8.4.3 本节自测练习 388

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

8.6 本章小结 389

本章自测练习答案 389

编程项目 390

第9章 递归思想 394

9.1 递归函数 394

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

9.1.2 跟踪递归调用 396

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

9.1.4 深入分析递归 398

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

9.1.6 本节自测练习 402

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

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

9.2.2 产生随机分形的函数及其规范说明 404

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

9.2.4 如何显示随机分形 407

9.2.5 编程示例：穿越迷宫 407

9.2.6 穿越迷宫函数的规范说明 408

9.2.7 穿越迷宫函数的设计 409

9.2.8 穿越迷宫函数的实现 410

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

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

9.2.11 本节自测练习 414

9.3 推导递归 415

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

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

9.3.3 本节自测练习 419

9.4 本章小结 420

本章自测练习答案 420

编程项目 422

第10章 树 427

10.1 树的简介 427

10.1.1 二叉树 427

10.1.2 二叉分类树 430

10.1.3 一般树 430

10.1.4 本节自测练习 431

10.2 树的表示法 431

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

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

10.2.3 本节自测练习 434

10.3 二叉树节点类 435

10.3.1 编程示例：猜测动物程序 439

10.3.2 猜测动物程序的设计与实现 440

10.3.3 猜测动物程序的改进 448

10.3.4 本节自测练习 448

10.4 树的遍历 449

10.4.1 二叉树的遍历 449

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

10.4.3 遍历中的问题 454

10.4.4 函数作为参数 454

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

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

10.4.7 树遍历的模板函数 458

10.4.8 本节自测练习 465

10.5 二叉查找树 466

10.5.1 二叉查找树存储机制 466

10.5.2 第6个bag类的定义 470

10.5.3 第6个bag类的某些简单函数的实现 470

10.5.4 计算某个元素在二叉查找树中出现的次数 471

10.5.5 添加一个新元素到二叉查找树中 472

10.5.6 从二叉查找树中删除某个元素 473

10.5.7 二叉查找树的组合操作符 475

10.5.8 时间分析和迭代器 477

10.5.9 本节自测练习 478

10.6 本章小结 478

本章自测练习答案 479

编程项目 482

第11章 平衡树 487

11.1 堆 487

11.1.1 堆的存储规则 487

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

11.1.3 插入新项 488

11.1.4 删除项 489

11.2 STL优先队列与堆算法 491

本节自测练习 492

11.3 B树 492

11.3.1 非平衡树的问题 493

11.3.2 B树的规则 493

11.3.3 B树的一个示例 495

11.3.4 用B树实现set类 495

11.3.5 在B树中查找项 499

11.3.6 在B树中插入项 501

11.3.7 B树的松散插入操作 501

11.3.8 修正子节点多余项的私有成员函数 503

11.3.9 回到成员函数Insert 504

11.3.10 采用自顶向下方法设计 505

11.3.11 从B树中删除项 505

11.3.12 B树的松散删除操作 506

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

11.3.14 从B树中删除最大的项 510

11.3.15 外部B树 512

11.3.16 本节自测练习 512

11.4 树、日志和时间分析 513

11.4.1 二叉查找树的时间分析 513

11.4.2 堆的时间分析 514

11.4.3 对数运算 515

11.4.4 对数级算法 516

11.4.5 本节自测练习 516

11.5 STL的map类和multimap类 517

11.6 本章小结 518

本章自测练习答案 518

编程项目 521

第12章 查找 523

12.1 顺序查找和二叉查找 523

12.1.1 顺序查找 523

12.1.2 顺序查找的分析 523

12.1.3 二叉查找 525

12.1.4 二叉查找的设计 526

12.1.5 二叉查找的分析 528

12.1.6 标准库的查找函数 531

12.1.7 用于有序区间的函数 531

12.1.8 用于无序区间的函数 532

12.1.9 STL的search函数 533

12.1.10 本节自测练习 534

12.2 开地址散列 534

12.2.1 散列简介 534

12.2.2 表类的声明 536

12.2.3 表类的设计 538

12.2.4 表ADT的实现 541

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

12.2.6 再散列减少聚类 547

12.2.7 本节自测练习 548

12.3 链式散列 549

本节自测练习 551

12.4 散列的时间分析 551

12.4.1 散列表的装填因子 551

12.4.2 本节自测练习 553

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

12.5.1 新表类 553

12.5.2 在新表类中使用向量 554

12.5.3 常量模板参数 554

12.5.4 函数模板参数 554

12.5.5 实现新表类 555

12.5.6 本节自测练习 556

12.6 TR1库扩展中的散列表 556

12.7 本章小结 557

本章自测练习答案 557

编程项目 561

第13章 排序 563

13.1 二次排序算法 563

13.1.1 选择排序的规范说明 563

13.1.2 选择排序的设计 563

13.1.3 选择排序的实现 565

13.1.4 选择排序的效率分析 567

13.1.5 插入排序 569

13.1.6 插入排序的效率分析 571

13.1.7 本节自测练习 573

13.2 递归排序算法 574

13.2.1 使用递归的分治法 574

13.2.2 归并排序 576

13.2.3 归并函数 577

13.2.4 动态内存在归并排序中的应用 581

13.2.5 归并排序的效率分析 582

13.2.6 文件的归并排序 583

13.2.7 快速排序 584

13.2.8 partition函数 585

13.2.9 快速排序的效率分析 588

13.2.10 为快速排序选择一个好的基准元素 589

13.2.11 本节自测练习 589

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

13.3.1 堆排序 590

13.3.2 构建堆 595

13.3.3 向下重排 596

13.3.4 堆排序的效率分析 597

13.3.5 本节自测练习 598

13.4 STL的排序与二叉查找 598

13.4.1 原始C标准库函数qsort 598

13.4.2 STL的排序函数 599

13.4.3 STL的堆排序 600

13.4.4 STL的二叉查找函数 600

13.4.5 用于STL排序函数的比较参数 601

13.4.6 使用迭代器编写一个自己的排序函数 601

13.5 本章小结 602

本章自测练习答案 603

编程项目 605

第14章 派生类与继承 610

14.1 派生类 610

14.1.1 如何声明派生类 612

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

14.1.3 使用派生类 614

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

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

14.1.6 覆盖继承的成员函数 616

14.1.7 本节自测练习 617

14.2 仿真生态系统 618

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

14.2.2 organism类 618

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

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

14.2.5 animal类的其他成员函数 623

14.2.6 本节自测练习 627

14.2.7 herbivore类 628

14.2.8 池塘生态仿真程序 630

14.2.9 池塘生态系统的实现细节 634

14.2.10 使用池塘模型 634

14.2.11 动态内存的使用 635

14.2.12 本节自测练习 636

14.3 虚拟成员函数和game类 636

14.3.1 game类简介 636

14.3.2 受保护的成员 640

14.3.3 虚拟成员函数 640

14.3.4 虚拟析构函数 641

14.3.5 game类的受保护虚拟成员函数 641

14.3.6 实现Connect Four游戏的派生类 642

14.3.7 connect4类的私有成员变量 642

14.3.8 connect4类的构造函数和restart函数 644

14.3.9 处理游戏状态的三个函数 644

14.3.10 处理移动的三个函数 645

14.3.11 clone函数 646

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

14.3.13 game类的play算法 647

14.3.14 本节自测练习 650

14.4 本章小结 650

进阶阅读 650

本章自测练习答案 651

编程项目 655

第15章 图 657

15.1 图的定义 657

15.1.1 无向图 657

15.1.2 有向图 660

15.1.3 图的更多术语 661

15.1.4 航线的例子 661

15.1.5 本节自测练习 662

15.2 图的实现 663

15.2.1 使用邻接矩阵表示图 663

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

15.2.3 使用边列表表示图 664

15.2.4 使用边集表示图 665

15.2.5 哪种表示方法最好 665

15.2.6 编程示例：标签图类 665

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

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

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

15.2.10 标签图类——函数neighbors 668

15.2.11 标签图类的实现 669

15.2.12 本节自测练习 674

15.3 图的遍历 674

15.3.1 深度优先搜索 675

15.3.2 宽度优先搜索 677

15.3.3 深度优先搜索的实现 679

15.3.4 宽度优先搜索的实现 680

15.3.5 本节自测练习 682

15.4 路径算法 683

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

15.4.2 具有加权边的图 683

15.4.3 最短距离算法 684

15.4.4 最短路径算法 691

15.4.5 本节自测练习 691

15.5 本章小结 692

本章自测练习答案 692

编程项目 693

附录 697

附录A ASCII字符集 697

附录B 大O表达式 698

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

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

附录E 使用老式编译器 701

附录F C++的输入和输出 701

附录G 选择库函数 708

附录H 标准模板类简介 711

附录I 一些有用函数的工具包 720

附录J 基本风格指南 723

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

附录L 异常处理 724