Data Structures Using C++

第1章 软件工程基本原理和c++类

1．1 软件的生命周期

1．2 软件开发阶段

1．2．1 分析阶段

1．2．2 设计阶段

1．2．3 实现阶段

1．2．4 测试和调试

1．3 算法分析：大o表示法

1．4 类

1．4．1 统一建模语言图

1．4．2 变量(对象)的声明

1．4．3 访问类的成员

1．4．4 类的内置运算

1．4．5 赋值运算符和类

1．4．6 类的作用域

1．4．7 函数和类

1．4．8 引用参数和类对象(变量)

1．4．9 成员函数的实现

1．4．10 构造函数

1．4．11 调用构造函数

.1．4．12 构造函数和默认参数

1. 4．13 析构函数

1．4．14 结构

1．5 数据抽象、类和抽象数据类型

1．6 编程示例：糖果机

1．6．1 问题分析和算法设计

1．6．2 收银机

1．6．3 控制装置

1．6．4 主程序

1．7 标识类、对象和操作

1．8 快速回顾

1．9 练习题

1．10 编程练习

第2章 面向对象的设计方法和c++

2．1 继承

2．1．1 重新定义基类的成员函数

2．1．2 派生类与基类的构造函数

2．1．3 派生类的头文件

2．1．4 头文件的多重包含

2．1．5 类的保护成员

2．1．6 三种继承方式：公有继承，保护继承或私有继承

2．2 聚合

2．3 多态：运算符和函数重载

2．4 运算符重载

2．4．1 为什么要重载运算符

2．4．2 运算符重载

2．4．3 运算符函数的语法

2．4．4 重载运算符的限制

2．4．5 this指针

2．4．6 类的友元函数

2．4．7 定义友元函数

2．4．8 运算符函数的两种形式：成员函数和非成员函数

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 头文件和类模板的实现文件

2．9 快速回顾

2．10 练习题

2．11 编程练习

第3章 指针和基于数组的表

3．1 指针数据类型和指针变量

3．1．1 声明指针变量

3．1．2 取地址运算符(&)

3．1．3 取值运算符(*)

3．1．4 类、结构和指针变量

3．1．5 初始化指针变量

3．1．6 动态变量

3．1．7 指针变量的运算

3．2 动态数组

3．2．1 函数和指针

3．2．2 指针和函数返回值

3．3 浅复制、深复制与指针

3．4 类和指针：一些特例

3．4．1 析构函数

3．4．2 赋值运算符

3．4．3 重载赋值运算符

3．4．4 复制构造函数

3．5 重载数组索引(下标)运算符([])

3．6 编程示例：newstring

3．7 基于数组的表

3．7．1 复制构造函数

3．7．2 重载赋值运算符

3．7．3 搜索

3．7．4 插入

3．7．5 删除

3．7．6 各种表操作的时间复杂度

3．8 编 程示例：多项式的运算

3．9 快速回顾

3．10 练习题

3. 11 编程练习

第4章 标准模板类库

4．1 stl的组成部分

4．1．1 容器类型

4．1．2 顺序容器

4．2 顺序容器：向量容器

4．2．1 声明vector对象

4．2．2 为向量容器声明一个迭代器

4．2．3 容器以及begin和end函数

4．2．4 对所有容器通用的成员函数

4．2．5 顺序容器公共的成员函数

4．2．6 copy算法

4．2．7 ostream迭代器和copy函数

4．3 顺序容器：双端队列

4．4 迭代器

4．4．1 迭代器的类型

4．4．2 输入迭代器

4．4．3 输出迭代器

4．4．4 前向迭代器

4．4．5 双向迭代器

4．4．6 随机访问迭代器

4．4．7 流迭代器

4．5 编程示例：成绩报告单

4．5．1 问题分析与算法设计

4．5．2 主程序

4．5．3 程序清单

4．6 快速回顾

4．7 练习题

4．8 编程练习

第5章 链表

5．1 链表

5．2 链表的属性

5．3 项的插入和删除

5．3．1 插入

5．3．2 删除

5．4 构建链表

5．4．1 正向构建链表

5．4．2 反向构建链表

5．5 adt链表

5．5．1 默认构造函数

