数据结构分类总结[多达80种,offer收割机]

1. 线性结构：

• • 数组（Array）
  • 链表（Linked List）：包括单链表、双向链表和循环链表
  • 栈（Stack）：后进先出（LIFO）的数据结构
  • 队列（Queue）：先进先出（FIFO）的数据结构
  • 双端队列（Deque）：允许在两端进行插入和删除操作

1. 非线性结构：

• • 树（Tree）：包括二叉树、平衡二叉树、二叉搜索树、AVL树、红黑树等
  • 图（Graph）：包括有向图、无向图、加权图、无权图等

1. 散列结构：

• • 哈希表（Hash Table）：通过哈希函数将键映射到表中的位置

1. 索引结构：

• • B树（B-Tree）：用于数据库和文件系统中的索引结构
  • B+树（B+-Tree）：B树的变体，所有数据都存储在叶子节点

1. 堆结构：

• • 二叉堆（Binary Heap）：包括最大堆和最小堆

1. 其他高级数据结构：

• • 优先队列（Priority Queue）
  • 集合（Set）和多重集合（Multiset）
  • 字典（Dictionary）或映射（Map）
  • 并查集（Disjoint Set Union，DSU）
  • 布隆过滤器（Bloom Filter）
  • 后缀树（Suffix Tree）
  • 后缀数组（Suffix Array）
  • 树状数组（Trie）：又称前缀树或字典树

1. 特殊用途的数据结构：

• • 线段树（Segment Tree）
  • 动态规划中的表格
  • 矩阵链乘问题中的最优子结构

1. 并行和分布式数据结构：

• • 并行数据结构：用于多核处理器或分布式计算环境中
  • 分布式数据结构：用于分布式系统中，如分布式哈希表（DHT）

1. 自适应数据结构：

• • 动态数组（Dynamic Array）：如C++中的std::vector，Java中的ArrayList。
  • 动态字符串（Dynamic String）：允许在字符串中间插入和删除字符。

1. 空间划分数据结构：

• • 四叉树（Quadtree）：用于二维空间的划分，常用于地理信息系统和图像处理。
  • 八叉树（Octree）：三维空间的划分，常用于三维空间的快速检索。

1. 几何数据结构：

• • 凸包数据结构（Convex Hull Data Structure）：用于存储点集的凸包。

1. 图论算法中的辅助数据结构：

• • 最短路径树（Shortest Path Tree）：如Dijkstra算法或Bellman-Ford算法中使用的。
  • 最小生成树（Minimum Spanning Tree, MST）：如Prim算法或Kruskal算法中使用的。

1. 流数据结构：

• • 布隆过滤器（Bloom Filter）：用于快速判断元素是否在一个集合中。
  • 计数布隆过滤器（Counting Bloom Filter）：布隆过滤器的扩展，可以删除元素。

1. 外部数据结构：

• • 外部排序（External Sorting）：当数据太大无法一次性加载到内存时使用。

1. 缓存数据结构：

• • LRU缓存（Least Recently Used Cache）：最近最少使用算法。
  • LFU缓存（Least Frequently Used Cache）：最少使用频率算法。

1. 序列化和反序列化数据结构：

• • 用于将数据结构转换为字节序列，以便存储或传输。

1. 并发数据结构：

• • 线程安全的队列、栈、集合等，用于多线程环境中。

1. 数据库索引数据结构：

• • 哈希索引、B树索引、位图索引等，用于数据库中快速检索数据。

1. 压缩数据结构：

• • 用于减少数据存储空间的数据结构，如前缀树的压缩变体。

1. 特殊用途的数据结构：

• • 环形缓冲区（Circular Buffer）：固定大小的缓冲区，用于数据流的缓存。
  • 滑动窗口（Sliding Window）：用于处理数据流中的固定大小窗口问题。

1. 平衡树的变种：

• • Splay树：一种通过旋转操作来重新平衡的二叉搜索树。
  • Treap：二叉搜索树的变种，使用随机生成的优先级来保持平衡。

1. 线段树的变种：

• • 懒惰线段树（Lazy Segment Tree）：用于延迟更新操作，提高效率。

1. 树状数组（Binary Indexed Tree, BIT）：

• • 又称为Fenwick树，用于处理序列数据的加法和前缀和问题。

1. 后缀自动机（Suffix Automaton）：

• • 一种用于处理字符串后缀的自动机结构，可以用于多种字符串匹配问题。

1. 区间树（Interval Tree）：

• • 用于存储区间数据，并快速查询重叠区间。

1. 曼哈顿距离树（Manhattan Distance Tree）：

• • 用于二维空间中计算曼哈顿距离的树结构。

1. K-D树（K-Dimensional Tree）：

• • 一种用于k维空间的分割树，用于快速检索。

1. 网络流数据结构：

• • 用于网络流问题，如最大流问题和最小费用流问题。

1. 近似最近邻（Approximate Nearest Neighbor, ANN）：

• • 用于在高维空间中快速找到近似的最近邻。

1. 数据流中的摘要数据结构：

• • 如计数器、T-Digest等，用于估计数据流中的分布。

1. 分块数据结构：

• • 将数据分成块，每块使用不同的数据结构来优化特定操作。

1. 自适应字典树（Adaptive Dictionary Tree）：

• • 一种可以根据字符串的频率动态调整的字典树。

1. 网格数据结构：

• • 用于表示和操作二维或多维网格数据。

1. 位图索引（Bitmap Index）：

• • 一种使用位数组来表示数据的存在或不存在的索引结构。

1. 数据流中的MQ（Median, Quantile）树：

