简介《数据结构课程设计-校园导航系统.doc》是一份面向计算机类专业学生、数据结构初学者及课程设计指导者的单文档课设报告围绕校园地图的图结构建模、景点信息查询和任意两点最短路径求解展开。压缩包内共1个doc文件大小约187KB内容按任务书、详细设计、调试与测试、时间复杂度分析、源程序清单及执行结果、C程序设计总结、致谢和参考文献等章节组织便于按课程设计流程查阅。已有67人浏览学习适合作为数据结构课程设计的参考样例。文档重点呈现邻接矩阵存储、景点与道路结构体设计、Floyd算法求最短路径以及从只能正序输出到完善路径输出的调试思路同时给出测试结果分析与复杂度讨论可帮助读者理解图结构选型、算法实现和报告撰写规范并对照检查自己的课设方案。1. 需求先立住为什么校园导航课设不该一上来就上 Dijkstra数据结构课程设计里校园导航系统几乎是出镜率最高的一道题给你一张校园平面图10 个以上场所两处之间可能有好几条路路长还不一样问任意两点之间的最短路径。任务书里那句“任意场所到达任意场所”是关键它决定了这是一道多源最短路问题而不是单源。很多人第一反应是 Dijkstra写完才发现要对着每个起点各跑一遍代码量和调试量都翻倍。以 10 个顶点、14 条无向边的规模Floyd 三重循环一次算完全部点对结果存进两张表查询时只做一次查表加一次路径回溯是这类课设里性价比最高的选型。这套方案适合要交课程设计报告、要现场演示、还要被追问复杂度的读者。2. 数据建模10 个景点、14 条无向边与邻接矩阵的取舍2.1 三层结构体景点、线性表、图校园导航系统的数据分三层最底层是“景点”这条记录中间层是存放所有景点的顺序表最上层是图本身。这样拆的好处是景点信息的增删改只动顺序表图的拓扑只动矩阵两边互不干扰。结构体定义如下#define MaxVertices 20 /* 景点个数上限 */ #define MaxWeight 1000 /* 无穷大的替代值必须大于任何真实路径和 */ /* 第一层单个景点的信息 */ typedef struct { char name[20]; /* 景点名称作为查询关键字 */ int code; /* 景点代号报告里方便列表 */ char introduction[50]; /* 一句话简介 */ } DataType; /* 第二层景点顺序表 */ typedef struct { DataType list[MaxVertices]; int size; /* 实际景点个数 */ } SeqList; /* 第三层邻接矩阵表示的图 */ typedef struct { SeqList vertices; /* 顶点集合 */ int Edge[MaxVertices][MaxVertices]; /* 边权矩阵MaxWeight 表示不通 */ int numOfEdge; /* 无向边条数 */ } AdjMGraph;MaxWeight这个宏是整套代码的命门取值要大于“任意两点最短路径的最大可能值”。本例最长的一条路走完也不到 200取 1000 足够如果把它设成 100那么两倍边权相加就会溢出成“比无穷大还大”Floyd 的比较条件直接失效。另外name[20]按 UTF-8 中文一字三字节算最多容纳 6 个汉字景点名要起短一点报告里写明这条约束。2.2 邻接矩阵还是邻接表按规模算一笔账10 个顶点用邻接矩阵占 20×20×4 字节不到 2KB判两点是否相邻是 O(1) 的Edge[i][j]换成邻接表省下的那点空间对这个规模毫无意义反而要在 Floyd 里反复跳链表代码复杂度上一个台阶。稀疏图用邻接表是对的但那是几万个顶点的事。这里更该讲的是“边的输入方式”也就是边表/* 边的三元组起点下标、终点下标、路长米 */ typedef struct { int row; int col; int weight; } RowColWeight; /* 只写单向 14 条对称边由建图函数补齐 */ 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;原始材料里把 28 条有向边全手写了一遍正反各一半。这种写法能跑但有两个隐患漏写反向边时程序不报错、只在查询时给出“走不通”的玄学结果边数统计也会变成 28答辩时说“14 条路”和代码里的numOfEdge对不上。改成单向录入、由函数补对称边数、报告、口述三处才能对齐。2.3 建图函数初始化、对称赋值与边数统计建图函数承担三件事拷景点、初始化矩阵、写边并补对称边。顺序不能乱否则会把已经写好的边权覆盖掉。void Creat(AdjMGraph *G, DataType v[], RowColWeight e[], int n, int edgeCount) { int i, j; /* 1. 顺序表装景点顶点下标即景点在数组中的位置 */ G-vertices.size n; for (i 0; i n; i) G-vertices.list[i] v[i]; /* 2. 矩阵初始化自己到自己为 0其余先当作不通 */ for (i 0; i MaxVertices; i) for (j 0; j MaxVertices; j) G-Edge[i][j] (i j) ? 0 : MaxWeight; /* 3. 写边同时补上反向边保证是无向图 */ G-numOfEdge 0; for (i 0; i edgeCount; i) { G-Edge[e[i].row][e[i].col] e[i].weight; G-Edge[e[i].col][e[i].row] e[i].weight; G-numOfEdge; } }对角线置 0 这一步决定了“查自己到自己”的输出是 0 而不是无穷大是测试用例里必查的一项。补对称边这一步决定了Path(体育馆, 东门)和Path(东门, 体育馆)结果一致很多同学只测了一个方向就交卷现场被反向提问当场翻车。2.4 景点与道路清单下面这张表同时是报告里的“校园平面图说明”把顶点下标、代号、简介一次写全后面写测试用例时直接引用。下标名称代号简介相邻景点米0东门10校车与访客主要入口主楼20、体育馆30、隧道351主楼11行政与办公区东门20、隧道202体育馆12塑胶跑道与球场东门30、隧道15、北门303隧道13连接东西两片的通道东门35、主楼20、体育馆15、北门304北门14通行与外卖集散点体育馆30、隧道30、东湖105东湖15湖边步道与休息区北门10、老教学楼35、图书馆86老教学楼16最早的授课楼东湖35、学生公寓20、图书馆25、南门57学生公寓17住宿区老教学楼20、图书馆108图书馆18藏书与自习东湖8、老教学楼25、学生公寓109南门19通往校外商业街老教学楼53. 总体设计六个源文件的分工与菜单驱动的主控流程3.1 模块划分与调用关系按“数据结构—算法—界面”三层切文件是这类课设最稳的组织方式报告里的模块图也好看SeqList.h顺序表操作景点信息的存取基础AdjMGraph.h图的类型定义与基本操作AdjMGraphCreat.h建图含边表录入Floyd.hFloyd 算法与前驱矩阵Inquiry.h景点信息查询、最短路径查询两个业务函数Operation.h菜单与两个查询的输入包装school.cpp景点数据、边数据、main。调用关系是一条单向链main → menu → Information1/Path1 → Information/Path → Floyd。把菜单和业务分开是为了让“换界面不换算法”——如果老师要求加一个“按代号查询”的功能只需在Inquiry.h里加函数、在菜单里加一个 case算法文件一行不动。全局的图变量放在school.cpp里定义头文件里用extern声明这是多文件工程里最容易被忽略的一条/* school.cpp 中定义 */ AdjMGraph G; /* Operation.h 与 Inquiry.h 中使用 */ extern AdjMGraph G;如果在头文件里直接写AdjMGraph G;被两个 .cpp 同时包含时链接器会报重复定义这条错误信息对初学者极不友好往往要查半小时。3.2 主函数与菜单循环原始材料的menu()在每次查询结束后递归调用自己功能上没问题但每查一次就多压一层栈演示时连查十几次虽然不至于崩报告里被问“这里为什么用递归”就不好答。改成循环更稳void menu(void) { int choice; while (1) { printf(\n 校园导航系统 \n); printf( 1. 景点信息查询\n); printf( 2. 最短路径查询\n); printf( 0. 退出\n); printf(\n); printf(请选择操作); if (scanf(%d, choice) ! 1) { /* 输入非数字时清空缓冲避免死循环 */ while (getchar() ! \n); continue; } if (choice 0) break; switch (choice) { case 1: Information1(); break; case 2: Path1(); break; default: printf(没有这个选项请重新输入\n); } } }scanf的返回值判断不是可选项。演示时手一抖敲进一个字母scanf读不到数字、缓冲区里那个字符还在循环会疯狂打印菜单现场很尴尬。加上清空缓冲这一行输入健壮性立刻不同这也是答辩时能主动讲的一个点。3.3 查询模块把景点名翻译成顶点下标两个业务函数的骨架完全一样先按名字在线性表里找下标找不到就提示找到再干活。把“名字找下标”抽成独立函数两处复用也避免了原代码里for循环结束后靠i size判断是否找到这种脆弱写法/* 返回景点下标找不到返回 -1 */ int LocateVertex(AdjMGraph *G, const char *name) { int i; for (i 0; i G-vertices.size; i) if (strcmp(G-vertices.list[i].name, name) 0) return i; return -1; } void Information1(void) { char name[20]; int idx; printf(请输入要查询的景点名称); scanf(%19s, name); idx LocateVertex(G, name); if (idx -1) { printf(没有找到该景点请核对名称后重试\n); return; } printf(名称%s\n代号%d\n简介%s\n, G.vertices.list[idx].name, G.vertices.list[idx].code, G.vertices.list[idx].introduction); }scanf(%19s, name)里的宽度限制对应char name[20]多一个字符就是栈上的越界写属于“平时不出事、演示时出事”的典型。信息查询走一遍线性表时间复杂度 O(n)n 是景点数这一点第 4 章算复杂度时直接引用。4. 最短路径实现Floyd 三重循环与路径回溯的正确写法4.1 算法主体与前驱记录Floyd 的本质是“逐步放开中转点”第 k 轮允许经过编号 0..k 的顶点weight[i][j]存当前最优距离path[i][j]存“i 到 j 的最优路径上i 之后先经过哪个中转点”没中转就是 -1。void Floyd(int cost[][MaxVertices], int n, int weight[][MaxVertices], int path[][MaxVertices]) { int i, j, k; /* 初始化距离矩阵复制边权前驱矩阵全部置 -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放最外层含义是“本轮允许经过顶点 k”放里面就变成动态规划的阶段被打乱结果时对时错属于最隐蔽的一类 bug——小图上跑出来是对的换一组数据就错。weight[i][k] weight[k][j]这类加法在不通的情况下会变成MaxWeight 某值只要MaxWeight取得足够大就不会溢出成负数这也是 2.1 节强调取值的原因。4.2 路径回溯用递归替掉正逆序判断原始材料里踩过的坑很典型正序查询能正确输出东门→主楼→隧道→北门→东湖反过来查就乱了。根源在于path表是“从终点往回指”的顺序打印和逆序打印需要的遍历方向相反靠if (j k)这种下标比较来分支只能应付特例。正解是按path的语义递归path[i][j] k意味着路径形如i → (i到k的路径) → k → (k到j的路径) → j递归天然把顺序摆正不需要任何方向判断。/* 只打印中间经过的顶点起点和终点由调用方负责 */ void PrintPath(AdjMGraph *G, int path[][MaxVertices], int i, int j) { int k path[i][j]; if (k -1) return; /* 直达递归终点 */ PrintPath(G, path, i, k); /* 先输出前半段 */ printf(%s —— , G-vertices.list[k].name); PrintPath(G, path, k, j); /* 再输出后半段 */ }递归深度最大等于顶点数10 个顶点最多 10 层栈完全撑得住。这段代码只有六行却把“正逆序”这个坑彻底消掉答辩时如果被问“你的路径怎么保证顺序正确”直接指着这六行讲语义比解释下标比较逻辑体面得多。4.3 查询入口不可达与同名输入的兜底业务层的Path把上面几块拼起来重点在两个判断名字找不到以及两点之间根本不连通。void Path(AdjMGraph *G, const char *from, const char *to) { int i, j, k, n G-vertices.size; int weight[MaxVertices][MaxVertices], path[MaxVertices][MaxVertices]; j LocateVertex(G, from); k LocateVertex(G, to); if (j -1 || k -1) { printf(起点或终点名称有误请核对后重试\n); return; } Floyd(G-Edge, n, weight, path); if (weight[j][k] MaxWeight) { /* 仍为无穷大说明不连通 */ printf(%s 与 %s 之间暂无可通行道路\n, from, to); return; } printf(最短距离%d 米\n, weight[j][k]); printf(%s —— , G-vertices.list[j].name); PrintPath(G, path, j, k); printf(%s\n, G-vertices.list[k].name); }weight[j][k] MaxWeight这个判断必须写。少了它不连通的两点会输出“最短距离 1000 米”看上去像条真路演示时一旦被点破就很被动。另外起点和终点相同的查询会走到weight[j][j] 0、path[j][j] -1输出“0 米东门 → 东门”逻辑自洽把它写进测试用例反而是加分项。4.4 复杂度口算与报告写法信息查询扫一遍线性表时间 O(n)空间 O(n)最短路查询里 Floyd 是三重循环时间 O(n³)两个 n×n 的辅助矩阵是 O(n²) 空间。注意原始材料写“空间复杂度 O(1)”是不准确的weight和path都是与 n 同阶的二维数组报告里写 O(n²) 才对得上代码。真正值得强调的一句是Floyd 只算一次、结果可复用如果菜单做成“一次建图、多次查询”每次查询的实际开销只剩回溯输出的 O(n)这是选型带来的收益比背复杂度公式有说服力。5. 避坑与排查五个最容易在验收现场翻车的地方5.1 现象所有最短路径都是 0 或 1000原因矩阵初始化时把“不通”写成了 0或者干脆没初始化Edge是全局变量默认为 0Floyd 一看处处相等就不更新。解决初始化必须显式写成(i j) ? 0 : MaxWeight并在建图后打印一次矩阵自查前几行对得上再往下做。5.2 现象一个方向查得到路反方向提示不通原因只写了Edge[row][col]忘了Edge[col][row]图变成了有向图。解决对称赋值统一放在建图函数里业务代码永远不直接写矩阵测试用例强制正反各查一次。5.3 现象路径输出成东门→东湖→北门→体育馆这种乱序原因用下标大小判断遍历方向只对部分数据成立。解决改成 4.2 节的递归回溯按path语义输出删掉所有方向判断分支。5.4 现象明明输入的是同一个景点名程序说找不到原因scanf(%s)遇到空格就截断或者录入时用了全角字符、查询时用了半角还有一种情况是前面某次scanf(%d)留下的换行符被%s读走。解决景点名统一约定不含空格输入用%19s菜单里读数字后清一次缓冲景点表里的名字和测试用例里的名字逐字比对一遍。5.5 现象编译报重复定义或者改一个文件另一个文件行为也变了原因全局图变量AdjMGraph G;写在了头文件里被多个源文件包含或者几个头文件互相包含形成环。解决变量在school.cpp定义一次头文件里只写extern每个头文件加包含保护Inquiry.h只依赖AdjMGraph.h不反向依赖。6. 验收与答辩测试用例表和复杂度口述怎么准备验收现场最怕的不是程序有小毛病而是被问“你怎么证明它是对的”。我的做法是提前把测试用例写成一张表覆盖正常、边界、异常三类逐条跑一遍把结果记在报告里表比截图更经得起追问。编号起点终点预期结果考察点T1东门图书馆78 米东门→体育馆→北门→东湖→图书馆多中转点路径顺序正确T2图书馆东门78 米路径与 T1 反向无向图对称性T3北门东湖10 米两点直达相邻顶点无中转T4东门东门0 米东门→东门自反边界T5东门食堂提示名称有误异常输入兜底T6临时断开 4-5 边后查东门→图书馆提示无可通行道路不连通分支T1 的 78 米建议自己手算复核一遍别直接信程序输出——把Edge矩阵和手算过程写进报告是“我理解算法”最直接的证据。T6 用改数据的方式构造改完记得改回来演示前把最终版本的图和数据固定下来。复杂度那部分准备三句话就够信息查询扫线性表 O(n)Floyd 三重循环 O(n³)辅助空间两张 n×n 矩阵 O(n²)建图只做一次多次查询时单次开销降到回溯输出的 O(n)。如果老师追问“为什么不用 Dijkstra”答案已经在第 1 章里这是任意两点查询Floyd 一次算完全部点对代码短、报告好写、演示不挑输入顺序。真被要求现场加功能优先挑“按代号查询”或“打印全部景点列表”改动落在Inquiry.h和菜单上不碰算法文件风险最低。血泪经验是交之前一定用一份“干净的”输入从头跑一遍别在调试中途的状态上直接演示我见过太多人栽在改了一半的数据上。从那以后我每次交课设前都强制走一遍「删掉编译产物 → 重新编译 → 按测试用例表逐条跑 → 正反各查一次」十分钟的事能省掉整场答辩的心跳。希望帮到你。本文还有配套的精品资源点击获取
