简介这份Word课程设计报告面向计算机相关专业学生与数据结构课程设计初学者围绕校园导航系统给出较完整的实现思路和文档范例可用于课程设计选题、实验报告撰写与最短路径算法复习。报告以无向图表示校园景点与道路采用邻接矩阵存储顶点和边并围绕景点信息查询、任意两点间最短路径求解展开设计内容覆盖任务书要求、数据结构与存储结构说明、Floyd算法设计、调试测试、时间复杂度分析、源程序清单、C程序设计总结及致谢等模块。压缩包共1个doc文件大小约187KB便于查阅和打印。已有67人学习下载适合需要参考课程设计组织方式、梳理图结构与最短路径实现细节、补齐测试分析和总结内容的读者也可作为数据结构综合实验的模板与排错思路参考。1. 需求先立住为什么校园导航这道课设不该只做成“能跑就行”校园导航系统是数据结构课程设计里被选得最多、也最容易被做浅的一道题。多数人拿到任务书先想界面、先想贴图结果一被问“你的图存在哪、这条路径凭什么最短、换一对起点还对不对”就答不上来。这份方案要解决的问题很具体把一所校园的平面图抽象成带权无向图用顶点存景点、用边存路程让使用者可以查任意景点的信息也可以查任意两个景点之间的最短路线。它适合正在赶数据结构课程设计、需要一份从建模到验收都说得清的同学也适合想拿一套完整图论小系统做参考的开发者。下面按数据怎么存、算法怎么算、代码怎么分、坑在哪、怎么答辩的顺序往下走。2. 数据建模与存储选型10 个景点、28 条边怎么装进内存这道题真正的起点不是算法是“校园”这两个字怎么落到结构体上。景点有名字、有代号、有一句简介道路有起点、有终点、有长度整张图还要能回答“从 A 到 B 通不通”。三件事对应三组数据混在一起写后面查询和求路径都会互相绊脚。2.1 顶点、边、图的三层结构体我一般把景点本身、景点集合、整张图拆成三层各管一件事。景点是记录顺序表是容器邻接矩阵是关系。这么拆的好处是查景点信息时只碰顺序表算路径时只碰矩阵两边互不干扰。#define MaxSize 20 /* 顺序表能放的最大景点数 */ #define MaxVertices 20 /* 图能容纳的最大顶点数 */ #define MaxWeight 1000 /* 不可达的边权取一个远大于任何真实路程的值 */ /* 第一层一个景点就是一条记录 */ typedef struct { char name[20]; /* 景点名称中文一个字符占两字节20 字节约 10 个汉字 */ int code; /* 景点代号打印和人工核对用 */ char introduction[50]; /* 一句话简介够写“藏书 50 万册”这种量级 */ } DataType; /* 第二层顺序表把景点按录入顺序连续存放按下标随机访问 */ typedef struct { DataType list[MaxSize]; int size; /* 当前实际景点数不是 20 */ } SeqList; /* 第三层邻接矩阵顶点表 边权矩阵 边计数 */ typedef struct { SeqList vertices; /* 顶点信息 */ int Edge[MaxVertices][MaxVertices]; /* 边权Edge[i][j] 为 i 到 j 的路程 */ int numOfEdge; /* 已登记的边条数 */ } AdjMGraph; /* 建图用的三元组一条带权边一行方便把数据写死在一张表里 */ typedef struct { int row, col, weight; } RowColWeight;这里有个容易忽略的细节DataType里的name[20]是字节数不是汉字数。UTF-8 下一个汉字占 3 字节20 字节只够 6 个汉字加结尾符“学生第二食堂”这种 6 字名字刚好卡在边界上。稳妥的做法是把它放大到char name[32]或者统一约定景点名不超过 6 个汉字写进报告的数据说明里。Edge矩阵按MaxVertices × MaxVertices开10 个景点实际只用左上角 10×10剩下 300 个格子是浪费的。但20 × 20 × 4 字节也就 1.6KB对这门课的量级完全无所谓。这就是“先用满再优化”的典型场景没必要为了省几百字节去写动态分配。2.2 邻接矩阵和邻接表的选择依据选存储结构时很多同学会条件反射选邻接表理由是“图通常稀疏、邻接表省空间”。放到这道题上这个理由不成立原因有三条。第一Floyd 算法的核心动作是反复访问weight[i][k] weight[k][j]。用矩阵是两次下标寻址O(1)用邻接表得先从 i 的边表里找 k、再从 k 的边表里找 j每轮三重循环里多做两次链表扫描代码量和常数都上去了。第二这道题要求“任意两个景点之间”的最短路径属于全源问题。矩阵天然就是全源答案的容器算完直接weight[s][t]取结果邻接表存的是邻接关系全源结果还得另开一张表承接等于白绕一圈。第三10 个景点、双向登记后 28 条边边数远小于n² 100理论上是稀疏图。但“稀疏”只在 n 很大时才有意义n10 的时候省下来的那点空间还不够多写一个链表节点结构体。所以结论很干脆顶点用顺序表关系用邻接矩阵矩阵里存权值不存 0/1。存权值的好处是求路径时不用回查边表坏处是必须区分“不通”和“长度为 0”这就引出下一节建图时的初始化问题。2.3 建图把 28 条带权边写进一张数据表任务书要求至少 10 个场所这里选 10 个覆盖吃、住、学、活动、出入口五类保证图是连通的、任意两点都有路可走。下标景点名称代号简介0学生第二食堂10学生的主要就餐点1男生宿舍11一共有八栋2操场12塑胶跑道和人工草坪3物理楼13各类实验器材4博学楼14上课集中地5草地15休闲的地方6老教学楼16学校最早的教学楼7女生宿舍17一共七栋8小门18通往校外生活区9图书馆19藏书 50 万册边用三元组数组写死无向图双向各登记一次所以 14 条实际道路变成 28 条记录。这种写法看着笨但改数据不用动代码答辩现场想加一个景点也只改数组。/* 顶点表顺序与下面的下标严格对应改顺序必须同步改边表 */ DataType v[] { {学生第二食堂, 10, 学生的主要就餐点}, {男生宿舍, 11, 一共有八栋}, {操场, 12, 塑胶跑道和人工草坪}, {物理楼, 13, 各类实验器材}, {博学楼, 14, 上课集中地}, {草地, 15, 休闲的地方}, {老教学楼, 16, 学校最早的教学楼}, {女生宿舍, 17, 一共七栋}, {小门, 18, 通往校外生活区}, {图书馆, 19, 藏书50万册} }; /* 边表一条无向边登记两次(0,1,20) 与 (1,0,20) 是同一段路 */ 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}, {3,0,35},{3,1,20},{3,2,15},{3,4,30}, {4,2,30},{4,3,30},{4,5,10}, {5,4,10},{5,6,35},{5,8,8}, {6,5,35},{6,7,20},{6,8,25},{6,9,5}, {7,6,20},{7,8,10}, {8,5,8},{8,6,25},{8,7,10}, {9,6,5} };建图函数负责三件事拷顶点、清矩阵、写边。清矩阵这一步是最容易漏的因为 C 的全局数组默认全是 0而 0 在权值语义里表示“两点重合”不是“不通”。void Creat(AdjMGraph *G, DataType v[], RowColWeight e[], int n, int m) { int i, j; /* 1. 顶点表整体拷贝size 记录真实数量 */ for (i 0; i n; i) G-vertices.list[i] v[i]; G-vertices.size n; /* 2. 矩阵初始化对角线 0自己到自己其余置 MaxWeight不直接通 */ for (i 0; i MaxVertices; i) for (j 0; j MaxVertices; j) G-Edge[i][j] (i j) ? 0 : MaxWeight; /* 3. 逐条写边。m 是登记条数无向图已在数据表里双写这里不再对称赋值 */ for (i 0; i m; i) G-Edge[e[i].row][e[i].col] e[i].weight; G-numOfEdge m; }参数含义要写进报告n是顶点数本例 10m是边表中已登记的记录数本例 28对应 14 条无向边。如果改成“数据表只写半边、建图函数里对称赋值”那m就是 14numOfEdge也要跟着改成m * 2。两种做法都对但一定不能混着来混用会让边数统计和实际矩阵对不上答辩时被追问一句就露馅。3. 最短路径算法Floyd 的三重循环与 path 矩阵还原图建好之后系统要回答的核心问题只有一个给定起点 s 和终点 t走哪条路最短。这道题的场景决定了算法选型不是“哪个高级用哪个”。3.1 为什么是全源 Floyd而不是单源 Dijkstra任务书写的是“任意两个场所之间的一条最短路径”。注意“任意两个”这四个字它把问题从单源变成了全源。Dijkstra 一次只能算一个起点到其余所有点的距离要覆盖全部点对就得对 10 个顶点各跑一次10 次里每次还要维护一个未确定集合代码长度和出错面都翻倍。Floyd 的写法是三重循环加一个松弛判断二十行以内解决问题一次算完全部 100 个点对。代价是 O(n³)n10 时是 1000 次内层判断现代机器上连一毫秒都用不到完全不需要为性能纠结。至于 Bellman-Ford它解决的是负权边问题。校园道路长度不可能是负数这条路从一开始就不用考虑。把这个判断写进报告的“算法选型”一节比单纯罗列三种算法名字要有说服力得多。3.2 weight 与 path 两张表的初始化与松弛Floyd 的关键是同时维护两张 n×n 表weight[i][j]存当前已知的最短距离path[i][j]存这条路径经过的中转点。初始化时weight直接抄邻接矩阵path全部置 -1表示“暂时认为 i 到 j 是直达的”。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 必须是最外层每轮只允许经过编号 k 的顶点做中转 */ 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; /* 记的是中转点不是前驱 */ } }三个参数要讲清楚cost是原始的邻接矩阵只读不改保证多次查询结果一致weight和path是传出参数由调用方开好MaxVertices × MaxVertices的栈上数组传进来。path[i][j] k这一行的语义是“i 到 j 的最短路在 k 处拐了一下”这条信息足够还原整条路径但不够直接打印因为它是分治式的不是链式的。k放在最外层这一点经常被写反。如果写成i在最外层算法退化成“只允许用 i 做中转”结果会偏大。这个错误不会报编译错误只会让距离算错属于典型的静默失败测试用例必须能覆盖到。3.3 路径还原path 里存的是中转点不是前驱这是整份课设里最容易翻车的一段。原始做法是用while循环顺着path往回找把中转点收进一个数组再根据起点下标和终点下标的相对大小决定正序还是逆序打印。这个思路在两点编号“一前一后”时能跑通一旦路径先升后降方向判断就失效输出顺序会乱。根因在于path记录的是分治结构path[i][j] k意味着“i 到 j i 到 k k 到 j”这是一个递归定义用循环加方向标志去模拟递归等于自己给自己找麻烦。直接按定义写递归代码短且不会错。/* 打印 i 到 j 的最短路径不含 j 本身由调用方在最后补上终点 */ void PrintPath(int path[][MaxVertices], int i, int j, SeqList *L) { int k path[i][j]; if (k -1) { /* 直达没有任何中转点输出起点即可 */ printf(%s - , L-list[i].name); } else { /* 拆成两段递归先 i 到 k再 k 到 j */ PrintPath(path, i, k, L); PrintPath(path, k, j, L); } }调用方这么写printf(最短距离为 %d\n, weight[s][t]); printf(路线); PrintPath(path, s, t, G.vertices); printf(%s\n, G.vertices.list[t].name); /* 递归不输出终点这里补 */递归深度最多等于路径上的中转点数10 个顶点撑死 9 层栈不会出问题。用这套写法正着查、反着查、路径先升后降、中间拐三次输出顺序都由调用栈保证不需要任何方向标志。这就是把数据结构本身的语义用对比事后打补丁省事。3.4 复杂度怎么写才经得起追问查询景点信息是顺序表线性扫描从头比到size时间复杂度 O(n)空间 O(1)。Floyd 是三重循环时间复杂度 O(n³)但空间不是 O(1)weight和path各开了一张 n×n 的表加上图本身的邻接矩阵空间是 O(n²)。有些参考资料说 Floyd 可以原地更新、空间 O(1)那是把weight直接建在邻接矩阵上、并且不保存路径的情况。这份方案要还原路径path省不掉所以必须写 O(n²)。报告里把这两句写准答辩时反而能加分。因为老师问复杂度考的往往不是背没背过而是知不知道自己开了几张表、每张表多大。4. 模块划分与代码组织七个文件各管一段十个景点、两个查询、一个菜单全塞进main.cpp也能跑但报告里的“模块功能说明”就没法写函数调用关系也说不清。按“数据结构—建图—算法—查询—交互”切成五层每层一个头文件main只负责准备数据这是课程设计里最省事的组织方式。4.1 头文件分层与调用关系文件职责对外提供SeqList.h顺序表结构体与基本操作DataType、SeqListAdjMGraph.h邻接矩阵结构体定义AdjMGraphAdjMGraphCreat.h由顶点表 边三元组建图Creat()Floyd.h全源最短路径计算Floyd()、PrintPath()Inquiry.h景点信息查询、路径查询Information()、Path()Operation.h菜单与两个查询入口menu()、Information1()、Path1()school.cpp数据表与main()—调用关系是一条直线没有回头路main调Creat建图然后进menumenu调两个入口函数入口函数再调Inquiry里的查询函数查询函数最后调Floyd。哪一层出问题看它上面的那一层就行排查路径非常短。注意AdjMGraph这个类型被多个文件用到得有统一的定义处。放在AdjMGraph.h里其他文件#include它避免在几处重复写结构体导致类型不一致。这类“重复定义”的问题编译期一般不报链接期才炸早期定好规矩能省很多时间。4.2 菜单用循环不要自己调自己原始写法是在menu()末尾再调一次menu()靠递归实现“查完继续查”。功能上确实能用但有两个隐患一是每查一次压一层栈帧演示时连续查几十次栈一直不释放二是没有退出分支用户想结束时只能关窗口。改成while循环顺手把非法输入也挡掉void menu(void) { int choice; while (1) { puts( 校园导航 ); puts( 1. 景点信息查询); puts( 2. 两点间最短路径查询); puts( 0. 退出); printf(请选择: ); /* scanf 返回成功读入的项数非数字输入会返回 0必须清缓冲 */ if (scanf(%d, choice) ! 1) { while (getchar() ! \n) ; /* 把这一行脏字符吃干净否则死循环 */ puts(请输入数字选项\n); continue; } switch (choice) { case 1: Information1(); break; case 2: Path1(); break; case 0: return; /* 唯一出口 */ default: puts(没有这个选项\n); } } }scanf那几行是血泪经验如果用户手滑输入一个字母choice保持原值不动缓冲区里的字母一直留着下一轮scanf又读到它屏幕会疯狂刷菜单。加一段清缓冲问题立刻消失。4.3 两个查询入口信息查询与路径查询景点信息查询是最简单的线性扫描用strcmp逐个比对找到就打印三个字段扫完没找到就提示。这里有个细节要处理for循环结束后i的值就是size用它判断“没找到”比另设一个标志变量干净。void Information(AdjMGraph G, char scenery[]) { int i; for (i 0; i G.vertices.size; i) { if (strcmp(G.vertices.list[i].name, scenery) 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, scenery); }路径查询要先把两个景点名翻译成下标再调Floyd再用PrintPath还原。翻译这一步必须校验如果起点或终点有一个没找到下标就停在初始值上直接拿去索引矩阵就是越界访问程序会莫名其妙崩掉而且崩的位置和出错原因隔了很远。void Path(AdjMGraph G, char from[], char to[]) { int i, s -1, t -1; int weight[MaxVertices][MaxVertices]; int path[MaxVertices][MaxVertices]; /* 1. 名称转下标找不到就记住 -1 */ for (i 0; i G.vertices.size; i) { if (strcmp(G.vertices.list[i].name, from) 0) s i; if (strcmp(G.vertices.list[i].name, to) 0) t i; } if (s -1 || t -1) { printf(起点或终点不在景点表中请重新输入\n); return; } /* 2. 一次 Floyd得到全部点对的距离与中转点 */ Floyd(G.Edge, G.vertices.size, weight, path); /* 3. 不可达要单独判断否则会打印出一个 1000 的假距离 */ if (weight[s][t] MaxWeight) { printf(%s 到 %s 之间没有可达路径\n, from, to); return; } /* 4. 输出 */ printf(最短距离%d\n路线, weight[s][t]); PrintPath(path, s, t, G.vertices); printf(%s\n, G.vertices.list[t].name); }两个数组开在函数栈上每次查询重新算一遍。10 个点的规模重复计算完全不心疼换来的是“每次结果都是最新数据”的确定性。如果以后景点增加到几百个再考虑把结果缓存成全局表、只在数据变动时重算那是另一个量级的优化这门课不需要提前做。5. 调试与避坑五个最容易翻车的地方课设的分数差距往往不在“写没写出来”而在“出错之后能不能定位”。下面五条是这类图论小系统里复现率最高的坑每条都按现象、原因、解决三步写照着排查能省掉大半天。5.1 路径输出正着查正常反着查乱序现象查“学生第二食堂 → 图书馆”时路线显示正常反过来查“图书馆 → 学生第二食堂”输出的景点顺序错乱甚至出现重复。原因用while循环顺着path往回找中转点收进数组后再靠“起点下标是否小于终点下标”决定正序还是逆序打印。path记录的是分治式中转点路径结构是“递归拆两段”不是一条从头到尾的链一旦某条最短路先经过编号大的点、再经过编号小的点这个大小判断就失效顺序自然乱。解决删掉方向标志和收集数组直接按path[i][j] k的语义写递归展开见 3.3 的PrintPath。递归的调用顺序天然就是路径顺序起点在前、终点在后任何形状的路径都不会错。5.2 从文档里抄代码带进全角标点现象代码看着和资料上一模一样编译却报一堆stray \243 in program之类的错误指向的位置还挺随机。原因报告文档里的代码片段带着中文引号、全角分号、全角括号粘进编辑器后字符串外面的标点必须全是半角编译器不认识这些字符。这类错误最气人因为肉眼看不出差别。解决编辑器统一 UTF-8 编码中文只允许出现在字符串字面量内部编译报stray时直接跳到报错行把该行所有标点重打一遍。更省事的办法是打开编辑器的“显示不可见字符”全角符号一眼就能看出来。5.3 邻接矩阵没初始化算出“一步到位”的假最短现象两个明明不直接相连的景点查出来距离是 0 或者一个很小的值路线显示为直达。原因Edge是全局数组默认全 0。如果建图时只写了有边的格子没把其余格子填成MaxWeight那些格子就保持 0Floyd 会认为“i 到 j 有一条长度为 0 的路”一路松弛下去所有距离都被压扁。解决建图函数第一步就把整个矩阵刷一遍(i j) ? 0 : MaxWeight然后再写真实边权。另外在输出前加一道判断weight[s][t] MaxWeight时提示“不可达”避免把 1000 这种哨兵值当成真实距离打出来。5.4 无向图只填半边A 能到 B、B 到不了 A现象查“食堂 → 操场”正常查“操场 → 食堂”提示不可达。原因边表里只登记了row → col矩阵只有上三角有值下三角全是MaxWeight。无向图的两个方向必须都有值缺一半就等于把路修成了单行道。解决两种做法二选一不能混。一是数据表里双向各写一条本例 14 条路写成 28 条记录建图函数照单全收二是数据表只写一半建图时统一补G-Edge[col][row] weight。混用的后果是边数统计翻倍或者路径单向报告里的“边数”也会和实际矩阵对不上。5.5 复杂度写错、测试用例缺失答辩当场卡壳现象报告里写 Floyd“时间 O(n³)、空间 O(1)”被问“那你weight和path两张二维表放在哪”答不上来或者测试章节只贴了几张运行截图没有一个完整的输入输出对照表。原因复杂度是从资料上抄的没对着自己的代码数一遍开了几张表测试是跑一遍截图了事没有设计用例的意识。解决复杂度按实际代码数weight[n][n]、path[n][n]、Edge[MaxVertices][MaxVertices]空间是 O(n²)写清楚反而显得懂。测试用例提前设计至少覆盖直达、一次中转、多次中转、不可达、景点名不存在五种情况每条写清输入、预期输出、实际输出截图作为附件而不是正文。6. 验收与答辩一张测试用例表和十分钟演示脚本课设的最后一步不是“跑通了”而是“能证明它跑对了”。我一般会准备一张测试用例表把边界情况全走一遍答辩时直接照着表演示比临场想输入靠谱得多。表里的距离值可以自己按矩阵手算核对算一遍就知道程序有没有偷偷走错路。编号输入操作预期输出考察点T1学生第二食堂 → 操场路径查询距离 30直达相邻顶点T2男生宿舍 → 图书馆路径查询距离 98经物理楼、博学楼、草地、小门、老教学楼多次中转T3图书馆 → 男生宿舍路径查询距离 98路线为 T2 的逆序反向查询一致性T4学生第二食堂 → 图书馆路径查询距离 108编号先升后降的路径T5物理楼信息查询代号 13、简介正常显示顶点信息读取T6体育馆信息查询提示未找到非法景点名T7操场 → 不存在路径查询提示起点或终点不存在下标校验T8连续查询 5 次菜单每次结果一致菜单不刷屏状态无污染演示节奏控制在十分钟内先用三十秒讲清楚“10 个顶点、14 条道路、28 条登记边”的数据规模再花两分钟跑 T1 到 T4重点展示 T3 的反向查询和 T4 的先升后降路径这两条是最能体现路径还原是否写对的。然后用一分钟跑 T5 到 T7 展示异常处理最后留五六分钟回答提问。提问高频集中在三个方向提前把答案写在纸上为什么用 Floyd 不用 Dijkstra全源、代码短、无负权10 个点的三次方开销可忽略空间复杂度为什么是 O(n²) 不是 O(1)两张 n×n 表加邻接矩阵如果校园扩到 50 个景点怎么办改MaxVertices、边表扩容、Floyd 仍是 125000 次内层判断可以接受再往上就该换 Dijkstra 加邻接表了。第三个问题看似超纲其实是在考你有没有想过方案的边界。从那以后我每次带这类课设都强制走一遍“先设计测试用例表、再写代码”的顺序而不是写完再随便点几下。因为点几下只能证明它没崩证明不了它算对。希望这份方案能帮你把这道题做扎实答辩时被追问也能答得上来。本文还有配套的精品资源点击获取 
长河君 · 2026/11/2 3:15:00 · 阅读 1.2k 校园导航课设：邻接矩阵与Floyd最短路径实现
简介这份Word课程设计报告面向计算机相关专业学生与数据结构课程设计初学者围绕校园导航系统给出较完整的实现思路和文档范例可用于课程设计选题、实验报告撰写与最短路径算法复习。报告以无向图表示校园景点与道路采用邻接矩阵存储顶点和边并围绕景点信息查询、任意两点间最短路径求解展开设计内容覆盖任务书要求、数据结构与存储结构说明、Floyd算法设计、调试测试、时间复杂度分析、源程序清单、C程序设计总结及致谢等模块。压缩包共1个doc文件大小约187KB便于查阅和打印。已有67人学习下载适合需要参考课程设计组织方式、梳理图结构与最短路径实现细节、补齐测试分析和总结内容的读者也可作为数据结构综合实验的模板与排错思路参考。1. 需求先立住为什么校园导航这道课设不该只做成“能跑就行”校园导航系统是数据结构课程设计里被选得最多、也最容易被做浅的一道题。多数人拿到任务书先想界面、先想贴图结果一被问“你的图存在哪、这条路径凭什么最短、换一对起点还对不对”就答不上来。这份方案要解决的问题很具体把一所校园的平面图抽象成带权无向图用顶点存景点、用边存路程让使用者可以查任意景点的信息也可以查任意两个景点之间的最短路线。它适合正在赶数据结构课程设计、需要一份从建模到验收都说得清的同学也适合想拿一套完整图论小系统做参考的开发者。下面按数据怎么存、算法怎么算、代码怎么分、坑在哪、怎么答辩的顺序往下走。2. 数据建模与存储选型10 个景点、28 条边怎么装进内存这道题真正的起点不是算法是“校园”这两个字怎么落到结构体上。景点有名字、有代号、有一句简介道路有起点、有终点、有长度整张图还要能回答“从 A 到 B 通不通”。三件事对应三组数据混在一起写后面查询和求路径都会互相绊脚。2.1 顶点、边、图的三层结构体我一般把景点本身、景点集合、整张图拆成三层各管一件事。景点是记录顺序表是容器邻接矩阵是关系。这么拆的好处是查景点信息时只碰顺序表算路径时只碰矩阵两边互不干扰。#define MaxSize 20 /* 顺序表能放的最大景点数 */ #define MaxVertices 20 /* 图能容纳的最大顶点数 */ #define MaxWeight 1000 /* 不可达的边权取一个远大于任何真实路程的值 */ /* 第一层一个景点就是一条记录 */ typedef struct { char name[20]; /* 景点名称中文一个字符占两字节20 字节约 10 个汉字 */ int code; /* 景点代号打印和人工核对用 */ char introduction[50]; /* 一句话简介够写“藏书 50 万册”这种量级 */ } DataType; /* 第二层顺序表把景点按录入顺序连续存放按下标随机访问 */ typedef struct { DataType list[MaxSize]; int size; /* 当前实际景点数不是 20 */ } SeqList; /* 第三层邻接矩阵顶点表 边权矩阵 边计数 */ typedef struct { SeqList vertices; /* 顶点信息 */ int Edge[MaxVertices][MaxVertices]; /* 边权Edge[i][j] 为 i 到 j 的路程 */ int numOfEdge; /* 已登记的边条数 */ } AdjMGraph; /* 建图用的三元组一条带权边一行方便把数据写死在一张表里 */ typedef struct { int row, col, weight; } RowColWeight;这里有个容易忽略的细节DataType里的name[20]是字节数不是汉字数。UTF-8 下一个汉字占 3 字节20 字节只够 6 个汉字加结尾符“学生第二食堂”这种 6 字名字刚好卡在边界上。稳妥的做法是把它放大到char name[32]或者统一约定景点名不超过 6 个汉字写进报告的数据说明里。Edge矩阵按MaxVertices × MaxVertices开10 个景点实际只用左上角 10×10剩下 300 个格子是浪费的。但20 × 20 × 4 字节也就 1.6KB对这门课的量级完全无所谓。这就是“先用满再优化”的典型场景没必要为了省几百字节去写动态分配。2.2 邻接矩阵和邻接表的选择依据选存储结构时很多同学会条件反射选邻接表理由是“图通常稀疏、邻接表省空间”。放到这道题上这个理由不成立原因有三条。第一Floyd 算法的核心动作是反复访问weight[i][k] weight[k][j]。用矩阵是两次下标寻址O(1)用邻接表得先从 i 的边表里找 k、再从 k 的边表里找 j每轮三重循环里多做两次链表扫描代码量和常数都上去了。第二这道题要求“任意两个景点之间”的最短路径属于全源问题。矩阵天然就是全源答案的容器算完直接weight[s][t]取结果邻接表存的是邻接关系全源结果还得另开一张表承接等于白绕一圈。第三10 个景点、双向登记后 28 条边边数远小于n² 100理论上是稀疏图。但“稀疏”只在 n 很大时才有意义n10 的时候省下来的那点空间还不够多写一个链表节点结构体。所以结论很干脆顶点用顺序表关系用邻接矩阵矩阵里存权值不存 0/1。存权值的好处是求路径时不用回查边表坏处是必须区分“不通”和“长度为 0”这就引出下一节建图时的初始化问题。2.3 建图把 28 条带权边写进一张数据表任务书要求至少 10 个场所这里选 10 个覆盖吃、住、学、活动、出入口五类保证图是连通的、任意两点都有路可走。下标景点名称代号简介0学生第二食堂10学生的主要就餐点1男生宿舍11一共有八栋2操场12塑胶跑道和人工草坪3物理楼13各类实验器材4博学楼14上课集中地5草地15休闲的地方6老教学楼16学校最早的教学楼7女生宿舍17一共七栋8小门18通往校外生活区9图书馆19藏书 50 万册边用三元组数组写死无向图双向各登记一次所以 14 条实际道路变成 28 条记录。这种写法看着笨但改数据不用动代码答辩现场想加一个景点也只改数组。/* 顶点表顺序与下面的下标严格对应改顺序必须同步改边表 */ DataType v[] { {学生第二食堂, 10, 学生的主要就餐点}, {男生宿舍, 11, 一共有八栋}, {操场, 12, 塑胶跑道和人工草坪}, {物理楼, 13, 各类实验器材}, {博学楼, 14, 上课集中地}, {草地, 15, 休闲的地方}, {老教学楼, 16, 学校最早的教学楼}, {女生宿舍, 17, 一共七栋}, {小门, 18, 通往校外生活区}, {图书馆, 19, 藏书50万册} }; /* 边表一条无向边登记两次(0,1,20) 与 (1,0,20) 是同一段路 */ 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}, {3,0,35},{3,1,20},{3,2,15},{3,4,30}, {4,2,30},{4,3,30},{4,5,10}, {5,4,10},{5,6,35},{5,8,8}, {6,5,35},{6,7,20},{6,8,25},{6,9,5}, {7,6,20},{7,8,10}, {8,5,8},{8,6,25},{8,7,10}, {9,6,5} };建图函数负责三件事拷顶点、清矩阵、写边。清矩阵这一步是最容易漏的因为 C 的全局数组默认全是 0而 0 在权值语义里表示“两点重合”不是“不通”。void Creat(AdjMGraph *G, DataType v[], RowColWeight e[], int n, int m) { int i, j; /* 1. 顶点表整体拷贝size 记录真实数量 */ for (i 0; i n; i) G-vertices.list[i] v[i]; G-vertices.size n; /* 2. 矩阵初始化对角线 0自己到自己其余置 MaxWeight不直接通 */ for (i 0; i MaxVertices; i) for (j 0; j MaxVertices; j) G-Edge[i][j] (i j) ? 0 : MaxWeight; /* 3. 逐条写边。m 是登记条数无向图已在数据表里双写这里不再对称赋值 */ for (i 0; i m; i) G-Edge[e[i].row][e[i].col] e[i].weight; G-numOfEdge m; }参数含义要写进报告n是顶点数本例 10m是边表中已登记的记录数本例 28对应 14 条无向边。如果改成“数据表只写半边、建图函数里对称赋值”那m就是 14numOfEdge也要跟着改成m * 2。两种做法都对但一定不能混着来混用会让边数统计和实际矩阵对不上答辩时被追问一句就露馅。3. 最短路径算法Floyd 的三重循环与 path 矩阵还原图建好之后系统要回答的核心问题只有一个给定起点 s 和终点 t走哪条路最短。这道题的场景决定了算法选型不是“哪个高级用哪个”。3.1 为什么是全源 Floyd而不是单源 Dijkstra任务书写的是“任意两个场所之间的一条最短路径”。注意“任意两个”这四个字它把问题从单源变成了全源。Dijkstra 一次只能算一个起点到其余所有点的距离要覆盖全部点对就得对 10 个顶点各跑一次10 次里每次还要维护一个未确定集合代码长度和出错面都翻倍。Floyd 的写法是三重循环加一个松弛判断二十行以内解决问题一次算完全部 100 个点对。代价是 O(n³)n10 时是 1000 次内层判断现代机器上连一毫秒都用不到完全不需要为性能纠结。至于 Bellman-Ford它解决的是负权边问题。校园道路长度不可能是负数这条路从一开始就不用考虑。把这个判断写进报告的“算法选型”一节比单纯罗列三种算法名字要有说服力得多。3.2 weight 与 path 两张表的初始化与松弛Floyd 的关键是同时维护两张 n×n 表weight[i][j]存当前已知的最短距离path[i][j]存这条路径经过的中转点。初始化时weight直接抄邻接矩阵path全部置 -1表示“暂时认为 i 到 j 是直达的”。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 必须是最外层每轮只允许经过编号 k 的顶点做中转 */ 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; /* 记的是中转点不是前驱 */ } }三个参数要讲清楚cost是原始的邻接矩阵只读不改保证多次查询结果一致weight和path是传出参数由调用方开好MaxVertices × MaxVertices的栈上数组传进来。path[i][j] k这一行的语义是“i 到 j 的最短路在 k 处拐了一下”这条信息足够还原整条路径但不够直接打印因为它是分治式的不是链式的。k放在最外层这一点经常被写反。如果写成i在最外层算法退化成“只允许用 i 做中转”结果会偏大。这个错误不会报编译错误只会让距离算错属于典型的静默失败测试用例必须能覆盖到。3.3 路径还原path 里存的是中转点不是前驱这是整份课设里最容易翻车的一段。原始做法是用while循环顺着path往回找把中转点收进一个数组再根据起点下标和终点下标的相对大小决定正序还是逆序打印。这个思路在两点编号“一前一后”时能跑通一旦路径先升后降方向判断就失效输出顺序会乱。根因在于path记录的是分治结构path[i][j] k意味着“i 到 j i 到 k k 到 j”这是一个递归定义用循环加方向标志去模拟递归等于自己给自己找麻烦。直接按定义写递归代码短且不会错。/* 打印 i 到 j 的最短路径不含 j 本身由调用方在最后补上终点 */ void PrintPath(int path[][MaxVertices], int i, int j, SeqList *L) { int k path[i][j]; if (k -1) { /* 直达没有任何中转点输出起点即可 */ printf(%s - , L-list[i].name); } else { /* 拆成两段递归先 i 到 k再 k 到 j */ PrintPath(path, i, k, L); PrintPath(path, k, j, L); } }调用方这么写printf(最短距离为 %d\n, weight[s][t]); printf(路线); PrintPath(path, s, t, G.vertices); printf(%s\n, G.vertices.list[t].name); /* 递归不输出终点这里补 */递归深度最多等于路径上的中转点数10 个顶点撑死 9 层栈不会出问题。用这套写法正着查、反着查、路径先升后降、中间拐三次输出顺序都由调用栈保证不需要任何方向标志。这就是把数据结构本身的语义用对比事后打补丁省事。3.4 复杂度怎么写才经得起追问查询景点信息是顺序表线性扫描从头比到size时间复杂度 O(n)空间 O(1)。Floyd 是三重循环时间复杂度 O(n³)但空间不是 O(1)weight和path各开了一张 n×n 的表加上图本身的邻接矩阵空间是 O(n²)。有些参考资料说 Floyd 可以原地更新、空间 O(1)那是把weight直接建在邻接矩阵上、并且不保存路径的情况。这份方案要还原路径path省不掉所以必须写 O(n²)。报告里把这两句写准答辩时反而能加分。因为老师问复杂度考的往往不是背没背过而是知不知道自己开了几张表、每张表多大。4. 模块划分与代码组织七个文件各管一段十个景点、两个查询、一个菜单全塞进main.cpp也能跑但报告里的“模块功能说明”就没法写函数调用关系也说不清。按“数据结构—建图—算法—查询—交互”切成五层每层一个头文件main只负责准备数据这是课程设计里最省事的组织方式。4.1 头文件分层与调用关系文件职责对外提供SeqList.h顺序表结构体与基本操作DataType、SeqListAdjMGraph.h邻接矩阵结构体定义AdjMGraphAdjMGraphCreat.h由顶点表 边三元组建图Creat()Floyd.h全源最短路径计算Floyd()、PrintPath()Inquiry.h景点信息查询、路径查询Information()、Path()Operation.h菜单与两个查询入口menu()、Information1()、Path1()school.cpp数据表与main()—调用关系是一条直线没有回头路main调Creat建图然后进menumenu调两个入口函数入口函数再调Inquiry里的查询函数查询函数最后调Floyd。哪一层出问题看它上面的那一层就行排查路径非常短。注意AdjMGraph这个类型被多个文件用到得有统一的定义处。放在AdjMGraph.h里其他文件#include它避免在几处重复写结构体导致类型不一致。这类“重复定义”的问题编译期一般不报链接期才炸早期定好规矩能省很多时间。4.2 菜单用循环不要自己调自己原始写法是在menu()末尾再调一次menu()靠递归实现“查完继续查”。功能上确实能用但有两个隐患一是每查一次压一层栈帧演示时连续查几十次栈一直不释放二是没有退出分支用户想结束时只能关窗口。改成while循环顺手把非法输入也挡掉void menu(void) { int choice; while (1) { puts( 校园导航 ); puts( 1. 景点信息查询); puts( 2. 两点间最短路径查询); puts( 0. 退出); printf(请选择: ); /* scanf 返回成功读入的项数非数字输入会返回 0必须清缓冲 */ if (scanf(%d, choice) ! 1) { while (getchar() ! \n) ; /* 把这一行脏字符吃干净否则死循环 */ puts(请输入数字选项\n); continue; } switch (choice) { case 1: Information1(); break; case 2: Path1(); break; case 0: return; /* 唯一出口 */ default: puts(没有这个选项\n); } } }scanf那几行是血泪经验如果用户手滑输入一个字母choice保持原值不动缓冲区里的字母一直留着下一轮scanf又读到它屏幕会疯狂刷菜单。加一段清缓冲问题立刻消失。4.3 两个查询入口信息查询与路径查询景点信息查询是最简单的线性扫描用strcmp逐个比对找到就打印三个字段扫完没找到就提示。这里有个细节要处理for循环结束后i的值就是size用它判断“没找到”比另设一个标志变量干净。void Information(AdjMGraph G, char scenery[]) { int i; for (i 0; i G.vertices.size; i) { if (strcmp(G.vertices.list[i].name, scenery) 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, scenery); }路径查询要先把两个景点名翻译成下标再调Floyd再用PrintPath还原。翻译这一步必须校验如果起点或终点有一个没找到下标就停在初始值上直接拿去索引矩阵就是越界访问程序会莫名其妙崩掉而且崩的位置和出错原因隔了很远。void Path(AdjMGraph G, char from[], char to[]) { int i, s -1, t -1; int weight[MaxVertices][MaxVertices]; int path[MaxVertices][MaxVertices]; /* 1. 名称转下标找不到就记住 -1 */ for (i 0; i G.vertices.size; i) { if (strcmp(G.vertices.list[i].name, from) 0) s i; if (strcmp(G.vertices.list[i].name, to) 0) t i; } if (s -1 || t -1) { printf(起点或终点不在景点表中请重新输入\n); return; } /* 2. 一次 Floyd得到全部点对的距离与中转点 */ Floyd(G.Edge, G.vertices.size, weight, path); /* 3. 不可达要单独判断否则会打印出一个 1000 的假距离 */ if (weight[s][t] MaxWeight) { printf(%s 到 %s 之间没有可达路径\n, from, to); return; } /* 4. 输出 */ printf(最短距离%d\n路线, weight[s][t]); PrintPath(path, s, t, G.vertices); printf(%s\n, G.vertices.list[t].name); }两个数组开在函数栈上每次查询重新算一遍。10 个点的规模重复计算完全不心疼换来的是“每次结果都是最新数据”的确定性。如果以后景点增加到几百个再考虑把结果缓存成全局表、只在数据变动时重算那是另一个量级的优化这门课不需要提前做。5. 调试与避坑五个最容易翻车的地方课设的分数差距往往不在“写没写出来”而在“出错之后能不能定位”。下面五条是这类图论小系统里复现率最高的坑每条都按现象、原因、解决三步写照着排查能省掉大半天。5.1 路径输出正着查正常反着查乱序现象查“学生第二食堂 → 图书馆”时路线显示正常反过来查“图书馆 → 学生第二食堂”输出的景点顺序错乱甚至出现重复。原因用while循环顺着path往回找中转点收进数组后再靠“起点下标是否小于终点下标”决定正序还是逆序打印。path记录的是分治式中转点路径结构是“递归拆两段”不是一条从头到尾的链一旦某条最短路先经过编号大的点、再经过编号小的点这个大小判断就失效顺序自然乱。解决删掉方向标志和收集数组直接按path[i][j] k的语义写递归展开见 3.3 的PrintPath。递归的调用顺序天然就是路径顺序起点在前、终点在后任何形状的路径都不会错。5.2 从文档里抄代码带进全角标点现象代码看着和资料上一模一样编译却报一堆stray \243 in program之类的错误指向的位置还挺随机。原因报告文档里的代码片段带着中文引号、全角分号、全角括号粘进编辑器后字符串外面的标点必须全是半角编译器不认识这些字符。这类错误最气人因为肉眼看不出差别。解决编辑器统一 UTF-8 编码中文只允许出现在字符串字面量内部编译报stray时直接跳到报错行把该行所有标点重打一遍。更省事的办法是打开编辑器的“显示不可见字符”全角符号一眼就能看出来。5.3 邻接矩阵没初始化算出“一步到位”的假最短现象两个明明不直接相连的景点查出来距离是 0 或者一个很小的值路线显示为直达。原因Edge是全局数组默认全 0。如果建图时只写了有边的格子没把其余格子填成MaxWeight那些格子就保持 0Floyd 会认为“i 到 j 有一条长度为 0 的路”一路松弛下去所有距离都被压扁。解决建图函数第一步就把整个矩阵刷一遍(i j) ? 0 : MaxWeight然后再写真实边权。另外在输出前加一道判断weight[s][t] MaxWeight时提示“不可达”避免把 1000 这种哨兵值当成真实距离打出来。5.4 无向图只填半边A 能到 B、B 到不了 A现象查“食堂 → 操场”正常查“操场 → 食堂”提示不可达。原因边表里只登记了row → col矩阵只有上三角有值下三角全是MaxWeight。无向图的两个方向必须都有值缺一半就等于把路修成了单行道。解决两种做法二选一不能混。一是数据表里双向各写一条本例 14 条路写成 28 条记录建图函数照单全收二是数据表只写一半建图时统一补G-Edge[col][row] weight。混用的后果是边数统计翻倍或者路径单向报告里的“边数”也会和实际矩阵对不上。5.5 复杂度写错、测试用例缺失答辩当场卡壳现象报告里写 Floyd“时间 O(n³)、空间 O(1)”被问“那你weight和path两张二维表放在哪”答不上来或者测试章节只贴了几张运行截图没有一个完整的输入输出对照表。原因复杂度是从资料上抄的没对着自己的代码数一遍开了几张表测试是跑一遍截图了事没有设计用例的意识。解决复杂度按实际代码数weight[n][n]、path[n][n]、Edge[MaxVertices][MaxVertices]空间是 O(n²)写清楚反而显得懂。测试用例提前设计至少覆盖直达、一次中转、多次中转、不可达、景点名不存在五种情况每条写清输入、预期输出、实际输出截图作为附件而不是正文。6. 验收与答辩一张测试用例表和十分钟演示脚本课设的最后一步不是“跑通了”而是“能证明它跑对了”。我一般会准备一张测试用例表把边界情况全走一遍答辩时直接照着表演示比临场想输入靠谱得多。表里的距离值可以自己按矩阵手算核对算一遍就知道程序有没有偷偷走错路。编号输入操作预期输出考察点T1学生第二食堂 → 操场路径查询距离 30直达相邻顶点T2男生宿舍 → 图书馆路径查询距离 98经物理楼、博学楼、草地、小门、老教学楼多次中转T3图书馆 → 男生宿舍路径查询距离 98路线为 T2 的逆序反向查询一致性T4学生第二食堂 → 图书馆路径查询距离 108编号先升后降的路径T5物理楼信息查询代号 13、简介正常显示顶点信息读取T6体育馆信息查询提示未找到非法景点名T7操场 → 不存在路径查询提示起点或终点不存在下标校验T8连续查询 5 次菜单每次结果一致菜单不刷屏状态无污染演示节奏控制在十分钟内先用三十秒讲清楚“10 个顶点、14 条道路、28 条登记边”的数据规模再花两分钟跑 T1 到 T4重点展示 T3 的反向查询和 T4 的先升后降路径这两条是最能体现路径还原是否写对的。然后用一分钟跑 T5 到 T7 展示异常处理最后留五六分钟回答提问。提问高频集中在三个方向提前把答案写在纸上为什么用 Floyd 不用 Dijkstra全源、代码短、无负权10 个点的三次方开销可忽略空间复杂度为什么是 O(n²) 不是 O(1)两张 n×n 表加邻接矩阵如果校园扩到 50 个景点怎么办改MaxVertices、边表扩容、Floyd 仍是 125000 次内层判断可以接受再往上就该换 Dijkstra 加邻接表了。第三个问题看似超纲其实是在考你有没有想过方案的边界。从那以后我每次带这类课设都强制走一遍“先设计测试用例表、再写代码”的顺序而不是写完再随便点几下。因为点几下只能证明它没崩证明不了它算对。希望这份方案能帮你把这道题做扎实答辩时被追问也能答得上来。本文还有配套的精品资源点击获取