简介这份资源面向正在学习数据结构、需要攻克图存储难点的学生与编程初学者聚焦图的邻接矩阵与邻接表两种存储结构及其相互转换。内容以有向图为例给出邻接矩阵的二维数组定义与邻接表的顶点、边节点结构并实现DispMat、MatToList、DispAdj、ListToMat等函数覆盖矩阵转邻接表、邻接表转矩阵以及手动输入图信息后转换的完整流程同时提示动态内存分配与释放等注意事项。资源包共1个docx文件约55KB以实验报告形式组织目的、问题描述、要求与完整C语言源码便于对照理解与上机复现。已有8614人学习适合作为图存储章节的实验参考与课程作业辅助材料帮助读者理清两种存储方式的适用场景与转换思路。1. 图的两种存储一张知识地图先摆出来图的存储这块很多人第一反应是“邻接矩阵和邻接表嘛背过”可真到写代码、做转换、考试画图的时候翻车往往就出在细节上。它其实是数据结构里少有的“两种表示、一套语义”的知识点同一个有向图用二维数组装是一副样子用数组加链表装又是另一副样子而所有图算法——遍历、最短路、拓扑排序——都建立在这两种底座之上。复习时如果只记住“矩阵查边快、邻接表省空间”这句口诀遇到权值、有向无向、头插尾插、INF 与 0 的区分立刻就会卡壳。这篇笔记把邻接矩阵与邻接表的定义、转换、易错点和复习清单串成一条线适合正在系统学图、或者考前想快速查漏补缺的人。2. 邻接矩阵二维数组里的图长什么样2.1 结构定义与三个核心字段邻接矩阵的本质是用一个二维数组arcs[i][j]表示顶点 i 到顶点 j 之间有没有边、边权是多少。围绕它要记的结构体通常只有三个字段顶点表vexs、矩阵arcs、以及vexnum顶点数和arcnum弧数。顶点表存的是顶点本身的信息矩阵存的是关系两个计数负责边界控制。C 语言里常见的写法是这样#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是容量上限vexnum是实际用了多少两者不能混。矩阵里arcs[i][j]的取值有三种语义要分清0 表示无边非零表示有边无权图常写 1而带权图里“无边”通常用一个极大值INF表示不能再用 0否则会把权值为 0 的边误判成不存在。这个区分是后面所有转换和打印的地基。2.2 有向图与无向图的对称性差异邻接矩阵最容易被忽略的性质是对称性。无向图的边没有方向i 到 j 有边j 到 i 也必然有边所以矩阵沿主对角线对称arcs[i][j] arcs[j][i]。有向图则不然arcs[i][j]只表示 i 指向 j反向不一定存在矩阵一般不对称。这个差异直接影响两件事一是建图时无向图要写两次arcs[i][j]和arcs[j][i]同时赋值有向图只写一次二是做转换时无向图转邻接表每条边会出现两次每个顶点各挂一个边结点有向图只出现一次。复习时拿一个有向图和一个无向图各画一遍矩阵对称与不对称的差别一眼就能看出来比背定义管用。2.3 空间与查询的取舍O(n²) 换 O(1)邻接矩阵的存储代价固定是 n² 个单元跟边数无关。稠密图边数接近 n²用它很划算稀疏图边远少于 n²就浪费严重。换来的好处是查询极快判断 i、j 之间有没有边直接看arcs[i][j]O(1)。另外它天然适合需要“按矩阵下标随机访问”的算法比如 Floyd 最短路就是直接在矩阵上做三重循环。所以选型不是谁绝对好而是看图的稠密度和算法需求。考试里常问“某图用哪种存储更合适”答案要落到边数与 n² 的关系上而不是一句“邻接表省空间”了事。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;firstarc是每条链表的头nextarc把同一起点的边串起来。注意adjvex存的是“对方顶点的下标”不是权值权值在info里这两个字段写反是初学阶段的高频错误。顶点数组用AdjList这个数组类型一次性声明长度由MAX_VERTEX_NUM限定实际有效长度看vexnum。3.2 头插法建表与边的顺序问题从矩阵转邻接表时遍历矩阵的列遇到非零就为它分配一个边结点然后插到对应顶点链表的头部这就是头插法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倒着走插完之后链表里邻接点的下标正好是从小到大打印出来好看也好对。如果正序遍历又用头插输出顺序就是反的很多同学对着答案怀疑自己逻辑错了其实只是插入方向的问题。这一点在手工画图和写实验报告时特别容易暴露属于“不改也能跑、但一比对就露馅”的细节。3.3 空间按边数走稀疏图的主场邻接表的空间是“顶点数 边数”量级每条实际存在的边才占一个结点稀疏图下比 n² 省得多。代价是查询 i、j 是否有边要顺着 i 的链表找最坏 O(degree(i))不如矩阵的 O(1)。它更适合需要“枚举某顶点所有邻居”的场景比如图的深度优先遍历、广度优先遍历顺着firstarc一路nextarc就能把邻居走完这正是邻接表的强项。选型时把“查边多还是遍历邻居多”想清楚答案自然出来。4. 双向转换矩阵与邻接表互转的完整链路4.1 矩阵转邻接表遍历列、建结点、挂链矩阵转邻接表的核心是“按行扫描矩阵非零即建边”。外层 i 遍历每个起点内层 j 遍历所有可能的终点arcs[i][j]非零就说明 i 到 j 有边为它建一个边结点挂到顶点 i 的链表上。转换前必须先把每个顶点的firstarc置空否则指针是野值挂链时直接崩。转换完成后同步vexnum和arcnum让新结构自洽。这里有个容易漏的点判断条件用! 0还是! INF取决于矩阵里“无边”到底怎么表示。如果带权图用INF表示无边那判断就该是arcs[i][j] ! INF用 0 判断会把权值为 0 的合法边漏掉。4.2 邻接表转矩阵先清零、再按链表回填反方向转换要先初始化矩阵把所有元素清成“无边”的表示无权图清 0带权图清 INF然后遍历每个顶点的边链表把arcs[i][p-adjvex]填成p-infofor (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; } }“先清零”这一步不能省。如果矩阵是局部变量又没初始化残留的随机值会让转换结果多出一堆莫名其妙的边这种 bug 排查起来很费时间属于典型的血泪经验。回填时下标是i和p-adjvex前者是起点、后者是终点写反了得到的就是转置矩阵有向图下错误非常隐蔽。4.3 打印函数把结构“翻译”成人能看的形式转换对不对最终要靠打印验证。矩阵打印按行列输出遇到INF打---之类占位符其余按数值输出邻接表打印则逐顶点输出“顶点下标邻居1 邻居2 …”。打印函数看着简单却是调试转换逻辑的黑匣子矩阵转表后打印表表转矩阵后打印矩阵两次输出一比对转换是否保真立刻见分晓。建议在转换前后各打印一次形成“输入—中间—输出”的对照比单看最终结果可靠得多。5. 易错点清单这五处最容易翻车5.1 易错点一0 与 INF 的语义混用为什么漏教材里无权图用 0/1带权图用 INF两套约定混着记写代码时就随手用 0 判无边。怎么补动手前先明确这张图是带权还是无权带权图统一用INF表示无边、用具体数值表示边权判断条件一律写! INF无权图才用 0 表示无边。把这条约定写在代码注释第一行后面所有函数都遵守它。5.2 易错点二头插法导致邻接点顺序颠倒为什么漏头插法逻辑本身没错跑起来结果也对只是顺序和手工画的不一致容易被当成“答案错了”。怎么补要么内层倒序遍历配合头插要么改用尾插保持正序。复习时明确自己用的是哪种画图核对时按同样规则画别拿正序的图去对倒序的输出。5.3 易错点三转换前忘记初始化目标结构为什么漏矩阵转表时忘了把firstarc置空表转矩阵时忘了清零矩阵局部变量的随机初值直接污染结果。怎么补把“初始化目标结构”当成转换函数的第一步固定动作firstarc NULL、矩阵整体赋“无边”值写完再进入主循环。养成“先清后填”的习惯这类 bug 基本绝迹。5.4 易错点四有向图与无向图的边数翻倍为什么漏无向图一条边在矩阵里占两个位置转成邻接表会出现两个边结点arcnum的统计口径容易算错。怎么补建图时就想清楚方向性无向图赋值写对称的两格统计边数时按“实际边数”记而不是按“非零元素个数”记转换后核对arcnum是否与源结构一致不一致就回头查对称赋值。5.5 易错点五动态内存只申请不释放为什么漏实验代码跑通就交malloc出来的边结点没人管程序结束由系统回收看起来“没影响”。怎么补转换函数结束时遍历每个顶点的链表逐个free边结点再释放图结构本身。虽然小实验里不释放也能跑但这是内存管理的基本功养成习惯比事后补锅强。6. 复习清单从画图到代码的查漏补缺路径复习这块我自己的顺序是“先画后写再对”。第一步随手拿一个有向图和一个无向图各画一遍邻接矩阵和邻接表重点核对三件事无向图矩阵是否对称、有向图邻接表每条边是否只出现一次、带权图的无边格是否标成 INF。画完对照下面这张表自查哪一格对不上就回到对应章节补检查项邻接矩阵邻接表空间量级O(n²)与边数无关O(ne)随边数增长查边 i→jO(1)直接取arcs[i][j]O(degree(i))顺链表找枚举邻居O(n)扫一整行O(degree(i))顺链表走无向图表现矩阵对称两个非零格每条边两个边结点带权无边表示用 INF不能用 0不存在的边不建结点第二步把两个转换函数默写一遍重点盯初始化、判断条件、下标方向三处写完用一个小图手工推演矩阵转表后打印表转矩阵后再打印两次输出和原图比对。第三步专门练“手动输入建图”这个变体——它把固定数组换成运行时读入考的是vexnum、arcnum的读入顺序和循环边界很多人固定数据跑得飞起一改成输入就数组越界原因往往是先读边数再读顶点、或者循环上界用了常量而不是vexnum。提示转换正确性的最低验证标准是“转过去再转回来和原结构逐格一致”有向图下这一步能同时抓出下标写反和漏边两类错误。我早期做这类实验习惯是代码跑通就收工结果一到手画图、一改输入方式就原形毕露。从那以后我每次碰图的存储都强制走一遍“画图—默写—互转验证”的流程哪怕只是复习也先画两张图再动键盘。这套笨办法救过我不少次希望帮到你。本文还有配套的精品资源点击获取