企业官网建设流程全解析

简介：面向数据结构初学者与需要巩固图存储知识的编程学习者，这份资料围绕图的邻接矩阵与邻接表两种表示方法展开，重点解决两种存储结构之间的转换与C语言实现问题。压缩包内共1个docx文档，约55KB，内容以实验目的、问题描述、程序要求和完整C代码为主体，结构紧凑，适合课程实验对照与考前复习。文档给出有向图的邻接矩阵、邻接表定义，以及DispMat、MatToList、DispAdj、ListToMat等函数的实现思路，并涉及动态内存分配、头插法建表、手动输入图信息和内存释放等细节。已有8616人学习，读者可借此理解稠密图与稀疏图下的存储取舍，掌握从矩阵到链表、再由链表还原矩阵的完整流程，并参考代码完善输入校验与资源管理。

1. 从一段写死的 6×6 矩阵说起：这份实验代码能解决什么问题

很多人在数据结构课上学到图的时候，卡点其实不在 BFS/DFS 怎么写，而在邻接矩阵和邻接表这两种存储结构怎么互相倒——矩阵好写，链表一上手就乱，转换过程中哪个下标进哪个结点，光靠看书很难对上。这份代码就是专门为这件事准备的：它先拿一个写死的 6 顶点、10 条弧的有向图当输入，走一遍邻接矩阵到邻接表的转换，再走一遍反向转换，最后把两次结果都打印出来，让你可以一格一格地核对。适合刚开数据结构课、要交一份“两种存储结构互转”实验的人，也适合工作几年后想回头把图的基础零件重新摸一遍的人。整份代码只有一个 .c 文件、两套结构体、四个核心函数，不依赖任何第三方库，编译一次就能跑，难度不高但坑不少，尤其是那几个“用一个常量同时当哨兵和权值”的地方。

2. 结构体先看清：MGraph 和 ALGraph 怎么把一张图塞进内存

读这份代码，别急着看 main，先把两个结构体的内存布局在脑子里画出来。图的两种存储方式本质上是同一个问题的两种答案：边的关系是稀疏的，你要么用 n×n 的格子把它摊平，要么用链表只记真正存在的那几条。选哪种，取决于图的稠密程度和你后续要做的操作，这份实验代码把两套都给出来了，正好可以对着比。

2.1 MGraph：定长二维数组加一个哨兵常量

先看矩阵侧的定义，这是全篇的基础：

#define MAX_VERTEX_NUM 20 // 顶点数上限，编译期就定死 typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 20x20 的 int 二维数组 typedef int VertexType; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; // 顶点表，存顶点本身的信息（编号/名字） AdjMatrix arcs; // 邻接矩阵，arcs[i][j] 存边权 int vexnum, arcnum; // 当前图实际的顶点数、弧数 } MGraph; #define INF 32767 // 约定：这个值代表“没有边”

这里有几个参数值得单独说。MAX_VERTEX_NUM是编译期常量，意味着MGraph是一个固定大小的对象，一个MGraph变量在栈上就要占 20×20×4 + 20×4 + 8 ≈ 1688 字节，两个变量g和g1一起声明就是 3.4KB 左右，在这个规模的实验里无所谓，但顶点上限一旦调到 1000，单个对象就是 4MB，放栈上会直接崩，那时候就得改成堆上 malloc 或者用动态数组。vexnum和arcnum是“有效区”，矩阵虽然是 20×20，但只有前 vexnum 行前 vexnum 列有意义，所有遍历都必须用 vexnum 而不是 MAX_VERTEX_NUM 当边界，这一点在DispMat和MatToList里都体现得很明显。

INF = 32767这个约定要留意，它只是DispMat里用来判断“该打横杠还是打数字”的哨兵，并不是这份代码里唯一的“无边”表示——MatToList用的是!= 0。两套约定并存，是后面好几个坑的源头，先记在这里。vexs数组在这份代码里其实一直没被赋过值，打印和转换全程只用下标，vexs属于“结构上留了位置但逻辑上没用上”的部分，做二次开发时如果顶点要带名字，就得自己把它填起来。

2.2 ALGraph：顶点数组外套一层边结点链表

邻接表侧是两个结构体嵌套，层次要理清楚：

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;

