简介面向计算机相关专业学生与数据结构课程设计指导者的校园导航系统课程设计文档围绕无向图建模、景点信息查询与任意两点最短路径求解展开适合作为课程设计选题、实验报告撰写与答辩准备参考。压缩包内仅含1个doc文件大小约187KB集中呈现任务书、详细设计、调试与测试、时间复杂度分析、源程序清单及执行结果并附C程序设计总结、致谢与参考文献。文档以邻接矩阵存储图结构结合顺序表保存景点名称、代号和简介采用Floyd算法实现最短路径查询同时记录调试问题、测试结果分析与改进思路。已有67人学习或下载可帮助读者梳理图结构表示、存储结构选择、算法实现、测试用例设计和报告规范快速形成较完整的课程设计框架。1. 校园导航系统课设包10 个景点、28 条边一份能直接跑通的《数据结构》课程设计答辩前一晚最经典的翻车场景是这样的把校园平面图抽象成 10 个景点、28 条路输入「学生第二食堂」到「图书馆」能正常打印一串节点反过来输入就变成颠倒的路径甚至卡在某个循环里出不来。这份 doc 就是围绕这个问题攒出来的完整交付物——任务书、存储结构说明、算法设计思想、调试记录、时间复杂度分析、源程序清单全在里面源码拆成 school.cpp、AdjMGraph.h、AdjMGraphCreat.h、SeqList.h、Floyd.h、Operation.h、Inquiry.h 七个文件主体是「顺序表存景点 邻接矩阵存道路 Floyd 求任意两点最短路」。数据结构课程设计里校园导航系统算是把图这一章吃透的标准题型顶点带属性、边带权、要查询、要问路。它适合三类人——正在做图论课设、需要一份能编译能演示的参考实现想把邻接矩阵和 Floyd 从纸面公式落到可运行代码以及已经写完但路径打印一直不对、想找到问题根源的人。下面按「结构体怎么定 → 图怎么建 → 最短路怎么算怎么打印 → 坑在哪 → 怎么验收」的顺序走一遍。2. 顶点用顺序表、边用邻接矩阵10 个景点的图为什么不该上邻接表2.1 三个结构体定下整份代码的数据契约这套实现里所有后续逻辑都建立在四个结构体上先把它们定死后面的建图、查询、最短路才有共同语言。景点用定长字符数组而不是char *是为了避开动态内存和深拷贝——课设规模下这点内存不值得省但省下的是成片的malloc/free调试时间。code字段和数组下标刻意解耦下标是程序内部寻址用的代号是对外展示用的两者分开之后你调整景点顺序不必改菜单提示也不会因为删掉一个景点就让所有边的 row/col 全部错位。#define MaxSize 20 /* 顺序表容量 */ #define MaxVertices 20 /* 顶点数上限 */ #define MaxWeight 1000 /* 不可达的无穷大边权 */ /* 景点既当顶点数据也当查询结果 */ typedef struct { char name[20]; /* 景点名注意编码下的字节数 */ int code; /* 对外代号跟数组下标解耦 */ char introduction[50]; /* 一句话简介 */ } DataType; /* 顺序表存所有顶点 */ typedef struct { DataType list[MaxSize]; int size; } SeqList; /* 图邻接矩阵 顶点表 边计数 */ typedef struct { SeqList vertices; /* 顶点集合 */ int Edge[MaxVertices][MaxVertices]; /* 边权矩阵 */ int numOfEdge; /* 边数无向图按双倍记 */ } AdjMGraph; /* 建图用的边集数组一条记录就是一条有向边 */ typedef struct { int row; int col; int weight; } RowColWeight;这里有个很多人踩过、但报告里从来不写的细节name[20]在 GBK 编码下一个汉字占 2 字节最多放 9 个汉字加结束符换到 UTF-8 下一个汉字 3 字节20 字节只够 6 个汉字加\0。像「学生第二食堂」这种 7 个汉字的景点名在 UTF-8 源文件里用strcpy拷进去就会写穿 2 个字节正好踩在相邻元素的code字段上——现象是查询时景点代号莫名其妙变成一个大数。稳妥做法是把name提到char name[32]或者干脆统一用 GBK 存源文件别在编码上赌运气。Edge是 20×20 的 int 矩阵算下来 1600 字节对现代机器毫无压力但它的意义不在省内存而在于把「两点之间有没有路、路多长」变成一次O(1)的下标访问。Floyd 的三重循环整个建立在这个假设上换任何别的存储结构算法都得重写。2.2 稠密还是稀疏28 条边对 45 条上限这道算术题选邻接矩阵还是邻接表课设报告里最常见的错误答案是「邻接表省空间」然后抄一段链表代码进去最后卡在指针上出不来。正确的判断方式是先算密度无向图 n 个顶点最多n(n-1)/2条边这里是 10 个景点、上限 45 条实际写了 28 条密度 0.62明显偏稠密。邻接表在这个规模下能省下的空间是「每个节点 8 字节 × 56 个节点 ≈ 448 字节」而代价是要么手写链表节点、要么用数组模拟链表调试成本翻几倍。更关键的约束是任务本身题目要求「任意两个景点之间的最短路径」也就是全源最短路。Floyd 的输入天然就是一张权值矩阵你就算用邻接表存图最后也得先O(n²)展开成矩阵再喂进去属于绕远路。所以这里的选型逻辑不是「矩阵比链表高级」而是「稠密图 全源查询 小规模」三个条件同时成立矩阵是唯一不别扭的选择。真到了几百个顶点、边只有几百条的稀疏路网邻接表配堆优化 Dijkstra 才是正解这一点在最后一章还会提到。顶点之所以单独用顺序表而不是直接塞进AdjMGraph是为了让「查景点信息」和「查最短路」共用同一份顶点数据查询简介时扫的是vertices.list打印路径时按下标回读的也是vertices.list不会出现两份数据对不上的情况。2.3 七个头文件的分层把图操作和业务菜单切开源码拆成七个文件不是摆设它对应一条清晰的责任链SeqList.h 管线性表AdjMGraph.h 管图的结构体和基础操作AdjMGraphCreat.h 负责建图Floyd.h 只放算法Inquiry.h 放两个查询函数Operation.h 放菜单和交互封装school.cpp 是唯一带main的入口。这样拆的好处是调试时能定位到层——路径算错去 Floyd.h查不到景点去 Inquiry.h界面乱跳去 Operation.h。但原始代码里有一处写法在单文件编译下能过一旦拆成多文件就链接报错school.cpp 里先写AdjMGraph G;定义全局变量然后才#include Operation.h而 Operation.h 里的函数直接用了G。这等于让头文件依赖「包含顺序」任何调整 include 顺序的改动都会炸。常规做法是在 AdjMGraph.h 里写extern AdjMGraph G;声明在 school.cpp 里定义头文件只管声明不管定义。/* AdjMGraph.h 里只声明不定义 */ extern AdjMGraph G; /* school.cpp 里唯一定义处 */ AdjMGraph G;顺带说一句函数原型Inquiry.h 里的Information和Path都按值接收AdjMGraph G而AdjMGraph内部含一个 1600 字节的矩阵每次调用都要整体压栈拷贝一次。10 个顶点的规模下感觉不到但这是坏习惯——改成const AdjMGraph *G传指针既省拷贝又能让编译器帮你挡住「函数里偷偷改图」的误操作。课设代码里这类「能跑但不对味」的地方答辩时被追问的概率反而不低。3. 把 28 条路写进矩阵建图函数里必须做的三件事3.1 边集数组怎么填14 对无向边一条都不能少建图这一步最容易被低估。原始代码的做法是准备一个RowColWeight rcw[]数组把每条边写成{起点下标, 终点下标, 权值}一条记录再配一个int n10, e28;告诉建图函数「10 个顶点、28 条边记录」。之所以是 28 而不是 14是因为无向图的每条路要在矩阵里写两个位置Edge[i][j]和Edge[j][i]。原始数据里确实成对出现了比如{0,1,20}和{1,0,20}就是同一条路的两个方向。/* 前 3 个景点之间的边注意每条路都成对出现 */ RowColWeight rcw[] { {0, 1, 20}, {0, 2, 30}, {0, 3, 35}, {1, 0, 20}, {1, 3, 20}, {2, 0, 30}, {2, 3, 15}, {2, 4, 30}, /* ... 其余 20 条同理共 28 条记录 */ };这段数组的隐式契约是row/col必须严格对应DataType a[]里景点的下标顺序。你如果在中途插了一个新景点把「图书馆」从下标 9 挪到下标 5那么所有row/col为 9 的记录全部失效程序不会报错只会算出一条通往错误景点的路径——这是这套代码里最隐蔽的一类 bug改完顶点表必须回头核对一遍边集。3.2 初始化先全填 MaxWeight再把对角线置 0建图函数要按「顶点表 → 矩阵初始化 → 逐条写边」三步走顺序不能换。初始化必须先把整个矩阵填成MaxWeight表示不可达再把Edge[i][i]置 0 表示自己到自己距离为零。这两步一旦漏掉矩阵里会残留栈上的随机值Floyd 跑出来的结果就是玄学——有时候对有时候冒出一条根本不存在的近路。void Creat(AdjMGraph *G, DataType v[], RowColWeight rcw[], int n, int e) { int i, j, k; /* 1. 顶点表整体拷贝size 单独记 */ for (i 0; i n; i) G-vertices.list[i] v[i]; G-vertices.size n; /* 2. 矩阵清零对角线 0其余视为不可达 */ for (i 0; i n; i) for (j 0; j n; j) G-Edge[i][j] (i j) ? 0 : MaxWeight; /* 3. 逐条写入边权计数 */ G-numOfEdge 0; for (k 0; k e; k) { i rcw[k].row; j rcw[k].col; G-Edge[i][j] rcw[k].weight; G-numOfEdge; } }参数说明v[]是顶点数组rcw[]是边集n是顶点数e是边记录条数无向图要传双倍。注意这个版本没有在函数内部做对称赋值因为它依赖调用方在边集里成对写全。如果你的习惯是「一条路只写一次」那就必须在循环里补一行G-Edge[j][i] G-Edge[i][j];两种策略二选一混着用一定会出错——一半边成对、一半边单写结果就是某些方向可达、反方向不可达Floyd 会诚实地告诉你「从图书馆到操场没有路」。numOfEdge这个字段在很多实现里被注释成「边数」但无向图里它实际记的是有向边记录数。如果后面有「判断图是否连通」之类的需求得先除以 2这一点在报告里写清楚属于加分项。3.3 自检建完图先打印矩阵和每个顶点的度建图之后别急着跑最短路先花十行代码打个自检能省掉后面几小时的排查。检查两件事矩阵是否对称每个顶点的度是否和预期一致。对称性直接反映无向图的正确性度则能快速发现漏写的边——比如你预期「老教」连了 4 条路打印出来只有 3 条那就回去数边集里跟下标 6 有关的记录。void Check(AdjMGraph *G) { int i, j, deg; for (i 0; i G-vertices.size; i) { deg 0; for (j 0; j G-vertices.size; j) { if (i ! j G-Edge[i][j] MaxWeight) { deg; /* 对称性检查i-j 有边j-i 也必须有且权值相同 */ if (G-Edge[j][i] ! G-Edge[i][j]) printf(非对称边: %d - %d\n, i, j); } } printf(%-12s 度%d\n, G-vertices.list[i].name, deg); } printf(边记录数%d实际无向边数%d\n, G-numOfEdge, G-numOfEdge / 2); }这套自检还能顺手验证MaxWeight的取值是否合理。原始代码取 1000如果某条真实路径的总长超过 1000就会被误判为不可达反过来两个不连通点之间做加法得到 2000不会小于 1000所以不会凭空造出一条路。也就是说 1000 这个值只对「长路径」有风险对「假连通」是安全的。校园里任意两点走下来一般不超过几百米量级1000 够用但报告里最好把这条假设点出来。4. Floyd 三重循环与 path 回溯最短路径算得对还要打得对4.1 cost、weight、path 三个矩阵各管什么Floyd 的经典写法需要三张同尺寸的矩阵很多人对着代码抄完还是不知道每张在干嘛。cost是输入就是建好的邻接矩阵G.Edge只读不改weight是输出weight[i][j]存最终的最短距离path是辅助path[i][j]存的是「i 到 j 的最短路上经过哪个中转点」取 -1 表示两点直达、不需要中转。三者的关系是cost提供初始值weight在递推中被不断松弛path在每次松弛成功时记下当前的中转点 k。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; } } /* 递推k 是最外层i、j 在内层 */ for (k 0; k n; k) { for (i 0; i n; i) { for (j 0; j n; j) { if (weight[i][j] weight[i][k] weight[k][j]) { weight[i][j] weight[i][k] weight[k][j]; path[i][j] k; /* 记下这次的中转点 */ } } } } }参数说明n是实际顶点数而不是MaxVertices传错会让未使用的下标参与运算虽然结果一般不受影响但会拖慢 n 倍——20³ 对 10³ 差 8 倍规模小时无所谓习惯要养好。cost里的不可达值参与加法是安全的因为MaxWeight MaxWeight一定大于任何单个MaxWeight不会触发松弛。4.2 为什么 k 必须是最外层循环三重循环的嵌套顺序是这段代码唯一不能动的地方。k在最外层的含义是「本轮只允许经过顶点 k 中转」经过 n 轮之后任意两点之间的路径允许经过全部顶点自然就是最优解。如果把k挪到内层等于对每一对 (i, j) 都做一次「只允许经过当前 k」的松弛之前轮次算出的中间结果会被反复覆盖某些组合会算错而且错得很隐蔽——小规模测试用例恰好能过换一张图就崩。这个顺序还带来一个副作用恰好是正确实现路径回溯的关键第 k 轮结束后weight[i][k]和weight[k][j]已经是最终值后面不会再变小因此path[i][k]、path[k][j]也定格了。这意味着path[i][j] k记下来的这条「拆成两段」的信息是永久有效的递归下去一定能拼出完整路径。反过来说如果实现里把path[i][j]记成k之外的东西比如path[i][k]递归就会走进死循环。4.3 路径打印把正序/逆序两个分支删掉换成一个递归原始代码在这块绕了远路。它用一个while (m ! -1)循环从中转点往前倒推靠if (j k) k m; else j m;判断「这次该收哪一端」把中转点一个个塞进value[]数组最后再根据起点终点下标大小决定正序还是倒序打印。这套逻辑只在「顶点编号顺序恰好等于路径方向」时成立换个编号方案就打印出一串乱序节点——报告里那句「逆序输出时得到的结果有点问题」根因就在这。正确的做法是把path的语义用递归表达出来i到j的最短路若经过中转点k那么路径就是「i 到 k 的最短路 k k 到 j 的最短路」。写出来只有五行正序逆序问题自动消失。/* 打印 i 到 j 之间的中转点不含两端 */ static void PrintMid(int path[][MaxVertices], SeqList L, int i, int j) { int k path[i][j]; if (k -1) return; /* 直达没有中转点 */ PrintMid(path, L, i, k); /* 左半段 */ printf(%s —— , L.list[k].name); PrintMid(path, L, k, j); /* 右半段 */ } void PrintPath(int path[][MaxVertices], SeqList L, int i, int j, int dist) { printf(最短距离%d\n, dist); printf(%s —— , L.list[i].name); /* 起点 */ PrintMid(path, L, i, j); /* 中间节点 */ printf(%s\n, L.list[j].name); /* 终点 */ }配套的查询函数还有一处必须补的防御原始Path里int j, k;声明后没有初始化靠strcmp匹配去赋值。一旦用户输入的景点名打错一个字j和k就是栈上的随机值随后weight[j][k]直接越界读轻则打印垃圾数据重则段错误。int j -1, k -1; for (i 0; i G.vertices.size; i) { if (strcmp(G.vertices.list[i].name, from) 0) j i; if (strcmp(G.vertices.list[i].name, to) 0) k i; } if (j -1 || k -1) { printf(景点名称有误请重新输入\n); return; } if (j k) { printf(起点和终点相同距离为 0\n); return; } Floyd(G.Edge, G.vertices.size, weight, path); PrintPath(path, G.vertices, j, k, weight[j][k]);这三个判断看起来啰嗦但它们挡住了实际演示中最常见的三种输入打错字、走神重复输入同一个景点、以及查一个不存在的景点。答辩现场被要求「随便输一个」的时候能稳住就是分数。5. 避坑与排查这套课设代码最常翻车的五个点5.1 五条血泪记录按现象、原因、解决写路径顺序错乱只有直达路径是对的。现象是从 A 到 B 打印出一串节点顺序跟实际走的路线对不上有时还会重复打印同一个景点。原因是用while循环从path里倒推中转点并且靠j k这样的编号大小比较来决定收哪一端隐含假设了「编号顺序等于路径方向」。解决办法是彻底删掉这段倒推逻辑改成上面那个PrintMid递归path的语义本来就是树形拆分用递归表达最直接。反向查询查不到或者返回 1000 表示不可达。现象是 A 到 B 有结果B 到 A 显示没有路径。原因是建图时只写了Edge[i][j]没写Edge[j][i]边集里一条路只出现了一次。解决办法是先跑Check函数打印矩阵对称性确认每对顶点双向都有权值如果采用「一条路写一次」的边集风格就在建图循环里补上对称赋值。输入中文景点名查不到或者控制台输出一堆乱码。现象是明明照着菜单上的名字敲的程序说「不在提供范围内」或者路径里的中文变成问号。原因有两层一是scanf(%s, name)遇到空格就截断景点名里带空格必然失败二是源文件编码和终端代码页不一致GBK 源文件在 UTF-8 终端下输出就是乱码。解决办法是统一编码Windows 下用chcp 65001切终端代码页、源文件存 UTF-8Linux 下确认 locale 设置输入上改用fgets读整行再去掉换行符或者干脆让用户输景点代号绕开中文输入。char buf[64]; fgets(buf, sizeof(buf), stdin); buf[strcspn(buf, \n)] \0; /* 去掉换行保留空格 */景点代号突然变成一个莫名其妙的大数。现象是查询简介时code打印出来是随机值而name和introduction显示正常。原因是name[20]装不下 UTF-8 编码下的长景点名strcpy写穿了 2 个字节正好覆盖相邻结构体成员的code字段。解决办法是把name扩到 32 字节或者用strncpy加手动补\0别用strcpy。程序越用越卡退出菜单后行为异常。现象是查几次之后响应变慢最后关不掉。原因很典型Information1()和Path1()在末尾调用menu()递归回到主菜单用户每操作一次就多压一层栈帧操作几十次之后栈就吃不消了。解决办法是把menu()改成while (1)循环各功能函数返回后继续循环输入 0 时break退出函数之间不再互相调用。void menu(void) { int n; while (1) { printf(1.景点信息查询 2.最短路径查询 0.退出\n请选择); if (scanf(%d, n) ! 1) break; if (n 0) break; switch (n) { case 1: Information1(); break; case 2: Path1(); break; default: printf(无此选项\n); } } }5.2 一套能过验收的测试用例表演示的时候最怕临时想不出查什么提前把下面这张表抄在纸上逐条走一遍覆盖直达、中转、不可达、错误输入四类场景。表里的距离按前面 28 条边推算实际跑出来的数值对不上就说明边集或对称赋值出了问题。编号输入预期结果验证点T1图书馆 → 图书馆距离 0路径只有自身起点终点相同的分支T2老教 → 图书馆距离 5直达单边直达path 应为 -1T3学生第二食堂 → 老教经草地中转距离 65一次中转的递归拆分T4男生宿舍 → 图书馆经物理楼、博学楼、草地、老教距离 90多次中转、路径长度最大T5输入「图书管」错字提示名称有误不崩溃防御 j/k 未初始化T6反向查 T4 的起终点距离相同路径节点顺序反转无向图对称性T7景点信息查询输入「操场」打印代号、简介顺序表扫描与 strcmpT4 是整张表里最有价值的一条距离最长、中转点最多路径打印的递归层级也最深任何一处path记录错误都会在这里暴露。T6 专门用来抓「单向边」的漏网之鱼。T5 用来证明程序不会因为用户手抖就崩掉——这一条在验收时往往是加分项因为它体现了对边界输入的处理意识。6. 把 1000 换成 INF再判断什么时候该换算法原始代码用MaxWeight 1000当无穷大够用但不严谨。换成0x3f3f3f3f这种「两个相加不溢出 int」的值更稳同时给 Floyd 内层加两个剪枝跳过i j的自比较跳过weight[i][k] INF的无效中转。前者省掉一批无意义的对角线运算后者能防止不可达点作为中转参与松弛。#define INF 0x3f3f3f3f for (k 0; k n; k) for (i 0; i n; i) { if (weight[i][k] INF) continue; /* i 到 k 都不通k 中转无意义 */ for (j 0; j n; j) { if (i j) continue; int t weight[i][k] weight[k][j]; if (t weight[i][j]) { weight[i][j] t; path[i][j] k; } } }改完之后记得把Creat里的初始化值一起换掉两处不一致会导致矩阵里同时存在 1000 和 0x3f3f3f3f 两种「无穷」比较逻辑立刻失效。至于该不该换算法我的判断标准很朴素顶点数在 50 以内、需要「任意两点都能问」、查询次数不多Floyd 就是最优解——代码短、没有堆、不用处理单源限制O(n³)在 n10 时只有 1000 次内层迭代微秒级完成。反过来如果景点涨到几百个、边却只有几百条或者需求变成「实时导航、每次只问一个起点」那 Dijkstra 配邻接表才是正路Floyd 光是初始化矩阵的O(n²)就够呛。很多人喜欢在课设里堆两个算法对比我更建议把一套 Floyd 的路径回溯讲透比塞两套半成品强。顺带一个效率上的小习惯Floyd 其实只需要在程序启动、建完图之后跑一次把weight和path存成全局矩阵之后每次查询只做下标查找。原始代码是每次查询都重新调一遍Floyd10 个顶点察觉不到但它反映的是「算法调用位置」的认识问题讲清楚这一点比优化几个时钟周期值钱。从那以后我每次接这类图论课设都强制自己先跑三件事打印邻接矩阵看对称性、用一条最长路径验证递归打印、再拿一个打错的景点名试崩不崩。这三步走完后面基本不会返工。希望帮到你。本文还有配套的精品资源点击获取