数据结构
2024-08-28 10:34:16
发布于:广东
这里的数据结构是指 提高级要求掌握 的数据结构
内容太多了,我就简单讲讲他们,想深入了解的最好还是去网上看看大佬的讲解
1. 线性结构
-
双端栈:
- 描述:可以在栈的两端进行插入和删除操作。
- 用途:适合需要双端操作的场景,如回溯算法。
-
双端队列:
- 描述:支持两端插入和删除操作的队列。
- 用途:适合需要两端操作的场景,比如滑动窗口问题。
-
有序队列:
- 描述:队列中的元素是有序的。
- 用途:常用于需要保持元素有序的场景,如优先级调度。
-
优先队列:
- 描述:元素按优先级排序,最高优先级的元素会被优先处理。
- 用途:广泛用于调度、算法(如 Dijkstra 算法)等场景。
-
倍增表(ST表):
- 描述:用于高效查询区间最小值或最大值,支持快速的区间查询。
- 用途:常用于区间查询、最小值/最大值查询等问题。
2. 集合与森林
-
等价类:
- 描述:将元素分成互相等价的类。
- 用途:用于处理等价关系问题,如集合划分。
-
并查集:
- 描述:支持合并和查找操作的数据结构。
- 用途:用于处理集合的并合问题,如网络连接、社区检测等。
-
树与二叉树的转化—孩子兄弟表示法:
- 描述:将树结构转换为二叉树结构的表示方法。
- 用途:用于简化树的操作,使得可以使用二叉树的算法处理树结构。
3. 特殊树
-
线段树与树状数组:
- 线段树:支持区间查询和更新操作的树结构。
- 树状数组(Binary Indexed Tree):用于高效的前缀和查询和更新操作。
- 用途:广泛用于区间操作,如区间求和、区间最小值等。
-
字典树(Trie树):
- 描述:一种多叉树,用于高效的字符串查找。
- 用途:主要用于字符串的前缀匹配和词典实现。
-
笛卡尔树:
- 描述:一种随机化树结构,支持高效的区间查询和更新。
- 用途:用于优先队列的实现、区间最小值查询等。
-
二叉平衡树(AVL树、Treap、Splay树):
- AVL树:自平衡的二叉搜索树,保持树的高度平衡。
- Treap:结合了二叉搜索树和堆的性质,支持随机化操作。
- Splay树:自调整的二叉搜索树,具有良好的摊还时间复杂度。
- 用途:用于需要高效的插入、删除和查找操作的场景。
-
基环树:
- 描述:一种特殊的树结构,主要用于表示关系图。
- 用途:主要用于图的处理和分析。
4. 常见图
-
稀疏图:
- 描述:边数远小于节点数的平方。
- 用途:常用于描述大规模网络,如社交网络。
-
偶图(二分图):
- 描述:图的顶点可以分为两个集合,且图中每条边都连接两个不同集合的顶点。
- 用途:用于任务分配、匹配问题等。
-
欧拉图:
- 描述:包含一个欧拉回路的图,即每条边都恰好经过一次。
- 用途:用于解决行程问题,如找寻一条经过所有街道的路径。
-
有向无环图(DAG):
- 描述:没有环的有向图。
- 用途:用于任务调度、拓扑排序等。
-
连通图与强连通图:
- 连通图:图中任意两点之间都有路径。
- 强连通图:有向图中任意两点之间都有路径。
- 用途:用于图的连通性分析和路径问题。
-
重连通图:
- 描述:通过添加边来使图变得连通。
- 用途:用于网络设计和优化。
5. 哈希表
-
数值哈希函数构造:
- 描述:将数值映射到哈希表中的位置。
- 用途:用于快速数据查找和插入操作。
-
排列哈希函数构造:
- 描述:用于处理排列问题的哈希函数。
- 用途:常用于排列数据的查找和比较。
-
字符串哈希函数构造:
- 描述:将字符串映射到哈希表中的位置。
- 用途:用于字符串查找、比对等操作。
-
哈希函数冲突的常用解决方法:
- 开放地址法:处理哈希表中冲突的方法之一,通过探测寻找空位置。
- 链地址法:将冲突的元素存储在链表中。
- 再哈希法:当哈希表负载过高时,重新计算哈希函数并扩展表的大小。
这里空空如也
有帮助,赞一个