ArcNode是真正的链表节点，三个字段分别承担“指向谁”“下一条在哪”“这条边多重”。VNode是表头，AdjList是VNode的数组类型别名，所以ALGraph.vertices[i]就是第 i 号顶点的表头，vertices[i].firstarc指向它出发的第一条弧。注意AdjList是类型别名不是变量，typedef struct VNode {...} VNode, AdjList[MAX_VERTEX_NUM];这一行同时定义了两样东西：结构体类型VNode，以及“长度为 20 的 VNode 数组”这个类型AdjList。这种写法在老教材里很常见，第一次看容易懵，其实是把数组类型也 typedef 了。

和矩阵侧比，ALGraph的存储开销是“表头固定 n 个 + 每条弧一个结点”，ArcNode里int加指针加int，在 64 位下因为对齐实际是 16 字节一个。所以邻接表的总开销约等于16n + 16e字节，矩阵是4n²，这个差距在稀疏图上非常明显，下一节算笔账。

还有一点必须提前说：ALGraph里只有firstarc这一层指针，没有任何“已分配结点”的记录，意味着谁 malloc 谁负责 free，代码里没有 free，长期跑必然泄漏，这不是理论问题，后面避坑章节会单独讲。

2.3 空间账本：稠密图和稀疏图的分界线在哪

把两边的字节数摊开算，选型就有依据了。矩阵固定4n²字节；邻接表约为16n + 16e字节（64 位，指针 8 字节、结构体对齐到 16）。令两者相等：4n² = 16n + 16e，也就是e ≈ 0.25n² - n。

表里的数字只是量级参考，真实项目里还要算上 malloc 的头部开销和缓存友好性。但结论很清楚：n 小的时候矩阵反而更省，n 大且稀疏时邻接表优势明显。这份实验里 n=6、e=10，其实已经过了分界点，所以邻接表那侧的结点数只有 10 个，看起来比矩阵轻。实际工程里判断标准更粗暴：如果后续要频繁做“u 到 v 有没有边”的查询，矩阵 O(1) 直接命中，值得为它多花点内存；如果要频繁遍历某个顶点的所有邻居（比如 BFS、拓扑排序、最短路），邻接表的 O(degree) 才是正解，矩阵每次都要扫一整行 n 个格子。

还有一层隐性成本是缓存。矩阵是连续内存，一行扫下来对 CPU 缓存很友好；邻接表的结点是分散 malloc 的，遍历时指针跳来跳去，cache miss 会明显更多。这条在数据规模小的时候感知不到，规模上去以后就是实打实的性能差距，做算法题时如果矩阵能过就别急着换链表。

3. 转换链路拆解：MatToList 和 ListToMat 的逐行验证

两个转换函数是这份代码的主体，加起来不到 40 行，但每一行都有讲究。我按“输入什么、中间做了什么、输出什么”的顺序拆，配合那份 6 顶点的测试数据，能把结果对到每一个下标。

3.1 MatToList：为什么 j 要从 n-1 倒着扫

先看完整实现：

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++) { /* 第二步：j 从大到小扫，配合头插法，链表顺序才和顶点号一致 */ for (j = n - 1; j >= 0; j--) { if (g->arcs[i][j] != 0) { /* 0 代表这条弧不存在 */ p = (ArcNode *)malloc(sizeof(ArcNode)); p->adjvex = j; /* 弧指向 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; }

外层i是弧的起点，内层j是终点，arcs[i][j] != 0就说明 i 到 j 有一条权值为arcs[i][j]的弧。关键在j的遍历方向：从n-1递减到0。因为插入方式是头插法（新结点永远插在链表最前面），如果 j 递增扫描，最后插入的会是编号最大的那条弧，链表顺序就是降序；反过来倒序扫描再头插，最终链表正好是0,1,2,...升序。这个细节在原代码里没有任何注释，但它决定了DispAdj打印出来好不好核对。

拿测试矩阵第 0 行{0,5,0,7,0,0}走一遍：j 从 5 扫到 0，先遇到arcs[0][3]=7，插入结点 3，链表变成[3]；继续扫到arcs[0][1]=5，头插结点 1，链表变成[1,3]。所以 0 号顶点出发的弧打印出来是1 3，和矩阵里“先 1 后 3”的列顺序完全一致。如果不倒着扫，打印结果就是3 1，肉眼核对时会怀疑自己转错了，其实是插入顺序的锅。

还有一处容易被忽略：G->vertices[i].data在整个函数里没被赋值。MatToList只负责“弧”的信息，顶点本身的data留给调用方填。这份代码里DispAdj也没用到data，所以跑起来看不出问题，但如果后面要按顶点名字打印，这里就是一个空洞。

3.2 ListToMat：先清零再填值，两趟不能合成一趟

反方向的函数短一些，但“清零”这一步是硬性要求：

void ListToMat(ALGraph *G, MGraph *g) { int i, j, n = G->vexnum; ArcNode *p; /* 第一趟：整个 n x n 区域清零，防止结构体里残留上一次的脏边 */ 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; } } g->vexnum = n; g->arcnum = G->arcnum; }

