数据结构（用面向对象方法与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.3 作为ADT的C++类
    • 1.3.1 面向对象的概念
    • 1.3.2 C++中的类
    • 1.3.3 C++中的对象
    • 1.3.4 C++中的输入输出
    • 1.3.5 C++中的函数
    • 1.3.6 动态存储分配
    • 1.3.7 C++中的继承
    • 1.3.8 多态性
    • 1.3.9 C++的模板
  • 1.4 算法定义
  • 1.5 算法性能分析与度量
    • 1.5.1 算法的性能标准
    • 1.5.2 算法的后期测试
    • 1.5.3 算法的事前估计
    • **1.5.4 算法的渐进分析
    • 习题

• 第2章 线性表

  • 2.1 线性表
    • 2.1.1 线性表的概念
    • 2.1.2 线性表的类定义
  • 2.2 顺序表
    • 2.2.1 顺序表的定义和特点
    • 2.2.2 顺序表的类定义及其操作
    • 2.2.3 顺序表的性能分析
    • 2.2.4 顺序表的应用
  • 2.3 单链表
    • 2.3.1 单链表的概念
    • 2.3.2 单链表的类定义
    • 2.3.3 单链表中的插入与删除
    • 2.3.4 带附加头结点的单链表
    • 2.3.5 单链表的模板类
  • 2.4 线性链表的其他变形
    • 2.4.1 循环链表
    • 2.4.2 双向链表
  • 2.5 单链表的应用：多项式及其运算
    • **2.5.1 多项式的表示
    • **2.5.2 多项式的类定义
    • **2.5.3 多项式的加法
    • **2.5.4 多项式的乘法
  • 2.6 静态链表
  • 习题

• 第3章 栈和队列

  • 3.1 栈
    • 3.1.1 栈的定义
    • 3.1.2 顺序栈
    • 3.1.3 链式栈
    • **3.1.4 栈的应用之一——括号匹配
    • **3.1.5 栈的应用之二——表达式的计算
  • 3.2 栈与递归
    • 3.2.1 递归的概念
    • 3.2.2 递归过程与递归工作栈
    • **3.2.3 用回溯法求解迷宫问题
  • 3.3 队列
    • 3.3.1 队列的概念
    • 3.3.2 循环队列
    • 3.3.3 链式队列
    • 3.3.4 队列应用举例：打印二项展开式(a+b)^{i}的系数
    • **3.3.5 队列应用举例：电路布线
  • 3.4 优先级队列
    • 3.4.1 优先级队列的概念
    • **3.4.2 优先级队列的存储表示和实现
  • 3.5 双端队列
    • 3.5.1 双端队列的概念
    • 3.5.2 双端队列的数组表示
    • 3.5.3 双端队列的链表表示
  • 习题

• 第4章 数组、串与广义表

  • 4.1 多维数组的概念与存储
    • 4.1.1 多维数组的概念
    • 4.1.2 多维数组的存储表示
  • 4.2 特殊矩阵
    • 4.2.1 对称矩阵的压缩表示
    • **4.2.2 三对角线/多对角线矩阵的压缩存储
  • 4.3 稀疏矩阵
    • 4.3.1 稀疏矩阵及其三元组数组表示
    • 4.3.2 稀疏矩阵的转置
    • **4.3.3 稀疏矩阵的相加和相乘
    • **4.3.4 矩阵的正交链表表示
  • 4.4 字符串
    • 4.4.1 字符串的概念
    • 4.4.2 C++有关字符串的库函数
    • 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.5.4 广义表的递归算法
    • **4.5.5 三元多项式的表示
  • 习题

• 第5章 树

  • 5.1 树的基本概念
    • 5.1.1 树的定义与术语
    • 5.1.2 树的抽象数据类型
  • 5.2 二叉树
    • 5.2.1 二叉树的定义
    • 5.2.2 二叉树的性质
    • 5.2.3 二叉树的抽象数据类型
  • 5.3 二叉树的存储表示
    • 5.3.1 二叉树的数组存储表示
    • 5.3.2 二叉树的链表存储表示
  • 5.4 二叉树遍历及其应用
    • 5.4.1 二叉树遍历的递归算法
    • 5.4.2 二叉树遍历的应用
    • 5.4.3 二叉树遍历的非递归算法
    • 5.4.4 二叉树的计数
  • 5.5 线索二叉树
    • 5.5.1 线索
    • 5.5.2 中序线索二叉树的建立与遍历
    • **5.5.3 中序线索二叉树的插入与删除
    • **5.5.4 前序与后序的线索化二叉树
  • 5.6 树与森林
    • 5.6.1 树的存储表示
    • 5.6.2 森林与二叉树的转换
    • 5.6.3 树与二叉树的转换
  • 5.7 树与森林的遍历及其应用
    • 5.7.1 树与森林的深度优先遍历
    • 5.7.2 树和森林的广度优先遍历
    • **5.7.3 树遍历算法的应用
    • **5.7.4 其他基于遍历序列的几种存储表示
  • 5.8 堆
    • 5.8.1 最小堆和最大堆
    • 5.8.2 堆的建立
    • 5.8.3 堆的插入与删除
  • 5.9 Huffman树及其应用
    • 5.9.1 路径长度
    • 5.9.2 Huffman树
    • **5.9.3 Huffman树的应用：最优判定树
    • 5.9.4 Huffman树的应用：Huffman编码
  • 习题

