简介《数据结构课程设计-校园导航系统》是一份面向计算机相关专业学生与数据结构初学者的课程设计文档围绕校园地图建模、景点信息查询与任意两点最短路径求解展开适合用于课程设计参考、实验报告撰写和算法复习。压缩包共1个doc文件大小约187KB内容以课程设计报告为主体涵盖任务书、详细设计、调试与测试、时间复杂度分析、源程序清单与执行结果以及总结、致谢和参考文献等模块。已有67人学习说明其对同类课设具有一定参考价值。文档中可重点查看邻接矩阵存储图结构、景点顺序表设计、Floyd算法求最短路径的实现思路以及调试过程中正序输出等问题的处理记录便于读者对照梳理从需求分析、数据结构选型到测试总结的完整流程。1. 从一份课设说起10 个景点、14 条路最短路径怎么求每学期期末总有人抱着一份“数据结构课程设计”到处问校园导航系统到底该从哪下手。题目看着很朴素——把校园画成一张图景点当顶点道路当边给任意两个地方找出一条最短路径。真动笔才发现坑全在细节里景点信息存哪、边权怎么灌、路径怎么还原、逆序查为什么输出乱掉。这份报告给出的解法是邻接矩阵存图、顺序表存景点、Floyd 算法算全源最短路径C 语言落地六个头文件加一个主文件控制台菜单交互时间复杂度 O(n³)。它适合正在赶课设、需要一份能直接跑起来又能改的同学也适合想把图论从课本搬到键盘上的开发者。下面按“骨架 → 建图 → 算法 → 踩坑 → 改造”的顺序拆一遍。2. 技术选型与工程骨架六个头文件怎么分工2.1 文件划分谁定义结构、谁负责建图拿到一份 C/C 课设源码第一件事不是看 main而是看头文件怎么切的。这套代码切得挺干净六个文件各管一件事文件职责里面有什么school.cpp主文件顶点初始数据、边初始数据、调用建图、进菜单SeqList.h线性表顺序表结构体、初始化、插入、取长度AdjMGraph.h图结构AdjMGraph定义、初始化、销毁AdjMGraphCreat.h建图把顶点数组 边数组一次性灌进图里Floyd.h算法全源最短路径产出weight和path两张表Inquiry.h业务景点信息查询、两景点路径查询与打印Operation.h交互菜单、两个查询入口的包装这种切法的好处是算法层Floyd.h完全不认识“景点”这个概念它只认int下标和权重矩阵景点语义全部压在Inquiry.h里。换句话说想把这个导航系统改造成“地铁换乘”或者“机房设备连通性”只需要换掉school.cpp的初始数据算法一行不用动。这是我比较认可的一种课设结构——虽然它简单但边界是对的。顺序表这块顺手带一句。报告里没贴SeqList.h全文按常规实现它长这样/* SeqList.h —— 顺序表连续存储 当前长度 */ #define MaxSize 20 typedef struct { DataType list[MaxSize]; /* 静态数组容量编译期定死 */ int size; /* 当前已存放的元素个数 */ } SeqList; void ListInitiate(SeqList *L) { L-size 0; } int ListInsert(SeqList *L, int pos, DataType x) { int i; if (L-size MaxSize) return 0; /* 满了插入失败 */ if (pos 0 || pos L-size) return 0; for (i L-size; i pos; i--) /* 从尾往前挪给 pos 腾位置 */ L-list[i] L-list[i - 1]; L-list[pos] x; L-size; return 1; }ListInsert的循环方向是有讲究的必须从size往pos倒着挪正着挪会把后面的元素覆盖掉。这类小地方在课设里翻车率极高后面第 5 章还会提到。2.2 三个结构体定骨架景点、顶点表、边整套程序的“数据模型”只有三个结构体认清它们剩下的都是流程。/* 1. 景点图上每个顶点携带的业务信息 */ typedef struct { char name[20]; /* 景点名称靠它做查询的 key */ int code; /* 代号方便口头报数 */ char introduction[50]; /* 一句话简介 */ } DataType; /* 2. 边建图时的“一次性输入格式”不是图本身 */ typedef struct { int row; int col; int weight; } RowColWeight; /* 3. 图邻接矩阵 顶点顺序表 */ typedef struct { SeqList vertices; /* 顶点集合 */ int Edge[MaxVertices][MaxVertices]; /* 邻接矩阵 */ int numOfEdge; /* 边数无向图记一条算一条 */ } AdjMGraph;DataType里name给 20 字节是个隐藏约束中文按 UTF-8 一个字 3 字节实际只能放 6 个汉字左右。报告里的景点名都在 5 字以内“学生第二食堂”刚好 6 字 18 字节已经贴着上限了再多一个字就溢出。这个坑后面单独说。RowColWeight这个结构体值得单独夸一句。它的作用是把“图长什么样”和“图怎么存”解耦主文件里写一堆{0,1,20}这样的三元组像填表格一样描述校园路网建图函数负责翻译成矩阵。改路网的时候只动数组不动逻辑这对课设后期反复调数据非常友好。2.3 邻接矩阵还是邻接表这道题不用纠结理论上讲稀疏图用邻接表省空间稠密图用邻接矩阵查询快。但放到这道题的具体场景里答案几乎是唯一的顶点数 10 个左右邻接矩阵是 10×10 100 个 int约 400 字节。邻接表要额外维护节点指针、链表遍历代码量翻倍省下来的那点内存还不够写指针的开销。更关键的是 Floyd 算法的输入天然就是矩阵形式——weight[i][k] weight[k][j]如果用邻接表每次取边权都得遍历链表三重循环里套链表遍历性能和代码可读性双输。所以这里的选择不是“权衡”而是“别折腾”。真正需要换邻接表的场景是顶点上千、边却很稀比如全国城市路网那时候矩阵会有大量MaxWeight浪费空间Floyd 的 O(n³) 也跑不动了得换成 Dijkstra 堆。这道题规模决定了矩阵 Floyd 就是最省事的组合。提示MaxWeight定义成 1000 表示“不可达”这是课设里的常见做法但它不是真无穷。如果哪条路径累加超过 1000就会和“不可达”混淆。规模小的时候没事规模一大必须换成INT_MAX并在加法前判溢出。3. 数据录入与建图从三元组数组到邻接矩阵3.1 顶点表怎么填DataType 数组与顺序表初始化主文件里的顶点数组就是一张“景点台账”下标即顶点编号这个约定贯穿全程序/* school.cpp —— 顶点初始化下标 0~9 就是顶点编号 */ DataType v[] { {学生第二食堂, 10, 学生的主要就餐点}, {男生宿舍, 11, 一共有八栋}, {操场, 12, 最新的塑胶跑道和人工草坪}, {物理楼, 13, 拥有各种实验器材}, {博学楼, 14, 学生上课集中地}, {草地, 15, 休闲娱乐的好地方}, {老教, 16, 学校最早的教学楼}, {女生宿舍, 17, 一共七栋}, {小门, 18, 可以通往校外生活区}, {图书馆, 19, 藏书五十万册} };这里有个容易忽略的点code字段10~19和数组下标0~9是两套编号。code是给人看的下标是给程序用的。如果后面想做“输入 13 直接跳到物理楼”的功能就得再写一个按code反查下标的函数不能拿code当数组下标用——这是新手最常犯的越界来源之一。建图函数先把顶点搬进顺序表再把矩阵初始化成“对角线 0、其余不可达”/* AdjMGraphCreat.h —— 建图 */ void Creat(AdjMGraph *G, DataType v[], RowColWeight e[], int n, int eCount) { int i, j, k; /* 第一步顶点入表 */ ListInitiate(G-vertices); for (i 0; i n; i) ListInsert(G-vertices, i, v[i]); /* 第二步矩阵初始化自己到自己距离 0其余视为不可达 */ for (i 0; i n; i) for (j 0; j n; j) G-Edge[i][j] (i j) ? 0 : MaxWeight; /* 第三步按边表灌权重无向图两个方向都要写 */ for (k 0; k eCount; k) { G-Edge[e[k].row][e[k].col] e[k].weight; G-Edge[e[k].col][e[k].row] e[k].weight; } G-numOfEdge eCount; }第二步的对角线置 0 不能省。Floyd 的第一轮递推依赖weight[i][i] 0如果对角线是MaxWeightweight[i][k] weight[k][k]就会变成MaxWeight x虽然多数情况下不会误更新但一旦数据里有负数权重就会全盘出错这道题没有负权属于防御性写法。第三步是重点。校园道路是双向的{3,4,30}表示“物理楼到博学楼 30 米”反方向也是 30 米所以必须写两遍矩阵。报告原稿的边表里是把两个方向都列出来的共 28 条效果一样但那样容易漏——漏一条镜像边图就变成有向图正向查有路、反向查不通这种 bug 排查起来非常费劲。我的习惯是边表只写单方向靠建图函数统一对称写。3.2 边表怎么灌14 条道路撑起一张连通图按单方向写法14 条无向边就够了对应原稿的 28 条有向记录/* 每条边只写一次{起点下标, 终点下标, 距离} */ RowColWeight e[] { {0, 1, 20}, {0, 2, 30}, {0, 3, 35}, /* 食堂连宿舍、操场、物理楼 */ {1, 3, 20}, /* 男宿连物理楼 */ {2, 3, 15}, {2, 4, 30}, /* 操场连物理楼、博学楼 */ {3, 4, 30}, /* 物理楼连博学楼 */ {4, 5, 10}, /* 博学楼连草地 */ {5, 6, 35}, {5, 8, 8}, /* 草地连老教、小门 */ {6, 7, 20}, {6, 8, 25}, {6, 9, 5}, /* 老教连女宿、小门、图书馆 */ {7, 8, 10} /* 女宿连小门 */ }; int n 10; /* 顶点数 */ int eCount 14; /* 边数无向图一条算一条 */这张路网的结构看一眼就明白0 号食堂是枢纽6 号老教是第二个枢纽5 号草地和小门8之间只有 8 米的短边9 号图书馆只通过 5 米的小路挂在老教上——典型的“末端建筑”。这种拓扑在后面的路径回溯里会出问题从图书馆9去食堂0路径要经过 6→5→4→3→0编号一路下降反过来从食堂去图书馆编号一路上升。原报告正是在“编号单调性”上翻了车第 5 章展开。加边的时候顺手做个自检无向图的矩阵必须关于主对角线对称且对角线全 0。写个十行的校验函数比肉眼盯 100 个数字靠谱得多/* 建图后自检对称性 对角线 */ int CheckGraph(AdjMGraph *G, int n) { int i, j; for (i 0; i n; i) { if (G-Edge[i][i] ! 0) return 0; /* 自己到自己必须是 0 */ for (j 0; j n; j) if (G-Edge[i][j] ! G-Edge[j][i]) /* 不对称说明漏写镜像边 */ return 0; } return 1; }3.3 主函数的调用链与菜单入口主函数短得可怜就三件事备数据、建图、进菜单。/* school.cpp 主流程 */ int main(void) { AdjMGraph G; Creat(G, v, e, n, eCount); /* 顶点 边 → 邻接矩阵 */ if (!CheckGraph(G, n)) { /* 自检不过就直接退出别带着脏数据跑 */ printf(图数据有误请检查边表。\n); return -1; } menu(G); /* 进入交互循环 */ return 0; }注意这里G是传地址的不是全局变量。原报告里AdjMGraph G;定义在school.cpp的全局作用域Operation.h里的函数直接引用它这样写能跑但一旦想把菜单复用给第二张图就抓瞎了。改成指针传参只多敲几个字符换来的是可测试性——后面你可以在一份代码里同时加载“校园图”和“校区班车图”菜单传哪张就查哪张。菜单本身是个switch两个选项查景点信息、查最短路径。原稿里每次操作完直接递归调用menu()回到菜单看起来清爽实际上是个隐患——递归层数等于用户操作次数连续查五十次就压五十层栈。改成while(1)循环加break才是正解第 6 章给出改法。4. 核心算法拆解Floyd 三重循环与路径还原4.1 cost、weight、path 三张表各管什么Floyd 的函数签名里有三个二维数组第一次看容易晕其实分工很清楚/* Floyd.h —— 全源最短路径 */ void Floyd(int cost[][MaxVertices], int n, int weight[][MaxVertices], int path[][MaxVertices]) { int i, j, k; /* ① 初始化weight 复制自 costpath 全部置 -1表示没有中转点 */ for (i 0; i n; i) for (j 0; j n; j) { weight[i][j] cost[i][j]; path[i][j] -1; } /* ② 三重循环以 k 为中转点尝试松弛每一条 i→j */ for (k 0; k n; k) for (i 0; i n; i) { if (weight[i][k] MaxWeight) continue; /* 剪枝i 到 k 都不通别算了 */ for (j 0; j n; j) { if (weight[i][k] weight[k][j] weight[i][j]) { weight[i][j] weight[i][k] weight[k][j]; path[i][j] k; /* 关键记下这次的中转点 */ } } } }三张表分别是cost只读的原始邻接矩阵进来是什么样出去还是什么样。这样同一张图可以被反复调用不会被算法污染。weight结果表weight[i][j]表示 i 到 j 的最短距离。初始值是直接边权循环结束后就是最终答案。path路径索引表path[i][j] k的含义是“从 i 到 j 的最优路径会经过 k”。初始全 -1表示 i 和 j 直接相连、中间没有别的点。path是这套代码的灵魂也是最容易写错的地方。很多课设版本干脆不维护path只在最后输出一个距离数字——那这题就白做了导航系统不告诉你怎么走等于没导。维护path只需要在松弛成功的那一行加一句赋值成本极低收益极大。中间那个if (weight[i][k] MaxWeight) continue;是我加的剪枝原稿没有。不加也能出正确结果因为MaxWeight x通常大于任何真实路径不会误更新但它有两个隐患一是MaxWeight是 1000 不是真无穷如果真实路径总和接近 1000加法后可能溢出回绕成小数字从而“算出一条不存在的神奇捷径”二是白白跑了大量无意义循环。加一行判断两个问题一起解决。4.2 路径还原从 path 矩阵长出一条完整路线path[i][j] k只说“中间经过 k”但 k 之前之后还有没有别的点得递归问。正确的还原逻辑是“中序”的/* 先输出 i 和 j 之间所有的中间点不含两端 */ static void PrintMid(int path[][MaxVertices], int i, int j, SeqList *V) { int k path[i][j]; if (k -1) return; /* i、j 直接相连没中间点收工 */ PrintMid(path, i, k, V); /* 递归左半段i 到 k 之间还有没有点 */ printf(%s -- , V-list[k].name); /* 左半段吐完才轮到中转点 k */ PrintMid(path, k, j, V); /* 再递归右半段k 到 j 之间还有没有点 */ } /* 对外接口把起点、中间点、终点串成一条线 */ void PrintRoute(AdjMGraph *G, int i, int j, int weight[][MaxVertices], int path[][MaxVertices]) { if (weight[i][j] MaxWeight) { printf(这两个景点之间没有可达路径。\n); return; } printf(最短距离%d\n路线%s -- , weight[i][j], G-vertices.list[i].name); PrintMid(path, i, j, G-vertices); printf(%s\n, G-vertices.list[j].name); }为什么是“左递归 → 输出 k → 右递归”因为路径的物理顺序是从 i 走到 j中间点 k 在位置上必然在 i 和 j 之间。左半段的点全部在 k 之前右半段的点全部在 k 之后所以必须先穿过左半段、再打印 k、再穿过右半段。这个顺序一旦搞反输出的就是一条反着走的路线或者干脆乱序。原报告的实现在这里确实出了问题。它用的是非递归的单向回溯/* 原稿思路有缺陷仅作对照 */ m path[j][k]; while (m ! -1) { value[count] m; if (j k) k m; /* 靠编号大小决定往回退哪一头 */ else j m; m path[j][k]; count; } /* 输出时再用 if (j k) 判断正序还是倒序打印 */这段代码的问题在于它假设“中转点编号单调”——要么一路往小走要么一路往大走。可实际路网未必如此比如 3→2→6→9 这样的路径编号先降后升一进while就选错方向m可能在两头来回弹运气好输出错序运气差直接死循环。这就是为什么原报告自己也写了“逆序输出得到的结果有点问题”。我给出的递归版本不依赖任何编号假设任何拓扑都成立代码还短一半。4.3 景点信息查询与主循环的衔接信息查询是全部功能里最简单的一次线性扫描/* Inquiry.h —— 按名称查景点 */ void Information(AdjMGraph *G, const char *name) { int i; for (i 0; i G-vertices.size; i) { if (strcmp(G-vertices.list[i].name, name) 0) { printf(名称%s\n, G-vertices.list[i].name); printf(代号%d\n, G-vertices.list[i].code); printf(简介%s\n, G-vertices.list[i].introduction); return; } } printf(没有找到叫「%s」的景点请核对名称。\n, name); }注意两点G-vertices.size不是写死的 10而是实际插入的顶点数这样以后加景点不用改查询代码return放在找到之后避免继续扫描也避免原稿那种“循环结束后判断i size”的写法——那种写法在break和return混用时容易判断错。路径查询则是先定位两个下标再调 Floyd再打印void PathQuery(AdjMGraph *G, const char *from, const char *to) { int i LocateVertex(G-vertices, from); int j LocateVertex(G-vertices, to); int weight[MaxVertices][MaxVertices]; int path[MaxVertices][MaxVertices]; if (i -1 || j -1) { printf(输入的景点名称有误请重新输入。\n); return; } if (i j) { printf(起点和终点是同一个地方。\n); return; } Floyd(G-Edge, G-vertices.size, weight, path); /* 每次查询现算 */ PrintRoute(G, i, j, weight, path); }LocateVertex就是刚才那个线性扫描函数抽出来复用。这里每次查询都重新跑一遍 Floyd对 10 个顶点来说开销可以忽略如果顶点数上去可以加一个“脏标记 缓存”只在图结构变动后才重算这就是第 6 章的改造方向之一。4.4 复杂度核算O(n³) 在这个规模下是什么体感三重循环每层 n 次时间复杂度 O(n³)这个没有争议。n 10 时最内层执行 1000 次左右加上剪枝实际更少现代机器上耗时在微秒级用户按回车之后结果几乎瞬间出现完全没有优化必要。空间复杂度要澄清一下原报告写的是 O(1)这个说法不对。函数里开了weight和path两个 n×n 的数组加上传进来的cost实际是 O(n²)n 10 时三个矩阵一共 300 个 int约 1.2 KB栈上放得下。如果顶点数涨到 500就是 500×500×3×4 字节 ≈ 3 MB还在栈上开就会爆栈得改成malloc或者全局静态数组。这是个知识点答辩时被问到“空间复杂度多少”答 O(1) 是要扣分的。对比一下 Dijkstra单源最短路径 O(n²)如果只查一对点Dijkstra 从起点跑一遍就够比 Floyd 快一个量级。但导航系统的典型用法是“客人反复问不同起点”Floyd 一次算完所有点对后续查询全是 O(1) 查表。在交互式菜单这个场景里Floyd 反而是更划算的——这就是“全源 vs 单源”的实际取舍不是单纯比复杂度数字。5. 避坑与排查五个当时卡了我半天的现象5.1 现象逆序查路线输出乱序严重时卡死现象从编号大的景点查编号小的景点打印出来的路线顺序颠三倒四某些组合下程序直接不返回光标一直闪。原因路径回溯用的是“靠j k判断该退哪一头”的单向循环隐含假设中转点编号单调。实际路网里存在先降后升的路径一违反假设m就会在两个值之间来回弹跳出循环的条件永远不成立。这不是 Floyd 的错是回溯写法的问题。解决换成 4.2 节的递归中序回溯或者用显式栈手动模拟中序。判据很简单——把path当成二叉树path[i][j] k表示 k 是根左子树是 i→k右子树是 k→j中序遍历就是路径顺序。任何拓扑都不会出问题。5.2 现象编译报stray \243 in program现象代码看着完全正常一编译就报一串stray \243指向的行号还经常是空行或者注释行。原因中文输入法没切回来敲了全角逗号、全角分号或者全角引号“”。这些字符在 UTF-8 下是多字节编译器按单字节读第一个字节0xA3就成了非法字符。课设里最容易中招的是scanf后面的全角逗号和DataType数组初始化里的中文引号。解决编辑器打开“显示不可见字符”把全角标点高亮出来或者写完之后全局搜一遍、、这几个高频字符。我的习惯是写完一个函数就编一次别攒几百行再编报错行号会和实际位置差很远。5.3 现象查不到路时打印出 1000 或者一个离谱的小数字现象查询两个本来不连通的景点结果输出“最短距离1000”或者更诡异输出一个 200 多的小数字。原因两处。第一处是输出前没判可达性直接把MaxWeight当距离打出来了。第二处更隐蔽——MaxWeight是 1000 不是真无穷weight[i][k] weight[k][j]在中转点不可达时会算成1000 某值如果某值较大两数相加进位溢出虽然 int 不会溢出但逻辑上已经错了或者后续某轮又和别的值比较时被误判为更优从而“创造”出一条不存在的路径。解决两道保险都加上。第一道在 Floyd 内层weight[i][k] MaxWeight直接continue第二道在输出前weight[i][j] MaxWeight就打印“不可达”。想更彻底的话把MaxWeight改成INT_MAX并且只在weight[i][k] ! INT_MAX weight[k][j] ! INT_MAX时才做加法。5.4 现象某个景点的简介被另一个景点的名字“吃掉”了现象查“学生第二食堂”的时候简介打印出来前半截是对的后半截变成了别的景点的名称。原因name[20]装不下。UTF-8 中文一个字 3 字节“学生第二食堂”是 6 个字 18 字节加上结尾\0刚好 19勉强塞进 20。但如果手滑多打一个字或者用 GBK 编码时字数按 2 字节算导致两个文件编码不一致name就会溢出到相邻的code或者introduction上——结构体成员在内存里是紧挨着的溢出不报错直接静默改数据。解决name加到 32 或 64 字节别抠这十几个字节scanf用%31s限定长度而不是%sstrcpy换成strncpy并且手动补\0。这个坑的恶劣之处在于它不崩溃、不报错只是数据悄悄变脏等发现的时候已经查了半天。5.5 现象连着查了二三十次之后程序突然退出现象功能都正常就是查得多了会莫名其妙结束没有错误提示。原因菜单是递归的。Information1()和Path1()干完活之后直接调menu()回到菜单每次操作压一层栈。栈空间默认几 MB每层帧不大但查几十上百次之后终究会耗尽。课设演示时一般查不了这么多次所以这个 bug 常常被藏到答辩现场才现形。解决菜单改循环。把menu()的递归调用改成return主函数里套while (1) { menu(G); }退出条件靠菜单里的“0. 退出”分支break。层次从“递归深度 操作次数”变成“恒定一层”问题消失。6. 二次开发把课设代码改成能扩展的导航内核这份代码跑通之后真正有价值的部分才开始怎么把它从“交作业”变成“能改的东西”。我按投入产出比列几个方向从易到难。第一刀砍向硬编码。顶点的DataType v[]和边的RowColWeight e[]现在写死在school.cpp里加一个景点就得重新编译。最省事的改法是抽一个文本文件出来一行一个景点、一行一条边/* 从 campus.txt 读图格式V 名称 代号 简介 / E 起点 终点 距离 */ int LoadGraph(AdjMGraph *G, const char *path) { FILE *fp fopen(path, r); char tag[4], name[64], intro[128]; int code, r, c, w, n 0, eCount 0; DataType vs[MaxVertices]; RowColWeight es[MaxVertices * MaxVertices]; if (!fp) return 0; while (fscanf(fp, %3s, tag) 1) { if (tag[0] V) { fscanf(fp, %63s %d %127s, name, code, intro); strcpy(vs[n].name, name); vs[n].code code; strcpy(vs[n].introduction, intro); n; } else if (tag[0] E) { fscanf(fp, %d %d %d, r, c, w); es[eCount].row r; es[eCount].col c; es[eCount].weight w; eCount; } } fclose(fp); Creat(G, vs, es, n, eCount); return CheckGraph(G, n); /* 读完立刻自检脏数据当场拦下 */ }这段代码的关键不在读文件本身而在读完立刻调CheckGraph。外置数据意味着人会改错改错就得有拦截。没有自检的外置配置比硬编码更危险——硬编码改错了编译不过配置文件改错了程序照跑只是结果是错的。第二个方向是算法层。现在每次查询都重跑 Floyd10 个顶点无所谓但如果要做成“多校区 班车线路”的规模就该加缓存维护一个dirty标志图结构变动时置 1查询时若为 1 才重算。再进一步如果只需要单点查询就换 Dijkstra/* 单源 Dijkstra只查到目标点为止适合点多的图 */ void Dijkstra(int cost[][MaxVertices], int n, int src, int dist[], int prev[]) { int visited[MaxVertices] {0}; int i, k, min; for (i 0; i n; i) { dist[i] cost[src][i]; prev[i] -1; } dist[src] 0; visited[src] 1; for (k 1; k n; k) { min MaxWeight; i -1; for (int t 0; t n; t) /* 找当前最近的未访问点 */ if (!visited[t] dist[t] min) { min dist[t]; i t; } if (i -1) break; /* 剩下的都不可达 */ visited[i] 1; for (int t 0; t n; t) /* 用 i 去松弛邻居 */ if (!visited[t] dist[i] cost[i][t] dist[t]) { dist[t] dist[i] cost[i][t]; prev[t] i; /* 记前驱用于还原路径 */ } } }prev数组和 Floyd 的path作用一样只是还原方式不同——Dijkstra 是从终点一路prev往前倒退到起点得到的序列反过来打印。两种还原方式都建议封装成同一个PrintRoute接口这样换算法不用动上层调用业务层感觉不到算法变了。第三个方向是把菜单那层递归拆成事件循环。改成while (1)之后顺手把“0. 退出”加上并且把输入用fgets读进来再解析避免scanf(%d)遇到非数字输入时陷入死循环。这类输入健壮性问题在演示时最容易出洋相评审老师随手敲个字母程序就开始疯狂刷菜单。验证改造成果的办法我一直用同一套手算一条路径当基准。比如从食堂0到图书馆9手工跑一遍 Floyd得到 0→3→4→5→6→9距离 353010355 115把 115 和路线写进测试用例再挑两组“不连通”的组合确认输出是“不可达”而不是 1000最后跑一遍CheckGraph确认矩阵仍然对称。三个用例全过才认为改动没破坏原有逻辑。血泪经验是这类课设代码的错八成不在算法本身而在数据入口和输出边界——数组越界、全角标点、MaxWeight误用、递归爆栈全是同一类毛病。所以从那以后我每次动完数据结构相关的代码都强制走一遍“自检函数 手算基准用例 边界输入乱敲”三条不省这一步。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/11/6 4:20:22 · 阅读 1.2k C语言邻接矩阵+Floyd实现校园导航最短路径与路径还原
简介《数据结构课程设计-校园导航系统》是一份面向计算机相关专业学生与数据结构初学者的课程设计文档围绕校园地图建模、景点信息查询与任意两点最短路径求解展开适合用于课程设计参考、实验报告撰写和算法复习。压缩包共1个doc文件大小约187KB内容以课程设计报告为主体涵盖任务书、详细设计、调试与测试、时间复杂度分析、源程序清单与执行结果以及总结、致谢和参考文献等模块。已有67人学习说明其对同类课设具有一定参考价值。文档中可重点查看邻接矩阵存储图结构、景点顺序表设计、Floyd算法求最短路径的实现思路以及调试过程中正序输出等问题的处理记录便于读者对照梳理从需求分析、数据结构选型到测试总结的完整流程。1. 从一份课设说起10 个景点、14 条路最短路径怎么求每学期期末总有人抱着一份“数据结构课程设计”到处问校园导航系统到底该从哪下手。题目看着很朴素——把校园画成一张图景点当顶点道路当边给任意两个地方找出一条最短路径。真动笔才发现坑全在细节里景点信息存哪、边权怎么灌、路径怎么还原、逆序查为什么输出乱掉。这份报告给出的解法是邻接矩阵存图、顺序表存景点、Floyd 算法算全源最短路径C 语言落地六个头文件加一个主文件控制台菜单交互时间复杂度 O(n³)。它适合正在赶课设、需要一份能直接跑起来又能改的同学也适合想把图论从课本搬到键盘上的开发者。下面按“骨架 → 建图 → 算法 → 踩坑 → 改造”的顺序拆一遍。2. 技术选型与工程骨架六个头文件怎么分工2.1 文件划分谁定义结构、谁负责建图拿到一份 C/C 课设源码第一件事不是看 main而是看头文件怎么切的。这套代码切得挺干净六个文件各管一件事文件职责里面有什么school.cpp主文件顶点初始数据、边初始数据、调用建图、进菜单SeqList.h线性表顺序表结构体、初始化、插入、取长度AdjMGraph.h图结构AdjMGraph定义、初始化、销毁AdjMGraphCreat.h建图把顶点数组 边数组一次性灌进图里Floyd.h算法全源最短路径产出weight和path两张表Inquiry.h业务景点信息查询、两景点路径查询与打印Operation.h交互菜单、两个查询入口的包装这种切法的好处是算法层Floyd.h完全不认识“景点”这个概念它只认int下标和权重矩阵景点语义全部压在Inquiry.h里。换句话说想把这个导航系统改造成“地铁换乘”或者“机房设备连通性”只需要换掉school.cpp的初始数据算法一行不用动。这是我比较认可的一种课设结构——虽然它简单但边界是对的。顺序表这块顺手带一句。报告里没贴SeqList.h全文按常规实现它长这样/* SeqList.h —— 顺序表连续存储 当前长度 */ #define MaxSize 20 typedef struct { DataType list[MaxSize]; /* 静态数组容量编译期定死 */ int size; /* 当前已存放的元素个数 */ } SeqList; void ListInitiate(SeqList *L) { L-size 0; } int ListInsert(SeqList *L, int pos, DataType x) { int i; if (L-size MaxSize) return 0; /* 满了插入失败 */ if (pos 0 || pos L-size) return 0; for (i L-size; i pos; i--) /* 从尾往前挪给 pos 腾位置 */ L-list[i] L-list[i - 1]; L-list[pos] x; L-size; return 1; }ListInsert的循环方向是有讲究的必须从size往pos倒着挪正着挪会把后面的元素覆盖掉。这类小地方在课设里翻车率极高后面第 5 章还会提到。2.2 三个结构体定骨架景点、顶点表、边整套程序的“数据模型”只有三个结构体认清它们剩下的都是流程。/* 1. 景点图上每个顶点携带的业务信息 */ typedef struct { char name[20]; /* 景点名称靠它做查询的 key */ int code; /* 代号方便口头报数 */ char introduction[50]; /* 一句话简介 */ } DataType; /* 2. 边建图时的“一次性输入格式”不是图本身 */ typedef struct { int row; int col; int weight; } RowColWeight; /* 3. 图邻接矩阵 顶点顺序表 */ typedef struct { SeqList vertices; /* 顶点集合 */ int Edge[MaxVertices][MaxVertices]; /* 邻接矩阵 */ int numOfEdge; /* 边数无向图记一条算一条 */ } AdjMGraph;DataType里name给 20 字节是个隐藏约束中文按 UTF-8 一个字 3 字节实际只能放 6 个汉字左右。报告里的景点名都在 5 字以内“学生第二食堂”刚好 6 字 18 字节已经贴着上限了再多一个字就溢出。这个坑后面单独说。RowColWeight这个结构体值得单独夸一句。它的作用是把“图长什么样”和“图怎么存”解耦主文件里写一堆{0,1,20}这样的三元组像填表格一样描述校园路网建图函数负责翻译成矩阵。改路网的时候只动数组不动逻辑这对课设后期反复调数据非常友好。2.3 邻接矩阵还是邻接表这道题不用纠结理论上讲稀疏图用邻接表省空间稠密图用邻接矩阵查询快。但放到这道题的具体场景里答案几乎是唯一的顶点数 10 个左右邻接矩阵是 10×10 100 个 int约 400 字节。邻接表要额外维护节点指针、链表遍历代码量翻倍省下来的那点内存还不够写指针的开销。更关键的是 Floyd 算法的输入天然就是矩阵形式——weight[i][k] weight[k][j]如果用邻接表每次取边权都得遍历链表三重循环里套链表遍历性能和代码可读性双输。所以这里的选择不是“权衡”而是“别折腾”。真正需要换邻接表的场景是顶点上千、边却很稀比如全国城市路网那时候矩阵会有大量MaxWeight浪费空间Floyd 的 O(n³) 也跑不动了得换成 Dijkstra 堆。这道题规模决定了矩阵 Floyd 就是最省事的组合。提示MaxWeight定义成 1000 表示“不可达”这是课设里的常见做法但它不是真无穷。如果哪条路径累加超过 1000就会和“不可达”混淆。规模小的时候没事规模一大必须换成INT_MAX并在加法前判溢出。3. 数据录入与建图从三元组数组到邻接矩阵3.1 顶点表怎么填DataType 数组与顺序表初始化主文件里的顶点数组就是一张“景点台账”下标即顶点编号这个约定贯穿全程序/* school.cpp —— 顶点初始化下标 0~9 就是顶点编号 */ DataType v[] { {学生第二食堂, 10, 学生的主要就餐点}, {男生宿舍, 11, 一共有八栋}, {操场, 12, 最新的塑胶跑道和人工草坪}, {物理楼, 13, 拥有各种实验器材}, {博学楼, 14, 学生上课集中地}, {草地, 15, 休闲娱乐的好地方}, {老教, 16, 学校最早的教学楼}, {女生宿舍, 17, 一共七栋}, {小门, 18, 可以通往校外生活区}, {图书馆, 19, 藏书五十万册} };这里有个容易忽略的点code字段10~19和数组下标0~9是两套编号。code是给人看的下标是给程序用的。如果后面想做“输入 13 直接跳到物理楼”的功能就得再写一个按code反查下标的函数不能拿code当数组下标用——这是新手最常犯的越界来源之一。建图函数先把顶点搬进顺序表再把矩阵初始化成“对角线 0、其余不可达”/* AdjMGraphCreat.h —— 建图 */ void Creat(AdjMGraph *G, DataType v[], RowColWeight e[], int n, int eCount) { int i, j, k; /* 第一步顶点入表 */ ListInitiate(G-vertices); for (i 0; i n; i) ListInsert(G-vertices, i, v[i]); /* 第二步矩阵初始化自己到自己距离 0其余视为不可达 */ for (i 0; i n; i) for (j 0; j n; j) G-Edge[i][j] (i j) ? 0 : MaxWeight; /* 第三步按边表灌权重无向图两个方向都要写 */ for (k 0; k eCount; k) { G-Edge[e[k].row][e[k].col] e[k].weight; G-Edge[e[k].col][e[k].row] e[k].weight; } G-numOfEdge eCount; }第二步的对角线置 0 不能省。Floyd 的第一轮递推依赖weight[i][i] 0如果对角线是MaxWeightweight[i][k] weight[k][k]就会变成MaxWeight x虽然多数情况下不会误更新但一旦数据里有负数权重就会全盘出错这道题没有负权属于防御性写法。第三步是重点。校园道路是双向的{3,4,30}表示“物理楼到博学楼 30 米”反方向也是 30 米所以必须写两遍矩阵。报告原稿的边表里是把两个方向都列出来的共 28 条效果一样但那样容易漏——漏一条镜像边图就变成有向图正向查有路、反向查不通这种 bug 排查起来非常费劲。我的习惯是边表只写单方向靠建图函数统一对称写。3.2 边表怎么灌14 条道路撑起一张连通图按单方向写法14 条无向边就够了对应原稿的 28 条有向记录/* 每条边只写一次{起点下标, 终点下标, 距离} */ RowColWeight e[] { {0, 1, 20}, {0, 2, 30}, {0, 3, 35}, /* 食堂连宿舍、操场、物理楼 */ {1, 3, 20}, /* 男宿连物理楼 */ {2, 3, 15}, {2, 4, 30}, /* 操场连物理楼、博学楼 */ {3, 4, 30}, /* 物理楼连博学楼 */ {4, 5, 10}, /* 博学楼连草地 */ {5, 6, 35}, {5, 8, 8}, /* 草地连老教、小门 */ {6, 7, 20}, {6, 8, 25}, {6, 9, 5}, /* 老教连女宿、小门、图书馆 */ {7, 8, 10} /* 女宿连小门 */ }; int n 10; /* 顶点数 */ int eCount 14; /* 边数无向图一条算一条 */这张路网的结构看一眼就明白0 号食堂是枢纽6 号老教是第二个枢纽5 号草地和小门8之间只有 8 米的短边9 号图书馆只通过 5 米的小路挂在老教上——典型的“末端建筑”。这种拓扑在后面的路径回溯里会出问题从图书馆9去食堂0路径要经过 6→5→4→3→0编号一路下降反过来从食堂去图书馆编号一路上升。原报告正是在“编号单调性”上翻了车第 5 章展开。加边的时候顺手做个自检无向图的矩阵必须关于主对角线对称且对角线全 0。写个十行的校验函数比肉眼盯 100 个数字靠谱得多/* 建图后自检对称性 对角线 */ int CheckGraph(AdjMGraph *G, int n) { int i, j; for (i 0; i n; i) { if (G-Edge[i][i] ! 0) return 0; /* 自己到自己必须是 0 */ for (j 0; j n; j) if (G-Edge[i][j] ! G-Edge[j][i]) /* 不对称说明漏写镜像边 */ return 0; } return 1; }3.3 主函数的调用链与菜单入口主函数短得可怜就三件事备数据、建图、进菜单。/* school.cpp 主流程 */ int main(void) { AdjMGraph G; Creat(G, v, e, n, eCount); /* 顶点 边 → 邻接矩阵 */ if (!CheckGraph(G, n)) { /* 自检不过就直接退出别带着脏数据跑 */ printf(图数据有误请检查边表。\n); return -1; } menu(G); /* 进入交互循环 */ return 0; }注意这里G是传地址的不是全局变量。原报告里AdjMGraph G;定义在school.cpp的全局作用域Operation.h里的函数直接引用它这样写能跑但一旦想把菜单复用给第二张图就抓瞎了。改成指针传参只多敲几个字符换来的是可测试性——后面你可以在一份代码里同时加载“校园图”和“校区班车图”菜单传哪张就查哪张。菜单本身是个switch两个选项查景点信息、查最短路径。原稿里每次操作完直接递归调用menu()回到菜单看起来清爽实际上是个隐患——递归层数等于用户操作次数连续查五十次就压五十层栈。改成while(1)循环加break才是正解第 6 章给出改法。4. 核心算法拆解Floyd 三重循环与路径还原4.1 cost、weight、path 三张表各管什么Floyd 的函数签名里有三个二维数组第一次看容易晕其实分工很清楚/* Floyd.h —— 全源最短路径 */ void Floyd(int cost[][MaxVertices], int n, int weight[][MaxVertices], int path[][MaxVertices]) { int i, j, k; /* ① 初始化weight 复制自 costpath 全部置 -1表示没有中转点 */ for (i 0; i n; i) for (j 0; j n; j) { weight[i][j] cost[i][j]; path[i][j] -1; } /* ② 三重循环以 k 为中转点尝试松弛每一条 i→j */ for (k 0; k n; k) for (i 0; i n; i) { if (weight[i][k] MaxWeight) continue; /* 剪枝i 到 k 都不通别算了 */ for (j 0; j n; j) { if (weight[i][k] weight[k][j] weight[i][j]) { weight[i][j] weight[i][k] weight[k][j]; path[i][j] k; /* 关键记下这次的中转点 */ } } } }三张表分别是cost只读的原始邻接矩阵进来是什么样出去还是什么样。这样同一张图可以被反复调用不会被算法污染。weight结果表weight[i][j]表示 i 到 j 的最短距离。初始值是直接边权循环结束后就是最终答案。path路径索引表path[i][j] k的含义是“从 i 到 j 的最优路径会经过 k”。初始全 -1表示 i 和 j 直接相连、中间没有别的点。path是这套代码的灵魂也是最容易写错的地方。很多课设版本干脆不维护path只在最后输出一个距离数字——那这题就白做了导航系统不告诉你怎么走等于没导。维护path只需要在松弛成功的那一行加一句赋值成本极低收益极大。中间那个if (weight[i][k] MaxWeight) continue;是我加的剪枝原稿没有。不加也能出正确结果因为MaxWeight x通常大于任何真实路径不会误更新但它有两个隐患一是MaxWeight是 1000 不是真无穷如果真实路径总和接近 1000加法后可能溢出回绕成小数字从而“算出一条不存在的神奇捷径”二是白白跑了大量无意义循环。加一行判断两个问题一起解决。4.2 路径还原从 path 矩阵长出一条完整路线path[i][j] k只说“中间经过 k”但 k 之前之后还有没有别的点得递归问。正确的还原逻辑是“中序”的/* 先输出 i 和 j 之间所有的中间点不含两端 */ static void PrintMid(int path[][MaxVertices], int i, int j, SeqList *V) { int k path[i][j]; if (k -1) return; /* i、j 直接相连没中间点收工 */ PrintMid(path, i, k, V); /* 递归左半段i 到 k 之间还有没有点 */ printf(%s -- , V-list[k].name); /* 左半段吐完才轮到中转点 k */ PrintMid(path, k, j, V); /* 再递归右半段k 到 j 之间还有没有点 */ } /* 对外接口把起点、中间点、终点串成一条线 */ void PrintRoute(AdjMGraph *G, int i, int j, int weight[][MaxVertices], int path[][MaxVertices]) { if (weight[i][j] MaxWeight) { printf(这两个景点之间没有可达路径。\n); return; } printf(最短距离%d\n路线%s -- , weight[i][j], G-vertices.list[i].name); PrintMid(path, i, j, G-vertices); printf(%s\n, G-vertices.list[j].name); }为什么是“左递归 → 输出 k → 右递归”因为路径的物理顺序是从 i 走到 j中间点 k 在位置上必然在 i 和 j 之间。左半段的点全部在 k 之前右半段的点全部在 k 之后所以必须先穿过左半段、再打印 k、再穿过右半段。这个顺序一旦搞反输出的就是一条反着走的路线或者干脆乱序。原报告的实现在这里确实出了问题。它用的是非递归的单向回溯/* 原稿思路有缺陷仅作对照 */ m path[j][k]; while (m ! -1) { value[count] m; if (j k) k m; /* 靠编号大小决定往回退哪一头 */ else j m; m path[j][k]; count; } /* 输出时再用 if (j k) 判断正序还是倒序打印 */这段代码的问题在于它假设“中转点编号单调”——要么一路往小走要么一路往大走。可实际路网未必如此比如 3→2→6→9 这样的路径编号先降后升一进while就选错方向m可能在两头来回弹运气好输出错序运气差直接死循环。这就是为什么原报告自己也写了“逆序输出得到的结果有点问题”。我给出的递归版本不依赖任何编号假设任何拓扑都成立代码还短一半。4.3 景点信息查询与主循环的衔接信息查询是全部功能里最简单的一次线性扫描/* Inquiry.h —— 按名称查景点 */ void Information(AdjMGraph *G, const char *name) { int i; for (i 0; i G-vertices.size; i) { if (strcmp(G-vertices.list[i].name, name) 0) { printf(名称%s\n, G-vertices.list[i].name); printf(代号%d\n, G-vertices.list[i].code); printf(简介%s\n, G-vertices.list[i].introduction); return; } } printf(没有找到叫「%s」的景点请核对名称。\n, name); }注意两点G-vertices.size不是写死的 10而是实际插入的顶点数这样以后加景点不用改查询代码return放在找到之后避免继续扫描也避免原稿那种“循环结束后判断i size”的写法——那种写法在break和return混用时容易判断错。路径查询则是先定位两个下标再调 Floyd再打印void PathQuery(AdjMGraph *G, const char *from, const char *to) { int i LocateVertex(G-vertices, from); int j LocateVertex(G-vertices, to); int weight[MaxVertices][MaxVertices]; int path[MaxVertices][MaxVertices]; if (i -1 || j -1) { printf(输入的景点名称有误请重新输入。\n); return; } if (i j) { printf(起点和终点是同一个地方。\n); return; } Floyd(G-Edge, G-vertices.size, weight, path); /* 每次查询现算 */ PrintRoute(G, i, j, weight, path); }LocateVertex就是刚才那个线性扫描函数抽出来复用。这里每次查询都重新跑一遍 Floyd对 10 个顶点来说开销可以忽略如果顶点数上去可以加一个“脏标记 缓存”只在图结构变动后才重算这就是第 6 章的改造方向之一。4.4 复杂度核算O(n³) 在这个规模下是什么体感三重循环每层 n 次时间复杂度 O(n³)这个没有争议。n 10 时最内层执行 1000 次左右加上剪枝实际更少现代机器上耗时在微秒级用户按回车之后结果几乎瞬间出现完全没有优化必要。空间复杂度要澄清一下原报告写的是 O(1)这个说法不对。函数里开了weight和path两个 n×n 的数组加上传进来的cost实际是 O(n²)n 10 时三个矩阵一共 300 个 int约 1.2 KB栈上放得下。如果顶点数涨到 500就是 500×500×3×4 字节 ≈ 3 MB还在栈上开就会爆栈得改成malloc或者全局静态数组。这是个知识点答辩时被问到“空间复杂度多少”答 O(1) 是要扣分的。对比一下 Dijkstra单源最短路径 O(n²)如果只查一对点Dijkstra 从起点跑一遍就够比 Floyd 快一个量级。但导航系统的典型用法是“客人反复问不同起点”Floyd 一次算完所有点对后续查询全是 O(1) 查表。在交互式菜单这个场景里Floyd 反而是更划算的——这就是“全源 vs 单源”的实际取舍不是单纯比复杂度数字。5. 避坑与排查五个当时卡了我半天的现象5.1 现象逆序查路线输出乱序严重时卡死现象从编号大的景点查编号小的景点打印出来的路线顺序颠三倒四某些组合下程序直接不返回光标一直闪。原因路径回溯用的是“靠j k判断该退哪一头”的单向循环隐含假设中转点编号单调。实际路网里存在先降后升的路径一违反假设m就会在两个值之间来回弹跳出循环的条件永远不成立。这不是 Floyd 的错是回溯写法的问题。解决换成 4.2 节的递归中序回溯或者用显式栈手动模拟中序。判据很简单——把path当成二叉树path[i][j] k表示 k 是根左子树是 i→k右子树是 k→j中序遍历就是路径顺序。任何拓扑都不会出问题。5.2 现象编译报stray \243 in program现象代码看着完全正常一编译就报一串stray \243指向的行号还经常是空行或者注释行。原因中文输入法没切回来敲了全角逗号、全角分号或者全角引号“”。这些字符在 UTF-8 下是多字节编译器按单字节读第一个字节0xA3就成了非法字符。课设里最容易中招的是scanf后面的全角逗号和DataType数组初始化里的中文引号。解决编辑器打开“显示不可见字符”把全角标点高亮出来或者写完之后全局搜一遍、、这几个高频字符。我的习惯是写完一个函数就编一次别攒几百行再编报错行号会和实际位置差很远。5.3 现象查不到路时打印出 1000 或者一个离谱的小数字现象查询两个本来不连通的景点结果输出“最短距离1000”或者更诡异输出一个 200 多的小数字。原因两处。第一处是输出前没判可达性直接把MaxWeight当距离打出来了。第二处更隐蔽——MaxWeight是 1000 不是真无穷weight[i][k] weight[k][j]在中转点不可达时会算成1000 某值如果某值较大两数相加进位溢出虽然 int 不会溢出但逻辑上已经错了或者后续某轮又和别的值比较时被误判为更优从而“创造”出一条不存在的路径。解决两道保险都加上。第一道在 Floyd 内层weight[i][k] MaxWeight直接continue第二道在输出前weight[i][j] MaxWeight就打印“不可达”。想更彻底的话把MaxWeight改成INT_MAX并且只在weight[i][k] ! INT_MAX weight[k][j] ! INT_MAX时才做加法。5.4 现象某个景点的简介被另一个景点的名字“吃掉”了现象查“学生第二食堂”的时候简介打印出来前半截是对的后半截变成了别的景点的名称。原因name[20]装不下。UTF-8 中文一个字 3 字节“学生第二食堂”是 6 个字 18 字节加上结尾\0刚好 19勉强塞进 20。但如果手滑多打一个字或者用 GBK 编码时字数按 2 字节算导致两个文件编码不一致name就会溢出到相邻的code或者introduction上——结构体成员在内存里是紧挨着的溢出不报错直接静默改数据。解决name加到 32 或 64 字节别抠这十几个字节scanf用%31s限定长度而不是%sstrcpy换成strncpy并且手动补\0。这个坑的恶劣之处在于它不崩溃、不报错只是数据悄悄变脏等发现的时候已经查了半天。5.5 现象连着查了二三十次之后程序突然退出现象功能都正常就是查得多了会莫名其妙结束没有错误提示。原因菜单是递归的。Information1()和Path1()干完活之后直接调menu()回到菜单每次操作压一层栈。栈空间默认几 MB每层帧不大但查几十上百次之后终究会耗尽。课设演示时一般查不了这么多次所以这个 bug 常常被藏到答辩现场才现形。解决菜单改循环。把menu()的递归调用改成return主函数里套while (1) { menu(G); }退出条件靠菜单里的“0. 退出”分支break。层次从“递归深度 操作次数”变成“恒定一层”问题消失。6. 二次开发把课设代码改成能扩展的导航内核这份代码跑通之后真正有价值的部分才开始怎么把它从“交作业”变成“能改的东西”。我按投入产出比列几个方向从易到难。第一刀砍向硬编码。顶点的DataType v[]和边的RowColWeight e[]现在写死在school.cpp里加一个景点就得重新编译。最省事的改法是抽一个文本文件出来一行一个景点、一行一条边/* 从 campus.txt 读图格式V 名称 代号 简介 / E 起点 终点 距离 */ int LoadGraph(AdjMGraph *G, const char *path) { FILE *fp fopen(path, r); char tag[4], name[64], intro[128]; int code, r, c, w, n 0, eCount 0; DataType vs[MaxVertices]; RowColWeight es[MaxVertices * MaxVertices]; if (!fp) return 0; while (fscanf(fp, %3s, tag) 1) { if (tag[0] V) { fscanf(fp, %63s %d %127s, name, code, intro); strcpy(vs[n].name, name); vs[n].code code; strcpy(vs[n].introduction, intro); n; } else if (tag[0] E) { fscanf(fp, %d %d %d, r, c, w); es[eCount].row r; es[eCount].col c; es[eCount].weight w; eCount; } } fclose(fp); Creat(G, vs, es, n, eCount); return CheckGraph(G, n); /* 读完立刻自检脏数据当场拦下 */ }这段代码的关键不在读文件本身而在读完立刻调CheckGraph。外置数据意味着人会改错改错就得有拦截。没有自检的外置配置比硬编码更危险——硬编码改错了编译不过配置文件改错了程序照跑只是结果是错的。第二个方向是算法层。现在每次查询都重跑 Floyd10 个顶点无所谓但如果要做成“多校区 班车线路”的规模就该加缓存维护一个dirty标志图结构变动时置 1查询时若为 1 才重算。再进一步如果只需要单点查询就换 Dijkstra/* 单源 Dijkstra只查到目标点为止适合点多的图 */ void Dijkstra(int cost[][MaxVertices], int n, int src, int dist[], int prev[]) { int visited[MaxVertices] {0}; int i, k, min; for (i 0; i n; i) { dist[i] cost[src][i]; prev[i] -1; } dist[src] 0; visited[src] 1; for (k 1; k n; k) { min MaxWeight; i -1; for (int t 0; t n; t) /* 找当前最近的未访问点 */ if (!visited[t] dist[t] min) { min dist[t]; i t; } if (i -1) break; /* 剩下的都不可达 */ visited[i] 1; for (int t 0; t n; t) /* 用 i 去松弛邻居 */ if (!visited[t] dist[i] cost[i][t] dist[t]) { dist[t] dist[i] cost[i][t]; prev[t] i; /* 记前驱用于还原路径 */ } } }prev数组和 Floyd 的path作用一样只是还原方式不同——Dijkstra 是从终点一路prev往前倒退到起点得到的序列反过来打印。两种还原方式都建议封装成同一个PrintRoute接口这样换算法不用动上层调用业务层感觉不到算法变了。第三个方向是把菜单那层递归拆成事件循环。改成while (1)之后顺手把“0. 退出”加上并且把输入用fgets读进来再解析避免scanf(%d)遇到非数字输入时陷入死循环。这类输入健壮性问题在演示时最容易出洋相评审老师随手敲个字母程序就开始疯狂刷菜单。验证改造成果的办法我一直用同一套手算一条路径当基准。比如从食堂0到图书馆9手工跑一遍 Floyd得到 0→3→4→5→6→9距离 353010355 115把 115 和路线写进测试用例再挑两组“不连通”的组合确认输出是“不可达”而不是 1000最后跑一遍CheckGraph确认矩阵仍然对称。三个用例全过才认为改动没破坏原有逻辑。血泪经验是这类课设代码的错八成不在算法本身而在数据入口和输出边界——数组越界、全角标点、MaxWeight误用、递归爆栈全是同一类毛病。所以从那以后我每次动完数据结构相关的代码都强制走一遍“自检函数 手算基准用例 边界输入乱敲”三条不省这一步。希望帮到你。本文还有配套的精品资源点击获取