栈

中缀表达式转后缀表达式

后缀表达式是原运算式对应的表达式树的后续遍历。

表达式树还可以转为DAG，把重复顶点用指针代替即可。

在转后缀表达式的过程中。需要根据操作符的优先级进行栈的变化。

icp：当前扫描到运算符ch的优先级。

isp:当前运算符进栈后的优先级。

在表达式后面加上#表示表达式结束。

对于操作数，直接输出。

对于操作符，

icp(串中操作符)>isp(栈最后一个元素)。进栈。

icp(串中操作符)<isp(栈最后一个元素)，退栈并输出。

icp(串中操作符)=isp(栈最后一个元素)，直接退栈。

栈内内容一般不算#，即#是隐式的。

更简便的说

遇到运算符时，

"(":入栈

")":依次把栈中运算符加入后缀表达式，直到出现"("。从栈中删除")"。

除“（）”以外的其他运算符。

优先级高于除"("以外的栈顶运算符时，直接入栈。

否则:从栈顶开始，依次弹出优先级当前运算符的运算符，直到找到了一个比他低的，或遇到了"("。

一般来说，优先级关系只能约束"*/">"+-"。"-+"和"**/"也不能连着。必须要弹出。

前缀表达式/波兰式

运算符写前面，操作数写后面。

运算

从右向左扫描，若为运算符，栈顶2个元素弹出来进行运算。若为数字，入栈。之后，计算结果再次入栈。

而后缀表达式与之相反。是从左向右。

中缀表达式

最常使用的表示方法，就是自然语言的表示方法。

线性表

特殊矩阵

对称矩阵

三角矩阵

三对角矩阵/带状矩阵

稀疏矩阵：三元组+M的行数+M的列数

不包含M中包含非零元素的行数和包含非零元素的列数。三元组中已经包含了。

kmp

前缀：除最后一个字符外，字符串的所有头部子串

后缀：除最后一个字符外，字符串的所有尾部字串

部分匹配值:字符串的前缀和后缀的最长相等前后缀长度。

得到子串的部分匹配值。

发现不匹配，需要将字串向后移动。

移动位数=已匹配的字符数-对应的部分匹配值。

移动之后，进行下一趟匹配。

整个匹配过程中，主串始终没有回退，KMP可以在复杂度上实现模式匹配。

使用部分匹配值，如果匹配失败。会找他前一个元素的部分匹配值。

将PM（部分匹配值）表右移一位，之后再每位+1，就得到了next数组

next[j]的含义是，在子串的第j个字符与主串发生失配时，跳到子串的next[j]位置重新与主串当前位置比较。

next函数不仅可以用PM得出。可以用公式解决。

kmp的进一步优化

如果。需要再次递归，将next[j]修正为next[next[j]],直到2者不相等为止。最后的数组称为nextval.

树

完全二叉树：每个结点都与满二叉树中编号为1-n的结点一一对应。

完全二叉树第k层的非叶结点数不一定是

二叉搜索树:每个结点的值都比左孩子结点的值大，比它右孩子结点的值小，不一定是BST，因为要满足左子树的值全小于根结点的值，右子树的值全大于根结点的值。

在二叉排序树中，新插入的结点是叶结点，但不一定是最底层。

二叉树结点数的关系:，推导：总结点数=总分支数**+1**，

总分支数=,度为m的结点引出m条分支。

森林的中序遍历也叫做后序遍历。森林的后序遍历就是对应二叉树的中序。有时候也可以认为，森林的中序遍历就是对应二叉树的中序。

树

带权路径长度WPL

计算是要乘以根节点数值的，这就是所谓带权的意义。

二叉树的线索化

将节点中空的左右指针改成指向前驱或后继的指针。在结点中增加标志域。

ltag和rtag。=0是左/右孩子，=1，是前驱/后继。

无左子树，lchild指向前驱。

无右子树，rchild指向后继。

前驱和后继，就是中序/前序/后序遍历时候的前驱和后继。

图

最小生成树MST问题

kruskal算法

将所有边按权值排序，之后按大小顺序加入，排序用堆。如果构成环了，就换下一个。如何判断是否成环？使用U-F(并查集)来判断。

kruskal是针对边的。

时间复杂度:适用于边稀疏顶点较多的图。

prim算法

类似于dijkstra算法。每次选择一个离当前顶点集合最近的顶点加入树。

时间复杂度不依赖于|E|，就是针对于点的。适用于求解边稠密的的MST。

并查集

使用森林的双亲表示来作为并查集的存储结构。数组的下标作为元素名，根节点的下标代表子集合名。根节点的双亲节点为负数。

AOE网

加快进度可以缩短工程工期的话，活动必须位于所有的关键路径上。

简单路径

序列中顶点不重复出现的路径

图算法在采用邻接矩阵或邻接表存储时的时间复杂度

	Dijkstra	Floyd	Prim	Kruskal	DFS	BFS	拓扑排序	关键路径
