C++与数据结构

第1篇 C++程序设计基础

第1章 C++语言概述

1.1 C++语言简介

1.2 最简单的C++程序

1.3 C++语言的基本组成

1.3.1 基本字符集

1.3.2 词法记号

1.3.3 语句

1.3.4 标准函数库

1.4 C++程序的基本结构

1.5 C++程序设计的编写与实现

习题1

实验训练1

第2章 数据类型与运算规则

2.1 数据类型

2.2 常量与变量

2.2.1 常量

2.2.2 变量

2.3 C++的运算规则与表达式

2.3.1 C++的运算规则

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 逗号运算符

2.4.3 “.”和“-＞”运算符

2.4.4 “（ ）”和“[ ]”运算符

2.4.5 “*”和“＆”运算符

2.4.6 （type）运算符

2.5 混合运算及数据类型转换

习题2

实验训练2

第3章 数组与指针

3.1 数组

3.1.1 一维数组

3.1.2 多维数组

3.1.3 字符数组和字符串

3.2 指针

3.2.1 指针的概念

3.2.2 指针变量定义

3.2.3 指针运算

3.3 指针与数组

3.3.1 指向数组的指针

3.3.2 指向字符串的指针

3.3.3 指针数组和指向指针的指针

3.4 指针与函数

3.4.1 指向函数的指针

3.4.2 返回指针值的函数

实验训练3

第4章 函数

4.1 函数的声明和调用

4.1.1 函数的声明

4.1.2 函数的调用

4.2 函数间的参数传递

4.2.1 值传递

4.2.2 函数参数为指针类型

4.3 带默认参数的函数

4.4 变量的存储属性

4.4.1 动态存储方式与静态存储

方式

4.4.2 局部变量的存储属性

4.4.3 全局变量的存储属性

习题4

实验训练4

第5章 结构类型及其他构造类型

5.1 结构类型

5.1.1 结构类型的概念与定义

5.1.2 结构变量的说明

5.1.3 引用结构中的成员

5.1.4 结构的初始化

5.2 结构数组

5.3 结构指针

5.4 在函数之间传递结构

5.4.1 向函数传递结构的成员

5.4.2 向函数传递整个结构

5.4.3 向函数传递结构的地址

5.5 联合类型

5.6 枚举类型

5.6.1 枚举的概念

5.6.2 枚举运算

习题5

实验训练5

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

6.1 面向对象的基本概念与基本特征

6.1.1 面向对象的基本概念

6.1.2 面向对象的基本特征

6.2 类的声明和对象的定义

6.2.1 类和对象的关系

6.2.2 声明类类型

6.2.3 定义对象的方法

6.2.4 类和结构体类型的异同

6.3 类的成员函数

6.3.1 成员函数的性质

6.3.2 在类外定义成员函数

6.3.3 inline成员函数

6.3.4 成员函数的存储方式

6.4 对象成员的引用

6.4.1 通过对象名和成员运算符访问

对象中的成员

6.4.2 通过指向对象的指针访问对象中

的成员

6.5 构造函数

6.5.1 对象的初始化

6.5.2 构造函数的作用

6.5.3 带参数的构造函数

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

初始化

6.5.5 构造函数的重载

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

6.6 析构函数

6.7 动态存储

习题6

实验训练6

第7章 引用、友元和重载

7.1 引用

7.1.1 引用的概念

7.1.2 引用的应用

7.1.3 引用作为函数参数

7.2 友元

7.2.1 友元的定义

7.2.2 友元函数

7.2.3 友元成员

7.2.4 友元类

7.3 重载

7.3.1 函数重载

7.3.2 运算符重载

习题7

实验训练7

第8章 继承与派生

8.1 继承与派生的概念

8.2 派生类的声明

8.3 派生类的构成

8.4 派生类成员的访问属性

8.4.1 公有继承

8.4.2 私有继承

8.4.3 保护成员和保护继承

8.4.4 多级派生时的访问属性

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

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

8.5.2 有子对象的派生类的构造

函数

8.5.3 多级派生时的构造函数

8.5.4 派生类的析构函数

8.6 多继承

8.6.1 声明多继承的方法

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

8.6.3 多继承的析构函数

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

8.7 虚基类

8.7.1 虚基类的概念

8.7.2 虚基类的初始化

习题8

实验训练8

第9章 多态性与虚函数

9.1 多态性

9.1.1 多态性的概念

9.1.2 编译时的多态性

9.1.3 运行时的多态性

9.2 虚函数

9.2.1 虚函数的作用

9.2.2 虚函数的声明

9.2.3 虚析构函数

9.3 纯虚函数与抽象类

9.3.1 纯虚函数

9.3.2 抽象类

习题9

实验训练9

第10章 模板

10.1 模板的概念

10.2 函数模板

10.2.1 函数模板和模板函数

10.2.2 重载模板函数

10.3 类模板

10.3.1 类模板和模板类的概念

10.3.2 类模板的派生

习题10

实验训练10

第2篇 数据结构--面向对象方法与C++描述

第11章 数据结构基本概念

11.1 数据结构的概念和术语

11.2 抽象数据类型

11.2.1 数据类型

11.2.2 数据抽象与抽象数据类型

11.3 算法和算法分析

11.3.1 算法

11.3.2 算法设计的要求

11.3.3 算法效率的度量

11.4 数据结构的抽象层次

习题11

