校园导航系统课程设计：邻接矩阵与Floyd最短路径骨架-北京尧图网络

简介这份《数据结构课程设计-校园导航系统》文档面向计算机相关专业学生及需要完成图结构课程设计的读者围绕校园景点查询与任意两点间最短路径问题展开。内容以C语言实现为主线涵盖图的邻接矩阵存储、景点与道路信息结构体设计、Floyd算法求最短路径、系统调试测试及时间复杂度分析等关键环节并给出源程序清单与执行结果。压缩包内共1个doc文件大小约187KB按任务书、详细设计、调试与测试、总结、致谢和参考文献组织可作为课程设计报告模板与算法实现参考。已有67人学习适合希望对照完整报告结构、梳理图算法实现思路并查漏补缺的读者。1. 校园导航系统一份课程设计里藏着图论落地的完整骨架十来个景点、二十几条路游客站在校门口问一句「去图书馆怎么走最近」背后就是一张带权无向图和一次全源最短路计算。这份《数据结构课程设计-校园导航系统》要解决的就是这类问题把校园平面图抽象成图景点是顶点道路是带权边然后提供两个最朴素也最实用的能力——查景点信息、查任意两点间的最短路径。它适合正在做数据结构课程设计、想把邻接矩阵和 Floyd 算法真正跑通一遍的开发者也适合想拿一个干净的小型 C 项目练手图结构建模的人。代码量不大但「建模—存储—算法—交互」这条链路是完整的拆明白这一套后面换成地铁导航、景区导览、仓库拣货路径骨架不用重写。2. 技术选型与数据结构建模为什么是邻接矩阵加 Floyd2.1 三个核心结构体撑起整个模型这个项目没有用什么框架纯 C 语言加标准库编译依赖只有stdio.h、string.h、malloc.h。选型上有一个很明确的判断校园景点数量在十几个这个量级属于典型的小规模稠密图那么存储结构用邻接矩阵比邻接表更划算——判边存在性是 O(1)Floyd 算法本身也天然吃矩阵。要是换成上千个节点的稀疏图邻接矩阵的 O(n²) 空间就该翻车了那时候得上邻接表配 Dijkstra 加堆优化。模型被拆成三层每层一个结构体职责划得很清楚#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; // 建图用的边描述避免在 main 里手写矩阵 typedef struct { int row; int col; int weight; } RowColWeight;DataType是业务层SeqList是顶点容器AdjMGraph是图的整体。这么分层的好处是查询景点信息时只需要扫vertices完全不碰边矩阵算路径时只吃Edge跟简介文本无关。MaxWeight 1000这个常量是个关键约定矩阵里凡是 1000 的位置都视为「没有直接道路」Floyd 的松弛判断依赖它做加法时不会误判成一条真实可走的短边。RowColWeight这个中间结构容易被忽略但它解决了一个很实际的痛点。二十八条边如果直接在main里写G.Edge[0][1] 20; G.Edge[1][0] 20;这样一对对赋值写起来啰嗦还极容易漏掉对称项。用{row, col, weight}三元组数组描述建图函数里统一处理双向赋值出错面小很多。2.2 建图函数把三元组数组灌进矩阵建图这段代码原报告里没贴全作者说「书上已经出现过」但逻辑很直白按这个场景的常见做法补出来大概是这样void Creat(AdjMGraph *G, DataType v[], RowColWeight rcw[], int n, int e) { int i, j; // 1. 顶点表初始化 for (i 0; i n; i) { G-vertices.list[i] v[i]; } G-vertices.size n; G-numOfEdge e; // 2. 边矩阵先全部置为「不通」 for (i 0; i n; i) { for (j 0; j n; j) { G-Edge[i][j] MaxWeight; } } // 3. 按三元组写入边权注意无向图要对称赋值 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; } }四个参数各管一件事v[]是景点数组rcw[]是边数组n是景点数e是边数。第 2 步的初始化不能省——C 的二维数组不会自动填 1000不初始化就是一堆随机值Floyd 跑出来的结果会非常玄学这是新手最容易栽的第一个坑。第 3 步的双向赋值对应无向图语义只写一半的话从 A 到 B 有路、从 B 到 A 没路问路功能直接就废了。调用侧的样子从原程序里能看清数据规模int n 10, e 28; // 10 个景点28 条边 Creat(G, a, rcw, n, e);十个景点、二十八条边平均每个节点度数 5.6是稠密图邻接矩阵的空间利用率其实不低选型站得住。2.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\n, G.vertices.list[i].introduction); break; } } // 循环走完还没 break说明没找到 if (i G.vertices.size) { printf(您所查询的景点不在我们所提供的范围内\n\n); } }入口参数是整张图加一个景点名字符串出口没有返回值直接打印。时间复杂度 O(n)空间 O(1)。这里有个很常见的写法技巧for循环变量i提到循环外声明循环结束后用i size判断是否命中省掉一个flag变量。这个模式在 C 里很常见但要小心如果中途breaki停在命中位置如果自然结束i等于size。逻辑是对的前提是循环条件严格写成i size。字符串输入用scanf(%s, sceneryname)这就埋了一个隐患——景点名里但凡有空格输入会被截断。校园景点名一般没空格所以这个项目里侥幸没出问题换成「学生第二食堂」这种长名字char name[20]也够用但如果你要扩成英文名或加描述性后缀长度得重新算。3. 最短路径核心链路Floyd 三重循环与路径回溯3.1 Floyd 算法本体十九行代码的全部内容全篇技术含量最高的就是这个函数十九行没有一句废话void Floyd(int cost[][MaxVertices], int n, int weight[][MaxVertices], int path[][MaxVertices]) { int i, j, k; // 初始化weight 拷贝原边权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; // 记录中转点 } } } } }四个参数cost是原始邻接矩阵只读weight是输出的最短距离矩阵path是输出的中转点矩阵n是顶点数。三个输出矩阵都是MaxVertices × MaxVertices的定长二维数组传参时退化成指针所以必须显式带上第二维长度MaxVertices——这是 C 语言二维数组传参的硬性要求漏了编译不过。path矩阵的语义要嚼透path[i][j] -1表示 i 到 j 的最短路是直达的中间不经过任何点path[i][j] k表示 i 到 j 的最短路要经过 k。这个「记中转点」的存法比记完整路径省空间代价是回溯时要递归或迭代展开。复杂度 O(n³)n10 的时候是一千次内层判断可以忽略不计。但如果景点扩到 200 个就是八百万次每次查询都重跑一遍 Floyd 就很不划算了。合格的改法是建图后跑一次 Floyd把weight和path缓存成全局或挂在图结构上查询时直接查表。原程序的写法是在Path里每次查询都调Floyd对课程设计来说无所谓对真实系统来说是明显的性能债二次开发时第一个该改的就是这里。注意weight[i][k] weight[k][j]相加时如果两个都是MaxWeight 1000结果是 2000不会溢出int也不会小于任何真实边权真实边权最大也就几十所以不用额外判! MaxWeight。但如果你的无穷大常量取成了INT_MAX这里就会整型溢出成负数松弛判断直接失效。无穷大的取值必须小于INT_MAX / 2。3.2 路径回溯那段让作者调试半天的逻辑距离算出来容易把「A 经 B 经 C 到 D」这条链还原成人类可读的一行才是真正麻烦的地方。原程序里的Path函数就是干这个的void Path(AdjMGraph G, char sceneryname[], char sceneryname1[]) { int i, j -1, k -1, n, m, count 0; n G.vertices.size; int weight[MaxVertices][MaxVertices], path[MaxVertices][MaxVertices]; int value[MaxVertices]; // 暂存中转点序列 // 1. 名称 - 下标 for (i 0; i n; i) { if (strcmp(G.vertices.list[i].name, sceneryname) 0) j i; if (strcmp(G.vertices.list[i].name, sceneryname1) 0) k i; } // 2. 跑一次 Floyd Floyd(G.Edge, n, weight, path); m path[j][k]; printf(最短路径长度%d\n, weight[j][k]); // 3. 直达的情况 if (m -1) { printf(%s —— %s\n, sceneryname, sceneryname1); } else { // 4. 回溯不断找当前区间里的中转点收窄区间 while (m ! -1) { value[count] m; if (j k) k m; else j m; m path[j][k]; } // 5. 按方向输出 printf(从 %s 到 %s 的最短路径为\n, sceneryname, sceneryname1); printf(%s——, sceneryname); if (j k) { for (i count - 1; i 0; i--) printf(%s——, G.vertices.list[value[i]].name); } else { for (i 0; i count; i) printf(%s——, G.vertices.list[value[i]].name); } printf(%s\n, sceneryname1); } }逐段解释。第 1 步把两个景点名映射成矩阵下标j和k这里用的是「扫一遍线性表比对字符串」和前文的Information同构。注意j、k初始化为 -1如果用户输错名字两者保持 -1后面path[-1][k]就是数组越界——这是个真实存在的健壮性缺口原程序没处理我在下面避坑章节还会提。第 4 步是核心。m path[j][k]拿到 j 到 k 之间的一个中转点把它记进value然后把区间收窄如果j k说明中转点在 k 这一侧之前新的右端点变成m否则左端点变成m。再取新区间的中转点循环到m -1区间内直达为止。这样收下来的value数组顺序是从外往里所以第 5 步输出时要看方向决定正着遍历还是倒着遍历。作者在报告里专门写了一段正序输出正常逆序输出出问题最后定位到循环方向。这就是典型的「数据是对的渲染顺序错了」。血泪经验是——回溯出来的中间点序列天然是有方向的别指望一个 for 循环通吃两个方向先想清楚value里存的是从起点侧往中间收还是反过来再决定循环怎么写。3.3 输入校验与调试几个该补没补的地方Path里j、k可能为 -1 的风险随手补两行就能堵住if (j -1 || k -1) { printf(输入的景点名称有误请检查后重试。\n); return; } if (j k) { printf(起点和终点相同距离为 0。\n); return; }另外scanf(%s%s, sceneryname, sceneryname1)没限制宽度名字超过 19 字符就会写穿name[20]。正确写法是scanf(%19s%19s, ...)。这类问题在课程设计里通常不会暴露因为测试数据都是造好的但一旦用户手滑多打几个字符程序行为就不可预测了可能悄无声息地改掉边上数据表现为「同一个查询结果时对时错」——这种 bug 最难查因为现象不像崩溃那么显眼。调试阶段建议开一个临时的打印函数把weight矩阵整个打出来核对void DumpMatrix(int m[][MaxVertices], int n) { for (int i 0; i n; i) { for (int j 0; j n; j) printf(%5d, m[i][j]); printf(\n); } }建图完之后打一次确认对角线是 0如果初始化为 0、对称位置相等、不通的位置都是 1000。Floyd 跑完再打一次检查weight[i][j] weight[j][i]无向图必对称以及三角不等式是否满足。这三条检查几乎是免费的能拦掉八成的数据层错误比在输出结果上瞎猜高效得多。4. 编译运行与工程组织六个头文件怎么串起来4.1 文件划分与依赖顺序原报告列了六个文件各管一摊文件职责被谁包含school.cpp主文件构造数据、调Creat、进菜单无SeqList.h顺序表结构与基本操作AdjMGraph.hAdjMGraph.h图结构体定义、图基本操作AdjMGraphCreat.hAdjMGraphCreat.hCreat建图函数school.cppFloyd.hFloyd 算法实现school.cppInquiry.hInformation与Path两个查询函数school.cppOperation.h菜单、Information1、Path1包装school.cpp这里有个依赖顺序的坑Inquiry.h里的函数签名用到了AdjMGraph类型所以它必须排在AdjMGraph.h之后被包含Operation.h里又调用了Inquiry.h的函数和全局变量G所以它必须放在最后。原程序的包含顺序正是这么排的#include stdio.h #include string.h #include malloc.h #define MaxSize 20 #define MaxVertices 20 #define MaxWeight 1000 #include Floyd.h #include AdjMGraphCreat.h #include Inquiry.h AdjMGraph G; // 全局图对象供各模块共享 #include Operation.h // 依赖 G必须放最后注意AdjMGraph G;这行的位置——它夹在两组 include 之间因为它必须在AdjMGraph.h被AdjMGraphCreat.h间接引入之后声明又要在Operation.h使用了G之前存在。这种夹心写法能跑但非常脆你一旦调整 include 顺序就会连环报错。更稳的做法是给AdjMGraph.h加 include guard把G改成extern声明放在头文件、定义放在school.cpp。4.2 编译命令与运行流程纯 C 代码没有图形库依赖任何主流编译器都能过。用 g 编译文件后缀是.cpp虽然代码全是 C 风格# GCC g -o school school.cpp -Wall ./school # 或者用 Clang clang -stdc11 -o school school.cpp ./school-Wall一定要加。这类老代码里常见「函数隐式声明」「变量未初始化」的隐患开警告能提前揪出来。如果用 MSVC注意.cpp后缀下 MSVC 会按 C 规则编译DataType a[] { ... }里的中文字符串如果要按 C 处理可能编码告警加/utf-8参数就好。跑起来的交互流程是两屏菜单****************菜单********************** 1,相关信息查询 2,最短路径查询 ******************************************* 请选择您想进行的操作 2 请输入你要查询的两景点的名称图书馆操场最短路径长度50 从图书馆到操场的最短路径为图书馆——博学楼——操场菜单的递归实现值得一提。menu()在每个操作处理完之后又调menu()形成无限循环想退出只能关窗口。这在课程设计里很常见也确实是偷懒——正确做法是把menu包进while(1)加一个「0 退出」分支。递归调用会一直压栈虽然实际使用中压不了几层但一旦用户连查几十次理论上会栈溢出。翻车场景很小概率但改起来就是两行void menu(void) { int n; while (1) { puts(1. 信息查询 2. 最短路径 0. 退出); scanf(%d, n); if (n 0) break; if (n 1) Information1(); else if (n 2) Path1(); } }改完之后把Information1和Path1末尾的menu()递归调用删掉流程就对了。4.3 数据录入那十行初始化的写法问题main里的景点初始化用的是一段中英引号混用的代码原报告里是这样的DataType a[] {{学生第二食堂,10,学生的主要就餐点}, {男生宿舍,11,一共有八栋}, ...};如果直接从文档复制里面的引号很可能是中文全角引号“ ”编译器会报一堆莫名其妙的错。作者在总结里专门提了「全角半角也得注意」指的就是这个。硬核教训从 Word 或网页里往编辑器粘贴代码先粘到一个纯文本文件里再打开检查或者干脆手打一遍能省下找不出错在哪的半小时。边数组rcw[]有二十八项全部是成对出现的比如{0,1,20}和{1,0,20}。如果哪天要加一条路必须两条一起加否则就成了有向图。这也是为什么Creat里做的是对称赋值——理论上你只用写一半的三元组函数会补全另一半。原程序的数组写全了属于冗余但无害真做二次开发时把e改成 14三元组只写单向的效果一样还少一半出错机会。5. 避坑与排查五个真踩过的坑5.1 矩阵没初始化距离算出来是乱数现象同样的输入最短路径一会儿对一会儿不对甚至出现负数。原因AdjMGraph是局部或栈上的变量时Edge数组里全是垃圾值对垃圾值做min松弛结果自然失控。解决Creat里第一件事就是把整个矩阵填成MaxWeight对角线填 0自己到自己距离为 0否则weight[i][i]会被算成绕一圈的路。这条必须写死不要指望calloc或全局变量。5.2 无穷大取值过大导致整型溢出现象明明没路的两点算出来一个很大的负数距离接着被当成合法路径输出。原因MaxWeight取成了INT_MAX一类的值weight[i][k] weight[k][j]相加溢出。解决无穷大取INT_MAX / 4以内的值1000对这个项目足够同时建图时所有「不相邻」一律填这个值不要让矩阵里出现两种「不通」的表示。5.3 逆序输出路径顺序反了现象查询 A 到 D 显示正常查 D 到 A 时中间点顺序颠倒路径显示成D——B——C——A但实际拓扑是反的。原因回溯path时用j k判断收窄方向输出时的遍历方向没跟着同步。解决把回溯和渲染解耦——先一路回溯到起点把完整节点序列从终点往起点压进数组最后统一倒序打印。这样无论哪个方向查询渲染逻辑只有一条。我一般会写个RebuildPath(int path[][MaxVertices], int i, int j)单独测试输入固定的path矩阵看输出对不对比连着 Floyd 一起调快得多。5.4 景点名输错导致数组越界现象输入一个不存在的景点名程序偶尔崩溃偶尔输出一段乱码路径。原因j或k保持 -1path[j][k]用 -1 做下标。解决映射完成后立刻校验j -1 || k -1并直接 return同时把strcmp的比较改成不区分大小写、去首尾空格减少用户输入失误。查询失败的提示语也要写清楚别只说「找不到」要告诉用户当前有哪些景点可选。5.5 头文件互相包含导致重复定义现象加了 include guard 之后反而编译报「multiple definition」或者去掉 guard 之后报「redefinition of struct」。原因结构体定义放在了头文件里多个.cpp各自 include 一次就有了多份定义全局变量AdjMGraph G;写在头文件里更是灾难。解决头文件只放类型声明和函数原型函数实现放.c全局变量在头文件里写extern AdjMGraph G;、在某个.cpp里写一次定义。课程设计规模小全塞头文件也能过但你要往上加功能这个坑迟早撞上。6. 二次开发从十景点 Demo 到能用的小系统这个项目最大的价值不是它现在能跑而是它的结构留了扩展口。想把课程设计改造成一个真能用的小导览系统按下面的顺序动手最省力。第一步把「每次查询都跑 Floyd」改成「建图后跑一次」。把weight和path两个矩阵提升为图结构的成员或者全局静态变量Creat完成后立即调一次FloydPath里只做名称映射和回溯。这一改查询响应从 O(n³) 降到 O(n) 加一次路径展开。用 200 个节点压测一下差别肉眼可见。验证方法在Floyd前后打时间戳或者干脆在Path里加个静态计数器看每次查询是否还在重复计算。第二步把硬编码数据外置成配置文件。现在景点和边写在main里改一个景点要重新编译。抽一个简单的文本格式比如每行名称代号简介一个景点起点终点距离一条边写个LoadFromFile函数读进来。这一步做完非程序员也能维护地图数据。下面是我常用的配置解析骨架// 顶点文件name code intro int LoadVertices(const char *file, DataType v[], int *n) { FILE *fp fopen(file, r); if (!fp) return -1; // 文件打不开交给调用方报错 int cnt 0; while (fscanf(fp, %19s %d %49s, v[cnt].name, v[cnt].code, v[cnt].introduction) 3) { cnt; if (cnt MaxVertices) break; // 防止越界 } fclose(fp); *n cnt; return 0; }fscanf的返回值是成功匹配的项数等于 3 才算读到一条完整记录这个判断必须写否则文件末尾的空行会让最后一条数据重复入库。宽度限制%19s、%49s对应结构体的数组长度差一位都是缓冲区溢出。第三步做路径的多解与偏好。现在只输出「最短距离」但实际导览里用户可能想要「少走楼梯」「路过食堂」这类偏好。改造路径是把Edge的权值从单一距离换成复合代价比如weight distance stair_penalty * 5 food_bonus * (-3)Floyd 一行不改就支持了。副作用是路径可能不再唯一你需要在松弛时记录「相等距离下的另一条路」代码量不大但要想清楚相等时取哪条——我一般按「中转点编号小的优先」结果稳定、可复现。第四步加个最简图形界面。不用上 Qt用 EasyX 或者直接生成 SVG 文件就够了。把所有顶点的坐标存进DataType再多一个x, y字段问路时把路径点连成折线输出成 SVG浏览器打开就能看。这一步的收益是把「一串名字加箭头」变成「一眼看懂的图」答辩演示效果好也确实是导览系统该有的样子。改造过程中有个验证习惯值得保留每改一处先把矩阵 dump 出来看一遍。我第一版加配置文件加载时就是因为没做这个检查n被算成了 0Creat里循环一次没进整个图是空的但程序不崩查询任何路径都返回 1000 加一条直达——现象极其迷惑查了半小时才发现是文件路径写错、fopen返回 NULL 却被当成功处理了。从那以后我每次加载数据后都强制走一遍「顶点数 0、边数 0、矩阵对称」的断言检查宁可多打几行日志。希望这些坑你一个都不用踩直接用上干净的骨架。本文还有配套的精品资源点击获取

校园导航系统课程设计：邻接矩阵与Floyd最短路径骨架

相关推荐

校园导航系统课设：邻接矩阵与Floyd最短路径实现

Model Zoo还是自研模型？工程视角下的迁移学习与微调决策指南

团队动力引擎：集体好奇心的激发与实践

更多资讯

7天AI扫盲路线图：技术人快速掌握大模型、Agent与AI应用

企业级问卷系统测试实战：从功能到性能的全面优化

LTC681X AFE驱动源码拆解：SPI帧结构、PEC15校验与BMS采样实现

Vue动态组件性能优化：从渲染链路到内存治理的实战指南

MCP协议与Sealos的云原生实践指南

小米MiMo-V2.6开源大模型深度解析：K2架构如何实现长上下文与端侧AI

今日更新

PLFM_RADAR：从被动告警到主动感知的微服务健康监控系统

SPI隔离设计实战：MAX14431BAEE+与STM32F407工业级应用

数字隔离器如何根治SPI通信地环路干扰：MAX14431与TM4C129实战

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？