简介：面向数据结构课程设计场景的校园导航系统文档，适合计算机相关专业学生及需要完成图论综合实验的读者，用于解决校园景点信息查询与任意两点间最短路径求解问题。压缩包内共1个doc文件，约187KB，内容为一份结构完整的课程设计报告，涵盖任务书、详细设计、调试测试、时间复杂度分析、源程序清单与执行结果、C程序设计总结、致谢及参考文献等模块，可作为课设撰写与答辩准备参考。报告以无向图抽象校园地图，采用邻接矩阵存储景点与道路，结合Floyd算法实现最短路径输出，并讨论Dijkstra、Bellman-Ford等算法的适用条件，还记录调试中路径正序输出等问题的处理思路。已有67人学习，适合需要参考报告结构、算法选型与测试分析写法的读者。

1. 帮学弟调试校园导航：一个“反向问路”引出的血泪现场

同一段代码，从食堂问到图书馆是 55 米，从图书馆问回食堂却成了 90 米，还把路线绕成了一个圈。这是某高校《数据结构》课程设计里最经典的一道题：校园导航系统。需求不复杂——把校园里十个左右的场所抽象成图上的顶点，道路抽象成带权边，给来访客人查景点信息、查两点之间的最短路径。技术上也很朴素：C 语言多文件组织，顺序表存景点，邻接矩阵存路，Floyd 算法算多源最短路，一趟把任意两点之间的距离和路线都算出来。它适合正在做课程设计、想找一个能跑通又能讲清楚的项目骨架的人：代码量不大，但图建模、算法实现、路径还原、交互菜单这几块一个不少，改起来也有明确方向。

2. 需求拆解与技术选型：10 个景点 28 条边，为什么偏偏是邻接矩阵配 Floyd

2.1 把任务书翻译成能编码的数据

题目里那句“至少包括 10 个以上的场所，每两个场所间可以有不同的路，路长也可能不同”，落到代码上就是三步：先列顶点，再列边，最后定算法。顶点表我一般这么开：

下标是数组索引，代号是给人看的编号，两者分离是有意为之：接下去所有算法只跟下标打交道，代号和名称纯粹是展示层的东西。要是把代号直接当下标用，一旦景点增删，所有边的索引全得跟着改，改一处漏一处。边表则用RowColWeight这种“三元组”形式平铺出来，一条边一行，起点、终点、路长。项目里一共 28 条记录，看起来像 28 条路，其实是 14 条路各写了两遍——因为校园道路是没有方向的，无向图在矩阵里必须对称存储。这一点非常关键，后面避坑章节会专门说它翻车的样子。

2.2 三个最短路算法，为什么选 Floyd

课程设计里能选的最短路算法就那三个：Dijkstra、Bellman-Ford、Floyd。Dijkstra 解决的是单源问题，跑一次得到“一个点到其余所有点”的距离，复杂度 O(n²)；Bellman-Ford 能处理负权边，但校园里不存在“负的米数”，用不上；Floyd 是三重循环，O(n³)，一次把任意两点之间的距离全算出来。

关键在于题目要求：“找出从任意场所到达另一场所的最佳路径”。翻译过来就是多源查询。用 Dijkstra 也能做，但得对每个起点各跑一次，n 次 Dijkstra 累积下来同样是 O(n³)，代码却要长一倍，还得额外维护 n 份距离数组。而本项目 n=10，Floyd 的三重循环总共也就 1000 次内层比较，配合一个 20×20 的矩阵，运行时间在微秒级别，完全看不出开销。所以这里的取舍非常干脆：要的是“代码短、结果全、调试直观”，不是“抠常数”。

提示：如果哪天景点扩到几百个，Floyd 的 O(n³) 就会变得难受，那时候才轮到 Dijkstra 加堆优化上场。选型永远跟着数据规模走，别背结论。

2.3 邻接矩阵还是邻接表

图的存储结构无非邻接矩阵和邻接表两派。邻接矩阵开一个 n×n 的二维数组，Edge[i][j]就是 i 到 j 的路长，不存在边就填一个表示“不通”的大数；邻接表则是每个顶点挂一条链表，只存真实存在的边。

