第三章 栈和队列
一 栈
栈的类型
- 顺序栈
- 链式栈
- 双向栈
栈的应用
- 数制转换
- 行编辑程序
- 迷宫求解
- 表达式求值： 前中后缀表达式，以及表达式之间的转换方法
队列
队列的类型
- 链队列
- 循环队列
- 优先级队列
队列的应用
- 离散事件模拟
递归
第四章 字符串
- 字符串的模式匹配和模式匹配的改进 KMP算法
第五章 数组和广义表
矩阵
- 对称矩阵，三角矩阵，三对角矩阵的压缩存储
- 稀疏矩阵的压缩存储和转置，以及快速转置算法（在转置之前就用一个数组记录下来对应的j应该存在哪一行）
广义表
- 广义表的取表头表尾运算
第六章 树和二叉树
二叉树
- 前中后序遍历
线索二叉树
- 前中后序线索二叉树
- 通过中序遍历建立终须线索化二叉树
森林
- 双亲表示法，孩子表示法表示森林，左子女右兄弟表示法
- 先根遍历后根遍历
霍夫曼树
- 霍夫曼算法（
- 霍夫曼编码，前缀码
第七章 图
DFS BFS
最小生成树：普利姆算法
活动网络 AOV AOE 拓扑排序，逆拓扑排序求关键路径
dijikstra算法求最短路径
第九章 查找
静态查找
顺序查找
折半查找
分块查找 分块有序查找
动态查找
二叉排序树
平衡二叉树 LL RR LR RL
B树，B+树
键树
哈希表
第十章 内部排序
插入排序
-
直接插入排序
比较次数 最好n 最差 n*n 稳定 - 折半插入排序 n*logn 稳定
- 二路插入排序
希尔排序 不稳定
快速排序
最好nlogn 最差n*n 不稳定
起泡排序
最好 n 最差 n*n 稳定
选择排序
- 直接选择排序 n*n 不稳定
- 锦标赛选择排序 n*logn 稳定
堆排序 n*logn 不稳定
归并排序 n*logn 稳定
- 归并
- 两路归并
- 基数排序
