简介围绕《数据结构》课程设计中的校园导航系统这份文档面向计算机专业学生及正在完成图论类课程设计的学习者聚焦校园地图建模、景点信息查询与任意两点间最短路径求解等典型问题。压缩包仅含1个doc文件约187KB内容为完整的课程设计报告而非零散代码片段。已有67人学习适合作为同类题目的参考范例。文档从任务书、详细设计到调试测试逐层展开给出邻接矩阵存储、顶点与边结构体设计、Floyd算法求最短路径及正序输出路径的处理思路并附源程序清单与执行结果、时间复杂度分析、C程序设计总结和参考文献。读者可据此梳理从图结构选型、算法实现到测试排错与报告撰写的完整流程对照完善自己的课程设计文档与程序实现。1. 从东区到东湖能走通、反着查就乱套这类 Bug 最磨人做数据结构课程设计那阵子校园导航系统的 Floyd 最短路径已经跑通了输入“东区”和“东湖”屏幕上端端正正打出东区 —— 主楼 —— 西体育馆 —— 隧道 —— 北大门 —— 东湖距离也对得上手算结果。可把起点终点一换从东湖查回东区中间那几个景点就开始乱序有时候顺序整个反过来有时候还漏掉一个中转点。程序不崩、不报错、编译零警告就是结果不对这种“算法没错、输出错乱”的故障最难查因为它不给你任何提示只能靠肉眼比对。这篇笔记就是从这个坑出发把校园导航系统里最短路径类的几类典型故障拆开路径还原为什么错、邻接矩阵怎么初始化、景点名为什么查不到、菜单为什么越点越慢。正在写图算法课程设计、或者线上路径规划功能突然返回异常路线的人都能对号入座。2. 最短路径顺序错乱path 矩阵存的是中转点不是上一步2.1 先分清两个矩阵一个存距离一个存分叉点Floyd 跑完之后会得到两张表很多人只盯着第一张。weight[i][j]存的是 i 到 j 的最短距离这个是大家都会看的path[i][j]存的是“为了让 i 到 j 更短最后一次经过的中转点 k 是谁”这张表才是路径还原的全部依据。它的语义不是“i 的下一步是 k”而是“i 到 j 这条路在 k 这里被劈成了 i 到 k 和 k 到 j 两段”。理解错这一层后面所有打印逻辑都会歪。/* Floyd 核心weight 存距离path 存分叉点-1 表示直达无中转 */ void Floyd(int cost[][MaxVertices], int n, int weight[][MaxVertices], int path[][MaxVertices]) { int i, j, k; for (i 0; i n; i) { for (j 0; j n; j) { weight[i][j] cost[i][j]; /* 拷贝邻接矩阵不改动原图 */ path[i][j] -1; /* 初始认为任意两点都直达 */ } } for (k 0; k n; k) { /* k 必须最外层每轮允许经过第 k 个点中转 */ for (i 0; i n; i) { 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; /* 记录本次生效的中转点 */ } } } } }三个循环的顺序不能换。k 放最外层含义是“第 k 轮循环结束时任意两点之间如果走得更短只允许借用编号 0 到 k 的顶点做中转”。这是 Floyd 动态规划的正确性来源。i、j 的顺序无所谓但 k 一旦挪到内层weight[i][k]和weight[k][j]可能在这一轮里刚被改过结果就变成了另一套算法的近似值。path[i][j] k这一行每次覆盖的是“当前最优解对应的那个分叉点”。因为 k 从小到大枚举后面的 k 会覆盖前面的 k最终留下来的就是最后生效的那次分叉。这一点很关键递归还原路径时每次都从path[i][j]取分叉点取到的必然是能把路径正确切开的那一个。2.2 边找路径边改起点终点是错乱的直接来源原始代码的还原逻辑大致长这样从path[j][k]取出中转点 m把 m 记进value[]数组然后根据j k判断往哪半边继续找循环直到 m 为 -1最后再根据一次j k决定value[]是从前往后打还是从后往前打。/* 有问题的写法靠顶点下标大小决定前进方向 */ m path[j][k]; while (m ! -1) { value[count] m; if (j k) k m; /* 认为编号大的在后半段 */ else j m; /* 认为编号小的在前半段 */ m path[j][k]; count; }这里藏着三个问题任何一个都足以让某组数据的结果出错。第一个问题是j k这个判断本身。它拿顶点编号大小去推断路径走向隐含假设是“编号大的景点一定排在路径后面”。这组测试数据里恰好成立东区编号小、东湖编号大沿途景点编号基本递增。可一旦换一条路径比如从编号 8 的小门走到编号 3 的物理楼编号是递减的判断分支立刻走反。第二个问题是 j 和 k 在循环里被不断覆写。等循环结束j、k 已经不是最初的起点和终点而是路径上的某个中间点。后面那句if (j k)拿被改过的值当依据等于用一个已经失效的变量去决定输出方向结果自然不稳定。第三个问题是value[]的记录顺序和输出顺序。数组是按“从外向内”的顺序存的打印时要么正着来要么倒着来靠一个全局的 if 一次性翻转。这种写法只有在路径的中间点恰好单调排列时才正确本质上是拿测试用例拟合出来的补丁不是解法。提示凡是“正向对、反向错”的路径问题先怀疑代码里有没有依赖顶点编号大小的假设这一类 bug 占了图算法输出异常的多数。2.3 用递归还原路径顺序天然正确正确的还原方式是把“打印 i 到 j 的路径”定义成一个递归问题先打印 i 到 k 的路径再打印 k 本身最后把 j 交给调用方补上。因为递归是先深入到最底层再逐层返回打印顺序天然就是路径的正向顺序跟编号大小、跟起点终点谁大谁小完全无关。/* 递归打印 i 到 j 之间的中转点不含 j 本身 */ void PrintPath(int i, int j, int path[][MaxVertices], AdjMGraph *G) { int k path[i][j]; if (k -1) { /* 直达递归到底只打起点 */ printf(%s, G-vertices.list[i].name); return; } PrintPath(i, k, path, G); /* 先走前半段 i - k */ printf( —— %s, G-vertices.list[k].name); /* 再打分叉点 k */ } /* 对外接口判不可达 打距离 打完整路径 */ void ShowPath(int i, int j, int weight[][MaxVertices], int path[][MaxVertices], AdjMGraph *G) { if (weight[i][j] MaxWeight) { /* 距离仍是无穷大说明不连通 */ printf(两地之间没有可通行的道路\n); return; } printf(最短距离%d 米\n路径, weight[i][j]); PrintPath(i, j, path, G); printf( —— %s\n, G-vertices.list[j].name); /* 终点在这里补 */ }参数含义要说清楚i、j是起点和终点在顶点表里的下标不是景点名称path是 Floyd 填好的分叉点矩阵G用来按下标反查景点名称。递归深度最多等于顶点数 n10 个景点最多 10 层完全不用担心栈。真正需要注意的是i j的情况此时path[i][i]是 -1函数会打印一次起点调用方再补一次终点屏幕上就会出现“图书馆 —— 图书馆”所以在调用前要先判掉起点等于终点。这个分支不算错只是用户体验上不好看加一句if (i j)单独提示即可。这段递归和原来那套 while 循环的差别不只是“写法更短”。递归把“路径 起点 前半段 分叉点 后半段”这个结构直接表达出来了而 while 循环版本把结构揉碎成了数组下标运算一旦数据结构被破坏错误就不可见。改完之后正向、反向、绕路、不可达四种情况都能一次跑对不再需要为“逆序输出”单独打补丁。3. 距离算成 1000、路径直接断开邻接矩阵的三个初始化陷阱3.1 无边不能填 0否则等于所有景点贴在一起邻接矩阵的第一条铁律自己到自己填 0没有路的两个景点填一个足够大的数有路的填权值。填 0 是最常见的翻车点。如果建图时忘记把整片矩阵先刷成“不通”Edge数组里残留的是未初始化内存的随机值某些格子可能正好是一个很小的数Floyd 就会认为两个本来不通的景点之间有一条 3 米的秘密通道然后一本正经地给你规划出一条现实中不存在的路线。/* 建图先全部置为不可达再逐条写入真实道路 */ void Creat(AdjMGraph *G, DataType v[], RowColWeight rcw[], int n, int e) { int i, j; ListInitiate(G-vertices); /* 顶点表清空 */ for (i 0; i n; i) ListInsert(G-vertices, i, v[i]); /* 10 个景点依次入表 */ G-numOfEdge e; for (i 0; i n; i) { for (j 0; j n; j) { G-Edge[i][j] (i j) ? 0 : MaxWeight; /* 关键先整体刷成不通 */ } } for (i 0; i e; i) { G-Edge[rcw[i].row][rcw[i].col] rcw[i].weight; G-Edge[rcw[i].col][rcw[i].row] rcw[i].weight; /* 无向图成对写 */ } }MaxWeight取 1000 是有讲究的。这组数据里最大单边权是 3510 个景点就算绕最远的路总长也不会超过 3501000 留了足够余量。如果哪天把权值单位从“抽象距离”改成“米”单边动辄三四百米1000 立刻就不够用了Floyd 会把一条真实的长路径误判成“比无穷大还长”从而拒绝更新最后查询结果仍然停在 1000。改数据的同时必须重新评估这个常量它不是一个随手写的魔法数字。3.2 无向图的边要写两遍漏一半就变成单行道校园里的路都是双向的但邻接矩阵不会自动帮你对称。边表里写一条{0, 1, 20}只代表“0 号景点能到 1 号景点”反方向仍然是MaxWeight。表现出的现象特别有迷惑性从学生第二食堂查男生宿舍路径正常从男生宿舍查学生第二食堂直接提示不连通。很多人第一反应是 Floyd 写错了实际上是建图阶段就少了一半信息。原始代码的边表里每条边都成对出现{0,1,20}和{1,0,20}各写一条这是对的。但手工维护这种对称性非常脆弱后续增删景点时漏写一条故障就会在某个特定方向上冒出来。我一般会在建图函数里只写一次让代码自动补反向边就像上面那段G-Edge[rcw[i].col][rcw[i].row] rcw[i].weight;。这样边表里每条路只写一遍e 28也就变成了实际道路条数 14 的两倍数量关系更清楚。如果用自动补反向边的方式边表长度要跟着改numOfEdge的语义也要统一。这一点在课程设计的报告里容易被追问建议在注释里写清楚“rcw 中每条记录代表一条双向道路”避免自己和读者理解不一致。注意判断图是否对称最省事的办法是遍历矩阵比较Edge[i][j]和Edge[j][i]一旦发现不等说明建图阶段就有问题不用往下查 Floyd。3.3 无穷大用 INT_MAX 会溢出判定条件也得跟着改有人觉得 1000 不够“无穷”换成INT_MAX更严谨结果算出来的距离是负数。原因很直接weight[i][k] weight[k][j]在两个都是INT_MAX的时候会溢出变成一个很大的负数而负数永远小于当前距离于是 Floyd 认为找到了一条负距离的捷径把weight和path一起写坏。正确的做法有两条路。一条是继续用有限的MaxWeight前提是保证它大于图中任意一条可能路径的长度之和10 个景点、最大边权 35 的场景下 1000 足够安全这也是原始代码的做法。另一条是坚持用极大值但在松弛前加判断/* 用极大值时必须先判两端可达再相加 */ if (weight[i][k] ! MaxWeight weight[k][j] ! MaxWeight weight[i][k] weight[k][j] weight[i][j]) { weight[i][j] weight[i][k] weight[k][j]; path[i][j] k; }两个条件缺一不可。少了前半段溢出照样发生少了后半段本来就直达的短路径会被后面一轮更长的路覆盖。这段判断只在用极大值表示不通时才需要用有限MaxWeight时可以省掉但代价是要维护好那个常量的取值范围。我倾向于保留判断因为它把“不通”这件事显式表达出来了读代码的人一眼能看出意图不用去反推 1000 这个数字是怎么来的。4. 输入景点名提示“不在所提供范围内”字符串匹配的四个失手点4.1 scanf(%s) 遇空格就停带空格的景点名永远查不到scanf(%s, name)读到第一个空白字符就收手剩下的内容留在输入缓冲区里。景点名里只要带空格比如“东区 食堂”实际存进name的只有“东区”后面用strcmp去跟完整名称比对永远不相等于是走进“找不到该景点”的分支。更麻烦的是残留的“食堂”会被下一次输入读取到造成连锁误判用户看到的现象是“第一次查不到第二次查了个完全不相干的地方”。/* 读一整行去掉尾部换行再比对 */ char buf[64]; if (fgets(buf, sizeof(buf), stdin) ! NULL) { buf[strcspn(buf, \n)] \0; /* 把换行换成结束符 */ } Information(G, buf);fgets会把换行符一起读进来必须用strcspn或strlen手动裁掉否则缓冲区里存的是“图书馆\n”跟“图书馆”比对还是不等。sizeof(buf)传的是整个数组大小fgets最多读sizeof(buf) - 1个字符再加结束符不会越界这是它比scanf安全的地方。缓冲区大小 64 字节在 GBK 编码下够放 31 个汉字在 UTF-8 下也够放 21 个对景点名来说绰绰有余。4.2 缓冲区残留和编码不一致strcmp 永远不等于 0比空格更隐蔽的是残留数据。前面用scanf读过菜单选项用户敲的那个回车还留在缓冲区里紧接着fgets一读直接读到空行传给查询函数的是一串空白。表现就是“我明明输入了景点名程序说没找到”。解决办法是在切换输入方式的地方清一次缓冲区或者全程统一用fgets读、再用sscanf或atoi解析数字不要混着来。编码问题也值得提一句。同一个景点名源文件用什么编码保存、终端用什么编码显示两边不一致时strcmp比的是字节而不是字看起来一模一样的两个字符串可能相差一个字节。常见现象是景点名在菜单里显示正常复制粘贴进去却查不到。这类问题用肉眼看不出来把两个字符串的长度和每个字节打出来一比对就清楚了。/* 排查用把输入串和表内串的字节打出来对比 */ printf(输入长度%zu\n, strlen(name)); for (i 0; name[i] ! \0; i) printf(%02X , (unsigned char)name[i]); printf(\n);还有一个容易被忽略的点DataType里char name[20]只有 20 字节。GBK 下一个汉字占 2 字节最多放 9 个汉字UTF-8 下一个汉字占 3 字节最多放 6 个。景点名一旦超过这个长度strcpy或scanf会直接写穿数组破坏相邻的code和introduction字段症状是“查询能查到但代号变成了乱码”。把数组放大到 64 字节成本几乎为零。4.3 扫描循环的边界决定提示走哪条分支查询函数的骨架是“从头扫到尾找到就输出扫完还没找到就提示”。这个逻辑本身没问题问题出在“怎么判断没找到”。原始写法是在循环外拿循环变量i跟size比较如果循环内部break了i停在命中位置i size不成立走输出分支如果循环自然结束i size成立走提示分支。这套逻辑在size 0时正确但如果顶点表为空i根本没被赋值比较的是一个未初始化的变量。/* 用一个显式的命中标记比复用循环变量可靠 */ int index -1; for (i 0; i G.vertices.size; i) { if (strcmp(G.vertices.list[i].name, name) 0) { index i; break; } } if (index -1) { printf(未找到景点[%s]请检查名称是否与菜单一致\n, name); return; } printf(名称%s\n代号%d\n简介%s\n, G.vertices.list[index].name, G.vertices.list[index].code, G.vertices.list[index].introduction);index初始化为 -1命中就赋值扫完还是 -1 就是没找到。这样判断依据和循环变量彻底解耦顶点表为空、循环提前退出、命中在最后一位三种情况都不会误判。提示信息里把用户输入的原始字符串打出来也非常有用用户自己就能发现是不是多打了一个空格或者打错了字。5. 点几次菜单就卡死、输错一个字符就刷屏交互与内存的常见问题5.1 每次操作完递归调 menu()点几十次就栈溢出原始代码里查询函数执行完最后一行是menu();菜单函数又在选完分支后调用查询函数。表面上看是“操作完自动回到菜单”实际上每一次操作都在调用栈上压了一层新的menu旧的那层永远不返回。操作十次就叠十层操作一百次就叠一百层叠到一定深度程序直接崩溃或者在某些环境里表现为“点了几下突然没反应”。/* 改成循环 唯一出口栈深度恒定为 1 */ void menu(void) { int choice; while (1) { printf(\n1. 景点信息查询 2. 最短路径查询 0. 退出\n请选择); if (scanf(%d, choice) ! 1) { /* 非数字输入 */ while (getchar() ! \n) ; /* 清掉这一行剩余字符 */ printf(请输入数字 0/1/2\n); continue; } switch (choice) { case 1: Information1(); break; case 2: Path1(); break; case 0: return; /* 唯一出口 */ default: printf(没有这个选项请重新选择\n); } } }while (1)配一个return退出所有分支执行完自然回到循环开头不产生任何新的栈帧。查询函数里也不要再调menu()只负责把活干完返回。这样改完之后点一百次和点一次的内存占用完全一样“用久了变卡”的现象直接消失。5.2 scanf 不检查返回值输错一个字母就无限刷屏scanf(%d, choice)遇到字母时返回 0字母本身留在缓冲区里没被消费。如果代码不检查返回值、直接进 switchchoice保持上一次的旧值用户会看到同一条查询结果反复刷屏如果外层是循环字母永远读不掉就变成死循环。上面那段代码里if (scanf(...) ! 1)和while (getchar() ! \n)配成一对前者负责发现异常后者负责把这一行垃圾数据清干净缺一不可。只清一次getchar()是不够的用户可能敲了一串字符必须清到换行为止。同样的检查要加在所有读数字的地方。课程设计里还有个典型场景查询最短路径时连续读两个景点名如果中途输入异常后一个读到的可能是上一次的残留错误被放大成“路径算出 0 米”。宁可多写几行校验也别指望用户输入永远规范。5.3 剩下的三个坑全角标点、数组越界、顶点数对不上第一个坑是全角标点。代码里混进中文引号、全角分号、全角括号编译报错的位置往往指向下一行让人以为逻辑写错了实际是上一行藏了个看不见的全角字符。这类错误在从文档里复制代码时特别高发血泪经验是编译报错提示“缺分号”但你明明看到有分号就把那一行删掉重敲一遍。第二个坑是路径记录数组越界。用value[MaxVertices]存中转点count一路自增没有边界检查路径上中转点一多就写穿数组。10 个顶点的场景下最多 8 个中转点看起来安全但如果哪天把景点扩到 20 个count就可能超过MaxVertices。要么把数组开得足够大要么在自增前加if (count MaxVertices)。第三个坑是顶点数、边数和实际数组长度对不上。n 10、e 28是手写的常量景点表里加了第 11 个景点却忘了改nFloyd 就只算前 10 个新景点在查询时永远“不连通”。这类问题不会报错只会表现为“某个景点怎么查都不对”。比较稳妥的写法是用sizeof(a) / sizeof(a[0])自动算顶点数边数同理让人工维护的常量少一个是一个。6. 快速定位最短路径异常先验矩阵再看分叉点最后手工对一条图算法的故障排查有个好处中间结果全是矩阵随时可以打出来看不用像并发问题那样靠猜。我现在的习惯是三步走绝大多数路径异常在第二步就能定位。第一步验邻接矩阵。把建图之后的Edge矩阵完整打印出来重点看三件事对角线是不是全 0Edge[i][j]和Edge[j][i]是否相等不该通的地方是不是真的等于MaxWeight。这一步能挡掉初始化漏刷、无向边漏写、权值填错这三类问题它们占了建图阶段故障的绝大多数。矩阵不大10 个景点也就 100 个数字扫一眼就能看出有没有异常值。第二步验path矩阵。路径顺序错乱九成出在这张表的使用方式上而不是表本身。打印path之后随便挑一对景点看path[i][j]是不是落在一条合理的中转点上。如果表本身正常而输出还是乱问题就在还原代码直接换成第 2 章那段递归函数即可。第三步手工对一条最短路径。挑三类用例一条直达边验证距离是否等于权值、路径是否只有起终点一条两跳路径验证中转点是否被正确打印一对不连通的景点验证提示分支是否走到。三类都过基本可以认为功能正确。如果时间允许再补一条“反向查询”起点终点对调距离应当完全相等路径应当完全相反。这个对称性检查不需要任何额外数据却能立刻暴露方向相关的 bug。/* 自检函数建图后调用一次把可疑点直接打出来 */ void CheckGraph(AdjMGraph *G) { int i, j, err 0; for (i 0; i G-vertices.size; i) { if (G-Edge[i][i] ! 0) { /* 对角线必须是 0 */ printf(顶点 %d 自环权值异常%d\n, i, G-Edge[i][i]); err; } for (j i 1; j G-vertices.size; j) { if (G-Edge[i][j] ! G-Edge[j][i]) { /* 无向图必须对称 */ printf(边[%d][%d]%d 与 边[%d][%d]%d 不对称\n, i, j, G-Edge[i][j], j, i, G-Edge[j][i]); err; } } } printf(自检结束可疑项 %d 个\n, err); }这个函数只做静态检查不涉及 Floyd跑一次就能把建图问题筛干净。从那以后我每次写完建图代码都强制先跑一遍自检再去看最短路径结果——毕竟路径算错的时候你永远不知道是算法写歪了还是数据本身就脏先排除数据问题能省掉一大半兜圈子的时间。希望这些排查顺序能帮你少熬两个晚上。本文还有配套的精品资源点击获取