计算机保研复习数据结构薄弱知识

​
看了一个博主写的非常全的数据结构文章，在这里把自己迷惑的，需要加强记忆的知识总结一下

参考链接：https://blog.csdn.net/weixin_40113925/article/details/100938378

​

1. 线性链表建表

头插法建表（逆序），尾插法建表（顺序）

2. 静态链表

用一维数组来实现线性链表。容量是一定的。静态链表中指针表示的是下一元素在数组中的位置。是顺序的存储结构。静态链表在插入、删除时也是通过修改指针域来实现的。

3. 顺序栈

栈的顺序存储结构。top=-1时为空栈，top=0说明栈中只有一个元素。元素进栈时top自增。

4. 链栈

栈的链式存储结构。栈顶指针就是链表头指针。不需要判断栈满，需要判断栈空。

5. 卡特兰数

卡特兰数（Catalan number）是 组合数学 中一个常出现在各种 计数问题 中的 数列。
一个栈的进栈序列为1，2，3，，，，n，有多少个不同的出栈序列？
C(2n,n)/(n+1)个。（卡特兰数）
判断出栈顺序是否成立：在某个数字后，所有比此数字小的数字应降序排列。

6. 利用栈实现中缀转后缀

从左到右遍历中缀表达式的每个数字和符号，若是数字则直接输出，若是符号，则判断其与栈顶符号的优先级，是右括号或者优先级低于栈顶符号，则栈顶元素依次出栈并输出，直到遇到左括号或栈空才将低优先级的那个符号入栈
注：在后缀表达式中（）不出现
具体例子参考：https://blog.csdn.net/qq_41686130/article/details/82858997

7. 顺序队列

队列的顺序存储结构。当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头前一个位置，而尾指针始终指向队尾元素的实际位置。

8. 循环队列

除一些简单的应用外，真正实用的顺序队列是循环队列。故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列"空"还是"满"。

9. 空串和空白串

长度为0的串称为空串。
仅由一个或者多个空格组成的串称为空白串。

10. 分支数量

分支数量=总的节点数-1=结点*度

11. 二叉树和树的区别

二叉树的结点的子树要区分左子树还是右子树，即使只有一颗子树也要进行区分，说明他是左子树还是右子树。这是二叉树和树最主要的差别。
二叉树不是树的一种特殊形式。二叉树和树是两种不同的结构。

12. 二叉树结点性质

对于任意一颗二叉树，若它含有n0个叶子节点，n2个度为2的结点，则必存在关系式：n0=n2+1

13. 完全二叉树性质

具有n个结点的完全二叉树的深度为⎣log2 n⎦+1.
如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i（1<=i<=n),有：
如果i＝1，则结点i无双亲，是二叉树的根；

如果i>1，则其双亲的编号是 i/2向下取整。

如果2i>n，无左孩子；否则，其左孩子是结点2i。

如果2i＋1>n，则结点i无右孩子；否则，其右孩子是结点2i＋1。

14. 二叉链表

每个结点存储左子树和右子树。
在有n个结点的二叉链表中，值为非空的链域的个数为n-1。在有N个结点的二叉链表中必定有2N个链域。除根结点外，其余N-1个结点都有一个父结点。所以，一共有N-1个非空链域，其余2N-(N-1)=N+1个为空链域。

15. 遍历二叉树相关

对于一颗二叉树，如果先序和后序序列正好相反，则该二叉树高度等于结点数，也就是不存在双分支结点。
对于一个表达式，前中后序遍历分别对应其前缀表示（波兰式）、中缀表示（正常表示）和后缀表示（逆波兰式）

16. 线索二叉树

对二叉树所有结点做某种处理可在遍历过程中实现；检索（查找）二叉树某个结点，可通过遍历实现；如果能将二叉树线索化，就可以简化遍历算法，提高遍历速度，目的是加快查找结点的前驱或后继的速度。将非线性结构线性化。

17. 线索化

对于二叉树的线索化，实质上就是遍历一次二叉树，只是在遍历的过程中，检查当前结点左，右指针域是否为空，若为空，将它们改为指向前驱结点或后继结点的线索。
加上结点前趋后继信息（结索）的二叉树称为线索二叉树。n个结点的线索二叉树上每个结点有2个指针域（指向左孩子和右孩子），总共有2n个指针域；一个n个结点的树有n-1条边，那么空指针域= 2n - (n-1) = n + 1，即线索数为n+1。指针域tag为0，存放孩子指针，为1，存放前驱/后继节点指针。

18. 树的存储结构

双亲表示法：连续内存存储，同时在每个结点附设指示器指示双亲位置。
孩子表示法：多重链表，每个结点有多个指针域指向多个子树。
孩子兄弟表示法：树转换成二叉树。每个结点得两个指针域分别指向第一个孩子结点和下一个兄弟结点。树与转换后得二叉树得关系：左孩子右兄弟。
转换后得二叉树得先序对应树的先根遍历，转换后的二叉树的中序对应二叉树的后根遍历。
森林转换成二叉树

19. 哈夫曼树