5．5．2 销毁表

5．5．3 初始化表

5．5．4 重载输出运算符

5．5．5 表的长度

5．5．6 检索第一个节点的数据

5．5．7 检索最后一个节点的数据

5．5．8 搜索表

5．5．9 在表头插入节点

5．5．10 在表尾插入节点

5．5．11 删除节点

5．5．12 复制表

5．5．13 析构函数

5．5．14 复制构造函数

5．5．15 重载赋值运算符

5．6 有序链表

5．6．1 搜索表

5．6．2 插入节点

5．6．3 删除节点

5．6．4 有序链表的头文件

5．7 双向链表

5．7．1 默认构造函数

5．7．2 isemptylist

5．7．3 销毁表

5．7．4 初始化表

5．7．5 表的长度

5．7．6 重载输出运算符

5．7．7 反向打印表

5．7．8 搜索表

5．7．9 第一个和最后一个元素

5．7．10 插入节点

5．7．11 删除节点

5．8 stl顺序容器：1ist

5．9 带有头节点和尾节点的链表

5．10 循环链表

5．11 编程示例：video store

5．12 快速回顾

5．13 练习题

5．14 编程练习

第6章 递归

6．1 递归的定义

6．1．1 直接递归和间接递归

6．1．2 无穷递归

6．2 递归法解决问题

6．3 递归还是迭代

6．4 递归和回溯：n-皇后问题

6．4．1 回溯

6．4．2 回溯和4皇后问题

6．4．3 8皇后问题

6．5 快速回顾

6．6 练习题

6．7 编程练习

第7章 堆栈

7．1 堆栈

7．2 使用数组实现堆栈

7．2．1 初始化堆栈

7．2．2 销毁堆栈

7．2．3 空堆栈

7．2．4 满堆栈

7．2．5 入栈

7．2．6 返回栈顶元素

7．2．7 出栈

7．2．8 复制堆栈

7．2．9 构造函数和析构函数

7．2．10 复制构造函数

7．2．11 重载赋值运算符(=)

7．2．12 堆栈的头文件

7．3 编程示例：求最高gpa

7．4 堆栈的链表实现

7．4．1 默认构造函数

7．4．2 销毁堆栈

7．4．3 初始化堆栈

7．4．4 入栈

7．4．5 返回栈顶元素

7．4．6 出栈

7．4．7 由类linked list type派生而来的堆栈

7．5 堆栈应用：后缀表达式计算器

7．5．1 主算法

7．5．2 完整的程序清单

7．6 消除递归：反向打印一个链表的非递归算法

7．7 stl堆栈类(堆栈容器适配器)

7．8 快速回顾

7．9 练习题

7．10 编程练习

第8章 队列

8．1 队列

8．1．1 队列操作

8．1．2 队列的数组实现

8．2 队列的链式实现

8．3 从类linkedlisttype派生而来的队列

8．4 stl类queue(队列容器适配器)

8．5 优先级队列

8．6 队列的应用：模拟

8．6．1 设计队列系统

8．6．2 客户

8．6．3 服务器

8．6．4 服务器表

8．6．5 等待客户的队列

8．6．6 主程序

8．7 快速回顾

8．8 练习题

&9 编程练习

第9章 搜索算法

9．1 搜索算法

9．1．1 顺序搜索

9．1．2 顺序搜索算法分析

9．1．3 有序表

9．1．4 折半搜索

9．1．5 折半搜索算法的性能

9．1．6 将数据项插入到一个有序表

9，2 基于比较的搜索算法的下限

9．3 散列算法

9．3．1 散列函数：示例

9．3．2 冲突解决

9．3．3 冲突解决：开型寻址法

9．3．4 二次探测

9．3．5 删除：开型寻址法

9．3．6 散列法：使用二次探测来实现

9．3．7 冲突解决：链地址法(开散列方法)，

9．3．8 散列法性能分析

9．4 快速回顾

9. 5 练习题

9．6 编程练习

第10章 排序算法

10．1 排序算法

10．2 选择排序：基于数组的表

10．3 插入排序：基于数组的表

10．4 插入排序：基于链表的表

10．5 基于比较的排序算法的下限

10．6 快速排序：基于数组的表