校园导航这个场景里，n 只有 10，边有 14 条（双向算 28 条记录），属于小规模偏稠密的图。矩阵占 20×20×4 字节 = 1.6KB，这点内存压根不用心疼；而它带来的好处是判边 O(1)、Floyd 里weight[i][k] + weight[k][j]可以直接数组下标取值，不用顺着链表找。反过来，如果用邻接表，Floyd 那三重循环里每次都要遍历链表找 k 的邻居，代码立刻丑三倍。所以这里矩阵是正解：规模小、要频繁随机访问、还要做矩阵式的动态规划，三个条件全中。

真正需要邻接表的，是那种几千个路口、几十万条边的城市路网：矩阵开不下，绝大多数格子还是空的，浪费得离谱。区分标准就一句话——顶点数小、边密集用矩阵；顶点数大、边稀疏用邻接表。

3. 工程结构拆解：七个源文件是怎么分工的

3.1 文件清单与包含顺序

这个课程设计最值得学的地方不是算法，而是它把一份几百行的小程序拆成了七个文件，每个文件只负责一件事：

有个细节必须注意：school.cpp里先#define MaxSize 20、#define MaxVertices 20、#define MaxWeight 1000，然后才#include "Floyd.h"和#include "AdjMGraphCreat.h"。原因是这两个头文件内部直接用了MaxVertices这些宏，如果先包含头文件、后定义宏，编译器会直接报“未声明的标识符”。这种依赖顺序在单文件程序里不显眼，一旦拆成多文件就成了新手第一天卡住的地方。

我一般会把这类常量单独抽一个config.h，让每个用到的头文件自己#include "config.h"，谁也不用猜谁先谁后。头文件还应该加包含保护：

/* config.h：全局常量集中管理，任何头文件都可以放心包含 */ #ifndef CONFIG_H #define CONFIG_H #define MaxSize 20 /* 顺序表最大容量 */ #define MaxVertices 20 /* 景点数上限 */ #define MaxWeight 1000 /* 表示"不直接连通"的权值，必须远大于任何真实路长 */ #endif

这样处理后，Floyd.h只依赖config.h，与school.cpp的书写顺序彻底解耦。宏MaxWeight的取值也有讲究：它必须比任何一条可能出现的路径总长都大，否则 Floyd 会把它当成真实距离去参与比较，算出来的“最短路”就是假的。十来个景点、单条路最长几十米，路径总长顶多几百，取 1000 够用。

3.2 四个结构体，字段各管什么

整个项目的骨架就压在四个结构体上，把它们读透，代码基本就通了一半：

/* 景点：顺序表里存的元素类型 */ typedef struct { char name[20]; /* 景点名称，查询时的关键字 */ int code; /* 景点代号，纯展示用 */ char introduction[50]; /* 一句话简介 */ } DataType; /* 边：建图时以"平铺三元组数组"的形式一次性传进来 */ typedef struct { int row; /* 起点在顶点表中的下标 */ int col; /* 终点在顶点表中的下标 */ int weight; /* 路长 */ } RowColWeight; /* 图：顶点用顺序表，边用邻接矩阵 */ typedef struct { SeqList vertices; /* 顶点集合 */ int Edge[MaxVertices][MaxVertices]; /* 邻接矩阵，存路长 */ int numOfEdge; /* 边的记录条数 */ } AdjMGraph;

DataType里的name长度定 20、introduction定 50，是典型的课程设计做法——够用、不动态分配、不会内存泄漏。真要做成产品，这两个字段应该换成char *加strdup，或者干脆用结构体里嵌柔性数组。但在这个规模下，固定长度反而省事，scanf("%s")直接读进去就行。

AdjMGraph把顶点表和邻接矩阵打包在一起，好处是传参只传一个指针。注意numOfEdge记的是“边记录条数”，对无向图来说等于真实道路数的两倍，这个语义在写报告和调试打印时容易搞混。

3.3 建图函数：一次把顶点和边都灌进去

建图是整个项目的入口，也是最容易埋雷的地方：

