数据结构与算法这六个字几乎是我跟所有学编程的人聊天时绕不开的话题。有人觉得它抽象难啃有人觉得它是面试造火箭、工作拧螺丝但真正在项目里调过接口、压过性能、排查过线上问题之后你就知道这玩意儿不是纸面功夫。最近我在整理简历和复习笔记正好把常用的数据结构以及常用的算法从头到尾捋了一遍顺手把一些容易踩坑的细节也记了下来。这篇文章既适合准备面试和期末复习的同学也适合正在做课程设计、刚开始系统学算法的新人我会尽量用大白话加实际例子把每个东西讲清楚还带着能直接用的代码和避坑经验。1. 内容整体设计与思路拆解1.1 数据结构是容器算法是加工流程先解决一个最基本的疑问数据结构和算法到底是什么关系我的理解很简单数据结构解决“数据怎么存”的问题算法解决“数据怎么算”的问题两者拆不开。举个例子。你在外卖平台点单后台有一万个订单这些订单要排队等待配送。订单用什么结构存如果用数组新增订单容易但中间插入一个“加急单”就麻烦了因为后面所有元素都要往后挪。如果用链表插入删除很灵活但想按时间范围查询某一批订单就得从头遍历速度感人。这个场景里“怎么存”是数据结构的选择“怎么按时间排序、怎么把加急单插到合适位置、怎么快速统计某个商家的订单数”就是算法问题。两者是一套组合拳不能只学一边。我在带新人时经常说别把数据结构当成考试科目把它当成你的工具箱。数组、链表、栈、队列、哈希表、树、堆、图每个工具都有自己的脾气和适用场景。算法也不是天书它就是一套固定的操作流程比如让你在一堆数字里找目标值最笨的办法是挨个看聪明点的办法是排序后每次砍一半。后者就是二分查找。1.2 从一张脑图认识常用的数据结构学数据结构脑子里一定要有全景图。我习惯把它们分成四类。第一类线性结构。数组、链表、栈、队列它们的特点是数据排成一条线每个元素最多有一个前驱和一个后继。第二类树形结构。二叉树、二叉搜索树、堆、B树、红黑树数据有层次关系像文件夹的目录一个父节点可以有多个子节点。第三类图形结构。邻接矩阵、邻接表数据之间是任意多对多的关系比如社交网络里的人和人导航地图里的路口和道路。第四类散列结构。哈希表它通过哈希函数把“键”直接映射到“存储位置”用空间换时间实现近似O(1)的查找。先记住这个分类后面每个结构单独拿出来深挖就不会乱了。1.3 算法复杂度判断代码好坏的第一把尺看一个算法的好坏不是看代码行数而是看数据量变大时它要跑多久、吃多少内存。大O表示法就是干这个的。O(1)代表常数时间不管数据多大用时都一样比如数组按下标访问。O(log n)是对数时间数据翻一倍只多一步比如二分查找。O(n)是线性时间数据翻一倍用时翻一倍比如遍历数组。O(n log n)是线性对数时间大多数高效排序都在这个级别。O(n²)是平方时间数据一多就爆炸冒泡排序就是典型。我常用一个电话簿的类比来理解在通讯录里找一个人O(1)是你知道他在第几页第几行直接翻过去O(n)是从第一页开始一页一页翻O(log n)是你随手翻开中间一页根据字母大小决定往前翻还是往后翻每次都能排除一半。另一个重点是空间换时间。哈希表能用O(1)时间查找是因为它提前开了一大块内存递归能写出简洁代码是因为系统栈在存中间状态。很多算法优化的本质就是在时间和空间之间做取舍。1.4 学习路线怎么安排更高效我见过很多新手一上来就啃红黑树、KMP结果两天就劝退了。我的建议是按层级来。第一层先把数组、链表、栈、队列玩明白。这几个结构简单但要实现得毫无瑕疵比如链表反转、栈实现队列面试经常考。第二层学树和哈希表。二叉树的遍历、二叉搜索树的增删查、堆的建堆和调整这些是高频考点。第三层学排序和二分查找这是算法思维的第一道坎也是后面很多算法的基础。第四层学递归、DFS、BFS、贪心、动态规划这些是真正的算法进阶内容。刷题不需要贪多一天认真做两三道每道题想清楚为什么用这个结构、为什么这个复杂度比一天刷二十道然后看一遍题解就忘要强得多。教材方面经典的严蔚敏《数据结构》适合打基础但是偏理论《大话数据结构》图多例子多适合入门王道系列适合考研复习知识点特别紧凑。配合力扣、洛谷这些平台练手就行。2. 常用数据结构核心细节与实操要点2.1 线性结构四兄弟数组、链表、栈、队列数组和链表是最基础的两个其余很多结构都是它们的组合或扩展。数组的特点是内存连续按下标访问是O(1)这因为只要知道首地址加个偏移量就能算出来。但插入和删除是O(n)因为要移动后续元素。数组还有个扩容问题动态数组在容量不够时一般按1.5倍或2倍扩容然后把旧数据拷贝过去摊还下来单次插入还是O(1)。链表的特点是节点在内存里不连续每个节点存着下一个节点的指针。插入和删除只要改指针理论上是O(1)但问题是你要先找到那个位置查找过程就是O(n)。链表还有个容易被忽视的缺点对CPU缓存不友好。数组在内存中是连续的一块加载时一次能读很多链表节点分散在各处每跳一个节点就可能触发一次内存访问实际跑起来比数据规模暗示的还要慢。链表实现时我最推荐一个技巧虚拟头节点。比如删除链表中某个节点如果删的是头节点处理起来很啰嗦加一个dummy节点统一用“前驱.next 前驱.next.next”来处理代码干净很多。栈和队列是两种受限的线性表。栈只能在一端操作后进先出。函数递归调用就是靠系统栈括号匹配、表达式求值、浏览器的后退按钮都是栈的应用。单调栈是一种特殊用法维护栈内元素单调递增或递减典型场景是一排柱子找左右两边第一个比它矮的柱子复杂度从O(n²)降到O(n)。队列是先进先出任务调度、CPU进程排队、BFS搜索都靠它。普通数组实现队列会有“假溢出”问题下标往后走前面空着却用不了所以工程上常用环形队列用一个数组加头尾指针取模绕圈。我这里放一个环形队列的核心思想示意用C写大概是这样class CircularQueue { vectorint data; int head, tail, size, capacity; public: CircularQueue(int k) : capacity(k), data(k), head(0), tail(0), size(0) {} bool enQueue(int value) { if (isFull()) return false; data[tail] value; tail (tail 1) % capacity; size; return true; } bool deQueue() { if (isEmpty()) return false; head (head 1) % capacity; size--; return true; } bool isEmpty() { return size 0; } bool isFull() { return size capacity; } };注意tail指向的是下一个空位取模是为了让头尾指针在数组边界处自然“绕圈”。很多底层的消息队列、日志缓冲区就是类似的做法。2.2 树结构从二叉树到堆和搜索树树是最重要的非线性结构。二叉树每个节点最多两个子节点左右之分是有意义的。遍历方式有四种前序、中序、后序、层序。前三种用递归写很简单但递归深度大了会爆栈所以要会迭代写法。迭代前序遍历用栈把节点压栈先压右孩子再压左孩子层序遍历用队列。二叉搜索树的特点是左子树所有节点小于根右子树所有节点大于根。查找、插入、删除的平均复杂度是O(log n)。但有个致命问题如果插入顺序恰好有序BST会退化成一条链表查找变成O(n)。解决这个问题的思路就是平衡比如AVL树是严格平衡任何节点的左右子树高度差不超过1红黑树是近似平衡最长路径不超过最短路径的两倍。C的std::map底层就是红黑树它能保持有序所以遍历结果是排序好的。堆是一种完全二叉树适合用数组存储。大顶堆的每个节点都大于等于它的子节点堆顶永远是最大值。堆的核心操作是上滤和下滤插入时在数组尾部加一个元素然后往上调整删除堆顶时把最后一个元素挪到堆顶然后往下调整。建堆可以在O(n)时间内完成而排序是O(n log n)。实际做TopK问题比如从一百万个数字里取前十个最大的最直观的想法是排序但排序要O(n log n)。用大小为10的小顶堆遍历一遍数组堆顶永远是目前第十大的数遇到比堆顶大的就把堆顶替换掉再调整最后堆里就是最大的十个数字时间复杂度O(n log 10)近似O(n)。C的priority_queue默认是大顶堆但可以这样声明小顶堆// 小顶堆greaterint 让优先队列反转为最小值在堆顶 priority_queueint, vectorint, greaterint minHeap;2.3 哈希表空间换时间的典型代表哈希表可能是日常开发中用得最多的数据结构。它的原理是把一个键通过哈希函数计算得到一个数组下标然后把值存到对应位置。理想情况下查找、插入、删除都是O(1)。哈希函数不可能完美不同键算出来同一个下标就产生冲突。解决冲突有两种主流方案。链地址法是把同一个下标下的元素串成链表C的unordered_map和Java的HashMap都是这个思路链表太长时Java会转成红黑树。开放寻址法是在冲突时往后探测空位适合数据量小、装在因子低的场景。装载因子是个关键参数元素个数除以桶数量。装载因子越高冲突概率越大性能下降。所以哈希表会扩容比如装载因子超过0.75就翻倍。扩容时要重新计算所有已有元素的存放位置开销很大所以预估数据量、提前指定初始容量是个重要优化技巧。工程上哈希表的典型场景缓存系统用URL当键响应内容当值去重比如统计一篇文章里每个词出现多少次索引数据库里基于哈希的索引能快速定位等值查询。做LRU缓存时有个经典组合双向链表加哈希表。哈希表负责O(1)地找到节点双向链表负责维护访问顺序。每次访问一个节点就把它移到链表头部缓存满时淘汰链表尾部的节点。这个设计把两个结构的优势拼在一起面试极其高频。用哈希表有个隐藏的坑遍历顺序不确定。unordered_map的遍历顺序由哈希函数和装载因子决定同一份数据在不同编译器版本或不同插入顺序下遍历结果都可能不一样。如果你的业务依赖固定顺序一定别用哈希表老老实实用map或者vector加排序。2.4 图结构邻接矩阵与邻接表的取舍图用来表达多对多的关系。人跟人的好友关系城市之间的路线软件包之间的依赖都可以建模成图。图的存储方式主要有两种。邻接矩阵用二维数组matrix[i][j]表示从i到j是否有边或者权重多少。它的优点是判断两点是否相连是O(1)缺点是空间占用是O(V²)适合顶点少、边很稠密的图。邻接表是每个顶点存一个链表或vector记录它能到达的邻居。优点是空间O(VE)适合稀疏图现实生活中大多数图都是稀疏的。缺点是判断两点是否直接相连要遍历邻居列表。写图算法时推荐用邻接表。C大概是这样// graph[u] 存放所有以 u 为起点的边pair目标节点, 权重 vectorvectorpairint, int graph(n); graph[0].push_back({1, 5}); graph[0].push_back({2, 3});DFS和BFS就是图上的两种遍历方式。DFS适合判断连通性、找路径、拓扑排序BFS适合求无权图的最短路径因为它一层层向外扩展第一次访问到目标节点时的层数就是最短距离。图论里的经典算法最短路径的Dijkstra最小生成树的Prim其实核心思想都是贪心加优先队列。我建议你在纸上手动模拟几个小图把过程走一遍比看十遍代码都管用。3. 常用算法原理、实现与避坑3.1 排序算法怎么选排序可以说是算法的“武林入门”。不用背所有排序但下面这几个一定要理解透。冒泡排序是最容易理解的两两比较大的往后交换每一轮确定一个最大值放到末尾。它稳定但时间O(n²)基本只用于教学。快速排序是分治思想的代表选一个基准元素把小于它的放左边大于它的放右边再递归处理左右两边。平均O(n log n)最坏O(n²)最坏情况发生在基准选得不巧、且数据本身有序时。C标准库的sort是混合实现IntroSort先快排递归深度超限就转堆排序小规模数据转插入排序所以性能很稳。很多面试官会手撕快排我写一个常见的原地partition版本int partition(vectorint nums, int low, int high) { int pivot nums[low]; while (low high) { while (low high nums[high] pivot) high--; nums[low] nums[high]; while (low high nums[low] pivot) low; nums[high] nums[low]; } nums[low] pivot; return low; } void quickSort(vectorint nums, int low, int high) { if (low high) return; int pos partition(nums, low, high); quickSort(nums, low, pos - 1); quickSort(nums, pos 1, high); }这个写法是“坑位法”把基准元素当作空位从右往左找小于基准的填到左边从左往右找大于基准的填到右边最后基准归位。注意比较时用了和这样能避免区间划分不均导致死循环。堆排序的优势是在原数组上建堆不需要额外空间时间复杂度稳定O(n log n)但它不稳定相等的元素可能会交换顺序。归并排序稳定时间复杂度O(n log n)缺点是合并时需要额外O(n)空间。它适合外部排序比如对超大数据文件排序内存放不下只能一块块读进来归并。排序算法的选择经验很简单大部分场景直接用标准库的sort就行不要自己造轮子。需要稳定排序时用stable_sort。需要找TopK时用堆不要先把所有数据排序。我把几个关键指标放一个表格里。算法平均时间最坏时间空间稳定性冒泡排序O(n²)O(n²)O(1)稳定快速排序O(n log n)O(n²)O(log n) 栈空间不稳定堆排序O(n log n)O(n log n)O(1)不稳定归并排序O(n log n)O(n log n)O(n)稳定3.2 二分查找left right 还是 left right二分查找逻辑简单但写对边界条件很难很多人都在这上面翻过车。它的适用范围是单调有序的数据每次取中间值比较把搜索区间砍半。最经典的写法是int binarySearch(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) return mid; else if (nums[mid] target) left mid 1; else right mid - 1; } return -1; }这里有两个关键点。第一mid一定要写成left (right - left) / 2不要写成(left right) / 2因为left加right可能整数溢出。第二当目标值在右边时left更新为mid 1在左边时right更新为mid - 1这不是固定的取决于你的区间定义。如果你用的是左闭右闭区间循环条件while (left right)那left和right的更新必须把mid排除在外否则会死循环。如果你用左闭右开区间循环条件是while (left right)这时right mid而不减1因为右边界是开区间。更进阶的需求是找第一个等于target的位置或者最后一个等于target的位置。我通常把二分逻辑封装成“查找第一个满足条件的位置”这个更通用的模板比如找第一个大于等于target的位置int lowerBound(vectorint nums, int target) { int left 0, right nums.size(); // 注意是开区间 while (left right) { int mid left (right - left) / 2; if (nums[mid] target) left mid 1; else right mid; } return left; }这个模板返回的是第一个大于等于target的下标把改成就变成第一个大于target的位置。熟悉这一套之后处理很多边界问题都会轻松很多。3.3 递归、DFS、BFS与贪心递归是很多算法的基础它的核心是“自己调用自己”。写递归就三件事终止条件、递归调用、处理返回值。递归容易有两个问题。一是死循环忘记终止条件。二是栈溢出递归深度超过系统限制比如在一组链式结构上做深递归深度一万就会爆。遇到这种情况要么改成迭代加显式栈要么用尾递归但很多编译器不优化要么干脆换成递推。DFS和BFS本质是树的遍历扩展到图上。DFS在有岔路时一条道走到黑适合找所有解、判断连通性、回溯场景。BFS是一圈圈扩散适合找最短路径、最少步数。贪心算法的思路是每一步都做当前最优选择希望最终结果也最优。它不一定能得到全局最优但遇到某些特定结构时非常高效。经典的例子是区间调度给定一堆会议的开始和结束时间选最多数量的不重叠会议。做法是按结束时间排序每次选结束时间最早且和已选会议不冲突的那个。这个“证明贪心正确”的过程才是核心面试时很多人只背答案一问为什么就露馅。最长递增子序列这类问题不要一上来就用DP因为它可以优化成二分加贪心时间复杂度O(n log n)我第一次看到这个解法时觉得特别巧妙。所以贪心的价值不是替代动态规划而是很多DP问题有更高效的贪心版本前提是你得判断得出来。3.4 字符串匹配与KMP算法字符串查找是每天都在用的功能。最简单的是暴力匹配模式串从文本串第一个字符开始逐个比对失配就整体后移一位再试时间复杂度O(n*m)。当文本很长、模式串很长时性能很糟糕。KMP算法的思想是失配时不把模式串整体右移一位重新比而是根据已经匹配的部分信息跳过不可能匹配的位置。这个“部分信息”就是next数组也叫部分匹配表。next数组的含义是当模式串第j个字符失配时模式串应该跳到哪个位置继续比。构建next数组的核心是“自己匹配自己”void buildNext(const string p, vectorint next) { next[0] -1; int i 0, j -1; while (i p.size() - 1) { if (j -1 || p[i] p[j]) { i; j; next[i] j; } else { j next[j]; } } } int kmpSearch(const string s, const string p) { int n s.size(), m p.size(); vectorint next(m); buildNext(p, next); int i 0, j 0; while (i n j m) { if (j -1 || s[i] p[j]) { i; j; } else { j next[j]; } } if (j m) return i - j; return -1; }它的时间复杂度是O(nm)因为i和j的移动都是单调的。KMP的难点不在代码而在理解next数组是怎么算出来的。我建议在纸上跑一遍“ABABCABAB”这种模式串把每个位置的next值手算一遍比看十遍文章都管用。3.5 动态规划和图论经典算法动态规划就是把一个大问题拆成有重叠子问题的小问题把小问题的答案存下来避免重复计算。理解DP就抓三个东西状态定义、转移方程、初始化。以最简单的斐波那契为例从递归到DP就是把f(n)保存下来每个值只算一次。而0-1背包问题是更典型的DP有n个物品每个有重量和价值背包容量有限问能装的最大价值。一维优化的背包代码很经典关键在于倒序遍历容量vectorint dp(capacity 1, 0); for (int i 0; i n; i) { for (int w capacity; w weight[i]; w--) { dp[w] max(dp[w], dp[w - weight[i]] value[i]); } }为什么要倒序因为二维状态转移时dp[i][w]依赖的是dp[i-1][w - weight[i]]如果正序遍历一维数组dp[w - weight[i]]已经包含了当前第i个物品的信息就会出现一个物品被选多次的问题。倒序遍历让更新时用的还是上一轮的结果。图论算法里Dijkstra是单源最短路径核心是每次从优先队列里取出距离最小的未访问节点然后松弛它的邻居。Prim是求最小生成树和Dijkstra长得极像区别是Prim更新的是节点到整个已选集合的最小距离而Dijkstra更新的是到起点的距离。这两个算法建议一起学对比着记忆效率高很多。4. 常见问题排查与学习建议实录4.1 面试高频问题与解题模板我在面试和被面试过程中发现有些数据结构题几乎是必考模板要背得滚瓜烂熟。判断链表有没有环用快慢指针快指针每次走两步慢指针走一步如果有环两者一定会相遇。为什么快指针不走三步因为步长差太大时可能跳过相遇点两步最稳妥。括号匹配用栈遇到左括号入栈右括号时检查和栈顶是否配对。这里有个常见坑右括号来了但栈为空直接返回false不然会访问空栈。两个栈实现队列一个栈负责入队一个栈负责出队出队时如果出队栈为空把入队栈所有元素压进去。这个“倒一次”的摊销复杂度是O(1)。TopK问题用堆前面已经说过了。LRU缓存的“双向链表哈希表”组合也是高频。还有一个容易被问到的是“两个有序数组合并成一个有序数组”从后往前填可以避免额外空间这个小技巧很实用。4.2 实际工程里最常见的算法翻车点工作中写代码遇到的坑往往不是算法本身难而是细节没注意。第一排序稳定性。如果你先用一个字段排了序再用另一个字段排序第二个排序如果是不稳定的第一个字段的相对顺序可能会被打乱。所以遇到“先按时间排序同时间按ID排序”这类需求最好用stable_sort或者在比较函数里把两个条件一起判断。第二整数溢出。二分查找的mid (left right) / 2在left和right都很大时会溢出。统计金额、计算时间戳差值时也容易溢出养成用left (right - left) / 2和long long的习惯。第三递归深度爆栈。有一道分治法求数组最大值的题递归深度是log n没问题但如果你递归下去每次都只减少一个元素比如写一个不成熟的快排partition深度就是O(n)n到十万就栈溢出。第四哈希表的无序性。我在一个项目里用unordered_map存配置项上线后发现配置的加载顺序不稳定日志排查特别痛苦。后来把key排序输出才定位到问题。从此学乖了需要顺序就用map不需要才用unordered_map。4.3 新手高频翻车点速查表我把这几年看新人踩过的坑整理成一张速查表你自己排查的时候也可以对着看。现象可能原因解决办法二分查找死循环区间更新条件不对明确左闭右闭还是左闭右开mid更新时排除mid快排最坏超时数据有序且基准选第一个基准随机化或三数取中链表操作丢失节点修改指针前没保存next画指针图先保存后继再改指向背包DP结果偏大容量正序遍历导致物品重复取倒序遍历容量哈希表遍历顺序总变用了unordered_map且依赖顺序换成map或排序后再处理递归栈溢出递归深度太大改迭代加显式栈或改递推排序后相等元素乱序排序不稳定用stable_sort或在比较器加次要条件哈希冲突导致O(1)变O(n)哈希函数差或装载因子过高换更好的哈希函数提前扩容4.4 高效学习与刷题建议最后说点实在的学习方法。刷题时不要一上来就看题解。先看题目数据范围估算自己该用什么复杂度然后思考10到15分钟。想不出来再看题解的第一行思路不要看代码然后自己写。写完后再跟最优解对比看差在哪里。这个流程虽然慢但一道题顶别人十道。建议不要只刷单一知识点。比如你刚学完二分就专门做几道二分题但之后要混合刷因为面试和实际工作里没人会告诉你“这题该用二分”。关于语言学算法用你日常写项目的语言就行。C的STL强大Java的集合类丰富Python写起来短。但要注意别太依赖API比如你要知道优先队列是怎么调整堆的才好在需要手写堆的时候不慌。如果是为了课程设计或期末复习严蔚敏的习题集、王道的数据结构辅导书可以搭配使用。课程设计里很多题目比如“植物百科数据的管理与分析”本质就是文件的增删改查加排序统计用线性表加几个排序算法就能完成关键是把接口设计清楚把每个函数的职责划分明白。我个人还有一个习惯把学过的数据结构和算法做成一张自检清单。每学一个就写下它是干嘛的、底层怎么存、各操作复杂度是多少、适合什么场景、有什么坑。复习时只看这张表很快就能把知识串起来。这几年带新人、面试别人最深的感觉是数据结构与算法不是让你背代码而是在训练一种思考秩序。遇到一个问题先想数据长什么样、该用什么容器装再想数据量多大、时间复杂度能不能接受最后想边界条件会不会炸。这套思路一旦形成肌肉记忆不管写业务代码还是做底层优化都会稳很多。最后再分享一个小技巧学任何算法都自己手动在纸上跑一遍过程特别是快排的partition、堆的上滤下滤、KMP的next数组。眼睛看十遍不如手走一遍这个过程虽然慢但你会真正理解它为什么效率高、哪里容易出问题。别人的代码能跑不代表你自己写的时候不踩坑亲手推导过一遍的算法才是你的。