数据结构是一门非常容易被低估的课。很多同学觉得它不就是一堆链表、树、图吗背一背就完事结果一到手写代码就卡住要么指针把你绕晕要么递归根本看不出返回值在干嘛。也有朋友工作两三年后回来补课才发现以前写的代码里到处是没必要的遍历、低效的拷贝、随意塞进 vector 里的这种操作本质上都是因为没建立数据结构意识。这篇内容就是为这两类人写的——把数据结构从抽象概念一步步拉到 C 代码层面讲清楚每个结构存在的理由、它在什么场景下无可替代以及实现时那些老师不细讲、但你自己写一定会踩的坑。1. 整体学习路线与设计思路1.1 概念先行还是代码先行我的观点是先理解这个结构要解决什么“访问约束”再动手写代码。什么叫访问约束你看数组它允许你按下标随机访问任意一个元素O(1)。但如果你要在数组头部频繁插入后面的元素全部要往后挪O(n) 就没了。链表则反过来插入只需要改指针但你要找一个中间元素必须从头遍历。数据结构本质就是在一组操作之间做取舍没有任何一种结构在所有操作上都是最优的。所以我在自己学习时会把每个数据结构拆成四个问题它的基本单位是什么节点、元素、顶点它允许哪些操作插入、删除、查找、遍历每个操作的复杂度是多少什么场景下这个结构最适合这四个问题想清楚代码只是一种表达。你会发现顺序表的实现其实就是封装一个动态数组链表的实现就是摆弄指针栈和队列只要限定插入删除的位置二叉树不过是一个带左右孩子指针的结构体加上递归。概念是骨架代码是血肉两者缺一不可。1.2 复杂度分析是所有选型的依据很多初学者觉得复杂度分析是考试用的东西实际写代码用不上。恰恰相反复杂度分析是数据结构的选型字典。举个例子一个任务需要频繁判断“某个值是否存在”你可以把所有数据放进 vector每次用 find 线性查找平均 O(n)。放进有序数组里用二分查找O(log n)但插入需要保持有序O(n)。放进 unordered_set哈希表查找和插入平均都是 O(1)。这三条路线数据量小的时候感受不出差别可当数据量来到几百万甚至上千万级别会发生质变。我帮身边一个朋友排查过一段程序他每次处理请求时要在内存里查一遍几千条配置单次很快但他一天要处理几百万次请求最后耗时就累积到了可怕的程度。换成哈希表之后整体性能直接提升了一个数量级。这就是数据结构选择的意义。学 C 实现时还有一个天然优势标准库里已经有一套成熟的容器实现vector、list、stack、queue、deque、map、unordered_map。你可以先学会用它们再去看源码或者自己实现一遍。自己实现的版本可能比标准库慢很多也脆弱很多但这个“销毁重造”的过程能让你真正理解容器背后的存储模式和数据边界这在调试复杂 bug 时是救命技能。2. 线性结构从顺序表到链表2.1 顺序表动态数组的实现要点顺序表最简单却最容易写出隐蔽 bug。我先给一个核心思路再讲几个容易翻车的细节。#include iostream #include stdexcept template typename T class MyVector { public: MyVector() : m_data(nullptr), m_size(0), m_capacity(0) {} ~MyVector() { delete[] m_data; } void push_back(const T value) { if (m_size m_capacity) { resize(); } m_data[m_size] value; } void insert(int index, const T value) { if (index 0 || index m_size) { throw std::out_of_range(index out of range); } if (m_size m_capacity) { resize(); } for (int i m_size; i index; --i) { m_data[i] m_data[i - 1]; } m_data[index] value; m_size; } void erase(int index) { if (index 0 || index m_size) { throw std::out_of_range(index out of range); } for (int i index; i m_size - 1; i) { m_data[i] m_data[i 1]; } --m_size; } T operator[](int index) { if (index 0 || index m_size) { throw std::out_of_range(index out of range); } return m_data[index]; } int size() const { return m_size; } int capacity() const { return m_capacity; } private: T* m_data; int m_size; int m_capacity; void resize() { int newCapacity m_capacity 0 ? 4 : m_capacity * 2; T* newData new T[newCapacity]; for (int i 0; i m_size; i) { newData[i] m_data[i]; } delete[] m_data; m_data newData; m_capacity newCapacity; } };这里有三个点值得展开扩容的正确姿势不要每次 push_back 都申请一块刚刚好的内存这样插入 n 个元素的总复杂度会变成 O(n²)。一次扩容翻倍均摊下来每次插入是 O(1)。有些教材用“加固定常量”的方式扩容均摊也是 O(1)但倍数扩容实现更简单内存碎片也更少。拷贝构造和赋值运算符上面的代码没写这两个实际使用中如果发生拷贝会触发默认逐字节拷贝两个对象指向同一块堆内存析构时双重释放。这是最经典的 C 内存问题之一。实践方案是禁用拷贝或者实现深拷贝MyVector(const MyVector other) { ... }以及operator现代 C 还可以用移动语义优化。erase 为什么要从前往后挪从前往后挪会让后续元素覆盖前一个位置index 位置被 index1 覆盖index1 被 index2 覆盖最后删掉末尾的残留元素size 减一即可。反过来从后往前挪会覆盖掉还没处理的数据逻辑全错。2.2 链表的指针操作与头节点技巧链表是很多人的噩梦因为每行代码都在操作地址一个不小心就段错误。我实现链表时习惯用一个虚拟头节点dummy head它不存储数据只是为了让操作统一。有了它插入第一个节点和插入到中间某个位置代码逻辑完全一致不需要特判“空链表”情况。template typename T struct Node { T data; Node* next; Node(const T value, Node* nextNode nullptr) : data(value), next(nextNode) {} }; template typename T class LinkedList { public: LinkedList() : m_head(new NodeT(T())), m_size(0) {} ~LinkedList() { NodeT* current m_head; while (current) { NodeT* next current-next; delete current; current next; } } void insert(int index, const T value) { if (index 0 || index m_size) return; NodeT* prev m_head; for (int i 0; i index; i) { prev prev-next; } prev-next new NodeT(value, prev-next); m_size; } void erase(int index) { if (index 0 || index m_size) return; NodeT* prev m_head; for (int i 0; i index; i) { prev prev-next; } NodeT* target prev-next; prev-next target-next; delete target; --m_size; } private: NodeT* m_head; int m_size; };insert 里那句new NodeT(value, prev-next)是灵魂写法先让新节点的 next 指向 prev 的旧后继再让 prev-next 指向新节点。很多新手会写反先让 prev-next 指向新节点然后拿不到原来的下一个节点链表直接断裂。记住口诀先接新后再断旧链顺序不能反。erase 同样要先把 target 记下来让 prev-next 绕过 target然后再 delete。直接用delete prev-next的思路很危险因为等你 delete 完就找不到 target 的 next 了整个链表就断了。2.3 顺序表和链表怎么选这是面试和实际开发都绕不开的问题。我遇到很多场景同事把 map 或者 list 作为默认容器其实并不合理。直观结论是频繁按下标随机访问 → vector只在尾部插入删除 → vector大量在头部或中间插入删除而且数据量较大 → list数据量很小 → 都可以vector 通常更优因为缓存局部性好。缓存局部性是很多人忽略的点。vector 的元素在内存里是连续排布的CPU 加载相邻数据时命中率高list 的节点分散在堆里每次遍历可能要跳到很远的内存位置缓存命中率低。这个性能差异在几十万以上级别数据时会非常明显。我自己写代码时默认容器优先选 vector只有当出现“频繁在中间插入删除”并且元素数量较大才换成 list 或者自己设计跳表之类的结构。用合适的容器比任何局部优化都更有效。3. 栈与队列吃透受限访问模型3.1 用数组实现栈的几个细节栈就是“后进先出”的限定版线性表。实现本身不难但有几个细节能看出你对结构理解得透不透。我用数组实现栈时会维护一个 topIndex指向当前栈顶元素的位置。入栈时先 topIndex 再赋值出栈时 topIndex-- 即可不需要物理删除那个元素因为它不再属于栈的范围了下次入栈会直接覆盖。template typename T class Stack { public: explicit Stack(int capacity) : m_capacity(capacity), m_top(-1), m_data(new T[capacity]) {} ~Stack() { delete[] m_data; } void push(const T value) { if (m_top 1 m_capacity) { resize(); } m_data[m_top] value; } void pop() { if (m_top 0) throw std::out_of_range(stack is empty); --m_top; } T top() { if (m_top 0) throw std::out_of_range(stack is empty); return m_data[m_top]; } bool empty() const { return m_top 0; } int size() const { return m_top 1; } private: int m_capacity; int m_top; T* m_data; void resize() { int newCapacity m_capacity * 2; T* newData new T[newCapacity]; for (int i 0; i m_top; i) { newData[i] m_data[i]; } delete[] m_data; m_data newData; m_capacity newCapacity; } };m_top 初始值设为 -1表示空栈。这里有几个关键点判空用m_top 0而不是m_top 0。0 表示还有一个元素很多人初始化时容易犯这个错误。栈的 pop 不需要返回值要取栈顶先调用 top() 再 pop()。这是 C 标准库的惯例因为“返回并弹出”在异常安全上很难做好万一返回值拷贝过程中抛异常栈的状态就混乱了。应用场景函数调用栈、表达式求值、括号匹配、撤销操作。要想检验自己是否理解栈可以试试用栈实现一个中缀表达式转后缀表达式做完你会对运算符优先级有全新的认识。3.2 队列的循环缓冲区队列是“先进先出”。用数组实现队列最怕的问题是队头出队后前面的位置空着而队尾指针已经走到数组末尾新元素进不来。解决办法就是循环队列——让 rear 在到达数组末尾时绕回开头形成一个环形逻辑结构。template typename T class CircularQueue { public: explicit CircularQueue(int capacity) : m_data(new T[capacity]), m_capacity(capacity), m_front(0), m_rear(0), m_size(0) {} ~CircularQueue() { delete[] m_data; } void push(const T value) { if (m_size m_capacity) { throw std::out_of_range(queue is full); } m_data[m_rear] value; m_rear (m_rear 1) % m_capacity; m_size; } void pop() { if (m_size 0) { throw std::out_of_range(queue is empty); } m_front (m_front 1) % m_capacity; --m_size; } T front() { if (m_size 0) throw std::out_of_range(queue is empty); return m_data[m_front]; } private: T* m_data; int m_capacity; int m_front; int m_rear; int m_size; };循环队列的关键操作是(rear 1) % m_capacity。有的实现会浪费一个位置来区分空和满我习惯用 m_size 来区分逻辑更直观也不容易误判。出队时不物理清除元素只移动 front这是循环队列一个很朴素但重要的理念。除了基础队列工程里更常用的是双端队列。C 标准库的 std::deque 就是分段连续存储既支持两端插入删除又不像链表那样每个节点单独分配我实现滑动窗口算法、任务调度队列时经常用它。3.3 栈与队列的联动案例有个很经典的例子能同时检验两种结构用队列实现栈或者用栈实现队列。我第一次做“用两个栈实现队列”时思路卡了很久。后来想明白了一个栈作为输入缓冲push 时直接压入pop 时先把所有元素弹出并压入另一个栈顺序就反转了再从第二个栈弹出就是先进先出。class QueueByTwoStacks { public: void push(int x) { input.push(x); } int pop() { if (output.empty()) { while (!input.empty()) { output.push(input.top()); input.pop(); } } int result output.top(); output.pop(); return result; } private: std::stackint input; std::stackint output; };这个技巧在实际中也有价值比如某些场景下你手头只有栈结构的 API却需要在语义上做成队列。反过来用队列实现栈也一样不过需要每次 pop 时把队尾之前的元素全都倒腾一遍复杂度会高一些。做这种题的意义不是背答案而是理解数据结构之间的转换关系这会让你在真正设计系统时多一层抽象思维。4. 二叉树与递归思维的建立4.1 二叉树节点的设计与三种遍历递归写法二叉树的节点比链表多一个指针需要同时记录左孩子和右孩子。递归遍历是理解二叉树的核心因为树的定义本身就是递归的一棵树的左右子树仍然是树。template typename T struct TreeNode { T data; TreeNode* left; TreeNode* right; TreeNode(const T value) : data(value), left(nullptr), right(nullptr) {} }; template typename T void preorder(TreeNodeT* node) { if (!node) return; std::cout node-data ; preorder(node-left); preorder(node-right); } template typename T void inorder(TreeNodeT* node) { if (!node) return; inorder(node-left); std::cout node-data ; inorder(node-right); } template typename T void postorder(TreeNodeT* node) { if (!node) return; postorder(node-left); postorder(node-right); std::cout node-data ; }递归遍历的字数很少但很多初学者看递归代码还是晕。我的建议是不要盯着代码一行行模拟执行而是把函数当作一个“已经正确完成某个任务的工具”。比如中序遍历你只需要相信一件事inorder(node-left) 会正确输出左子树的中序序列然后输出当前节点再相信 inorder(node-right) 会正确输出右子树。信心的建立来自于多做几道递归题包括求深度、判断对称、路径求和。还有一种容易忽略的遍历叫层序遍历也叫广度优先遍历。它天然需要队列配合先把根节点入队出队一个节点时就把它左右孩子入队直到队列为空。为什么递归写不了层序遍历因为递归的天然调用顺序是深度优先的如果想强行递归实现层序遍历需要额外记录节点所处的层数并按层数把节点塞到对应层的容器里本质上还是借了个“层”的概念模拟队列。4.2 二叉搜索树的插入与删除二叉搜索树简称 BST是二叉树最典型的应用之一。它满足左子树所有节点值小于根节点右子树所有节点值大于根节点。插入逻辑很纯粹递归往下走走到空位置就放进去TreeNodeint* insertBST(TreeNodeint* root, int value) { if (!root) { return new TreeNodeint(value); } if (value root-data) { root-left insertBST(root-left, value); } else if (value root-data) { root-right insertBST(root-right, value); } return root; }注意这里root-left insertBST(...)返回值要被接收否则新节点挂不上去。很多新手递归写出来但忘记“用返回值接住上一层”导致树根本没变化。删除比插入复杂因为要分三种情况删除叶子节点直接释放它返回 nullptr。删除只有一个孩子的节点让孩子顶替它的位置。删除有两个孩子的节点这个情况最麻烦。主流做法是找到左子树中最大的节点或者右子树中最小的节点把它提上来替换被删节点的值然后递归删除那个用来替换的节点。我用右子树最小节点的方案写一个TreeNodeint* findMin(TreeNodeint* node) { while (node node-left) { node node-left; } return node; } TreeNodeint* deleteBST(TreeNodeint* root, int value) { if (!root) return nullptr; if (value root-data) { root-left deleteBST(root-left, value); } else if (value root-data) { root-right deleteBST(root-right, value); } else { if (!root-left !root-right) { delete root; return nullptr; } else if (!root-left) { TreeNodeint* rightChild root-right; delete root; return rightChild; } else if (!root-right) { TreeNodeint* leftChild root-left; delete root; return leftChild; } else { TreeNodeint* successor findMin(root-right); root-data successor-data; root-right deleteBST(root-right, successor-data); } } return root; }两个孩子的删除方案理解起来比较绕我们不物理删除当前根节点而是把右子树的最小值复制到当前节点再递归去右子树删掉那个最小值。这样保证了当前节点的左子树仍然都小于根节点右子树中剩下的都大于根节点BST 性质不破坏。4.3 平衡问题与自平衡树普通 BST 有一个致命问题如果插入序列本身有序比如 1, 2, 3, 4, 5, 树会退化成一个直线链表查找复杂度从 O(log n) 退化到 O(n)。为了避免这种情况需要在插入删除后调整树形结构让左右子树高度差保持在一定范围内这就是平衡树。最常见的自平衡树有 AVL 树和红黑树。AVL 树要求每个节点的左右子树高度差不超过 1调整方式是单旋和双旋。红黑树规则更复杂但它的优势是插入删除时调整次数更少所以 C 标准库 std::map、std::set 底层采用红黑树。这里不需要手写红黑树但你需要理解一个现象当 map 的底层是红黑树时它的键值对始终是有序的因此 std::map 支持按键范围遍历、迭代器查找相邻键、lower_bound/upper_bound这些操作而 std::unordered_map 做不到。选择 map 还是 unordered_map本质是在“有序性”和“平均查找速度”之间做取舍。5. 图存储结构与遍历写法5.1 邻接矩阵和邻接表的取舍很多人学完二叉树就跳过图觉得图离业务很远。但图模型实际上到处都有社交关系、地图导航、任务依赖、网络爬虫的链接关系、六度分隔理论。图的存储方式主要有两种邻接矩阵和邻接表。邻接矩阵是一个二维数组adj[i][j]表示 i 到 j 是否有边。判断两个顶点是否相邻是 O(1)但需要 O(V²) 的空间稀疏图非常浪费。邻接表则是每个顶点对应一个链表或向量存储它所有邻接点空间是 O(VE)遍历某个顶点的全部邻接点非常自然。#include vector #include list #include iostream class Graph { public: explicit Graph(int vertices) : adjList(vertices) {} void addEdge(int from, int to) { adjList[from].push_back(to); adjList[to].push_back(from); // 无向图需要加一条反向边 } void dfs(int start) { std::vectorbool visited(adjList.size(), false); dfsHelper(start, visited); std::cout std::endl; } private: std::vectorstd::listint adjList; void dfsHelper(int vertex, std::vectorbool visited) { visited[vertex] true; std::cout vertex ; for (int neighbor : adjList[vertex]) { if (!visited[neighbor]) { dfsHelper(neighbor, visited); } } } };工程上稀疏图占绝大多数因此邻接表更常用。但邻接矩阵在稠密图里也有优势比如判断连通性、求所有点对最短路径的 Floyd 算法矩阵形态更容易实现和向量化。5.2 BFS 与拓扑排序的实战价值图的深度优先遍历和二叉树的递归很像函数调用天然就是深度优先。广度优先遍历则需要队列#include queue void bfs(int start, const std::vectorstd::listint adjList) { std::vectorbool visited(adjList.size(), false); std::queueint q; q.push(start); visited[start] true; while (!q.empty()) { int vertex q.front(); q.pop(); std::cout vertex ; for (int neighbor : adjList[vertex]) { if (!visited[neighbor]) { visited[neighbor] true; q.push(neighbor); } } } }注意一个细节入队时就标记 visited而不是出队时再标记。如果出队时才标记同一个节点可能被多个邻居重复入队导致队列膨胀甚至引起错误。这个细节在很多 BFS 问题里都是隐藏的坑。BFS 还有一个额外用途求无权图的最短路径。因为在 BFS 中第一次访问到某个节点时就一定是从起点到它的最短路径。这一性质在迷宫寻路、社交关系里“你和我隔了几个人”这类问题中非常好用。图的另一种重要技术是拓扑排序适合有向无环图。经典场景是任务依赖比如编译工程时A 依赖 B 和 CC 依赖 D那么排序结果必须保证被依赖的库先编译。实现思路用队列Kahn 算法统计每个节点的入度入度为 0 的节点入队每弹出一个节点就把它的邻接节点入度减 1减到 0 就入队。最终如果出队次数不等于总节点数说明图中有环。拓扑排序的代码本身不难但它背后的思维非常实用。我在实际项目中遇到的任务编排、依赖解析这类问题几乎都能用同一套逻辑抽象解决。6. 排序与查找工程里的高频操作6.1 常用排序的适用边界排序可以说是数据结构的综合练习因为你会用到数组、链表、栈、树、堆等一堆结构。C 里 std::sort 底层是快速排序和插入排序的组合大多数情况下直接用就行。但理解排序算法本身能帮你在标准库不够用的时候做出正确选择。常用排序可以做一个简单对比排序算法平均时间复杂度最坏情况空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定插入排序O(n²)O(n²)O(1)稳定归并排序O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(1)不稳定实际选型时注意几点数据规模小比如十几到几十个元素插入排序反而最快因为常数因子小、缓存友好。需要稳定排序时std::stable_sort 会使用归并排序的思想代价是需要额外空间。系统自带排序不可用时比如嵌入式环境、内存受限堆排序是稳妥的原地排序方案。还有一种理解排序的方式把插入排序看作“在线算法”随时可以处理新来的元素把归并排序看作“分治算法”的典型代表适合通过递归思路掌握把快速排序看作“分区思想”的经典配合随机化基准值可以避免最坏情况。6.2 二分查找与哈希表的配合二分查找的前提是数据有序。它的代码很短但边界条件极其容易写错。我给出一个闭区间的写法这个写法在调试时最直观因为[left, right]区间内始终都是“还没确定答案”的部分。int binarySearch(const std::vectorint arr, int target) { int left 0, right arr.size() - 1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { return mid; } else if (arr[mid] target) { left mid 1; } else { right mid - 1; } } return -1; }为什么用left (right - left) / 2而不是(left right) / 2因为后者可能整型溢出这在 left 和 right 都是大整数时真实发生。这个问题我在 LeetCode 那种大规模测试用例里踩过排查半天发现是溢出导致 mid 变成负数而我一直以为是语法问题。查找本身是 O(log n)但尚未真正高速如果需要更快的判定“是否存在”哈希表才是主角。前面提到的 std::unordered_set 就是哈希表实现查找 O(1)。哈希表的本质是一个数组加哈希函数冲突靠拉链法解决。C 标准库的 unordered_map 内部就是哈希桶加链表。理解这一点有什么好处当元素很多、负载因子过高时rehash 会发生迭代器全部失效性能也会骤降。所以如果你对性能有极致要求可以提前预留空间map.reserve(n)。实践中我会这样组合使用数据需要保持有序遍历时用 map只需要查重或计数时用 unordered_map。例如在统计大量文本的词频时用 unordered_map 计数最快要输出字典序排序结果时再把键取出来放进 vector 排序。各干各擅长的活。7. 常见问题与排查技巧实录7.1 段错误的排查思路写链表和树最怕的就是段错误。这种错误的特点是程序直接崩掉但不告诉你哪一行出错所以很多人一遇到就慌。我的排查思路是分三层第一层检查空指针访问。访问某个指针的成员前必须确认它不为空。常见于链表 insert 时 prev 跑到空节点或者树递归时节点已经失效。第二层检查越界访问。数组下标是否超出了实际分配的长度是否把 size 和 capacity 混淆。这一类错误在顺序表实现里特别常见比如按 capacity 循环访问但 size 实际更小。第三层检查指针悬挂。某个节点被 delete 后还有另一个指针指向它。这通常是浅拷贝导致的两个链表共享了同一个节点。排查方式是用调试器打上断点看崩溃调用栈最上层的函数再反推哪一步操作可能让指针指向非法内存。我的习惯是链表相关代码里每个涉及指针的句子都先加断言比如assert(prev ! nullptr)这样崩溃位置会更精确。断言是调式好伙伴但正式发布时记得关掉或者替换成可恢复的错误处理。7.2 内存泄漏与野指针C 手写数据结构时new 和 delete 必须成对出现。链表中泄漏最隐蔽的场景是删除链表里部分节点时只断了链忘了 delete或者 delete 完没把指针置空。这些操作单个看问题不大但在循环中重复执行就会让内存占用不停上涨。我常用的防泄漏工具是 Valgrind它适合自查代码有没有内存问题。另外C11 以后可以用智能指针简化表达。比如链表节点用std::unique_ptrNode管理 next则删除节点时子节点也会被自动释放可以大幅减少手动 delete 的负担。不过智能指针也不是万能循环引用时 unique_ptr 无法处理两个节点互相指向对方就谁也释放不了这种情况需要 weak_ptr 打破引用环。对新手来说我更建议先老老实实用裸指针写一遍体会手动管理内存的痛再上智能指针。这个过程会让你明白为什么 C 需要 RAII 这么一套机制以后看别人代码时也能判断什么地方有生命周期问题。7.3 迭代器失效这个隐蔽问题写 C 容器代码最烦的bug之一是迭代器失效。简单说vector 扩容后它内部的数据存储位置可能整体搬家所有旧迭代器都会指向旧地址再用就会出问题。std::vectorint vec {1, 2, 3}; auto it vec.begin(); vec.push_back(4); // 可能触发扩容it 失效 std::cout *it; // 未定义行为可能崩溃list 没有这个问题因为节点是独立分配的insert 或 erase 只会影响被操作的那个节点的迭代器。遇到“边遍历边删除”的场景list 或 map 往往比 vector 更合适。如果必须在 vector 中删除标准做法是利用 erase 返回的迭代器for (auto it vec.begin(); it ! vec.end();) { if (condition(*it)) { it vec.erase(it); } else { it; } }这条技巧看起来是细节但很多人实测都会踩坑。我自己一度也是“先记录下来再统一删除”的写法虽然能绕开迭代器失效但多了一次遍历和拷贝数据大了性能吃亏。这些经验值得在新手阶段就记住省得以后再交学费。7.4 一张速查表帮你记住核心场景学数据结构时信息量大我建议自己动手整理一张速查表把“结构、核心操作复杂度、典型场景”放一起。下面是我的常用版数据结构核心操作复杂度典型场景数组/vector访问 O(1)尾部插入 O(1) 均摊缓存数据、随机访问、遍历链表头插 O(1)查找 O(n)大量插入删除、LRU 缓存栈push/pop O(1)函数调用、表达式求值、括号匹配队列push/pop O(1)BFS、任务调度、滑动窗口哈希表查找/插入 O(1) 平均查重、计数、缓存二叉搜索树查找/插入/删除 O(log n)动态有序数据、范围查询堆取最大最小 O(1)插入 O(log n)优先队列、TopK 问题图遍历 O(VE)路径规划、依赖分析、社交网络这张表不需要背而是你在选容器时用来查的。写代码前先问自己这个场景的主要操作是什么如果是“频繁判断某个值是否存在”哈希表大概率是答案如果是“要实时取出最大元素”堆才是答案。选对数据结构代码往往就已经成功了大半。8. 一些很值得养成的实操习惯最后聊几个我在实现数据结构时很受用的习惯对新手和老手都有用。第一个习惯是调试时打印每一层的状态。新手最怕的不是算法难而是代码跑起来完全不知道内部发生了什么。在自己的实现里临时加几行 cout打印插入前后的链表节点、打印递归调用的深度、打印每次扩容后的 size 和 capacity都比直接看抽象代码强得多。我看到好多人卡在一个 bug 上其实只要打印出当前指针地址马上就能看出是不是指向了错误的地方。第二个习惯是先画图再写代码。链表插入删除时画个箭头图旋转平衡树时画三个节点的高低关系BFS 队列变化时画出队列入队过程。我跟很多同事和同学交流发现大家都有一个共同点凡是画过图的题目代码基本一遍过凡是直接对着编辑器硬写的必然会在边界条件上反复试错。画图不是浪费时间它是把复杂逻辑落地的减速带帮你把心智负担降下来。第三个习惯是自己实现一遍标准库的常用容器。vector、list、stack、queue 都自己写一遍再对照标准库的接口设计思考为什么它要那样设计。这个过程会让你理解 move 语义、分配器、异常安全、迭代器设计这些进阶概念。标准库代码你或许读不完但自己实现朴素版再对比收获完全不一样。第四个习惯是测试时不要只用正常数据。空容器、单元素容器、大数据容量容器、频繁插入删除的场景都要测一遍。很多隐蔽 bug 都藏在这些边界里。我排查过一个栈溢出问题就是测试时只压入了少量数据等真正跑到百万级递归时才炸。提前在边界测试里把问题暴露出来比线上出问题再应急要舒服得多。我自己当年学数据结构最深刻的体会是这门课不单是知识的堆积更多是思维的训练。学任何新结构先把“它解决什么问题、什么约束、代价是什么”想清楚再推进到代码实现之后碰到实际问题时就能自然地想到用哪种结构。现在网上的学习资料非常多但资料太多也容易让人浮于表面只看不做。动手写一遍、调试一遍、踩一遍坑——这是通向真正的理解最靠谱的路径。如果你正在学这本书或者这门课给自己定个小目标学完一个结构就把它完整实现一遍并且写一个简单的应用比如用栈做括号匹配用队列做迷宫 BFS用 BST 做动态排名表。做完这些你再看其它代码时眼里看到的就不再是一堆语法而是背后一个个清晰的数据组织方式。这就是数据结构带给你的长期价值。
数据结构是一门非常容易被低估的课。很多同学觉得它不就是一堆链表、树、图吗背一背就完事结果一到手写代码就卡住要么指针把你绕晕要么递归根本看不出返回值在干嘛。也有朋友工作两三年后回来补课才发现以前写的代码里到处是没必要的遍历、低效的拷贝、随意塞进 vector 里的这种操作本质上都是因为没建立数据结构意识。这篇内容就是为这两类人写的——把数据结构从抽象概念一步步拉到 C 代码层面讲清楚每个结构存在的理由、它在什么场景下无可替代以及实现时那些老师不细讲、但你自己写一定会踩的坑。1. 整体学习路线与设计思路1.1 概念先行还是代码先行我的观点是先理解这个结构要解决什么“访问约束”再动手写代码。什么叫访问约束你看数组它允许你按下标随机访问任意一个元素O(1)。但如果你要在数组头部频繁插入后面的元素全部要往后挪O(n) 就没了。链表则反过来插入只需要改指针但你要找一个中间元素必须从头遍历。数据结构本质就是在一组操作之间做取舍没有任何一种结构在所有操作上都是最优的。所以我在自己学习时会把每个数据结构拆成四个问题它的基本单位是什么节点、元素、顶点它允许哪些操作插入、删除、查找、遍历每个操作的复杂度是多少什么场景下这个结构最适合这四个问题想清楚代码只是一种表达。你会发现顺序表的实现其实就是封装一个动态数组链表的实现就是摆弄指针栈和队列只要限定插入删除的位置二叉树不过是一个带左右孩子指针的结构体加上递归。概念是骨架代码是血肉两者缺一不可。1.2 复杂度分析是所有选型的依据很多初学者觉得复杂度分析是考试用的东西实际写代码用不上。恰恰相反复杂度分析是数据结构的选型字典。举个例子一个任务需要频繁判断“某个值是否存在”你可以把所有数据放进 vector每次用 find 线性查找平均 O(n)。放进有序数组里用二分查找O(log n)但插入需要保持有序O(n)。放进 unordered_set哈希表查找和插入平均都是 O(1)。这三条路线数据量小的时候感受不出差别可当数据量来到几百万甚至上千万级别会发生质变。我帮身边一个朋友排查过一段程序他每次处理请求时要在内存里查一遍几千条配置单次很快但他一天要处理几百万次请求最后耗时就累积到了可怕的程度。换成哈希表之后整体性能直接提升了一个数量级。这就是数据结构选择的意义。学 C 实现时还有一个天然优势标准库里已经有一套成熟的容器实现vector、list、stack、queue、deque、map、unordered_map。你可以先学会用它们再去看源码或者自己实现一遍。自己实现的版本可能比标准库慢很多也脆弱很多但这个“销毁重造”的过程能让你真正理解容器背后的存储模式和数据边界这在调试复杂 bug 时是救命技能。2. 线性结构从顺序表到链表2.1 顺序表动态数组的实现要点顺序表最简单却最容易写出隐蔽 bug。我先给一个核心思路再讲几个容易翻车的细节。#include iostream #include stdexcept template typename T class MyVector { public: MyVector() : m_data(nullptr), m_size(0), m_capacity(0) {} ~MyVector() { delete[] m_data; } void push_back(const T value) { if (m_size m_capacity) { resize(); } m_data[m_size] value; } void insert(int index, const T value) { if (index 0 || index m_size) { throw std::out_of_range(index out of range); } if (m_size m_capacity) { resize(); } for (int i m_size; i index; --i) { m_data[i] m_data[i - 1]; } m_data[index] value; m_size; } void erase(int index) { if (index 0 || index m_size) { throw std::out_of_range(index out of range); } for (int i index; i m_size - 1; i) { m_data[i] m_data[i 1]; } --m_size; } T operator[](int index) { if (index 0 || index m_size) { throw std::out_of_range(index out of range); } return m_data[index]; } int size() const { return m_size; } int capacity() const { return m_capacity; } private: T* m_data; int m_size; int m_capacity; void resize() { int newCapacity m_capacity 0 ? 4 : m_capacity * 2; T* newData new T[newCapacity]; for (int i 0; i m_size; i) { newData[i] m_data[i]; } delete[] m_data; m_data newData; m_capacity newCapacity; } };这里有三个点值得展开扩容的正确姿势不要每次 push_back 都申请一块刚刚好的内存这样插入 n 个元素的总复杂度会变成 O(n²)。一次扩容翻倍均摊下来每次插入是 O(1)。有些教材用“加固定常量”的方式扩容均摊也是 O(1)但倍数扩容实现更简单内存碎片也更少。拷贝构造和赋值运算符上面的代码没写这两个实际使用中如果发生拷贝会触发默认逐字节拷贝两个对象指向同一块堆内存析构时双重释放。这是最经典的 C 内存问题之一。实践方案是禁用拷贝或者实现深拷贝MyVector(const MyVector other) { ... }以及operator现代 C 还可以用移动语义优化。erase 为什么要从前往后挪从前往后挪会让后续元素覆盖前一个位置index 位置被 index1 覆盖index1 被 index2 覆盖最后删掉末尾的残留元素size 减一即可。反过来从后往前挪会覆盖掉还没处理的数据逻辑全错。2.2 链表的指针操作与头节点技巧链表是很多人的噩梦因为每行代码都在操作地址一个不小心就段错误。我实现链表时习惯用一个虚拟头节点dummy head它不存储数据只是为了让操作统一。有了它插入第一个节点和插入到中间某个位置代码逻辑完全一致不需要特判“空链表”情况。template typename T struct Node { T data; Node* next; Node(const T value, Node* nextNode nullptr) : data(value), next(nextNode) {} }; template typename T class LinkedList { public: LinkedList() : m_head(new NodeT(T())), m_size(0) {} ~LinkedList() { NodeT* current m_head; while (current) { NodeT* next current-next; delete current; current next; } } void insert(int index, const T value) { if (index 0 || index m_size) return; NodeT* prev m_head; for (int i 0; i index; i) { prev prev-next; } prev-next new NodeT(value, prev-next); m_size; } void erase(int index) { if (index 0 || index m_size) return; NodeT* prev m_head; for (int i 0; i index; i) { prev prev-next; } NodeT* target prev-next; prev-next target-next; delete target; --m_size; } private: NodeT* m_head; int m_size; };insert 里那句new NodeT(value, prev-next)是灵魂写法先让新节点的 next 指向 prev 的旧后继再让 prev-next 指向新节点。很多新手会写反先让 prev-next 指向新节点然后拿不到原来的下一个节点链表直接断裂。记住口诀先接新后再断旧链顺序不能反。erase 同样要先把 target 记下来让 prev-next 绕过 target然后再 delete。直接用delete prev-next的思路很危险因为等你 delete 完就找不到 target 的 next 了整个链表就断了。2.3 顺序表和链表怎么选这是面试和实际开发都绕不开的问题。我遇到很多场景同事把 map 或者 list 作为默认容器其实并不合理。直观结论是频繁按下标随机访问 → vector只在尾部插入删除 → vector大量在头部或中间插入删除而且数据量较大 → list数据量很小 → 都可以vector 通常更优因为缓存局部性好。缓存局部性是很多人忽略的点。vector 的元素在内存里是连续排布的CPU 加载相邻数据时命中率高list 的节点分散在堆里每次遍历可能要跳到很远的内存位置缓存命中率低。这个性能差异在几十万以上级别数据时会非常明显。我自己写代码时默认容器优先选 vector只有当出现“频繁在中间插入删除”并且元素数量较大才换成 list 或者自己设计跳表之类的结构。用合适的容器比任何局部优化都更有效。3. 栈与队列吃透受限访问模型3.1 用数组实现栈的几个细节栈就是“后进先出”的限定版线性表。实现本身不难但有几个细节能看出你对结构理解得透不透。我用数组实现栈时会维护一个 topIndex指向当前栈顶元素的位置。入栈时先 topIndex 再赋值出栈时 topIndex-- 即可不需要物理删除那个元素因为它不再属于栈的范围了下次入栈会直接覆盖。template typename T class Stack { public: explicit Stack(int capacity) : m_capacity(capacity), m_top(-1), m_data(new T[capacity]) {} ~Stack() { delete[] m_data; } void push(const T value) { if (m_top 1 m_capacity) { resize(); } m_data[m_top] value; } void pop() { if (m_top 0) throw std::out_of_range(stack is empty); --m_top; } T top() { if (m_top 0) throw std::out_of_range(stack is empty); return m_data[m_top]; } bool empty() const { return m_top 0; } int size() const { return m_top 1; } private: int m_capacity; int m_top; T* m_data; void resize() { int newCapacity m_capacity * 2; T* newData new T[newCapacity]; for (int i 0; i m_top; i) { newData[i] m_data[i]; } delete[] m_data; m_data newData; m_capacity newCapacity; } };m_top 初始值设为 -1表示空栈。这里有几个关键点判空用m_top 0而不是m_top 0。0 表示还有一个元素很多人初始化时容易犯这个错误。栈的 pop 不需要返回值要取栈顶先调用 top() 再 pop()。这是 C 标准库的惯例因为“返回并弹出”在异常安全上很难做好万一返回值拷贝过程中抛异常栈的状态就混乱了。应用场景函数调用栈、表达式求值、括号匹配、撤销操作。要想检验自己是否理解栈可以试试用栈实现一个中缀表达式转后缀表达式做完你会对运算符优先级有全新的认识。3.2 队列的循环缓冲区队列是“先进先出”。用数组实现队列最怕的问题是队头出队后前面的位置空着而队尾指针已经走到数组末尾新元素进不来。解决办法就是循环队列——让 rear 在到达数组末尾时绕回开头形成一个环形逻辑结构。template typename T class CircularQueue { public: explicit CircularQueue(int capacity) : m_data(new T[capacity]), m_capacity(capacity), m_front(0), m_rear(0), m_size(0) {} ~CircularQueue() { delete[] m_data; } void push(const T value) { if (m_size m_capacity) { throw std::out_of_range(queue is full); } m_data[m_rear] value; m_rear (m_rear 1) % m_capacity; m_size; } void pop() { if (m_size 0) { throw std::out_of_range(queue is empty); } m_front (m_front 1) % m_capacity; --m_size; } T front() { if (m_size 0) throw std::out_of_range(queue is empty); return m_data[m_front]; } private: T* m_data; int m_capacity; int m_front; int m_rear; int m_size; };循环队列的关键操作是(rear 1) % m_capacity。有的实现会浪费一个位置来区分空和满我习惯用 m_size 来区分逻辑更直观也不容易误判。出队时不物理清除元素只移动 front这是循环队列一个很朴素但重要的理念。除了基础队列工程里更常用的是双端队列。C 标准库的 std::deque 就是分段连续存储既支持两端插入删除又不像链表那样每个节点单独分配我实现滑动窗口算法、任务调度队列时经常用它。3.3 栈与队列的联动案例有个很经典的例子能同时检验两种结构用队列实现栈或者用栈实现队列。我第一次做“用两个栈实现队列”时思路卡了很久。后来想明白了一个栈作为输入缓冲push 时直接压入pop 时先把所有元素弹出并压入另一个栈顺序就反转了再从第二个栈弹出就是先进先出。class QueueByTwoStacks { public: void push(int x) { input.push(x); } int pop() { if (output.empty()) { while (!input.empty()) { output.push(input.top()); input.pop(); } } int result output.top(); output.pop(); return result; } private: std::stackint input; std::stackint output; };这个技巧在实际中也有价值比如某些场景下你手头只有栈结构的 API却需要在语义上做成队列。反过来用队列实现栈也一样不过需要每次 pop 时把队尾之前的元素全都倒腾一遍复杂度会高一些。做这种题的意义不是背答案而是理解数据结构之间的转换关系这会让你在真正设计系统时多一层抽象思维。4. 二叉树与递归思维的建立4.1 二叉树节点的设计与三种遍历递归写法二叉树的节点比链表多一个指针需要同时记录左孩子和右孩子。递归遍历是理解二叉树的核心因为树的定义本身就是递归的一棵树的左右子树仍然是树。template typename T struct TreeNode { T data; TreeNode* left; TreeNode* right; TreeNode(const T value) : data(value), left(nullptr), right(nullptr) {} }; template typename T void preorder(TreeNodeT* node) { if (!node) return; std::cout node-data ; preorder(node-left); preorder(node-right); } template typename T void inorder(TreeNodeT* node) { if (!node) return; inorder(node-left); std::cout node-data ; inorder(node-right); } template typename T void postorder(TreeNodeT* node) { if (!node) return; postorder(node-left); postorder(node-right); std::cout node-data ; }递归遍历的字数很少但很多初学者看递归代码还是晕。我的建议是不要盯着代码一行行模拟执行而是把函数当作一个“已经正确完成某个任务的工具”。比如中序遍历你只需要相信一件事inorder(node-left) 会正确输出左子树的中序序列然后输出当前节点再相信 inorder(node-right) 会正确输出右子树。信心的建立来自于多做几道递归题包括求深度、判断对称、路径求和。还有一种容易忽略的遍历叫层序遍历也叫广度优先遍历。它天然需要队列配合先把根节点入队出队一个节点时就把它左右孩子入队直到队列为空。为什么递归写不了层序遍历因为递归的天然调用顺序是深度优先的如果想强行递归实现层序遍历需要额外记录节点所处的层数并按层数把节点塞到对应层的容器里本质上还是借了个“层”的概念模拟队列。4.2 二叉搜索树的插入与删除二叉搜索树简称 BST是二叉树最典型的应用之一。它满足左子树所有节点值小于根节点右子树所有节点值大于根节点。插入逻辑很纯粹递归往下走走到空位置就放进去TreeNodeint* insertBST(TreeNodeint* root, int value) { if (!root) { return new TreeNodeint(value); } if (value root-data) { root-left insertBST(root-left, value); } else if (value root-data) { root-right insertBST(root-right, value); } return root; }注意这里root-left insertBST(...)返回值要被接收否则新节点挂不上去。很多新手递归写出来但忘记“用返回值接住上一层”导致树根本没变化。删除比插入复杂因为要分三种情况删除叶子节点直接释放它返回 nullptr。删除只有一个孩子的节点让孩子顶替它的位置。删除有两个孩子的节点这个情况最麻烦。主流做法是找到左子树中最大的节点或者右子树中最小的节点把它提上来替换被删节点的值然后递归删除那个用来替换的节点。我用右子树最小节点的方案写一个TreeNodeint* findMin(TreeNodeint* node) { while (node node-left) { node node-left; } return node; } TreeNodeint* deleteBST(TreeNodeint* root, int value) { if (!root) return nullptr; if (value root-data) { root-left deleteBST(root-left, value); } else if (value root-data) { root-right deleteBST(root-right, value); } else { if (!root-left !root-right) { delete root; return nullptr; } else if (!root-left) { TreeNodeint* rightChild root-right; delete root; return rightChild; } else if (!root-right) { TreeNodeint* leftChild root-left; delete root; return leftChild; } else { TreeNodeint* successor findMin(root-right); root-data successor-data; root-right deleteBST(root-right, successor-data); } } return root; }两个孩子的删除方案理解起来比较绕我们不物理删除当前根节点而是把右子树的最小值复制到当前节点再递归去右子树删掉那个最小值。这样保证了当前节点的左子树仍然都小于根节点右子树中剩下的都大于根节点BST 性质不破坏。4.3 平衡问题与自平衡树普通 BST 有一个致命问题如果插入序列本身有序比如 1, 2, 3, 4, 5, 树会退化成一个直线链表查找复杂度从 O(log n) 退化到 O(n)。为了避免这种情况需要在插入删除后调整树形结构让左右子树高度差保持在一定范围内这就是平衡树。最常见的自平衡树有 AVL 树和红黑树。AVL 树要求每个节点的左右子树高度差不超过 1调整方式是单旋和双旋。红黑树规则更复杂但它的优势是插入删除时调整次数更少所以 C 标准库 std::map、std::set 底层采用红黑树。这里不需要手写红黑树但你需要理解一个现象当 map 的底层是红黑树时它的键值对始终是有序的因此 std::map 支持按键范围遍历、迭代器查找相邻键、lower_bound/upper_bound这些操作而 std::unordered_map 做不到。选择 map 还是 unordered_map本质是在“有序性”和“平均查找速度”之间做取舍。5. 图存储结构与遍历写法5.1 邻接矩阵和邻接表的取舍很多人学完二叉树就跳过图觉得图离业务很远。但图模型实际上到处都有社交关系、地图导航、任务依赖、网络爬虫的链接关系、六度分隔理论。图的存储方式主要有两种邻接矩阵和邻接表。邻接矩阵是一个二维数组adj[i][j]表示 i 到 j 是否有边。判断两个顶点是否相邻是 O(1)但需要 O(V²) 的空间稀疏图非常浪费。邻接表则是每个顶点对应一个链表或向量存储它所有邻接点空间是 O(VE)遍历某个顶点的全部邻接点非常自然。#include vector #include list #include iostream class Graph { public: explicit Graph(int vertices) : adjList(vertices) {} void addEdge(int from, int to) { adjList[from].push_back(to); adjList[to].push_back(from); // 无向图需要加一条反向边 } void dfs(int start) { std::vectorbool visited(adjList.size(), false); dfsHelper(start, visited); std::cout std::endl; } private: std::vectorstd::listint adjList; void dfsHelper(int vertex, std::vectorbool visited) { visited[vertex] true; std::cout vertex ; for (int neighbor : adjList[vertex]) { if (!visited[neighbor]) { dfsHelper(neighbor, visited); } } } };工程上稀疏图占绝大多数因此邻接表更常用。但邻接矩阵在稠密图里也有优势比如判断连通性、求所有点对最短路径的 Floyd 算法矩阵形态更容易实现和向量化。5.2 BFS 与拓扑排序的实战价值图的深度优先遍历和二叉树的递归很像函数调用天然就是深度优先。广度优先遍历则需要队列#include queue void bfs(int start, const std::vectorstd::listint adjList) { std::vectorbool visited(adjList.size(), false); std::queueint q; q.push(start); visited[start] true; while (!q.empty()) { int vertex q.front(); q.pop(); std::cout vertex ; for (int neighbor : adjList[vertex]) { if (!visited[neighbor]) { visited[neighbor] true; q.push(neighbor); } } } }注意一个细节入队时就标记 visited而不是出队时再标记。如果出队时才标记同一个节点可能被多个邻居重复入队导致队列膨胀甚至引起错误。这个细节在很多 BFS 问题里都是隐藏的坑。BFS 还有一个额外用途求无权图的最短路径。因为在 BFS 中第一次访问到某个节点时就一定是从起点到它的最短路径。这一性质在迷宫寻路、社交关系里“你和我隔了几个人”这类问题中非常好用。图的另一种重要技术是拓扑排序适合有向无环图。经典场景是任务依赖比如编译工程时A 依赖 B 和 CC 依赖 D那么排序结果必须保证被依赖的库先编译。实现思路用队列Kahn 算法统计每个节点的入度入度为 0 的节点入队每弹出一个节点就把它的邻接节点入度减 1减到 0 就入队。最终如果出队次数不等于总节点数说明图中有环。拓扑排序的代码本身不难但它背后的思维非常实用。我在实际项目中遇到的任务编排、依赖解析这类问题几乎都能用同一套逻辑抽象解决。6. 排序与查找工程里的高频操作6.1 常用排序的适用边界排序可以说是数据结构的综合练习因为你会用到数组、链表、栈、树、堆等一堆结构。C 里 std::sort 底层是快速排序和插入排序的组合大多数情况下直接用就行。但理解排序算法本身能帮你在标准库不够用的时候做出正确选择。常用排序可以做一个简单对比排序算法平均时间复杂度最坏情况空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定插入排序O(n²)O(n²)O(1)稳定归并排序O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n²)O(log n)不稳定堆排序O(n log n)O(n log n)O(1)不稳定实际选型时注意几点数据规模小比如十几到几十个元素插入排序反而最快因为常数因子小、缓存友好。需要稳定排序时std::stable_sort 会使用归并排序的思想代价是需要额外空间。系统自带排序不可用时比如嵌入式环境、内存受限堆排序是稳妥的原地排序方案。还有一种理解排序的方式把插入排序看作“在线算法”随时可以处理新来的元素把归并排序看作“分治算法”的典型代表适合通过递归思路掌握把快速排序看作“分区思想”的经典配合随机化基准值可以避免最坏情况。6.2 二分查找与哈希表的配合二分查找的前提是数据有序。它的代码很短但边界条件极其容易写错。我给出一个闭区间的写法这个写法在调试时最直观因为[left, right]区间内始终都是“还没确定答案”的部分。int binarySearch(const std::vectorint arr, int target) { int left 0, right arr.size() - 1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { return mid; } else if (arr[mid] target) { left mid 1; } else { right mid - 1; } } return -1; }为什么用left (right - left) / 2而不是(left right) / 2因为后者可能整型溢出这在 left 和 right 都是大整数时真实发生。这个问题我在 LeetCode 那种大规模测试用例里踩过排查半天发现是溢出导致 mid 变成负数而我一直以为是语法问题。查找本身是 O(log n)但尚未真正高速如果需要更快的判定“是否存在”哈希表才是主角。前面提到的 std::unordered_set 就是哈希表实现查找 O(1)。哈希表的本质是一个数组加哈希函数冲突靠拉链法解决。C 标准库的 unordered_map 内部就是哈希桶加链表。理解这一点有什么好处当元素很多、负载因子过高时rehash 会发生迭代器全部失效性能也会骤降。所以如果你对性能有极致要求可以提前预留空间map.reserve(n)。实践中我会这样组合使用数据需要保持有序遍历时用 map只需要查重或计数时用 unordered_map。例如在统计大量文本的词频时用 unordered_map 计数最快要输出字典序排序结果时再把键取出来放进 vector 排序。各干各擅长的活。7. 常见问题与排查技巧实录7.1 段错误的排查思路写链表和树最怕的就是段错误。这种错误的特点是程序直接崩掉但不告诉你哪一行出错所以很多人一遇到就慌。我的排查思路是分三层第一层检查空指针访问。访问某个指针的成员前必须确认它不为空。常见于链表 insert 时 prev 跑到空节点或者树递归时节点已经失效。第二层检查越界访问。数组下标是否超出了实际分配的长度是否把 size 和 capacity 混淆。这一类错误在顺序表实现里特别常见比如按 capacity 循环访问但 size 实际更小。第三层检查指针悬挂。某个节点被 delete 后还有另一个指针指向它。这通常是浅拷贝导致的两个链表共享了同一个节点。排查方式是用调试器打上断点看崩溃调用栈最上层的函数再反推哪一步操作可能让指针指向非法内存。我的习惯是链表相关代码里每个涉及指针的句子都先加断言比如assert(prev ! nullptr)这样崩溃位置会更精确。断言是调式好伙伴但正式发布时记得关掉或者替换成可恢复的错误处理。7.2 内存泄漏与野指针C 手写数据结构时new 和 delete 必须成对出现。链表中泄漏最隐蔽的场景是删除链表里部分节点时只断了链忘了 delete或者 delete 完没把指针置空。这些操作单个看问题不大但在循环中重复执行就会让内存占用不停上涨。我常用的防泄漏工具是 Valgrind它适合自查代码有没有内存问题。另外C11 以后可以用智能指针简化表达。比如链表节点用std::unique_ptrNode管理 next则删除节点时子节点也会被自动释放可以大幅减少手动 delete 的负担。不过智能指针也不是万能循环引用时 unique_ptr 无法处理两个节点互相指向对方就谁也释放不了这种情况需要 weak_ptr 打破引用环。对新手来说我更建议先老老实实用裸指针写一遍体会手动管理内存的痛再上智能指针。这个过程会让你明白为什么 C 需要 RAII 这么一套机制以后看别人代码时也能判断什么地方有生命周期问题。7.3 迭代器失效这个隐蔽问题写 C 容器代码最烦的bug之一是迭代器失效。简单说vector 扩容后它内部的数据存储位置可能整体搬家所有旧迭代器都会指向旧地址再用就会出问题。std::vectorint vec {1, 2, 3}; auto it vec.begin(); vec.push_back(4); // 可能触发扩容it 失效 std::cout *it; // 未定义行为可能崩溃list 没有这个问题因为节点是独立分配的insert 或 erase 只会影响被操作的那个节点的迭代器。遇到“边遍历边删除”的场景list 或 map 往往比 vector 更合适。如果必须在 vector 中删除标准做法是利用 erase 返回的迭代器for (auto it vec.begin(); it ! vec.end();) { if (condition(*it)) { it vec.erase(it); } else { it; } }这条技巧看起来是细节但很多人实测都会踩坑。我自己一度也是“先记录下来再统一删除”的写法虽然能绕开迭代器失效但多了一次遍历和拷贝数据大了性能吃亏。这些经验值得在新手阶段就记住省得以后再交学费。7.4 一张速查表帮你记住核心场景学数据结构时信息量大我建议自己动手整理一张速查表把“结构、核心操作复杂度、典型场景”放一起。下面是我的常用版数据结构核心操作复杂度典型场景数组/vector访问 O(1)尾部插入 O(1) 均摊缓存数据、随机访问、遍历链表头插 O(1)查找 O(n)大量插入删除、LRU 缓存栈push/pop O(1)函数调用、表达式求值、括号匹配队列push/pop O(1)BFS、任务调度、滑动窗口哈希表查找/插入 O(1) 平均查重、计数、缓存二叉搜索树查找/插入/删除 O(log n)动态有序数据、范围查询堆取最大最小 O(1)插入 O(log n)优先队列、TopK 问题图遍历 O(VE)路径规划、依赖分析、社交网络这张表不需要背而是你在选容器时用来查的。写代码前先问自己这个场景的主要操作是什么如果是“频繁判断某个值是否存在”哈希表大概率是答案如果是“要实时取出最大元素”堆才是答案。选对数据结构代码往往就已经成功了大半。8. 一些很值得养成的实操习惯最后聊几个我在实现数据结构时很受用的习惯对新手和老手都有用。第一个习惯是调试时打印每一层的状态。新手最怕的不是算法难而是代码跑起来完全不知道内部发生了什么。在自己的实现里临时加几行 cout打印插入前后的链表节点、打印递归调用的深度、打印每次扩容后的 size 和 capacity都比直接看抽象代码强得多。我看到好多人卡在一个 bug 上其实只要打印出当前指针地址马上就能看出是不是指向了错误的地方。第二个习惯是先画图再写代码。链表插入删除时画个箭头图旋转平衡树时画三个节点的高低关系BFS 队列变化时画出队列入队过程。我跟很多同事和同学交流发现大家都有一个共同点凡是画过图的题目代码基本一遍过凡是直接对着编辑器硬写的必然会在边界条件上反复试错。画图不是浪费时间它是把复杂逻辑落地的减速带帮你把心智负担降下来。第三个习惯是自己实现一遍标准库的常用容器。vector、list、stack、queue 都自己写一遍再对照标准库的接口设计思考为什么它要那样设计。这个过程会让你理解 move 语义、分配器、异常安全、迭代器设计这些进阶概念。标准库代码你或许读不完但自己实现朴素版再对比收获完全不一样。第四个习惯是测试时不要只用正常数据。空容器、单元素容器、大数据容量容器、频繁插入删除的场景都要测一遍。很多隐蔽 bug 都藏在这些边界里。我排查过一个栈溢出问题就是测试时只压入了少量数据等真正跑到百万级递归时才炸。提前在边界测试里把问题暴露出来比线上出问题再应急要舒服得多。我自己当年学数据结构最深刻的体会是这门课不单是知识的堆积更多是思维的训练。学任何新结构先把“它解决什么问题、什么约束、代价是什么”想清楚再推进到代码实现之后碰到实际问题时就能自然地想到用哪种结构。现在网上的学习资料非常多但资料太多也容易让人浮于表面只看不做。动手写一遍、调试一遍、踩一遍坑——这是通向真正的理解最靠谱的路径。如果你正在学这本书或者这门课给自己定个小目标学完一个结构就把它完整实现一遍并且写一个简单的应用比如用栈做括号匹配用队列做迷宫 BFS用 BST 做动态排名表。做完这些你再看其它代码时眼里看到的就不再是一堆语法而是背后一个个清晰的数据组织方式。这就是数据结构带给你的长期价值。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