void Creat(AdjMGraph *G, DataType v[], RowColWeight rcw[], int n, int e) { int i, j, k; /* 1. 顶点表：把 n 个景点顺序塞进顺序表 */ ListInitiate(&G->vertices); for (i = 0; i < n; i++) ListInsert(&G->vertices, i, v[i]); /* 2. 邻接矩阵初始化：自己到自己距离 0，其余先当"不通" */ for (i = 0; i < n; i++) for (j = 0; j < n; j++) G->Edge[i][j] = (i == j) ? 0 : MaxWeight; /* 3. 逐条写边，rcw[k].weight 就是这条路的路长 */ for (k = 0; k < e; k++) { i = rcw[k].row; j = rcw[k].col; G->Edge[i][j] = rcw[k].weight; } G->numOfEdge = e; }

参数含义很直白：G是待构造的图指针，v是顶点数组，rcw是边三元组数组，n是顶点数，e是边记录条数。三个循环分别干了三件事——灌顶点、铺满矩阵、写边。注意第 3 步只写了Edge[i][j]，没有写Edge[j][i]，所以无向图的对称性完全依赖调用方在rcw里把两个方向都列出来。项目里的 28 条记录正是这么成对写的：{0,1,20}配{1,0,20}，{2,3,15}配{3,2,15}。

这种写法的优点是建图函数干净利落、一行代码不掺业务；缺点是数据表一长就容易漏配。我一般会在建图完成后加一段自检：

/* 建图后自检：无向图必须对称，漏写一半会立刻暴露 */ for (i = 0; i < n; i++) for (j = 0; j < n; j++) if (G->Edge[i][j] != G->Edge[j][i]) printf("警告：边 (%d,%d) 不对称，检查 rcw 表\n", i, j);

十几行代码，能省掉后面半小时的“为什么这条路只能单向走”的排查。

4. 核心算法拆解：Floyd 三重循环与 path 矩阵还原

4.1 两张表：一张记距离，一张记路径

Floyd 的入口参数有四样：cost是原始邻接矩阵，n是顶点数，weight和path是两张输出表。weight[i][j]最终存 i 到 j 的最短距离，path[i][j]存的是“i 到 j 的最短路径中途经的某个中间点”，没有中间点就记-1。

void Floyd(int cost[][MaxVertices], int n, int weight[][MaxVertices], int path[][MaxVertices]) { int i, j, k; /* 初始化：dist 直接抄邻接矩阵，path 全部清 -1 */ for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { weight[i][j] = cost[i][j]; path[i][j] = -1; } } /* 三重循环：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; /* 记下这次的中转点 */ } } } } }

这段代码短得不像话，但有两个地方必须讲清楚。第一，k一定要在最外层。Floyd 的本质是动态规划：第 k 轮结束时，weight[i][j]表示“只允许经过编号 0..k 的点作为中转”时的最短距离。如果把 k 放到内层，就变成了“每一对 (i,j) 内部都试一遍所有中转点”，逻辑上不再是逐轮递推，结果会错。这是最经典的 Floyd 写法错误，编译器不会报，只会悄悄给出错误答案。

第二，k从 0 开始完全没问题。原文调试记录里提到“逆序输出有问题”，一度怀疑是循环从 0 起导致的，其实跟起点无关——k从 0 起才是标准写法，k=0只是表示“允许借用 0 号顶点中转”。真正的问题出在路径还原那一段，跟这三重循环没有关系。

4.2 path 矩阵里到底存了什么

很多人第一次看path[i][j] = k会以为它存的是“j 的前驱”，其实不是。它存的是：在 i 到 j 的最优路径上，位于中间的那个点。这个语义带来一个好处和一个麻烦。

好处是内存极省：一张 n×n 的 int 矩阵就够了，不用为每条路径开数组。

麻烦是还原路径得靠递归。因为path[i][j] = k只告诉你“要经过 k”，至于 i 到 k 怎么走、k 到 j 怎么走，得继续查path[i][k]和path[k][j]。原项目里用了一个if (j < k) k = m; else j = m;的写法，靠比较下标大小来猜该往哪边收缩，这个思路只在部分数据上凑巧成立，一旦路径上的中间点编号不是单调递增，输出就会错乱，甚至死循环。

正确的还原方式是把“两端”当成子问题递归下去：

