简介这份北理工2020年《数据结构》课程资源包面向正在学习C数据结构与算法的本科生及考研复习者帮助解决从理论理解到代码实践、再到考前冲刺的完整学习需求。压缩包共65个文件约55.42MB以29个cpp源码、16个doc与5个docx文档、9个ppt与1个pptx课件、5个pdf资料为主分别对应编程实践、知识点整理、课堂讲义与试题解析等用途。内容覆盖数组、链表、栈、队列、树、图、哈希表等核心结构并配有股票撮合系统、一元多项式运算、哈夫曼树、平衡二叉树、迷宫问题、关键路径等乐学编程案例可帮助读者在C中动手实现并调试自定义数据结构与STL应用。复习PPT与知识点归总提炼了复杂度分析、排序与查找算法的要点历年试题与练习题则提供自测与查漏补缺的机会。目前已有685人学习适合希望系统夯实数据结构基础、提升算法设计与问题解决能力的读者。1. 数据结构这门课为什么“看懂”和“写出来”之间隔了一整个学期如果你正在搜“北理工-2020《数据结构》资源”大概率不是想找一份课件收藏而是遇到了一个很具体的困境链表插入能看懂图的最短路径能背出步骤但一上机就卡在指针越界、递归爆栈、测试用例对不上。这门课真正的门槛不在概念而在“把抽象逻辑翻译成能跑通的代码”这一步。2020 年前后的课程资源通常包含讲义、习题、实验框架和历年题但资源本身不会替你完成翻译。我见过太多人把 PPT 翻了三遍考试还是栽在手写代码上。这篇笔记按“先立住理论、再动手复现”的顺序把这份资源里最值得投入的部分拆成可执行的路径适合正在跟课、准备补考或想用 C/C 把基础打牢的读者。2. 先分清资源里有什么讲义、实验框架和题库各管什么2.1 三类材料的真实用途和优先级拿到一份课程资源第一反应不应该是从头看到尾。按投入产出比排实验框架 讲义例题 题库。实验框架里通常有已经搭好的main函数、输入输出约定和部分空函数这是最接近“能跑”的起点讲义例题负责解释算法为什么成立题库用来检验边界条件是否覆盖全。很多人反过来先刷题再回头看框架结果发现框架里的结构体定义和题目里的完全不是一套白白浪费时间。材料类型典型内容建议投入判断标准实验框架头文件、结构体、空函数、测试入口60%能否在本地编译通过并跑出一个用例讲义例题算法步骤、复杂度推导、图示25%能否合上资料复述关键循环不变式题库/历年题选择、填空、手写代码15%能否在 20 分钟内写出无语法错误的版本提示如果框架里用了课程自定义的Status或ElemType宏先别改直接沿用否则后面所有函数签名都要跟着动。2.2 用一条最小命令确认环境能跑在动手改任何代码之前先确认编译器能识别框架里的头文件路径。假设你把资源解压到了ds2020/目录实验一在lab1/下常见做法是# 进入实验目录先只编译不链接检查头文件依赖 cd ds2020/lab1 gcc -c main.c -I../include -o main.o # 如果上面通过再链接成可执行文件 gcc main.o list.c -I../include -o lab1 ./lab1这段命令的关键在-I../include它告诉编译器去上一级的include目录找.h文件。很多“找不到头文件”的报错不是代码写错而是路径没给对。参数-c只编译不链接适合先排查语法错误去掉-c后必须把所有.c文件一起列上否则会出现undefined reference。如果框架用的是 C把gcc换成g并在链接时注意iostream和stdio不要混用输出。2.3 从线性表开始建立“可运行”的信心线性表是整门课里最容易获得正反馈的部分因为它的输入输出最直观。以单链表为例框架里通常会留一个ListInsert的空实现。我一般会先写一个最小测试插入三个元素打印再删除中间一个再打印。不要一上来就处理所有边界先让主流程跑通。// 单链表插入的最小实现假设结构体已定义 Status ListInsert(LinkList *L, int i, ElemType e) { // 参数 i 从 1 开始计数i1 表示插在头结点之后 if (i 1) return ERROR; LinkList p *L; // p 指向头结点 int j 0; while (p j i - 1) { // 找到第 i-1 个结点 p p-next; j; } if (!p || j i - 1) return ERROR; // i 超过表长1 LinkList s (LinkList)malloc(sizeof(LNode)); if (!s) return OVERFLOW; s-data e; s-next p-next; // 先接后面再断前面 p-next s; return OK; }逻辑说明j i - 1控制指针停在待插入位置的前驱p-next s之前必须先让s-next指向原来的后继否则会丢链。参数i的合法范围是1到表长1i1时循环一次都不走直接插在头结点后面。失败时看p是否为空以及j是否越过了i-1。这个函数写对之后后面的栈、队列、树、图都只是换一种“找前驱”的方式。3. 把树和图跑起来递归、队列和邻接表的落地细节3.1 二叉树的三种遍历为什么先写非递归版本讲义上通常先讲递归遍历因为代码短。但实验和考试里真正拉开差距的是非递归版本因为它逼你显式管理栈。我建议先写中序非递归再回头理解递归的调用栈。框架里如果给了Stack的实现直接复用不要自己再造一个。// 中序遍历的非递归实现依赖已实现的栈结构 void InOrderTraverse(BiTree T) { Stack S; InitStack(S); BiTree p T; while (p || !StackEmpty(S)) { if (p) { Push(S, p); // 一路向左把沿途结点压栈 p p-lchild; } else { Pop(S, p); // 左边走不动了弹出一个访问 printf(%c , p-data); p p-rchild; // 转向右子树 } } }逻辑说明循环条件p || !StackEmpty(S)保证所有结点都被处理。if (p)分支负责“深入左子树”else分支负责“回退并转向右子树”。参数上唯一需要注意的是Pop必须把弹出的结点写回p否则右子树会丢。如果输出顺序不对先检查Push是否压的是结点指针而不是结点本身再检查StackEmpty在栈空时是否返回了正确的布尔值。3.2 图的存储选邻接矩阵还是邻接表这个问题在实验里经常被低估。邻接矩阵写起来快但遇到稀疏图会浪费大量空间而且遍历时每次都要扫一整行。邻接表省空间但指针操作多删除边的时候容易出错。我的判断标准很简单如果题目给的顶点数不超过 100且需要频繁判断两点之间是否有边用邻接矩阵如果顶点数上千或者边数远小于顶点数的平方用邻接表。// 邻接表的边结点插入头插法注意顺序不影响遍历结果 void InsertEdge(ALGraph *G, int u, int v) { EdgeNode *e (EdgeNode *)malloc(sizeof(EdgeNode)); e-adjvex v; e-next G-vertices[u].firstedge; // 新边插在头部 G-vertices[u].firstedge e; // 如果是无向图还要对称插入一条 v - u EdgeNode *e2 (EdgeNode *)malloc(sizeof(EdgeNode)); e2-adjvex u; e2-next G-vertices[v].firstedge; G-vertices[v].firstedge e2; }逻辑说明头插法让新边总是出现在链表头部遍历顺序和插入顺序相反但这对 DFS 和 BFS 的正确性没有影响。参数u和v是顶点下标不是顶点值调用前要先用LocateVex转换。如果是有向图去掉对称插入那三行。常见错误是忘记给e-next赋初值导致遍历时跳到非法地址。3.3 用 BFS 求无权图最短路径的完整步骤BFS 求最短路径是图这一章最值得亲手写一遍的算法因为它把队列、访问标记和距离数组串在了一起。步骤是初始化距离数组为 -1起点距离为 0起点入队队列非空时出队一个顶点遍历它的所有邻接点如果邻接点距离为 -1则距离加一并入队。// 无权图单源最短路径dist 数组需提前分配并初始化为 -1 void BFSShortestPath(ALGraph G, int start, int dist[]) { int queue[MAXV], front 0, rear 0; for (int i 0; i G.vexnum; i) dist[i] -1; dist[start] 0; queue[rear] start; while (front rear) { int u queue[front]; for (EdgeNode *e G.vertices[u].firstedge; e; e e-next) { int v e-adjvex; if (dist[v] -1) { // 未访问过 dist[v] dist[u] 1; queue[rear] v; } } } }逻辑说明dist[v] -1同时承担了“未访问”和“距离未确定”两个职责所以不需要额外的visited数组。队列用数组模拟时front和rear的初值都是 0rear指向下一个空位。参数MAXV要大于等于顶点数否则会越界。如果结果里出现距离为 -1 的顶点说明该顶点与起点不连通这是正常现象不是代码错误。4. 排序和查找为什么快排的边界总在考试里翻车4.1 快速排序的划分函数必须背下来的三个位置快排的框架不难难在划分函数里low和high的移动顺序。我见过最多的错误是先把low往右移再判断结果基准元素被覆盖。正确的做法是先把基准元素暂存到pivot然后high先走找到比pivot小的填到low位置再low走找到比pivot大的填到high位置最后把pivot填回low。// 快速排序的划分函数返回基准元素的最终位置 int Partition(int a[], int low, int high) { int pivot a[low]; // 暂存基准low 位置视为空 while (low high) { while (low high a[high] pivot) high--; a[low] a[high]; // 比基准小的移到左边 while (low high a[low] pivot) low; a[high] a[low]; // 比基准大的移到右边 } a[low] pivot; // 基准归位 return low; }逻辑说明high先走是为了保证最后low和high相遇的位置一定小于等于基准这样a[low] pivot才不会破坏顺序。参数low和high是闭区间下标。如果排序结果里出现重复元素位置错乱检查内层循环有没有写和漏掉等号会导致死循环。4.2 折半查找的循环条件和边界折半查找的代码短但while条件写low high还是low high直接决定能不能找到最后一个元素。标准做法是low high因为当low high时中间位置还没被检查过。// 折半查找返回下标找不到返回 -1 int BinarySearch(int a[], int n, int key) { int low 0, high n - 1; while (low high) { int mid low (high - low) / 2; // 防止 lowhigh 溢出 if (a[mid] key) return mid; else if (a[mid] key) low mid 1; else high mid - 1; } return -1; }逻辑说明mid用low (high - low) / 2而不是(low high) / 2是为了避免两个大整数相加溢出。参数n是数组长度high初始为n - 1。如果查找结果不稳定先确认数组是否真的有序折半查找对无序数组的行为是未定义的。4.3 把排序算法串成一个可对比的测试单独写一个排序很难看出问题我一般会写一个测试入口把同一组随机数分别喂给冒泡、插入、快排然后比较输出是否一致。这样既能验证正确性又能直观感受不同算法在相同数据量下的耗时差异。// 测试入口生成随机数组复制三份分别排序后比较 int main() { int n 1000; int *base (int *)malloc(n * sizeof(int)); srand(42); // 固定种子保证可复现 for (int i 0; i n; i) base[i] rand() % 10000; int *a copyArray(base, n); int *b copyArray(base, n); int *c copyArray(base, n); BubbleSort(a, n); InsertSort(b, n); QuickSort(c, 0, n - 1); printf(consistent: %d\n, sameArray(a, b, n) sameArray(b, c, n)); return 0; }逻辑说明srand(42)固定随机种子保证每次运行的数据一样方便排查。copyArray需要自己实现返回新分配的数组。sameArray逐个比较元素。如果consistent输出 0先检查QuickSort的递归边界是否写成了low high再检查Partition的返回值有没有被正确使用。5. 避坑与排查五个让实验卡到深夜的典型问题5.1 编译通过但运行崩溃现象是段错误现象gcc没有任何警告运行时报Segmentation fault。原因通常是空指针解引用或数组越界最常见的是链表操作里p-next在p为NULL时被访问。解决在gdb里用run跑起来崩溃后输入bt看调用栈定位到具体行或者在每个指针解引用前加assert(p ! NULL)先让错误提前暴露。5.2 递归遍历大树时栈溢出现象二叉树深度超过几千时程序直接退出没有输出。原因递归调用层数等于树高系统栈默认只有几 MB。解决改成非递归版本用显式栈或 Morris 遍历如果必须递归把树高作为参数传入并在超过阈值时切换策略。考试里手写代码一般不会遇到但实验数据如果随机生成深度可能远超预期。5.3 图的遍历结果少访问了顶点现象DFS 输出顶点数少于实际顶点数。原因图不连通而代码只从第一个顶点开始遍历。解决在外层加一个循环对所有未访问的顶点都调用一次 DFS。这个点在讲义里通常一笔带过但实验的测试用例经常包含非连通图。5.4 排序结果在小数据量下正确大数据量下错乱现象10 个元素排序没问题1000 个元素出现逆序。原因快排的递归深度过大导致栈溢出或者Partition在重复元素多时退化成 O(n^2)。解决在QuickSort里加一个判断当high - low小于某个阈值时改用插入排序或者随机选择基准元素避免最坏情况。5.5 文件读取时最后一个数据丢失现象从input.txt读顶点和边最后一行没被处理。原因while (!feof(fp))的写法会导致最后一行被读两次或漏读。解决改用while (fscanf(fp, %d %d, u, v) 2)用返回值判断是否读到了完整数据。这个坑在实验的数据输入部分非常常见和数据结构本身无关但会让人误以为算法写错了。6. 把资源用出复利一套自测清单和一个手写代码习惯资源本身是静态的真正拉开差距的是你怎么用它。我自己的习惯是每学完一个结构先合上资料在白纸上写出结构体定义和三个核心操作的函数签名然后再打开编译器把签名补成完整实现。这个过程会暴露大量“以为自己会了”的漏洞。下面这张自测清单可以帮你判断是否真的掌握了一个模块。模块自测问题通过标准线性表不看书写出单链表反转15 分钟内编译通过边界用例正确栈和队列用两个栈实现队列能说清摊还复杂度为什么是 O(1)二叉树写出非递归后序遍历能解释为什么需要额外标记或双栈图手写 Dijkstra 的松弛过程能指出为什么不能处理负权边排序比较快排和归并的稳定性能说出各自适用场景和空间代价查找写出平衡二叉树的插入调整能画出四种旋转的示意图另一个习惯是给每个实验写一个README只记三件事这个实验的核心数据结构是什么、我卡了多久、最后是怎么解决的。过一个月回头看这份记录比任何课件都值钱。2020 年的这份资源里实验框架的注释风格和变量命名可能和现在流行的写法有差异但底层逻辑没有变。把线性表、树、图、排序这四块各跑通一个完整实验再回头翻讲义你会发现之前看不懂的复杂度推导突然有了具体的对应物。希望帮到你。本文还有配套的精品资源点击获取