g->arcs[i][p->adjvex] = p->info这一行是整个反向转换的核心：i是当前表头对应的起点，p->adjvex是这条弧指向的终点，p->info是权值，三者一落座，矩阵里对应格子就被填上了。因为邻接表里只存“存在的弧”，所以矩阵的其余位置必须靠第一趟清零保证是 0，否则g1这个局部变量在栈上拿到的就是上一次函数调用留下的垃圾值，打印出来会多出一堆莫名其妙的边。这也是为什么两个循环不能合成一个——清零要覆盖全矩阵，填值只覆盖有弧的位置，顺序反了照样出错。

函数返回类型这里原代码是省略的，默认int，在老的 C89 编译器下只是警告，在 C99 及以后的-std=c99下会直接报错。这个坑第 5 章单独讲，改法很简单，前面加个void就行。

3.3 DispMat 与 DispAdj：把结构打印成肉眼能核对的样子

转换对不对，最终要靠打印函数来验证，这两个函数写得朴实但够用：

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"); } } 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"); } }

DispMat用%3d定宽输出，6 个顶点排下来正好对齐，扫一眼就能看出哪一行有哪些非零元。DispAdj先判断p != NULL再打i:，这是为了跳过那些没有任何出边的孤立顶点——不打表头，输出里就不会出现一堆光秃秃的2:后面什么都没有。这份测试数据里每个顶点都有出边，所以没机会触发这个分支，换成稀疏图时就能看出好处。

DispMat里的== INF判断，在这份测试数据下其实是死代码：main 里传进来的矩阵用的是 0 表示无边，INF一次都不会命中。两套“无边”约定并存，是这份代码最值得拎出来说的地方，第 5 章展开。

4. 跑通它：编译、输入、输出对照一遍

代码本身不长，从新建文件到看到正确输出，熟练的话五分钟。但第一次跑还是建议按下面的步骤走一遍，把每个环节的预期结果先对好，出问题才知道卡在哪。

4.1 编译命令与必须开的警告选项

把代码存成graph_conv.c，编译命令用这条：

gcc -std=gnu89 -Wall -Wextra -o graph_conv graph_conv.c

-Wall -Wextra一定要开。原代码里ListToMat没有声明返回类型，getchar()的返回值没接，main用的是void main(void)，这些在默认编译下悄无声息，开了警告才会一条条列出来。-std=gnu89是为了让隐式int返回类型只报警告不报错；如果坚持用-std=c99，就得先给ListToMat补上void，否则会直接编译失败。

编译过程中大概率会看到这两类警告：return type defaults to 'int'（对应ListToMat），以及control reaches end of non-void function。前者补void，后者说明函数声明和实现不一致，一并处理掉。把这些警告清干净，是后面改代码不出低级错误的前提。

如果用的是较新的编译器而且不想降标准，直接把ListToMat定义改成void ListToMat(ALGraph *G, MGraph *g)，再#include <stdlib.h>把malloc的隐式声明消掉，-std=c11 -Wall也能编过。

4.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 3 1: 2 2: 0 5 3: 2 5 4: 3 5: 0 4

对着矩阵逐行数一下边的条数：1,3（2 条）+2（1 条）+0,5（2 条）+2,5（2 条）+3（1 条）+0,4（2 条）= 10 条，和arcnum = 10对得上，说明一条没丢。第三段转回来的矩阵应该和第一段完全一样，逐格比对即可，这就是整个实验的验收标准。

如果第二段打印出的顺序是3 1而不是1 3，说明有人把MatToList里的j--改成了j++，结构没错但顺序反了，属于“看起来能跑其实有坑”的典型。如果第三段矩阵里出现了原矩阵没有的非零值，回去查清零循环是不是被优化掉了。

4.3 把写死的矩阵换成键盘输入

实验要求里明确提到要支持手动输入任意图，这块原代码没给，得自己补。我的习惯是输入“顶点数 + 弧数 + 若干条弧的三元组”，而不是让用户敲 n×n 个数字——后者对稀疏图太不友好：