/* 递归输出 i 到 j 的最短路径上的中间点，不含两端 */ void PrintMid(int path[][MaxVertices], int i, int j, AdjMGraph *G) { int mid = path[i][j]; if (mid == -1) /* 没有中间点，说明 i、j 直连 */ return; PrintMid(path, i, mid, G); /* 先输出 i → mid 段 */ printf("%s ——> ", G->vertices.list[mid].name); PrintMid(path, mid, j, G); /* 再输出 mid → j 段 */ }

调用方只需要先打印起点名、再调PrintMid(path, s, t, G)、最后打印终点名，顺序天然是从起点到终点。递归深度最多 n 层（这里是 10），栈完全扛得住。这十几行代码是整个项目里我最建议自己手写一遍的部分——它把“分治还原路径”这件事讲得比任何教科书都直白。

4.3 信息查询：线性扫描加一个下标判断

景点信息查询没什么算法含量，就是顺序表扫描：

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); break; } } if (i == G.vertices.size) printf("您所查询的景点不在我们所提供的范围内！\n"); }

这段代码的巧思在最后那句if (i == G.vertices.size)：循环正常走完，i 一定等于表长；中途break出来，i 就小于表长。用计数器判断“找没找到”，比额外开一个flag变量干净。缺点也明显：传进来的是AdjMGraph G而不是指针，整个图（含 20×20 矩阵）被拷贝了一份，1.6KB 的栈拷贝在 PC 上无所谓，但这是个坏习惯，改成const AdjMGraph *G更好。

复杂度上，查询是 O(n) 顺序扫描，n 个景点最多比 10 次，可以忽略；Floyd 是 O(n³)。原文报告里写 Floyd 空间复杂度 O(1)，这是不准确的——它需要两张 n×n 的辅助矩阵，空间是 O(n²)。这一点如果答辩被问到，得答对。

4.4 菜单与函数调用关系

交互层在Operation.h里，menu()打印两个选项，switch分发到Information1()或Path1()，两个函数各自scanf拿输入、调底层、然后回头再调menu()，形成自递归的菜单循环。这种写法简单粗暴，缺点是退出只能靠关窗口——switch里没有default，输入 3 会直接什么都不做地卡在那里。做二次开发时，第一件事就是把菜单改成while(1)加case 0: return;。

5. 避坑与排查：课程设计里最容易翻车的五个点

5.1 现象：A 到 B 有路，B 到 A 提示不通

原因：无向图在邻接矩阵里必须对称，但rcw表里只写了{0,1,20}没写{1,0,20}，Creat又只赋Edge[row][col]，于是矩阵成了有向的。这种情况下 Floyd 算出来的weight[1][0]仍是MaxWeight，程序要么输出“最短路径为 1000”，要么按不可达处理。

解决：建完图跑一遍对称性自检（见 3.3 的代码），或者干脆在Creat里加一句G->Edge[j][i] = rcw[k].weight;，让调用方只写单向、函数负责双向。两种都行，关键是团队内约定死一种，别一半靠函数、一半靠数据表。

5.2 现象：编译报MaxVertices未定义，可明明写在文件开头了

原因：Floyd.h、AdjMGraphCreat.h里直接用MaxVertices声明数组，但宏定义写在school.cpp的#include之后，预处理器展开头文件时宏还不存在。同类事故还有全角引号——从 Word 里拷出来的”学生第二食堂”看着像双引号，编译器直接报一堆莫名其妙的错，肉眼盯半天看不出区别。

解决：常量统一抽到config.h，每个头文件自己包含；头文件加#ifndef保护。全角标点的问题只能靠编辑器解决——把乱码字符高亮打开，或者编译前先全局搜一遍中文标点。

5.3 现象：输入一个不存在的景点名，程序直接崩或者输出上一次的结果

原因：Path()里用j、k记录两个景点的下标，但循环里只有strcmp相等才赋值，找不到就完全不初始化。此时j、k是栈上的随机值，path[j][k]就是一次越界访问。

解决：初值置 -1，循环后立刻判断：

int j = -1, k = -1; for (i = 0; i < G.vertices.size; i++) { if (strcmp(G.vertices.list[i].name, sceneryname) == 0) j = i; if (strcmp(G.vertices.list[i].name, sceneryname1) == 0) k = i; } if (j == -1 || k == -1) { printf("输入的景点名有误，请检查后重试\n"); return; }

