数据结构 | 依邻依伴

算法的数据结构是算法设计和实现的基础，它们提供了组织和存储数据的有效方式，以便算法能够高效地访问和处理数据。以下是一些常见的数据结构：

数组（Array）：

数组（Array）是一种基本的数据结构，用于存储相同类型的多个元素。在不同的编程语言中，数组的实现和特性可能有所不同，但它们通常具有以下共同特点：

元素类型相同：数组中的所有元素都是同一数据类型，如整数、浮点数、字符或对象。
连续存储：数组的元素在内存中通常是连续存储的，这使得通过索引访问元素非常快速。
固定或动态大小：在某些语言中（如C或C++），数组的大小在声明时确定，并且通常是固定的。而在其他语言中（如Python、Java、JavaScript），数组的大小是动态的，可以根据需要增长或缩小。
索引访问：可以通过索引（通常是从0开始的整数）快速访问数组中的任何元素。
遍历：可以通过循环结构遍历数组中的所有元素。

链表（Linked List）：

链表（Linked List）是一种基本的数据结构，由一系列节点组成，每个节点包含两部分：数据和指向下一个（或上一个，或两者）节点的指针。链表的结构使得它在某些操作中比数组更灵活，尽管在其他操作中可能效率较低。链表的类型包括：

单向链表（Singly Linked List）：每个节点包含一个指向下一个节点的指针。
双向链表（Doubly Linked List）：每个节点包含两个指针，一个指向前一个节点，一个指向下一个节点。
循环链表（Circular Linked List）：链表的最后一个节点的指针指向第一个节点，形成一个环。

特点：

动态大小：链表的大小可以动态变化，不需要在创建时确定。
非连续存储：链表的元素在内存中不必连续存储，每个元素通过指针连接到下一个元素。
插入和删除操作：在链表中插入和删除节点通常比在数组中更高效，因为不需要移动其他元素。
访问速度：链表不支持随机访问，访问特定位置的元素需要从头开始遍历，直到到达目标位置。

栈（Stack）：

栈（Stack）是一种遵循后进先出（Last In First Out, LIFO）原则的数据结构。在栈中，最后添加的元素将是第一个被移除的元素。这种特性使得栈在许多算法和编程任务中非常有用。

特点：

限制性访问：只能在栈顶进行添加和移除操作。
动态大小：大多数实现允许栈的大小动态变化。
内存效率：通常使用数组或链表来实现，可以有效地利用内存。

队列（Queue）：

遵循先进先出（FIFO）原则的线性数据结构。
允许在一端添加元素，在另一端移除元素。
队列（Queue）是一种遵循先进先出（First In First Out, FIFO）原则的数据结构。在队列中，最先添加的元素将是第一个被移除的元素。这种特性使得队列在许多需要保持元素顺序的场景中非常有用。

特点：

有序访问：元素按照它们被添加的顺序进行访问。
动态大小：大多数实现允许队列的大小动态变化。
两端操作：操作主要集中在队列的两端，一端用于添加元素（enqueue），另一端用于移除元素（dequeue）。

双端队列（Deque）：

双端队列（Deque，全称 Double-Ended Queue）是一种具有队列和栈特性的数据结构，它允许在两端进行添加（enqueue）和移除（dequeue）操作。这种灵活性使得双端队列在多种算法和应用中非常有用。

特点：

两端操作：可以在两端自由地添加和移除元素。
动态大小：大多数实现允许双端队列的大小动态变化。
灵活性：结合了队列（FIFO）和栈（LIFO）的特性，可以根据需要选择操作端。

哈希表（Hash Table）：

哈希表（Hash Table），也称为散列表，是一种通过哈希函数将键（Key）映射到表中一个位置以便存储和检索数据的数据结构。它提供了非常快速的数据插入、删除和查找操作，特别是在处理大量数据时。

工作原理：

哈希函数：哈希表使用一个哈希函数，将键映射到一个索引上，这个索引决定了数据在哈希表中的存储位置。
解决冲突：由于不同的键可能映射到同一个索引，因此需要一种方法来解决这种冲突。常见的方法包括链地址法（使用链表存储具有相同哈希值的元素）和开放寻址法（寻找表中的下一个空闲位置）。

特点：

