一、数据结构是计算机科学的基石，也是算法设计和系统开发的底层支撑。

1. 线性结构 (Linear Structures)

数据元素之间存在一对一的线性关系。

• 数组:
  • 特点： 内存连续，支持 $O(1)$ 随机访问（通过下标），但插入/删除需移动元素，平均 $O(n)$。
  • 应用： 缓存友好，适合作为其他数据结构的底层存储（如哈希表、堆）。
  • 变体： 动态数组（如 C++ vector, Java ArrayList）通过倍增扩容策略实现均摊 $O(1)$ 的尾部插入。
• 链表:
  • 特点： 内存离散，通过指针链接。插入/删除仅需修改指针 $O(1)$（已知位置时），但不支持随机访问，查找为 $O(n)$。
  • 类型： 单链表、双向链表、循环链表。
  • 注意： 指针操作易出错（空指针、断链），且缓存不友好。
• 栈:
  • 原则： 后进先出。
  • 核心操作： push, pop, peek 均为 $O(1)$。
  • 应用： 函数调用栈、表达式求值、括号匹配、浏览器历史记录、DFS 的非递归实现。
• 队列:
  • 原则： 先进先出。
  • 核心操作： enqueue, dequeue 均为 $O(1)$。
  • 变体： 双端队列、优先队列（本质是堆）、循环队列（解决假溢出问题）。
  • 应用： BFS、任务调度、缓冲区、消息队列。

2. 树形结构 (Tree Structures)

数据元素之间存在一对多的层次关系。

• 二叉树:
  • 遍历： 前序、中序、后序（DFS）；层序遍历（BFS）。
  • 性质： 第 $i$ 层最多 $2^{i-1}$ 个节点；深度为 $k$ 的二叉树最多 $2^k - 1$ 个节点。
• 二叉搜索树 :
  • 定义： 左子树所有值 < 根 < 右子树所有值。
  • 性能： 平均查找/插入/删除 $O(\log n)$，最坏（退化为链表）$O(n)$。
• 平衡二叉搜索树:
  • 目的： 防止 BST 退化，保证最坏情况 $O(\log n)$。
  • AVL 树： 严格平衡（左右子树高度差 $\le 1$），查找快，插入/删除旋转多。
  • 红黑树： 弱平衡，插入/删除旋转少，综合性能更优。工业界标准（Java TreeMap, C++ std::map, Linux 内核调度器）。
• 堆:
  • 定义： 完全二叉树 + 堆序性质（大顶堆/小顶堆）。通常用数组存储。
  • 操作： 建堆 $O(n)$，插入/删除堆顶 $O(\log n)$，获取极值 $O(1)$。
  • 应用： Top-K 问题、优先队列、堆排序、Dijkstra 算法。
• Trie:
  • 特点： 按字符逐层存储，利用公共前缀节省空间。
  • 应用： 自动补全、拼写检查、IP 路由最长前缀匹配、词频统计。

3. 图结构 (Graph Structures)

数据元素之间存在多对多的网状关系。

• 存储方式：
  • 邻接矩阵： 空间 $O(V^2)$，适合稠密图，判断边存在性 $O(1)$。
  • 邻接表： 空间 $O(V+E)$，适合稀疏图，遍历邻居高效。
• 遍历算法：
  • BFS： 最短路径（无权图）、连通分量、拓扑排序辅助。
  • DFS： 环检测、拓扑排序、强连通分量、回溯法基础。
• 经典算法：
  • 最短路径： Dijkstra（非负权）、Bellman-Ford（可处理负权）、Floyd-Warshall（全源）。
  • 最小生成树： Kruskal（基于并查集）、Prim。
  • 拓扑排序： Kahn 算法（入度法）、DFS 逆后序。

4. 散列结构 (Hashing)

• 核心思想： 通过哈希函数将键映射到桶索引，实现理想 $O(1)$ 的增删改查。
• 冲突解决：
  • 链地址法： 每个桶挂链表（或红黑树，当链过长时）。Java HashMap 采用此法。
  • 开放寻址法： 线性探测、二次探测、双重哈希。缓存友好，但删除复杂。
• 关键指标： 负载因子 = 元素数 / 桶数。过高需扩容重哈希。
• 设计要点： 哈希函数的均匀性、抗碰撞性；equals 与 hashCode 的一致性契约。

5. 复杂度分析速查表

数据结构	访问	搜索	插入	删除	备注
数组	$O(1)$	$O(n)$	$O(n)$	$O(n)$	尾部插入均摊 $O(1)$
链表	$O(n)$	$O(n)$	$O(1)$*	$O(1)$*	*已知节点位置
栈/队列	N/A	$O(n)$	$O(1)$	$O(1)$	仅端点操作
BST (平均)	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	最坏 $O(n)$
平衡BST	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	最坏保证
堆	N/A	$O(n)$	$O(\log n)$	$O(\log n)$	查极值 $O(1)$
哈希表	N/A	$O(1)$†	$O(1)$†	$O(1)$†	†平均情况