10．7 归并排序：基于链表的表

10．7．1 划分

10．7．2 归并

10．7．3 分析：归并排序

10．8 堆排序：基于数组的表

10．8．1 构建堆

10．8．2 分析：堆排序

10．9 再论优先级队列

10．9．1 在优先级队列中插入一个元素

10．9．2 从优先级队列删除一个元素

10．10 编程示例：选举结果

10．10．1 问题分析和算法设计

10．10．2 主程序

10．10．3 对姓名排序

10．10．4 处理投票数据

10．10．5 计算选票数的总和

10．10．6 打印标题和结果

10．11 快速回顾

10．12 练习题

10．13 编程练习

第11章 二叉树

11．1 二叉树

11．2 二叉树的遍历

11．2．1 中序遍历

11．2．2 前序遍历

11．2．3 后序遍历

11．2．4 二叉树的实现

11．3 二叉搜索树

11．3．1 search函数

11．3．2 insert函数

11．3．3 delete函数

11．4 二叉搜索树分析

11. 5 二叉树的非递归遍历算法

11．5．1 非递归中序遍历

11．5．2 非递归前序遍历

11．5．3 非递归后序遍历

11．6 二叉树遍历和作为参数的函数

11．7 avi(平衡)树

11．7．1 avl树的插入操作

11．7．2 avl树的旋转

11．7．3 avl树的删除操作

11．7．4 avl树的性能分析

11．8 编程示例：videostore

11．9 快速回顾

11．10 练习题

11. 11 编程练习

第12章 图

12．1 初识图

12．2 图的定义和符号

12．3 图的表示方法

12．3．1 邻接矩阵

12．3．2 邻接表

12，4 图的操作

12．5 回顾模板

12．6 图的adt定义

12．7 图的遍历

12．7．1 深度优先遍历

12．7．2 广度优先遍历

12．8 最短路径算法

12．9 最小生成树

12．10 拓扑排序

12．11 快速回顾

12．12 练习题

12．13 编程练习

第13章 标准模板库(stl)ⅱ

13．1 pair类

13．1．1 比较pair类型的对象

13．1．2 pair类型和make_pair函数

13．2 关联容器

13．2．1 关联容器：集合和多重集合

13．2．2 关联容器：映射和多重映射

13．3 容器、相关头文件和迭代器支持

13．4 算法

13．5 stl算法分类

13．5．1 非修改算法

13．5．2 修改算法

13．5．3 数值算法

13．5．4 堆算法

13．5．5 函数对象

13．5．6 谓词

13．5．7 插入迭代器

13．6 stl算法

13．6．1 fi11和fill n函数

13．6．2 generate和generate_n函数

13．6．3 find、find if、find end和find first of函数

13．6．4 remove、remove if、remove_copy和remove copy_if函数

13．6．5 replace、replace_if、replace_copy和replace_copy_if函数

13．6．6 swap、iter_swap和swap_ranges函数

13．6．7 search、search_n、sort和binary_search函数

13．6．8 adjacent_find、merge和inplace_merge函数

13．6．9 reverse、reverse_copy、rotate、rotate_copy函数

13．6．10 count、count_if、max、max_element、min、min_element和random_shufne函数

13．6．11 for_each和transform函数

13．6．12 includes、set_intersection、set_union、set_diffefence和set_symmetric_difference函数

13．6．13 accumulate、adjacent_difference、inner_product和partial_sum函数

13．7 快速回顾

13．8 练习题

13．9 编程练习

附录a 保留字

附录b 运算符优先级

附录c 字符集

附录d 运算符重载

附录e 头文件

e．1 头文件cassert

e．2 头文件cctype

e．3 头文件cmath

e．4 头文件cstddef

e．5 头文件cstring

e．6 头文件string

附录f 其他c++主题

f．1 继承、指针和虚函数

f．2 类和虚析构函数

f．3 取地址运算符和类

附录g 针对java程序员的c++介绍

g．1 数据类型

g．2 名称常量、变量以及赋值语句

g．3 预处理指令

g．4 c++程序

g．5 输入和输出

g．6 控制结构

g．7 命名空间

g．8 函数及其参数

g．9 数组

附录h 参考文献

附录i 精选习题答案