企业官网建设流程全解析

简介：这份文档面向正在学习数据结构、需要攻克图存储难点的学生与编程初学者，聚焦图的邻接矩阵与邻接表两种存储结构及其相互转换。内容围绕有向图展开，先讲邻接矩阵的二维数组表示与对称性特点，再讲邻接表以链表节省空间的优势，并给出C语言中AdjMatrix、AdjList、ArcNode等类型定义，以及DispMat、MatToList、DispAdj、ListToMat等核心函数的实现思路，还涉及动态内存分配与释放、手动输入图信息等实践要点。资源包共1个docx文件，约55KB，篇幅精炼，适合作为实验报告参考或课程作业辅助材料。目前已有8613人学习，说明该知识点需求广泛。读者可借此理清两种存储方式的转换流程，理解稀疏图与稠密图的选型依据，并对照代码加深对图结构在路由、社交网络分析等场景中应用的认识。

1. 从一份“能跑但不敢改”的 C 代码说起

很多同学在数据结构课设里第一次接触图的存储，拿到的就是一份能编译、能打印、但一改就崩的 C 代码。这份资源正是围绕“图的邻接矩阵和邻接表存储”展开的完整实验程序：它把同一个有向图分别用二维数组和链表两种方式存进内存，再实现双向转换，最后把结果打印出来对照。适合正在做图论实验、需要交课程设计，或者想彻底搞懂这两种存储结构到底怎么互转的开发者。代码不长，但里面藏着几个新手必踩的坑，比如头插法导致的顺序反转、INF和0的语义混淆、以及邻接表转矩阵时忘记清零。接下来我按“先看懂结构、再跑起来、最后能改”的顺序把它拆开讲。

2. 结构拆解：两种存储类型与四个核心函数

2.1 邻接矩阵与邻接表的数据类型定义

这份代码最值得先看的是类型定义，因为它决定了后面所有函数的操作方式。邻接矩阵用AdjMatrix这个二维数组类型承载，外层再包一个MGraph结构体，把顶点表、矩阵、顶点数、弧数捆在一起。邻接表这边则是经典的“顶点数组 + 边链表”组合：VNode存顶点数据和指向第一条边的指针，ArcNode存邻接点下标、权值和下一条边的指针，ALGraph再把顶点数组和计数包起来。

#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; // 邻接矩阵，arcs[i][j] 表示 i 到 j 的权 int vexnum, arcnum; // 顶点数、弧数 } MGraph; 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;

这里有几个参数需要留意。MAX_VERTEX_NUM固定为 20，意味着这份代码只能处理不超过 20 个顶点的图，超过就会越界，这是实验代码的常见简化。arcs[i][j]存的是权值，0表示没有边，INF（定义为 32767）在打印时被当作“无穷”显示成---。注意0和INF在这份代码里语义并不统一：矩阵初始化用0表示无边，但DispMat又把INF单独处理，实际运行时如果矩阵里混入INF，转换函数MatToList的判断条件g->arcs[i][j] != 0会把INF也当成一条边，这是一个隐藏的语义冲突，后面避坑章节会展开。

邻接表这边，ArcNode的info存权值，adjvex存目标顶点下标。顶点数组vertices的每个元素只挂一条链表，链表里每个节点代表一条从该顶点出发的弧。有向图里，顶点 i 的链表只包含 i 指向别人的边，不包含别人指向 i 的边，这一点在转换时必须严格对应，否则转出来的矩阵会变成无向图。

2.2 四个函数的职责边界

整份程序的核心就是四个函数，两两配对：DispMat和DispAdj负责打印，MatToList和ListToMat负责转换。职责划分很清晰，但每个函数内部都有值得推敲的细节。

DispMat遍历vexnum × vexnum的矩阵，遇到INF打印---，否则打印数值。它的参数是MGraph *，直接读结构体里的arcs和vexnum，不做任何修改，属于纯输出函数。

MatToList是矩阵转邻接表。它先遍历所有顶点把firstarc置空，然后对每一行从右往左扫描矩阵，遇到非零元素就malloc一个ArcNode，用头插法挂到对应顶点的链表上。这里从右往左扫是刻意为之：头插法会把后插入的节点放到链表头部，从右往左扫正好让链表顺序和矩阵列下标从小到大一致。如果从左往右扫，打印出来的邻接表顺序会是反的，虽然逻辑上没错，但对照矩阵时容易看晕。

