对于信息类非计算机专业的本科生，有必要在学习《C语言程序设计》的基础上，进一步学习、掌握面向对象的C++程序设计和有效组织各种数据在计算机中的存储、传递和转换的方法，以提高程序设计和软件开发能力。本书正是针对这种需要，既介绍了面向对象的C++程序设计方法，又将系统的数据结构融合到面向对象的方法中。

本书系统地介绍面向对象的C++程序设计方法和数据结构的C++描述，并通过具体的实例分析，使读者能够真正掌握数据结构应用于面向对象设计的方法，从而更好地从事软件开发和工程应用。

本书系统地介绍了面向对象的封装性、继承性和多态性以及C++程序设计基础。在此基础上，采用面向对象的思想和抽象数据类型的概念，用C++语言有效地组织和描述了线性表、数组、串、栈、队列、树和图等各种常用的数据结构的相关类及其实现，并介绍了每一种数据结构的不同存储方法、典型操作及其应用。

本书分两大部分，共15章。第一部分介绍面向对象的概念及C++程序设计基础；第二部分介绍各种常用数据结构的C++抽象类及其实现。

本书可作为高等院校电子信息类专业以及其他相关专业本科生的教科书，也可供从事程序设计的工程人员参考使用。

第一部分 面向对象的C++程序设计基础

第1章 面向对象的设计方法

 1.1 面向对象的思想

1.1.1 面向对象的程序设计

1.1.2 面向对象的语言

 1.2 面向对象的基本概念

1.2.1 对象

1.2.2 消息

1.2.3 类

 1.3 面向对象的基本特性

1.3.1 封装性

1.3.2 继承性

1.3.3 多态性

 1.4 C++的初步知识

1.4.1 从C到C++

1.4.2 最简单的C++程序

1.4.3 C++程序的构成和书写形式

1.4.4 C++程序的编写和实现

 习题一

第2章 C++类及其对象的封装性

 2.1 类的声明和对象的定义

2.1.1 类和对象的关系

2.1.2 声明类类型

2.1.3 定义对象的方法

2.1.4 类和结构体类型的异同

 2.2 类的成员函数

2.2.1 成员函数的性质

2.2.2 在类外定义成员函数

2.2.3 inline成员函数

2.2.4 成员函数的存储方式

 2.3 对象成员的引用

2.3.1 通过对象名和成员运算符访问对象中的成员

2.3.2 通过指向对象的指针访问对象中的成员

 2.4 类的封装性和信息隐蔽

2.4.1 公共接口和私有实现的分离

2.4.2 类声明和成员函数定义的分离

 2.5 构造函数

2.5.1 对象的初始化

2.5.2 构造函数的作用..

2.5.3 带参数的构造函数

2.5.4 用参数初始化表对数据成员初始化

2.5.5 构造函数的重载

2.5.6 使用默认参数的构造函数

 2.6 析构函数

 2.7 调用构造函数和析构函数的顺序

 2.8 对象指针

2.8.1 指向对象的指针

2.8.2 指向对象成员的指针

2.8.3 this指针

 2.9 动态存储

 2.10 C++中的对象

 习题二

第3章 友元、重载和引用

 3.1 友元

3.1.1 友元的定义

3.1.2 友元函数

3.1.3 友元成员

3.1.4 友元类

 3.2 重载

3.2.1 函数重载

3.2.2 运算符重载

 3.3 引用

3.3.1 引用的概念

3.3.2 引用的应用

3.3.3 引用作为函数参数

 习题三

第4章 继承与派生

 4.1 继承与派生的概念

 4.2 派生类的声明方式

 4.3 派生类的构成

 4.4 派生类成员函数的访问属性

4.4.1 公有继承

4.4.2 私有继承

4.4.3 保护成员和保护继承

4.4.4 多级派生时的访问属性

 4.5 派生类的构造函数和析构函数

4.5.1 简单的派生类的构造函数

4.5.2 有子对象的派生类的构造函数

4.5.3 多级派生时的构造函数

4.5.4 派生类构造函数的特殊形式

4.5.5 派生类的析构造函数

 4.6 多继承

4.6.1 声明多继承的方法

4.6.2 多继承派生类的构造函数

4.6.3 多继承的析构函数

4.6.4 多继承引起的二义性问题

 4.7 虚基类

4.7.1 虚基类的概念

4.7.2 虚基类的初始化

 习题四

第5章 多态性与虚函数

 5.1 多态性

5.1.1 多态性的概念

5.1.2 编译时的多态性

5.1.3 运行时的多态性

 5.2 虚函数

5.2.1 虚函数的作用

5.2.2 虚函数的声明

5.2.3 虚析构函数

 5.3 纯虚函数与抽象类

5.3.1 纯虚函数

5.3.2 抽象类

5.3.3 应用实例

 习题五

第6章 模板

 6.1 模板的概念

 6.2 函数模板

6.2.1 函数模板和模板函数

6.2.2 重载模板函数

 6.3 类模板

6.3.1 类模板和模板类的概念

6.3.2 类模板的派生

 习题六

第二部分 数据结构——用面向对象方法与C++描述

第7章 绪论

 7.1 数据结构的基本概念

 7.2 抽象数据类型及面向对象概念