• 第6章 集合与字典

  • 6.1 集合及其表示
    • 6.1.1 集合的基本概念
    • 6.1.2 用位向量实现集合抽象数据类型
    • 6.1.3 用有序链表实现集合的抽象数据类型
  • 6.2 并查集与等价类
    • 6.2.1 并查集的定义及其实现
    • **6.2.2 并查集的应用：等价类划分
  • 6.3 字典
    • 6.3.1 字典的概念
    • 6.3.3 字典的线性表描述
  • 6.4 跳表
    • 6.4.1 跳表的概念
    • **6.4.2 跳表的类定义
    • **6.4.3 跳表的搜索、插入和删除
  • 6.5 散列
    • 6.5.1 散列表与散列方法
    • 6.5.2 散列函数
    • 6.5.3 处理冲突的闭散列方法
    • 6.5.4 处理冲突的开散列方法
    • 6.5.5 散列表分析
  • 习题

• 第7章 搜索结构

  • 7.1 静态搜索结构
    • 7.1.1 静态搜索表
    • 7.1.2 顺序搜索
    • 7.1.3 基于有序顺序表的顺序搜索和折半搜索
    • **7.1.4 基于有序顺序表的其他搜索方法
  • 7.2 二叉搜索树
    • 7.2.1 二叉搜索树的概念
    • 7.2.2 二叉搜索树上的搜索
    • 7.2.3 二叉搜索树的插入
    • 7.2.4 二叉搜索树的删除
    • 7.2.5 二叉搜索树的性能分析
    • **7.2.6 最优二叉搜索树
  • 7.3 AVL树
    • 7.3.1 AVL树的概念
    • 7.3.2 平衡化旋转
    • 7.3.3 AVL树的插入
    • 7.3.4 AVL树的删除
    • 7.3.5 AVL树的性能分析
  • 7.4 伸展树
  • 7.5 红黑树
    • 7.5.1 红黑树的概念和性质
    • 7.5.2 红黑树的搜索
    • **7.5.3 红黑树的插入
    • **7.5.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 Kruskal算法
    • 8.4.2 Prim算法
  • 8.5 最短路径
    • 8.5.1 非负权值的单源最短路径
    • **8.5.2 任意权值的单源最短路径
    • **8.5.3 所有顶点之间的最短路径
  • 8.6 用顶点表示活动的网络（AOV网络）
  • 8.7 用边表示活动的网络（AOE网络）
  • 习题

• 第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.3.3 快速排序的改进算法
    • **9.3.4 三路划分的快速排序算法
  • 9.4 选择排序
    • 9.4.1 直接选择排序
    • **9.4.2 锦标赛排序
    • 9.4.3 堆排序
  • 9.5 归并排序
    • 9.5.1 归并
    • 9.5.2 归并排序算法
  • 9.6 基于链表的排序算法
    • **9.6.1 链表插入排序
    • **9.6.2 链表归并排序
    • **9.6.3 链表排序结果的重排
  • 9.7 分配排序
    • 9.7.1 桶式排序
    • 9.7.2 基数排序
    • **9.7.3 MSD基数排序
    • 9.7.4 LSD基数排序
  • 9.8 内部排序算法的分析
    • 9.8.1 排序方法的下界
    • 9.8.2 各种内部排序方法的比较
  • 习题

• 第10章 文件、外部排序与搜索

  • 10.1 主存储器与外存储器
    • 10.1.1 磁带
    • 10.1.2 磁盘存储器
    • 10.1.3 缓冲区与缓冲池
  • 10.2 文件组织
    • 10.2.1 文件的概念
    • 10.2.2 文件的存储结构
  • 10.3 外排序
    • 10.3.1 外排序的基本过程
    • 10.3.2 k路平衡归并与败者树
    • **10.3.3 初始归并段的生成(run generation)
    • **10.3.4 并行操作的缓冲区处理
    • **10.3.5 最佳归并树
  • 10.4 多级索引结构
    • 10.4.1 静态的ISAM方法
    • 10.4.2 动态的m路搜索树
    • 10.4.3 B树
    • 10.4.4 B树的插入
    • 10.4.5 B树的删除
    • **10.4.6 B+树
    • **10.4.7 VSAM
  • 10.5 可扩充散列
    • **10.5.1 二叉Trie树
    • **10.5.2 将二叉Trie树转换为目录表
    • **10.5.3 目录表扩充与收缩
    • **10.5.4 性能分析
  • 10.6 Trie树
    • 10.6.1 Trie树的定义
    • 10.6.2 Trie的搜索
    • 10.6.3 在Trie树上的插入和删除
  • 习题