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

1. 线性结构 (Linear Structures)

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

• 数组:
  • 特点：内存连续，支持 $O(1)$ 随机访问（通过下标），但插入/删除需移动元素，平均 $O(n)$。
  • 应用：缓存友好，适合作为其他数据结构的底层存储（如哈希表、堆）。
  • 变体：动态数组（如 C++vector, JavaArrayList）通过倍增扩容策略实现均摊 $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$），查找快，插入/删除旋转多。
  • 红黑树：弱平衡，插入/删除旋转少，综合性能更优。工业界标准（JavaTreeMap, 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)$ 的增删改查。
• 冲突解决：
  • 链地址法：每个桶挂链表（或红黑树，当链过长时）。JavaHashMap采用此法。
  • 开放寻址法：线性探测、二次探测、双重哈希。缓存友好，但删除复杂。
• 关键指标：负载因子 = 元素数 / 桶数。过高需扩容重哈希。
• 设计要点：哈希函数的均匀性、抗碰撞性；equals 与 hashCode 的一致性契约。

5. 复杂度分析速查表

⚠️重要提醒时间复杂度中的 $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; }

一、常见数据结构

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. 排序算法

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

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（树深度）