带权路径长度最小的二叉树是哈夫曼树。
前缀编码：在一个字符集中，任意一个字符的编码都不是另一个字符编码的前缀。
哈夫曼编码就是前缀编码。
一颗有n个叶子节点的哈夫曼树共有2n-1个结点。度为2的结点有n-1个。可以存储在一个大小为2n-1的一维数组中，哈夫曼树的节点个数必为奇数。

20 完全图 连通图

完全图 ：具有n个顶点和n(n-1)/2条边的无向图，必定是连通图。
有向完全图 ：具有n个顶点和n(n-1)条边的有向图，每两个顶点之间都有两条方向相反的边连接的图。
连通图 ：无向图图 G 的任意两点之间都是连通的，则称G是连通图。
强连通图 ：有向图G的任意两点之间都是连通的，则称G是强连通图。各个顶点间均互相有向可达。

21 图的遍历

深度优先搜索利用栈，广度优先搜索利用队列。
求一条从顶点i到顶点s的简单路径，使用深度优先
求两个顶点之间的一条长度最短的路径，使用广度优先
当各边上的权值均相等时,BFS算法可用来解决单源最短路径问题。

22. 最小生成树

最小生成树 ：生成树中边的权值(代价)之和最小的树。最小生成树问题是构造连通网的最小代价生成树。
prim算法：加点法。
kruskal算法：加边法

23. 贪心算法

Prim算法、Kruskal算法和Dijkstra算法均属于贪心算法。
Dijkstra算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有边的权重都为非负值。时间复杂度为O（N*N）

24. 静态查找表

只实现查找，不实现插入和删除
顺序查找 ：从表的一端开始逐个进行记录的关键字和给定值的比较。适用于无序的顺序表或线性链表

折半查找/二分查找 ：用于顺序有序表。平均查找时间约为。用顺序方式存储且结点按关键字有序排序。每次查找(low+high)/2，向下取整（不是向上）

（静态树表的查找：根据元素被查找的概率构建查找数）

分块查找 ：将表分成几块，块内无序，块间有序，即前一块中的最大值小于后一块中的最小值。并且有一张有序索引表，每一项存放每一块的最大值和指向该块第一个元素的指针。块间查找用二分查找，块内用顺序查找，效率介于顺序和二分之间；

比较 ：
时间：顺序查找最差，二分最好，分块介于两者之间
空间：分块最大，需要增加索引数据的空间
分块时数据块之间在物理上可不连续。所以可以达到插入、删除数据只涉及对应的块；另外，增加了索引的维护。

25. 平衡因子

该节点的左子树深度-右子树深度
平衡二叉树每个结点的平衡因子都为1，-1，0.
在平衡二叉树上进行查找，时间复杂度仅为O(logn)

26. 红黑树

结点是红色或者黑色。
根是黑色，叶子是黑色

27. 哈希表

哈希函数 ：在记录的关键字与记录的存储位置之间建立的一种对应关系。是从关键字空间到存储位置空间的一种映象。
哈希表 ：应用哈希函数，由记录的关键字确定记录在表中的位置信息，并将记录根据此信息放入表中，这样构成的表叫哈希表。
Hash查找适合于关键字可能出现的值的集合远远大于实际关键字集合的情形。更适合查找，不适合频繁更新
Hash表等查找复杂依赖于Hash值算法的有效性，在最好的情况下，hash表查找复杂度为O(1)。只有无冲突的hash_table复杂度才是O(1)。一般是O©，c为哈希关键字冲突时查找的平均长度。插入，删除，查找都是O(1)。平均查找长度不随表中结点数目的增加而增加,而是随负载因子的增大而增大
由于冲突的产生，使得哈希表的查找过程仍然是一个给定值与关键字比较的过程。

根据抽屉原理，冲突是不可能完全避免的，所以应考虑选择好的散列函数和冲突处理方法。

常用的哈希函数
直接定址法：仅适合于：地址集合的大小 == 关键字集合的大小
数字分析法：对关键字进行分析，取关键字的若干位或其组合作哈希地址。仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度。

平方取中法：以关键字的平方值的中间几位作为存储地址。

折叠法：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址。移位叠加/间界叠加。适合于: 关键字的数字位数特别多，且每一位上数字分布大致均匀情况。

除留余数法：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key%p，p<=m。

随机数法：取关键字的伪随机函数值作哈希地址，即H(key)=random(key)，适于关键字长度不等的情况。
冲突解决

开放定址法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中。即Hi=(H(key)+di) % m，i=1,2,……k(k<=m-1)，H(key)哈希函数，m哈希表长，di增量序列。缺点：删除：只能作标记，不能真正删除；溢出；载因子过大、解决冲突的算法选择不好会发生聚集问题。要求装填因子α较小，故当结点规模较大时会浪费很多空间。

线性探测再散列：di=1，2，3，…，m-1

二次探测再散列：di=12,-12,22,-22,…，±k2（k<=m/2）

伪随机探测再散列: di为伪随机数序列

链地址法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针。拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间。一旦发生冲突，在当前位置给单链表增加结点就行。

其他方法：再哈希法、建立公共溢出区

在用拉链法构造的散列表中，删除结点的操作易于实现。拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间。由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况。拉链法解决冲突时，需要使用指针，指示下一个元素的存储位置

