链表、树和图专项练习

最新推荐文章于 2024-09-08 15:25:36 发布

Caoyy686868

最新推荐文章于 2024-09-08 15:25:36 发布

阅读量340

点赞数

文章标签：链表数据结构树图

本文链接：https://blog.csdn.net/YYSTINTERNET/article/details/125509361

版权

带头结点单链表：head->next==NULL;带头结点循环链表：head->next==head;不带头结点单链表：head==NULL。
线性表长度是所包含元素的个数。元素的类型决定了元素所占存储空间的大小。
有n个结点的二叉链表，值为空的链域个数为n+1个，非空的个数为n-1。
线性表=顺序表+链表。
深度遍历用栈，广度遍历用队列。
链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。
栈是解决封闭对应问题的有效方法。比如在解析XML中，遇到一个<demo>标签（左标签）就入栈，遇到其子标签的左标签（如<subdemo>）同样入栈。遇到右标签(如</subdemo>或</demo>)就校验栈顶标签是否与该右标签对应，能对应就出栈，不能对应则说明标签不对称，是无效的XML文件。
如果链表数据是无序的，则单向搜索与双向搜索平均速度相同。如果链表是有序的，而要搜索的数据距离最小值（最大值）较近，这种情况下的双向搜索平均速度更快。因此双向搜索更稳定，方差更小。
链表和数组的区别：

链表是链式存储结构，数组是顺序存储结构；

链表通过指针连接元素，而数组则是把所有元素按顺序进行存储；

链表插入和删除元素不需要移动元素，数组删除和增加元素需要移动元素。
需要分配较大的空间，插入和删除不需要移动元素的线性表，其存储结构是静态链表。
B树支持随机搜索，B+树支持随机和顺序搜索。
在哈夫曼树（二叉）中，结点的度可能为0或2。、
红黑树的插入复杂度为O(log(n))。
完全二叉树满足，深度h： $2^{h}-1\geq n,h\geq log_{2}(n+1)$ 。
TRIE树，又称单词查找树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度的减少无谓的字符串比较，查询效率比哈希表高。
计算树叶子结点的等量关系为：边数相等。例如：e=n-1=n0+n1+n2+n3+n4+n5-1，e=n0*0+n1*1+n2*2+n3*3+n4*4+n5*5。
具有n个结点的二叉树的形态个数计算公式： $C_{2n}^{n}/(n+1)$ 。
B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；B-树：多路搜索树，每个结点存储向上取整M/2-1到M-1个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整棵树中出现，且只出现一次，非叶子结点可以命中；B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3。
不稳定排序：快速排序、希尔排序、选择排序、堆排序。
LTag=0：lchild域指示结点的左孩子；LTag=1：lchild域指示结点的前驱；
RTag=0：rchild域指示结点的右孩子；RTag=1：rchild域指示结点的后继。
M阶B-树中含有N个关键字，最大深度为 $log_{\frac{M}{2}}(\frac{N+1}{2})+2$ 。
平衡二叉树：插入点位于x的左孩子的左子树中（LL型）；插入点位于x的左孩子的右子树中（LR型）；插入点位于x的右孩子的左子树中（RL型）；插入点位于x的右孩子的右子树中（RR型）。
n个结点，k条边的森林，共有n-k棵树。
n个结点的满二叉树调整成最小堆的最优复杂度O(n)。
有n个数构造出的Huffman树共有2n-1个结点。
n个结点的线索二叉树上含有的线索树为n+1。
二叉树线索化后，“前序求后继，后序求前驱，中序啥都行。”
一棵左右子树不空的二叉树：先序线索化和后序线索化空指针域都是1，中序线索化为2。
采用邻接表存储的图按深度优先搜索方法进行遍历的算法类似于二叉树的先序遍历；

采用邻接表存储的图按广度优先搜索方法进行遍历的算法类似于二叉树的层序遍历。
图的广度优先（队列），深度优先（栈）。
求图的最小生成树算法：prim算法权值可正可负（稠密图）、Kruskal算法（稀疏图）；求图最短路径算法：Dijkstra算法不能有负的权值（单源）、DFS/BFS（单源）、Floyed算法（多源）、Bellman-Ford算法（单源、负权）。
m阶B-树：一种平衡的多路查找树；树中每个结点至多有m棵子树；若根节点不是叶子结点，则至少有两颗子树。
从二叉排序树中查找一个元素时，其时间复杂度一般为O（log2n）
平衡二叉树本质是二叉排序树。
拓扑排序是结点的逻辑排序。
路径最长叫关键路径，关键路径上面的活动叫做关键活动。
图中任意两点度的和大于或等于顶点总数，那么这个图一定是哈密顿图。
对于用邻接表表示图（包含n个定点e条边）时，拓扑排序算法时间复杂度为O(n+e)。
求最短路径的 FLOYD 算法的时间复杂度为O(n^3),空间复杂度O(n^2)。
一个无向图的连通分量是其极大地连通子图。
无向图特有：邻接多重表；有向图特有：十字链表，边集数组；二者共有：邻接表，邻接矩阵。
检测有向图中是否存在环的算法：深度优先遍历，拓扑排序。