校园导航系统课设：邻接矩阵+Floyd实现任意景点最短路径与信息查询

简介：面向数据结构课程设计的校园导航系统报告文档，适合正在完成图论类课设、需要参考规范文档结构与实现思路的计算机专业学生。正文按任务书要求、数据结构与存储结构说明、算法设计思想、调试与测试、时间复杂度分析、源程序清单与执行结果、C程序设计总结、致谢与参考文献依次展开，形成可直接对照的写作框架。技术实现以邻接矩阵存储无向图，顶点保存景点名称、代号与简介，边保存路径长度，用Floyd算法求解任意两景点间最短路径，并配套景点信息查询，覆盖十处以上场所的校园平面图设计。资源包为1个doc文件，约187KB，单文档囊括报告正文与代码清单，便于按章节检索改写。已有67人学习，可帮助读者快速理清从需求分析到编码实现再到文档成型的完整链路。

1. 校园导航系统的课设落点：十个景点、十四条路，与两条查询主线

数据结构课程设计里，校园导航系统是出镜率很高的一个题目，但真正动手写的人大多会卡在同一个地方：任务书只说了“找出任意两个场所之间的最佳路径”，却没讲清楚路径该怎么输出、查不到的景点怎么提示、矩阵里的“无穷大”用什么数代替。原料其实不复杂，十个景点、十四条双向道路、一张带权无向图，全部家当就这些。麻烦的是把“查景点简介”和“查最短路”这两条主线做扎实，还得让程序在验收现场不翻车。

这套方案面向两类人：正在做数据结构课设、需要一个能跑通也能写进报告的实现的学生；以及想借一个小规模图算法项目把邻接矩阵、Floyd 和路径回溯一次吃透的开发者。下面按“需求怎么立、结构怎么选、代码怎么落、坑怎么避、答辩怎么收”的顺序拆开，每一段都可以直接改成本校的版本。

2. 需求拆解与选型：三句话任务书背后的无向带权图

2.1 把任务书的要求翻译成可验收的功能点

任务书原文写得克制，三句话，但每一句背后都藏着验收点。我习惯先把它们摊开成一张表，做完一项划一项，避免写到一半发现漏了东西。

这张表里最容易被忽略的是最后一行那句“正反两个方向”。很多人测通了 A 到 B 就收工，结果 B 到 A 的路径打印出来是乱的——这是这类题目最常见的翻车点之一，后面第 5 章会专门拆。

另外有个细节值得提前定下来：无向图到底算 14 条边还是 28 条边。按“两个景点之间的一条路”来理解，14 条无向边；落到邻接矩阵里，每条边要对角落两个位置，所以矩阵里有 28 个非零元。报告里写“边数 e = 14”，代码里numOfEdge也记 14，别一边写 28 一边写 14，答辩老师一眼就能看出来。

2.2 邻接矩阵还是邻接表：顶点只有十个时的取舍

选存储结构这一步，很多人是被教材带偏的。教材讲邻接表节省空间，讲得头头是道，于是有人对着 10 个景点的图也去写链表，结果 Floyd 跑不起来——因为 Floyd 需要频繁访问weight[i][k]和weight[k][j]，邻接表得先遍历链表找到那条边，再转成矩阵，等于白写一层。

真正该做的是算一笔账。10 个顶点，上限按 20 算，矩阵是 20×20 共 400 个int，撑死 1.6KB。邻接表只存 28 个边节点，确实省，可省下来那点内存在这个量级上毫无意义；而代价是每次随机访问边权都要走一遍指针。所以这里的选择没有悬念：邻接矩阵。

反过来，什么时候该换成邻接表？我的经验是看两个指标：顶点数超过几百，且边的数量远小于顶点数的平方。校园里 500 个楼宇、800 条路，这时候矩阵是 25 万格，其中绝大多数是“不可达”，那就该上邻接表了。10 个景点这个规模，矩阵是唯一合理解。

还有一层考虑是代码可读性。矩阵的Edge[i][j]一眼就能看出是“i 到 j 的直连距离”，而邻接表得先理解firstEdge、next这套指针结构。课设报告是要给人看的，能少一层解释就少一层。

2.3 Floyd、Dijkstra 还是对每个点跑一次 Dijkstra

最短路径算法有三四个可选项，这里逐个排除。

Dijkstra 是单源的，一次只能算“一个起点到所有点”的距离。而任务书要的是“任意两个景点之间”，如果每次查询都重跑一遍 Dijkstra，本质上是在做 n 次单源计算，复杂度也是 O(n³)，和 Floyd 同阶，但代码量翻倍——你还要写一个选最小值的循环，再维护一个visited数组。

Bellman-Ford 处理的是负权边。校园道路的长度不可能是负数，这个算法在这里没有用武之地，引进来只会让报告多一段用不上的解释。

Floyd 的写法只有三层循环，五行代码，一次跑完就能拿到所有点对的最短距离和走法。n=10 的时候，三重循环是 1000 次内层比较，快到你根本感觉不到延迟。而且它天然契合“任意两点”这个需求：用户点哪一对景点，weight[i][j]直接就是答案，不需要重新计算。

代价也得说清楚：Floyd 的时间复杂度 O(n³)、空间复杂度 O(n²)，顶点数涨到几千就不合适了。但这是课设，不是导航软件，规模摆在这里，选 Floyd 是最省事也最好讲的。

