简介C数据结构是一份面向C初学者的PDF学习资料聚焦数组与结构体的用法并辅以具体程序示例讲解函数与基本算法。文档从图书馆书籍管理场景切入演示如何用结构体封装书名、作者、类目和ID等不同类型数据让读者理解用户自定义数据类型在记录管理中的作用。资源包含1个PDF文件压缩包整体约35KB内容精炼便携适合快速查阅与代码对照。已有2021人学习下载。文档后半部分提供了一道求方程根的C完整程序涉及f()、xpoint()、root()等函数展示二分法迭代求根的思路以及do-while循环、精度控制等关键写法可帮助初学者将数据结构知识与实际编码结合起来为后续学习链表、树等复杂结构打下基础。1. 手里的C数据结构.pdf到底是什么一份能直接抄进编译器的代码底稿期末复习周或者408备考进入代码轮的时候很多人手里都有一份C数据结构.pdf。它不是教材也不是源码包而是一份把线性表、树、图、查找、排序这些知识点按C语法重排过的学习资料概念放前面算法代码给中间复杂度分析跟在后面。它的价值在于帮你少走弯路——C语言版的数据结构书写得再经典指针、结构体和C的类、模板、引用之间还是有道坎这份PDF正好把两者之间最常用的写法对齐了。适合两类人一类是正在啃严蔚敏但代码写不出来的初学者另一类是准备期末或408想把高频算法默写下来的备考党。这篇文章我按自己读这类资料的习惯把怎么拆、怎么写、怎么排错完整讲一遍。2. 一份C数据结构PDF该怎么拆先建立主线再逐章消化拿到一份PDF先别从头翻到尾那样看到第六章图就忘了第一章链表。数据结构这门课的主线非常固定线性结构线性表、栈、队列→ 非线性结构树、图→ 查找 → 排序。你手里的C数据结构.pdf大概率也是按这个顺序排的每章挑重点往下吃比“一页一页啃”快得多。我建议按下面四个模块切分每个模块对应一轮复习周期而不是按页码切。2.1 线性表、栈与队列C里先练这四个“肌肉记忆”线性表是数据结构的地基C里它可以拆成两种形态。顺序表对应C的 vector特征是按下标随机访问是 O(1)但插入删除要移动元素平均挪 n/2 个链表则由一个个 new 出来的节点组成特征是插入删除只改指针、查找要遍历。你在PDF这一章里最该盯住的是“节点定义”和“指针怎么走”而不是背代码本身。C的节点定义长这样struct ListNode { int val; ListNode* next; ListNode(int v) : val(v), next(nullptr) {} };这套写法把 C 语言版里的typedef struct和malloc全省略了构造函数自带初始化。练的时候我一般会拿一张纸画出“头结点→节点1→节点2”然后手动模拟每一步指针变化写出来才是自己的。栈和队列在C里虽然可以直接用 std::stack 和 std::queue但期末和408都要求会手写“数组模拟版”栈用一个数组加一个 top 下标队列用数组加 front 和 rear循环队列还要会算(rear 1) % maxSize判满。这几个结构在PDF里出现频率最高因为几乎所有后续算法都要依赖它们。2.2 树与图从递归遍历到邻接表PDF翻得最多的两章二叉树这部分PDF里最核心的代码其实就是三种递归遍历加起来不到十行。先序遍历是“访问根→左→右”中序是“左→根→右”后序是“左→右→根”。递归版本很好背但你要理解“访问”这件事发生在哪一行这决定了遍历顺序。层序遍历用队列做BFS的套路在这里第一次出现。二叉搜索树的插入和删除是这一章的难点删除要分三种情况叶子直接删、单子树用子树顶上、双子树用中序前驱或后继替换考试最爱在这里出填空。图这一章PDF通常给出邻接矩阵和邻接表两种存储。C里写邻接表非常顺用vectorint adj[N]或者vectorvectorint都可以比C语言版那堆结构体嵌套结构体好读多了。你真正需要动手的代码只有DFS和BFS两个框架DFS递归往下走BFS用队列逐层展开。408对图的代码题考得比树少但期末里“画出广度优先生成树”“写出深度优先遍历序列”这类题一定要会。2.3 查找与排序代码背哪版、期末与408常考哪版查找这一章顺序查找没有技术含量重点在折半查找的边界以及二叉排序树、哈希表的平均查找长度计算。408喜欢考“给定关键字序列构造哈希表并计算ASL”期末则爱考“折半查找判定树”。排序是整份PDF里表格最多的一章直接插入、冒泡、快排、堆排、归并这五个必须会手写另外还要背下一张表时间复杂度、空间复杂度、稳定性每个算法一行。这里有个容易被坑的地方PDF里的排序算法版本未必是考试要的版本。拿快排举例严蔚敏版教材用的是“挖坑法枢轴元素暂存”有的PDF则写“左右交换指针法”两种都能排对但如果你照着交换版默写碰上408那种“写出第一趟排序结果”的题序列和答案会对不上。我建议你以PDF里和考纲一致的那个版本为准把一趟排序的中间序列亲手推一遍推不出来说明还没真懂。2.4 把“必背代码”改成自己的注释再默写这一节的目的是把PDF里的代码真正变成你的。常见做法是五步走先原样抄进编译器跑通再给每一步加中文注释然后合上PDF只看注释补代码接着关掉所有参考盲写最后和PDF原版对比差异。我一般会在注释里先写“这一步在干什么、指针现在指向谁、循环结束时谁可能变成nullptr”因为这些就是考试时最容易出错的地方。很多人写数据结构实验报告直接把PDF里的代码复制粘贴进Word既没编译过也没运行过重复率还高。正确做法是哪怕只改一个变量名也先把代码敲进VSCode跑一遍再截图贴报告里。面试场景也是一样的逻辑C八股里“手写单链表反转”出现频率极高那题其实就是对“pre、cur、next三个指针怎么换班”的肌肉记忆和链表插入删除是同一套功夫。3. 把PDF里的算法变成能跑的C代码四个可以直接复现的例程阅读PDF和动手写代码是两回事这一章我给出四个高频考点例程全部是C17可编译的最小实现。先把VSCode配好C/C环境或者直接用Dev C能编译能调试就行然后把这四个例程单独放进工程跑一遍。每个例程后面我都会说明参数和边界这部分是你抄完代码之后最值得停下来的地方。3.1 单链表按位置插入先把指针练稳单链表插入是数据结构链表章节的祖宗题408代码题里衍生的“反转链表”“删除重复节点”都建立在它之上。下面的实现带头结点从头结点的前驱位置开始找所以位置1和位置len1都能正确处理。#include iostream struct ListNode { int val; ListNode* next; ListNode(int v) : val(v), next(nullptr) {} }; bool insertAt(ListNode* head, int pos, int value) { if (pos 1) return false; // 位序从 1 开始计数 ListNode dummy(0); // 哨兵节点统一头插和中间插入的逻辑 dummy.next head; ListNode* cur dummy; for (int i 1; i pos cur ! nullptr; i) { cur cur-next; // 让 cur 停在待插入位置的前一个节点 } if (cur nullptr) return false; // pos 超过 len 1 时越界 ListNode* newNode new ListNode(value); newNode-next cur-next; cur-next newNode; head dummy.next; // 头插时同步更新外部 head return true; }逻辑说明循环用i pos控制步数当 pos 等于链表长度加1时cur 会正好停在尾节点上此时插入相当于尾插只有 pos 比 len1 还大时 cur 才会变成 nullptr返回 false。这比“先判断 pos 合法再找到第 pos-1 个节点”的老写法更稳。参数说明ListNode* head是引用传参解决的是头插时 head 需要被更新的问题如果只传ListNode* head在函数里改 head 不会影响外部变量。new 出来的节点不用手动初始化 next构造函数已经替你做完了。面试里你把这个版本写出来再答清“为什么用引用传参”这道题基本就拿下了。3.2 二叉树中序非递归遍历栈模拟递归是高频考点递归中序是三行的事但408和面试都爱考非递归版因为它强迫你理解“系统栈里到底存了什么”。非递归中序的核心是一路往左压栈弹出来访问再转向右子树。#include iostream #include stack struct TreeNode { int val; TreeNode *left, *right; TreeNode(int v) : val(v), left(nullptr), right(nullptr) {} }; void inorder(TreeNode* root) { std::stackTreeNode* st; TreeNode* cur root; while (cur ! nullptr || !st.empty()) { while (cur ! nullptr) { // 把当前节点的整条左链压栈 st.push(cur); cur cur-left; } cur st.top(); st.pop(); std::cout cur-val ; // 出栈时访问这就是中序的位置 cur cur-right; // 转向右子树下一轮继续压它的左链 } }逻辑说明外层循环的条件是“当前节点非空或栈非空”两者都为空说明整棵树遍历完。内层循环把左子树全部入栈出栈时访问节点然后立即转向右子树。如果你把访问语句移到第一次遇到节点时内层 while 之前就是先序非递归移到左右子树都处理完之后就是后序但后序需要额外记录上一次访问的节点。参数说明这里传的是TreeNode* root按值传指针即可因为遍历不需要修改树的结构。调试时可以把 st 当作黑匣子盯住打印每一步栈顶就能直观看到“栈模拟递归”的真面目。3.3 折半查找的边界写对int mid low (high - low) / 2折半查找看着简单实际上是最容易翻车的二分边界题。下面这个版本适用于“非递减有序数组”查找成功返回下标失败返回 -1。#include vector int binarySearch(const std::vectorint arr, int target) { int low 0, high static_castint(arr.size()) - 1; while (low high) { int mid low (high - low) / 2; // 防止 low high 直接相加溢出 if (arr[mid] target) return mid; else if (arr[mid] target) low mid 1; // 目标在右半区 else high mid - 1; // 目标在左半区 } return -1; }三个必答的边界问题第一为什么mid low (high - low) / 2而不是(low high) / 2因为后者在 low 和 high 逼近 int 上限时会溢出写成减法形式可以把这个风险消掉。第二为什么循环条件是low high而不是low high因为等于的情况意味着搜索区间里还有一个元素这个元素有可能是 target漏掉它就可能在数组只有一个元素时直接返回 -1。第三为什么更新是low mid 1和high mid - 1因为 mid 已经比较过了下一轮搜索区间必须排除它否则当 low 和 high 相邻时会出现死循环。408的填空题经常考这三处期末卷子也爱在这设陷阱。3.4 冒泡排序的双重优化从教科书版到能过OJ版教科书版的冒泡排序是两层 for 无脑交换但真正能过OJ和期末上机的是优化后的版本。优化点有两个一是记录本轮是否发生交换没交换说明序列已有序直接结束二是每轮结束后上一轮最后交换的位置之后的元素已经是最终位置不必再比较。#include vector #include algorithm void bubbleSort(std::vectorint a) { int n static_castint(a.size()); for (int i 0; i n - 1; i) { bool swapped false; // 本轮是否交换过 for (int j 0; j n - 1 - i; j) { // 每轮比较区间右端收缩 if (a[j] a[j 1]) { std::swap(a[j], a[j 1]); swapped true; } } if (!swapped) break; // 本轮无交换序列已有序 } }逻辑说明外层 i 控制已经排好序的尾部长度内层 j 只在[0, n-1-i)区间比较。swapped是这版代码的灵魂最好情况下数组本身有序第一轮扫描结束无交换直接跳出复杂度降为 O(n)。参数说明传引用std::vectorint a避免整个vector拷贝如果只想看排序过程可以在内层循环里加一行打印输出每一轮的中间序列这是排查排序错误最直接的手段。408的填空题偶尔会在break那行设空让你填“不需要再继续排序”的条件答!swapped或flag false都对。4. C实现数据结构的选型理由和严蔚敏C语言版的差别在哪很多人在PDF之外还下载过严蔚敏《数据结构》C语言版 pdf两本对照着看就会发现同一个算法两套写法。到底以哪个为准我的答案是思路看C语言版落代码用C版。这一章把关键差别讲透你就能明白为什么标题里的“C”不是噱头。4.1 为什么数据结构资料要多看C版而不是C语言版严蔚敏C语言版是经典教材但作为“能直接抄进编译器的参考底稿”它有一个绕不开的问题里面大量使用typedef struct、二级指针、malloc/free、函数指针这些写法在C工程里既不安全也不直观。比如链表初始化C语言版需要InitList(LinkList* L)然后再 malloc而C版一个构造函数全搞定。408的代码题只考算法思想语言是载体可你用C语言写就要多处理很多和算法无关的内存细节平白增加出错概率。C版把 struct 改成带构造函数的类把二级指针改成引用传参把 malloc 改成 new代码行数缩短三分之一读起来更接近你将来在工作中写的代码。学数据结构的意义是理解“数组、链表、树这些结构到底是怎么在内存里组织起来的”而这套理解用C表达比用C语言表达障碍更少。4.2 模板、引用传参和new/deleteC写数据结构必改的三个写法从C语言版对照到C版我总结出三个必改动作。第一个是typedef int ElemType换成模板PDF里常见的顺序表定义会变成templatetypename T class SeqList这样同一个类可以存 int、double、自定义结构体复习时不用为每种类型复制一份代码面试时答“模板的编译期实例化”也是加分点。第二个是链表头插、删除这类操作C语言版传LinkList* L调用时写成InsertList(L, ...)C版直接bool insertAt(ListNode* head, ...)原因在3.1里已经说过引用传参让函数内部可以直接改写外部指针本身省去一级间接。第三个是malloc/free换成new/deletenew 会自动调用构造函数delete 会自动调用析构函数还记得前面链表节点定义里的ListNode(int v) : val(v), next(nullptr) {}吗这行构造函数只有 new 会触发malloc 不会。另外还有一个容易被忽略的细节只读的遍历函数参数要写成const ListNode* head或const std::vectorint a。加上 const 之后函数体内误改指针指向的内容时编译器直接报错相当于给代码上了一道保险。C里 const 的用法在PDF的类和对象章节通常有一小段但真正用起来是在写这些数据结构操作函数的时候。4.3 STL容器能替代手写数据结构吗笔试与工程的分界线先说工程结论日常业务代码里能 STL 就用 STLvector、map、unordered_map、stack、queue 完全够用自己手写链表维护成本太高还容易内存泄漏。但考试、面试、上机是另一套规则408的代码题和企业的白板题考的就是“不给你STL你能不能从节点开始把结构搭出来”。这条分界线其实就在你脑子里用 STL 是在调用别人封装好的黑匣子手写是在拆开黑匣子看里面的实现。刷完了PDF里的链表章节你应该能不看任何参考写出单链表反转和按值删除节点刷完树章节能写出层序遍历和二叉搜索树的插入。这些能力在STL里根本用不上但它是面试官判断“你是真会还是只会调包”的试金石。真正到工作中遇到性能热点需要自研容器时这些代码又会回来找你。5. 数据结构代码常见问题排查五个让我Debug到深夜的坑代码写进编译器只是第一步跑挂才是常态。下面五个坑我都在写数据结构实验和对外封装代码时踩过前四个是纯C数据结构代码自身的常见问题最后一个是把C代码编成DLL后更高频的崩溃场景每一段按“现象→原因→解决”的顺序写。5.1 空指针崩溃Segmentation fault 和 Access Violation现象程序编译通过运行到一半突然退出Linux下打印Segmentation faultWindows下弹出“访问冲突”或直接闪退用GDB或VSCode调试时定位到某一行解引用操作。原因最常见的是访问了空指针的成员。典型代码长这样遍历链表时while (p ! nullptr) { cout p-val; p p-next; }漏写了判空条件或者p-next本身是 nullptr 后继续p p-next-next。树的递归里也常见递归出口没判root nullptr到空节点还访问root-left。解决在每个解引用前先判空更重要的是养成“画图再写代码”的习惯。我一般会在出问题的那行前面加一行打印输出当前指针的地址和值看到地址是 0x0 就知道是谁的锅。Windows下如果遇到Access Violation (0xC0000005)先检查是不是这个原因再往越界方向查。5.2 析构函数触发 double free浅拷贝埋的雷现象程序功能正常但退出时输出double free detected或者报heap corruption有的不崩只是内存越界越来越严重。原因C默认的拷贝构造函数是浅拷贝。你把一个链表对象赋值给另一个对象两个对象的 head 指针指向同一块内存析构时两个对象各自 delete 一遍同一块地址就 double free 了。这是C语言版不太容易遇到的坑因为C语言里一切都要手动管理反而不存在编译器偷偷生成的拷贝。解决如果一个类管理了用 new 分配的资源就要遵守三件套原则Rule of Three自定义析构函数、拷贝构造函数、拷贝赋值运算符。拷贝构造里深度复制所有节点而不是只复制头指针。如果偷懒不想写就把拷贝构造函数和赋值运算符声明为 delete强制禁止拷贝。调试时可以用valgrind或 Windows 下的 CRT 内存检测工具报错位置会直接指向第二次 delete 的那行。5.3 递归遍历栈溢出树的高度葬送了递归现象测试小树时一切正常换成高度上万的二叉树或退化成链表的二叉搜索树后程序崩了Windows下常见错误码0xC00000FD对应“栈溢出”。原因递归调用深度等于树的高度每次递归都要把当前函数栈帧压进调用栈。二叉树如果插入顺序有序比如依次插入 1,2,3,...,100000树高就是100000递归版中序遍历会压100000层栈帧把默认的栈空间耗尽。解决把递归遍历改成非递归版本用自己定义的 std::stack 模拟调用栈详见3.2。stack 的数据在堆上100000层也没问题。如果一定要用递归也可以增大线程栈大小但考试和面试的标准答案是“非递归更稳”。排查的时候别急着怀疑编译选项先打印树的高度基本一眼就能确认是不是这个问题。5.4 排序结果差一位循环边界和等号的幽灵现象冒泡或直接插入排序后数组首尾元素错位比如最小值没排到最前面或者数组最后面多了一个旧值。原因边界写错。要么内层循环多写一次导致访问a[j 1]越界要么少写一次导致最后一个元素没参与比较最常见的是把j n - 1 - i写成j n - 1 - i。解决把数组规模缩到 3 个元素的小用例排序后打印每一轮结果肉眼立刻能看出哪一轮开始错。还有一招是构造固定答案对比用手推的正确答案放进 vector和你的排序结果逐位比较。后面第六章要讲的随机测试法就是把“手推”升级成“生成大量随机数据自动比对”这是最省时间的做法。5.5 在Windows下把C代码编成DLL运行库和Access Violation的排查思路现象把C写好的排序算法封装成DLL用C#调用一运行就报Access Violation (C0000005)。另一种更隐蔽的现象是在开发机器上跑得好好的换一台干净的机器exe 双击没反应或提示缺少VCRUNTIME140.dll。原因前者通常是C侧访问了无效内存——比如导出函数参数里传了空指针、越界访问数组或者返回了局部对象的引用/指针也有可能是C#的 P/Invoke 签名和C导出函数不一致调用约定和参数类型没对上。后者是目标机器缺运行库C 编译出的程序依赖 Microsoft Visual C Redistributable没装就会在启动阶段直接失败。解决缺运行库就装对应版本的“Microsoft Visual C Redistributable”注意x64和x86要跟编译目标一致装错版本照样闪退。遇到C0000005先在C侧查内存访问这是根源再核对C#侧声明确认DllImport的参数类型、CallingConvention和C端完全一致。我之前遇到一次报这个错最后定位到是导出函数里vector局部变量出了作用域后被外部继续引用属于C侧的内存生命周期问题C#侧无从解决只能回C改代码。6. 用随机数生成器验证你的数据结构实现一个稳定的自测套路6.1 用mt19937生成测试数据把排序和查找“压一遍”代码跑通了怎么知道它真的对我的习惯是不用手推的那三五组数据而是让随机数生成器替我说话。C里rand()的随机质量差、范围小直接用std::mt19937配合std::uniform_int_distribution分布均匀且可复现正是数据结构自测需要的。#include random #include vector #include algorithm #include iostream std::mt19937 rng(std::random_device{}()); std::uniform_int_distributionint dist(-1000, 1000); std::vectorint test(1000); for (int x : test) { x dist(rng); } std::vectorint expect test; std::sort(expect.begin(), expect.end()); bubbleSort(test); if (test expect) { std::cout sorted correctly std::endl; } else { std::cout mismatch found std::endl; }逻辑说明先用同样的数据生成一个 test 和一个 expectexpect 交给std::sort保证正确再用你写的bubbleSort处理 test最后直接比较两个 vector。一跑就是一千个随机用例比你手推几十个数覆盖面大得多。参数说明uniform_int_distributionint dist(-1000, 1000)的范围可以调成包含负数和零的区间这样能测出负数排序和重复元素的边界改成uniform_int_distributionlong long可以扩大数值范围但注意排序比较逻辑不要溢出。折半查找也用同样的套路生成有序随机数组随机挑 100 个 target调用你的binarySearch每返回一个下标就用arr[mid] target校验一次再挑 100 个肯定不存在的数确认全部返回 -1。链表就构造空链表、单节点、头插、尾插、中间插入、删除头结点这些用例每种场景单独跑一遍。树的话随机插入 N 个整数最后中序遍历输出检查是否严格升序这是验证二叉搜索树插入逻辑最快的方法。这套自测跑完代码基本可以拿去交实验报告或者进面试写白板了。我后来每次学完PDF里的一节都会先写这个“随机对照测试”跑不过就停手往回翻那一节的代码重新理解不往下看新内容。这个习惯帮我少调了很多后半夜的bug也让我不再一碰到排序、查找这类题就从原理问到自己心虚。数据结构这东西代码不是看会的是跑会的。希望这篇笔记能帮你在拿到一份C数据结构.pdf之后快速把它变成自己手底下真能跑的代码。本文还有配套的精品资源点击获取 C++数据结构PDF实战：从链表二叉树到排序查找的代码实现与自测
简介C数据结构是一份面向C初学者的PDF学习资料聚焦数组与结构体的用法并辅以具体程序示例讲解函数与基本算法。文档从图书馆书籍管理场景切入演示如何用结构体封装书名、作者、类目和ID等不同类型数据让读者理解用户自定义数据类型在记录管理中的作用。资源包含1个PDF文件压缩包整体约35KB内容精炼便携适合快速查阅与代码对照。已有2021人学习下载。文档后半部分提供了一道求方程根的C完整程序涉及f()、xpoint()、root()等函数展示二分法迭代求根的思路以及do-while循环、精度控制等关键写法可帮助初学者将数据结构知识与实际编码结合起来为后续学习链表、树等复杂结构打下基础。1. 手里的C数据结构.pdf到底是什么一份能直接抄进编译器的代码底稿期末复习周或者408备考进入代码轮的时候很多人手里都有一份C数据结构.pdf。它不是教材也不是源码包而是一份把线性表、树、图、查找、排序这些知识点按C语法重排过的学习资料概念放前面算法代码给中间复杂度分析跟在后面。它的价值在于帮你少走弯路——C语言版的数据结构书写得再经典指针、结构体和C的类、模板、引用之间还是有道坎这份PDF正好把两者之间最常用的写法对齐了。适合两类人一类是正在啃严蔚敏但代码写不出来的初学者另一类是准备期末或408想把高频算法默写下来的备考党。这篇文章我按自己读这类资料的习惯把怎么拆、怎么写、怎么排错完整讲一遍。2. 一份C数据结构PDF该怎么拆先建立主线再逐章消化拿到一份PDF先别从头翻到尾那样看到第六章图就忘了第一章链表。数据结构这门课的主线非常固定线性结构线性表、栈、队列→ 非线性结构树、图→ 查找 → 排序。你手里的C数据结构.pdf大概率也是按这个顺序排的每章挑重点往下吃比“一页一页啃”快得多。我建议按下面四个模块切分每个模块对应一轮复习周期而不是按页码切。2.1 线性表、栈与队列C里先练这四个“肌肉记忆”线性表是数据结构的地基C里它可以拆成两种形态。顺序表对应C的 vector特征是按下标随机访问是 O(1)但插入删除要移动元素平均挪 n/2 个链表则由一个个 new 出来的节点组成特征是插入删除只改指针、查找要遍历。你在PDF这一章里最该盯住的是“节点定义”和“指针怎么走”而不是背代码本身。C的节点定义长这样struct ListNode { int val; ListNode* next; ListNode(int v) : val(v), next(nullptr) {} };这套写法把 C 语言版里的typedef struct和malloc全省略了构造函数自带初始化。练的时候我一般会拿一张纸画出“头结点→节点1→节点2”然后手动模拟每一步指针变化写出来才是自己的。栈和队列在C里虽然可以直接用 std::stack 和 std::queue但期末和408都要求会手写“数组模拟版”栈用一个数组加一个 top 下标队列用数组加 front 和 rear循环队列还要会算(rear 1) % maxSize判满。这几个结构在PDF里出现频率最高因为几乎所有后续算法都要依赖它们。2.2 树与图从递归遍历到邻接表PDF翻得最多的两章二叉树这部分PDF里最核心的代码其实就是三种递归遍历加起来不到十行。先序遍历是“访问根→左→右”中序是“左→根→右”后序是“左→右→根”。递归版本很好背但你要理解“访问”这件事发生在哪一行这决定了遍历顺序。层序遍历用队列做BFS的套路在这里第一次出现。二叉搜索树的插入和删除是这一章的难点删除要分三种情况叶子直接删、单子树用子树顶上、双子树用中序前驱或后继替换考试最爱在这里出填空。图这一章PDF通常给出邻接矩阵和邻接表两种存储。C里写邻接表非常顺用vectorint adj[N]或者vectorvectorint都可以比C语言版那堆结构体嵌套结构体好读多了。你真正需要动手的代码只有DFS和BFS两个框架DFS递归往下走BFS用队列逐层展开。408对图的代码题考得比树少但期末里“画出广度优先生成树”“写出深度优先遍历序列”这类题一定要会。2.3 查找与排序代码背哪版、期末与408常考哪版查找这一章顺序查找没有技术含量重点在折半查找的边界以及二叉排序树、哈希表的平均查找长度计算。408喜欢考“给定关键字序列构造哈希表并计算ASL”期末则爱考“折半查找判定树”。排序是整份PDF里表格最多的一章直接插入、冒泡、快排、堆排、归并这五个必须会手写另外还要背下一张表时间复杂度、空间复杂度、稳定性每个算法一行。这里有个容易被坑的地方PDF里的排序算法版本未必是考试要的版本。拿快排举例严蔚敏版教材用的是“挖坑法枢轴元素暂存”有的PDF则写“左右交换指针法”两种都能排对但如果你照着交换版默写碰上408那种“写出第一趟排序结果”的题序列和答案会对不上。我建议你以PDF里和考纲一致的那个版本为准把一趟排序的中间序列亲手推一遍推不出来说明还没真懂。2.4 把“必背代码”改成自己的注释再默写这一节的目的是把PDF里的代码真正变成你的。常见做法是五步走先原样抄进编译器跑通再给每一步加中文注释然后合上PDF只看注释补代码接着关掉所有参考盲写最后和PDF原版对比差异。我一般会在注释里先写“这一步在干什么、指针现在指向谁、循环结束时谁可能变成nullptr”因为这些就是考试时最容易出错的地方。很多人写数据结构实验报告直接把PDF里的代码复制粘贴进Word既没编译过也没运行过重复率还高。正确做法是哪怕只改一个变量名也先把代码敲进VSCode跑一遍再截图贴报告里。面试场景也是一样的逻辑C八股里“手写单链表反转”出现频率极高那题其实就是对“pre、cur、next三个指针怎么换班”的肌肉记忆和链表插入删除是同一套功夫。3. 把PDF里的算法变成能跑的C代码四个可以直接复现的例程阅读PDF和动手写代码是两回事这一章我给出四个高频考点例程全部是C17可编译的最小实现。先把VSCode配好C/C环境或者直接用Dev C能编译能调试就行然后把这四个例程单独放进工程跑一遍。每个例程后面我都会说明参数和边界这部分是你抄完代码之后最值得停下来的地方。3.1 单链表按位置插入先把指针练稳单链表插入是数据结构链表章节的祖宗题408代码题里衍生的“反转链表”“删除重复节点”都建立在它之上。下面的实现带头结点从头结点的前驱位置开始找所以位置1和位置len1都能正确处理。#include iostream struct ListNode { int val; ListNode* next; ListNode(int v) : val(v), next(nullptr) {} }; bool insertAt(ListNode* head, int pos, int value) { if (pos 1) return false; // 位序从 1 开始计数 ListNode dummy(0); // 哨兵节点统一头插和中间插入的逻辑 dummy.next head; ListNode* cur dummy; for (int i 1; i pos cur ! nullptr; i) { cur cur-next; // 让 cur 停在待插入位置的前一个节点 } if (cur nullptr) return false; // pos 超过 len 1 时越界 ListNode* newNode new ListNode(value); newNode-next cur-next; cur-next newNode; head dummy.next; // 头插时同步更新外部 head return true; }逻辑说明循环用i pos控制步数当 pos 等于链表长度加1时cur 会正好停在尾节点上此时插入相当于尾插只有 pos 比 len1 还大时 cur 才会变成 nullptr返回 false。这比“先判断 pos 合法再找到第 pos-1 个节点”的老写法更稳。参数说明ListNode* head是引用传参解决的是头插时 head 需要被更新的问题如果只传ListNode* head在函数里改 head 不会影响外部变量。new 出来的节点不用手动初始化 next构造函数已经替你做完了。面试里你把这个版本写出来再答清“为什么用引用传参”这道题基本就拿下了。3.2 二叉树中序非递归遍历栈模拟递归是高频考点递归中序是三行的事但408和面试都爱考非递归版因为它强迫你理解“系统栈里到底存了什么”。非递归中序的核心是一路往左压栈弹出来访问再转向右子树。#include iostream #include stack struct TreeNode { int val; TreeNode *left, *right; TreeNode(int v) : val(v), left(nullptr), right(nullptr) {} }; void inorder(TreeNode* root) { std::stackTreeNode* st; TreeNode* cur root; while (cur ! nullptr || !st.empty()) { while (cur ! nullptr) { // 把当前节点的整条左链压栈 st.push(cur); cur cur-left; } cur st.top(); st.pop(); std::cout cur-val ; // 出栈时访问这就是中序的位置 cur cur-right; // 转向右子树下一轮继续压它的左链 } }逻辑说明外层循环的条件是“当前节点非空或栈非空”两者都为空说明整棵树遍历完。内层循环把左子树全部入栈出栈时访问节点然后立即转向右子树。如果你把访问语句移到第一次遇到节点时内层 while 之前就是先序非递归移到左右子树都处理完之后就是后序但后序需要额外记录上一次访问的节点。参数说明这里传的是TreeNode* root按值传指针即可因为遍历不需要修改树的结构。调试时可以把 st 当作黑匣子盯住打印每一步栈顶就能直观看到“栈模拟递归”的真面目。3.3 折半查找的边界写对int mid low (high - low) / 2折半查找看着简单实际上是最容易翻车的二分边界题。下面这个版本适用于“非递减有序数组”查找成功返回下标失败返回 -1。#include vector int binarySearch(const std::vectorint arr, int target) { int low 0, high static_castint(arr.size()) - 1; while (low high) { int mid low (high - low) / 2; // 防止 low high 直接相加溢出 if (arr[mid] target) return mid; else if (arr[mid] target) low mid 1; // 目标在右半区 else high mid - 1; // 目标在左半区 } return -1; }三个必答的边界问题第一为什么mid low (high - low) / 2而不是(low high) / 2因为后者在 low 和 high 逼近 int 上限时会溢出写成减法形式可以把这个风险消掉。第二为什么循环条件是low high而不是low high因为等于的情况意味着搜索区间里还有一个元素这个元素有可能是 target漏掉它就可能在数组只有一个元素时直接返回 -1。第三为什么更新是low mid 1和high mid - 1因为 mid 已经比较过了下一轮搜索区间必须排除它否则当 low 和 high 相邻时会出现死循环。408的填空题经常考这三处期末卷子也爱在这设陷阱。3.4 冒泡排序的双重优化从教科书版到能过OJ版教科书版的冒泡排序是两层 for 无脑交换但真正能过OJ和期末上机的是优化后的版本。优化点有两个一是记录本轮是否发生交换没交换说明序列已有序直接结束二是每轮结束后上一轮最后交换的位置之后的元素已经是最终位置不必再比较。#include vector #include algorithm void bubbleSort(std::vectorint a) { int n static_castint(a.size()); for (int i 0; i n - 1; i) { bool swapped false; // 本轮是否交换过 for (int j 0; j n - 1 - i; j) { // 每轮比较区间右端收缩 if (a[j] a[j 1]) { std::swap(a[j], a[j 1]); swapped true; } } if (!swapped) break; // 本轮无交换序列已有序 } }逻辑说明外层 i 控制已经排好序的尾部长度内层 j 只在[0, n-1-i)区间比较。swapped是这版代码的灵魂最好情况下数组本身有序第一轮扫描结束无交换直接跳出复杂度降为 O(n)。参数说明传引用std::vectorint a避免整个vector拷贝如果只想看排序过程可以在内层循环里加一行打印输出每一轮的中间序列这是排查排序错误最直接的手段。408的填空题偶尔会在break那行设空让你填“不需要再继续排序”的条件答!swapped或flag false都对。4. C实现数据结构的选型理由和严蔚敏C语言版的差别在哪很多人在PDF之外还下载过严蔚敏《数据结构》C语言版 pdf两本对照着看就会发现同一个算法两套写法。到底以哪个为准我的答案是思路看C语言版落代码用C版。这一章把关键差别讲透你就能明白为什么标题里的“C”不是噱头。4.1 为什么数据结构资料要多看C版而不是C语言版严蔚敏C语言版是经典教材但作为“能直接抄进编译器的参考底稿”它有一个绕不开的问题里面大量使用typedef struct、二级指针、malloc/free、函数指针这些写法在C工程里既不安全也不直观。比如链表初始化C语言版需要InitList(LinkList* L)然后再 malloc而C版一个构造函数全搞定。408的代码题只考算法思想语言是载体可你用C语言写就要多处理很多和算法无关的内存细节平白增加出错概率。C版把 struct 改成带构造函数的类把二级指针改成引用传参把 malloc 改成 new代码行数缩短三分之一读起来更接近你将来在工作中写的代码。学数据结构的意义是理解“数组、链表、树这些结构到底是怎么在内存里组织起来的”而这套理解用C表达比用C语言表达障碍更少。4.2 模板、引用传参和new/deleteC写数据结构必改的三个写法从C语言版对照到C版我总结出三个必改动作。第一个是typedef int ElemType换成模板PDF里常见的顺序表定义会变成templatetypename T class SeqList这样同一个类可以存 int、double、自定义结构体复习时不用为每种类型复制一份代码面试时答“模板的编译期实例化”也是加分点。第二个是链表头插、删除这类操作C语言版传LinkList* L调用时写成InsertList(L, ...)C版直接bool insertAt(ListNode* head, ...)原因在3.1里已经说过引用传参让函数内部可以直接改写外部指针本身省去一级间接。第三个是malloc/free换成new/deletenew 会自动调用构造函数delete 会自动调用析构函数还记得前面链表节点定义里的ListNode(int v) : val(v), next(nullptr) {}吗这行构造函数只有 new 会触发malloc 不会。另外还有一个容易被忽略的细节只读的遍历函数参数要写成const ListNode* head或const std::vectorint a。加上 const 之后函数体内误改指针指向的内容时编译器直接报错相当于给代码上了一道保险。C里 const 的用法在PDF的类和对象章节通常有一小段但真正用起来是在写这些数据结构操作函数的时候。4.3 STL容器能替代手写数据结构吗笔试与工程的分界线先说工程结论日常业务代码里能 STL 就用 STLvector、map、unordered_map、stack、queue 完全够用自己手写链表维护成本太高还容易内存泄漏。但考试、面试、上机是另一套规则408的代码题和企业的白板题考的就是“不给你STL你能不能从节点开始把结构搭出来”。这条分界线其实就在你脑子里用 STL 是在调用别人封装好的黑匣子手写是在拆开黑匣子看里面的实现。刷完了PDF里的链表章节你应该能不看任何参考写出单链表反转和按值删除节点刷完树章节能写出层序遍历和二叉搜索树的插入。这些能力在STL里根本用不上但它是面试官判断“你是真会还是只会调包”的试金石。真正到工作中遇到性能热点需要自研容器时这些代码又会回来找你。5. 数据结构代码常见问题排查五个让我Debug到深夜的坑代码写进编译器只是第一步跑挂才是常态。下面五个坑我都在写数据结构实验和对外封装代码时踩过前四个是纯C数据结构代码自身的常见问题最后一个是把C代码编成DLL后更高频的崩溃场景每一段按“现象→原因→解决”的顺序写。5.1 空指针崩溃Segmentation fault 和 Access Violation现象程序编译通过运行到一半突然退出Linux下打印Segmentation faultWindows下弹出“访问冲突”或直接闪退用GDB或VSCode调试时定位到某一行解引用操作。原因最常见的是访问了空指针的成员。典型代码长这样遍历链表时while (p ! nullptr) { cout p-val; p p-next; }漏写了判空条件或者p-next本身是 nullptr 后继续p p-next-next。树的递归里也常见递归出口没判root nullptr到空节点还访问root-left。解决在每个解引用前先判空更重要的是养成“画图再写代码”的习惯。我一般会在出问题的那行前面加一行打印输出当前指针的地址和值看到地址是 0x0 就知道是谁的锅。Windows下如果遇到Access Violation (0xC0000005)先检查是不是这个原因再往越界方向查。5.2 析构函数触发 double free浅拷贝埋的雷现象程序功能正常但退出时输出double free detected或者报heap corruption有的不崩只是内存越界越来越严重。原因C默认的拷贝构造函数是浅拷贝。你把一个链表对象赋值给另一个对象两个对象的 head 指针指向同一块内存析构时两个对象各自 delete 一遍同一块地址就 double free 了。这是C语言版不太容易遇到的坑因为C语言里一切都要手动管理反而不存在编译器偷偷生成的拷贝。解决如果一个类管理了用 new 分配的资源就要遵守三件套原则Rule of Three自定义析构函数、拷贝构造函数、拷贝赋值运算符。拷贝构造里深度复制所有节点而不是只复制头指针。如果偷懒不想写就把拷贝构造函数和赋值运算符声明为 delete强制禁止拷贝。调试时可以用valgrind或 Windows 下的 CRT 内存检测工具报错位置会直接指向第二次 delete 的那行。5.3 递归遍历栈溢出树的高度葬送了递归现象测试小树时一切正常换成高度上万的二叉树或退化成链表的二叉搜索树后程序崩了Windows下常见错误码0xC00000FD对应“栈溢出”。原因递归调用深度等于树的高度每次递归都要把当前函数栈帧压进调用栈。二叉树如果插入顺序有序比如依次插入 1,2,3,...,100000树高就是100000递归版中序遍历会压100000层栈帧把默认的栈空间耗尽。解决把递归遍历改成非递归版本用自己定义的 std::stack 模拟调用栈详见3.2。stack 的数据在堆上100000层也没问题。如果一定要用递归也可以增大线程栈大小但考试和面试的标准答案是“非递归更稳”。排查的时候别急着怀疑编译选项先打印树的高度基本一眼就能确认是不是这个问题。5.4 排序结果差一位循环边界和等号的幽灵现象冒泡或直接插入排序后数组首尾元素错位比如最小值没排到最前面或者数组最后面多了一个旧值。原因边界写错。要么内层循环多写一次导致访问a[j 1]越界要么少写一次导致最后一个元素没参与比较最常见的是把j n - 1 - i写成j n - 1 - i。解决把数组规模缩到 3 个元素的小用例排序后打印每一轮结果肉眼立刻能看出哪一轮开始错。还有一招是构造固定答案对比用手推的正确答案放进 vector和你的排序结果逐位比较。后面第六章要讲的随机测试法就是把“手推”升级成“生成大量随机数据自动比对”这是最省时间的做法。5.5 在Windows下把C代码编成DLL运行库和Access Violation的排查思路现象把C写好的排序算法封装成DLL用C#调用一运行就报Access Violation (C0000005)。另一种更隐蔽的现象是在开发机器上跑得好好的换一台干净的机器exe 双击没反应或提示缺少VCRUNTIME140.dll。原因前者通常是C侧访问了无效内存——比如导出函数参数里传了空指针、越界访问数组或者返回了局部对象的引用/指针也有可能是C#的 P/Invoke 签名和C导出函数不一致调用约定和参数类型没对上。后者是目标机器缺运行库C 编译出的程序依赖 Microsoft Visual C Redistributable没装就会在启动阶段直接失败。解决缺运行库就装对应版本的“Microsoft Visual C Redistributable”注意x64和x86要跟编译目标一致装错版本照样闪退。遇到C0000005先在C侧查内存访问这是根源再核对C#侧声明确认DllImport的参数类型、CallingConvention和C端完全一致。我之前遇到一次报这个错最后定位到是导出函数里vector局部变量出了作用域后被外部继续引用属于C侧的内存生命周期问题C#侧无从解决只能回C改代码。6. 用随机数生成器验证你的数据结构实现一个稳定的自测套路6.1 用mt19937生成测试数据把排序和查找“压一遍”代码跑通了怎么知道它真的对我的习惯是不用手推的那三五组数据而是让随机数生成器替我说话。C里rand()的随机质量差、范围小直接用std::mt19937配合std::uniform_int_distribution分布均匀且可复现正是数据结构自测需要的。#include random #include vector #include algorithm #include iostream std::mt19937 rng(std::random_device{}()); std::uniform_int_distributionint dist(-1000, 1000); std::vectorint test(1000); for (int x : test) { x dist(rng); } std::vectorint expect test; std::sort(expect.begin(), expect.end()); bubbleSort(test); if (test expect) { std::cout sorted correctly std::endl; } else { std::cout mismatch found std::endl; }逻辑说明先用同样的数据生成一个 test 和一个 expectexpect 交给std::sort保证正确再用你写的bubbleSort处理 test最后直接比较两个 vector。一跑就是一千个随机用例比你手推几十个数覆盖面大得多。参数说明uniform_int_distributionint dist(-1000, 1000)的范围可以调成包含负数和零的区间这样能测出负数排序和重复元素的边界改成uniform_int_distributionlong long可以扩大数值范围但注意排序比较逻辑不要溢出。折半查找也用同样的套路生成有序随机数组随机挑 100 个 target调用你的binarySearch每返回一个下标就用arr[mid] target校验一次再挑 100 个肯定不存在的数确认全部返回 -1。链表就构造空链表、单节点、头插、尾插、中间插入、删除头结点这些用例每种场景单独跑一遍。树的话随机插入 N 个整数最后中序遍历输出检查是否严格升序这是验证二叉搜索树插入逻辑最快的方法。这套自测跑完代码基本可以拿去交实验报告或者进面试写白板了。我后来每次学完PDF里的一节都会先写这个“随机对照测试”跑不过就停手往回翻那一节的代码重新理解不往下看新内容。这个习惯帮我少调了很多后半夜的bug也让我不再一碰到排序、查找这类题就从原理问到自己心虚。数据结构这东西代码不是看会的是跑会的。希望这篇笔记能帮你在拿到一份C数据结构.pdf之后快速把它变成自己手底下真能跑的代码。本文还有配套的精品资源点击获取