⚠️ 重要提醒 时间复杂度中的 $O(1)$ 对于哈希表是平均情况。在最坏情况下（所有键冲突），哈希表的操作会退化为 $O(n)$。在安全敏感场景中需考虑哈希洪水攻击防御。

1. 查找

1.1 线性查找

// 1. 手动实现线性查找（返回索引，未找到返回-1）
int linearSearch(const vector<int>& vec, int target) {
    for (int i = 0; i < vec.size(); ++i) {
        if (vec[i] == target) return i;
    }
    return -1;
}

1.2 二分查找

//二分查找(需要数组有序)
int binarySearch(const vector<int> &vec, int target) {
    if (vec.empty()) return -1;
    int left = 0;
    int right = static_cast<int>(vec.size()) - 1;
    while (left <= right) {
        const int mid = left + (right - left) / 2;
        if (vec[mid] == target) {
            return mid;
        }
        if (vec[mid] < target) { //指针右移
            left = mid + 1;
        } else {
            right = mid - 1;   //指针左移
        }
    }
    return -1;
}

测试

int main() {


   vector<int> arr = {12, 23, 45, 31, 56, 82, 62};

    int num = linearSearch(arr,62);//索引为6
    printf("%d\n",num);
    //先给数组排序
    sort(arr.begin(), arr.end());
   // {12, 23, 31, 45 ,56 ,62 ,82};
    int num2 = binarySearch(arr,45);
    printf("%d",num2);
    return 0;
}

2、链表

2.1、循环链表算找入口

在循环链表中"找出口"通常指的是检测环的入口节点（即链表从哪个节点开始进入循环）。这是经典的 Floyd 判圈算法（龟兔赛跑算法） 的应用场景。

核心数学原理

1. 检测是否有环： 快指针每次走2步，慢指针每次走1步。若有环，两者必在环内相遇。
2. 寻找入口： 相遇后，将其中一个指针移回链表头，两个指针都改为每次走1步，再次相遇点即为环入口。

设链表头到入口距离为 aa ，入口到首次相遇点距离为 bb ，相遇点回到入口距离为 cc （环长 =b+c=b+c ）。
相遇时：慢指针走了 a+ba+b ，快指针走了 a+b+n(b+c)a+b+n(b+c) （多绕了 nn 圈）。
因为快指针速度是慢指针2倍：2(a+b)=a+b+n(b+c)⇒a=c+(n−1)(b+c)2(a+b)=a+b+n(b+c)⇒a=c+(n−1)(b+c) 。
这意味着：从头走到入口的距离 aa ，等于从相遇点走到入口的距离 cc 加上整数圈。所以两指针同速前进必在入口处相遇。

#include <iostream>

// 链表节点定义
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class CircularListSolver {
public:
    /**
     * 查找循环链表的入口节点
     * @param head 链表头节点
     * @return 环入口节点指针，若无环返回 nullptr
     * 
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     */
    static ListNode* findCycleEntry(ListNode* head) {
        if (!head || !head->next) return nullptr;

        // ===== 第一步：快慢指针检测环并找到相遇点 =====
        ListNode* slow = head;
        ListNode* fast = head;
        
        while (fast && fast->next) {
            slow = slow->next;          // 慢指针走1步
            fast = fast->next->next;    // 快指针走2步
            
            if (slow == fast) break;    // 相遇！
        }

        // 无环情况：快指针到达末尾
        if (!fast || !fast->next) return nullptr;

        // ===== 第二步：找入口 =====
        // 关键：一个指针回到头部，两者同速前进
        ListNode* ptr = head;
        while (ptr != slow) {
            ptr = ptr->next;
            slow = slow->next;
        }

        return ptr; // ptr == slow，即为环入口
    }

    /**
     * 辅助：计算环的长度
     */
    static int getCycleLength(ListNode* entry) {
        if (!entry) return 0;
        int len = 1;
        ListNode* curr = entry->next;
        while (curr != entry) {
            ++len;
            curr = curr->next;
        }
        return len;
    }
};