提示：如果报告里被问到“为什么不用 Dijkstra”，答案不是“Floyd 更简单”，而是“需求是全源最短路，Floyd 一次计算覆盖所有点对，Dijkstra 需要跑 n 次才能达到同样效果”。

3. 数据结构与总体设计：顺序表装景点、矩阵装路、path 矩阵装走法

3.1 三套结构体的职责边界

这套程序里一共三个核心结构体，各管一摊事，边界划清楚了后面写函数就不会互相牵扯。

#define MaxSize 20 /* 顺序表容量，景点数上限再留点余量 */ #define MaxVertices 20 /* 顶点上限，与上面同值便于统一修改 */ #define MaxWeight 1000 /* 代表“两点之间没有直接道路”，注意这个值的取法，见 5.2 */ typedef struct { char name[20]; /* 景点名称，中文按字节占位，20 字节其实只够 6 个汉字 */ int code; /* 景点代号，任务书明确要求存储 */ char introduction[50]; /* 景点简介，超长会被截断 */ } DataType; typedef struct { DataType list[MaxSize]; /* 顶点数组，顺序存储 */ int size; /* 已用的顶点个数 */ } 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存的是“一个景点是什么”，SeqList负责把这些景点排成一排并能按下标访问，AdjMGraph则把景点集合和道路矩阵捆在一起。这样设计的好处是：查询景点信息时只碰vertices，算最短路时只碰Edge，两套逻辑互不干扰。任务书里说的“将景点的操作变成对图中顶点的操作”，落到代码上就是这个意思。

有个地方要提前留意：name[20]在 UTF-8 编码下一个汉字约占 3 个字节，20 字节实际只装得下 6 个汉字多一点。“学生第二食堂”刚好 6 个字，加上结束符就顶到边了，再多一个字就截断。稳妥的做法是直接把name扩到 32 或 40，introduction扩到 80，代价只是多占几百字节。

3.2 建图：对角清零、对称填充、无穷大怎么选

建图函数是整份程序的地基，地基歪了后面全歪。三条规则必须一次写对。

void Creat(AdjMGraph *G, DataType v[], int n, RowColWeight rcw[], int e) { int i, j; /* 第一步：顶点表整体拷贝，size 就是景点个数 */ G->vertices.size = n; for (i = 0; i < n; i++) G->vertices.list[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 (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; } G->numOfEdge = e; }

对角线填 0 不是随便定的。Floyd 里会做weight[i][k] + weight[k][j]这样的加法，如果对角线是“无穷大”，那么i经过自己到j的路径长度就变成了无穷大加某个数，虽然不会出错，但会让中间结果变得难以理解。填 0 之后，i经过自己到j的候选路径就是0 + weight[i][j]，等于原值，参与比较也是安全的。

第三步的对称写入是最容易出事的地方，只写Edge[row][col]不写Edge[col][row]，图在逻辑上就从无向退化成有向，表现出来就是“A 到 B 查得到，B 到 A 提示不可达”。这一点在第 5 章还会展开。

调用方式长这样，十个景点和十四条路一次性喂进去：

DataType a[] = { {"学生第二食堂", 10, "学生的主要就餐点"}, {"男生宿舍", 11, "一共有八栋"}, {"操场", 12, "塑胶跑道和人工草坪"}, {"物理楼", 13, "拥有各种实验器材"}, {"博学楼", 14, "学生上课集中地"}, {"草地", 15, "休闲娱乐的好地方"}, {"老教", 16, "学校最早的教学楼"}, {"女生宿舍", 17, "一共七栋"}, {"图书馆", 18, "藏书五十万册"}, {"北门", 19, "校园北侧出入口"} }; RowColWeight rcw[] = { {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, e = 14; /* 10 个景点，14 条无向道路 */ Creat(&G, a, rcw, n, e);

数组里 14 条记录，每条只写一遍，对称那一半交给Creat里去补。这样比手写 28 条三元组更不容易出错，报告里也好解释。

3.3 头文件怎么拆：六个文件各自的边界

原始方案把代码拆成六个头文件加一个主文件，这个拆法不算最优，但比全部塞进一个.cpp强得多，至少在报告里能画出模块图。

拆模块的原则很简单：一个文件只回答一个问题。Floyd.h只回答“怎么算最短路”，不问“景点叫什么”；Inquiry.h只回答“怎么把结果打印成人能看懂的样子”，不问“最短路怎么算”。这样调试的时候，哪个环节出问题就只改那一个文件，不用在全篇一千行里翻。

有一处依赖需要留意：Floyd.h里用到了MaxVertices这个宏，所以宏定义必须放在AdjMGraph.h里，被Floyd.h包含之后再展开。如果宏写在主文件里，编译时就会提示未定义。这类编译期报错在课设里很常见，改起来不难，但要理解原因。

3.4 Floyd 的三重循环与 path 矩阵的语义

核心算法本身只有五行，写清楚每一行的含义比背下来更重要。

void Floyd(int cost[][MaxVertices], int n, int weight[][MaxVertices], int path[][MaxVertices]) { int i, j, k; /* 初始化：抄一份直连矩阵，路径矩阵全部置 -1（-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++) 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; /* 记下真正起作用的那个中间点 */ } }

path[i][j] = -1这个初始化不能改成 0。用

本文还有配套的精品资源，点击获取