数据结构

线性数据结构

  1. 数组（Array）

    • 实现方式：
      • 静态数组：在声明时指定大小，编译器分配固定大小的内存。
      • 动态数组：在运行时动态分配内存，如 C++ 中的 std::vector。
    • 特点：固定大小，通过索引访问。
    • 应用：基本数据存储、矩阵运算等。

  2. 链表（Linked List）

    • 单链表（Singly Linked List）：
      • 实现方式：每个节点包含数据和一个指向下一个节点的指针。
      • 特点：动态大小，通过指针链接节点。
    • 双向链表（Doubly Linked List）：
      • 实现方式：每个节点包含数据和两个指针，分别指向前一个节点和后一个节点。
      • 特点：支持双向遍历。
    • 循环链表（Circular Linked List）：
      • 实现方式：最后一个节点的指针指向第一个节点，形成闭环。
      • 特点：没有头尾之分，适用于某些循环操作。
    • 应用：动态数据存储、内存管理等。

  3. 栈（Stack）

    • 实现方式：
      • 数组实现：使用数组模拟栈，通过一个指针记录栈顶位置。
      • 链表实现：使用链表模拟栈，通过一个指针指向栈顶节点。
    • 特点：后进先出（LIFO）。
    • 应用：表达式求值、回溯算法等。

  4. 队列（Queue）

    • 普通队列（FIFO）：
      • 实现方式：
        • 数组实现：使用数组模拟队列，通过两个指针分别记录队头和队尾位置。
        • 链表实现：使用链表模拟队列，通过两个指针分别指向队头和队尾节点。
    • 优先队列（Priority Queue）：
      • 实现方式：通常使用堆（如最大堆或最小堆）实现，支持按优先级出队。
    • 双端队列（Deque）：
      • 实现方式：可以在两端进行插入和删除操作，通常使用双向链表实现。
    • 特点：先进先出（FIFO）。
    • 应用：任务调度、缓冲区管理等。

  5. 向量（Vector）

    • 实现方式：
      • 动态数组：内部使用一个数组存储元素，当数组满时，动态扩容。
    • 特点：动态数组，大小可变。
    • 应用：动态数据存储、列表操作等。

非线性数据结构

  1. 树（Tree）

    • 二叉树（Binary Tree）：
      • 实现方式：每个节点包含数据和两个指针，分别指向左子节点和右子节点。
    • 二叉搜索树（Binary Search Tree）：
      • 实现方式：每个节点的左子树只包含比该节点小的值，右子树只包含比该节点大的值。
    • 平衡二叉树（Balanced Binary Tree）：
      • AVL 树：
        • 实现方式：每个节点记录其左右子树的高度差，通过旋转操作保持平衡。
      • 红黑树（Red-Black Tree）：
        • 实现方式：每个节点有一个颜色属性（红色或黑色），通过特定规则保持平衡。
    • 堆（Heap）：
      • 最大堆（Max Heap）：
        • 实现方式：每个节点的值大于或等于其子节点的值，通常使用数组实现。
      • 最小堆（Min Heap）：
        • 实现方式：每个节点的值小于或等于其子节点的值，通常使用数组实现。
    • B 树和 B + 树：
      • 实现方式：多路搜索树，每个节点可以有多个子节点，B + 树的所有关键字都在叶子节点上。
    • 字典树（Trie）：
      • 实现方式：每个节点代表一个字符，通过路径表示字符串。
    • 后缀树（Suffix Tree）：
      • 实现方式：每个节点代表一个后缀，通过路径表示字符串的后缀。
    • 特点：分层结构，节点间有父子关系。
    • 应用：文件系统、数据库索引、字符串匹配等。

  2. 图（Graph）

    • 无向图（Undirected Graph）：
      • 实现方式：
        • 邻接矩阵：使用二维数组表示节点之间的连接关系。
        • 邻接表：使用链表或数组存储每个节点的邻接节点。
    • 有向图（Directed Graph）：
      • 实现方式：与无向图类似，但边有方向。
    • 加权图（Weighted Graph）：
      • 实现方式：在邻接矩阵或邻接表中存储边的权重。
    • 特点：节点通过边连接，表示复杂关系。
    • 应用：社交网络、路径规划、网络拓扑等。

其他数据结构

  1. 哈希表（Hash Table）

    • 实现方式：
      • 散列表：使用哈希函数将键映射到数组中的索引位置，处理冲突的方法包括链地址法和开放地址法。
    • 特点：通过哈希函数将键映射到表中的位置，支持快速查找。
    • 应用：字典、缓存、集合操作等。

  2. 跳表（Skip List）

    • 实现方式：
      • 多层链表：每一层都是一个有序链表，高层链表的节点间隔更大，通过多层索引加速查找速度。
    • 特点：通过多层索引加速链表的查找速度。
    • 应用：快速查找、排序等。

  3. 布隆过滤器（Bloom Filter）

    • 实现方式：
      • 位数组：使用一个位数组和多个哈希函数，通过哈希函数将元素映射到位数组中的多个位置。
    • 特点：空间效率高，用于测试元素是否属于集合，允许误报但不允许漏报。
    • 应用：大数据中的成员测试、缓存过滤等。

  4. 并查集（Disjoint Set / Union-Find）

    • 实现方式：
      • 路径压缩：通过路径压缩优化查找操作，使查找操作的时间复杂度接近常数。
      • 按秩合并：通过按秩合并优化合并操作，保持树的高度较低。
    • 特点：用于管理不相交集合，支持高效的合并和查找操作。
    • 应用：连通性问题、动态连通性等。

  5. 位图（Bitmap）

    • 实现方式：
      • 位数组：使用一个位数组，每个位表示一个状态。
    • 特点：利用位来表示信息，非常节省空间。
    • 应用：内存管理、文件权限管理等。

  6. 空间划分数据结构

    • 四叉树（Quadtree）：
      • 实现方式：将平面区域递归地划分为四个子区域，每个节点最多有四个子节点。
    • 八叉树（Octree）：
      • 实现方式：将三维空间区域递归地划分为八个子区域，每个节点最多有八个子节点。
    • kd 树：
      • 实现方式：通过交替选择不同的维度进行分割，构建一棵二叉树。
    • 特点：用于处理多维空间数据，支持区域查询和碰撞检测。
    • 应用：图像处理、计算机图形学等。

  7. LRU 缓存（Least Recently Used Cache）

    • 实现方式：
      • 哈希表 + 双向链表：使用哈希表存储键值对，双向链表维护最近使用的顺序，每次访问或插入时更新链表。
    • 特点：维护一个最近最少使用的缓存，支持高效的缓存淘汰策略。
    • 应用：缓存机制、浏览器历史记录等。