数据结构
第一章 绪论
wedge
时间复杂度和空间复杂度
- 比较简单，不做赘述
第二章 线性表
linear list
- 线性表是指具有相同类型的n（n>=0）个元素的数据元素的有限序列
- 表中元素个数有限
- 有逻辑上的顺序性
- 表中每个元素占有相同大小的空间
- 线性表是一种逻辑结构，仅讨论元素间的逻辑关系
线性表的顺序表示
- 顺序表是指用一组连续的存储单元，依次存储线性表中的各个元素
- 优点是可以随机访问,时间复杂度O(1)，缺点是一般情况下插入删除比较慢,时间复杂度O(n)
- 可用于二分查找
线性表的链式表示
- 单链表是指通过一组任意的存储单元来存储线性表中的元素。对于每个链表节点，除了要存放元素自身的信息，还需要一个指向后继结点的指针
- 若仅论插入和删除操作，时间复杂度是O(1)，而访问的复杂度是O(n)
- 我认为无法用于二分查找
链表的头插法和尾插法
- 比较简单，不做赘述
循环链表和静态链表
- 循环链表和单链表的区别是循环链表最后一个节点的指针指向头结点
- 静态链表是借助数组来表述线性表的链式存储结构，数组元素存放元素之外还存放下一个元素的位置
- 逻辑上优缺点和链表没有区别，但是它无法无限扩展
第三章 栈和队列
stack and queue
栈的定义与实现方式
- 栈是只允许在一端进行插入或删除的线性表
- 栈可以是空栈
- 栈可以通过顺序表存储，称为顺序栈，通过维护栈顶指针实现。缺点是会出现栈满的情况
- 共享栈也是栈的一种顺序表示方法，判满条件是栈顶指针是否相邻。优点是有效利用了存储空间。
- 栈可以通过单链表存储，称为链栈，优点是不存在栈满上溢的情况，通过维护头指针实现
队列的定义与表示
- 队列是一种只允许在表的一端进行插入，另一端进行删除的线性表
- 队列可以是空队列
- 队列可以通过顺序表存储，通过维护头指针和尾指针实现。缺点是会出现队满情况。很多情况下，溢出是一种假溢出，因为并没有将存储空间全部填满
- 队列可以通过链表存储，通过维护头指针和尾指针实现。优点是不存在队满情况
循环队列
- 循环队列的插入，删除，求表长,判断队列的满和空是易考点，一般来说，当队列不为空时，头指针指向的是第一个元素；而尾指针指向的位置则根据题目而定。若题目未提到，则一般指向队尾元素的后一个位置，即下一个存放元素的位置。
- 当front指向第一个元素，rear指向最后一个元素的下一个位置时
队列长度：(Q.rear + MaxSize - Q.front) % MaxSize
队满条件：(Q.rear + 1) % MaxSize == Q.front
队空条件：Q.rear == Q.front - 一般求表长、判断队列的满和空的问题记公式比较傻且不灵活，用特殊法取几个样例搞搞比较快。
- 若尾指针指向的是队尾元素的后一个，它的目的是便于区分队空还是队满，它的本质是牺牲了一个存储空间，但是令人惊奇的是，它的判满条件竟然和尾指针指向最后一个元素的方法的判满条件是一样的
双端队列
- 对于一个入队顺序为1,2,3,4的序列来说
能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的是4,1,3,2
能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的是4,2,1,3
既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的是4,2,3,1
栈与队列的应用
- 栈可以用于括号匹配，比较简单，不做赘述
- 栈可以用于表达式转换
- 在求解表达式转换的过程中有关栈的问题时，可参考以下方式：若要知道栈内情况，可以遍历中缀表达式，看到某个字符前面有几个运算符还没有运算即可。
- 中缀转换时可将所有运算单位加上括号，将符号移到括号前面，去掉所有括号就是前缀表达式；移到括号后面，去掉所有括号就是后缀表达式
- 后缀表达式是表达式树的后序遍历
- 栈可以用于递归
- 队列可用于缓冲队列，解决主机和外部设备速度不匹配的问题
特殊矩阵的压缩存储
- 可将二维矩阵通过行优先或者列优先变为一维存放
- 特殊矩阵主要有对称矩阵，三角矩阵，带状矩阵等，他们虽然从而二维到一维的表示方式较为繁琐，但是一般考试时用特殊法搞搞都能做出来。
- 稀疏矩阵可用（行，列，值）的三元组表示
第四章 树与二叉树
tree and binary tree
树的定义与基本性质
- 树是N(N>=0)个结点的有限集合，N=0时称为空树
- 树的度是指树中节点的最大度数
- 树的基本性质：
- 节点总数就是总度数加1
- 树中某一层的节点数现场推即可
二叉树的定义及其主要特性
- 二叉树子树有左右之分，其次序不能任意颠倒，是有序树。但二叉树和度为2的有序树不一样，度为2的树至少有3个结点，而二叉树可以为空；且度为2的有序树的孩子节点的左右次序是相对另一个孩子节点而言的
- 二叉树上的叶子结点数等于度为2的结点数加1
二叉树的存储结构
- 顺序存储，根结点下标为1，下标为i的结点的父节点下标为i/2
- 链式存储，不做赘述，值得注意的是含n个结点的二叉链表中含有n+1个空链域
二叉树的遍历
- 可以唯一确定一棵二叉树的序列组合包括：
- 中序遍历与前序遍历
- 中序遍历与后序遍历
- 中序遍历与层序遍历
- 关于如何通过遍历序列构造子树：通过前序和后续遍历可确定子树的根节点，从而在中序遍历中划分出左右子树，再递归往下划分即可
线索二叉树
- 线索二叉树在普通二叉树的基础上多了两个成员：ltag与rtag，表示lchild和rchild指向的是真正的左右孩子还是结点的前后驱
- 通过中序遍历建立的中序线索二叉树就是指前后驱的关系是根据中序遍历来确定的，前序线索二叉树、后序线索二叉树亦然
- 中序线索化二叉树遍历不需要借助栈
- 线索二叉树是一种物理结构
树与森林
- 可用二叉树通过左孩子右兄弟的方法表示树、森林
- 树的遍历包括先根遍历和后根遍历，森林的遍历包括先序遍历和中序遍历，对应关系如下
| 树 | 森林 | 二叉树 |
|---|---|---|
| 先根遍历 | 先序遍历 | 先序遍历 |
| 后根遍历 | 中序遍历 | 中序遍历 |
- 树的应用有并查集，不做赘述
二叉排序树
- 二叉排序树简称BST，可以为空，可通过中序遍历获得有序序列
- 二叉排序树删掉某个叶子节点再插入，与原来的相同
- 二叉树删除时，若删除的结点x只有一棵子树，则让其子树替代x即可；但若有两棵子树，则让他的中序后继结点代替x，然后不断递归这个过程直到转换成前一种情况
- 二叉排序树的查找平均效率与其形态有关，最坏可达O(n)
- 当有序表是静态查找时，宜用顺序表存储；而采用动态查找时，则适合用二叉排序树作为其逻辑结构
平衡二叉树
- 平衡二叉树简称AVL树，是一种特殊的二叉排序树，对于AVL树中的每一个结点，他的左右子树高度差不超过1
- 关于平衡二叉树的插入导致不平衡的操作：
- 找到不平衡的子树的根节点x
- 观察插入的节点关于x的方位
- 左边的左边——LL(右单旋转)
右边的右边——RR(左单旋转)
左边的右边——LR(先左后右)
右边的左边——RL(先右后左)
哈弗曼树与哈弗曼编码
- 哈弗曼树是为了使带权路径长度最小
- 构造不再赘述，同一序列构造出的哈弗曼树可以不同，但有同样的带权路径长度
- 哈弗曼树是一种特殊的二叉树，只有度为0的结点和度为2的结点，且内容全在叶节点上
- 向左为0，向右为1，这样从根节点遍历到叶节点可得到该结点的哈弗曼编码（当然也可左1右0）
第五章 图
graph
图的基本概念
- 图G由顶点集V和边集E组成，图不可以是空图，但是边集可以为空。数据结构一般讨论简单图
- 并非V和E的任意子集都可构成G的子图
- 无向图中的极大连通子图称为联通分量，极小连通子图即为最小生成树
- 在有向图中，若两个节点之间有来回的路径，称这两个顶点为强连通的。若任意两个顶点均为强连通，则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量
- 在路径序列中，顶点不出现重复的路径称为简单路径（故回路必然不为简单路径）
图的存储
- 可用邻接矩阵表示，适合稠密图，无向图用邻接矩阵表示时，矩阵是一个对称矩阵
- 可用邻接表表示，适合稀疏图，极大的节省了存储空间，遍历的复杂度为O(n+e)
- 有向图可采用十字链表表示，主要思想是弧结点有两个域，分别指向依附于入点的下一条边和依附于出点的下一条边
- 无向图可用邻接多重表表示，思想与上相似
图的遍历
- 主要有深搜和广搜。对于同一个图，基于邻接矩阵的遍历得到的DFS序和BFS序是唯一的，而基于邻接表的遍历所得到的DFS序和BFS序是不唯一的
- BFS生成树高度小于等于DFS生成树高度
最小生成树
- 过程EZ,不做赘述
- Prim时间复杂度O(n^2),适合稠密图;Kruskal时间复杂度O(eloge),适合稀疏图
最短路径
- 单源最短路使用Dijkstra算法，但是边权存在负权职则不适用
- Floyd每迭代一次，就是考虑了是否能通过k点缩小i到j的权值
- Dijkstra时间复杂度O(n^2)(可通过堆优化至nlogn),Floyd时间复杂度的O(n^3)
拓扑排序
- 有向无环图简称DAG，每个DAG都有一个或多个拓扑序列
- 若用DAG表示一个工程，顶点表示活动，边表示先后关系，则称该图为AOE网
关键路径
- AOE网中仅有一个入度为0的顶点，称为开始顶点（源点），表示整个工程的开始；也仅存在一个出度为0的顶点，称为结束顶点（汇点），代表整个工程的结束
- 从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，关键路径上的所有活动称为关键活动
- 关键路径的求法：
- 计算事件Vk的最早发生时间ve(k) = max{ve(j) + weight(Vj,Vk)}
- 计算事件Vk的最迟发生时间vl(k) = min{vl(k) - weight(Vj,Vk)}
- 计算活动ai的最早开始时间e(i) = 该活动起点的最早发生时间
- 计算活动ai的最迟开始时间l(i) = 该活动终点的最迟发生时间 - 该活动所需时间
- 计算出所有活动差额d(i) = l(i) - e(i),找出d(i) = 0的活动即为关键路径
- 关键路径出现在小题的话就肉眼找个最长路吧
- 关键路径不唯一
第六章 查找
search
顺序查找与折半查找与分块查找
- 顺序查找ASL(成功) = (n + 1) / 2,ASL(失败) = n + 1
- 折半查找的过程可以用二叉树表示，称为判定树，用判定树求ASL较为直观
- 题目中经常出现判断某个序列是否为折半查找的序列，这时只需谨记折半查找会让查找区间越来越小的原则即可
- 分块查找将各块长度取到sqrt(n)时最优，ASL(成功) = sqrt(n) + 1
B树与B+树
- B树所有结点的孩子结点的最大值称为B树的阶，一般用m表示，一棵m阶的B树或为空树，或满足如下性质：
- 每个结点至多有m棵子树
- 若根节点不是终端结点，则至少有2棵子树
- 根节点外的所有非叶节点至少有⌈m/2⌉棵子树（即至少含有⌈m/2⌉-1个关键字）
- 所有叶节点出现在同一层上，且不带任何信息
- B树所有节点平衡因子均为0
- B树的插入可能会引起分裂，分裂时把中间⌈m/2⌉的位置的结点上移，如此递归
- B树的删除，当所删除的结点k不在终端结点时：
- B+树是应用于数据库的一种B树的变形树，一棵m阶的B+树满足以下性质：
- 每个结点至多有m棵子树
- 若根节点不是终端结点，则至少有2棵子树
- 根节点外的所有非叶节点至少有⌈m/2⌉棵子树
- 结点子树与关键字相等
- 包含所有全部关键字及指向相应记录的指针，且叶节点中的关键字按大小排序
- 所有分支节点中仅包含他的各个子结点中关键字最大值及指向其子节点的指针
- B+树支持顺序查找
散列(Hash)表
- 散列函数会把两个不同的关键字映射到同一地址，即“冲突”，这些发生不碰撞的不同关键字称为同义词
- 冲突是不可以完全避免的，因而要设计好处理冲突的方法
- 理想情况下对散列表的查找时间复杂度为O(1)
- 较为常见的散列函数构造法有直接定址法（注意这个方法不会产生冲突），扣除余数法，数字分析法，平方取中法和折叠法，其中扣除余数法一般选取不大于散列表长m但最接近于m的质数
- 处理冲突的方法主要有开放定址法和拉链法，其中开放定址法包括：
- 线性探测法，这种方法容易产生堆积
- 平方探测法，优点是可以避免堆积问题，缺点是无法探测到散列表上的所有单元，但是至少能探测到一半单元
- 再散列法，即双哈希（我就是要用单哈希大质数卡过样例！），具体散列函数为
Hi = (H(key) + i * Hash2(key)) % m - 伪随机序列法
- 在开放地址的情形下，不能随便物理删除表中已有的元素
- 散列表的查找效率取决于：散列函数，处理冲突的办法，装填因子
- 装填因子 = 表中记录n / 散列表长m，散列表的平均查找长度依赖于装填因子而不是n和m
字符串模式匹配
- 简单模式匹配时间复杂度为O(n*m)
- kmp在匹配模式上和简单模式匹配没有什么太大的差别，区别在于使用的next数组可以保证指针i、j的位置不会往前退，因而可以做到O(n+m)的时间复杂度
- kmp的重点在于构造next数组，构造方法如下：
- next[1] = 0，next[2] = 1
- 求解后面每一位的next[j]值时，根据j的前一位进行比较，令k = next[j] = 1
- 将S[j-1]与S[k]进行比较，若相等，则next[j] = k + 1;若不相等，则k = next[k]，若k不等于0，跳到（3），若k等于0，next[j] = 1
排序
sort
插入排序
- 有序情况况下普通插入排序达到O(n)复杂度
- 希尔排序本质就是把序列分组进行插入排序
交换排序
- 冒泡排序所产生的子序列是全局有序的
- 判断一个序列是否是快拍n趟的结果时，只需看它是否有n个元素落在了最终位置
- 快速排序的性能主要取决于划分操作的好坏，但一般情况下啊快排是最快的
- 初始有序的情况下冒泡排序可以达到O(n)复杂度，而快排退化为O(n)。元素越乱，快排越快
选择排序
- 堆排过程如下：
- 先要建立初始堆，从最后一个结点的父节点开始调整，直到成为大根堆或者小根堆
- 将最后一个顶点和堆顶元素交换（其实堆顶元素是没了），然后往下调整
- 对堆进行插入操作时，先插在堆的末端，然后向上调整
归并排序与基数排序
- 基数排序n趟后，维护了低n位的有序
各种内部排序的比较
| 算法种类 | 最好情况 | 平均情况 | 最坏情况 | 空间复杂度 | 是否稳定 |
|---|---|---|---|---|---|
| 直接插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 是 |
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 是 |
| 简单选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 否 |
| 希尔排序 | O(1) | 否 | |||
| 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn) | 否 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 否 |
| 2-路归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 是 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(r) | 是 |
外部排序
- 外部排序分为如下步骤：通过置换-选择排序生成初始归并段，通过最佳归并树组织归并顺序，通过多路归并排序进行排序，排序时采用败者树优化
- 置换-选择排序步骤如下：
- 设一个工作区容量为w，先从出入文件FI中输入w个记录
- 从工作区wa中选出关键字最小的的记录，记为MINIMAX
- 将MINIMAX记录输出至输出文件FO
- 若FI未读完，从FI中输入下一个记录到WA中
- 将WA中所有比MINIMAX大的关键字中选取一个最小的关键字记录，作为新的MINIMAX
- 重复(3)~(5)，直到WA中选不出新的MINIMAX为止，由此得到一个初始归并段，输出一个结束标志到FO中
- 重复(2)~(6)，直到WA为空，由此得到全部初始归并段
最佳归并树
- 通过将哈夫曼树的思想推广到m叉树，以此描述m-路归并排序的最佳过程
- 若初始段不足以构成一棵严格的m叉树，需添加长度为0的虚段。设有n个记录，则有u = (n - 1) % (m - 1),u代表多余的结点，因此需补充m-u-1个虚段
最佳败者树
- 没看懂。。。据说408不考
