1. 项目概述为什么我们需要一本自己的《数据结构习题集》如果你正在学习计算机科学或者准备踏入软件开发这个行当那么“数据结构”这四个字对你来说一定不陌生甚至可能有点“又爱又恨”。爱的是它是构建一切复杂程序的基石是面试官最喜欢问的“八股文”之一恨的是那些抽象的概念、复杂的算法和永远做不完的题目常常让人感到挫败。市面上的教材比如严蔚敏老师的《数据结构C语言版》或者李春葆老师的《数据结构教程》都提供了丰富的理论知识。王道考研的辅导书更是将考点梳理得明明白白。但问题在于从“看懂”到“会做”再到“熟练”中间隔着一条巨大的鸿沟。这就是我决定整理这份《数据结构习题集》的初衷。它不是一个简单的题目罗列而是我结合自己十多年的开发、面试和教学经验从海量题目中筛选、归类、并重新解构的实战手册。我发现很多同学学数据结构容易陷入两个极端要么死记硬背代码题目一变就懵要么只停留在理论层面动手写代码时漏洞百出。这份习题集的目标就是充当一座桥梁帮你把散落的知识点通过一道道精心设计的题目串联成可以解决实际问题的能力网络。无论是为了应对期末考试还是备战技术面试或是单纯想夯实编程内功这份习题集都试图提供一条清晰的路径。我会围绕线性表、栈、队列、树、图、查找、排序这些核心章节不仅给出题目和答案更重要的是拆解每道题背后的考察意图、多种解法的优劣对比以及在实际开发中可能的应用场景。比如当你理解了deque双端队列在滑动窗口问题中的妙用或是哈希表在缓存设计中的核心地位学习就不再是枯燥的记忆而是一次次“哦原来如此”的顿悟。2. 习题集整体设计与学习路径规划盲目刷题是学习数据结构的大忌。没有章法的练习就像在迷宫里乱撞耗时费力却收效甚微。一份好的习题集必须配有科学的学习路径。我的设计思路是“分层递进场景驱动”将整个学习过程划分为四个明确的阶段确保你能步步为营从入门到精通。2.1 第一阶段夯实基础——理解抽象与实现这个阶段的目标不是追求难题、怪题而是确保你对每一种基本数据结构的定义、特性和基本操作达到“肌肉记忆”般的熟练程度。很多同学轻视这一步直接去啃《王道数据结构笔记》里的复杂算法结果基础不牢地动山摇。核心任务手动实现抛开C STL的deque、Java的ArrayList亲手用C语言或你熟悉的语言实现一遍线性表顺序表、链表、栈、队列包括循环队列、二叉树链式存储。这个过程痛苦但必要。你会深刻理解“指针操作”、“内存管理”、“边界条件”这些教材里一笔带过却至关重要的细节。复杂度分析为你的每一个Insert、Delete、Search操作清晰地标出时间复杂度和空间复杂度。问自己在头部插入和尾部插入为什么代价不同链表和数组的随机访问性能差异根源在哪对比学习制作一个对比表格。这是厘清概念最有效的方法。例如数据结构物理结构插入/删除头部随机访问典型应用顺序表 (数组)连续存储O(n)O(1)需要频繁按索引查询单链表离散存储O(1)O(n)频繁在头部插入/删除双链表离散存储O(1)O(n)需要双向遍历栈 (数组实现)连续存储仅尾部操作 O(1)不支持函数调用栈、表达式求值队列 (循环数组)连续存储头部出O(1)尾部入O(1)不支持消息队列、广度优先搜索实操心得在第一阶段我强烈建议你准备一个“错题本”但不是抄题目而是记录**“思维卡点”**。比如“在实现双向链表删除节点时总是忘记处理前驱节点指针为NULL的情况”。这种针对具体操作失误的记录比泛泛地写“链表操作不熟”有用一百倍。2.2 第二阶段核心突破——掌握典型问题与算法当基础操作像呼吸一样自然时就可以进入第二阶段。这一阶段我们将面对数据结构教材和《数据结构与算法》课程中的经典问题。这些问题模式固定是构建解题思维的“模板”。重点专题链表专题反转链表递归与非递归、检测环快慢指针法、合并有序链表、寻找中间节点、删除倒数第N个节点。这些题目是面试的绝对高频点务必做到一遍写对。栈与队列专题用栈实现队列、用队列实现栈、括号匹配、表达式求值中缀转后缀、滑动窗口最大值使用deque。这里你会体会到栈的“后进先出”和队列的“先进先出”如何巧妙地解决特定问题。树专题二叉树的三种深度优先遍历递归与非递归、层次遍历、求深度/节点数、最近公共祖先、二叉搜索树的验证与操作。这是从线性结构到非线性结构的关键跳跃。初步排序实现冒泡、选择、插入排序并理解其O(n²)的复杂度。尝试实现归并排序和快速排序理解分治思想。注意事项本阶段刷题切忌只看不写。务必在IDE里手敲代码并自己设计测试用例。一个常见的陷阱是“眼高手低”——看答案觉得懂了一写就错。我的方法是每道题用30分钟独立思考和编写如果解不出再看解析然后关掉解析从头再写一遍。2.3 第三阶段综合应用——融会贯通与优化前两个阶段是“零件加工”第三阶段是“组装整机”。这里的题目往往需要组合多种数据结构并引入更复杂的算法思想如递归、回溯、动态规划、贪心等。这也是区分“普通”和“优秀”的关键阶段。典型场景图的应用深度优先搜索(DFS)和广度优先搜索(BFS)的路径查找、拓扑排序、最短路径Dijkstra算法、最小生成树Prim/Kruskal。这些算法在社交网络、地图导航、依赖管理中广泛应用。高级树结构AVL树或红黑树的旋转调整理解思想即可除非面试特定要求、B树/B树为何是数据库索引的基石、字典树(Trie)在自动补全中的应用。了解这些能让你明白数据结构的设计是如何深刻影响上层系统性能的。哈希的威力两数之和、字母异位词分组、最长无重复子串……大量问题可以通过哈希表将时间复杂度从O(n²)降至O(n)。你需要熟练掌握如何设计合适的键(Key)。堆与优先队列Top K 问题、流数据的中位数、任务调度。Java的PriorityQueue其本质就是堆数据结构。理解堆就能理解许多“实时获取最值”场景的高效解决方案。排查技巧实录在解决复杂递归或回溯问题时最有效的调试方法不是依赖IDE的调试器步步跟进容易跟丢而是**“人肉递归”“打印状态”**。准备一张纸画出递归树在代码关键点打印出当前的参数和状态如路径、选择列表。这对于理解“全排列”、“N皇后”这类问题尤其管用。我曾用这个方法帮很多同学瞬间打通了回溯算法的任督二脉。2.4 第四阶段实战与拓展——面向真实世界学习的最终目的是应用。这一阶段习题将更贴近实际工程和前沿领域帮助你完成从“学生”到“工程师”的思维转变。拓展方向结合特定语言/框架研究Java中ArrayList与LinkedList的源码差异分析Redis的数据结构如跳表实现有序集合、压缩列表阅读ARM ELF文件的格式定义理解文件头、节区头表这些“数据结构”在系统层面的作用。系统设计中的数据结构如何用队列实现一个简单的消息中间件如何用哈希表双向链表设计一个LRU缓存Deque在Java的ArrayDeque中是如何分配内存以保证两端高效操作的思考这些问题能让数据结构知识“活”起来。应对海量数据当数据量无法装入单机内存时所谓“大数据”我们学过的BitMap、布隆过滤器、一致性哈希等结构就派上了用场。这时数据结构的重点从“精确”变成了“概率”和“分布”。3. 核心数据结构深度解析与高频考点拆解掌握了学习路径我们还需要对几个最容易混淆、最常考的核心数据结构进行“显微镜”式的观察。理解它们的本质差异和适用场景是高效解题的前提。3.1 栈、队列与双端队列Deque操作受限的线性表很多人知道栈是LIFO后进先出队列是FIFO先进先出。但关键在于理解它们“操作受限”这一特性带来的优势和特定应用。栈它模拟了“回溯”行为。函数调用栈是最经典的例子调用新函数时入栈函数返回时出栈保证了执行顺序的正确性。在算法中它擅长解决“对称”、“匹配”、“回退”类问题比如括号匹配、浏览器前进后退、深度优先搜索的非递归实现。考点如何用O(1)时间复杂度获取栈内最小值辅助栈法如何用栈来模拟递归队列它模拟了“排队”行为。保证了处理的公平性和顺序性。广度优先搜索(BFS)是队列的招牌应用它按“层次”遍历树或图。消息队列则是分布式系统中的核心组件。考点如何用数组实现高效的循环队列判断队列空和满的条件是什么通常用(rear1)%capacity front表示满front rear表示空但会浪费一个存储空间。双端队列 (Deque)这是栈和队列的“结合体”也是面试中的新宠。两端都能进行插入删除灵活性极高。核心应用滑动窗口最大值/最小值问题。这是Deque的经典高光场景。暴力法需要O(n*k)而利用一个维护窗口内元素索引的、单调递减的Deque可以在O(n)时间内解决。其核心思想是在Deque中存储可能成为未来窗口最大值的元素索引并及时淘汰过期和不可能的元素。实现细节在C STL中deque通常由一段段定长的连续空间缓冲区通过一个中央map不是哈希表而是一个指针数组来管理因此它支持随机访问且两端增删效率接近O(1)是替代vector需要大量头部操作时和list需要随机访问时的折中选择。3.2 树与二叉树从链式结构到递归王国树是理解递归最直观的数据结构。很多同学对递归感到恐惧很大程度上是因为没有建立起清晰的“递归树”思维模型。二叉树遍历前序、中序、后序。必须掌握递归和迭代两种写法。迭代写法通常需要借助栈来模拟递归过程。非递归遍历的窍门可以统一采用一种“标记法”。在将节点入栈时同时入栈一个标记如NULL当从栈中取出节点发现标记时才进行访问。这种方法代码模板统一易于记忆。二叉搜索树(BST)它的中序遍历序列是递增的。这个性质是解决很多BST问题的钥匙如验证BST、寻找第K小元素。易错点验证BST时不能只判断左孩子根右孩子。必须确保整个左子树的所有节点都小于根整个右子树的所有节点都大于根。需要用上下界递归验证。平衡二叉树(AVL/红黑树)为什么要平衡因为极端情况下如插入有序序列BST会退化成链表查找复杂度从O(log n)恶化到O(n)。平衡通过旋转操作来维持。学习建议对于大多数面试不需要手写旋转代码但必须理解旋转的四种情况LL, RR, LR, RL以及平衡因子的概念。重点理解其“通过局部调整维持全局平衡”的思想。3.3 哈希表用空间换时间的艺术哈希表是平均时间复杂度为O(1)的“神器”但其内部机制充满细节。核心三要素哈希函数将任意长度的输入映射到固定范围的索引。理想情况是均匀分布减少冲突。常用方法有取模、乘法取整等。冲突解决链地址法每个桶数组位置挂一个链表或红黑树如Java 8的HashMap。这是最常用的方法。开放地址法发生冲突时按某种探测序列线性探测、平方探测寻找下一个空位。对装载因子更敏感。扩容机制当元素数量超过容量 * 装载因子时需要扩容通常是翻倍并重新哈希所有元素。这是一个O(n)的高成本操作但摊还下来仍是O(1)。高频考点设计一个哈希集合或哈希映射。利用哈希表将“两重循环查找”优化为“一次遍历查找”如“两数之和”。设计复杂的键(Key)例如将字符串排序后的结果作为键来分组“字母异位词”。3.4 堆一种特殊的完全二叉树堆通常指二叉堆它是一棵完全二叉树且满足父节点的值总是大于等于大顶堆或小于等于小顶堆子节点的值。核心操作insert新元素放末尾然后“上浮”(sift-up)。pop取最值取堆顶将末尾元素移到堆顶然后“下沉”(sift-down)。这两个操作的时间复杂度都是O(log n)。应用场景优先队列Java的PriorityQueueC的priority_queue底层就是堆。用于需要动态获取最大值/最小值的场景。Top K 问题求最大的K个元素用小顶堆维护K个元素堆顶是这K个里最小的求最小的K个元素用大顶堆。堆排序基于堆的选择排序时间复杂度O(n log n)是不稳定的排序算法。注意事项堆只保证堆顶元素是最值内部元素是无序的。它的物理存储通常用数组利用下标关系定位父节点和子节点对于下标i父节点为(i-1)/2左孩子为2*i1右孩子为2*i2。4. 排序算法全景图从原理到优化策略排序是数据结构的集大成者它综合考察了对数组的操作、递归、分治、堆等多项知识。死记硬背代码行不通必须理解其背后的“动力学”。4.1 比较排序的“天下”基于比较的排序其时间复杂度下界是O(n log n)。我们可以从简单到复杂梳理出一条清晰的脉络。排序算法平均时间复杂度最坏时间复杂度空间复杂度是否稳定核心思想适用场景冒泡排序O(n²)O(n²)O(1)稳定相邻交换每一趟将最大元素“冒泡”到最后教学用途实际极少使用选择排序O(n²)O(n²)O(1)不稳定每趟选择最小大元素放到已排序序列末尾对稳定性无要求且交换次数少插入排序O(n²)O(n²)O(1)稳定将元素插入到已排序序列的合适位置小规模数据或基本有序数据效率很高希尔排序O(n^1.3)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)不稳定分治。选取基准分区递归排序通用性最强平均性能最好是很多语言内置排序的实现堆排序O(n log n)O(n log n)O(1)不稳定利用堆的性质进行选择排序对空间复杂度有要求且不需要稳定性的场景实操心得快速排序的优化。教科书上的快排选取第一个元素作为基准在数组有序时会导致最坏情况。工业级实现通常会做优化三数取中从子数组的首、中、尾元素中取中位数作为基准有效避免有序数组的退化。小区间改用插入排序当递归到的子数组规模很小如长度10时递归开销可能比排序本身还大此时切换为插入排序能提升整体性能。双路或三路快排应对大量重复元素的数组。经典快排在处理重复元素时效率低下双路快排从两端向中间扫描或三路快排将数组分为小于、等于、大于基准三部分能很好解决这个问题。4.2 非比较排序当元素有范围时当数据有特定限制时我们可以突破O(n log n)的比较排序下限。计数排序适用于数据范围k不大如0-100的分数的整数排序。创建一个长度为k的计数数组统计每个元素出现的次数然后依次输出。时间复杂度O(nk)。桶排序将数据分到有限数量的有序桶里每个桶内再单独排序通常用插入排序。适用于数据均匀分布的情况。基数排序从最低位到最高位依次对每一位进行稳定的排序通常用计数排序。适用于整数或字符串排序。时间复杂度O(d*(nk))d为最大位数。如何选择排序算法这是一个经典的面试问题。我的决策思路是数据规模小n 50插入排序。常数因子小且对于基本有序数据效率极高。通用场景追求平均性能快速排序。记得做好优化如三数取中。需要稳定性或排序链表归并排序。对内存使用敏感且不需要稳定性堆排序。数据是整数且范围已知且不大计数排序或基数排序。5. 从习题到实战经典题型解题框架与思维模板刷题不能只追求数量更要总结“题型”和“框架”。掌握一个框架往往能解决一类问题。这里分享几个我总结的、极其高频的解题思维模板。5.1 链表类问题快慢指针与虚拟头节点链表问题两大法宝快慢指针和虚拟头节点。快慢指针模板应用1寻找链表中点。慢指针每次走1步快指针每次走2步。当快指针走到末尾时慢指针正好在中点或中点前一个取决于链表长度奇偶和初始化。这是归并排序链表的基础。# 寻找链表中点偶数个节点时返回靠前的那个 def findMiddle(head): slow fast head while fast and fast.next and fast.next.next: # 注意循环条件 slow slow.next fast fast.next.next return slow应用2判断链表是否有环并找到环入口。快慢指针相遇说明有环。相遇后将其中一个指针移回链表头然后两个指针同速前进再次相遇点即为环入口。这是一个经典的数学推导结论。应用3寻找倒数第k个节点。让快指针先走k步然后快慢指针同步前进快指针到末尾时慢指针即为所求。虚拟头节点模板为什么要用简化对链表头节点可能发生变化的操作如删除头节点、在头节点前插入的处理逻辑避免繁琐的边界判断。def removeElements(head, val): dummy ListNode(0) # 创建一个虚拟头节点 dummy.next head curr dummy while curr.next: if curr.next.val val: curr.next curr.next.next # 删除操作 else: curr curr.next return dummy.next # 返回新的头节点5.2 二叉树类问题递归与迭代的思维转换二叉树问题十之八九离不开递归。写递归代码的关键是明确递归函数的定义。递归三要素框架定义这个函数要做什么输入什么返回什么例如maxDepth(root)返回以root为根的树的最大深度。基线条件递归的出口是什么例如if not root: return 0。递推关系如何从子问题的解得到原问题的解例如maxDepth(root) 1 max(maxDepth(root.left), maxDepth(root.right))。迭代遍历模板栈模拟 前序、中序、后序的迭代写法各有不同容易混淆。我推荐使用一种**“标记法”统一模板**将访问节点和处理节点分离。# 以前序遍历为例 def preorderTraversal(root): if not root: return [] stack [root] result [] while stack: node stack.pop() if node is not None: # 右左中的顺序入栈因为栈是LIFO所以出栈顺序是中左右前序 if node.right: stack.append(node.right) # 右 if node.left: stack.append(node.left) # 左 stack.append(node) # 中 stack.append(None) # 在中节点后加入一个空标记 else: # 遇到空标记说明下一个栈顶元素是需要处理的节点 node stack.pop() result.append(node.val) return result通过调整右、左、中的入栈顺序和标记位置可以统一实现三种遍历极大地减轻了记忆负担。5.3 回溯算法决策树的深度探索回溯是解决组合、排列、子集、切割等问题的利器。其本质是在一棵决策树上进行深度优先搜索。回溯法通用模板result [] # 存放结果集 path [] # 存放当前路径 def backtracking(选择列表, 其他参数...): if 满足结束条件: result.add(path的副本) # 注意添加副本而非引用 return for 选择 in 选择列表: 做选择将选择加入path backtracking(新的选择列表, 其他参数...) # 递归 撤销选择将选择从path移除关键点路径已经做出的选择。选择列表当前可以做的选择。结束条件到达决策树底层无法再做选择的条件。去重在求组合、子集时如果原集合有重复元素需要先排序然后在同一层遍历中使用if i start and nums[i] nums[i-1]: continue来跳过重复选择。5.4 动态规划状态定义与转移方程动态规划是面试中的难点但掌握套路后也能化繁为简。核心是“状态”和“转移”。解题四步法确定dp数组及下标的含义dp[i]或者dp[i][j]代表什么这是最关键也最容易出错的一步。确定递推公式状态转移方程如何从已知状态推导出未知状态例如dp[i] max(dp[i-1], dp[i-2] nums[i])。dp数组如何初始化根据dp数组的定义和递推公式确定初始值。例如dp[0]和dp[1]通常需要手动初始化。确定遍历顺序是正序、倒序还是先遍历背包再遍历物品这取决于递推公式的依赖关系。举例推导dp数组写代码前用手动计算一个小例子验证你的四步是否正确。这是避免低级错误的最佳方法。经典问题与状态定义爬楼梯dp[i]表示爬到第i阶楼梯的方法数。dp[i] dp[i-1] dp[i-2]。背包问题0/1背包dp[i][j]表示从前i个物品中选放入容量为j的背包的最大价值。优化后可用一维数组dp[j]并倒序遍历j。完全背包dp[j]表示容量为j的背包能装的最大价值。用一维数组时需正序遍历j。最长公共子序列dp[i][j]表示text1[0:i]和text2[0:j]的最长公共子序列长度。6. 学习资源、工具与持续精进建议有了好的习题集和解题框架还需要配合高效的学习工具和方法才能事半功倍。6.1 推荐学习资源与工具链可视化工具Data Structure Visualizations一个非常经典的在线网站可以动态演示各种数据结构操作和算法执行过程对建立直观理解帮助巨大。算法动画网站如 visualgo.net提供了大量排序、查找、图论算法的可视化。刷题平台LeetCode国际主流题目多社区活跃适合准备外企或国内大厂面试。建议按“题库 - 学习计划 - 热门企业题库”的顺序进行。牛客网国内主流有大量国内公司真题和面经更适合国内校招和社招。AcWing有非常系统的算法基础课和提高课题目分类清晰讲解详细适合系统学习。本地IDE与调试务必在本地环境如VS Code, IntelliJ IDEA, CLion等编写和调试代码。熟练使用断点、单步执行、变量监视等功能。理解程序运行的每一步状态变化比单纯看答案有效十倍。6.2 构建知识体系与应对面试制作自己的“知识脑图”使用XMind、MindMaster等工具以“数据结构”为中心向外辐射出线性结构、树形结构、图形结构、散列结构等分支每个分支再细化到具体实现、操作、复杂度、典型问题。定期回顾和更新这张图。模拟面试与白板编程找同学互相出题或者使用在线模拟面试功能。白板编程练习在纸上或白板上写代码锻炼在没有IDE提示和自动补全的情况下写出正确、整洁代码的能力。注意代码格式、变量命名、注释关键步骤。面试时的沟通技巧明确问题拿到题目后先和面试官确认输入、输出、边界条件、特殊要求时间/空间复杂度限制。阐述思路不要立刻写代码。先说出你的初步想法哪怕是暴力解法。然后逐步优化并解释每一步优化的原因“暴力法是O(n²)这里我们可以用哈希表将查找时间降到O(1)从而整体降到O(n)”。边写边讲写代码时同步解释你在写什么“这里初始化一个哈希表用来存储已经遍历过的值及其索引……”。测试用例写完代码后主动设计几个测试用例正常情况、边界情况、异常情况走一遍代码。学习数据结构与算法是一场持久战没有捷径。这份《习题集》和指南希望能为你提供一张清晰的地图和一套可靠的工具。真正的成长源于每一行自己敲出的代码每一次痛苦的调试和每一个苦思冥想后豁然开朗的瞬间。从今天起选择一道题打开你的编辑器开始行动吧。在反复的练习和总结中那些抽象的struct和pointer终将内化成你解决复杂问题时手中最锋利的武器。