简介这份资源面向正在学习数据结构、需要掌握图存储结构转换的初学者与在校学生聚焦图的邻接矩阵与邻接表两种存储方式及其相互转换。内容围绕有向图展开包含邻接矩阵的二维数组表示、邻接表的链表节点结构以及MatToList、ListToMat、DispMat、DispAdj等核心函数的实现思路并支持手动输入图信息完成两种存储方式的互换可帮助读者理解稀疏图与稠密图下的空间与查询效率差异。资源包共1个docx文件约55KB以实验报告形式组织涵盖实验目的、问题描述、程序要求与完整C语言源码便于对照阅读与上机调试。目前已有8614人学习适合作为数据结构课程实验的参考材料也可用于巩固动态内存分配、链表遍历与矩阵操作等编程基本功为后续网络路由、社交网络分析等图算法应用打下基础。1. 从一份“能跑但不敢改”的 C 代码说起很多同学第一次接触图的存储都是在数据结构课上拿到一份能编译、能打印、但一改就崩的 C 代码。这份资源就是这样一个典型样本它用纯 C 实现了有向图的邻接矩阵与邻接表双向转换包含矩阵打印、链表头插建表、链表回填矩阵四个核心函数外加一个硬编码 6 顶点 10 弧的测试用例。适合正在做图论实验、需要交作业或想搞懂“矩阵和链表到底怎么互转”的开发者。代码不长但里面藏着几个新手必踩的坑比如INF和0的语义混用、头插法导致的逆序输出、以及ListToMat漏写返回类型。把它跑通不难难的是看懂每一行在干什么然后改成能手动输入任意图的版本。2. 项目定位与技术选型为什么是纯 C 加两个结构体2.1 这份代码解决的是什么问题图的存储方式选择本质上是空间和查询效率的权衡。邻接矩阵用二维数组arcs[i][j]表示顶点 i 到 j 的边查询 O(1)但空间固定为 O(n²)稀疏图浪费严重。邻接表给每个顶点挂一条边链表空间 O(ne)遍历某顶点的邻接点很快但判断两点是否直接相连要扫链表。这份资源的核心价值不是教你背定义而是给出一个可运行的转换器矩阵转链表用MatToList链表转矩阵用ListToMat两个方向都落地成代码你能直接看到数据结构在内存里怎么变形。从工程角度看它选纯 C 而不是 C是因为图的存储结构本身就是指针和数组的组合用 C 能把ArcNode的nextarc指针、AdjList的数组套链表关系暴露得最清楚。没有 STL 的vector或list帮你兜底每一块malloc都得自己管这恰恰是理解邻接表内存布局的最好方式。代码里用typedef int VertexType和typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]把类型抽象出来换顶点数据类型时只改一处这个习惯值得保留。2.2 两个核心结构体的字段含义先看矩阵侧的结构体#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;vexs存顶点本身的信息这份代码里其实没怎么用因为测试用例只关心边的权值。arcs是核心arcs[i][j]非零表示 i 到 j 有边值就是权。vexnum和arcnum是元数据转换时必须同步过去否则打印和后续遍历会越界或漏边。再看邻接表侧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; // 顶点数组每个元素挂一条边链表 int vexnum, arcnum; } ALGraph;AdjList是VNode的数组类型vertices[i].firstarc指向顶点 i 的第一条出边。ArcNode里的adjvex是目标顶点下标info是权值nextarc串起同起点的其他边。这里有个细节info在矩阵转链表时直接抄arcs[i][j]所以链表里存的也是权值不是简单的 0/1。2.3 转换的算法骨架矩阵转链表的逻辑是外层遍历每个顶点 i内层从n-1倒着扫到 0遇到arcs[i][j] ! 0就malloc一个ArcNode用头插法挂到vertices[i].firstarc上。倒序扫描加头插最终链表顺序正好是 j 从小到大这是个巧妙的写法后面会细讲。链表转矩阵更直接先把g-arcs全部清零然后遍历每个顶点 i 的边链表把p-info写到g-arcs[i][p-adjvex]最后同步vexnum和arcnum。两个方向都不需要额外的辅助空间时间复杂度分别是 O(n²) 和 O(ne)。提示MAX_VERTEX_NUM定成 20 是实验课的常见上限实际改图规模时记得同步改这个宏否则数组越界不会报错只会悄悄踩坏别的内存。3. 跑起来编译、测试用例与输出解读3.1 编译命令与文件组织这份代码是单文件结构所有函数和main都在一个.c里。新建graph_convert.c把正文里的代码原样贴进去用 GCC 编译gcc graph_convert.c -o graph_convert -Wall ./graph_convert加-Wall是为了让编译器把隐式声明和未使用变量揪出来。原代码里ListToMat没写返回类型老编译器会默认int新标准下会报警告加上-Wall你能第一时间看到。如果用的是 Visual Studio把scanf相关的安全警告忽略掉即可这份代码目前还没用到scanf但后面改手动输入时会遇到。3.2 硬编码测试用例长什么样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} };第 0 行有到 1 的权 5、到 3 的权 7第 2 行有到 0 的权 8、到 5 的权 9第 5 行有到 0 的权 3、到 4 的权 1。arcnum写死为 10数一下非零元素正好 10 个对得上。这个用例的好处是既有跨行跨列的边又有不同权值转换后容易核对。3.3 输出怎么读程序先打印原矩阵DispMat遇到INF打---否则打数值。注意这里有个语义陷阱矩阵里 0 表示“无边”INF表示“不可达”但测试用例里根本没有INF所以---永远不会出现。打印出来是规整的 6×6 数字阵。接着MatToList建表DispAdj打印邻接表格式是顶点下标: 邻接点1 邻接点2 ...。因为用了倒序扫描加头插顶点 0 的链表输出应该是1 3而不是3 1这个顺序和矩阵从左到右扫非零元素的顺序一致方便肉眼比对。最后ListToMat把链表回填到g1再DispMat打印。正常情况下g1的矩阵应该和原矩阵一模一样这是验证转换正确性的最直接方法。如果两次打印不一致说明ListToMat的清零或回填有漏。注意原代码main末尾有getchar()在终端里会停住等你按回车这是老式控制台程序防止窗口一闪而过的习惯。用 IDE 运行时如果卡住不动按一下回车就退出了。3.4 手动输入版本的改造入口实验要求里明确提到“手动输入任意图形”原代码只做了硬编码。改造点集中在main开头先scanf读vexnum和arcnum再用双重循环读arcs[i][j]或者按“起点 终点 权值”的三元组读arcnum条边。前者适合稠密图后者适合稀疏图且更符合直觉。读完之后把后续的MatToList、DispAdj、ListToMat、DispMat原样调用即可转换逻辑一行都不用动。这个改造留到最后一章细说。4. 核心函数拆解四个函数撑起双向转换4.1 DispMat打印矩阵时 INF 和 0 的语义要分清#define INF 32767 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); } }这个函数只做展示但暴露了一个设计上的模糊点INF被定义成 32767用来表示“两顶点不可达”而 0 表示“没有边”。在无权图里这两个概念可以合并但在带权图里它们是不同的——0 权边是合法的不可达才是INF。这份代码的测试用例全用 0 表示无边所以INF分支是死代码。如果你要扩展成带权图且允许 0 权边必须把“无边”的表示从 0 改成INF同时改MatToList里的判断条件g-arcs[i][j] ! 0为! INF否则 0 权边会被漏掉。%3d和%3s的宽度 3 是为了对齐顶点数多了之后数字变宽会错位可以改成%4d。4.2 MatToList倒序扫描加头插顺序才对void MatToList(MGraph *g, ALGraph *G) { int i, j, n g-vexnum; ArcNode *p; 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) { 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; }逐段看。第一个循环把firstarc全部置空这是必须的因为G是malloc出来的里面的指针是脏值不清空后面头插会挂到野指针上。第二个循环外层按行扫内层从n-1倒着扫到 0。为什么倒序因为头插法会把后插入的节点放到链表最前面。如果正序扫描顶点 0 的边1, 3会变成链表3 - 1打印出来是3 1和矩阵从左到右的顺序相反核对时容易看花眼。倒序扫描后先处理j3插到头部再处理j1插到头部最终链表是1 - 3正好还原矩阵顺序。这个技巧在链表建表里很常见血泪经验是只要用头插又想保持原序就倒着遍历。malloc之后没有检查返回值实验代码可以接受但生产代码里p NULL时应该报错退出否则后面解引用直接崩。G-arcnum g-arcnum直接抄过来前提是矩阵里的非零元素个数确实等于arcnum如果手动输入时数错了这里不会帮你纠正打印出来的弧数是错的但链表是对的排查时容易懵。4.3 DispAdj打印邻接表时 NULL 头的处理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); } }这个函数有个小瑕疵如果某个顶点没有出边p NULLif不成立但后面的printf(\n)照样执行输出一个空行。对于出度为 0 的顶点你看到的是空白行而不是顶点: 无读起来不直观。改进方法是在else分支打印printf(%3d: 无\n, i)或者统一先打顶点号再判断。另外它只打印adjvex不打印info带权图调试时看不到权值建议改成printf(%d(%d) , p-adjvex, p-info)把目标顶点和权值一起打出来。4.4 ListToMat清零、回填、同步元数据void ListToMat(ALGraph *G, MGraph *g) { int i, j, n G-vexnum; ArcNode *p; 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; // 按链表回填 p p-nextarc; } } g-vexnum n; g-arcnum G-arcnum; }清零这一步不能省。g如果是栈上变量arcs里是随机值不清零的话没边的位置会残留垃圾数据打印出来一堆莫名其妙的数字。回填时g-arcs[i][p-adjvex] p-info直接覆盖因为邻接表里每个(i, adjvex)对最多出现一次不会冲突。如果图里有重边同一对顶点多条边邻接表能存多条但矩阵只能存一条后写的会覆盖先写的这是矩阵表示的固有局限转换前要心里有数。原代码这个函数没写返回类型严格说是隐式intC99 之后不建议这么写。补上void即可不影响逻辑。另外g-arcnum G-arcnum同样依赖元数据准确如果链表是手动建的而arcnum没数对矩阵的弧数字段就是错的但矩阵内容本身是对的。5. 避坑与排查五个真实会卡住你的点5.1 打印出---但图里明明有边现象DispMat输出里出现---但对照测试用例那个位置应该有数值。原因INF被定义成 32767而某条边的权值恰好被误写成 32767或者手动输入时把“无边”填成了INF而MatToList判断的是! 0导致INF被当成合法边建进链表回填后矩阵里出现 32767打印成---。解决统一“无边”的表示要么全用 0无权图要么全用INF带权图并把MatToList的判断条件跟着改。改完在两个方向各打印一次核对。5.2 邻接表打印顺序和矩阵对不上现象矩阵第 0 行非零列是 1、3邻接表却打印3 1。原因MatToList内层用了正序扫描加头插后插入的 3 跑到了链表头。解决把内层循环改成for (j n - 1; j 0; j--)倒序扫描或者改用尾插法多维护一个尾指针。倒序改一行就够尾插要改结构实验场景选前者。5.3 程序跑完输出一堆乱码或直接崩现象DispAdj打印出巨大数字或段错误。原因ALGraph *G用malloc分配后没有初始化vertices[i].firstarc里面是脏指针MatToList虽然清了firstarc但如果G是在别处复用且没重新清空或者malloc失败返回 NULL 没检查就会解引用野指针。解决malloc后立刻memset(G, 0, sizeof(ALGraph))或手动循环置空并检查G ! NULL。养成“分配即初始化”的习惯这类玄学崩溃能少一大半。5.4 手动输入后弧数对但矩阵少边现象输入了 10 条边arcnum显示 10但转换后的矩阵非零元素只有 8 个。原因手动输入时同一对顶点输了两次重边邻接表存了两条回填矩阵时后一条覆盖前一条矩阵只剩一条但arcnum还是 10。解决输入阶段用矩阵暂存并判重或者接受这个差异但在文档里说明“矩阵表示不支持重边”。实验报告里写清楚这个限制比藏着掖着强。5.5 换编译器后ListToMat报隐式声明错误现象GCC 加-Wall提示implicit declaration of function ListToMat或者链接时报未定义。原因原代码ListToMat定义时没写返回类型老编译器默认int新标准或 C 编译器直接拒绝。解决在函数定义前补void并在main之前加函数原型声明void ListToMat(ALGraph *G, MGraph *g);。顺手把main的void main(void)改成标准的int main(void)并在末尾return 0;跨平台兼容性更好。6. 二次开发把手动输入和释放内存补上改造的第一步是把硬编码换成手动输入。我一般会在main开头加这么一段int n, m, i, j, u, v, w; printf(输入顶点数和弧数: ); scanf(%d %d, n, m); g.vexnum n; g.arcnum m; for (i 0; i n; i) for (j 0; j n; j) g.arcs[i][j] 0; // 先全部置无边 printf(输入每条边: 起点 终点 权值\n); for (i 0; i m; i) { scanf(%d %d %d, u, v, w); g.arcs[u][v] w; // 有向图只填一个方向 }这段代码的关键是先把矩阵清零再按三元组填边适合稀疏图输入也避免了让用户对着 n×n 个位置一个个填 0。有向图只填arcs[u][v]无向图要对称填arcs[v][u] w改一行就能切换。输入完直接走原来的MatToList、DispAdj、ListToMat、DispMat四连转换逻辑零改动。第二步是补内存释放。原代码malloc出来的ArcNode和ALGraph从头到尾没free实验课跑一次就退出无所谓但如果你要把它嵌进循环里反复转换不释放会持续泄漏。释放邻接表的写法void DestroyAdj(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(p); // 先存下一个再释放当前 p q; } G-vertices[i].firstarc NULL; } }这里有个顺序陷阱不能先free(p)再读p-nextarc释放后的内存内容不可靠。必须先q p-nextarc把下一个节点存下来再free(p)然后p q。这个模式在链表释放里是标准写法翻车过一次就记住了。验证改造是否成功我习惯用一个小规模图做回归3 个顶点、3 条边矩阵和链表各打印一次肉眼比对再跑一次“矩阵→链表→矩阵”确认两次矩阵完全一致。如果一致说明双向转换闭环没问题如果不一致优先查ListToMat的清零和MatToList的判断条件。这套流程走下来这份实验代码就从“能跑”变成了“能改、能扩、能放心交给别人看”。从那以后我每次改这种结构转换代码都强制自己先跑一遍“原样→转换→转回→比对”的闭环再动别的逻辑。希望帮到你。本文还有配套的精品资源点击获取 C语言实现图的邻接矩阵与邻接表双向转换：原理、代码与避坑指南
简介这份资源面向正在学习数据结构、需要掌握图存储结构转换的初学者与在校学生聚焦图的邻接矩阵与邻接表两种存储方式及其相互转换。内容围绕有向图展开包含邻接矩阵的二维数组表示、邻接表的链表节点结构以及MatToList、ListToMat、DispMat、DispAdj等核心函数的实现思路并支持手动输入图信息完成两种存储方式的互换可帮助读者理解稀疏图与稠密图下的空间与查询效率差异。资源包共1个docx文件约55KB以实验报告形式组织涵盖实验目的、问题描述、程序要求与完整C语言源码便于对照阅读与上机调试。目前已有8614人学习适合作为数据结构课程实验的参考材料也可用于巩固动态内存分配、链表遍历与矩阵操作等编程基本功为后续网络路由、社交网络分析等图算法应用打下基础。1. 从一份“能跑但不敢改”的 C 代码说起很多同学第一次接触图的存储都是在数据结构课上拿到一份能编译、能打印、但一改就崩的 C 代码。这份资源就是这样一个典型样本它用纯 C 实现了有向图的邻接矩阵与邻接表双向转换包含矩阵打印、链表头插建表、链表回填矩阵四个核心函数外加一个硬编码 6 顶点 10 弧的测试用例。适合正在做图论实验、需要交作业或想搞懂“矩阵和链表到底怎么互转”的开发者。代码不长但里面藏着几个新手必踩的坑比如INF和0的语义混用、头插法导致的逆序输出、以及ListToMat漏写返回类型。把它跑通不难难的是看懂每一行在干什么然后改成能手动输入任意图的版本。2. 项目定位与技术选型为什么是纯 C 加两个结构体2.1 这份代码解决的是什么问题图的存储方式选择本质上是空间和查询效率的权衡。邻接矩阵用二维数组arcs[i][j]表示顶点 i 到 j 的边查询 O(1)但空间固定为 O(n²)稀疏图浪费严重。邻接表给每个顶点挂一条边链表空间 O(ne)遍历某顶点的邻接点很快但判断两点是否直接相连要扫链表。这份资源的核心价值不是教你背定义而是给出一个可运行的转换器矩阵转链表用MatToList链表转矩阵用ListToMat两个方向都落地成代码你能直接看到数据结构在内存里怎么变形。从工程角度看它选纯 C 而不是 C是因为图的存储结构本身就是指针和数组的组合用 C 能把ArcNode的nextarc指针、AdjList的数组套链表关系暴露得最清楚。没有 STL 的vector或list帮你兜底每一块malloc都得自己管这恰恰是理解邻接表内存布局的最好方式。代码里用typedef int VertexType和typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]把类型抽象出来换顶点数据类型时只改一处这个习惯值得保留。2.2 两个核心结构体的字段含义先看矩阵侧的结构体#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;vexs存顶点本身的信息这份代码里其实没怎么用因为测试用例只关心边的权值。arcs是核心arcs[i][j]非零表示 i 到 j 有边值就是权。vexnum和arcnum是元数据转换时必须同步过去否则打印和后续遍历会越界或漏边。再看邻接表侧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; // 顶点数组每个元素挂一条边链表 int vexnum, arcnum; } ALGraph;AdjList是VNode的数组类型vertices[i].firstarc指向顶点 i 的第一条出边。ArcNode里的adjvex是目标顶点下标info是权值nextarc串起同起点的其他边。这里有个细节info在矩阵转链表时直接抄arcs[i][j]所以链表里存的也是权值不是简单的 0/1。2.3 转换的算法骨架矩阵转链表的逻辑是外层遍历每个顶点 i内层从n-1倒着扫到 0遇到arcs[i][j] ! 0就malloc一个ArcNode用头插法挂到vertices[i].firstarc上。倒序扫描加头插最终链表顺序正好是 j 从小到大这是个巧妙的写法后面会细讲。链表转矩阵更直接先把g-arcs全部清零然后遍历每个顶点 i 的边链表把p-info写到g-arcs[i][p-adjvex]最后同步vexnum和arcnum。两个方向都不需要额外的辅助空间时间复杂度分别是 O(n²) 和 O(ne)。提示MAX_VERTEX_NUM定成 20 是实验课的常见上限实际改图规模时记得同步改这个宏否则数组越界不会报错只会悄悄踩坏别的内存。3. 跑起来编译、测试用例与输出解读3.1 编译命令与文件组织这份代码是单文件结构所有函数和main都在一个.c里。新建graph_convert.c把正文里的代码原样贴进去用 GCC 编译gcc graph_convert.c -o graph_convert -Wall ./graph_convert加-Wall是为了让编译器把隐式声明和未使用变量揪出来。原代码里ListToMat没写返回类型老编译器会默认int新标准下会报警告加上-Wall你能第一时间看到。如果用的是 Visual Studio把scanf相关的安全警告忽略掉即可这份代码目前还没用到scanf但后面改手动输入时会遇到。3.2 硬编码测试用例长什么样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} };第 0 行有到 1 的权 5、到 3 的权 7第 2 行有到 0 的权 8、到 5 的权 9第 5 行有到 0 的权 3、到 4 的权 1。arcnum写死为 10数一下非零元素正好 10 个对得上。这个用例的好处是既有跨行跨列的边又有不同权值转换后容易核对。3.3 输出怎么读程序先打印原矩阵DispMat遇到INF打---否则打数值。注意这里有个语义陷阱矩阵里 0 表示“无边”INF表示“不可达”但测试用例里根本没有INF所以---永远不会出现。打印出来是规整的 6×6 数字阵。接着MatToList建表DispAdj打印邻接表格式是顶点下标: 邻接点1 邻接点2 ...。因为用了倒序扫描加头插顶点 0 的链表输出应该是1 3而不是3 1这个顺序和矩阵从左到右扫非零元素的顺序一致方便肉眼比对。最后ListToMat把链表回填到g1再DispMat打印。正常情况下g1的矩阵应该和原矩阵一模一样这是验证转换正确性的最直接方法。如果两次打印不一致说明ListToMat的清零或回填有漏。注意原代码main末尾有getchar()在终端里会停住等你按回车这是老式控制台程序防止窗口一闪而过的习惯。用 IDE 运行时如果卡住不动按一下回车就退出了。3.4 手动输入版本的改造入口实验要求里明确提到“手动输入任意图形”原代码只做了硬编码。改造点集中在main开头先scanf读vexnum和arcnum再用双重循环读arcs[i][j]或者按“起点 终点 权值”的三元组读arcnum条边。前者适合稠密图后者适合稀疏图且更符合直觉。读完之后把后续的MatToList、DispAdj、ListToMat、DispMat原样调用即可转换逻辑一行都不用动。这个改造留到最后一章细说。4. 核心函数拆解四个函数撑起双向转换4.1 DispMat打印矩阵时 INF 和 0 的语义要分清#define INF 32767 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); } }这个函数只做展示但暴露了一个设计上的模糊点INF被定义成 32767用来表示“两顶点不可达”而 0 表示“没有边”。在无权图里这两个概念可以合并但在带权图里它们是不同的——0 权边是合法的不可达才是INF。这份代码的测试用例全用 0 表示无边所以INF分支是死代码。如果你要扩展成带权图且允许 0 权边必须把“无边”的表示从 0 改成INF同时改MatToList里的判断条件g-arcs[i][j] ! 0为! INF否则 0 权边会被漏掉。%3d和%3s的宽度 3 是为了对齐顶点数多了之后数字变宽会错位可以改成%4d。4.2 MatToList倒序扫描加头插顺序才对void MatToList(MGraph *g, ALGraph *G) { int i, j, n g-vexnum; ArcNode *p; 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) { 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; }逐段看。第一个循环把firstarc全部置空这是必须的因为G是malloc出来的里面的指针是脏值不清空后面头插会挂到野指针上。第二个循环外层按行扫内层从n-1倒着扫到 0。为什么倒序因为头插法会把后插入的节点放到链表最前面。如果正序扫描顶点 0 的边1, 3会变成链表3 - 1打印出来是3 1和矩阵从左到右的顺序相反核对时容易看花眼。倒序扫描后先处理j3插到头部再处理j1插到头部最终链表是1 - 3正好还原矩阵顺序。这个技巧在链表建表里很常见血泪经验是只要用头插又想保持原序就倒着遍历。malloc之后没有检查返回值实验代码可以接受但生产代码里p NULL时应该报错退出否则后面解引用直接崩。G-arcnum g-arcnum直接抄过来前提是矩阵里的非零元素个数确实等于arcnum如果手动输入时数错了这里不会帮你纠正打印出来的弧数是错的但链表是对的排查时容易懵。4.3 DispAdj打印邻接表时 NULL 头的处理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); } }这个函数有个小瑕疵如果某个顶点没有出边p NULLif不成立但后面的printf(\n)照样执行输出一个空行。对于出度为 0 的顶点你看到的是空白行而不是顶点: 无读起来不直观。改进方法是在else分支打印printf(%3d: 无\n, i)或者统一先打顶点号再判断。另外它只打印adjvex不打印info带权图调试时看不到权值建议改成printf(%d(%d) , p-adjvex, p-info)把目标顶点和权值一起打出来。4.4 ListToMat清零、回填、同步元数据void ListToMat(ALGraph *G, MGraph *g) { int i, j, n G-vexnum; ArcNode *p; 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; // 按链表回填 p p-nextarc; } } g-vexnum n; g-arcnum G-arcnum; }清零这一步不能省。g如果是栈上变量arcs里是随机值不清零的话没边的位置会残留垃圾数据打印出来一堆莫名其妙的数字。回填时g-arcs[i][p-adjvex] p-info直接覆盖因为邻接表里每个(i, adjvex)对最多出现一次不会冲突。如果图里有重边同一对顶点多条边邻接表能存多条但矩阵只能存一条后写的会覆盖先写的这是矩阵表示的固有局限转换前要心里有数。原代码这个函数没写返回类型严格说是隐式intC99 之后不建议这么写。补上void即可不影响逻辑。另外g-arcnum G-arcnum同样依赖元数据准确如果链表是手动建的而arcnum没数对矩阵的弧数字段就是错的但矩阵内容本身是对的。5. 避坑与排查五个真实会卡住你的点5.1 打印出---但图里明明有边现象DispMat输出里出现---但对照测试用例那个位置应该有数值。原因INF被定义成 32767而某条边的权值恰好被误写成 32767或者手动输入时把“无边”填成了INF而MatToList判断的是! 0导致INF被当成合法边建进链表回填后矩阵里出现 32767打印成---。解决统一“无边”的表示要么全用 0无权图要么全用INF带权图并把MatToList的判断条件跟着改。改完在两个方向各打印一次核对。5.2 邻接表打印顺序和矩阵对不上现象矩阵第 0 行非零列是 1、3邻接表却打印3 1。原因MatToList内层用了正序扫描加头插后插入的 3 跑到了链表头。解决把内层循环改成for (j n - 1; j 0; j--)倒序扫描或者改用尾插法多维护一个尾指针。倒序改一行就够尾插要改结构实验场景选前者。5.3 程序跑完输出一堆乱码或直接崩现象DispAdj打印出巨大数字或段错误。原因ALGraph *G用malloc分配后没有初始化vertices[i].firstarc里面是脏指针MatToList虽然清了firstarc但如果G是在别处复用且没重新清空或者malloc失败返回 NULL 没检查就会解引用野指针。解决malloc后立刻memset(G, 0, sizeof(ALGraph))或手动循环置空并检查G ! NULL。养成“分配即初始化”的习惯这类玄学崩溃能少一大半。5.4 手动输入后弧数对但矩阵少边现象输入了 10 条边arcnum显示 10但转换后的矩阵非零元素只有 8 个。原因手动输入时同一对顶点输了两次重边邻接表存了两条回填矩阵时后一条覆盖前一条矩阵只剩一条但arcnum还是 10。解决输入阶段用矩阵暂存并判重或者接受这个差异但在文档里说明“矩阵表示不支持重边”。实验报告里写清楚这个限制比藏着掖着强。5.5 换编译器后ListToMat报隐式声明错误现象GCC 加-Wall提示implicit declaration of function ListToMat或者链接时报未定义。原因原代码ListToMat定义时没写返回类型老编译器默认int新标准或 C 编译器直接拒绝。解决在函数定义前补void并在main之前加函数原型声明void ListToMat(ALGraph *G, MGraph *g);。顺手把main的void main(void)改成标准的int main(void)并在末尾return 0;跨平台兼容性更好。6. 二次开发把手动输入和释放内存补上改造的第一步是把硬编码换成手动输入。我一般会在main开头加这么一段int n, m, i, j, u, v, w; printf(输入顶点数和弧数: ); scanf(%d %d, n, m); g.vexnum n; g.arcnum m; for (i 0; i n; i) for (j 0; j n; j) g.arcs[i][j] 0; // 先全部置无边 printf(输入每条边: 起点 终点 权值\n); for (i 0; i m; i) { scanf(%d %d %d, u, v, w); g.arcs[u][v] w; // 有向图只填一个方向 }这段代码的关键是先把矩阵清零再按三元组填边适合稀疏图输入也避免了让用户对着 n×n 个位置一个个填 0。有向图只填arcs[u][v]无向图要对称填arcs[v][u] w改一行就能切换。输入完直接走原来的MatToList、DispAdj、ListToMat、DispMat四连转换逻辑零改动。第二步是补内存释放。原代码malloc出来的ArcNode和ALGraph从头到尾没free实验课跑一次就退出无所谓但如果你要把它嵌进循环里反复转换不释放会持续泄漏。释放邻接表的写法void DestroyAdj(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(p); // 先存下一个再释放当前 p q; } G-vertices[i].firstarc NULL; } }这里有个顺序陷阱不能先free(p)再读p-nextarc释放后的内存内容不可靠。必须先q p-nextarc把下一个节点存下来再free(p)然后p q。这个模式在链表释放里是标准写法翻车过一次就记住了。验证改造是否成功我习惯用一个小规模图做回归3 个顶点、3 条边矩阵和链表各打印一次肉眼比对再跑一次“矩阵→链表→矩阵”确认两次矩阵完全一致。如果一致说明双向转换闭环没问题如果不一致优先查ListToMat的清零和MatToList的判断条件。这套流程走下来这份实验代码就从“能跑”变成了“能改、能扩、能放心交给别人看”。从那以后我每次改这种结构转换代码都强制自己先跑一遍“原样→转换→转回→比对”的闭环再动别的逻辑。希望帮到你。本文还有配套的精品资源点击获取