企业官网建设流程全解析

简介：这份资源面向正在学习数据结构的高校学生与编程初学者，聚焦图这一非线性结构的两种核心存储方式——邻接矩阵与邻接表，帮助读者理解二者在空间占用、查询效率与适用场景上的差异，并掌握相互转换的编程实现。资源包内含1个docx文档，压缩后约55KB，内容以C语言代码与实验说明为主，涵盖邻接矩阵的二维数组定义、邻接表的顶点与边节点结构，以及DispMat、MatToList、DispAdj、ListToMat等函数的完整实现。文档围绕两个实验任务展开：将给定有向图从邻接矩阵转换为邻接表并反向转换，以及支持用户手动输入图信息后完成存储方式互换，同时涉及动态内存分配、链表遍历与内存释放等关键操作。目前已有8612人学习下载，适合希望借助可运行代码加深对图存储结构理解、提升编程与算法实践能力的读者参考。

1. 从一次内存踩坑说起：图的两种存储到底怎么选

带过几届数据结构实验，我发现一个规律：大部分同学能把邻接矩阵和邻接表的定义背得滚瓜烂熟，但真让他写一个「矩阵转邻接表」的完整程序，十有八九会在指针和内存上翻车。我印象最深的一次，某同学的程序在本地跑得好好的，换台机器直接段错误，查了半天才发现是邻接表的边节点忘了分配内存，纯靠运气在跑。图的存储结构本身不难，难的是把两种结构之间的转换写对、写稳、写完整。

这份资源就是围绕这个痛点来的：用 C 语言实现有向图的邻接矩阵和邻接表两种存储，并且完成双向转换——矩阵转邻接表、邻接表转矩阵，最后还支持手动输入任意图。它适合正在做数据结构实验的学生，也适合想重新捡起 C 语言指针和链表操作的开发者。代码不长，但每一行都值得拆开看，因为里面藏着图存储的核心逻辑和几个容易忽略的边界条件。

2. 邻接矩阵与邻接表的结构定义：先把地基打对

2.1 邻接矩阵的结构体设计

邻接矩阵的本质是一个二维数组，arcs[i][j]表示从顶点 i 到顶点 j 的边的权值。对于有向图，这个矩阵通常不对称；对于无向图，它是对称的。资源里用#define MAX_VERTEX_NUM 20限制了最大顶点数，用typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]定义了矩阵类型。

#define MAX_VERTEX_NUM 20 typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; // 顶点表，存放顶点数据 AdjMatrix arcs; // 邻接矩阵，存放边权值 int vexnum, arcnum; // 当前顶点数和弧数 } MGraph;

这里有几个参数需要留意。MAX_VERTEX_NUM设为 20 意味着这个实现最多处理 20 个顶点的图，超过就会数组越界。arcnum记录弧的数量，在矩阵转邻接表时用来传递图的规模信息。vexs数组存放顶点本身的数据，虽然在这个实验里顶点编号就是索引，但保留这个字段是为了后续扩展——比如顶点带名字或编号时可以直接用。

注意：arcs数组在初始化时必须全部清零，否则未初始化的位置会残留垃圾值，导致转换时把不存在的边也建出来。

2.2 邻接表的节点与头结点定义

邻接表的核心是「每个顶点挂一条链表」，链表里每个节点代表一条从该顶点出发的边。资源里把边节点和顶点节点分开定义：

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;

ArcNode里的adjvex存的是目标顶点的下标，info存权值，nextarc串起同一起点的其他边。AdjList是一个数组，每个元素是VNode类型，firstarc指向该顶点的第一条边。这种「数组 + 链表」的组合就是邻接表的经典实现。

为什么不用单纯的链表数组？因为图算法经常需要按顶点编号随机访问某个顶点的邻接表，数组的 O(1) 随机访问特性在这里很关键。如果全用链表，查找某个顶点的邻接表就得从头遍历，效率会掉一个量级。

2.3 两种结构的选型逻辑

选邻接矩阵还是邻接表，核心看图的稠密程度。稠密图（边数接近顶点数的平方）用邻接矩阵更划算，因为空间利用率高，而且判断两点之间是否有边只需要 O(1) 时间。稀疏图（边数远小于顶点数的平方）用邻接表更省空间，遍历某个顶点的所有邻接点只需要 O(degree) 时间。

