C语言实现6顶点有向图的邻接矩阵与邻接表双向转换

简介这份文档面向正在学习数据结构、需要理解图存储与转换的读者围绕有向图的邻接矩阵和邻接表展开兼顾课程实验与C语言实现练习。压缩包共1个docx文件约55KB内容包含实验目的、问题描述、具体要求与完整程序示例便于按实验任务逐步阅读和复现。文档以AdjMatrix、AdjList和ArcNode等结构为基础给出DispMat、MatToList、DispAdj、ListToMat等函数的实现覆盖邻接矩阵与邻接表的相互转换、打印输出及手动输入图信息后的存储转换并提示动态内存分配与释放等注意事项。已有8616人学习适合希望从代码层面掌握两种图存储方式差异、完成相关实验与查漏补缺的读者参考。1. 一张 6 顶点有向图把你卡在两种存储之间带 6 个顶点、10 条弧的有向图让你分别用邻接矩阵和邻接表存一遍再互转一次输出还得和原图对得上——这题在数据结构课设里出现频率极高。图的邻接矩阵和邻接表存储表面上只是“二维数组 vs 链表”的差别真动手写转换函数时倒序扫描、头插法、哨兵值这三件事随便错一个控制台打出来就是一坨对不上的数字还很难看出错在哪。手上这份 C 语言实现给了一个能跑的最小闭环MGraph装矩阵、ALGraph装链表MatToList和ListToMat做双向转换最后把两种形态全打到屏幕上做肉眼比对。适合刚学完图论、想把这套结构真正落成可编译代码的人也适合要交实验报告、需要一份能改能扩底稿的人。2. 结构体先摆平MGraph 与 ALGraph 的内存布局和字段语义动手写转换逻辑之前得先认清这两套结构在内存里长什么样。很多转换函数写错根子不在循环写错而是对字段语义理解偏了比如把arcs[i][j]的 0 当成“权重为 0 的边”而不是“没有边”。2.1 MGraph一个 20×20 的定长二维数组撑起整张图邻接矩阵那一侧的类型定义是这样几行#define MAX_VERTEX_NUM 20 /* 顶点数上限所有数组都按这个开 */ typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef int VertexType; /* 顶点信息这里直接存编号 */ typedef struct { VertexType vexs[MAX_VERTEX_NUM]; /* 顶点表存顶点本身的信息 */ AdjMatrix arcs; /* 邻接矩阵存边和权值 */ int vexnum, arcnum; /* 当前图的顶点数、弧数 */ } MGraph;typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];这一行的写法值得单独说一句它 typedef 的不是指针而是“20 个 int 的数组”再套一层“20 个这样的数组”所以后面写AdjMatrix arcs;完全等价于int arcs[20][20];。不少同学第一次看到g-arcs[i][j]会下意识去找arcs的 malloc其实没有——这块 1600 字节是跟着MGraph变量一起分配在栈上的MGraph g;一声明空间就到位了不需要也不应该再给它分配。vexs存的是顶点本身的信息这份代码里VertexType是int实际只当编号用从头到尾没被赋值过DispMat打印时也不看它。要真做带城市名的图把VertexType改成char name[32]再同步改打印和输入就行arcs那边一行都不用动。vexnum和arcnum是元数据前者决定所有循环的边界后者只用于展示改错arcnum不会让程序崩但会让你的实验报告数字对不上属于典型的“不影响运行但影响得分”的字段。矩阵里存什么这份代码有个隐含约定0 表示没有边非 0 表示有边且值就是权值。同时文件顶上又定义了#define INF 32767DispMat里还专门判了if(g-arcs[i][j]INF) printf(%3s,---);。这两套语义是打架的——MatToList里判的是! 0也就是说 INF 那条分支在转换时会被当成一条权重 32767 的真实边。所以实际跑起来INF 只是给打印函数留的一个“未来可能用”的口子真正的判定标准是 0。这一点在后面第 5 章还会专门翻出来讲。2.2 ALGraph顶点数组加边结点链表VNode 与 ArcNode 怎么配合邻接表那一侧是两个结构体加一个数组类型typedef struct ArcNode { /* 边结点一条弧就是一个结点 */ int adjvex; /* 这条弧指向的顶点下标 */ struct ArcNode *nextarc; /* 同起点的下一条弧 */ int info; /* 权值 */ } ArcNode; typedef struct VNode { /* 顶点结点每个顶点一个串起它的出边 */ VertexType data; /* 顶点信息 */ ArcNode *firstarc; /* 出边链表头指针 */ } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; /* 顶点数组长度固定 20 */ int vexnum, arcnum; } ALGraph;} VNode, AdjList[MAX_VERTEX_NUM];这行一次性定义了两个类型名VNode是单个顶点结点AdjList是“20 个 VNode 的数组”。所以ALGraph里的AdjList vertices;展开就是VNode vertices[20];。这个写法在教材里很常见但读代码时容易漏掉AdjList其实带了长度误以为是VNode *。ArcNode里三个字段各司其职adjvex是弧头顶点在vertices数组里的下标不是顶点值本身info是权值对应矩阵里的arcs[i][j]nextarc串起同一个起点的所有出边。有向图里一条弧对应一个ArcNode挂在起点那个VNode的链表上无向图里一条边要建两个ArcNodei 的链表挂 j、j 的链表挂 i这是后面改无向图时第一个要动的地方。真正把两者区分开的是空间账矩阵不管图稀不稀疏永远占n²个格邻接表占n个顶点结点加e个边结点e是实际弧数。6 个顶点 10 条弧的图上矩阵 36 个格子里只有 10 个非零利用率不到三成换成 1000 个顶点、2000 条弧的稀疏图矩阵要 100 万个格链表只需要 3000 个结点差距是三个数量级。反过来稠密图接近n²条边时链表每个结点还要多带一个 8 字节指针反而比矩阵更占地方。维度邻接矩阵 MGraph邻接表 ALGraph空间复杂度O(n²)与边数无关O(ne)随边数增长判断 i→j 是否有边O(1)一次下标访问O(degree(i))要扫链表遍历某顶点全部出边O(n)要扫一整行O(degree(i))只走实际存在的边适合的图稠密图、频繁判边稀疏图、频繁遍历邻接点实现难点哨兵值统一指针操作与内存释放2.3 用 sizeof 把两种结构的内存账算清楚光看定义不够直观加四行打印把两套结构的实际字节数量出来心里就有数了#include stdio.h int main(void) { printf(sizeof(AdjMatrix) %zu\n, sizeof(AdjMatrix)); /* 20*20*4 1600 */ printf(sizeof(MGraph) %zu\n, sizeof(MGraph)); /* 1600 80 8 */ printf(sizeof(VNode) %zu\n, sizeof(VNode)); /* int 指针含对齐 */ printf(sizeof(ArcNode) %zu\n, sizeof(ArcNode)); /* int 指针 int含对齐 */ printf(sizeof(ALGraph) %zu\n, sizeof(ALGraph)); /* 20*sizeof(VNode) 8 */ return 0; }在常见的 64 位环境上AdjMatrix是 1600 字节MGraph约 1688 字节矩阵 1600 顶点表 80 两个 int 加对齐。VNode是int加一个 8 字节指针按 8 字节对齐后 16 字节ALGraph就是 20×168 328 字节跟图里有多少边完全无关——边结点是后面malloc出来的不在这 328 字节里。ArcNode因为字段顺序是int / 指针 / int中间会插 4 字节填充实际 24 字节而不是 16 字节。这个数字很关键算邻接表总开销时按vexnum*16 arcnum*24 8估比按字段长度硬加准得多。提示不同编译器、不同位宽下这些数字会变别把上面几个值当标准答案抄进报告自己跑一遍打印再写。跑通这一步之后你对“矩阵是定长预分配、链表是按需分配”这件事就有体感了后面看转换函数为什么一个要malloc、一个不用也就顺理成章。3. 转换链路拆解MatToList 的倒序头插与 ListToMat 的回填两个转换函数是整个程序的核心加起来不到 40 行但每一行的顺序都有讲究。这一段把两个函数完整拆开顺便解释清楚一个很反直觉的地方为什么j要从n-1往0扫。3.1 MatToList为什么 j 要从 n-1 往 0 扫先看矩阵转链表的完整实现void MatToList(MGraph *g, ALGraph *G) { int i, j, n g-vexnum; ArcNode *p; /* 第一步把每个顶点的出边链表头置空否则 firstarc 是野指针 */ for (i 0; i n; i) G-vertices[i].firstarc NULL; /* 第二步逐行扫矩阵非零元素建结点挂上去 */ for (i 0; i n; i) { for (j n - 1; j 0; j--) { /* 注意这里是倒序 */ if (g-arcs[i][j] ! 0) { /* 0 表示 i 到 j 没有弧 */ p (ArcNode *)malloc(sizeof(ArcNode)); p-adjvex j; /* 弧头顶点下标 */ p-info g-arcs[i][j]; /* 权值原样搬过来 */ /* 头插法新结点插到链表最前面 */ p-nextarc G-vertices[i].firstarc; G-vertices[i].firstarc p; } } } G-vexnum n; /* 元数据别忘了一起搬 */ G-arcnum g-arcnum; }第一段初始化不能省。G是main里malloc出来的那块内存里全是垃圾值firstarc不置空就等着后面p-nextarc G-vertices[i].firstarc把野指针串进链表运行时打印到一半直接段错误。我见过不少人调试半天以为链表逻辑错了其实是漏了这三行。第二段是重点。倒序扫描配头插法结果是正序。假设第 0 行非零元素在下标 1 和 3j从n-1递减到 0先碰到 3头插得到链表3再碰到 1头插到最前面链表变成1→3。如果正序扫描再头插先插 1 再插 3链表就是3→1跟矩阵列下标顺序正好反过来。教材上两种写法都有但倒序加头插这个组合的好处是链表里出边的顺序和矩阵列下标的升序一致后面不管是用DispAdj打印比对还是用它做 BFS 遍历输出序列都能和矩阵版本逐个对上省掉一堆“顺序不同但结果等价”的解释成本。第 4 章那个 BFS 交叉验证能成立靠的就是这个性质。复杂度这块要清醒这两层循环是无条件跑满n²次的跟图里有多少条边没关系所以MatToList的时间复杂度是 O(n²)不是 O(ne)。稀疏图上这个转换是亏的——1000 个顶点、2000 条弧为了建 2000 个结点得扫 100 万次矩阵。真要优化得让矩阵那一侧额外存一个行内非零元素的索引或者干脆从边的列表出发建链表但那就偏离“矩阵转链表”这个题意了。3.2 DispAdj 与 DispMat打印函数里的两个隐患转换对不对全靠两个打印函数做肉眼比对。矩阵那边void DispMat(MGraph *g) { int i, j; for (i 0; i g-vexnum; i) { for (j 0; j g-vexnum; j) { if (g-arcs[i][j] INF) printf(%3s, ---); /* 用 --- 表示没有边对齐好看 */ else printf(%3d, g-arcs[i][j]); } printf(\n); } }%3d是为了让每列宽度一致输出能对齐成方阵。INF那条分支的意图是把“没有边”打成---而不是0视觉上更清楚但它跟MatToList里判 0 的约定是冲突的——第 2 章提过一次第 5 章还会展开。如果统一用 0 表示无边这段其实可以直接printf(%3d, ...)。链表那边问题更隐蔽void DispAdj(ALGraph *G) { int i; ArcNode *p; for (i 0; i G-vexnum; i) { p G-vertices[i].firstarc; if (p ! NULL) /* 这里把顶点号也一起包进去了 */ printf(%3d:, i); while (p ! NULL) { printf(%3d, p-adjvex); p p-nextarc; } printf(\n); } }把printf(%3d:, i)放进if (p ! NULL)里面效果是出度为 0 的顶点整行都不打印连顶点号都不出现。6 个顶点的图如果有个孤立点输出就只有 5 行你会以为转换漏了顶点其实是打印函数的锅。正确写法是把顶点号提到if外面每行必打没有出边就打一个空的“顶点号:”。另外这个函数只打adjvex不打info带权图转换成链表后你在屏幕上根本看不出权值对不对验证等于只做了一半——后面第 6 章会给一个带权版本的打印。3.3 ListToMat清零、回填、补元数据三步反方向的转换短得多void ListToMat(ALGraph *G, MGraph *g) { int i, j, n G-vexnum; ArcNode *p; /* 第一步矩阵清零。局部变量 g1 是栈上的垃圾值不清零就是随机数 */ for (i 0; i n; i) for (j 0; j n; j) g-arcs[i][j] 0; /* 第二步顺着每个顶点的出边链表回填矩阵 */ for (i 0; i n; i) { p G-vertices[i].firstarc; while (p ! NULL) { g-arcs[i][p-adjvex] p-info; /* 行是起点 i列是弧头 adjvex */ p p-nextarc; } } /* 第三步补上元数据否则 DispMat 的循环边界是垃圾 */ g-vexnum n; g-arcnum G-arcnum; }第一步的清零是必须的而且要按n清不是MAX_VERTEX_NUM。main里的MGraph g1;是局部变量栈上那块 1600 字节里是上一位函数调用留下的残留数据不清就直接往上写没被覆盖到的位置全是随机数打印出来一片乱七八糟的“边”。第二步的双重身份要认清外层i从G-vertices取链表是矩阵的行内层p-adjvex是矩阵的列。写成g-arcs[p-adjvex][i]就变成转置了运行时不会报错但输出会跟原图对不上而且恰好在你图本身不对称有向图基本都不对称的时候才暴露。复杂度是 O(n² e)清零那层花n²回填只花实际弧数。跟MatToList一样清零环节让稀疏图也吃满n²这是定长数组存储绕不开的成本。到这一步两个函数一正一反理论上ListToMat(MatToList(M))应该还原出M。但“理论上”这三个字在 C 语言里不太可靠得真跑一遍看输出这就是下一章要做的事。4. 编译与跑通从硬编码的 6 顶点用例切到手动输入代码逻辑看懂了和程序能跑是两回事。这一章从编译命令开始给出预期输出再把题目要求的“手动输入任意图”那部分补上。4.1 一次编译三组输出对照整个程序就一个.c文件编译不需要额外依赖# -Wall 把警告全打开这个程序里能揪出隐式返回类型的问题 gcc -Wall -g -o graph graph.c ./graph-Wall千万别省。原代码里ListToMat没写返回类型C89 下会被当成隐式int编译器一声不吭但加上-Wall立刻会报return type defaults to int。补上void就干净了。main里的测试数据是一张 6 顶点、10 条弧的有向图矩阵直接硬编码int A[][6] { {0, 5, 0, 7, 0, 0}, {0, 0, 4, 0, 0, 0}, {8, 0, 0, 0, 0, 9}, {0, 0, 5, 0, 0, 6}, {0, 0, 0, 5, 0, 0}, {3, 0, 0, 0, 1, 0} }; g.vexnum 6; g.arcnum 10; /* 手动数出来的改数据记得一起改 */ for (i 0; i g.vexnum; i) for (j 0; j g.vexnum; j) g.arcs[i][j] A[i][j];跑起来之后屏幕上应该出现三段输出。第一段是原矩阵每列宽 30 5 0 7 0 0 0 0 4 0 0 0 8 0 0 0 0 9 0 0 5 0 0 6 0 0 0 5 0 0 3 0 0 0 1 0第二段是矩阵转出来的邻接表。注意每行的顶点号后面跟的是出边的弧头下标按升序排0: 1 3 1: 2 2: 0 5 3: 2 5 4: 3 5: 0 4第三段是链表再转回矩阵的结果逐格跟第一段一致就说明两个转换函数都没写错。这一步的比对要一行一行看尤其是有向图把arcs[i][j]写成arcs[j][i]在不含对称边的图上会立刻露馅——比如第 0 行第 1 列是 5转置后第 1 行第 0 列也会变成 5而原图那里是 0。4.2 手动输入版本按边表读比读矩阵省事题目要求里明确说了要把程序完善成“手动输入任意图”。有两种输入形态让用户一个格子一个格子地敲矩阵或者按边的形式敲“起点 终点 权值”。前者在 10 个顶点时就要敲 100 个数字还得自己保证输的是对称或非对称的正确形状体验极差后者敲多少条边就输多少行出错概率低得多。我一般选后者int main(void) { MGraph g, g1; ALGraph *G; int i, j, n, m, u, v, w, cnt; printf(输入顶点数和弧数(空格分隔): ); if (scanf(%d%d, n, m) ! 2) return 1; /* 边界检查别让用户输个 30 把数组写穿 */ if (n 0 || n MAX_VERTEX_NUM) { printf(顶点数必须在 1~%d 之间\n, MAX_VERTEX_NUM); return 1; } g.vexnum n; for (i 0; i n; i) for (j 0; j n; j) g.arcs[i][j] 0; /* 先整体清零0 表示无边 */ printf(依次输入 %d 条弧: 起点 终点 权值\n, m); cnt 0; while (cnt m) { if (scanf(%d%d%d, u, v, w) ! 3) break; if (u 0 || u n || v 0 || v n || u v) { printf(端点非法请重新输入第 %d 条弧\n, cnt 1); continue; /* 自环按非法处理有需要可放开 */ } g.arcs[u][v] w; /* 有向图只写一个方向 */ cnt; } g.arcnum cnt; G (ALGraph *)malloc(sizeof(ALGraph)); printf(\n邻接矩阵为\n); DispMat(g); printf(矩阵转邻接表\n); MatToList(g, G); DispAdj(G); printf(邻接表转矩阵\n); ListToMat(G, g1); DispMat(g1); FreeAdj(G); /* 把边结点还回去 */ free(G); return 0; }几个参数值得说明。n和m读进来后立刻做范围校验这是防越界最省事的一道闸MAX_VERTEX_NUM是 20用户输 21 就会写到vexs[20]外面去栈上的其他变量被悄悄改写症状是后面打印的东西莫名其妙。u v的自环我按非法跳过了因为大部分教材图例里不含自环而矩阵对角线上的自环值又会被MatToList的! 0当成一条正常边建结点虽然逻辑上没错但容易跟“对角线占位”混淆初学者调试时会被绕进去。真需要自环就把这个条件去掉。改成无向图的话g.arcs[u][v] w;后面补一行g.arcs[v][u] w;MatToList那边一行都不用改因为它的判定条件是对整个矩阵扫的对称矩阵自然会在 i 和 j 两边都建出结点。这也说明转换函数本身对图的有向无向是透明的方向语义完全由矩阵承担。4.3 用一次 BFS 交叉验证转换是否等价肉眼比对 6×6 的矩阵还行换成 15 个顶点就开始眼花。更可靠的办法是让两种结构各跑一次 BFS比较输出的顶点序列是否逐位相同/* 基于邻接矩阵的 BFS */ void BFSMat(MGraph *g, int start) { int visited[MAX_VERTEX_NUM] {0}; int queue[MAX_VERTEX_NUM], front 0, rear 0; int i, v; visited[start] 1; queue[rear] start; while (front rear) { v queue[front]; printf(%d , v); for (i 0; i g-vexnum; i) /* 列小到大扫天然有序 */ if (g-arcs[v][i] ! 0 !visited[i]) { visited[i] 1; queue[rear] i; } } printf(\n); } /* 基于邻接表的 BFS */ void BFSAdj(ALGraph *G, int start) { int visited[MAX_VERTEX_NUM] {0}; int queue[MAX_VERTEX_NUM], front 0, rear 0; ArcNode *p; int v; visited[start] 1; queue[rear] start; while (front rear) { v queue[front]; printf(%d , v); for (p G-vertices[v].firstarc; p ! NULL; p p-nextarc) if (!visited[p-adjvex]) { visited[p-adjvex] 1; queue[rear] p-adjvex; } } printf(\n); }这两个函数能输出完全一致的序列靠的正是 3.1 里那个“倒序扫描 头插”让链表的出边顺序等于矩阵列下标的升序。如果当初用了正序加头插链表里出边是降序BFS 的入队顺序就变了序列对不上你会误以为转换函数有 bug回头去查一堆本来正确的代码。这个坑我在别的地方实打实翻过车所以现在写这类转换一律先定好顺序约定。用固定起点跑两个序列一致基本可以判定转换正确想更狠一点把起点从 0 遍历到vexnum-1各跑一遍。4.4 收尾把 malloc 出来的 ArcNode 还回去MatToList里每个非零元素都malloc了一个ArcNode10 条弧就是 10 次分配。程序退出时操作系统会回收但只要你把这段代码嵌进循环、或者做成菜单式反复调用的程序不释放就是实打实的泄漏void FreeAdj(ALGraph *G) { int i; ArcNode *p, *q; for (i 0; i G-vexnum; i) { p G-vertices[i].firstarc; while (p ! NULL) { q p-nextarc; /* 先存下一个否则 free 完就丢链了 */ free(p); p q; } G-vertices[i].firstarc NULL; /* 置空防止二次释放 */ } }q p-nextarc;这一行顺序不能反先free(p)再去读p-nextarc就是访问已释放内存-g编译后配合内存检查工具会直接报错。释放完把firstarc置空是好习惯下次同一个ALGraph复用给MatToList时即使漏了初始化那段也不会串到已释放的结点上——当然初始化还是不能省。5. 排查清单这套转换代码最容易翻车的五个地方下面这五条基本覆盖了这类图存储实验里 90% 的报错和“输出不对但能跑”的情况。每条按现象、原因、改法的顺序写对着自查能省不少时间。5.1 数据层的三个坑坑一转换后邻接表里出现了本该不存在的边或者漏了边。现象是DispAdj打出来的链表比预期长或短尤其是带权图里权值恰好为 0 的那些边直接消失。原因在MatToList里的if (g-arcs[i][j] ! 0)它把 0 当成“没有弧”可带权图里 0 完全可能是一个合法的权值而无权图里又习惯用 0 表示无边、1 表示有边两套语义混在一份代码里。更糟的是同一份文件里还定义着INF 32767DispMat按 INF 判无边转换函数按 0 判无边两个函数对“什么算边”的判断根本不一致。改法是先把哨兵定死全文件统一。无权图用 0/1那DispMat里 INF 那条分支删掉带权图用INF表示无边、任意整数含 0表示权值那MatToList的判定改成! INFListToMat的清零那层改成填INFMatToList里p-info照搬。改的时候四个函数一起改只改一半比不改还危险。坑二DispAdj输出少了几行孤立点直接不见了。现象是 6 个顶点的图只打出 5 行对着编号数会发现缺的那个顶点没有任何出边。原因在DispAdj里printf(%3d:, i)被包在if (p ! NULL)里面出度为 0 的顶点连自己的编号都不打印。这个坑很阴因为程序没崩多数人第一反应是“转换函数漏建了顶点”跑去MatToList里加打印查半天结果那边完全正常。改法是把顶点号那行提到if外面for (i 0; i G-vexnum; i) { printf(%3d:, i); /* 每行必打顶点号 */ for (p G-vertices[i].firstarc; p ! NULL; p p-nextarc) printf(%3d, p-adjvex); printf(\n); }坑三手动输入时顶点数输大了程序直接崩或者输出乱码。现象是输入 25 个顶点后段错误或者程序继续跑但打印出来的矩阵尺寸不对。原因是MAX_VERTEX_NUM是 20vexs和arcs都按 20 开代码里没有任何一处校验输入scanf读到 25 就直接拿去当循环边界后面写g.arcs[i][j]的时候一路写到数组外面的栈内存上。这类越界最麻烦的地方是它不立刻崩——被覆盖的可能是别的局部变量等到后面某个时刻才以奇怪的方式炸出来。改法是在读完n之后立刻拦一道if (n 0 || n MAX_VERTEX_NUM)把非法输入挡在写内存之前。弧数m也顺手校验一下上限n*(n-1)有向图不含自环的情况防止用户多敲几行导致数组越界。5.2 编译与内存层的两个坑坑四ListToMat编译报警告某些编译器下链接直接失败。现象是 GCC 加-Wall后报return type defaults to int换成更严格的 C 标准编译时报错。原因是函数定义写成了ListToMat(ALGraph *G, MGraph *g)前面既没有void也没有intC89 会隐式补成int但函数体里没有return调用方拿到的返回值是垃圾。这份代码在旧编译器上能跑换环境就挂。改法很简单函数头补void。同一份代码里其他函数都写了返回类型就这一个漏了属于抄教材时的常见遗漏。养成开-Wall -Wextra编译的习惯这类问题第一遍就能暴露。坑五反复调用转换函数后内存占用一路上涨或者退出时崩溃。现象是做成菜单式循环转换一次打印一次然后回到菜单之后每转一次内存就涨一点或者程序结束时报 double free。原因是MatToList每次调用都重新malloc一批ArcNode挂到G-vertices上但第一段初始化只置空了firstarc没释放上一次挂上去的链——旧结点全成了内存空洞。另一种情况是free(G)之后又把G传给MatToList那是访问已释放内存。改法是在MatToList开头先调一次FreeAdj(G)把旧链清掉再置空重建free(G)之后立刻把指针置NULL。这个改法在只调用一次的场景里看不出差别但只要程序有循环就必须加。6. 二次开发把这套实验代码改成能用的图工具这份代码作为实验作业是完整的但要拿去当工具用头一个卡点是那两行#define MAX_VERTEX_NUM 20。真实数据动不动几百个顶点20 这个上限太窄。我一般把arcs换成二级指针动态开vexs换成VertexType *ALGraph的vertices也一起换/* 动态版本n 由输入决定不再写死 20 */ g-arcs (int **)malloc(n * sizeof(int *)); for (i 0; i n; i) { g-arcs[i] (int *)malloc(n * sizeof(int)); for (j 0; j n; j) g-arcs[i][j] 0; } /* 释放时反过来先放每一行再放行指针数组 */ for (i 0; i n; i) free(g-arcs[i]); free(g-arcs);改动集中在分配和释放两处MatToList、ListToMat的循环体一行不动因为arcs[i][j]的写法在二级指针和二维数组上语法完全一致。风险在释放顺序行指针和行数组必须成对释放漏一层就是泄漏释放顺序反了就是崩溃。第二个改造点是统一哨兵。第 5 章坑一讲过0 和 INF 混用是这套代码最深的隐患。我倾向改成矩阵初值统一填INFMatToList判! INFListToMat清零时填INFDispMat判INF打---。这样带权图里权值 0 也能正常表示无向图只是在g-arcs[u][v]和g-arcs[v][u]各写一次。改造点涉及位置主要风险顶点数改为动态main分配、FreeAdj后的释放释放顺序与层数要配对哨兵统一为 INFMatToList、ListToMat、DispMat四处必须同步改改一半更危险支持无向图输入段写双向边数统计翻倍arcnum别忘同步加带权打印DispAdj里加p-info输出宽度变化列对齐要调第三个改造点是我最推荐的把第 4.3 节那两个 BFS 加成常驻的自检函数做成一个Verify(MGraph *g, ALGraph *G)内部对每个起点跑两遍 BFS 比对序列不一致就打印是哪个起点、哪一位开始分叉。这样后面无论你怎么改哨兵、怎么改输入方式跑一次自检就知道有没有改坏。有次我改哨兵值改到一半去接了个电话回来接着改ListToMat自检一跑立马发现矩阵版本把INF当成边建了结点——两个 BFS 序列长度都不一样。从那以后我每次动这类“一个数据结构转另一个”的代码都强制先让Verify跑一遍再谈别的比对肉眼看矩阵靠谱得多。这套代码的价值不在于 40 行转换逻辑本身而在于它把两种存储的字段语义、遍历顺序、哨兵约定、内存归属全摊开摆在一份能编译的文件里改哪一处、影响哪几个函数边界清清楚楚。把第 5 章那五个坑逐一改掉再加一个自检函数它就已经是个能塞进小项目里用的图存储模块了。希望帮到你。本文还有配套的精品资源点击获取