简介面向数据结构初学者与备考学生的图存储专题学习资料聚焦邻接矩阵与邻接表两种核心存储结构及其相互转换。内容围绕有向图展开涵盖邻接矩阵的对称性与空间开销分析、邻接表的链表组织与度数查询效率并给出矩阵转邻接表、邻接表转矩阵的完整C语言实现包括DispMat、MatToList、DispAdj、ListToMat等函数及动态内存分配与释放的注意事项还支持手动输入图信息完成转换。资源包共1个docx文件约55KB以实验报告形式整合实验目的、问题描述、程序要求与可运行源码结构紧凑便于对照阅读。已有8613人学习适合需要理解两种存储方式差异、完成课程实验或巩固图算法基础的读者参考。1. 从一份“能跑但不敢改”的图存储代码说起很多人第一次写图的存储都是把邻接矩阵和邻接表当成两个孤立的知识点背下来矩阵是二维数组邻接表是链表数组考试能默写真到要改代码的时候就卡住。我手头这份 C 语言实现正好相反它不满足于“分别存一遍”而是把两种结构放在同一个程序里互相转换——矩阵转邻接表、邻接表再转回矩阵最后用打印函数把结果摊开给你看。这种“双向验证”的思路比单纯背定义有用得多。这份资源适合两类人一类是正在学数据结构、想把图的存储从纸面落到代码里的学生另一类是已经工作、需要快速回顾 C 语言结构体、指针和动态内存分配的老手。它不依赖任何第三方库一个gcc就能编译核心代码不到两百行但把邻接矩阵、邻接表、头插法建表、权值传递这几个关键点都串起来了。下面我按“先看清结构、再跑起来、最后动手改”的顺序拆一遍。2. 结构设计拆解两套存储结构如何共用一套顶点信息2.1 邻接矩阵 MGraph 的字段与内存布局先看矩阵这一侧。代码里用typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]把二维数组包装成一个类型再塞进MGraph结构体。这个结构体只有三个成员顶点表vexs、矩阵arcs、以及vexnum和arcnum两个计数。顶点表存的是顶点本身的信息这里用int表示实际项目里换成字符串或结构体都行矩阵存的是边和权值0表示没有边非零表示有边且值就是权。#define MAX_VERTEX_NUM 20 typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; // 顶点表下标即顶点编号 AdjMatrix arcs; // 邻接矩阵arcs[i][j] 表示 i 到 j 的权值 int vexnum, arcnum; // 当前顶点数、弧数 } MGraph;这里有个细节值得注意MAX_VERTEX_NUM是编译期常量矩阵大小固定为 20×20。这意味着这份代码只能处理顶点数不超过 20 的图超过就会越界。学习阶段够用但如果要改成手动输入任意图第一件事就是把固定数组换成动态分配或者至少加一个输入校验防止用户输入 25 个顶点直接把栈撑爆。arcnum在矩阵结构里其实不是必须的因为遍历矩阵就能数出边数但保留它可以让两种结构在转换时保持计数一致后面MatToList和ListToMat都会用到。2.2 邻接表 ALGraph 的节点定义与头插法邻接表这一侧由两个结构体组成边节点ArcNode和顶点节点VNode。ArcNode里三个字段——adjvex存邻接顶点下标nextarc指向下一条边info存权值。VNode里data是顶点信息firstarc指向第一条边。整个图用AdjList数组装起来再包一层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; // 顶点数组每个元素挂一条边链表 int vexnum, arcnum; } ALGraph;建表用的是头插法这一点在MatToList里体现得很明显外层循环遍历行i内层循环从j n-1倒着走到0每遇到非零元素就malloc一个ArcNode把adjvex设为j、info设为矩阵值然后插到vertices[i].firstarc的头部。倒序遍历是为了让最终链表顺序和矩阵列顺序一致——头插法会把先插入的节点挤到后面倒着插正好抵消这个效果。这个技巧在链表题里很常见但第一次看容易懵以为只是随便写的循环方向。提示头插法建出来的链表是逆序的如果希望邻接表按顶点编号从小到大排列要么倒序遍历插入要么改成尾插并维护尾指针。这份代码选了前者代码更短但可读性稍差。2.3 两套结构之间的字段映射关系把两个结构体摆在一起看映射关系其实很清晰MGraph.vexs[i]对应ALGraph.vertices[i].dataMGraph.arcs[i][j]对应ALGraph.vertices[i]那条链表里adjvex j的节点权值从矩阵元素搬到ArcNode.info。顶点数vexnum和弧数arcnum两边都要同步否则打印或后续遍历会出错。矩阵侧字段邻接表侧字段转换时的动作vexs[i]vertices[i].data逐个复制顶点信息arcs[i][j] ! 0ArcNode.adjvex j为每条非零边建一个节点arcs[i][j]的值ArcNode.info权值原样搬运vexnum/arcnumvexnum/arcnum直接赋值保持一致这张表看着简单但实际写转换函数时最容易漏的是顶点信息复制。原始代码里MatToList只建了边链表没有把g-vexs[i]赋给G-vertices[i].data因为示例里顶点信息没被打印所以没暴露问题。如果你后续要按顶点名字输出这一步必须补上否则邻接表里的data全是未初始化值。3. 跑通两个转换程序从固定矩阵到手动输入3.1 编译环境与最小可运行步骤这份代码是纯 C没有外部依赖Linux 下用gcc、Windows 下用 MinGW 或 Visual Studio 都能编。我一般会先建一个目录把代码存成graph_convert.c然后执行下面两条命令。第一条只编译不运行用来抓语法错误第二条编译并运行把输出重定向到文件方便对照。gcc -Wall -Wextra -o graph_convert graph_convert.c ./graph_convert-Wall -Wextra是我习惯加的这份代码里ListToMat没写返回类型老编译器会默认int新标准下会报警告。加上这两个参数能提前看到问题不至于运行到一半才发现函数签名不对。运行后应该先看到 6×6 的邻接矩阵再看到邻接表的打印最后看到转回来的矩阵。如果终端里矩阵列没对齐那是%3d和%3s混用的结果不影响逻辑只影响观感。3.2 程序一邻接矩阵转邻接表的完整链路程序一的主线是main里先手工填一个 6×6 矩阵调DispMat打印原矩阵再malloc一个ALGraph调MatToList转换最后DispAdj打印链表。矩阵内容写死在A[][6]里vexnum 6、arcnum 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} }; 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];MatToList的核心是两层循环加头插。外层i走顶点内层j从n-1递减到0遇到g-arcs[i][j] ! 0就分配节点。注意判断条件是! 0而不是! INF因为这份代码里INF只在DispMat里用来打印---矩阵实际存的是0表示无边。如果你把无权图改成用INF表示无边这个判断要同步改否则会把INF当成权值建出一条边。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;DispAdj的打印格式是顶点下标: 邻接点1 邻接点2 ...只打印adjvex不打印权值。想看到权值的话把printf(%3d, p-adjvex)改成printf(%3d(%d), p-adjvex, p-info)就行。这个函数里有个小坑if (p ! NULL) printf(%3d:, i)只在链表非空时打印顶点号孤立顶点会被完全跳过输出里看不出它存在。调试时如果发现顶点数对不上先检查这里。3.3 程序二邻接表转回矩阵与手动输入改造程序二复用同一个main在DispAdj之后调ListToMat(G, g1)把链表转回矩阵再DispMat(g1)打印。ListToMat先把g-arcs全部清零然后遍历每个顶点的边链表把p-info写到g-arcs[i][p-adjvex]。这一步是矩阵转链表的逆操作逻辑对称但要注意清零必须在遍历之前否则残留的旧值会混进结果。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;题目要求里还有一条“手动输入任意图形”原始代码没实现但改造起来不难。思路是把main里写死的A数组换成scanf循环先读顶点数和弧数再读每条弧的起点、终点、权值直接往矩阵里填。下面这段可以插在g.vexnum赋值之后替换掉硬编码部分。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) { int u, v, w; printf(输入第 %d 条弧 (起点 终点 权值): , k 1); scanf(%d %d %d, u, v, w); g.arcs[u][v] w; // 有向图只填一个方向 }手动输入版本要注意两个边界一是u、v必须落在0到vexnum-1之间否则写矩阵时越界二是重复输入同一条弧时后一次会覆盖前一次arcnum却照加导致计数和实际边数不符。稳妥做法是输入前先检查g.arcs[u][v]是否已经非零非零就提示重复并让用户重输。这些校验原始代码没有但真拿去做课程设计或小工具时加上能省不少调试时间。4. 避坑与排查这份代码里最容易翻车的五个点4.1 邻接表内存泄漏malloc 了却没 free现象是程序跑完没报错但用valgrind或长期运行的服务里内存持续上涨。原因很直接MatToList里每个ArcNode都是malloc出来的main结束时没有对应的释放逻辑ALGraph本身也是malloc的。学习代码里这不算错但如果你把这段逻辑嵌进一个循环处理多张图的程序泄漏就会累积。解决方法是写一个DestroyAdj(ALGraph *G)遍历每个顶点的链表逐个free节点最后free(G)。调用时机放在DispAdj和ListToMat之后、main返回之前。注意释放顺序先释放边节点再释放顶点数组所在的ALGraph反过来会丢指针。4.2 矩阵转邻接表时顶点信息丢失现象是邻接表打印正常但按顶点名字输出时全是乱码或零。原因在 2.3 节提过MatToList只建了边链表没复制g-vexs[i]到G-vertices[i].data。原始示例里顶点信息没被使用所以问题被掩盖了。解决是在MatToList的初始化循环里补一行G-vertices[i].data g-vexs[i];。如果顶点信息是字符串还要注意深拷贝不能直接赋指针否则两边指向同一块内存释放时容易重复 free。4.3 用 INF 表示无边却按 0 判断现象是转换出来的邻接表多出一堆不该有的边或者矩阵打印时满屏---但链表里却有节点。原因是代码里INF定义为32767DispMat用它判断打印---但MatToList的判断条件是! 0。如果某张图的矩阵用INF填无边位置INF ! 0成立每条“无边”都会被建成一条权值为 32767 的边。解决是统一约定要么全用0表示无边要么全用INF并且把MatToList和ListToMat里的判断条件同步改掉。我一般倾向用INF因为权值为 0 的边在真实场景里是合法的比如零成本转移用 0 表示无边会混淆。4.4 固定数组越界顶点数超过 20 直接崩现象是输入 21 个顶点后程序崩溃或输出乱码。原因是MAX_VERTEX_NUM写死 20vexs、arcs、vertices都是定长数组没有任何边界检查。手动输入版本尤其危险用户不知道上限输多了就踩内存。解决有两个方向简单版是在读入vexnum后加一句if (vexnum MAX_VERTEX_NUM) { printf(顶点数超限\n); return; }彻底版是把矩阵和顶点数组改成malloc动态分配按实际顶点数申请空间。学习阶段前者够用后者留到二次开发时再做。4.5 头插法导致邻接表顺序与预期相反现象是矩阵里0 - 1, 0 - 3打印出来的邻接表却是3在前1在后和直觉不符。原因是头插法每次把新节点放在链表头部后插入的反而靠前。原始代码用倒序遍历j抵消了这个效果但如果你自己改循环方向或者改成尾插顺序就会变。解决是明确你要的顺序要升序就保持倒序遍历加头插或者正序遍历加尾插需要维护尾指针要降序就正序遍历加头插。改完之后拿一个已知矩阵对一遍输出别凭感觉判断。5. 二次开发把教学代码改成能复用的图存储模块这份代码最大的价值不是它现在能跑而是它把两种结构的转换边界划得很清楚改起来有明确的切入点。我一般会按三步走先抽公共部分再补校验最后加一个统一入口。第一步把MGraph和ALGraph的初始化、销毁、打印抽成独立函数放到graph.h里main只负责调度。这样矩阵转链表、链表转矩阵就不再依赖main里的局部变量可以被其他程序复用。抽的时候注意MatToList和ListToMat的返回值原始代码里ListToMat没写返回类型抽出来时统一改成void或int返回 0 表示成功别留着隐式int的坑。第二步补输入校验和错误码。手动输入版本至少要做三件事顶点数不超过MAX_VERTEX_NUM、弧的端点下标在合法范围内、重复弧给出提示。校验逻辑可以集中在一个ValidateEdge(u, v, n)函数里返回布尔值调用处统一处理。这样后面接文件读入或命令行参数时校验逻辑不用重写。第三步加一个ConvertGraph统一入口根据传入的源类型和目标类型自动分派。下面这个骨架可以直接套typedef enum { MATRIX, ADJLIST } GraphType; int ConvertGraph(void *src, GraphType srcType, void *dst, GraphType dstType) { if (srcType MATRIX dstType ADJLIST) { MatToList((MGraph *)src, (ALGraph *)dst); return 0; } if (srcType ADJLIST dstType MATRIX) { ListToMat((ALGraph *)src, (MGraph *)dst); return 0; } return -1; // 同类型转换或非法组合 }这个入口的好处是把“哪种转哪种”的判断收在一处后面要加第三种存储结构比如十字链表时只改这个函数和新增的转换实现调用方不用动。验证方法也简单拿原始示例的 6×6 矩阵跑一遍MATRIX - ADJLIST - MATRIX对比两次DispMat的输出是否完全一致再手动输入一个 3 个顶点的稀疏图确认邻接表里没有多余节点、矩阵里没有残留旧值。有个血泪教训值得说我早期改这类代码时喜欢直接在主函数里加逻辑改到第三版就发现main里堆了七八个临时变量转换函数之间靠全局变量传参调一次错一次。从那以后我每次动这种教学代码都先把结构体定义和函数原型单独拎到一个头文件里强制自己走一遍“声明—实现—调用”的流程再往里填逻辑。这份代码的ListToMat没写返回类型、MatToList里顶点信息没复制都是没有头文件约束时容易留下的尾巴。希望这份拆解能帮你少走一遍我踩过的弯路。本文还有配套的精品资源点击获取
