C++数据结构导引

第1章 软件开发

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

1.2 设计

1.2.1 对象

1.2.2 操作

1.2.3 算法

1.2.4 函数YearSum()的设计

1.2.5 函数DisplayTable()的设计

1.2.6 关于算法的一些最后说明

1.3 编码

1.4 测试、执行和调试

1.5 维护

1.5.1 小测验

1.5.2 练习

第2章 数据结构入门和抽象数据类型——C风格类型

2.1 数据结构、抽象数据类型和实现

2.2 简单数据类型

2.2.1 Boolean数据

2.2.2 Character数据

2.2.3 整型数据

2.2.4 实数数据

2.2.5 小结

2.2.6 小测验

2.2.7 练习

2.3 数组

2.3.1 一维数组

2.3.2 下标运算

2.3.3 数组作为形参

2.3.4 越界错误

2.3.5 数组的问题

2.3.6 多维数组

2.3.7 小测验

2.3.8 练习

2.4 结构

2.4.1 为什么需要结构

2.4.2 C风格结构

2.4.3 结构的运算

2.4.4 联合

2.4.5 内存中的结构

2.4.6 小测验

2.4.7 练习

2.5 过程式编程

2.5.1 例子：一个时间数据类型

2.5.2 PP对OOP

第3章 数据结构和抽象数据结构进阶——C++类型

3.1 类

3.1.1 “传统的”（C）结构，OOP（C++）结构以及类之间的区别

3.1.2 类声明

3.1.3 例子：C++标准I/O类

3.2 用户定义类型的例子：一个Time类

3.2.1 实现一个类

3.2.2 一些现象

3.2.3 类构造函数

3.2.4 复制操作——初始化和赋值

3.2.5 访问函数

3.2.6 输入/输出——重载运算符——友元函数

3.2.7 其他操作：关系操作和前进

3.2.8 总结以及其他一些细节

3.2.9 小测验

3.2.10 练习

3.3 作为ADT的串

3.3.1 串的C风格实现

3.3.2 一个串类

3.3.3 练习

3.4 C++串类型

3.4.1 定义和构造函数

3.4.2 存储

3.4.3 输入/输出

3.4.4 string流

3.4.5 修改符

3.4.6 复制符

3.4.7 访问单独的字符

3.4.8 查找操作

3.4.9 比较

3.4.10 string和C风格串

3.4.11 小测验

3.4.12 练习

3.5 一个例子：文本编辑

3.5.1 对象

3.5.2 操作

3.5.3 文本编辑算法

3.6 数据加密（可选）

3.6.1 数据加密标准

3.6.2 公共密钥加密

3.6.3 练习

3.7 模式匹配（可选）

第4章 栈

4.1 栈的介绍

4.2 设计和创建一个Stack类

4.2.1 设计一个Stack类

4.2.2 实现一个栈类

4.2.3 选择数据成员

4.2.4 函数成员

4.2.5 前瞻

4.2.6 小测验

4.2.7 练习

4.3 栈的两个应用：函数调用，逆波兰表示

4.3.1 在函数调用中使用栈

4.3.2 逆波兰表示中栈的应用

4.3.3 小测验

4.3.4 练习

第5章 队列

5.1 队列入门

5.1.1 例子：训练和实践问题

5.1.2 调度队列的例子

5.2 基于数组的队列实现

5.2.1 小测验

5.2.2 练习

5.3 队列的应用：信息中心仿真

5.3.1 问题分析和需求规格说明

5.3.2 设计

5.3.3 编码和执行

第6章 改进ADT——第1部分： 模板和标准容器

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

6.1.1 从算法到算法

6.1.2 从数据到容器

6.2 函数通用性——重载和模板

6.2.1 重载

6.2.2 函数模板

6.2.3 例子：显示一个数组

6.3 类通用性——模板

6.3.1 Typedef有什么错

6.3.2 类模板

6.3.3 一个Stack类模板

6.3.4 Stack类模板的另一个版本

6.3.5 标准C++的容器类模板

6.3.6 小测验

6.3.7 练习

6.4 vector容器

6.4.1 定义vector对象

6.4.2 一些vector操作

6.4.3 例子：登录计数

6.4.4 内部实现一瞥——增加容量

6.4.5 对迭代器的第一次探讨

……

第7章 改进ADT——第2部分：递归，算法分析，以及标准算法

第8章 列表

第9章 其他链表结构

第10章 二叉树

第11章 排序

第12章 OOP和ADT

第13章 树

第14章 图和有向图

附录A ASCII字符集

附录B 数制系统

附录C 基本C++

附录D 其他C++特性

附录E 小测验答案

索引

数据结构是计算机科学专业的核心课程之一，面向对象方法已经成为目前系统开发和程序设计的主流模式，而C++是目前使用的最广泛的面向对象程序设计语言之一，本书将这几部分内容进行了有机的结合。 本书首先对软件工程进行了简单的探讨，作为后面实现各类数据结构时进行开发的基础；接着讲最基本的栈、队列和树以及高级的AVL树、红—黑树和图等各类不同的数据结构主题，同时，对C++进行全面的探讨，包括了模板和多态性等高级内容和STL中的容器和算法，并使用C++给出各种数据结构的不同实现；数据结构和算法是密不可分的，讲授数据结构必然要涉及到相关的算法，本书对算法开发、分析和验证进行一定程度的探讨，并且详细地介绍了搜索和排序算法；理论联系实际才能使读者较好地接受所学的内容，本书结合计算机科学和应用的不同领域中的例子，例如信息中心仿真、数据加密模式和大整数算术等，文中的练习可以培养读者使用所学知识来解决问题的能力。 本书适合作为大专院校计算机或软件专业的教材，也可以供从事计算机工程和应用的科技工作者参考。