7.2.1 数据类型

7.2.2 数据抽象与抽象数据类型

 7.3 算法和算法分析

7.3.1 算法

7.3.2 算法设计的要求

7.3.3 算法效率的度量

 7.4 数据结构的抽象层次

 习题七

第8章 线性表

 8.1 线性表的定义

8.1.1 线性表的逻辑结构

8.1.2 线性表的存储表示

 8.2 抽象链表类

8.2.1 线性链表的特点

8.2.2 抽象链表类的定义

8.2.3 抽象链表中各成员函数的实现

 8.3 单链表

8.3.1 单链表的定义

8.3.2 单链表类的定义

8.3.3 单链表的常用成员函数的实现

8.3.4 单链表举例——一元多项式加法

 8.4 循环链表

8.4.1 循环链表的定义

8.4.2 循环链表类的定义

8.4.3 循环链表常用函数的实现

8.4.4 循环链表举例——约瑟夫(Josephu)问题

 8.5 双向链表

8.5.1 双向链表的定义

8.5.2 双向链表类的定义

8.5.3 双向链表的常用成员函数的实现

 习题八

第9章 数组

 9.1 数组的定义

9.1.1 数组的逻辑结构

9.1.2 数组的存储结构

9.1.3 数组的常用操作

 9.2 数组类的定义及实现

9.2.1 数组类的定义

9.2.2 数组类常用函数的实现

9.2.3 数组类的应用举例——一元多项式加法

 习题九

第10章 串

 10.1 串的概念

10.1.1 串的定义

10.1.2 串的基本术语

10.1.3 串的存储表示和实现

1O.1.4 串的基本运算

 10.2 字符串类的定义及实现

10.2.1 字符串类的定义

10.2.2字符串类中常用成员函数的实现

 习题十

第11章 堆栈与队列

 11.1 堆栈的概念及其运算

 11.2 栈的抽象类定义

 11.3 栈的定义及其实现

11.3.1 顺序栈的定义

11.3.2 顺序栈类的定义及典型成员函数的实现

11.3.3 多栈共享空间问题

11.3.4 链栈的定义

11.3.5 链式栈类的定义及典型成员函数的实现

 11.4 堆栈的应用举例

11.4.1 数制转换

11.4.2 一个趣味游戏——迷宫问题

 11.5 队列的概念及其运算

 11.6 抽象队列类的定义

 11.7 队列的定义及其实现

11.7.1 队列的顺序存储结构

11.7.2 循环队列的定义

11.7.3 顺序循环队列类的定义及常用成员函数的实现

11.7.4 链式队列的定义

11.7.5 链式队列类的定义及常用成员函数的实现

11.7.6 链式队列的应用举例

11.7.7 优先级队列的定义

11.7.8 优先级队列类的定义及常用成员函数的实现

 习题十一

第12章 树

 12.1 树、二叉树与森林的基本概念

12.1.1 树

12.1.2 二叉树

12.1.3 树与森林的存储结构

 12.2 二叉树的抽象类和树的抽象类

12.2.1 二叉树的抽象类

12.2.2 树的抽象类

 12.3 二叉树的遍历和树的遍历

12.3.1 二叉树的遍历

12.3.2 树的遍历

 12.4 二叉排序树

 12.5 二叉树的计数

 12.6 赫夫曼树及其应用

12.6.1 最优二叉树(赫夫曼树)

12.6.2 赫夫曼编码

 习题十二

第13章 图

 13.1 图的基本概念

13.1.1 图的定义

13.1.2 图的术语

13.1.3 图的基本操作

13.1.4 图的存储表示

 13.2 图的抽象类

13.2.1 图的邻接矩阵类

13.2.2 图的邻接表类

 13.3 图的遍历

13.3.1 深度优先搜索DFS

13.3.2 广度(或宽度)优先搜索BFS

 13.4 图的连通性与最小生成树

13.4.1 无向图的连通分量和生成树

13.4.2 最小生成树

13.4.3 关节点和重连通分量

 13.5 最短路径

13.5.1 图结点的可达性

13.5.2 从某个源点到其余各项点的最短路径

13.5.3 每一对顶点之间的最短路径

 13.6 活动网络

13.6.1 用顶点表示活动的网络(AOV网络)

13.6.2 用边表示活动的网络(AOE网络)

 习题十三

第14章 查找与散列结构

 14.1 静态查找表

14.1.1 顺序表的查找

14.1.2 有序表的查找

14.1.3 索引顺序表的查找

 14.2 动态查找表

 14.3 哈希表及其查找

14.3.1 哈希表

14.3.2 哈希函数的构造方法

14.3.3 处理冲突的方法

14.3.4 哈希表的查找及其分析

 习题十四

第15章 排序

 15.1 排序的基本概念

 15.2 插入排序

15.2.1 直接插入排序

15.2.2 其他插入排序

15.2.3 希尔排序

 15.3 快速排序

 15.4 选择排序

15.4.1 简单选择排序

15.4.2 锦标赛排序

15.4.3 堆排序

 15.5 归并排序

15.5.1 归并

15.5.2 迭代的归并排序算法

 15.6 基数排序

15.6.1 多关键字排序

15.6.2 链式基数排序

 习题十五

参考文献