Chapter 5
数组
行优先顺序，列优先顺序
地址计算
矩阵
矩阵压缩
对称矩阵
三角矩阵
稀疏矩阵：三元组存储( i , j , a i j )
广义表：a 1表头，( a 2 , . . . , a n )表尾
长度：元素个数
深度：嵌套深度（递归）
例1：A = ( ) A=()A=()长度为0，深度为1
例2：B = ( ( ) ) B=(())B=(())长度为1，深度为2
Head 取表头，Tail 取表尾
表节点tag=1，原子节点tag=0
Chapter 6
树
概念：节点，节点的度，树的度，叶子节点（终端节点），分支节点（非终端节点），孩子，兄弟，祖先，层次，深度（高度），有序树，无序树，森林
性质：树中节点数减一等于度数和
二叉树
性质：第i ii层至多有2 i − 1个节点，深度为k kk的二叉树最多有2 k − 1 个节点。二叉树终端节点数等于二度节点数加一
完全二叉树：叶子节点只在最后两层，左子树深度等于右子树深度或大一
深度：⌊ log 2 n ⌋ + 1
双亲：
左孩子：2 ∗ i ，右孩子：2 ∗ i + 1
二叉树顺序存储：浪费空间
二叉链表
含有n节点的二叉链表有n+1个空指针域
二叉树遍历：非线性结构线性化
DLR：先序遍历
LDR：中序遍历
LRD：后序遍历（根节点最后一个输出）
逆波兰式另一种解法：通过后序遍历形成后缀表达式
层次遍历：队列实现（出队一个节点，入队左右孩子）
先序非递归实现：栈存右孩子
线索二叉树
线索：指向前驱和后继的指针
线索链表
遍历线索树不需要栈
树与森林
双亲表示法：多重链表（空链域太多）
单链表
孩子兄弟表示法
左指针：孩子
右指针：兄弟
森林与树的转换
对森林的先序遍历：从左到右一次先序
对森林的中序遍历：从左到右依次后序
赫夫曼树（最优二叉树）
路径，路径长度，树的路径长度
节点的带权路径长度，树的带权路径长度
权值大离根近，权值小离根远
不存在1度节点
如果有n个叶子节点，则共有2n-1个节点
赫夫曼编码：不等长编码，目的是缩短编码长度
编码与解码
Chapter 7
图
无向图：邻接点，度，关联
无向完全图：1 2 n ( n − 1 )条边
有向图：邻接点，入度，出度，关联
有向完全图：n ( n − 1 )条边
稀疏图，稠密图
连通，连通图，连通分量
强连通，强连通图，强连通分量
图的表示：邻接矩阵，邻接表（逆邻接表）
稠密图用邻接矩阵存储，稀疏图用邻接表存储
图的遍历：dfs,bfs
dfs：栈实现，先根遍历推广 邻接矩阵O ( n 2 )邻接表O ( n + e )
bfs：队列实现，数层次遍历 邻接矩阵O ( n 2 ) 邻接表O ( n + e )
连通分量
生成树（bfs生成树，dfs生成树）=》生成森林
最小生成树
Prim算法：
选点思想：适用于稠密图
O ( n 2 )
Kruskal算法
选边思想：适用于稀疏图
O ( e log e )
AOV网
关键路径：路径长度，关键活动
顶点对应事件，边对应活动
最早发生时间，最晚开始时间
最早开始时间，最晚开始时间，时间余量
最早：正向拓扑 最晚：反向拓扑
最短路径
迪杰斯特拉算法O ( n 2 )
Chapter 9
查找表：静态查找表，动态查找表
关键字：主关键字（唯一），次关键字（不唯一）
静态表：顺序表，有序表（折半查找，插值查找），索引顺序表，斐波那契查找
动态表：二叉排序树，平衡二叉树，B树，散列表
评价标准：平均查找长度：ASL
顺序表与链表：遍历逐个找
优点：简单，适应面广
缺点：ASL比较大，数据多时查找效率很低
索引查找表：先根据索引找到记录所在的块，再从块中找
哨兵法：省略对下标越界的检查，提高算法执行速度
折半查找（二分查找）
前提：有序，顺序存储
判定树：n 个节点，最多判定⌊ log 2 n ⌋ + 1次
只适用于有序表的顺序存储
效率很高
索引顺序表
索引：把一个关键字与它对应的记录相关联的过程
索引存储结构：数据主表，索引表
索引项的一般形式：关键字值+地址
主表：用数组存待查记录，每个数据元素至少有一个关键字域
索引表：按关键字有序，表中每个节点有最大关键字域和指向本块的第一个节点的指针
块间有序，块内无序
第i + 1 个块的关键字均大于（小于）第i ii个块的记录关键字
（长度为n的表分为b块，每块有s个记录）
二叉排序树
左小右大
中序遍历二叉排序树得到增序列
插入，删除都保持有序性
平衡二叉树（AVL树）
平衡因子（Balance Factor）：左子树高度减右子树高度
平衡化旋转
单向：单向左旋，单向右旋
双向：先左后右，先右后左
适合查找，较少插入和删除
B树（多路平衡查找树）
B-：非终端节点至少有
棵子树，最多有m 棵子树
叶子节点都同一层次且不包含任何信息
若m 阶B-树中有N 个关键字，则叶子节点（查找不成功的节点）有N + 1 个
B+树
一个节点有N 个关键字，则一定有N 棵子树
叶子节点按小到大链接
叶子结点包含了全部记录的关键字信息以及关键字记录的指针
非终端节点中只含有其子树根节点中最大最小关键字
哈希
哈希存储：数组存储
哈希函数：关键字与对应地址的联系（哈希函数是一个压缩映象）
直接定址法：关键字的线性函数，仅适用于地址集与关键字集等大
数字分析法：选几位
平方取中法：适用于关键字中（比较常用）
折叠法：移位相加，间界相加（类似蛇形）从右向左分割 适用于关键字位数比较多，数字分布比较均匀的情况
除留余数法：最简单，最常用。（选择质数，或不含20以内质因子的合数）
设计哈希函数应考虑：
计算哈希函数所需时间
关键字长度
哈希表大小
关键字分布情况
记录查找频率
解决冲突
开放定址法：线性探测再散列，二次探测再散列，伪随机探测再散列。充分利用空间，但比较容易产生聚集
再哈希法：构造若干个哈希函数，不易聚集但增加计算时间
链地址法（拉链法）：表前插入/表后插入
建立公共溢出区
哈希查找：按照处理冲突的方式查找，知道地址对应值为空
性能评价：时间复杂度，辅助空间，稳定性
内部排序
插入排序
直接插入排序
稳定
最好情况：比较n − 1 次 移动0 次
最差情况：
希尔排序
不稳定
克服了直接插入排序每次只能交换相邻两个记录的缺点
选择排序
简单选择排序
不稳定
辅助空间O ( 1 )
时间复杂度O ( n 2 )
堆排序
不稳定
辅助空间O ( 1 )
时间复杂度O ( n log n )
交换排序
冒泡排序
稳定
时间复杂度O ( n 2 )
快速排序
不稳定
最好时间复杂度O ( n log n )
最坏时间复杂度O ( n 2 )
归并排序
稳定
2路归并
辅助空间O ( n )
时间复杂度O ( n log n )
基数排序
稳定
时间复杂度O ( d ( n + r a d i x ) ) （关键字d位，每位基数radix，n个对象）
辅助空间O ( n + r a d i x )
笔试题记不清了，只记得去年笔试附加题考了十字链表
写在后面
记得去年考数据结构时候焦头烂额，笔试前一天晚上通宵一晚整理复习了一本书。当时困得要死，好在后来结果差强人意。现在把当时笔记重新整理下分享出来，方便大家复习。大家加油嗷！！！