这类“没找到就往下走”的 bug 在 C 里没有任何保护，只要程序崩了，第一反应就该去看下标有没有可能是 -1 或者随机值。

5.4 现象：两个本来不连通的点，输出最短路径 1000

原因：MaxWeight被当作“无穷大”写进矩阵，但 Floyd 里weight[i][k] + weight[k][j]会拿它参与加法。如果两个点压根不连通，这个“距离”会一直是 1000 或者 2000，最后照样被当成有效结果打印出来。

解决：输出前判断if (weight[s][t] >= MaxWeight / 2) printf("两地之间无通路\n");，而不是直接打印数字。如果想让容错更强，把MaxWeight改成0x3f3f3f3f（约 10.6 亿），这样两个“无穷”相加也不会溢出成负数——1000 加两次就 2000，虽然不会溢出，但 1000 这个量级太容易被真实路长追平，一旦有路径总长超过 1000，判断逻辑就失效了。

5.5 现象：正向查路径正常，反向查路径绕圈或直接错位

原因：原文的if (j < k) k = m; else j = m;靠下标大小猜方向，本质上是假设“路径上的中间点编号必然单调”，这个假设对某些数据成立，对另一些立刻失效。加上while循环里path[j][k]的下标在不断变化，一旦猜错方向，就会在两个点之间来回跳。

解决：丢掉方向猜测，改用 4.2 的递归还原。另外还有一个小坑要注意：调用递归前必须先把起点名打印出来，否则输出会变成“路径为：主楼 ——> 图书馆”而丢掉起点。

6. 二次开发：把课程设计改成能用的东西

课程设计交完就该考虑怎么让它有点实用价值。最值得动手的第一件事是把写死的数组挪出代码：

/* 从 map.txt 读图：第一行 n e，随后 n 行景点，再 e 行边 */ int LoadMap(const char *file, AdjMGraph *G) { FILE *fp = fopen(file, "r"); DataType v[MaxVertices]; RowColWeight rcw[MaxVertices * MaxVertices]; int n, e, i; if (!fp) return -1; fscanf(fp, "%d%d", &n, &e); for (i = 0; i < n; i++) fscanf(fp, "%s %d %s", v[i].name, &v[i].code, v[i].introduction); for (i = 0; i < e; i++) fscanf(fp, "%d %d %d", &rcw[i].row, &rcw[i].col, &rcw[i].weight); fclose(fp); Creat(G, v, rcw, n, e); return 0; }

文本格式建议一行一景点、一行一边，字段用空格隔开，fscanf就能直接吃。换校园、加景点、改路长全变成改文本文件，不用重编译。注意introduction里有空格的话，%s会截断，要么改用%[^"]之类带定界符的格式，要么把简介里的空格换成下划线——这是我从一个带空格的地名上栽过跟头之后才记住的。

第二件事是把 Floyd 和 Dijkstra 各写一份做对拍。Floyd 是全源，Dijkstra 是单源，对每个起点各跑一次 Dijkstra，把结果和 Floyd 的weight矩阵逐格比对，只要有一格不等，就说明其中一份实现有 bug。这个方法比手工造测试用例靠谱得多，而且顺手能把 Dijkstra 也练一遍，答辩的时候多一个加分项。

第三件事是交互体验。现在的菜单是自递归的，输入非法字符会直接陷入死循环（scanf("%d")读失败后字符留在缓冲区反复失败）。改成while循环 +fgets读整行再解析，同时给景点名加个前缀匹配，输入“图书”也能命中“图书馆”。这些改动都不涉及算法，但用户感知最强。

最后一个技巧：把路径输出改成带方向箭头的完整句子，并在末尾附上总距离，比单独打印一个数字更像导航。我吃过一次亏——答辩时老师问“这条路是 55 米还是 5 米”，我才发现输出里只有一个光秃秃的“55”，单位全靠脑补。从那以后我每次写这类项目，所有输出格式都强制走一遍“打印出来读一遍”的流程，读不通顺就说明信息丢了。希望帮到你。

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