开哈希表–链式地址法;闭哈希表–开放地址法.开哈希和闭哈希主要的区别在于，随着哈希表的密集度提高，使用闭哈希时，不仅会与相同哈希值的元素发生冲突，还容易与不同哈希值的元素发生冲突；而开哈希则不受哈希表疏密与否的影响，始终只会与相同哈希值的元素冲突而已。所以在密集度变大的哈希表中查找时，显然开哈希的平均搜索长度不会增长。

设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到Hash表中需要做n*(n-1)/2次线性探测。如果使用二次探测再散列法将这n个关键字存入哈希表，至少要进行n*(n+1)/2次探测

Hash查找效率：装填因子=表中记录数/表容量

28. 静态查找和动态查找

静态查找就是我们平时概念中的查找，是“真正的查找”。之所以说静态查找是真正的查找，因为在静态查找过程中仅仅是执行“查找”的操作，即：
（1）查看某特定的关键字是否在表中（判断性查找）；
（2）检索某特定关键字数据元素的各种属性（检索性查找）。
这两种操作都只是获取已经存在的一个表中的数据信息，不对表的数据元素和结构进行任何改变，这就是所谓的静态查找。
静态查找包括：
顺序查找
折半查找
Fibonacci
分块查找
详细可以参考：http://blog.csdn.net/wangzi11322/article/details/45456871

动态查找
动态查找不像是“查找”，更像是一个对表进行“创建、扩充、修改、删除”的过程。动态查找的过程中对表的操作会多两个动作：
（1）首先也有一个“判断性查找”的过程，如果某特定的关键字在表中不存在，则按照一定的规则将其插入表中；
（2）如果已经存在，则可以对其执行删除操作。动态查找的过程虽然只是多了“插入”和“删除”的操作，但是在对具体的表执行这两种操作时，往往并不是那么简单。
动态查找包括：

1. 二叉排序树
2. 平衡二叉树
   详细参考：http://blog.csdn.net/wangzi11322/article/details/45456971

29. 内部排序和外部排序

内部排序：全部数据可同时放入内存进行的排序。

外部排序：文件中数据太多，无法全部调入内存进行的排序。

30. 直接插入排序

最坏情况是数据递减序，数据比较和移动量最大，达到O(n^2)，最好是数据是递增序，比较和移动最少为O(n)。
类比为扑克牌码牌的过程。

31. 折半插入排序

就是选一个元素，把它插入到有序队列中的时候，利用折半查找来找到适合他的位置。
由于插入第i个元素到r[1]到r[i-1]之间时，前i个数据是有序的，所以可以用折半查找确定插入位置，然后插入 。减少了比较次数但是没减少移动次数，复杂度仍为O（n^2）

32. 希尔排序

缩小增量排序。在实际应用中，步长的选取可简化为开始为表长n的一半（n/2），以后每次减半，最后为1。插入的改进，最后一趟已基本有序，比较次数和移动次数相比直接插入最后一趟更少。在每一趟中使用直接插入排序。

33. 冒泡排序

冒泡排序属于交换排序。
时复O(n2)，通常认为冒泡是比较差的，可以加些改进，比如在一趟中无数据的交换（序列是递增的），则结束等措施，所以比较次数和初始序列顺序有关。在数据已基本有序或数据量较少时可以使用。

34. 快速排序

通过一趟排序将记录分割为两部分，一部分的关键字均比另一部分小。
特点： 在第i趟完成后，会有i个以上的数出现在它最终要出现的位置，也就是说它左边的数都比他小，右边的数都比他大。
时间复杂度。最好情况：每次支点总在中间，O(nlog2n)，平均O(nlog2n)。最坏，数据已是递增或递减，O(n2)。pivotkey的选择越靠近中央，即左右两个子序列长度越接近，排序速度越快。越无序越快。
空间复杂度。需栈空间以实现递归，最坏情况：S(n)=O(n)；一般情况：S(n)=O(log2n)
在序列已是有序的情况下，时间复杂度最高。原因：支点选择不当。改进：随机选取支点或最左、最右、中间三个元素中的值处于中间的作为支点，通常可以避免最坏情况。所以，快速排序在表已基本有序的情况下不合适。在每次划分后分区较为平衡时，递归次数较少。

35. 简单选择排序

O(n^2)。总比较次数n(n-1)/2。

36. 堆排序

堆排序就是在不断地建堆，交换，建堆，交换。
找出若干个数中最大/最小的前K个数，用堆排序是最好。

37. 归并排序

归并 ：将两个有序表和为一个有序表。归并排序：将n个元素视为n个有序表，先两两合并，再两两合并，直到全部合并。
单独一个数组归并，时间：O(nlogn)，空间：O(n)，归并排序算法比较占用内存，但却是效率高且稳定的排序算法。一般在外排序中使用。归并的趟数是logn。

38. 基数排序

39.排序算法的一些特点

堆排序、冒泡排序、快速排序在每趟排序过程中,都会有一个元素被放置在其最终的位置上。
高效稳定的算法：归并
不稳定的排序方法：快排，堆排，希尔，选择