数据结构C/C++代码实现全解析：从线性表到图论算法，附避坑指南

简介面向正在学习数据结构与算法、需要参考代码实现的同学作者将自己在CSDN问答中反复解答过的内容整理成一份压缩包。包内共35个文件其中34个为C/C源码文件另含1个Markdown说明文档整包约28KB轻量易下载。代码覆盖线性表、栈与队列、串、数组/矩阵、广义表、二叉树与线索二叉树、哈夫曼树、图及图算法等主线内容具体包括顺序表、链表、栈队列的顺序与链式实现以及BFS、DFS、Dijkstra、Floyd、Prim、Kruskal、拓扑排序、关键路径等经典算法还涉及邻接表、邻接矩阵、十字链表、邻接多重表等多种图存储方式。对于课程设计、考研复习或日常刷题均可直接对照源码理解存储结构与算法流程节省自行调试时间。目前已有369人学习下载对于入门到进阶阶段的学习者较为实用。1. 数据结构代码包为什么说它比刷题库更值得过一遍期末考前一周某同学抱着一堆数据结构代码来找我说他的“哈夫曼树.cpp”一编译就跑飞。我扫了一眼发现他把顶点数写死在全局数组里遍历时却按另一个 n 值去跑——这是复现数据结构源码最常见的通病文件能跑换一组输入就翻车。这份「数据结构C/C代码实现」资源把从线性表到图论最常考的二十多个经典实现收在一个包里顺序表、链表、栈队列、二叉树、线索二叉树、哈夫曼树、DFS/BFS、Dijkstra、Floyd、Prim、Kruskal、拓扑排序、关键路径全都有。它不是教科书是一批可以照着改、照着跑的源码适合期末突击、复试手撕代码以及做课程设计时不想从零开始的人。2. 线性表与栈队列先分清存储结构再看代码才不晕拿到压缩包先别急着逐文件编译这二十多个文件虽然各自独立但它们背后只有两种存储思路连续存储和链式存储。理解了这个后面看图和树都会顺很多。2.1 顺序表与链表存储结构决定操作代价顺序表的核心是数组逻辑相邻就是物理相邻按下标访问是 O(1)但插入和删除要搬动后续元素。链表的核心是结点加指针插入删除只要改指针但访问第 k 个元素得从头走。代码包里「顺序表.cpp」和「单链表.cpp」刚好是这两种思路的对照。顺序表插入的经典写法#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } SeqList; int ListInsert(SeqList *L, int i, int e) { if (i 1 || i L-length 1) return 0; // 位置越界 if (L-length MAXSIZE) return 0; // 表已满 for (int j L-length; j i; j--) // 从后往前搬 L-data[j] L-data[j - 1]; L-data[i - 1] e; // 下标要减 1 L-length; return 1; }这段代码里最容易看懵的是for循环下标逻辑位置 i 从 1 开始数组下标从 0 开始所以data[i-1]才是要插入的位置。搬运时j从length开始往前先把最后一个元素挪到length位置再依次后移最后把新元素写进空出来的i-1。参数L是结构体指针修改length必须用它否则函数结束就丢。初始化时记得让length 0很多翻车都是因为忘了给长度赋初值。单链表的插入处理的是另一种边界头插法和尾插法代码差异很大空表插入和非空表插入的指针操作也不一样。建议把顺序表和单链表两个文件放一起读一个看搬移的循环一个看指针的衔接两边对照能看出「为什么链表插入不需要搬元素」——它只需要改两个指针代价与表长无关。2.2 栈与队列先进后出与先进先出的代码骨架栈和队列都属于操作受限的线性表区别只在进出口的数量。栈只允许一端进出队列一端进另一端出。代码包里「栈.cpp」「链栈.cpp」对应顺序栈和链栈「队列.cpp」「链队.cpp」对应顺序循环队列和链队列。这里我重点说链栈因为它揭示了链表做栈时的头插思想。typedef struct StackNode { int data; struct StackNode *next; } StackNode; StackNode* Push(StackNode *top, int x) { StackNode *s (StackNode*)malloc(sizeof(StackNode)); s-data x; s-next top; // 新结点指向旧栈顶 return s; // 新结点成为栈顶 } StackNode* Pop(StackNode *top, int *x) { if (top NULL) return NULL; *x top-data; StackNode *p top; top top-next; // 栈顶后移 free(p); return top; }这段代码和其他链式实现最大的不同是入栈出栈都要return新栈顶。因为栈顶是局部变量直接改top指针在函数内部生效调用方拿不到新值所以要么返回新指针要么传二级指针。很多初学者在这段上翻车就是只调用Push(top, x)却不接收返回值结果打印出来栈还是空的。初始化时top NULL判断空栈就看top NULL这个约定在链式结构里是统一的。顺序队列的代码里要特别注意「循环队列」的写法入队rear (rear 1) % MAXSIZE出队front (front 1) % MAXSIZE判空条件是front rear判满条件是(rear 1) % MAXSIZE front。如果不取模直接rear数组很快就越界这也是顺序队列最容易出 bug 的地方。2.3 读这批源码的通用顺序先看笔记再按依赖分组压缩包里有个「数据结构.md」文件它其实是这批代码的索引笔记建议你第一个打开它。我一般会按这条线读先线性表顺序表、单链表、双向链表再栈队列栈、链栈、队列、链队然后树二叉树、线索二叉树、哈夫曼树最后图邻接矩阵、邻接表、DFS/BFS、最短路径、最小生成树、拓扑排序、关键路径。每个文件基本不超过两百行用到的都是纯 C 的写法printf、malloc、free占大头个别文件用了 C 的引用或cout。编译时用 g 更稳妥避免.cpp后缀配 gcc 时报链接错。3. 树与图遍历递归、回溯与队列的三个分水岭树和图是这门课里最考验代码转化能力的两块。树的遍历靠递归和栈图的遍历要靠队列或递归栈它们的实现骨架其实只有几行但每一行都卡在「什么时候进、什么时候出」上。3.1 二叉树一次递归搞定先序中序后序二叉树的三序遍历代码结构几乎一样区别只在于访问结点的时机。先序是「访问—左—右」中序是「左—访问—右」后序是「左—右—访问」。代码包里「二叉树.cpp」用的是链式存储结点结构包含数据域和左右孩子指针typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; } BiTNode; void PreOrder(BiTNode *T) { if (T NULL) return; // 递归出口 printf(%c , T-data); // 先访问根 PreOrder(T-lchild); // 再走左子树 PreOrder(T-rchild); // 最后走右子树 }这段代码看似简单但递归出口T NULL是整个函数的灵魂。把它换成T-lchild NULL之类就会漏子树。中序和后序只要挪动printf那一行的位置即可访问时机越靠后根结点的输出就越晚。理解递归时别在脑子里人肉压栈画一棵三层的小树用笔标出每个结点的访问序号比盯着代码想快得多。3.2 线索二叉树与哈夫曼树两个容易混的改造点「线索二叉树.cpp」和「哈夫曼树.cpp」放在一起很容易让人以为都是指针改动但二者方向完全不同。线索二叉树是把空指针利用起来指向遍历序列中的前驱和后继哈夫曼树是从下往上建树每次选两个权值最小的结点合并。线索二叉树的结点要加ltag和rtag两个标志位0 表示孩子指针1 表示线索这就是它和普通二叉树在结构上唯一的区别。哈夫曼树建树的起点是叶子结点集合每次从森林里选两个最小权的树合并新树的权是二者之和。代码实现里最常见的做法是维护一个权值数组每次扫描找两个最小值void SelectMin(int w[], int n, int *s1, int *s2) { int min1 INF, min2 INF; *s1 *s2 -1; for (int i 0; i n; i) { if (w[i] min1 w[i] ! -1) { min2 min1; *s2 *s1; min1 w[i]; *s1 i; } else if (w[i] min2 w[i] ! -1) { min2 w[i]; *s2 i; } } }这段代码的坑在于w[i] -1的结点代表已被合并过必须跳过。如果初始 n 个叶子建哈夫曼树最终结点数是2n - 1数组长度要按这个上限预留很多跑飞都是数组开小了。另外s1和s2用指针传出是为了一个函数同时返回两个下标如果你自己不习惯这种写法用结构体返回也可以。3.3 DFS与BFS图遍历的一纵一横图的 DFS 和 BFS 是后续拓扑排序、最短路径的基础文件。DFS 走的是「一条路走到底再回头」BFS 走的是「一圈一圈往外扩」。DFS 常写成递归BFS 必须配队列。// DFS 核心visited 数组需全局初始化 void DFS(int v) { visited[v] 1; printf(%d , v); for (int w FirstNeighbor(v); w 0; w NextNeighbor(v, w)) { if (!visited[w]) { DFS(w); } } }// BFS 核心用队列实现 void BFS(int v) { queueint q; visited[v] 1; q.push(v); while (!q.empty()) { int cur q.front(); q.pop(); printf(%d , cur); for (int w FirstNeighbor(cur); w 0; w NextNeighbor(cur, w)) { if (!visited[w]) { visited[w] 1; q.push(w); } } } }两段代码里FirstNeighbor和NextNeighbor是图存储结构提供的邻居接口如果是邻接矩阵实现这两个函数就是一层for循环扫一行如果是邻接表实现就是沿着边表指针走。DFS 的标记时机在递归之前BFS 的标记时机在入队之前。有个常犯错误是出队时才标记visited这会导致同一个结点被反复入队队列膨胀逻辑上也不再是严格的一层一层扫。选 DFS 还是 BFS取决于你要什么结果找路径是否存在、判断连通分量用 DFS 更省空间求无权图的最短路径、层序遍历用 BFS 更直接。4. 最短路径与最小生成树四个经典算法怎么选、怎么看图论部分是这个包里文件数最多的区域Dijkstra、Floyd、Prim、Kruskal、拓扑排序、关键路径还有三个建图文件。每个算法的代码都不短但如果按「算法思想—数据结构—核心循环」三步拆开看就能很快抓到主干。4.1 最短路径Dijkstra 与 Floyd单源与全源的分工Dijkstra 解决单源最短路径要求边权非负Floyd 解决任意两点间最短路径走的是一条动态规划的思路逐步允许中间结点集合扩大。代码包里「Dijkstra.cpp」通常用邻接矩阵存图维护dist[]和path[]两个数组每次从未确定最短路径的结点里选dist最小的那个做松弛。#define MAXV 100 #define INF 0x3f3f3f3f void Dijkstra(int v, int n, int arcs[MAXV][MAXV], int dist[], int path[]) { bool s[MAXV] {false}; for (int i 0; i n; i) { dist[i] arcs[v][i]; if (dist[i] INF) path[i] v; else path[i] -1; } s[v] true; dist[v] 0; for (int k 1; k n; k) { int u -1, min INF; for (int j 0; j n; j) { if (!s[j] dist[j] min) { u j; min dist[j]; } } if (u -1) break; s[u] true; for (int j 0; j n; j) { if (!s[j] arcs[u][j] INF dist[u] arcs[u][j] dist[j]) { dist[j] dist[u] arcs[u][j]; path[j] u; } } } }参数v是源点编号n是顶点数。INF用0x3f3f3f3f是因为它足够大且相加不会溢出 int如果用INT_MAX松弛时dist[u] arcs[u][j]一加就可能变成负数整个比较逻辑就废了。Dijkstra 的外层循环跑n-1次每次选一个未确定结点内层第一次扫描找最小第二次扫描做松弛这就是它的 O(n²) 来源。Floyd 的三重循环里最外层是中间结点 k内两层是起点和终点写成if (dist[i][k] dist[k][j] dist[i][j])更新这个 k 在最外层是它和 Dijkstra 最大的区别也是考试里最爱问的「为什么 Floyd 的 k 不能放内层」。两种算法怎么选参考这张表场景推荐算法复杂度限制单源边权非负DijkstraO(n²)不能有负权边单源可能有负权边Bellman-Ford 或 SPFAO(nm)无负环全源点数少FloydO(n³)边权可以为负但不能有负环全源点数多对每个点跑 DijkstraO(n·e·logn)非负权4.2 最小生成树Prim 与 Kruskal加点与加边Prim 从一个起点出发每次把连接「已选集合」和「未选集合」的最短边拉进来适合稠密图Kruskal 把所有边按权排序从小到大选不构成环的边适合稀疏图。代码包里「Prim.cpp」的核心是维护lowcost[]数组每次选最小一通操作后更新相邻顶点void Prim(int v, int n, int arcs[MAXV][MAXV]) { int lowcost[MAXV]; bool used[MAXV] {false}; for (int i 0; i n; i) lowcost[i] arcs[v][i]; used[v] true; for (int k 1; k n; k) { int u -1, min INF; for (int j 0; j n; j) { if (!used[j] lowcost[j] min) { u j; min lowcost[j]; } } if (u -1) return; used[u] true; for (int j 0; j n; j) { if (!used[j] arcs[u][j] lowcost[j]) { lowcost[j] arcs[u][j]; } } } }和 Dijkstra 的代码相比Prim 的更新条件是arcs[u][j] lowcost[j]没有dist[u] ...的累加区别就在这里最短路径关心「到源点的累计距离」最小生成树只关心「到已选集合最小边的当前值」。Kruskal 的实现通常要配合并查集判断加入一条边是否会形成环。「Kruskal.cpp」里的核心就是把边按权重排序然后逐个尝试 unionunion 失败说明成环跳过这条边。4.3 拓扑排序、关键路径与十字链表从建图到应用「邻接矩阵创建图.cpp」「邻接表创建图.cpp」「十字链表.cpp」「邻接多重表.cpp」四个文件解决的是同一件事不同方式存图。邻接矩阵最直观但浪费空间邻接表省空间但定位边的操作略绕十字链表同时存入弧和出弧适合频繁修改或有向图邻接多重表专为无向图设计每条边只存一次。你不需要每个文件都精读先建图再看 DFS/BFS 怎么在对应结构上取邻居最后回到应用算法这样图论部分就串起来了。关键路径相关文件是这套代码里难度较高的一个。「拓扑排序.cpp」是基础关键路径要先拓扑排序确定事件的最早发生时间再逆拓扑序求最晚发生时间两者相等的活动才是关键活动。有一个很现实的经验如果拓扑排序跑出来的顶点数小于图中结点数说明图里有环这时候做关键路径纯属浪费时间先回去查建图代码。5. 避坑手册从这批代码里最容易踩到的五个坑源码能跑只是起点换输入就挂才是常态。下面这些坑是我在带人看这类代码时反复遇到的每一条都是「现象—原因—解决」的结构你对照着检查自己的文件即可。5.1 坑一递归函数没有出口程序运行直接炸栈现象运行二叉树遍历或 DFS 时程序卡死或报Segmentation fault甚至整个窗口崩溃。原因递归出口判断写错或漏写。比如把if (T NULL) return;写成if (T-lchild NULL) return;叶子结点带空子树时递归无法停止或者 DFS 里visited数组忘记初始化同一结点被反复访问递归深度呈指数级增长。解决每个递归函数先检查出口再检查业务逻辑。二叉树递归出口必须是T NULL图 DFS 的出口本质是「所有邻居都已访问」靠visited标记来兜底。另外一个直觉判断法递归函数里如果没有「直接 return」的分支大概率是错的。5.2 坑二数组下标从 1 开始的操作存进下标从 0 开始的数组现象顺序表插入后元素错位打印出来第一个元素是空的或者最后一个元素被丢。原因序号和下标混用。逻辑位置 i 从 1 开始数组下标从 0 开始插入代码里搬移用j i写入却用了data[i]而不是data[i - 1]于是一个元素被写到下一个位置表尾丢元素。解决统一约定要么所有接口都从 0 开始更符合 C 的习惯要么保留 1 起始的语义但在写入处手动减 1。我一般会在代码开头加注释// 位置从 1 开始下标从 0 开始每次改代码都盯着这一行看能避免 80% 的下标问题。5.3 坑三.cpp文件用 C 风格写着编译却用 gcc 命令现象代码明明写得没问题gcc 编译却报C语法错误换 g 又报malloc没强转两边轮流出错。原因文件后缀是.cpp但主体是malloc、printf的 C 写法gcc 默认按 C 编译对 C 语法不适配g 按 C 编译从void*到int*的隐式转换又不合法。解决统一用 g 编译并把malloc的返回值做强转(StackNode*)malloc(sizeof(StackNode))。命令写g 顺序表.cpp -o 顺序表 ./顺序表不做两步能避开很多环境问题。代码包里写的虽然是 C 风格按 C 工程处理最省事。5.4 坑四图的顶点编号从 0 开始建图却从 1 开始录入现象Dijkstra 或 Floyd 跑出来的路径错乱某些顶点明明有边却显示不可达。原因建图代码按 1 到 n 读入顶点算法内部按 0 到 n-1 访问顶点编号整体偏移一位。邻接矩阵的对角线、visited数组的大小全跟着错位而且这种错误往往只在部分数据上暴露隐蔽性极强。解决读代码第一件事就是确认「顶点编号从 0 还是从 1 开始」。从 0 开始循环写i n建边时u--、v--从 1 开始数组开n1大小循环写i n。代码里通常能通过for (i 0; i n; i)判断发现混用就把录入处减 1 对齐。5.5 坑五链表删除结点后没释放或者先释放又访问了 next现象循环链表或链栈在多次删除后程序报错用内存检测工具能看到「use after free」。原因删除结点时先free(p)又访问p-next或p-next没有提前存下来free 之后指针变成悬空指针下一轮循环取p-next就是读取已释放的内存。解决删除前先把下一个结点地址存起来再释放当前结点。一般的顺序是q p-next; p-data 搬到 p-next 或建立连接; free(q)。写链表操作时养成一个习惯任何指针在 free 之后都视为不可用访问链关系必须在 free 之前完成。6. 进阶用法把这批源码改造成你自己的算法模板代码包里的文件命名直接对应算法名这本身就是一份很好的检索目录。但「能看懂」和「能上考场手写」之间还差一步把每个文件重构成不依赖全局变量、能接受任意规模输入的模板。这一步做完你的收获会比单纯编译通过大得多。6.1 把源码改造成可复用模板的四个动作第一把写死的常量抽成预处理宏放在文件顶部#ifndef MAXV #define MAXV 100 // 顶点数上限按题目改 #endif #define INF 0x3f3f3f3f第二把全局数组改成参数传入函数或者至少把数组大小与 n 绑定。第三把测试输入从main里抽取成单独函数方便换用例。第四每个文件加一个print 数组/树的辅助函数调试时直接看输出而不是靠断点。6.2 五组自测用例验证你改造完的文件没写坏空表/空树/空图顺序表length0、二叉树TNULL、图n1程序不能崩。最小规模单链表只插入一个结点删除它之后链表为空。边界下标顺序表在位置 1 和位置length1各插入一次。图不连通Dijkstra 跑两个互不相连的顶点输出应保持INF。重复顶点BFS 同一个起点跑两次第二次应直接结束。每改一个算法文件就用第 3 组或第 5 组用例过一遍十次有九次能提前暴露下标或标记问题。从那以后我每次拿到新代码都强制自己先跑一组最小输入再加数据规模这个习惯帮我省下的排错时间比任何调试器的帮助都大。这份资源的价值也正在这里——它不是标准答案而是你对照练习、亲手改成自己风格模板的素材希望帮到你。本文还有配套的精品资源点击获取