DispAdj遍历每个顶点，打印顶点下标和它后面挂的整条链表。注意它只在firstarc非空时才打印顶点下标加冒号，空链表顶点直接跳过不输出，这会导致输出里缺失孤立顶点，对照时容易误以为顶点丢了。

ListToMat是反向转换。它先把目标矩阵全部清零，然后遍历每个顶点的链表，把p->info写到g->arcs[i][p->adjvex]。这里i是当前顶点下标，p->adjvex是边指向的顶点下标，写入位置正好对应有向边的方向。最后同步vexnum和arcnum。

2.3 主函数里的硬编码测试图

main函数里直接硬编码了一个 6 顶点的有向图，用二维数组A[6][6]给出邻接矩阵，然后手动赋给g.arcs，设置vexnum=6、arcnum=10。接着依次调用DispMat打印原矩阵、MatToList转成邻接表、DispAdj打印邻接表、ListToMat转回矩阵、DispMat打印转回的结果。整个流程是一个闭环验证：矩阵 → 邻接表 → 矩阵，如果两次打印的矩阵一致，说明转换逻辑正确。

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];

这个测试图有 10 条弧，权值分布在 1 到 9 之间，没有INF，所以MatToList里!= 0的判断不会误伤。但如果换成手动输入、允许用户填INF表示无穷，这个判断就会出问题。主函数最后有一个getchar()，作用是让控制台窗口停住，方便看输出，在 Windows 下用 IDE 运行时常见，命令行下则多余。

3. 跑起来：编译、运行与手动输入改造

3.1 编译与运行的最小步骤

这份代码是标准 C，没有依赖任何第三方库，用gcc直接编译即可。把源码保存为graph_convert.c，在终端执行：

gcc graph_convert.c -o graph_convert ./graph_convert

Windows 下如果用 MinGW，命令相同；如果用 Visual Studio，新建空项目把.c文件加进去直接 F5 也行。运行后应该看到三段输出：第一段是原始邻接矩阵，第二段是转换后的邻接表，第三段是转回后的邻接矩阵。重点核对第一段和第三段是否完全一致，一致就说明双向转换没有丢边或改权。

有向图 G 的邻接矩阵为： 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 的邻接矩阵转成邻接表： 0: 3 1 1: 2 2: 5 0 3: 5 2 4: 3 5: 4 0 图 G 的邻接表转成邻接矩阵： 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

邻接表输出里每行是“顶点下标: 邻接点下标序列”，顺序是从小到大，这是因为MatToList从右往左扫配合头插法的结果。如果看到顺序是反的，说明扫描方向或插入方式被改过。

3.2 把硬编码改成手动输入

实验要求里明确提到“手动输入图形信息进行存储”，但原代码只给了硬编码版本。改造思路很简单：把main里给A赋值的那段换成scanf循环，让用户先输入顶点数和弧数，再逐行输入矩阵。

printf("输入顶点数和弧数："); scanf("%d %d", &g.vexnum, &g.arcnum); printf("逐行输入 %d x %d 的邻接矩阵（0 表示无边）：\n", g.vexnum, g.vexnum); for (i = 0; i < g.vexnum; i++) { for (j = 0; j < g.vexnum; j++) { scanf("%d", &g.arcs[i][j]); } }

这里要注意两个参数：g.vexnum必须不超过MAX_VERTEX_NUM，否则数组越界；输入的矩阵必须和arcnum自洽，否则打印出来的弧数对不上，虽然不影响转换结果，但对照实验报告时会露馅。输入时用0表示无边，不要输入INF，因为MatToList的判断只认0。如果确实想支持INF语义，需要把判断改成g->arcs[i][j] != 0 && g->arcs[i][j] != INF，同时ListToMat清零后对无边位置补INF，这属于二次开发范畴，后面会讲。

手动输入版本跑通后，建议先用一个 3 顶点的小图验证，比如0->1权 2、1->2权 3、2->0权 4，转一圈看矩阵是否原样回来。小图容易肉眼核对，比直接上 6 顶点图更稳。

3.3 邻接表转矩阵时的清零为什么不能省

ListToMat开头有一段双重循环把g->arcs全部置零，这段代码看起来平淡，但它是整个反向转换正确性的前提。原因在于g1是main里的局部变量，未初始化时矩阵里是栈上的垃圾值。如果不先清零，那些没有边覆盖的位置会保留垃圾值，转出来的矩阵就会多出莫名其妙的边。