快速访问：在理想情况下，哈希表可以在常数时间内完成插入、删除和查找操作。
动态大小：许多哈希表实现允许动态调整大小，以保持操作的效率。
冲突处理：冲突是哈希表性能的关键因素，需要有效的冲突解决策略。

树（Tree）：

树（Tree）是一种非线性数据结构，由节点（Node）组成，每个节点包含数据和指向其他节点的链接（通常称为边或指针）。

树的基本术语：

节点（Node）：树的基本单元，包含数据和指向其他节点的链接。
根节点（Root）：树的顶级节点，没有父节点。
子节点（Child）：与特定节点直接相连的节点。
父节点（Parent）：与特定节点直接相连的节点的上一级节点。
叶节点（Leaf）：没有子节点的节点。
边（Edge）：连接两个节点的链接。
路径：从根节点到叶节点的一系列相连的节点。
深度（Depth）：从根节点到特定节点的路径上的边的数量。
高度（Height）：树中最长路径上的边的数量。

树的类型：

二叉树（Binary Tree）：每个节点最多有两个子节点（左子节点和右子节点）。
平衡树（Balanced Tree）：如AVL树，保持树的高度平衡，以确保操作的效率。
搜索树（Search Tree）：如二叉搜索树（BST），节点的数据有序，以便进行快速搜索。
堆（Heap）：一种特殊的二叉树，满足父节点的值总是大于（或小于）子节点的值。
B树（B-Tree）：用于数据库和文件系统的多路搜索树，可以有多个子节点。
红黑树（Red-Black Tree）：一种自平衡的二叉搜索树。
后缀树（Suffix Tree）：用于处理字符串的高效数据结构。

图（Graph）：

图（Graph）是一种数据结构，用于表示一组对象（顶点或节点）及其之间的关系（边）。图可以是无向的或有向的，并且可以是加权的或无权的。

图的基本术语：

顶点（Vertex）：图中的点，代表一个对象或实体。
边（Edge）：连接两个顶点的线，代表顶点之间的关系。
邻接（Adjacency）：如果两个顶点之间有边，则它们是邻接的。
无向图（Undirected Graph）：图中的边没有方向，即如果顶点A与顶点B相连，则它们互为邻接。
有向图（Directed Graph）：图中的边有方向，通常称为弧（Arc），表示从一个顶点指向另一个顶点的关系。
权重（Weight）：边的属性，表示连接两个顶点的代价或距离。
路径（Path）：顶点和边的序列，从一个顶点开始，通过一系列边到达另一个顶点。
环（Cycle）：一个起点和终点相同的路径，没有重复的顶点（除了起点和终点）。
连通图（Connected Graph）：任意两个顶点之间都存在路径。
分量（Component）：在非连通图中，最大的连通子图称为分量。
度（Degree）：顶点的边的数量。在有向图中，分为入度（指向顶点的边的数量）和出度（从顶点出发的边的数量）。

图的表示方法：

邻接矩阵（Adjacency Matrix）：使用二维数组表示，矩阵的行和列代表顶点，元素值表示顶点之间的连接关系（无向图）或方向关系（有向图）。
邻接表（Adjacency List）：使用链表表示，每个顶点对应一个链表，链表中包含与该顶点相邻的所有顶点。
边列表（Edge List）：列出图中所有的边，通常用于表示无向图。

堆（Heap）：

堆（Heap）是一种特殊的完全二叉树，它满足特定的性质，通常用于实现优先队列。在堆中，每个节点的值都遵循一定的顺序规则，最常见的是最大堆和最小堆。

最大堆（Max Heap）：在最大堆中，父节点的值总是大于或等于其子节点的值。堆的顶部（根节点）是最大值。
最小堆（Min Heap）：在最小堆中，父节点的值总是小于或等于其子节点的值。堆的顶部（根节点）是最小值。
完全二叉树：除了最后一层外，每一层都被完全填满，并且最后一层的节点都尽可能地向左对齐。
堆序性质：每个节点的值满足最大堆或最小堆的顺序规则。
数组：堆通常使用数组来表示，其中每个元素的子节点可以通过索引计算得到。对于给定索引 i的元素，其左子节点的索引为 2*i + 1，右子节点的索引为 2*i + 2，父节点的索引为 (i - 1) / 2（假设索引从0开始）。

