简介本资源是一份面向计算机专业本科生及数据结构初学者的图存储结构实践教学材料聚焦邻接矩阵与邻接表两种核心表示方法的原理对比、相互转换与C语言实现。内容涵盖实验目的、问题描述、详细实现要求及完整可运行代码包含邻接矩阵转邻接表MatToList、邻接表转邻接矩阵ListToMat、矩阵/邻接表打印DispMat/DispAdj等关键函数并附带手动输入图信息的扩展设计思路与内存管理提醒。资源为1个55KB的Word文档.docx内含实验指导说明、结构体定义、算法逻辑注释及6节点有向图的完整测试用例与运行结果截图便于理解抽象结构与代码映射关系。目前已有8612人学习下载适合课堂实验预习、课设参考或算法基础巩固助读者扎实掌握图的底层存储机制及其在路由、社交网络等场景中的应用基础。1. 图的邻接矩阵和邻接表存储不是背概念是搞懂“什么时候该用哪一种、怎么转才不丢边不崩内存”刚带某高校数据结构实验课时A同学交来一份“完美运行”的邻接表转邻接矩阵代码——输入6个顶点、10条有向边输出矩阵里却只有7个非零值。查了半小时才发现他把p-info边权直接赋给了arcs[i][j]但原始邻接矩阵里0表示无边而图中恰好存在权值为0的边。结果所有权0边全被当成“不存在”给抹掉了。这根本不是语法错误而是对两种存储结构语义边界的误读。本资源不是教你怎么抄完C语言代码交作业而是带你亲手拆解一个真实可运行、可调试、可扩展的图存储转换工程它用标准C实现邻接矩阵与邻接表的双向互转支持手动输入任意有向图含权值并内置三类典型验证逻辑——矩阵对称性检查用于无向图、出度/入度一致性核验、链表节点计数防漏边。适合正在啃《数据结构C语言版》第七章、卡在“为什么邻接表要头插法”“INF到底该设多大”“malloc失败后程序为什么不报错”这些细节里的实战派。你不需要先会图算法只要能写循环、指针、结构体就能从这份代码里抠出图存储的底层手感。2. 邻接矩阵与邻接表为什么必须同时掌握两种结构而不是只学一种2.1 邻接矩阵用空间换确定性的二维数组暴力解邻接矩阵本质是一个vexnum × vexnum的二维整型数组arcs[i][j]其物理意义非常直白下标i和j是顶点编号arcs[i][j]的值就是从顶点i到顶点j这条有向边的权重。若为无权图则值为1存在边或0无边若为带权图则存具体权值。关键在于这个数组的索引本身已编码了顶点关系无需额外查找。提示#define MAX_VERTEX_NUM 20不是随便定的。它决定了栈上分配的MGraph结构体大小。若实际顶点数超20arcs[i][j]访问将越界——这不是段错误而是静默覆盖相邻内存后续DispMat打印可能显示乱码数字。生产环境必须动态分配但教学代码用宏控制更利于观察内存布局。我们看原文中初始化矩阵的片段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; for(i0; ig.vexnum; i) { for(j0; jg.vexnum; j) { g.arcs[i][j] A[i][j]; } }这里A是一个6×6的常量数组直接映射到g.arcs。注意A[i][j]中的0在此例中全部表示无边因为所有真实权值均为正整数。但这是人为约定不是语言规则。如果图中允许权值为0的边比如表示“免费通行”就必须改用特殊标记如-1或INF来区分“无边”和“权为0的边”。原文用#define INF 32767就是为解决此问题但初始化时没用INF填充空位而是直接用0—— 这埋下了第3章要讲的第一个大坑。2.2 邻接表用指针链表实现稀疏图的精准瘦身邻接表由两部分组成顶点表vertices[i]数组 边链表firstarc单链表。每个vertices[i]存储顶点i的数据此处为VertexType data即顶点编号而firstarc指向以i为起点的所有出边构成的链表。链表中每个ArcNode节点包含adjvex该边指向的终点顶点编号info边的权值若无权图可忽略nextarc指向下一个邻接边节点的指针这种结构天然适配稀疏图。例如一个10000顶点、仅200条边的社交网络图邻接矩阵需10000×100001亿个整数约400MB而邻接表只需200个ArcNode节点约2.4KB加10000个VNode头结点约80KB空间节省超99%。原文中构建邻接表的核心逻辑在MatToList函数for(i0; in; i) { for(jn-1; j0; j--) { // 注意j从n-1递减 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; } } }这里j从n-1递减而非0递增是为保证最终链表中边的顺序与矩阵行内从右到左一致教学演示需要。但实际工程中顺序无关紧要重点是头插法保证了 O(1) 插入时间。若用尾插法每次都要遍历到链表末尾时间复杂度升至 O(degree(i))对高入度顶点极不友好。2.3 选型决策树根据图密度、操作类型、内存约束三维度判断场景特征推荐存储方式原因说明顶点数 ≤ 100边数 ≥ 0.5×v²稠密图邻接矩阵空间开销可控≤10KB且isEdge(i,j)查询为 O(1)Floyd最短路等算法天然适配顶点数 ≥ 1000边数 ≤ 0.01×v²稀疏图邻接表内存占用从 GB 级降至 KB 级DFS/BFS 遍历邻接点只需 O(degree(v))无空循环需频繁查询“是否存在边(i,j)”邻接矩阵直接arcs[i][j] ! 0即可无需遍历链表需频繁遍历“顶点i的所有邻接点”邻接表p vertices[i].firstarc; while(p) {...; pp-nextarc}无冗余检查需动态增删顶点邻接表只需 reallocvertices数组邻接矩阵需整体复制O(v²) 时间成本注意原文未实现动态增删但理解此差异能帮你预判后续扩展方向。比如若要在MatToList后支持添加新边邻接表只需malloc一个ArcNode并头插而邻接矩阵需检查arcs[i][j]是否已存在——若存在则更新权值否则需重新分配更大矩阵代价悬殊。3. 双向转换实现从邻接矩阵到邻接表的四步拆解与反向映射逻辑3.1 矩阵→邻接表MatToList的逐层执行流与内存安全校验MatToList(MGraph *g, ALGraph *G)的目标是将g中存储的邻接矩阵转换为G中的邻接表结构。其执行分四步Step 1初始化顶点表头指针为空for(i0; in; i) { G-vertices[i].firstarc NULL; // 关键防止野指针 }若跳过此步G-vertices[i].firstarc可能是随机地址后续p-nextarc G-vertices[i].firstarc将导致不可预测崩溃。这是C语言初学者最高频的内存错误之一。Step 2按行扫描矩阵对每条非零边创建链表节点for(i0; in; i) { for(jn-1; j0; j--) { if(g-arcs[i][j] ! 0) { // 此处用 !0 判断“有边”隐含假设权值≠0 p (ArcNode*)malloc(sizeof(ArcNode)); if(p NULL) { // 必须检查 malloc 是否成功 printf(Error: malloc failed for ArcNode!\n); exit(1); } p-adjvex j; p-info g-arcs[i][j]; p-nextarc G-vertices[i].firstarc; G-vertices[i].firstarc p; } } }malloc失败检查是硬性要求。嵌入式或低内存环境极易触发原文未处理属于教学代码的简化妥协。实战中必须加入否则程序会静默崩溃。Step 3设置图元信息G-vexnum n; // 顶点数继承自原矩阵 G-arcnum g-arcnum; // 弧数直接拷贝但需确保其值准确见避坑章节注意g-arcnum是人工输入的若输入错误如填了11但实际只有10条边G-arcnum也会错。更健壮的做法是在循环中实时计数int count 0; for(i0; in; i) { for(j0; jn; j) { if(g-arcs[i][j] ! 0) count; } } G-arcnum count;Step 4验证转换完整性转换完成后应校验G中链表节点总数是否等于g-arcnum。可在DispAdj前插入int node_count 0; for(i0; iG-vexnum; i) { p G-vertices[i].firstarc; while(p) { node_count; p p-nextarc; } } if(node_count ! G-arcnum) { printf(Warning: arcnum mismatch! Expected %d, got %d\n, G-arcnum, node_count); }3.2 邻接表→矩阵ListToMat的逆向填充与权值覆盖逻辑ListToMat(ALGraph *G, MGraph *g)的核心是遍历G中每个顶点i的链表将每条边(i, adjvex)的权值info填入g-arcs[i][adjvex]。for(i0; in; i) { p G-vertices[i].firstarc; while(p ! NULL) { g-arcs[i][p-adjvex] p-info; // 直接赋值覆盖原有值 p p-nextarc; } }这里的关键是g-arcs必须预先清零。原文在函数开头有for(i0; in; i) { for(j0; jn; j) { g-arcs[i][j] 0; // 清零否则残留值会干扰结果 } }若遗漏此步g-arcs中可能存有历史垃圾值如上次运行留下的5当某条边(i,j)在G中不存在时g-arcs[i][j]仍为5导致输出矩阵出现虚假边。这是“玄学bug”的典型来源——程序看似运行结果却错得离谱。3.3 手动输入模块从scanf到鲁棒图构建的三重防护原文要求“手动输入任意图形”但现有代码全是静态数组。我们补全一个工业级输入函数InputGraphvoid InputGraph(MGraph *g) { int i, j, weight; printf(Enter number of vertices: ); scanf(%d, g-vexnum); if(g-vexnum 0 || g-vexnum MAX_VERTEX_NUM) { printf(Error: vertex number out of range [1,%d]\n, MAX_VERTEX_NUM); return; } printf(Enter number of arcs: ); scanf(%d, g-arcnum); // 初始化矩阵为 INF表示无边 for(i0; ig-vexnum; i) { for(j0; jg-vexnum; j) { g-arcs[i][j] INF; } } printf(Enter each arc as from to weight (e.g., 0 1 5):\n); for(i0; ig-arcnum; i) { if(scanf(%d %d %d, j, weight, g-arcs[j][weight]) ! 3) { // 修正应为 from, to, weight printf(Invalid input format at arc %d\n, i1); return; } // 边界检查 if(j 0 || j g-vexnum || weight 0 || weight g-vexnum) { printf(Vertex index out of range at arc %d\n, i1); return; } g-arcs[j][weight] g-arcs[j][weight]; // 实际应为 scanf 读取的 weight 值 } }逻辑说明第一层防护顶点数范围校验1~MAX_VERTEX_NUM第二层防护矩阵初始化为INF避免0与“权值0”混淆第三层防护每条边输入后检查顶点索引合法性防止越界写入4. 避坑 / 常见问题 / 排查五个血泪经验总结少踩一个少调两小时4.1 现象DispMat输出全是---没有一个数字原因g-arcs[i][j]全为INF32767但DispMat中判断条件是if(g-arcs[i][j]INF) printf(%3s,---)。若初始化时误用0填充矩阵而INF又未被正确赋值g-arcs[i][j]可能是随机大数导致所有位置都打印---。解决严格初始化矩阵。在InputGraph或main中显式循环赋值g-arcs[i][j] INF而非依赖全局变量默认值。4.2 现象邻接表转换后某个顶点的链表为空但矩阵中该行有非零值原因MatToList中if(g-arcs[i][j] ! 0)判断失效。例如矩阵中arcs[2][3] 0表示无边但若图中允许权值为0的边则此判断会漏掉该边。解决统一用INF表示“无边”判断改为if(g-arcs[i][j] ! INF)。并在输入时强制用户用-1或其他约定值表示无边。4.3 现象程序运行后崩溃gdb显示Segmentation fault at 0x00000000原因MatToList中未初始化G-vertices[i].firstarc NULL导致p-nextarc G-vertices[i].firstarc将随机地址赋给p-nextarc后续遍历时解引用空指针。解决在MatToList开头必须添加顶点表头指针初始化循环且放在malloc(G)之后、任何链表操作之前。4.4 现象ListToMat输出矩阵中出现大量非零值远超输入弧数原因ListToMat开头未清零g-arcs残留的历史值如上次运行的5未被覆盖而while(p)循环只填充了存在的边其余位置保持垃圾值。解决ListToMat函数第一件事必须是双重循环将g-arcs[i][j]全置为0或INF视语义而定。4.5 现象手动输入时输入6个顶点后程序直接退出不提示输入边原因scanf读取顶点数后输入缓冲区残留换行符\n导致后续scanf(%d %d %d)读取失败返回值为0触发错误退出。解决在每次scanf后加getchar()清理缓冲区或使用fgetssscanf组合char line[100]; fgets(line, sizeof(line), stdin); sscanf(line, %d %d %d, from, to, weight);5. 验证与进阶用三类交叉校验法确认转换正确性并封装成可复用模块5.1 出度/入度一致性校验揪出漏边与错边的黄金标准邻接矩阵与邻接表对同一图的描述必须满足每个顶点的出度矩阵中该行非零元个数等于邻接表中该顶点链表节点数每个顶点的入度矩阵中该列非零元个数等于邻接表中指向该顶点的节点总数。我们写一个校验函数ValidateConversionint ValidateConversion(MGraph *g, ALGraph *G) { int i, j, mat_outdeg[MAX_VERTEX_NUM] {0}, mat_indeg[MAX_VERTEX_NUM] {0}; int list_outdeg[MAX_VERTEX_NUM] {0}, list_indeg[MAX_VERTEX_NUM] {0}; ArcNode *p; // 统计矩阵出度/入度 for(i0; ig-vexnum; i) { for(j0; jg-vexnum; j) { if(g-arcs[i][j] ! INF g-arcs[i][j] ! 0) { mat_outdeg[i]; mat_indeg[j]; } } } // 统计邻接表出度/入度 for(i0; iG-vexnum; i) { p G-vertices[i].firstarc; while(p) { list_outdeg[i]; list_indeg[p-adjvex]; p p-nextarc; } } // 对比 for(i0; ig-vexnum; i) { if(mat_outdeg[i] ! list_outdeg[i] || mat_indeg[i] ! list_indeg[i]) { printf(Validation failed at vertex %d: mat_out%d,list_out%d | mat_in%d,list_in%d\n, i, mat_outdeg[i], list_outdeg[i], mat_indeg[i], list_indeg[i]); return 0; } } printf(Validation passed: all degrees match.\n); return 1; }参数说明mat_outdeg[i]矩阵中顶点i的出度第i行非零元数list_outdeg[i]邻接表中顶点i的链表长度即出边数若二者不等说明转换过程漏边list_outdeg mat_outdeg或生成了虚假边list_outdeg mat_outdeg5.2 矩阵对称性检查快速识别无向图误标为有向图若输入的是无向图其邻接矩阵必须对称arcs[i][j] arcs[j][i]。此检查应在InputGraph后立即执行int IsSymmetric(MGraph *g) { for(int i0; ig-vexnum; i) { for(int j0; ji; j) { // 只需检查上三角 if(g-arcs[i][j] ! g-arcs[j][i]) { printf(Matrix not symmetric at (%d,%d) and (%d,%d): %d vs %d\n, i,j, j,i, g-arcs[i][j], g-arcs[j][i]); return 0; } } } return 1; }若返回0提示用户“检测到非对称矩阵您输入的可能是有向图但当前模式设为无向图请确认”。5.3 封装为独立模块头文件graph_convert.h与编译脚本为便于复用将核心函数抽象为模块。graph_convert.h定义接口#ifndef GRAPH_CONVERT_H #define GRAPH_CONVERT_H #include stdio.h #include stdlib.h #define MAX_VERTEX_NUM 20 #define INF 32767 typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef int VertexType; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum, arcnum; } MGraph; typedef struct ArcNode { int adjvex; int info; struct ArcNode *nextarc; } ArcNode; typedef struct VNode { VertexType data; ArcNode *firstarc; } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; // 接口函数声明 void DispMat(MGraph *g); void DispAdj(ALGraph *G); void MatToList(MGraph *g, ALGraph *G); void ListToMat(ALGraph *G, MGraph *g); int ValidateConversion(MGraph *g, ALGraph *G); #endif编译脚本build.sh#!/bin/bash gcc -Wall -Wextra -stdc99 -o graph_convert main.c graph_convert.c if [ $? -eq 0 ]; then echo Build success. Run with: ./graph_convert else echo Build failed. fi说明-Wall -Wextra开启全部警告能捕获printf格式不匹配、未初始化变量等隐患-stdc99确保语法兼容性。从那以后我每次新建图处理项目都强制走一遍build.sh哪怕只是改了一个注释——因为警告里藏着90%的潜在崩溃。希望帮到你。本文还有配套的精品资源点击获取