算法与数据结构——基于现代C++的方法及实践

第1章 绪论 1.1 数据结构的基本概念 1.1.1 数据类型与数据结构 1.1.2 数据的逻辑结构 1.1.3 数据的存储结构 1.1.4 数据的操作 1.2 算法与算法分析 1.2.1 算法 1.2.2 算法设计的要求 1.2.3 算法效率分析 习题1第2章 C++编程基础与数据集合类型 2.1 现代C++及面向对象编程概述 2.1.1 面向对象编程与数据结构 2.1.2 现代C++的新特性概述 2.2 C++语言编程基础 2.2.1 C++程序的编辑、编译和运行 2.2.2 C++的数据类型与流程控制 2.2.3 C++的标准输入流和输出流 2.2.4 类与对象 2.2.5 类的继承 2.2.6 抽象函数与抽象类 2.2.7 多态性 2.2.8 异常处理 2.2.9 C++模板与泛型编程 2.2.10 函数对象与Lambda表达式 2.2.11 C++程序的基本组织方法 2.3 C++语言数据集合类型 2.3.1 数组 2.3.2 线性表类 2.3.3 栈类 2.3.4 队列类 2.3.5 关联容器map类 习题2第3章 遍历、迭代与递归 3.1 高级编程语言中的循环结构与遍历操作 3.1.1 C++中的循环结构 3.1.2 C++中遍历数据集合的常用范式 3.2 迭代 3.2.1 迭代的基本概念 3.2.2 迭代算法 3.3 递归 3.3.1 递归算法 3.3.2 递归与迭代的比较 3.3.3 递归数据结构 习题3第4章 字符串 4.1 字符串的概念及类型定义 4.1.1 字符串的定义及其抽象数据类型 4.1.2 C++中的字符串类 4.2 字符串的顺序存储结构及其实现 4.2.1 字符串的顺序存储结构的定义 4.2.2 字符串的基本操作的实现 4.2.3 字符串的其他操作的实现 4.3 字符串的链式存储结构及其实现 4.3.1 字符串的链式存储结构的定义 4.3.2 字符串的链式存储结构基本操作的实现 习题4第5章 排序算法 5.1 数据序列及其排序 5.1.1 排序操作相关基本概念 5.1.2 C++标准库中的排序算法 5.2 插入排序 5.2.1 直接插入排序算法 5.2.2 希尔排序算法 5.3 交换排序 5.3.1 冒泡排序 5.3.2 快速排序 5.4 选择排序 5.4.1 直接选择排序 5.4.2 堆排序 5.5 归并排序 习题5第6章 线性表 6.1 线性表的概念及类型定义 6.1.1 抽象数据类型层面的线性表 6.1.2 C++中的线性表类 6.2 线性表的顺序存储结构 6.2.1 顺序表的类型定义 6.2.2 顺序表的操作 6.2.3 顺序表操作的算法分析 6.3 线性表的链式存储结构 6.3.1 线性链表的结点结构 6.3.2 单向链表 6.3.3 单向循环链表 6.3.4 双向链表 习题6第7章 栈与队列 7.1 栈的概念及类型定义 7.1.1 栈的基本概念 7.1.2 抽象数据类型层面的栈 7.1.3 C++中的栈类 7.2 栈的存储结构及实现 7.2.1 栈的顺序存储结构及操作实现 7.2.2 栈的链式存储结构及操作实现 7.2.3 栈的应用举例 7.3 队列的概念及类型定义 7.3.1 队列的基本概念 7.3.2 抽象数据类型层面的队列 7.3.3 C++中的队列类 7.4 队列的存储结构及实现 7.4.1 队列的顺序存储结构及操作实现 7.4.2 队列的链式存储结构及操作实现 7.4.3 队列的应用举例 习题7第8章 数组与广义表 8.1 数组 8.1.1 一维数组 8.1.2 二维数组 8.1.3 在C++中自定义矩阵类 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第9章 树与二叉树 9.1 树的定义与基本术语 9.1.1 树的定义和表示 9.1.2 树的基本术语 9.1.3 树的基本操作 9.2 二叉树的定义与实现 9.2.1 二叉树的定义 9.2.2 二叉树的性质 9.2.3 二叉树的存储结构 9.2.4 二叉树类的定义 9.3 二叉树的遍历 9.3.1 二叉树遍历的过程 9.3.2 二叉树遍历的递归算法 9.3.3 二叉树遍历的非递归算法 9.3.4 按层次遍历二叉树 9.4 构建二叉树 9.4.1 建立链式存储结构的完全二叉树 9.4.2 根据广义表表示式建立二叉树 9.4.3 根据先根和中根次序遍历序列建立二叉树 9.5 用二叉树表示树与森林 习题9第10章 图 10.1 图的定义与基本术语 10.1.1 图的定义 10.1.2 结点与边的关系 10.1.3 子图与生成子图 10.1.4 路径、回路及连通性 10.1.5 图的基本操作 10.2 图的存储结构 10.2.1 图结构的邻接矩阵表示法 10.2.2 图结构的邻接