// ==================== 测试代码 ====================
int main() {
    // 构建链表: 1 -> 2 -> 3 -> 4 -> 5 -> 3 (环入口为节点3)
    ListNode* n1 = new ListNode(1);
    ListNode* n2 = new ListNode(2);
    ListNode* n3 = new ListNode(3);
    ListNode* n4 = new ListNode(4);
    ListNode* n5 = new ListNode(5);
    
    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    n4->next = n5;
    n5->next = n3; // ← 形成环，入口是 n3

    // 测试找入口
    ListNode* entry = CircularListSolver::findCycleEntry(n1);
    if (entry) {
        std::cout << "✅ 找到环入口，节点值: " << entry->val << std::endl;
        std::cout << "📏 环长度: " << CircularListSolver::getCycleLength(entry) << std::endl;
    } else {
        std::cout << "❌ 无环" << std::endl;
    }

    // 清理内存（注意：有环时不能简单 delete 整条链）
    // 实际工程中应先断开环再逐个释放
    n5->next = nullptr; // 断环
    for (ListNode* p = n1; p; ) {
        ListNode* tmp = p;
        p = p->next;
        delete tmp;
    }

    return 0;
}

要点	说明
空指针保护	fast->next 访问前必须检查 fast 非空，否则段错误
纯循环链表	若整个链表就是环（头节点即入口），算法同样正确，此时 $ a=0 $
不要修改原链表	Floyd 算法只读，不改变任何 next 指针，线程安全
内存释放	带环链表不能直接遍历 delete，必须先断环或用哈希表记录已释放节点
替代方案	若允许 $ O(n) $ 空间，可用 unordered_set<ListNode*> 记录访问过的节点，首次重复即为入口，代码更直观但牺牲空间

一、常见数据结构

1. 链表（Linked List）

• 特点：由节点组成，每个节点包含数据和指向下一个节点的指针。

• 类型：

  • 单向链表

  • 双向链表

  • 循环链表

• 操作复杂度：

  • 查找：O(n)

  • 插入/删除（已知位置）：O(1)

• 常见题型：

  • 反转链表

  • 检测环（快慢指针）

  • 合并两个有序链表

2. 栈（Stack）

• 特点：后进先出（LIFO）

• 实现方式：数组或链表

• 基本操作：push、pop、peek/top

• 应用场景：

  • 函数调用栈

  • 表达式求值（中缀转后缀）

  • 括号匹配

  • DFS（深度优先搜索）

3. 队列（Queue）

• 特点：先进先出（FIFO）

• 变种：

  • 双端队列（Deque）

  • 优先队列（通常用堆实现）

• 应用场景：

  • BFS（广度优先搜索）

  • 任务调度

  • 滑动窗口最大值（配合双端队列）

4. 哈希表（Hash Table / HashMap）

• 特点：键值对存储，通过哈希函数快速访问

• 平均时间复杂度：

  • 插入/查找/删除：O(1)

• 冲突处理：

  • 链地址法（拉链法）

  • 开放寻址法

• 注意事项：

  • 哈希函数设计

  • 负载因子与扩容

• 应用：

  • 字典、缓存（如 LRU Cache）

  • 快速去重、计数

5. 二叉树（Binary Tree）

• 定义：每个节点最多有两个子节点（左、右）

• 常见类型

  • 二叉搜索树（BST）：左 < 根 < 右

• 完全二叉树、满二叉树、平衡二叉树（如 AVL、红黑树）

• 遍历方式

  • 前序（根左右）

  • 中序（左根右）→ BST 中序为升序

  • 后序（左右根）

  • 层序（BFS，用队列实现）

• 经典问题

  • 最大深度、最小深度

  • 判断是否为平衡二叉树

  • 二叉树的序列化与反序列化

5.1 红黑树（本质上是平衡二叉树的变种）

C++ 中的红黑树（Red-Black Tree）是 C++ 标准模板库（STL）中 std::map、std::set、std::multimap 和 std::multiset 等关联容器通常使用的底层数据结构。

由于它是 STL 的实现细节，开发者通常不需要自己手动实现红黑树，而是直接使用这些容器。但了解其原理对于优化代码性能和理解 STL 很有帮助。

以下是关于 C++ 红黑树的核心知识点：

1. 什么是红黑树？

红黑树是一种自平衡二叉搜索树。它在每个节点上增加了一个存储位来表示节点的颜色（红色或黑色），通过对任何一条从根到叶子的路径上各个节点的颜色进行约束，确保没有一条路径会比其他路径长出两倍，从而实现近似平衡。

2. 红黑树的五大性质

为了保证平衡，红黑树必须满足以下条件：

1. 节点颜色：每个节点要么是红色，要么是黑色。

2. 根节点：根节点是黑色的。

3. 叶子节点：所有的叶子节点（NIL 节点，即空节点）都是黑色的。

4. 红色约束：如果一个节点是红色的，则它的两个子节点都必须是黑色的（不能有两个连续的红色节点）。

5. 黑高一致：对任意节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点（称为“黑高”）。

记忆口诀

左根右，根叶黑，不红红，黑路同

AVL树和红黑树的区别

为什么要红黑树，方便数组遍历，查找速度增加