这个实验里用的示例图有 6 个顶点、10 条弧，算中等稠密。用矩阵存储需要 36 个整型空间，用邻接表需要 6 个头结点加 10 个边节点。数据量小的时候差别不明显，但当顶点数到几千、边数只有几万时，邻接矩阵的 O(n²) 空间就会直接爆掉。所以实际工程中，社交网络、路由表这类稀疏图几乎都用邻接表。

3. 矩阵转邻接表：头插法的顺序陷阱

3.1 转换的核心逻辑

矩阵转邻接表的思路很直接：遍历矩阵的每一行，对于第 i 行，找出所有arcs[i][j] != 0的位置，为每个位置创建一个边节点，插入到顶点 i 的邻接表中。资源里的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; }

3.2 为什么倒序遍历

头插法的特点是新节点总是插在链表头部。如果正序遍历列（j 从 0 到 n-1），那么最后插入的节点会排在链表最前面，导致邻接表中边的顺序和矩阵中的列顺序相反。倒序遍历（j 从 n-1 到 0）配合头插法，可以让最终链表中的节点顺序和矩阵列顺序一致。

这个顺序在单纯打印时影响不大，但如果后续要对邻接表做有序操作（比如按顶点编号排序、二分查找），顺序错乱就会带来额外开销。我一般建议在转换阶段就把顺序理顺，后面省事。

3.3 内存分配的检查

malloc之后没有检查返回值是这个代码的一个隐患。在嵌入式环境或内存紧张的场景下，malloc可能返回 NULL，直接解引用就会崩溃。稳妥的做法是加一层判断：

p = (ArcNode *)malloc(sizeof(ArcNode)); if (p == NULL) { printf("内存分配失败\n"); return; }

虽然实验环境下很少触发，但养成检查习惯没坏处。另外，每次调用MatToList之前必须确保G->vertices[i].firstarc已经被初始化为 NULL，否则头插法会把新节点挂到野指针上，直接段错误。

3.4 打印邻接表的实现

DispAdj函数负责把邻接表打印出来，格式是「顶点编号: 邻接点1 邻接点2 ...」。这个函数本身不复杂，但有一个容易忽略的点——它只打印了adjvex，没有打印权值info。如果图是带权的，打印结果会丢失权值信息。

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", p->adjvex)改成printf("%3d(%d)", p->adjvex, p->info)，这样输出里就带上了边的权重。调试带权图时这个改动很有用。

4. 邻接表转矩阵：清零与遍历的配合

4.1 转换前的矩阵清零

邻接表转矩阵的第一步是把目标矩阵全部清零。资源里的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; }

清零这一步不能省。如果目标矩阵之前被用过，残留的旧值会污染转换结果。清零的范围是n × n，其中n是当前图的顶点数，不是MAX_VERTEX_NUM。如果图比较小，只清零实际用到的区域就够了，没必要把整个 20×20 的数组都刷一遍。

4.2 遍历邻接表填矩阵

清零之后，遍历每个顶点的邻接表，把边节点的adjvex和info填到矩阵对应位置。这里g->arcs[i][p->adjvex] = p->info直接赋值，因为邻接表中每个边节点代表一条从 i 出发的边，矩阵中对应位置就应该存这条边的权值。

对于有向图，这个逻辑没问题。但如果是无向图，邻接表中一条边会出现两次（i 的链表里有 j，j 的链表里也有 i），填矩阵时arcs[i][j]和arcs[j][i]都会被赋值，结果是对称矩阵，符合无向图的定义。

4.3 顶点数和弧数的传递

转换完成后，g->vexnum和g->arcnum需要从源图复制过来。这两个字段在后续打印和算法中会用到，如果忘了赋值，打印时可能只输出部分顶点，或者弧数显示为 0。资源里在函数末尾做了赋值，这一步不能漏。

4.4 手动输入图的实现思路

资源里的main函数用的是硬编码的矩阵，但实验要求里提到了「手动输入任意图形」。实现手动输入需要增加两个函数：一个读入顶点数和弧数，另一个读入每条边的起点、终点和权值。