邻接矩阵				-
邻接表	-	-	-

图的存储结构

十字链表

解决了无法快速找到一个顶点入边的问题。

邻接多重表

对比邻接表，一条边会存储2次，产生冗余。

邻接多重表删边：直接删除边结点代表的块，还有所有指向该块的指针。

删顶点：删除该顶点所代表的顶点结点，以及和这一顶点相同水平的所有边结点，以及所有指向被删除边结点的指针。

2者对比

查找

折半查找/二分查找

折半查找的过程可用二叉树来描述

折半查找在查找不成功时，比较次数最多为树高或

二分查找时，调整索引要减1加1.

哈希表

装填因子:

开放定址法:存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。

1.线性探测法:

。就是向后面一个个探测

2.平方探测法/二次探测法：。

散列表长度必须是一个可以表示为4k+3的素数。可以避免堆积问题。

3.双散列法：。

4.伪随机序列法

开放定址的情况下，不能随便删除表中已有元素，删除元素会导致其他具有相同散列地址的元素找不到。

可以做逻辑删除。散列表需要定期维护。

B树

m阶B树的每个结点都至多拥有m-1个关键字，m棵子树。

若根节点不是叶结点，至少拥有2棵子树，即关键字数量

除根节点外的所有非叶结点至少有棵子树，即关键字数目为个关键字。

B树的高度

包含n个关键字，m阶B树

最低高度:每个结点最多m颗子树，m-1个关键字。

最大高度:

除根节点外每个非叶结点至少有颗子树。

h+1层是查找不到信息的叶结点。关键字个数为n的B树，查找不成功的结点为n+1,

B树的查找

1.在B树中找结点：在磁盘中进行

2.在结点中找关键字：在内存中进行

B树的删除

删除一定会导致叶结点的变化，如果在叶结点删的，一定会变化。如果不是在叶结点删的，也会发生调整。调整叶结点。

B树的插入

1.定位 找到插入关键字的最底层非叶结点。插入位置一定会是最底层的某个非叶结点。

2.插入，如果结点关键字数目仍然。不需要调整。

调整:如果关键字数目超了，就从中间的关键字选，(结点内部关键字有序)。(如果奇数阶就找中间，偶数阶找中间的前一个或后一个)。把中间的关键字上升到父节点中，之后两边作为子树。

如果父节点又超了，就继续向上调整。递归的调整。

哈希表查找失败的平均长度

查找失败，是指一个不在里面的元素，查找到它确实不存在为止，所需的平均查找长度。

只考虑能映射的元素。如%7,只考虑0-6的元素的查找长度。

例1：现有长度为11且初始为空的散列表HT,散列函数是H（key）=key%7, 采用线性探查（线性探测再散列）法解决冲突。将关键字序列87, 40, 30, 6, 11, 22, 98, 20 依次插入HT后，HT查找失败的平均查找长度是（）.

直到查找到空才算结束。比如在其中查找0，0位置不是0，但线性探查法可能把同义词弄到后面，所以要一个一个查。0的查找次数是9，以此类推，1是8,2是7，等等。

到6的平均是

如果不是线性探测法，是二次探测法呢？

目前的真题只考过线性探测。

例2：长度为5，初始为空的散列表HT，散列函数H(k)=(k+4)%5,用线性探测再散列法解决冲突，将关键字2022,12,25依次插入HT，然后删除关键字25，则HT查找失败的平均查找长度是？

需要注意的是，再散列法的删除不是真删，只是打标记。

注意为4的时候，要算2，因为25还要比较。

排序

插入排序：第i趟排序后，前i+1个元素相对顺序正确

选择排序：第i趟排序后，最小的i个元素或最大的i个元素，已经处于最终位置。

冒泡排序：第i趟排序后，最小的i个元素或最大的i个元素，已经处于最终位置

快速排序：第i趟排序后，至少有i个元素已经处于最终位置

堆排序

堆是一种完全二叉树。

从堆弹出的过程：将堆的最后一个元素和堆顶元素调换，之后调整堆。

外部排序

减少平衡归并中，外存读写次数所采取的方法，增大归并路数/减少归并段个数。

置换-选择排序(生成初始归并段)

初始待排文件:FI,初始归并段输出文件:FO,/内存工作区wa，FO和wa初始状态为空，WA可容纳w个记录。

算法步骤:

1.FI选w个记录输入WA,

2.WA中选最小的，记作MINIMAX记录

3.MINIMAX输入到FO中。

4.若FI不空，从FI中输入下一个到WA

5.从WA中所有关键字比MINIMAX记录大的关键字中选最小。作为新的MINIMAX记录。

6.重复3-5，直到WA中选不出MINIMAX记录为止。得到一个初始归并段，输出一个归并段结束标志到FO中去

7.重复2-6，直到WA为空。

归并段最大为所有项数(数组有序)

最小为WA大小。(逆序)