• • 用于估计数据流中的中位数或其他分位数。

1. 数据流中的Cuckoo哈希：

• • 一种哈希表结构，允许多个键映射到同一个位置。

1. 数据流中的HyperLogLog：

• • 一种用于估计数据流中不同元素数量的数据结构。

1. 数据流中的MinHash：

• • 用于估计数据集中的近似Jaccard相似度。

1. Skip List：

• • 一种概率平衡的数据结构，它允许快速地进行搜索、插入和删除操作。

1. Cuckoo Filter：

• • 一种高效的近似集合数据结构，用于快速检查元素是否存在。

1. Rope：

• • 一种用于高效存储和操作长字符串的数据结构。

1. Skip Graph：

• • 一种分布式系统中使用的图结构，允许快速查找和遍历。

1. Van Emde Boas Tree：

• • 一种用于存储和快速检索有限范围内的整数的数据结构。

1. Y-fast Trie：

• • 一种用于存储字符串集合的数据结构，它结合了Trie和二叉搜索树的优点。

1. X-fast Trie：

• • Y-fast Trie的改进版本，进一步优化了空间和时间效率。

1. 后缀数组的变种：

• • 如双后缀数组（Double Suffix Array）等。

1. LZW压缩算法：

• • 一种用于无损数据压缩的算法，它构建了一个基于输入数据的字典。

1. B树的变种：

• • 如B*树，它是一种优化的B树，用于减少磁盘I/O操作。

1. 关联数组：

• • 一种使用键值对存储数据的数据结构，类似于哈希表。

1. Fat/Slim树：

• • 一种用于数据库索引的数据结构，它结合了B树和B+树的特点。

1. Hopscotch哈希：

• • 一种哈希表的变体，它允许哈希表在高负载因子下保持性能。

1. 配对堆（Pairing Heap）：

• • 一种基于二叉树的自适应堆结构，具有优秀的平均性能。

1. 斐波那契堆（Fibonacci Heap）：

• • 一种具有优异的摊还分析性能的堆结构。

1. 网络流算法中的预流图（Preflow Graph）：

• • 在最大流问题中使用的数据结构。

1. 网格哈希（Grid Hash）：

• • 一种用于快速检索二维空间中对象的哈希表。

1. 动态图数据结构：

• • 用于存储和操作图中的边和顶点，允许动态添加和删除。

1. 区间最小/最大查询数据结构：

• • 用于快速查询区间内的最小或最大值。

1. 树状数组的变种：

• • 如RMQ树（Range Minimum Query Tree），用于区间最小值查询。

1. 多维数据结构：

• • 如k-d树、多维数组等，用于多维数据的存储和检索。

1. 位图索引（Bitmap Index）：

• • 用于快速检索布尔值数据。

1. 并查集的变种：

• • 如路径压缩的并查集，用于快速的联合和查找操作。

1. 差分数组：

• • 一种用于快速区间更新和区间查询的数据结构。

1. 持久化数据结构：

• • 允许在多个版本中存储和访问数据结构的状态。

1. 堆栈森林（Stack Forest）：

• • 一种用于模拟多个栈的数据结构，可以高效地合并和拆分栈。

1. 队列森林（Queue Forest）：

• • 类似于堆栈森林，但用于模拟多个队列。

1. 线性同构树（Linear Homogeneous Tree）：

• • 一种用于区间查询和区间更新的数据结构。

1. 线段树的优化版本：

• • 如树状线段树（Segment Tree with Lazy Propagation）。

1. 树状数组的优化版本：

• • 如可持久化树状数组（Persistent Binary Indexed Tree）。

1. 链表的变种：

• • 如循环链表、双向循环链表、有序链表等。

1. 栈的变种：

• • 如后缀表达式栈、逆波兰表达式栈等。

1. 队列的变种：

• • 如优先队列、指数级退避队列等。

1. 哈希表的变种：

• • 如开放寻址法哈希表、链表法哈希表等。

1. 图的变种：

• • 如邻接表、邻接矩阵、十字链表、边集数组等。

1. 树状图（Tree Graph）：

• • 结合了树和图的特点，用于表示具有层次结构的图。

1. 有向无环图（Directed Acyclic Graph, DAG）：

• • 一种特殊的图，没有环，常用于拓扑排序和任务调度。

1. 并查集的优化版本：

• • 如按秩合并（Union by Rank）和路径压缩（Path Compression）。

1. 配对堆（Pairing Heap）：

• • 一种基于树的自适应堆结构，具有优秀的平均性能。

1. 斐波那契堆（Fibonacci Heap）：

• • 一种具有优异的摊还分析性能的堆结构。

1. 二项堆（Binary Heap）：

• • 一种基于完全二叉树的堆结构，可以是最大堆或最小堆。

1. 红黑树的变种：

• • 如SB树（Scatter-Bound Tree）等。

1. AVL树的变种：

• • 如2-3树、2-4树等。

1. Treap（树堆）：

• • 结合了二叉搜索树和堆的特性。

1. 字典树（Trie）的变种：

• • 如压缩字典树（Compressed Trie）、后缀字典树（Suffix Trie）等。

1. 区间树的变种：

• • 如区间线段树（Interval Segment Tree）等。

1. 多关键字搜索树（Multi-Keyword Search Tree）：

• • 一种用于多属性搜索的树结构。

1. 动态图的变种：

• • 如动态并查集、动态图的邻接表等。

1. 网格数据结构的变种：

• • 如二维数组、二维链表等。

1. 特殊矩阵的存储结构：

• • 如对称矩阵、稀疏矩阵等。