简介一套面向数据结构课程设计的校园导游系统C语言实现适合需要完成图论相关课设、并希望获得高分参考的计算机专业学生。程序以校园平面图为背景用顶点表示景点、边表示路径支持不少于10个景点的信息查询以及任意两个景点间最短简单路径的问路查询可作为图存储、遍历与最短路径算法的综合实践范例。资源包共10个文件以cpp源码为核心配有多张程序运行截图、景点数据文本以及readme说明文档整体仅409KB结构简洁便于直接查阅和调试。该项目代码已通过运行测试答辩评审平均分94.5分目前已有313人浏览学习。下载后可以获得完整可运行源码、界面效果图和配套说明适合快速理解实现思路并用于自己的课程设计或复习参考。1. 为什么校园导游系统要先画图再写代码——从 10 个景点的无向带权图说起我拆这份DataStructure-curriculum-design-master.zip之前以为 95 分的高分课程设计一定有复杂的界面。解压后才发现源码只有一个校园导游.cpp配合VexType.txt和几张运行截图。再看题目要求景点不少于 10 个边存路径长度查询任意两个景点之间的最短简单路径——这不是界面题是一道完整的图论应用题。程序的核心价值在于用邻接矩阵表达校园地图、把景点数据和路径数据分离、再用 Dijkstra 完成问路查询。对正在做数据结构课程设计的人这套代码最大的学习点是小数据量下怎样用最克制的 C 语言写法把图的建立、查询、最短路径一次讲清楚。2. 数据层C 语言里的景点结构体与 VexType.txt 加载实现源码文件只有一个校园导游.cpp却专门放了一个VexType.txt说明数据与算法是分开的。这是作业第一个得分点没有把 10 个景点的信息硬编码在 main 里而是让程序从文本文件加载。看起来多了一步文件操作但换来的是改景点名称不用重新编译。下面先讲清楚顶点和边到底用什么结构组织。2.1 10 个景点其实不适合用邻接表邻接矩阵更稳题目要求景点不少于 10 个这个数量级决定了存储方式。10 个顶点的无向图最多 45 条边属于典型稀疏图从理论上讲邻接表更省空间。但在 C 语言课程设计里省这点空间没有实际意义10×10 的 int 邻接矩阵只有 400 字节而邻接表还要动态分配结点、管理链表指针。重点不是空间而是 Dijkstra 实现时邻接矩阵可以 O(1) 取edge[u][v]路径回溯也只需要借助pre数组。我一般看到 20 个以内的景点都优先选邻接矩阵等数据量到几百再考虑邻接表或链式前向星。2.2 顶点结构体、图结构体、边的存储景点信息包括代号、名称、简介正好对应一个结构体。图则把顶点数组和邻接矩阵包在一起。这个项目没有单独拆VexType.h所有定义都放在校园导游.cpp顶部这也是单文件课程设计的常见风格。一个能跑起来的设计通常长这样#define MAXVEX 30 #define INF 0x3f3f3f3f typedef struct { int code; // 景点代号如 1 char name[30]; // 景点名称 char desc[200]; // 景点简介 } VexType; typedef struct { VexType vexs[MAXVEX]; // 顶点数组 int edge[MAXVEX][MAXVEX]; // 邻接矩阵 int vexNum, edgeNum; // 实际顶点数和边数 } Graph;code对应VexType.txt里的景点代号查询时用户输入的就是它name用于路径输出desc存简介。edge[i][j]表示第 i 个景点到第 j 个景点的路径长度不可达时填INF。INF用0x3f3f3f3f而不是 9999是因为这个值做加法不容易超过 int 上限而且 memset 按字节填充也很方便。VexType.txt最常用的格式是每行编号 名称 简介三段中间用空格隔开名称里不要带空格简介可以带空格读取时用%s处理名称用%[^\n]读简介剩余部分。字段示例在程序中的用途code1命令输入后转换数组下标name南门列表展示和路径输出desc学校正门校车起点queryInfo查询时打印2.3 读取 VexType.txt 的完整函数loadVexes是程序启动后第一个被调用的函数。它负责打开文件、按行解析、初始化邻接矩阵。一个能直接跑的版本是这样int loadVexes(Graph *G) { FILE *fp fopen(VexType.txt, r); if (fp NULL) { printf(配置文件缺失请检查 VexType.txt\n); return 0; } int idx 0; while (fscanf(fp, %d %s %[^\n], G-vexs[idx].code, G-vexs[idx].name, G-vexs[idx].desc) 3) { idx; if (idx MAXVEX) { printf(景点数超过 MAXVEX\n); break; } } fclose(fp); G-vexNum idx; for (int i 0; i G-vexNum; i) { for (int j 0; j G-vexNum; j) { if (i j) G-edge[i][j] 0; else G-edge[i][j] INF; } } return G-vexNum; }fscanf返回 3 表示这一行三个字段都成功读入。%d跳过空白读取编号%s读到空格停止%[^\n]把这一行剩余内容全部读进 desc。MAXVEX宏定义的是最大顶点数量数据文件超过 30 行就停止载入防止越界。初始化邻接矩阵时对角线置 0其余置INF这一步即使后面手动加边也不能跳过否则矩阵里残留的是未初始化的垃圾值。另一种常见写法是用fgets读一行再用sscanf解析。区别在于fgets能够限制每行最大长度避免简介过长导致缓冲区溢出fscanf写法短但要求数据文件格式非常规整。课程设计的数据量小我更推荐fgets版本因为答辩老师经常会问“简介超长怎么办”能答出缓冲区边界就是加分项。2.4 文件缺失、重复编号、边表初始化的坑第一个坑是文件编码。VexType.txt在 Windows 里必须存成 ANSI/GBK程序编译时也用 GBK才能显示正常中文。如果文件带了 UTF-8 BOMfscanf读到的第一个编号前面会有 BOM 字节%d解析失败函数直接返回 0程序也就认为没有景点。第二个坑是重复编号。10 个景点如果编号不连续或者出现两个code3Dijkstra 里的code-1下标就会错位。常见做法是加载时检查G-vexs[i].code ! i1不相等就提示数据文件格式有问题让用户修正后再运行。第三个坑是边表没有独立文件而是直接写在代码里比如addEdge(0, 1, 500);表示景点 0 到 1 相距 500 米。因为是无向图必须在函数里同时给edge[u][v]和edge[v][u]赋值。漏掉一个路径查询就会出现“去得了回不来”的现象。把边补全后图的准备阶段才算完成。3. 查询与最短路径命令解析和 Dijkstra 的 C 语言实现数据层把图建好接下来就是导游系统真正要交的两个功能景点信息查询和问路查询。景点信息查询本质是数组遍历问路查询才是算法的重头戏。为了让老师能连续检验功能我用一个 while 循环把菜单和两个查询串起来。3.1 菜单循环和命令解析怎么写课程设计不要求图形界面所以命令入口做得越直接越好。main函数里先调用loadVexes然后进入menu循环用整数选项区分功能。下面是命令分发的代码void menu(Graph *G) { int op; do { printf(1-查景点信息 2-问路查询 3-列出全部景点 0-退出\n); printf(请输入命令); scanf(%d, op); switch (op) { case 1: queryInfo(G); break; case 2: queryPath(G); break; case 3: listVexs(G); break; case 0: printf(退出系统\n); break; default: printf(无效命令请重新输入\n); break; } } while (op ! 0); }scanf(%d, op)会自动跳过前导空格和换行所以用户敲完数字加回车没有副作用。queryInfo和queryPath都接收Graph*因为访问G-vexs和G-edge都需要传入指针。listVexs遍历顶点数组打印全部景点这个功能不是题目硬性要求但放在菜单里能让老师快速看到 10 个景点都被VexType.txt正确加载了。命令解析也可以改成字符串版本比如输入path 3 7。scanf(%d)胜在简单缺点是没法支持“按中文名查询”。如果你想扩展成名称查询可以换成fgets读整行再用sscanf把命令和参数拆出来。3.2 为什么选 Dijkstra 而不是 Floyd题目要求查询任意两个景点之间的一条最短简单路径这有两个现成算法可选Dijkstra 和 Floyd。Dijkstra 是单源最短路径复杂度 O(n²)每次查询重新跑一遍Floyd 是任意点对最短路径复杂度 O(n³)跑完之后任意两点距离直接查表。10 个景点用 Floyd 也只做上千次基础运算两个都能接受。我选择 Dijkstra 的原因有三个第一课程设计要求输出路径Dijkstra 只要维护一维pre前驱数组就能回溯Floyd 要维护二维path矩阵理解成本高第二Dijkstra 是数据结构课程的核心考点答辩时老师更容易顺着这个思路提问你能接一句“用堆优化可以降到 O(n log n)”就是额外亮点第三这个场景是偶发性的两点查询不是高频查询Floyd 预计算的优势发挥不出来。3.3 Dijkstra 实现和路径回溯代码Dijkstra 函数我写成dijkstra(G, start, end)start 和 end 都是数组下标。函数内部用三个一维数组dist存起点到各点最短距离pre存路径前驱used标记顶点是否已经确定最短距离void dijkstra(Graph *G, int start, int end) { int dist[MAXVEX], pre[MAXVEX], used[MAXVEX] {0}; for (int i 0; i G-vexNum; i) { dist[i] G-edge[start][i]; pre[i] start; } used[start] 1; for (int k 0; k G-vexNum; k) { int min INF, u -1; for (int i 0; i G-vexNum; i) { if (!used[i] dist[i] min) { min dist[i]; u i; } } if (u -1) break; used[u] 1; for (int v 0; v G-vexNum; v) { if (!used[v] G-edge[u][v] ! INF dist[u] G-edge[u][v] dist[v]) { dist[v] dist[u] G-edge[u][v]; pre[v] u; } } } if (dist[end] INF) { printf(两个景点之间没有连通路径\n); return; } int path[MAXVEX], cnt 0; for (int v end; v ! start; v pre[v]) { path[cnt] v; if (cnt G-vexNum) break; } path[cnt] start; printf(最短距离: %d 米\n, dist[end]); for (int i cnt - 1; i 0; i--) { printf(%s, G-vexs[path[i]].name); if (i 0) printf( - ); } printf(\n); }这段代码先初始化dist[i]为起点到 i 的直连距离所有点的前驱暂时记为 start。外层循环每次从没有确定距离的点里找dist最小的 u把它加入已确定集合然后用 u 松弛邻接点。松弛条件有两个v 未确定且edge[u][v]不是 INF避免把不可达边当成 0 参与计算。路径回溯从终点倒着查找 pre直到回到 start存进 path 数组后再逆序输出这样打印顺序就是从起点到终点。下面这几个变量是答辩时最容易问到的参数作用关键细节dist[]起点到各个景点的当前最短距离初始为直连距离松弛时更新pre[]记录每个景点的前驱最后用来回溯完整路径used[]标记景点是否已确定最短距离避免重复选择和死循环start/end查询的起止下标用户输入的编号减 1INF不可达标志不能参与更新运算注意path数组和pre的配合如果 end 不可达dist[end]还是 INF我会先判断并返回避免 path 回溯时停在不可靠的位置。另一个细节是pre[i]初始化为 start如果 start 和 end 之间根本没有路径回溯循环也会在 start 停下来但结果不对所以不可达判断必须放在输出之前。3.4 Dijkstra 的复杂度与答辩扩展这个版本的复杂度是 O(n²)两层循环各执行 n 次。n10 时只有 100 次运算人眼几乎看不出耗时。如果数据量从 10 变成 1000O(n²) 是百万级仍然可以接受但如果到 10 万顶点就必须用优先队列做堆优化把找最小 dist 的步骤从 O(n) 降到 O(log n)。课程设计里我不建议直接写堆优化代码超过 50 行就不再是老师想看的重点。答辩时主动提一句“这个版本没有做堆优化因为 n 很小”反而能证明你清楚复杂度边界。还要考虑输入边界用户输入景点编号为 0 或负数时queryPath里如果直接拿code-1访问数组会越界。常见做法是 input 后判断code 1 || code G-vexNum越界就提示重新输入。起点等于终点时直接输出景点名称和 0 距离不需要进入 Dijkstra。4. 交互与控制台输入中文化环境下的 VC 6.0 适配与运行这段代码在 Visual Studio Code 里写最后要拿到学校机房的 VC 6.0 编译。很多课程设计不是算法错而是环境问题导致运行不了。这一章把编码、中文输入、exe 运行三个环节的细节拆开讲。4.1 UTF-8 源码在 VC 6.0 编译器里的编码问题VC 6.0 默认按系统 ANSI 代码页读源文件Windows 中文版就是 GBK。VSCode 默认保存 UTF-8两个一冲突源文件里的中文字符串在编译阶段就变成乱码运行后printf输出的也是乱码。解决办法是在 VSCode 右下角点击编码选择“通过编码保存”改成 GBK。保存后可以先用记事本打开确认中文不是乱码再放进 VC 6.0。如果希望保留一份 UTF-8 源码可以把文件结构改成两个目录src放便于阅读的 UTF-8 版compile放 GBK 版提供编译。这道工序对成绩没有直接作用但在换电脑编辑、后续维护时非常实用。4.2 VC 6.0 控制台无法输入中文的规避资源说明里提到VC 6.0 自带的控制台运行器无法输入中文。这不是scanf的毛病而是 VC 6.0 的宿主进程对中文输入法支持不好。最简单的方法是不在 VC 6.0 里按 CtrlF5而是直接到 release 目录双击已经编译好的 exeWindows 10 的 cmd 窗口可以正常接收中文。如果必须从 IDE 里启动可以在程序开头加上本地化设置#include locale.h int main() { setlocale(LC_ALL, .936); Graph G; if (loadVexes(G) 0) { return 1; } menu(G); return 0; }.936是 Windows 简体中文字符集代码页等价于 GBK 环境。setlocale告诉 CRT 当前采用适合中文的本地化设置让printf的输出正常转换到控制台代码页scanf接收输入时也不容易丢字节。如果编译器支持zh_CN.GBK这种名称也可以替换但在 Windows 环境下写.936最稳妥。4.3 运行交互流程和实际命令编译后双击 exe程序先加载VexType.txt然后进入菜单。我习惯在loadVexes后打印一行“加载 10 个景点完成”这样一眼就能判断文件是否被正确读取。实际交互过程看起来是这样加载 10 个景点完成 1-查景点信息 2-问路查询 3-列出全部景点 0-退出 请输入命令1 景点编号3 南门学校正门校车起点出门右转是地铁站。这里“命令 1”和“景点编号 3”都用%d读取中间换行会被自动跳过所以不会出现输入卡住。查询一次后回到菜单方便连续操作。如果输入 0do-while 退出main 函数返回。运行中几个常遇到的故障从现象到原因可以对照这张表现象原因对策双击 exe 闪退VexType.txt不在 exe 同目录把 txt 和 exe 放同一目录中文显示乱码编译后的源文件编码不是 GBK在 VSCode 中改 ANSI 后重新编译IDE 调试时无法输入中文VC 6.0 控制台运行器限制直接运行 exe或加setlocale加载景点数为 0文件带 BOM 或字段格式错误用记事本另存为 ANSI 编码4.4 从源码到 exe 的整理思路资源里有一批1.png、2.png这样的运行截图截图配合 README 可以按“提交版”归档校园导游.cpp、VexType.txt、README.md放在同一目录。源码包里没有看到现成 exe拿到代码的人需要自己编译。用 VC 6.0 新建空工程把 cpp 添加进去编译即可如果本机装的是 MinGW也可以执行gcc 校园导游.cpp -o 校园导游.exe但前提仍是源文件保存为 GBK 编码否则中文字符串会乱码。5. 换学校换数据时怎么改从邻接矩阵到可配置的代码调整5.1 增加景点时要不要改结构体10 个景点是最低要求很多学校的实际景点会更多。增加景点时先改MAXVEX再把VexType.txt的景点行补全。路径边表如果继续写在addEdge里必须保证参数是景点加载后的数组下标不能直接用 code。比如addEdge(0, 1, 500)对应的是代号 1 和 2如果你在 txt 里把 1 号景点的 code 改成 100code-1仍然能得到下标 0但边表传参写 0 就必须和 code 保持一致。最稳妥的做法是在addEdge调用处写清楚注释注明“第三个景点到第五个景点”。5.2 把边表也放进文件的改造不让老师改代码就能换校园地图是把这个作业从“写死”变成“可配置”的关键一步。常见做法是在loadVexes之后调用loadEdgesEdge.txt每行存u v wvoid loadEdges(Graph *G) { FILE *fp fopen(Edge.txt, r); if (fp NULL) { printf(未找到 Edge.txt跳过边加载\n); return; } int u, v, w; while (fscanf(fp, %d %d %d, u, v, w) 3) { if (u 1 v 1 u G-vexNum v G-vexNum) { G-edge[u-1][v-1] w; G-edge[v-1][u-1] w; } } fclose(fp); printf(边数据加载完成\n); }这段代码把Edge.txt里的景点编号减 1 后写入邻接矩阵同时写入对称位置保证无向图两个方向距离一致。加载边之前矩阵必须在loadVexes中被初始化为 INF。Edge.txt缺失时直接跳过不影响景点信息查询但路径查询会全部返回不可达所以打印“跳过边加载”这段日志比直接崩溃更容易排查。5.3 支持中文景点名查询的一个小改法菜单里的 2 号命令目前用编号输入。想改成直接输入中文名称比如“图书馆”只需要在queryPath里加一次遍历用strcmp(用户输入, G-vexs[i].name)找到对应下标。如果想做模糊匹配改用strncmp(input, G-vexs[i].name, strlen(input)) 0只匹配用户输入的前缀不用完整名称。改完这一处查询入口就同时支持编号和中文名了。本文还有配套的精品资源点击获取 C语言实现校园导游系统：图存储与Dijkstra算法详解
简介一套面向数据结构课程设计的校园导游系统C语言实现适合需要完成图论相关课设、并希望获得高分参考的计算机专业学生。程序以校园平面图为背景用顶点表示景点、边表示路径支持不少于10个景点的信息查询以及任意两个景点间最短简单路径的问路查询可作为图存储、遍历与最短路径算法的综合实践范例。资源包共10个文件以cpp源码为核心配有多张程序运行截图、景点数据文本以及readme说明文档整体仅409KB结构简洁便于直接查阅和调试。该项目代码已通过运行测试答辩评审平均分94.5分目前已有313人浏览学习。下载后可以获得完整可运行源码、界面效果图和配套说明适合快速理解实现思路并用于自己的课程设计或复习参考。1. 为什么校园导游系统要先画图再写代码——从 10 个景点的无向带权图说起我拆这份DataStructure-curriculum-design-master.zip之前以为 95 分的高分课程设计一定有复杂的界面。解压后才发现源码只有一个校园导游.cpp配合VexType.txt和几张运行截图。再看题目要求景点不少于 10 个边存路径长度查询任意两个景点之间的最短简单路径——这不是界面题是一道完整的图论应用题。程序的核心价值在于用邻接矩阵表达校园地图、把景点数据和路径数据分离、再用 Dijkstra 完成问路查询。对正在做数据结构课程设计的人这套代码最大的学习点是小数据量下怎样用最克制的 C 语言写法把图的建立、查询、最短路径一次讲清楚。2. 数据层C 语言里的景点结构体与 VexType.txt 加载实现源码文件只有一个校园导游.cpp却专门放了一个VexType.txt说明数据与算法是分开的。这是作业第一个得分点没有把 10 个景点的信息硬编码在 main 里而是让程序从文本文件加载。看起来多了一步文件操作但换来的是改景点名称不用重新编译。下面先讲清楚顶点和边到底用什么结构组织。2.1 10 个景点其实不适合用邻接表邻接矩阵更稳题目要求景点不少于 10 个这个数量级决定了存储方式。10 个顶点的无向图最多 45 条边属于典型稀疏图从理论上讲邻接表更省空间。但在 C 语言课程设计里省这点空间没有实际意义10×10 的 int 邻接矩阵只有 400 字节而邻接表还要动态分配结点、管理链表指针。重点不是空间而是 Dijkstra 实现时邻接矩阵可以 O(1) 取edge[u][v]路径回溯也只需要借助pre数组。我一般看到 20 个以内的景点都优先选邻接矩阵等数据量到几百再考虑邻接表或链式前向星。2.2 顶点结构体、图结构体、边的存储景点信息包括代号、名称、简介正好对应一个结构体。图则把顶点数组和邻接矩阵包在一起。这个项目没有单独拆VexType.h所有定义都放在校园导游.cpp顶部这也是单文件课程设计的常见风格。一个能跑起来的设计通常长这样#define MAXVEX 30 #define INF 0x3f3f3f3f typedef struct { int code; // 景点代号如 1 char name[30]; // 景点名称 char desc[200]; // 景点简介 } VexType; typedef struct { VexType vexs[MAXVEX]; // 顶点数组 int edge[MAXVEX][MAXVEX]; // 邻接矩阵 int vexNum, edgeNum; // 实际顶点数和边数 } Graph;code对应VexType.txt里的景点代号查询时用户输入的就是它name用于路径输出desc存简介。edge[i][j]表示第 i 个景点到第 j 个景点的路径长度不可达时填INF。INF用0x3f3f3f3f而不是 9999是因为这个值做加法不容易超过 int 上限而且 memset 按字节填充也很方便。VexType.txt最常用的格式是每行编号 名称 简介三段中间用空格隔开名称里不要带空格简介可以带空格读取时用%s处理名称用%[^\n]读简介剩余部分。字段示例在程序中的用途code1命令输入后转换数组下标name南门列表展示和路径输出desc学校正门校车起点queryInfo查询时打印2.3 读取 VexType.txt 的完整函数loadVexes是程序启动后第一个被调用的函数。它负责打开文件、按行解析、初始化邻接矩阵。一个能直接跑的版本是这样int loadVexes(Graph *G) { FILE *fp fopen(VexType.txt, r); if (fp NULL) { printf(配置文件缺失请检查 VexType.txt\n); return 0; } int idx 0; while (fscanf(fp, %d %s %[^\n], G-vexs[idx].code, G-vexs[idx].name, G-vexs[idx].desc) 3) { idx; if (idx MAXVEX) { printf(景点数超过 MAXVEX\n); break; } } fclose(fp); G-vexNum idx; for (int i 0; i G-vexNum; i) { for (int j 0; j G-vexNum; j) { if (i j) G-edge[i][j] 0; else G-edge[i][j] INF; } } return G-vexNum; }fscanf返回 3 表示这一行三个字段都成功读入。%d跳过空白读取编号%s读到空格停止%[^\n]把这一行剩余内容全部读进 desc。MAXVEX宏定义的是最大顶点数量数据文件超过 30 行就停止载入防止越界。初始化邻接矩阵时对角线置 0其余置INF这一步即使后面手动加边也不能跳过否则矩阵里残留的是未初始化的垃圾值。另一种常见写法是用fgets读一行再用sscanf解析。区别在于fgets能够限制每行最大长度避免简介过长导致缓冲区溢出fscanf写法短但要求数据文件格式非常规整。课程设计的数据量小我更推荐fgets版本因为答辩老师经常会问“简介超长怎么办”能答出缓冲区边界就是加分项。2.4 文件缺失、重复编号、边表初始化的坑第一个坑是文件编码。VexType.txt在 Windows 里必须存成 ANSI/GBK程序编译时也用 GBK才能显示正常中文。如果文件带了 UTF-8 BOMfscanf读到的第一个编号前面会有 BOM 字节%d解析失败函数直接返回 0程序也就认为没有景点。第二个坑是重复编号。10 个景点如果编号不连续或者出现两个code3Dijkstra 里的code-1下标就会错位。常见做法是加载时检查G-vexs[i].code ! i1不相等就提示数据文件格式有问题让用户修正后再运行。第三个坑是边表没有独立文件而是直接写在代码里比如addEdge(0, 1, 500);表示景点 0 到 1 相距 500 米。因为是无向图必须在函数里同时给edge[u][v]和edge[v][u]赋值。漏掉一个路径查询就会出现“去得了回不来”的现象。把边补全后图的准备阶段才算完成。3. 查询与最短路径命令解析和 Dijkstra 的 C 语言实现数据层把图建好接下来就是导游系统真正要交的两个功能景点信息查询和问路查询。景点信息查询本质是数组遍历问路查询才是算法的重头戏。为了让老师能连续检验功能我用一个 while 循环把菜单和两个查询串起来。3.1 菜单循环和命令解析怎么写课程设计不要求图形界面所以命令入口做得越直接越好。main函数里先调用loadVexes然后进入menu循环用整数选项区分功能。下面是命令分发的代码void menu(Graph *G) { int op; do { printf(1-查景点信息 2-问路查询 3-列出全部景点 0-退出\n); printf(请输入命令); scanf(%d, op); switch (op) { case 1: queryInfo(G); break; case 2: queryPath(G); break; case 3: listVexs(G); break; case 0: printf(退出系统\n); break; default: printf(无效命令请重新输入\n); break; } } while (op ! 0); }scanf(%d, op)会自动跳过前导空格和换行所以用户敲完数字加回车没有副作用。queryInfo和queryPath都接收Graph*因为访问G-vexs和G-edge都需要传入指针。listVexs遍历顶点数组打印全部景点这个功能不是题目硬性要求但放在菜单里能让老师快速看到 10 个景点都被VexType.txt正确加载了。命令解析也可以改成字符串版本比如输入path 3 7。scanf(%d)胜在简单缺点是没法支持“按中文名查询”。如果你想扩展成名称查询可以换成fgets读整行再用sscanf把命令和参数拆出来。3.2 为什么选 Dijkstra 而不是 Floyd题目要求查询任意两个景点之间的一条最短简单路径这有两个现成算法可选Dijkstra 和 Floyd。Dijkstra 是单源最短路径复杂度 O(n²)每次查询重新跑一遍Floyd 是任意点对最短路径复杂度 O(n³)跑完之后任意两点距离直接查表。10 个景点用 Floyd 也只做上千次基础运算两个都能接受。我选择 Dijkstra 的原因有三个第一课程设计要求输出路径Dijkstra 只要维护一维pre前驱数组就能回溯Floyd 要维护二维path矩阵理解成本高第二Dijkstra 是数据结构课程的核心考点答辩时老师更容易顺着这个思路提问你能接一句“用堆优化可以降到 O(n log n)”就是额外亮点第三这个场景是偶发性的两点查询不是高频查询Floyd 预计算的优势发挥不出来。3.3 Dijkstra 实现和路径回溯代码Dijkstra 函数我写成dijkstra(G, start, end)start 和 end 都是数组下标。函数内部用三个一维数组dist存起点到各点最短距离pre存路径前驱used标记顶点是否已经确定最短距离void dijkstra(Graph *G, int start, int end) { int dist[MAXVEX], pre[MAXVEX], used[MAXVEX] {0}; for (int i 0; i G-vexNum; i) { dist[i] G-edge[start][i]; pre[i] start; } used[start] 1; for (int k 0; k G-vexNum; k) { int min INF, u -1; for (int i 0; i G-vexNum; i) { if (!used[i] dist[i] min) { min dist[i]; u i; } } if (u -1) break; used[u] 1; for (int v 0; v G-vexNum; v) { if (!used[v] G-edge[u][v] ! INF dist[u] G-edge[u][v] dist[v]) { dist[v] dist[u] G-edge[u][v]; pre[v] u; } } } if (dist[end] INF) { printf(两个景点之间没有连通路径\n); return; } int path[MAXVEX], cnt 0; for (int v end; v ! start; v pre[v]) { path[cnt] v; if (cnt G-vexNum) break; } path[cnt] start; printf(最短距离: %d 米\n, dist[end]); for (int i cnt - 1; i 0; i--) { printf(%s, G-vexs[path[i]].name); if (i 0) printf( - ); } printf(\n); }这段代码先初始化dist[i]为起点到 i 的直连距离所有点的前驱暂时记为 start。外层循环每次从没有确定距离的点里找dist最小的 u把它加入已确定集合然后用 u 松弛邻接点。松弛条件有两个v 未确定且edge[u][v]不是 INF避免把不可达边当成 0 参与计算。路径回溯从终点倒着查找 pre直到回到 start存进 path 数组后再逆序输出这样打印顺序就是从起点到终点。下面这几个变量是答辩时最容易问到的参数作用关键细节dist[]起点到各个景点的当前最短距离初始为直连距离松弛时更新pre[]记录每个景点的前驱最后用来回溯完整路径used[]标记景点是否已确定最短距离避免重复选择和死循环start/end查询的起止下标用户输入的编号减 1INF不可达标志不能参与更新运算注意path数组和pre的配合如果 end 不可达dist[end]还是 INF我会先判断并返回避免 path 回溯时停在不可靠的位置。另一个细节是pre[i]初始化为 start如果 start 和 end 之间根本没有路径回溯循环也会在 start 停下来但结果不对所以不可达判断必须放在输出之前。3.4 Dijkstra 的复杂度与答辩扩展这个版本的复杂度是 O(n²)两层循环各执行 n 次。n10 时只有 100 次运算人眼几乎看不出耗时。如果数据量从 10 变成 1000O(n²) 是百万级仍然可以接受但如果到 10 万顶点就必须用优先队列做堆优化把找最小 dist 的步骤从 O(n) 降到 O(log n)。课程设计里我不建议直接写堆优化代码超过 50 行就不再是老师想看的重点。答辩时主动提一句“这个版本没有做堆优化因为 n 很小”反而能证明你清楚复杂度边界。还要考虑输入边界用户输入景点编号为 0 或负数时queryPath里如果直接拿code-1访问数组会越界。常见做法是 input 后判断code 1 || code G-vexNum越界就提示重新输入。起点等于终点时直接输出景点名称和 0 距离不需要进入 Dijkstra。4. 交互与控制台输入中文化环境下的 VC 6.0 适配与运行这段代码在 Visual Studio Code 里写最后要拿到学校机房的 VC 6.0 编译。很多课程设计不是算法错而是环境问题导致运行不了。这一章把编码、中文输入、exe 运行三个环节的细节拆开讲。4.1 UTF-8 源码在 VC 6.0 编译器里的编码问题VC 6.0 默认按系统 ANSI 代码页读源文件Windows 中文版就是 GBK。VSCode 默认保存 UTF-8两个一冲突源文件里的中文字符串在编译阶段就变成乱码运行后printf输出的也是乱码。解决办法是在 VSCode 右下角点击编码选择“通过编码保存”改成 GBK。保存后可以先用记事本打开确认中文不是乱码再放进 VC 6.0。如果希望保留一份 UTF-8 源码可以把文件结构改成两个目录src放便于阅读的 UTF-8 版compile放 GBK 版提供编译。这道工序对成绩没有直接作用但在换电脑编辑、后续维护时非常实用。4.2 VC 6.0 控制台无法输入中文的规避资源说明里提到VC 6.0 自带的控制台运行器无法输入中文。这不是scanf的毛病而是 VC 6.0 的宿主进程对中文输入法支持不好。最简单的方法是不在 VC 6.0 里按 CtrlF5而是直接到 release 目录双击已经编译好的 exeWindows 10 的 cmd 窗口可以正常接收中文。如果必须从 IDE 里启动可以在程序开头加上本地化设置#include locale.h int main() { setlocale(LC_ALL, .936); Graph G; if (loadVexes(G) 0) { return 1; } menu(G); return 0; }.936是 Windows 简体中文字符集代码页等价于 GBK 环境。setlocale告诉 CRT 当前采用适合中文的本地化设置让printf的输出正常转换到控制台代码页scanf接收输入时也不容易丢字节。如果编译器支持zh_CN.GBK这种名称也可以替换但在 Windows 环境下写.936最稳妥。4.3 运行交互流程和实际命令编译后双击 exe程序先加载VexType.txt然后进入菜单。我习惯在loadVexes后打印一行“加载 10 个景点完成”这样一眼就能判断文件是否被正确读取。实际交互过程看起来是这样加载 10 个景点完成 1-查景点信息 2-问路查询 3-列出全部景点 0-退出 请输入命令1 景点编号3 南门学校正门校车起点出门右转是地铁站。这里“命令 1”和“景点编号 3”都用%d读取中间换行会被自动跳过所以不会出现输入卡住。查询一次后回到菜单方便连续操作。如果输入 0do-while 退出main 函数返回。运行中几个常遇到的故障从现象到原因可以对照这张表现象原因对策双击 exe 闪退VexType.txt不在 exe 同目录把 txt 和 exe 放同一目录中文显示乱码编译后的源文件编码不是 GBK在 VSCode 中改 ANSI 后重新编译IDE 调试时无法输入中文VC 6.0 控制台运行器限制直接运行 exe或加setlocale加载景点数为 0文件带 BOM 或字段格式错误用记事本另存为 ANSI 编码4.4 从源码到 exe 的整理思路资源里有一批1.png、2.png这样的运行截图截图配合 README 可以按“提交版”归档校园导游.cpp、VexType.txt、README.md放在同一目录。源码包里没有看到现成 exe拿到代码的人需要自己编译。用 VC 6.0 新建空工程把 cpp 添加进去编译即可如果本机装的是 MinGW也可以执行gcc 校园导游.cpp -o 校园导游.exe但前提仍是源文件保存为 GBK 编码否则中文字符串会乱码。5. 换学校换数据时怎么改从邻接矩阵到可配置的代码调整5.1 增加景点时要不要改结构体10 个景点是最低要求很多学校的实际景点会更多。增加景点时先改MAXVEX再把VexType.txt的景点行补全。路径边表如果继续写在addEdge里必须保证参数是景点加载后的数组下标不能直接用 code。比如addEdge(0, 1, 500)对应的是代号 1 和 2如果你在 txt 里把 1 号景点的 code 改成 100code-1仍然能得到下标 0但边表传参写 0 就必须和 code 保持一致。最稳妥的做法是在addEdge调用处写清楚注释注明“第三个景点到第五个景点”。5.2 把边表也放进文件的改造不让老师改代码就能换校园地图是把这个作业从“写死”变成“可配置”的关键一步。常见做法是在loadVexes之后调用loadEdgesEdge.txt每行存u v wvoid loadEdges(Graph *G) { FILE *fp fopen(Edge.txt, r); if (fp NULL) { printf(未找到 Edge.txt跳过边加载\n); return; } int u, v, w; while (fscanf(fp, %d %d %d, u, v, w) 3) { if (u 1 v 1 u G-vexNum v G-vexNum) { G-edge[u-1][v-1] w; G-edge[v-1][u-1] w; } } fclose(fp); printf(边数据加载完成\n); }这段代码把Edge.txt里的景点编号减 1 后写入邻接矩阵同时写入对称位置保证无向图两个方向距离一致。加载边之前矩阵必须在loadVexes中被初始化为 INF。Edge.txt缺失时直接跳过不影响景点信息查询但路径查询会全部返回不可达所以打印“跳过边加载”这段日志比直接崩溃更容易排查。5.3 支持中文景点名查询的一个小改法菜单里的 2 号命令目前用编号输入。想改成直接输入中文名称比如“图书馆”只需要在queryPath里加一次遍历用strcmp(用户输入, G-vexs[i].name)找到对应下标。如果想做模糊匹配改用strncmp(input, G-vexs[i].name, strlen(input)) 0只匹配用户输入的前缀不用完整名称。改完这一处查询入口就同时支持编号和中文名了。本文还有配套的精品资源点击获取