数据结构——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 精选习题答案