企业官网建设流程全解析

简介：这份资源面向正在学习数据结构、需要攻克图存储难点的学生与编程初学者，聚焦图的邻接矩阵与邻接表两种存储结构及其相互转换。内容围绕有向图展开，包含邻接矩阵的二维数组表示、邻接表的顶点与边节点结构定义，以及MatToList、ListToMat、DispMat、DispAdj等核心函数的实现思路，并延伸到手动输入图信息后完成存储方式转换的完整程序设计，涉及动态内存分配与释放等易错细节。资源包共1个docx文件，约55KB，以实验报告形式组织目的、问题描述、要求与完整C语言源码，便于对照阅读与上机复现。目前已有8614人学习，适合作为课程实验参考或考前梳理图存储知识的练习材料，帮助读者理解稠密图与稀疏图下两种存储方式的取舍，并为后续网络路由、图算法等应用打下基础。

1. 图的两种存储：一张知识地图先摆出来

图的存储这块，很多人第一反应是「邻接矩阵和邻接表嘛，背过」，真到写代码或者做题时却卡在转换和边界上。其实整个方向就一张地图：顶点集怎么存、边集怎么存、两者怎么互转、转换时哪些信息会丢。邻接矩阵用二维数组arcs[i][j]表达「i 到 j 有没有边、权值多少」，查询 O(1)，空间 O(n²)；邻接表给每个顶点挂一条边链表，只存实际存在的边，空间 O(n+e)，遍历某点邻居 O(degree)。有向图矩阵不对称、无向图对称，这是判断写没写反的第一道关。适合正在学数据结构、准备实验或考试复习的人，把这张地图先立住，后面每个模块都是往格子里填细节。

2. 邻接矩阵：二维数组里的图长什么样

2.1 结构定义与三个核心字段

邻接矩阵的本质是一个n×n的二维数组，行下标是起点，列下标是终点。教材和实验里常见的定义长这样：

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

三个字段各管一件事：vexs负责「顶点是谁」，arcs负责「边在哪、多重」，vexnum/arcnum负责「规模多大」。复习时最容易忽略的是arcnum——它不参与矩阵存储，但转换、校验、输出统计都要用，漏维护就会在转换后对不上账。矩阵里0通常表示无边，INF（如 32767）表示不可达，正数表示权值，这三个语义必须在整份代码里统一，否则DispMat打印和转换判断会互相打架。

2.2 有向图与无向图的矩阵差异

同样是矩阵，有向图和无向图的写法差一个对称性：

实验里明确用的是有向图，所以MatToList只按行扫描、只建出边链表，这是对的。如果换成无向图还照抄这段，就会漏掉一半边——这是转换题里最常见的翻车点之一。判断方法很简单：转换完把邻接表还原回矩阵，和原矩阵逐格比对，无向图必须对称，不对称就是漏写了反向边。

2.3 打印与初始化：DispMat的细节

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和%3s的宽度要一致，否则矩阵列会错位，复习时对不上行列。INF单独判一次，是为了把「不可达」和「权值为 0 的边」区分开——如果图里允许 0 权边，那0就不能再当「无边」用，得换一个哨兵值。这个坑在加权图里非常隐蔽：矩阵初始化全填 0，结果 0 权边被当成无边，转换后边就凭空消失了。稳妥做法是初始化填INF，对角线填 0，边写入时再覆盖。

3. 邻接表：链表挂顶点，空间花在刀刃上

3.1 边结点与顶点结点的两级结构

邻接表是「数组 + 链表」的混合结构，分两级：

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;

vertices[i]是第 i 个顶点的「头」，firstarc指向它的第一条出边，顺着nextarc走完就是 i 的全部邻居。这里的关键认知是：邻接表只存「存在的边」，所以空间是 O(n+e)，稀疏图优势明显；代价是查「i 到 j 有没有边」要遍历 i 的链表，最坏 O(n)，不像矩阵 O(1)。复习时把这两句对照记，选择题基本不会错。

3.2 头插法建表与遍历顺序

MatToList建表用的是头插法，代码骨架是：

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; // 表头前移 } } }

头插法的效果是「后插入的排在前面」，所以内层循环从n-1倒着扫，最终链表顺序才和矩阵列下标从小到大一致。如果正着扫又用头插，输出就是逆序——结果不算错，但和教材示例对不上，考试默写时容易被判「顺序不符」。这里还有个易忽略点：G->vertices[i].firstarc必须先置NULL，否则野指针会让链表接到随机内存上，程序时好时坏，属于典型的玄学 bug。

3.3DispAdj输出与空顶点处理

DispAdj遍历每个顶点，沿链表打印邻居下标：

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

if (p != NULL)这一句是出度为零的顶点（汇点）不打印空行，保持输出干净。但要注意：如果题目要求「每个顶点都占一行」，这个判断就得去掉，改成无条件打印行首。两种写法没有对错，取决于输出格式要求，复习时看清题干再定。另外info字段在纯拓扑输出里用不上，但转换回矩阵时必须带上，否则权值全丢——这是下一章转换的核心。

