数据结构与面向对象程序设计

第1章 软件开发的阶段

1.1 规范说明、设计与实现

1.1.1 概念设计：问题分解

1.1.2 前置条件与后置条件

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

1.1.4 有关ANSI/SOC++标准的实现问题

1.1.5 本节自测练习

1.2 运行时间分析

1.2.1 台阶计数问题

1.2.2 大O表示法

1.2.3 C++函数的时间分析

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

1.2.5 本节自测练习

1.3 测试与调试

1.3.1 选择测试数据

1.3.2 边界值

1.3.3 完全代码测试

1.3.4 调试

1.3.5 本节自测练习

1.4 本章小结

本章自测练习参考答案

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

2.1 类与成员

2.1.1 编程示例：节流阀类throttle

2.1.2 使用类

2.1.3 throtde类的演示小程序

2.1.4 实现成员函数

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

2.1.6 本节自测练习

2.2 构造函数

2.2.1 throttle类的构造函数

2.2.2 修订throttle类的成员函数

2.2.3 内联成员函数

2.2.4 本节自测练习

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

2.3.1 创建名称空间

2.3.2 头文件

2.3.3 实现文件

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

2.3.5 本节自测练习

2.4 类与参数

2.4.1 编程示例：point类

2.4.2 参数默认值

2.4.3 参数

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

2.4.5 本节自测练习

2.5 操作符重载

2.5.1 二元比较操作符重载

2.5.2 二元算术操作符重载

2.5.3 输入输出操作符重载

2.5.4 友元函数

2.5.5 point类汇总

2.5.6 操作符重载小结

2.5.7 本节自测练习

2.6 标准模板库与pair类

2.7 本章小结

本章自测练习参考答案

编程项目

第3章 容器类

3.1 bag类

3.1.1 bag类的规范说明

3.1.2 bag类的文档说明

3.1.3 bag类的演示程序

3.1.4 bag类的设计

3.1.5 类的不变式

3.1.6 bag类的实现

3.1.7 bag类的集成

3.1.8 bag类的测试

3.1.9 bag类的分析：

3.1.1 0本节自测练习

3.2 编程项目：sequence类

3.2.1 sequence类的规范说明

3.2.2 sequence类的文档说明

3.2.3 sequence类的设计

3.2.4 sequence类的伪代码实现

3.2.5 本节自测练习

3.3 交互式测试程序

本节自测练习

3.4 STL中的multiset类及其迭代器

3.4.1 multiset模板类

3.4.2 multiset类的一些成员

3.4.3 迭代器与[…）模式

3.4.4 测试迭代器的相等性

3.4.5 multiset类的其他操作符

3.4.6 不合法的迭代器

3.4.7 本节自测练习

3.5 本章小结

本章自测练习参考答案

编程项目

第4章 指针与动态数组

4.1 指针与动态内存

4.1.1 指针变量

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

4.1.3 动态变量与new操作符

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

4.1.5 内存堆与badalloc异常

4.1.6 delete操作符

4.1.7 本节自测练习

4.2 把指针与数组作为参数

4.2.1 以指针作为值参数

4.2.2 数组参数

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

4.2.4 以指针作为引用参数

4.2.5 本节自测练习

4.3 具有动态数组的bag类

4.3.1 指针成员变量

4.3.2 成员函数按需分配内存

4.3.3 值语义

4.3.4 析构函数

4.3.5 修订后的bag类定义

4.3.6 修订后的bag类实现

4.3.7 修订后的bag类集成

4.3.8 本节自测练习

4.4 有关动态类的说明

4.4.1 4条规则

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

4.4.3 本节自测练习

4.5 STL的string类与编程项目

4.5.1 以null结尾的字符串

4.5.2 初始化字符串变量

4.5.3 空字符串

4.5.4 读写字符串变量

4.5.5 strcpy函数

4.5.6 strcat函数

4.5.7 strlen函数

4.5.8 strcmp函数

4.5.9 string类的规范说明

4.5.10 string类的构造函数

4.5.11 重载operator[]

4.5.12 其他重载成员

4.5.13 string类的其他操作

4.5.14 string类的设计

4.5.15 string类的实现

4.5.16 string类的演示程序

4.5.17 串联输出操作符

4.5.18 声明常量对象

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

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

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

4.5.22 本节自测练习

4.6 编程项目：polynomial类

4.7 本章小结

本章自测练习参考答案

编程项目

第5章 链表

5.1 链表的基本节点类

5.1.1 为节点声明类

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

5.1.3 头指针和尾指针

5.1.4 空指针NULL

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

5.1.6 节点类构造函数

5.1.7 节点类成员函数

5.1.8 成员选择操作符

5.1.9 本节自测练习

5.2 链表工具包

5.2.1 链表工具包的头文件

5.2.2 计算链表的长度

5.2.3 链表的参数

5.2.4 在链表头插入新节点

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

5.2.6 在链表中查找节点

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

5.2.8 链表复制

5.2.9 在链表头删除节点

5.2.10 在非链表头删除节点

5.2.11 清空链表

5.2.12 链表工具包的集成

5.2.13 使用链表工具包

5.2.14 本节自测练习

5.3 用链表实现bag类

5.3.1 第3个bag类的规范说明

5.3.2 第3个bag类的类定义

……

第6章 用模板、迭代器和STL金鑫软件开发

第7章 栈

第8章 队列

第9章 递归思想

第10章 树

第11章 平衡树

第12章 查找

第13章 排序

第14章 派生类与继承

第15章 图

附录

《世界著名计算机教材精选：数据结构与面向对象程序设计（C++版）（第4版）》是为计算机科学专业的第二门课程CS2编写的，首先介绍了软件开发的各个阶段、C++面向对象程序设计思想，然后从软件开发的角度，利用面向对象设计的思想，系统阐述了指针和动态数组、链表、模板类、迭代器、栈、队列、递归实现、树和图等内容，并对排序与查找的相关算法进行了深入剖析。为了让读者巩固所学知识，在每节后面都给出了大量练习题，并在每章后面给出了答案。为了锻炼读者的动手能力，每章末给出了大量编程项目，在本书的配套网站还给出了一些更具挑战性的编程项目。 本书不仅非常适合于作为计算机及相关专业“数据结构”和“C++面向对象程序设计”的教材，也是计算机软件开发人员的常备参考书。