集合（Set）：

集合（Set）是一种数据结构，用于存储一组不重复的元素。在编程语言中，集合通常提供了一种快速检查成员资格、删除重复项和执行集合运算（如并集、交集、差集）的方法。

特点：

无序性：集合中的元素没有固定的顺序。
唯一性：集合中的每个元素都是唯一的，不允许重复。
动态性：集合的大小可以动态变化，可以添加或删除元素。

字典（Dictionary）或映射（Map）：

字典（Dictionary）或映射（Map）是一种存储键值对（Key-Value Pairs）的数据结构，它允许你通过键（Key）来快速检索、添加或删除对应的值（Value）。

字典/映射的特点：

键值对存储：每个元素由一个键和一个与之对应的值组成。
唯一键：每个键在字典中是唯一的，不允许重复。
快速访问：通过键可以快速访问对应的值，通常在常数时间内完成。
动态大小：字典的大小可以根据需要动态变化。

并查集（Disjoint Set Union, DSU）：

并查集（Disjoint Set Union, DSU）是一种数据结构，用于处理一些不相交集合的合并及查询问题。它在许多算法问题中非常有用，尤其是在那些需要动态地连接和查询两个元素是否在同一集合的问题中。并查集可以高效地执行以下两个主要操作：

查找（Find）：确定两个元素是否属于同一个集合。
合并（Union）：合并两个集合。

线段树（Segment Tree）：

线段树（Segment Tree）是一种高级的数据结构，用于处理与数组相关的各种问题，特别是那些涉及区间查询和区间更新的问题。它允许在对数时间内完成这些操作，这使得线段树非常适合需要频繁更新和查询的场景。

线段树的构建：

线段树的构建通常从代表整个数组的根节点开始，然后递归地将区间分成两半，直到每个叶子节点代表数组中的一个单独元素。对于区间查询，叶子节点代表单个元素的区间，而非叶子节点代表更广泛的区间。

特点：

二叉树结构：线段树是一种二叉树，其中每个节点代表数组的一个区间。
完全二叉树：为了高效地映射数组索引，线段树通常被构建为一棵完全二叉树。
动态更新：可以动态地更新节点代表的区间的信息。

树状数组（Binary Indexed Tree, BIT 或 Fenwick Tree）：

树状数组（Binary Indexed Tree，简称 BIT），也被称为 Fenwick Tree，是一种用于在对数时间内完成数据集合的统计和更新的数据结构。它特别适合用于处理一维数据的区间查询和更新问题，如区间求和、区间最小值或最大值查询等。

基本原理：

树状数组是一种基于二进制指数加法原理的数据结构。它使用一个数组来存储数据，并通过特定的索引计算方法来实现快速的区间查询和更新。

后缀数组（Suffix Array）和后缀树（Suffix Tree）：

后缀数组（Suffix Array）和后缀树（Suffix Tree）是两种用于处理字符串的高级数据结构，它们在字符串处理、文本搜索、生物信息学等领域有着广泛的应用。这两种结构都可以在一定程度上帮助解决字符串的快速检索问题，但它们在实现和使用上有所不同。

后缀数组（Suffix Array）

后缀数组是一种用于存储字符串所有后缀的有序数组，使得通过这个数组可以快速比较字符串中的所有子串。

特点：

构建：后缀数组通过将字符串的所有后缀（包括空串）按照字典序排序并存储在一个数组中来构建。
快速访问：通过后缀数组，可以快速访问到字符串的任何后缀。
空间效率：相比于后缀树，后缀数组更加空间高效，因为它只存储后缀的起始位置，而不是完整的后缀。

后缀树（Suffix Tree）

后缀树是一种更为复杂的数据结构，它是一种 trie（前缀树），其中每个节点的子节点代表原字符串的一个后缀。

特点：

构建：后缀树通过将字符串的所有后缀构建成一个 trie 结构来实现，每个后缀从树的根开始，沿着树向下扩展。
空间消耗：相比于后缀数组，后缀树通常需要更多的空间，因为它存储了所有后缀的完整路径。
快速搜索：后缀树可以快速地执行字符串搜索，因为它将所有后缀存储在树中。