for (i = 0; i < n; i++) for (j = 0; j < n; j++) g->arcs[i][j] = 0;

清零的范围是n × n，n取自G->vexnum，而不是MAX_VERTEX_NUM。这意味着矩阵中超出vexnum的区域不会被清零，但后续打印和转换也只用到vexnum范围，所以不影响结果。如果要把这份代码改成支持动态顶点数、反复转换多次，清零范围最好扩到MAX_VERTEX_NUM，避免残留数据在后续操作中被误读。

4. 避坑与排查：五个真实会翻车的点

4.1 邻接表打印顺序和矩阵对不上

现象：转出来的邻接表每行邻接点下标是从大到小，和矩阵列顺序相反。原因：MatToList用了头插法，如果扫描方向是从左往右，后插入的小下标会被顶到链表头部，顺序就反了。原代码从j = n-1往0扫，正好抵消头插法的反转。解决：要么保持从右往左扫，要么改成尾插法（多维护一个尾指针），二选一，不要混用。

4.2 转回矩阵后多出原本没有的边

现象：第一次打印矩阵正常，转成邻接表再转回来，矩阵里冒出一些权值为 0 但位置不该有边的格子，或者某些格子变成垃圾值。原因：ListToMat的目标矩阵没有清零，栈上残留数据被当成边。解决：转换前对目标矩阵做全量清零，范围至少覆盖vexnum × vexnum。

4.3 输入 INF 后转换结果错乱

现象：手动输入时用32767表示无穷，转成邻接表后每条“无穷边”都变成了真实边，邻接表里多出一堆不该有的节点。原因：MatToList的判断条件是g->arcs[i][j] != 0，INF不等于 0，被当成有效边。解决：把判断改成同时排除0和INF，并在ListToMat里对无边位置按需补INF，保持语义一致。

4.4 顶点数超过 20 直接崩溃

现象：输入 21 个顶点，程序运行到一半段错误。原因：MAX_VERTEX_NUM固定为 20，vexs、arcs、vertices都是定长数组，越界写入踩到其他内存。解决：实验阶段把输入限制在 20 以内并加校验；要支持更大规模，得把定长数组改成malloc动态分配，同时把MAX_VERTEX_NUM换成运行时变量。

4.5 孤立顶点在邻接表输出里“消失”

现象：图里有一个没有任何出边的顶点，转成邻接表后打印结果里找不到它，误以为转换丢了顶点。原因：DispAdj只在firstarc != NULL时打印顶点下标，空链表顶点被跳过。解决：把打印顶点下标的判断移到循环外，每个顶点都打印下标，链表为空时只打印下标加冒号，这样顶点一个不少。

5. 二次开发：把实验代码改成能复用的图转换模块

这份代码作为实验作业是完整的，但作为可复用模块还有距离。我一般会做三件事：把定长数组换成动态分配、把INF语义统一、把打印和转换解耦。动态分配这块，MGraph的arcs可以改成int **，初始化时按vexnum分配行和列，ALGraph的vertices同理；这样顶点数就不再受 20 限制，代价是要多写释放逻辑，free的顺序和malloc相反，先释放每条链表再释放顶点数组。

INF语义统一是另一个值得做的改造。我的习惯是：矩阵里0表示无边，INF只用于最短路等算法的初始化，转换函数只认0。这样MatToList的判断保持!= 0即可，ListToMat清零后无边位置自然为0，两边语义一致，不会出现“无穷边变真边”的翻车。如果算法层确实需要INF，在算法入口处单独做一次映射，不要让它渗进存储层。

验证改造是否成功，我通常用一个固定套路：构造一个包含孤立顶点、自环、双向边的测试图，跑“矩阵 → 邻接表 → 矩阵”闭环，比对两次矩阵是否逐元素相等；再跑“邻接表 → 矩阵 → 邻接表”，比对两次邻接表的边集合是否一致。两个方向都过，才认为转换逻辑可靠。这个套路比肉眼核对靠谱得多，尤其是顶点数上去之后。

还有一个具体技巧：把DispMat和DispAdj的输出重定向到文件，用diff比对两次转换的结果，比在终端里滚动看要稳。命令行下./graph_convert > out1.txt，改完再跑一次> out2.txt，diff out1.txt out2.txt没输出就说明闭环一致。这个习惯我从第一次做图实验就养成了，后来每次改转换逻辑都强制走一遍，省了很多“看起来对但实际错”的排查时间。希望帮到你。

本文还有配套的精品资源，点击获取