红黑树的左右子树，相差不超过两倍

红黑树的删除

将6设置为根节点，10右旋到6节点下面

3. C++ STL 中的使用

在 C++ 中，你几乎总是通过以下方式使用红黑树：

• std::map<Key, T>: 键值对映射，按键排序。

• std::set<T>: 集合，元素唯一且有序。

• std::multimap<Key, T>: 允许重复键的映射。

• std::multiset<T>: 允许重复元素的集合。

示例代码：

#include <iostream>
#include <map> // 底层通常由红黑树实现
#include <set>
​
int main() {
    // std::map 使用红黑树
    std::map<std::string, int> scores;
    
    scores["Alice"] = 90;
    scores["Bob"] = 85;
    scores["Charlie"] = 95;
​
    // 自动按键排序输出
    for (const auto& pair : scores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
​
    // std::set 使用红黑树
    std::set<int> numbers = {5, 2, 9, 1, 5, 6}; 
    // 注意：set 会自动去重，所以 5 只会出现一次
    
    for (int n : numbers) {
        std::cout << n << " ";
    }
    // 输出顺序: 1 2 5 6 9
    
    return 0;
}

4. 时间复杂度

由于红黑树是平衡的，其操作的时间复杂度非常稳定：

• 查找 (Search): $O(\log N)$

• 插入 (Insert): $O(\log N)$

• 删除 (Delete): $O(\log N)$

• 遍历 (Traversal): $O(N)$

相比之下，普通的二叉搜索树在最坏情况下（退化成链表）可能达到 $O(N)$。

5. 为什么选择红黑树而不是 AVL 树？

虽然 AVL 树也是平衡树，且查询速度更快（更平衡），但在 C++ STL 中选择红黑树主要基于以下原因：

• 插入/删除效率更高：红黑树在插入和删除时需要的旋转次数比 AVL 树少。AVL 树为了维持严格平衡，每次插入或删除后可能需要多次旋转来恢复平衡；而红黑树只要求“大致平衡”，因此维护成本更低。

• 场景适配：STL 中的 map/set 经常涉及大量的插入和删除操作，红黑树的折中方案在整体性能上表现更好。

6. 如果你想自己实现红黑树

如果你是为了学习算法而需要自己实现一个红黑树，核心步骤包括：

1. 定义节点结构：包含 key, value, color (RED/BLACK), left, right, parent 指针。

2. 左旋与右旋 (Rotate Left/Right)：这是调整树结构的基本操作。

3. 插入后的修复 (Rebalance)：插入新节点（默认为红色）后，检查是否违反红黑树性质，通过变色和旋转修复。

4. 删除后的修复 (Rebalance)：删除节点后同样需要检查和修复。

这是一个经典的算法面试题，实现难度较高，因为需要处理多种情况（如叔叔节点是红色还是黑色，节点是左孩子还是右孩子等）。

总结

• 日常开发：直接使用 std::map 或 std::set，无需关心底层红黑树的具体实现。

• 性能需求：如果你需要有序的键值对或集合，且数据量较大，红黑树是实现的最佳选择之一。

• 学习目的：理解红黑树有助于深入掌握 C++ STL 的机制以及平衡树算法。

---

二、经典算法

1. 排序算法

算法	时间复杂度（平均）	稳定性	是否原地
冒泡排序	O(n²)	是	是
选择排序	O(n²)	否	是
插入排序	O(n²)	是	是
快速排序	O(n log n)	否	是
归并排序	O(n log n)	是	否
堆排序	O(n log n)	否	是

面试重点：快排（分治+递归）、归并（分治+稳定）、堆排序（基于堆）

2. 查找算法

• 顺序查找：O(n)，适用于无序数组

• 二分查找

  ：O(log n)，要求

  有序数组

  • 注意边界条件（left <= right）

  • 变种：查找第一个/最后一个目标值

3. 图/树遍历

• DFS（深度优先搜索）

  • 用栈（递归本质是函数栈）

  • 适用于：路径问题、回溯、拓扑排序

• BFS（广度优先搜索）

  • 用队列

  • 适用于：最短路径（无权图）、层序遍历

在树中：DFS = 前/中/后序；BFS = 层序遍历

---

三、建议练习题目（LeetCode 高频）

• 链表：206（反转）、141（环检测）、21（合并）

• 栈：20（括号匹配）、155（最小栈）

• 队列：225（用栈实现队列）、622（设计循环队列）

• 哈希表：1（两数之和）、49（字母异位词分组）

• 二叉树：104（最大深度）、94（中序遍历）、102（层序遍历）

• 排序：912（排序数组，练快排/归并）

• 二分查找：704、35

• DFS/BFS：200（岛屿数量）、104（树深度）

---