4. 双向转换：矩阵与邻接表怎么互推

4.1 矩阵转邻接表：按行扫、只建出边

MatToList的完整逻辑可以拆成三步：清空表头、双重循环扫矩阵、维护规模字段。第一步把G->vertices[i].firstarc全部置NULL，防止残留指针；第二步按行 i 扫列 j，arcs[i][j] != 0就为 j 建一个边结点挂到 i 的链表上；第三步把vexnum和arcnum抄过去。判断条件用!= 0还是!= INF取决于矩阵初始化约定：如果无边填 0，就用!= 0；如果无边填INF，就得用!= INF && != 0，否则会把INF当成一条权值 32767 的边建出来，转换结果直接多出一堆假边。

4.2 邻接表转矩阵：先清零、再按链表填

ListToMat是反向操作，顺序很关键：

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;

清零必须在填值之前，否则旧矩阵的残留值会混进来。填值用p->info而不是写死 1，是为了保住权值；如果只关心连通性，写 1 也行，但那就丢了加权信息。转换完arcnum直接抄邻接表的，不再重新数——因为邻接表的arcnum在建表时已经维护过，重数一遍反而容易和链表实际结点数对不上。这里有个血泪经验：转换函数最好成对写，MatToList和ListToMat互为逆操作，写完立刻做一次「矩阵→表→矩阵」往返，逐格比对，能一次性抓出绝大多数下标写反、条件写错的问题。

4.3 转换的复杂度与适用场景

这张表是复习时的「选型依据」：稠密图、频繁查两点连通性，选矩阵；稀疏图、频繁遍历某点所有邻居（如 BFS/DFS），选邻接表。转换本身没有「更优」一说，只有「当前操作需要哪种视图」。实验要求两个程序分别以矩阵和表为起点互转，本质就是让你把两个方向都手写一遍，体会各自的遍历方式差异。

5. 易错点清单：转换题里最容易翻车的五处

5.1 易错点一：无边哨兵值不统一

为什么漏：矩阵初始化用 0，判断却写!= INF，或者反过来，代码能跑但结果多边少边。怎么补：在文件头统一定义#define INF 32767，初始化、判断、打印三处引用同一个宏，改一处全改。

5.2 易错点二：头插法配正序扫描导致逆序

为什么漏：只记住「头插」，忘了头插会把顺序翻过来，输出和示例对不上还以为是逻辑错。怎么补：要么内层倒序扫配头插，要么正序扫配尾插，二选一，写完拿 3 个顶点的小图手推一遍链表顺序。

5.3 易错点三：表头指针没置空

为什么漏：malloc出来的ALGraph里firstarc是随机值，直接头插会接到野指针上，程序时崩时不崩。怎么补：建表第一步无条件for (i=0;i<n;i++) G->vertices[i].firstarc = NULL;，养成肌肉记忆。

5.4 易错点四：无向图只建单向边

为什么漏：有向图代码直接套到无向图上，只写了arcs[i][j]，漏了arcs[j][i]，转换后矩阵不对称。怎么补：转换完做对称性断言，无向图逐格检查arcs[i][j] == arcs[j][i]，不等就补反向边。

5.5 易错点五：arcnum不维护或重复计数

为什么漏：只关注链表和矩阵，忘了规模字段，转换后统计对不上；或者转换时又数一遍链表，和原值冲突。怎么补：arcnum只在建图时数一次，转换时直接抄，不重算；往返转换后比对arcnum是否一致，作为自检项。

6. 复习落地：一张自检表加一个往返测试习惯

复习这块内容，最有效的方式不是反复看代码，而是拿一张自检表逐项过，再用「往返转换」当后悔药。下面这张表可以直接抄到笔记里，每复习一遍打一次勾：

具体怎么练：先手写一个 4 顶点、5 条边的小有向图，矩阵和邻接表各画一遍；然后照着代码把MatToList和ListToMat各默写一次，重点默写循环边界和判断条件；最后跑一次往返，把原矩阵和还原矩阵并排打印，逐格比对。往返测试的价值在于它是「黑匣子」——你不需要逐行调试，只要两端相等，中间大概率没错；不相等，就顺着链表和矩阵的差异定位到具体顶点。

手动输入那部分也别跳过。实验要求把程序完善成手动输入任意图，这一步练的是「输入校验」：顶点数、边数、每条边的起点终点权值，输错一个下标就越界。加一句if (u < 0 || u >= n) continue;之类的边界判断，比事后调试省事得多。从那以后我每次写图相关的转换，都强制走一遍「小图手推 → 默写核心循环 → 往返比对」三步，宁可多花十分钟，也不让野指针和哨兵值在考场上给我惊喜。希望这份梳理帮到你。

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