数据结构C和C++语言描述（第2版）

第1章 数据结构入门
1.1 信息和涵义
1.1.1 二进制整数和十进制整数
1.1.2 实数
1.1.3 字符串
1.1.4 硬件和软件
1.1.5 实现的概念
1.1.6 示例
1.1.7 抽象数据类型
1.1.8 序列的值定义
1.1.9 变长字符串的ADT表示
1.1.10 C的数据类型
1.1.11 C中的指针
1.1.12 C中的数据结构
1.1.13 练习1
1.2 C中的数组
1.2.1 数组的抽象数据类型定义
1.2.2 使用一维数组
1.2.3 一维数组的实现
1.2.4 将数组作为参数
1.2.5 C中的字符串
1.2.6 字符串操作
1.2.7 二维数组
1.2.8 多维数组
1.2.9 练习2
1.3 C中的结构
1.3.1 结构的实现
1.3.2 联合（Union）
1.3.3 联合的实现
1.3.4 结构参数
1.3.5 表示其他数据结构
1.3.6 有理数
1.3.7 内存的分配和变量的作用域
1.3.8 练习3
1.4 C＋＋中的类
1.4.1 Rational类
1.4.2 Rational类的使用
1.3 方法的实现
1.4.4 重载
1.4.5 继承
1.4.6 构造函数
1.4.7 练习4
第2章 堆栈
2.1 定义和示例
2.1.1 基本操作
2.1.2 示例
2.1.3 堆栈的抽象数据类型定义
2.1.4 练习1
2.2 用C描述堆栈
2.2.1 pop操作的实现
2.2.2 测试异常情况
2.2.3 实现push操作
2.2.4 练习2
2.3 示例：中缀、后缀和前缀
2.3.1 基本定义和示例
2.3.2 后缀表达式的计算
2.3.3 计算后缀表达式的程序
2.3.4 程序的局限性
2.3.5 中缀表达式转换为后缀表达式
2.3.6 将中缀表达式转换为后缀表达式的程序
2.3.7 用C＋＋模板实现的堆栈
2.3.8 练习3
第3章 递归
3.1 递归定义和递归过程
3.1.1 阶乘函数
3.1.2 自然数的乘法
3.1.3 斐波纳契数列
3.1.4 对分查找
3.1.5 递归定义或算法的特点
3.1.6 练习1
3.2 C中的递归
3.2.1 用C实现阶乘
3.2.2 用C实现斐波纳契数列
3.2.3 用C实现对分查找
3.2.4 递归链
3.2.5 代数表达式的递归定义
3.2.6 练习2
3.3 编写递归程序
3.3.1 汉诺塔问题
3.3.2 使用递归将前缀表达式转换为后缀表达式
3.3.3 练习3
3.4 递归的模拟
3.4.1 从函数中返回
3.4.2 递归函数的实现
3.4.3 阶乘的模拟
3.4.4 优化模拟例程
3.4.5 消除goto语句
3.4.6 模拟汉诺塔问题
3.4.7 练习4
3.5 递归的效率
第4章 队列和链表
4.1 队列及其顺序表示
4.1.1 队列的抽象数据类型定义
4.1.2 队列的C语言实现
4.1.3 insert操作
4.1.4 优先队列
4.1.5 用数组实现的优先队列
4.1.6 练习1
4.2 链表
4.2.1 从链表中插入和删除结点
4.2.2 堆栈的链表实现
4.2.3 getnode和freenode操作
4.2.4 队列的链表实现
4.2.5 链表数据结构
4.2.6 链表操作的例子
4.2.7 优先队列的链表实现
4.2.8 头结点
4.2.9 练习2
4.3 C中的链表
4.3.1 链表的数组实现
4.3.2 数组实现的局限性
4.3.3 动态变量的分配和释放
4.3.4 使用动态变量实现的链表
4.3.5 用链表实现的队列
4.3.6 C中链表操作的例子
4.3.7 非整数链表和非齐次链表
4.3.8 数组实现和动态实现链表的比较
4.3.9 头结点的实现
4.3.10 练习3
4.4 示例：用链表进行模拟
4.4.1 模拟进程
4.4.2 数据结构
4.4.3 模拟程序
4.4.4 练习4
4.5 其他链表结构
4.5.1 循环链表
4.5.2 用循环锭表表示堆栈
4.5.3 用循环链表表示队列
4.5.4 循环链表的基本操作
4.5.5 约瑟夫问题
4.5.6 头结点
4.5.7 使用循环链表实现长正整数的加法
4.5.8 双向链表
4.5.9 使用双向链表实现长整数的加法
4.5.10 练习5
4.6 C＋＋中的链表
第5章 树
5.1 一叉树
5.1.1 二叉树中的操作
5.1.2 二叉树的应用
5.1.3 练习1
5.2 二叉树的表示
5.2.1 二叉树的结点表示
5.2.2 内部结点和外部结点
5.2.3 二叉树的隐式数组表示
5.2.4 选择一个二叉树表示
5.2.5 二叉树遍历的C语言表示
5.2.6 线索化二叉树
5.2.7 使用father字段的通历
5.2.8 异构二叉树
5.2.9 练习2
5.3 示例：哈夫曼算法
5.3.1 哈夫曼算法
5.3.2 C程序
5.3.3 练习3
5.4 将表表示为二叉树
5.4.1 寻找第k个元素
5.4.2 删除元素
5.4.3 用C语言实现用树表示的表
5.4.4 构建一个用树表示的表
5.4.5 回顾约瑟夫问题
5.4.6 练习4
5.5 树及其应用
5.5.1 树的C语言表示
5.5.2 树的遍历
5.5.3 用树来表示广义表达式
5.5.4 对表达式树求值
5.5.5 构建树
5.5.6 练习5
5.6 示例：游戏树
第6章 排序
6.1 背景
6.1.1 效率方面的考虑
6.1.2 符号O
6.1.3 排序的效率
6.1.4 练习1
6.2 交换排序
6.2.1 冒泡排序
6.2.2 快速排序
6.2.3 快速排序的效率
6.2.4 练习2
6.3 选择排序以及树排序
6.3.1 直接选择排序
6.3.2 二叉树排序
6.3.3 堆排序
6.3.4 作为优先级队列的堆
6.3.5 使用堆进行排序
6.3.6 堆排序的过程
6.3.7 练习3
6.4 插入排序
6.4.1 简单插入
6.4.2 希尔排序
6.4.3 地址计算排序
6.4.4 练习4
6.5 归并排序以及基数排序
6.5.1 归并排序
6.5.2 Cook-Kim算法
6.5.3 基数排序
6.5.4 练习5
第7章 搜索
7.1 基本搜索技术
7.1.1 作为抽象数据类型的目录
7.1.2 算法符号
7.1.3 顺序搜索
7.1.4 顺序搜索的效率
7.1.5 重新排序链表以最大化搜索效率
7.1.6 在有序表中进行搜索
7.1.7 使用索引的顺序搜索
7.1.8 二叉树搜索
7.1.9 插值搜索
7.1.10 练习1
7.2 树搜索
7.2.1 在二叉搜索树中插入元素
7.2.2 在二叉搜索树中删除元素
7.2.3 二叉搜索树操作的效率
7.2.4 不均匀的二叉搜索树的效率
7.2.5 最佳搜索树
7.2.6 平衡二叉树
7.2.7 练习2
7.3 广义搜索树
7.3.1 多路搜索树
7.3.2 在多路树中进行搜索
7.3.3 实现多路树
7.3.4 遍历多路树
7.3.5 在多路搜索树中进行插入
7.3.6 B树
7.3.7 B树插入算法
7.3.8 计算father和index
7.3.9 在多路搜索树中进行删除
7.3.10 多路搜索树的效率
7.3.11 改进B树
7.3.12 B树
7.3.13 数字搜索树
7.3.14 Trie
7.3.15 练习3
7.4 散列
7.4.1 使用开放寻址来解决散列冲突
7.4.2 从散列表删除项
7.4.3 再散列方法的效率
7.4.4 散列表重新排序
7.4.5 Brent方法
7.4.6 二叉树散列
7.4.7 通过额外的存储空间来获得改进
7.4.8 联合散列
7.4.9 单独链地址法
7.4.10 在外部存储器中进行散列
7.4.11 分离方法
7.4.12 动态散列以及可扩展散列
7.4.13 线性散列
7.4.14 选择散列函数
7.4.15 理想的散列函数
7.4.16 散列函数的通用类
7.4.17 练习4
第8章 图及其应用
8.1 图
8.1.1 图的应用
8.1.2 图的C语言表示
8.1.3 传递闭包
8.1.4 Warshall算法
8.1.5 最短路径算法
8.1.6 练习1
8.2 流问题
8.2.1 改进流函数
8.2.2 示例
8.2.3 算法和程序
8.2.4 练习2
8.3 图的链接表示
8.3.1 再访Dijkstra算法
8.3.2 组织图结点集合
8.3.3 调度的应用
8.3.4 C程序
8.3.5 练习3
8.4 图的遍历以及生成森林
8.4.1 图的遍历方法
8.4.2 生成森林
8.4.3 无向图以及它们的遍历
8.4.4 深度优先遍历
8.4.5 深度优先遍历的应用
8.4.6 深度优先通历的效率
8.4.7 广度优先遍历
8.4.8 最小生成树
8.4.9 Kruskal算法
8.4.10 Round-Robin算法
8.4.11 练习4
第9章 存储管理
9.1 广义表
9.1.1 修改表的操作
9.1.2 示例
9.1.3 表的链表表示
9.1.4 表的表示
9.1.5 crlist操作
9.1.6 表头的用法
9.1.7 释放表结点
9.1.8 C中的广义表
9.1.9 编程语言和表
9.1.10 练习1
9.2 自动表管理
9.2.1 引用计数方法
9.2.2 无用信息收集
9.2.3 无用信息收集的算法
9.2.4 收集和压缩
9.2.5 无用信息收集的变种
9.2.6 练习2
9.3 动态存储管理
9.3.1 存储块的压缩
9.3.2 首次匹配、最佳匹配和最差匹配
9.3.3 首次匹配方法的改进
9.3.4 释放存储块
9.3.5 边界标签方法
9.3.6 Buddy System
9.3.7 其他的Buddy System
9.3.8 练习3