void InputMat(MGraph *g) { int i, j, k, u, v, w; printf("输入顶点数 弧数: "); if (scanf("%d %d", &g->vexnum, &g->arcnum) != 2) return; if (g->vexnum <= 0 || g->vexnum > MAX_VERTEX_NUM) { printf("顶点数超出上限 %d\n", MAX_VERTEX_NUM); g->vexnum = 0; return; } for (i = 0; i < g->vexnum; i++) { /* 先整体清零 */ g->vexs[i] = i; /* 顶点信息暂用编号占位 */ for (j = 0; j < g->vexnum; j++) g->arcs[i][j] = 0; } printf("依次输入 %d 条弧（起点 终点 权值），顶点编号 0 开始：\n", g->arcnum); for (k = 0; k < g->arcnum; k++) { if (scanf("%d %d %d", &u, &v, &w) != 3) break; if (u < 0 || u >= g->vexnum || v < 0 || v >= g->vexnum) { printf("第 %d 条弧端点越界，已跳过\n", k + 1); continue; } g->arcs[u][v] = w; /* 有向图，只写一个方向 */ } }

scanf的返回值一定要判，输入流里混进字母的时候不判会陷入死循环。端点越界要跳过而不是直接写，否则arcs[u][v]就越界访问了。有向图只写arcs[u][v]一个格子；如果要做无向图，这里再加一句g->arcs[v][u] = w;就成。用这份输入函数替换main里那段写死的赋值，再配上同样的MatToList和DispAdj，就是一个完整的交互版程序。

输入这一步最容易翻车的地方是“弧数”和实际输入的条数对不上，比如用户说 10 条但只敲了 8 条，后面的循环就会卡在scanf上等输入。稳妥做法是循环里计数，结束后发现数量不足就提示并让arcnum按实际值回填，图本身还是能用的。

5. 常见问题排查：五个我实际踩过的坑

下面这五条不是从书上抄的，是照着这份代码一行行跑、一行行改的时候真实撞上的。每条按“现象 → 原因 → 解决”写，遇到对应的症状可以直接对号入座。

5.1 转换出来的邻接表顺序是反的

现象：编译运行都正常，矩阵打印也没问题，但邻接表那一段打出来的下标是从大到小排的，和矩阵里列的顺序对不上，肉眼核对时总以为转错了。

原因：MatToList用的是头插法，新结点插在链表头部，而内层循环j是递增扫描的，先遇到小编号的弧先进链表，后面大编号的弧又插到头部，最终顺序就成了降序。原代码写的是for (j = n - 1; j >= 0; j--)，倒序扫描配合头插，结果才是升序。

解决：两种改法任选其一——把j改成从n-1递减；或者保持j递增但改用尾插法（维护一个tail指针）。后者代码长一点，好处是边插入边保持顺序，调试时打印中间状态更直观。如果只是想快速验证，第一种改动最小，把循环条件换一下就行。

5.2 权值为 0 的边在链表里凭空消失

现象：输入一个带 0 权值边的图，矩阵里明明是 0（看起来像无边），实际那条边是存在的，转成邻接表后这条边没了，再转回来矩阵里也丢了。

原因：MatToList用if (g->arcs[i][j] != 0)判断边是否存在，把“权值为 0 的边”和“不存在的边”混为一谈了。同时DispMat又用== INF判断无边，两套约定不一致。这份测试数据里所有弧权值都是正的，所以没暴露，一旦换成带零权边的图就翻车。

解决：统一约定。要么用INF表示无边、arcs[i][j] != INF判断存在，同时输入函数里把无边位置初始化为INF；要么保留 0 表示无边，那就得明确“本程序不支持 0 权边”，在实验说明里写清楚。我更倾向前者，因为最短路那类算法本来就要用INF当初始值，早点统一后面省事。

5.3 ListToMat 在 C99 编译器下直接报错

现象：同样的代码，在旧环境里只是黄色警告，换到新一点的编译器上gcc -std=c99一跑，error: return type defaults to 'int'，直接编不过。

原因：ListToMat的定义是ListToMat(ALGraph *G, MGraph *g)，没有写返回类型。C89 允许省略并默认int，C99 把这个隐式规则删掉了，加上-Werror就是硬错误。

解决：函数头补上void，同时检查所有同类函数——这份代码里只有它一个漏了。编译选项上，如果暂时不想改代码，用-std=gnu89能绕过，但那是权宜之计，迟早要改。顺手把-Wall -Wextra打开，能一次性扫出这一类的漏网之鱼。