void CreateMGraph(MGraph *g) { int i, j, k, w; printf("输入顶点数和弧数："); scanf("%d %d", &g->vexnum, &g->arcnum); for (i = 0; i < g->vexnum; i++) for (j = 0; j < g->vexnum; j++) g->arcs[i][j] = 0; // 初始化矩阵 for (k = 0; k < g->arcnum; k++) { printf("输入第 %d 条边的起点、终点和权值：", k + 1); scanf("%d %d %d", &i, &j, &w); g->arcs[i][j] = w; // 有向图只填一个方向 } }

输入时要注意顶点编号从 0 开始还是从 1 开始。资源里的示例矩阵用的是 0 起始编号，所以输入时也要保持一致。如果用户习惯从 1 开始编号，可以在读入后统一减 1，或者在提示里明确说明编号规则。

5. 避坑与排查：那些年我们踩过的指针坑

5.1 段错误：邻接表头指针未初始化

现象：程序在MatToList执行到p->nextarc = G->vertices[i].firstarc时崩溃，报段错误。

原因：G->vertices[i].firstarc没有被初始化为 NULL，里面是随机值。头插法把这个随机值当作链表尾部，后续遍历时访问了非法地址。

解决：在MatToList开头加一个循环，把所有firstarc置为 NULL。如果ALGraph是动态分配的，malloc之后也要手动初始化每个头指针，malloc不会自动清零。

5.2 打印结果为空：矩阵清零范围不对

现象：邻接表转矩阵后，打印出来的矩阵全是 0，但邻接表明明有边。

原因：清零时用了MAX_VERTEX_NUM而不是实际的vexnum，或者清零循环的边界写错了，把后面要填的值也清掉了。

解决：清零和填值分两个独立循环，先全部清零，再遍历邻接表填值。清零范围用n = G->vexnum，不要用宏定义的最大值。

5.3 边顺序颠倒：头插法与遍历方向不匹配

现象：矩阵转邻接表后，邻接表中边的顺序和矩阵列顺序相反，打印出来看着别扭。

原因：正序遍历列配合头插法，导致后插入的节点排在前面。

解决：把列遍历改成倒序（j从n-1到0），或者改用尾插法。尾插法需要额外维护一个尾指针，代码稍复杂，倒序遍历更简洁。

5.4 内存泄漏：邻接表节点未释放

现象：程序反复运行转换函数后，内存占用持续上升。

原因：每次MatToList都会malloc一批边节点，但程序结束前没有free这些节点。

解决：写一个DestroyAdj函数，遍历每个顶点的链表，逐个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; } }

5.5 顶点编号越界：输入未做范围检查

现象：手动输入图信息时，输入了大于vexnum-1的顶点编号，程序访问矩阵越界或邻接表数组越界。

原因：scanf读入的编号没有做范围校验，直接用作数组下标。

解决：读入后加一个判断，如果编号小于 0 或大于等于vexnum，提示重新输入。这个检查在交互式程序里很有必要，能避免大部分非法输入导致的崩溃。

6. 从能跑到好用：几个提升代码质量的技巧

把基本功能跑通只是第一步，要让这份代码真正好用，还有几个地方可以打磨。第一个是统一用n = g->vexnum作为循环边界，而不是到处写MAX_VERTEX_NUM。前者是实际规模，后者是容量上限，混用会导致打印时输出一堆无意义的零行。第二个是在DispMat里把INF的处理逻辑理清楚——资源里用INF表示无穷大（不存在的边），但矩阵初始化时用的是 0，这两个语义要统一。如果 0 表示没有边，那INF只在特定算法（如最短路径）里用，打印时把 0 显示为---更直观。

第三个技巧是给转换函数加上返回值，用 0 表示成功、-1 表示失败（比如内存分配失败）。这样调用方可以根据返回值决定后续操作，而不是默默崩溃。第四个是在手动输入模式里加一个「打印当前图」的选项，输入完边之后先让用户确认，确认无误再执行转换。这个交互细节能省掉很多「输入错了只能重来」的麻烦。

最后一个习惯是我自己踩坑之后养成的：每次写完涉及指针的代码，先在纸上画出内存布局图，标清楚哪些指针指向堆、哪些指向栈、哪些可能为 NULL。图的邻接表操作本质上就是指针操作，画一遍图比盯着代码看十分钟都管用。从那以后我每次写链表相关的代码，都强制自己在草稿纸上画一遍节点连接关系，确认没有悬空指针再上机。希望这些经验帮到你，少走几个弯路。

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