数据结构原理

第一章 绪论
1 引言
2 数据结构概念
3 算法的概念
第二章 算法分析基础
1 引论
2 算法的时间复杂性分析方法
3 时间与空间分析
第三章 线性表
1 线性表的定义·运算·堆栈和队列
2 线性表的存储结构
2.1 线性表的顺序分配
2.2 线性表的链接分配
2.3 循环链接结构和双重链接结构
2.3.1 循环链表
2.3.2 双重链表
3 堆栈和队列的应用
3.1 堆栈与递归
3.2 算术表达式求值
3.3 队列
第四章 数组和串
1 数组
2 稀疏矩阵
2.1 三元组数组表示
2.2 正交链表
3 串
3.1 串的概念及运算
3.2 串的存储方式
3.2.1 串的顺序分配
3.2.2 串的链接分配
3.3 串的匹配算法
第五章 树形
1 基本概念
2 二叉树形
2.1 二叉树形的性质
2.2 二叉树形的表示及遍历方式
2.2.1 二叉树形的存储方式
2.2.2 二叉树形的遍历
2.3 二叉树形的遍历算法
2.4 二叉树形的应用
2.4.1 复制二叉树形
2.4.2 二叉树形与算术表达式
2.5 二叉树形的穿线结构
3 树形的表示方式
3.1 树形和森林的二叉树表示
3.2 FATHER链接结构
3.2.1 向上链接
3.2.2 集合表示与FATHER链接
3.3 树形的顺序表示
4 树形的通路长度
第六章 图
1 图的基本概念及存储方式
1.1 基本定义
1.2 图的存储结构
1.2.1 邻接矩阵
1.2.2 邻接表
2 图的遍历算法
3 拓扑排序和关键路径
3.1 拓扑排序
3.2 关键路径
4 传递闭包
5 图的连通分支
5.1 无向图的连通分支
5.2 有向图的强连通分支
6 最短路径
6.1 单源最短路径
6.2 每对顶点之间的最短路径
7 最小支撑树
第七章 内排序
1 插入排序
2 交换排序
2.1 起泡排序
2.2 分划交换排序
3 选择排序
3.1 直接选择排序
3.2 堆排序
4 合并排序
5 排序下界
6 分布排序
6.1 基数分布
6.2 值分布
第八章 查找
1 线性表查找
1.1 顺序查找
1.2 有序表的查找
1.2.1 对半查找
1.2.2 Fibonacci查找
1.2.3 插值查找
1.2.4 索引技术
2 二叉树查找
2.1 静态树
2.2 动态树
2.2.1 高度平衡树
2.2.2 重量平衡树
2.2.3 平衡树的简单应用
3 树字查找树
4 杂凑
4.1 杂凑函数
4.1.1 抽取法
4.1.2 压缩法
4.1.3 除法杂凑函数
4.1.4 乘法杂凑函数
4.2 冲突调节
4.2.1 拉链法
4.2.2 线性探查
4.2.3 双重杂凑
4.2.4 杂凑有序表和杂凑表的删除
5 （a,b）-树
第九章 内存管理
1 均匀大小记录的管理
1.1 访问计数器法
1.2 废料收集
2 不同大小的记录的管理
2.1 查找分配
2.2 压缩分配
3 伙伴系统
第十章 外排序
1 外存储器
1.1 磁带
1.2 磁盘
2 磁带排序
2.1 平衡合并排序
2.2 多路合并和初始游程的生成
3 磁盘排序
第十一章 文件
1 顺序文件
1.1 串行处理文件
1.2 顺序处理文件
2 杂凑（散列）文件
2.1 杂凑文件的设计
2.1.1 杂凑函数与文件的构造
2.1.2 杂凑文件中的操作
2.2 可扩充的杂凑文件
3 索引文件
3.1 动态索引结构和静态索引结构
3.2 索引顺序文件
3.3 B＋树索引文件
4 倒排文件和多重链表文件
附录