5.4 第二次运行时打印出上一次的脏数据

现象：同一个程序连续跑两次，第二次的转回矩阵里多出几条原本不存在的边，或者某些格子是乱七八糟的负数。

原因：ListToMat的矩阵清零循环用的是n = G->vexnum，如果G->vexnum没被正确赋值（比如MatToList因为某种原因提前返回），n就是 0，清零循环一次都不执行，g1作为栈上的局部变量拿到的是上一次函数调用留下的残留值。

解决：清零的边界不要依赖外部传入的n，直接用MAX_VERTEX_NUM或者对n做一次合法性检查（if (n <= 0 || n > MAX_VERTEX_NUM) return;）。另一个习惯是把MGraph g1 = {0};写成初始化形式，让编译器帮你把整个结构体先清一遍，比指望函数内部清干净更保险。这种“栈上未初始化变量”的问题没有编译警告，只能靠代码规范防。

5.5 malloc 之后没有 free，跑久了内存一直涨

现象：这是个一次性的实验程序，跑完就退出，看不出问题。但把它改成一个循环处理多张图的批处理程序后，内存占用一路往上走，几百张图之后就能看到明显的增长。

原因：MatToList里每条弧都malloc一个ArcNode，全篇没有任何free。main里那个G = (ALGraph *)malloc(sizeof(ALGraph))同样没有释放。进程退出时操作系统会回收，所以实验里感觉不到；一旦放进循环里，就是标准的泄漏。

解决：写一个DestroyAdj(ALGraph *G)，遍历每个表头把链表结点逐个free掉，再把firstarc置空；main结尾补一句free(G)。养成习惯：只要写了malloc，同一个文件里就要有一个能配对的释放函数，哪怕这次用不上。这条是血泪经验，实验代码里偷的懒，搬到真实项目里都会原样还回来。

6. 二次开发：手动输入、无向图和内存释放三块补齐

把这份实验代码改成能日常用的小工具，改动量不大，但有三块必须补，缺一块就会在某个场景下翻车。

第一块是输入层。原代码把图写死在main里，改成第 4 章那个InputMat之后，就应该同步补一个InputAdj，用“顶点数 + 弧三元组”直接建链表，这样两边都能从键盘起手，两条转换路径才算对称。输入校验别省：顶点数上限、端点越界、arcnum与实际输入条数不一致，这三类错误必须在输入阶段就拦住，不要留给后面的转换函数去兜底，那边兜不住。

第二块是图类型开关。当前实现默认有向图，MatToList只读一个方向的弧，ListToMat也只写一个格子。加一个int directed字段，转换时按类型决定要不要对称处理：

/* 在 MatToList 内层，无向图需要额外插一条 v->u 的弧 */ if (!directed && i != j) { p = (ArcNode *)malloc(sizeof(ArcNode)); p->adjvex = i; p->info = g->arcs[i][j]; p->nextarc = G->vertices[j].firstarc; G->vertices[j].firstarc = p; }

注意i != j这个判断，自环在无向图里只该存一次，不加判断会多出一条重复边，后面统计度数就不准了。对应的ListToMat在无向模式下也要对称写回，否则转回来的矩阵只有上三角。测试方法很简单：造一个三顶点的无向三角形，正反各转一次，矩阵必须完全对称，arcnum必须等于 3。

第三块是内存管理。补充一个释放函数，并且在每次批量处理前调用：

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; } G->vexnum = G->arcnum = 0; }

这里必须先用q把nextarc存下来再free(p)，顺序反了就是 use-after-free，调试器里能看到释放后仍然被读的告警。这个写法在任何链表释放场景都通用，值得当成肌肉记忆。

改完之后建议加一段自检：随机生成 100 张小图，每张都走“矩阵 → 邻接表 → 矩阵”一个来回，比较两次矩阵是否逐格相等、arcnum是否一致，任何一个不满足就打印失败的那张图。这种随机来回测试比手写几个用例有效得多，能顺带把 0 权边、自环、孤立顶点这些边界情况都扫一遍。

从那以后我每次写这种“两种结构互转”的代码，都会强制走一遍“转过去再转回来，逐格比对”的验证流程，哪怕只有三个顶点也照做——后悔药没有，多敲两行自检代码的成本比事后查一个玄学 bug 低太多。这份源码就是一个.c文件，拿过去补上void和释放函数，十分钟能跑起来，剩下的时间花在随机测试上最划算。希望帮到你。

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