第12章 线性表

12.1 线性表的定义

12.1.1 线性表的逻辑结构

12.1.2 线性表的抽象类定义

12.2 线性表的顺序表示和实现

12.2.1 线性表的顺序表示

12.2.2 顺序表类的定义

12.2.3 顺序表类的实现

12.3 线性表的链式表示和实现

12.3.1 线性表的链式表示

12.3.2 抽象链表类的定义

12.3.3 抽象链表类各成员函数

的实现

12.4 单链表

12.4.1 单链表的定义

12.4.2 单链表类的定义

12.4.3 单链表的常用成员函数

的实现

12.4.4 单链表举例-- 一元多项式

加法

12.5 循环链表

12.5.1 循环链表的定义

12.5.2 循环链表类的定义

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

12.5.4 循环链表举例--约瑟夫

问题

12.6 双向链表

12.6.1 双向链表的定义

12.6.2 双向链表类的定义

12.6.3 双向链表的常用成员函数

的实现

习题12

实验训练12

第13章 堆栈与队列

13.1 堆栈的概念及其运算

13.2 抽象堆栈类的定义

13.3 堆栈的定义及其实现

13.3.1 顺序栈的定义

13.3.2 顺序栈类的定义及典型成员

函数的实现

13.3.3 多栈共享空间问题

13.3.4 链栈的定义

13.3.5 链式栈类的定义及典型成员

函数的实现

13.4 堆栈的应用举例

13.4.1 数制转换

13.4.2 一个趣味游戏--迷宫问题

13.5 队列的概念及其运算

13.6 抽象队列类的定义

13.7 队列的定义及其实现

13.7.1 队列的顺序存储结构

13.7.2 循环队列的定义

13.7.3 顺序循环队列类的定义及常用

成员函数的实现

13.7.4 链式队列的定义

13.7.5 链式队列类的定义及常用成员

函数的实现

13.7.6 链式队列的应用举例

13.7.7 优先级队列的定义

13.7.8 优先级队列类的定义及常用

成员函数的实现

习题13

实验训练13

第14章 树与二叉树

14.1 树、二叉树和森林的基本概念

14.1.1 树

14.1.2 二叉树

14.1.3 树与森林的存储结构

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

14.2.1 二叉树的抽象类

14.2.2 树的类

14.3 二叉树的遍历和树的遍历

14.3.1 二叉树的遍历

14.3.2 树的遍历

14.4 二叉排序树

14.5 二叉树的计数

14.6 哈夫曼树及其应用

14.6.1 最优二叉树（哈夫曼树）

14.6.2 哈夫曼编码

习题14

实验训练14

第15章 图

15.1 图的基本概念

15.1.1 图的定义

15.1.2 图的术语

15.1.3 图的基本操作

15.1.4 图的存储表示

15.2 图的抽象类

15.2.1 图的邻接矩阵类

15.2.2 图的邻接表类

15.3 图的遍历

15.3.1 深度优先搜索DFS

15.3.2 广度（或宽度）优先搜索

BFS

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

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

15.4.2 最小生成树

15.4.3 关节点和重连通分量

15.5 最短路径

15.5.1 图结点的可达性

15.5.2 从某个源点到其余各顶点

的最短路径

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

15.6 活动网络

15.6.1 用顶点表示活动的网络

（AOV网络）

15.6.2 用边表示活动的网络

（AOE网络）

习题15

实验训练15

第16章 查找与散列结构

16.1 基本概念

16.2 静态查找表

16.2.1 顺序表的查找

16.2.2 有序表的查找

16.2.3 索引顺序表的查找

16.3 动态查找表

16.4 Hash表及其查找

16.4.1 Hash表

16.4.2 Hash函数的构造方法

16.4.3 处理冲突的方法

16.4.4 Hash表的查找及其分析

习题16

实验训练16

第17章 排序

17.1 排序的基本概念

17.2 插入排序

17.2.1 直接插入排序

17.2.2 其他插入排序

17.2.3 希尔排序

17.3 快速排序

17.4 选择排序

17.4.1 简单选择排序

17.4.2 锦标赛排序

17.4.3 堆排序

17.5 归并排序

17.5.1 归并

17.5.2 迭代的归并排序算法

17.6 基数排序

17.6.1 多关键字排序

17.6.2 链式基数排序

习题17

实验训练17

参考文献

《C++与数据结构（第2版）》是国家网络精品课程的教学成果，根据教育部计算机基础课程教学指导委员会《计算机基础课程教学基本要求》（试行）中，有关理工类专业“算法基础与程序设计”课程教学要求组织编写，内容由浅入深，循序渐进，案例丰富，通俗易懂，实用性强。《C++与数据结构（第2版）》分为C++程序设计基础和数据结构——面向对象方法与C++描述两篇，包括C++语言概述，数据类型与运算规则，数组与指针，函数，结构类型及其他构造类型，C++类及其对象的封装性，引用、友元和重载，继承与派生，多态性与虚函数，模板，数据结构基本概念，线性表，堆栈与队列，树与二叉树，图，查找与散列结构，排序共15章。《C++与数据结构（第2版）》各章节配有实验例题和题目，方便实践教学，并为任课老师提供电子课件和示例源代码。

　　《C++与数据结构（第2版）》可作为高等学校信息类专业及其他相关专业本科生的教科书，也可供从事程序设计的工程人员参考使用。