2、数据结构与算法（C++）

一、数据结构是计算机科学的基石也是算法设计和系统开发的底层支撑。1. 线性结构 (Linear Structures)数据元素之间存在一对一的线性关系。数组:特点内存连续支持 $O(1)$ 随机访问通过下标但插入/删除需移动元素平均 $O(n)$。应用缓存友好适合作为其他数据结构的底层存储如哈希表、堆。变体动态数组如 Cvector, 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, Cstd::map, Linux 内核调度器。堆:定义完全二叉树 堆序性质大顶堆/小顶堆。通常用数组存储。操作建堆 $O(n)$插入/删除堆顶 $O(\log n)$获取极值 $O(1)$。应用Top-K 问题、优先队列、堆排序、Dijkstra 算法。Trie:特点按字符逐层存储利用公共前缀节省空间。应用自动补全、拼写检查、IP 路由最长前缀匹配、词频统计。3. 图结构 (Graph Structures)数据元素之间存在多对多的网状关系。存储方式邻接矩阵空间 $O(V^2)$适合稠密图判断边存在性 $O(1)$。邻接表空间 $O(VE)$适合稀疏图遍历邻居高效。遍历算法BFS最短路径无权图、连通分量、拓扑排序辅助。DFS环检测、拓扑排序、强连通分量、回溯法基础。经典算法最短路径Dijkstra非负权、Bellman-Ford可处理负权、Floyd-Warshall全源。最小生成树Kruskal基于并查集、Prim。拓扑排序Kahn 算法入度法、DFS 逆后序。4. 散列结构 (Hashing)核心思想通过哈希函数将键映射到桶索引实现理想 $O(1)$ 的增删改查。冲突解决链地址法每个桶挂链表或红黑树当链过长时。JavaHashMap采用此法。开放寻址法线性探测、二次探测、双重哈希。缓存友好但删除复杂。关键指标负载因子 元素数 / 桶数。过高需扩容重哈希。设计要点哈希函数的均匀性、抗碰撞性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 vectorint vec, int target) { for (int i 0; i vec.size(); i) { if (vec[i] target) return i; } return -1; }1.2 二分查找//二分查找(需要数组有序) int binarySearch(const vectorint vec, int target) { if (vec.empty()) return -1; int left 0; int right static_castint(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() { vectorint 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 判圈算法龟兔赛跑算法的应用场景。核心数学原理检测是否有环快指针每次走2步慢指针每次走1步。若有环两者必在环内相遇。寻找入口相遇后将其中一个指针移回链表头两个指针都改为每次走1步再次相遇点即为环入口。设链表头到入口距离为 aa 入口到首次相遇点距离为 bb 相遇点回到入口距离为 cc 环长 bcbc 。相遇时慢指针走了 abab 快指针走了 abn(bc)abn(bc) 多绕了 nn 圈。因为快指针速度是慢指针2倍2(ab)abn(bc)⇒ac(n−1)(bc)2(ab)abn(bc)⇒ac(n−1)(bc) 。这意味着从头走到入口的距离 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非空否则段错误纯循环链表若整个链表就是环头节点即入口算法同样正确此时 $ a0 $不要修改原链表Floyd 算法只读不改变任何next指针线程安全内存释放带环链表不能直接遍历 delete必须先断环或用哈希表记录已释放节点替代方案若允许 $ O(n) $ 空间可用unordered_setListNode*记录访问过的节点首次重复即为入口代码更直观但牺牲空间一、常见数据结构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. 红黑树的五大性质为了保证平衡红黑树必须满足以下条件节点颜色每个节点要么是红色要么是黑色。根节点根节点是黑色的。叶子节点所有的叶子节点NIL 节点即空节点都是黑色的。红色约束如果一个节点是红色的则它的两个子节点都必须是黑色的不能有两个连续的红色节点。黑高一致对任意节点从该节点到其所有后代叶子节点的简单路径上均包含相同数目的黑色节点称为“黑高”。记忆口诀左根右根叶黑不红红黑路同AVL树和红黑树的区别为什么要红黑树方便数组遍历查找速度增加红黑树的左右子树相差不超过两倍红黑树的删除将6设置为根节点10右旋到6节点下面3. C STL 中的使用在 C 中你几乎总是通过以下方式使用红黑树std::mapKey, T: 键值对映射按键排序。std::setT: 集合元素唯一且有序。std::multimapKey, T: 允许重复键的映射。std::multisetT: 允许重复元素的集合。示例代码#include iostream #include map // 底层通常由红黑树实现 #include set ​ int main() { // std::map 使用红黑树 std::mapstd::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::setint 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. 如果你想自己实现红黑树如果你是为了学习算法而需要自己实现一个红黑树核心步骤包括定义节点结构包含 key, value, color (RED/BLACK), left, right, parent 指针。左旋与右旋 (Rotate Left/Right)这是调整树结构的基本操作。插入后的修复 (Rebalance)插入新节点默认为红色后检查是否违反红黑树性质通过变色和旋转修复。删除后的修复 (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、35DFS/BFS200岛屿数量、104树深度