记录一些复习（主要是看视频课程）过程中遇到的难点和容易遗忘的点，以及一些之前不知道的小知识点之类。
仅为个人笔记所用，不是知识点总结，慎重参考。
线性表：
- 当要在指针 p 所指的结点之前进行插入操作时，可以先在 p 所指结点后进行插入，再 swap 两个结点的 data 域。
当要删除 p 所指的结点时，可以先 swap p 和 p->next 的 data 域，再删除 p->next。 -
反转链表的两种方法：
①从首结点开始依次将所有结点插入到某个固定的结点后，即反转完成。
②使用三个指针， pre 指向前一个结点， cur 指向后一个结点， tmp 为临时指针。
tmp=cur->next;
cur->next=pre;
pre=cur;
cur=tmp;
遍历完整个链表即可。 - 对于 n 个数据，以不同的次序全部入栈并出栈，有 f(n) 种出栈序列： f(n)=C(2n,n)/(n+1)。
-
中缀表达式转后缀表达式的方法：准备一个栈用来存放运算符，依次读取中缀表达式中的每个元素，
——若为数字，直接将其加入新表达式；
——若为(，则压入栈中；
——若为运算符，且栈为空或者栈中上一个元素为(或者栈中上一个运算符的优先级低于此运算符，则将此运算符入栈，
否则，循环将栈中的运算符出栈并加入新表达式，直到满足上述条件；
——若为)，循环将栈中的运算符出栈并加入新表达式，直到遇到(并将其出栈为止；
——若读取完毕，则将栈中剩余元素依次出栈并加入新表达式，直到栈为空。
注：左右括号均不加入新表达式，出栈后直接丢弃即可。
树：
-
非递归方式实现树的遍历。
-
中序遍历。用的是王道视频里讲的思路，需要用到栈，详见王道视频课程。
①从根结点开始，依次压栈的同时一路遍历到最左端的结点；
②将栈顶元素出栈并加入中序序列，同时检查此元素是否有右孩子？若有，将右孩子压栈，然后自此处开始，依次压栈的同时一路遍历到最左端的结点；
③循环执行②，直到栈为空。 -
后序遍历。自己想的思路，也许并不算好。
需要用到一个栈和额外的存储空间保存当前结点是否已被访问过，若已被访问过则标记为 visited。
①根结点入栈；
②若栈顶元素没有标记为 visited，将其右孩子、左孩子（如果有的话）依次入栈，同时将其标记为 visited；
若栈顶元素已被标记为 visited，将其出栈，加入遍历序列；
③循环②，直到栈为空。 -
先序遍历。与后序遍历流程一样，只是将元素加入遍历序列的时机不同。
需要用到一个栈和额外的存储空间保存当前结点是否已被访问过，若已被访问过则标记为 visited。
①根结点入栈；
②若栈顶元素没有标记为 visited，将其右孩子、左孩子（如果有的话）依次入栈，同时将其标记为 visited，并加入遍历序列；
若栈顶元素已被标记为 visited，将其出栈；
③循环②，直到栈为空。
也可利用后面深度优先遍历的思路
-
- 根据(先序遍历or后序遍历or层次遍历)and中序遍历序列确定一个二叉树：都是在中序遍历序列中寻找根结点。
-
二叉树线索化和线索二叉树的使用
线索化的代码看得云里雾里，实在想不明白。关于线索化，我倒是一直觉得直接遍历一遍，遍历的同时完成线索化不就好了……如果考试时真要用到此代码，我就真的这么写了……
以下为我自己的对于中序遍历线索化实现，与网上的其他代码相比复杂了许多，不过好歹完成了操作。
中序遍历线索化的思考：对于每一个结点，如果只考虑其前驱结点，则有两种可能：
①此结点无左子树。此时它的前驱结点为其所在的某个“可能更大的子树”的双亲结点。
②此结点有左子树。此时它的前驱结点为其左子树最右端的结点。
因此，只要想方设法与这两个结点建立联系，然后递归对树的所有结点执行此操作即可。此处采用自上至下的方式访问每个结点，因此可以将前驱结点为“祖先结点”的可能以参数的形式递归传递下来，将前驱结点为“子孙结点”的可能以返回值的形式传递上来。
//返回值：当前子树的最右结点
//cur：当前结点
//pre：在cur->left==nullptr时会成为cur前驱结点的祖先结点
TreeNode* inThread(TreeNode* cur, TreeNode* pre)
{
if (cur->left != nullptr)
{
//若左子树不为空，则继续线索化左子树，左子树的前驱结点依然为pre
TreeNode* tmp = inThread(cur->left, pre);
//与返回上来的前驱结点建立联系
if (tmp->right == nullptr)
{
tmp->rtag = 1;
tmp->right = cur;
}
}
//若左子树为空，则直接与传递下来pre建立联系
else
{
cur->ltag = 1;
cur->left = pre;
if (pre != nullptr && nullptr == pre->right)
{
pre->rtag = 1;
pre->right = cur;
}
}
//递归线索化右子树，同时将最右结点以返回值形式传递上去
if (cur->right != nullptr)
{
return inThread(cur->right, cur);
}
else
{
return cur;
}
}
使用线索二叉树中序遍历的方法：
①将指针移动到最左边的结点，即中序遍历的起点，访问此结点；
②右指针指向后继结点时直接访问；
右指针指向右孩子时，先移动到右孩子，然后以此为起点移动到最左边的结点，访问此结点；
③重复②直到右指针为空。
-
对bst执行删除结点时的操作，对AVL树进行插入时的操作
bst 树结点的删除：
①若待删除结点 z 为叶子结点，则直接删除；
②若待删除结点 z 只有一棵子树，则让 z 的子树代替 z；
③若待删除结点 z 有两棵子树，则让 z 的中序遍历序列的直接后继结点代替 z，再删除该直接后继结点。
AVL 插入新结点：
只对最小不平衡子树进行调整，四种平衡旋转。详见书 -
并查集，哈夫曼树
并查集要用到双亲表示法
哈夫曼树，每次选取权值最小的子树合成新树。（求 n 叉树（n>2）的最小带权路径长度时，可按最后一章“最佳归并树”的构建方式，先补充权值为 0 的结点，再构建哈夫曼树！）详见全文最后三行
图：
- 四种图的表示法——邻接矩阵，邻接表，邻接多重表（表示无向图），十字链表（表示有向图）。
- 在无权图邻接矩阵中，A^n[ i ][ j ] 为从 i 到 j 的长度为n的路径的数量。
- 广度优先搜索可以确定无权图的单源最短路径。
-
最小生成树算法——Prim，Kruskal；最短路径算法——Dijkstra，Floyd
详见书 - 关键路径：
①从头至尾计算事件（结点）的最早发生时间；（取最大值）
②从尾至头计算事件（结点）的最晚发生时间；（取最小值）
③计算活动（边）的最早发生时间 = 其弧尾事件的最早发生时间；
④计算活动（边）的最晚发生时间 = 其弧头事件的最晚发生时间 - 边的权重；
⑤计算活动（边）的最晚发生时间 - 最早发生时间，等于 0 的则为关键路径。
查找：
-
顺序查找，折半查找（二分查找），分块查找
其中分块查找：
①将待查数据分成若干个块，要求每个块中的最大元素均小于下一个块中的最小元素，并记录每个块中最大元素的值；
②利用记录的最大值在分块间进行查找，确定目标元素所在的分块；
③在该分块内进行查找，找到目标元素或查找失败。 - m 阶 B 树的特性：
- 每个结点最多有 m 棵子树；
- 若根结点不是终端结点，则至少有两棵子树；
- 除根以外的非叶结点至少有⌈m/2⌉棵子树。
B 树的查找、插入、删除操作。
插入的可能情况——直接插入，向上分裂
删除的可能情况——终端结点（直接删除，兄弟够借，兄弟不够借）非终端结点（前驱、后继结点替换再删除，左右子树合并）
详见课本或视频
注：B 树的所有终端结点必须在同一层
- B+ 树和 B 树的区别：
①B+ 树的结点中n 个关键字对应 n 个分支，B 树的结点中n 个关键字对应 n+1 个分支；
②B+ 树的叶结点包含所有的关键字，B 树中分支结点和叶子结点包含的关键字不重复；
③B+ 树的叶结点记录信息，分支结点仅起索引作用，记录子树的最大关键字和指向子树的指针。（类似分块查找）
④B+ 树有两种查找方式，可以从根结点开始查找，也可以从叶子结点顺序查找。 - 散列函数的选取——直接定址法、除留取余法、数字分析法、平方取中法、折叠法。
除留取余法：Hash(key)=key%p,一般选<=表长的最大质数作为 p。 - 处理冲突的方法——开放定址法（线性探测法、平方探测法、再散列法、伪随机法），拉链法
- 填装因子 = 表中记录数 / 表长
- 散列函数的选取——直接定址法、除留取余法、数字分析法、平方取中法、折叠法。
-
kmp算法
参考视频
排序：
-
9种内部排序算法的实现、时间复杂度、空间复杂度、稳定性
在理解的基础上将书中的表熟记于心！
总结：（折半插入参考直接插入）
最好情况下时间复杂度为O(n)——直接插入，冒泡排序
平均情况下时间复杂度为O(nlogn)——快排，堆排，归并
最坏情况下时间复杂度为O(n^2)——快排
空间复杂度——快排O(logn)，归并O(n)，基数O(r)
不稳定排序——希尔，快排，堆排，简单选择
注：关于做题的补充
关于排序，被问过最多的一道题——下列选项中，不可能是快速排序第 2 趟排序结果的是 __，需要注意的几点就是：
- 如果第一趟快排后确认的元素 k 的位置在序列中间，则第二趟排序将分别确认 k 左边和 k 右边的一个元素，即第二趟排序完成后会至少有 3 个元素在最终位置；
- 如果第一趟快排后确认的元素 k 的位置在序列边缘（如最左边，升序的话就是 k 为最小值），那显然，第二趟排序只能确认 k 右边的一个元素，即第二趟排序完成后会至少有 2 个元素在最终位置；
- 综上所述，若只有2个元素确认了最终位置，那么这2个元素中必定至少有一个元素在序列的边缘位置！！按此思路解题即可！
- 大顶堆/小顶堆的构建——从最末分支结点向根结点循环，每次均自上而下调节
堆在排序中的操作——将根结点与末端结点互换，而后自根向下调节
堆的插入——新元素插入末端，自下而上调节 -
外部排序
- 败者树——可视为一棵完全二叉树。叶结点存数，每个分支结点保存当前“回合”的败者，最顶端保存胜者；当删去胜者时，从胜者所在序列取出新元素放入叶结点，从叶子结点向上调节，确立新的胜者。
- 置换-选择排序——“只以递增的形式选择元素确立归并段”
-
最佳归并树——只有度为 0 和度为 m 的结点。将置换-选择排序得到的归并段的长度作为权值，构建哈夫曼树，为最佳归并树。
最佳归并树的总IO次数 = 带权路径长度之和 * 2（I一次O一次）
当叶子结点不够时，增加权值为 0 的结点（虚段）。对于n 个结点构建 m 叉归并树：- 若 (n-1)%(m-1) == 0，则可以直接构建 m 叉归并树；
- 若 (n-1)%(m-1) == u 不为 0，则需补充 m-u-1 个虚段。
网友评论