企业官网建设流程全解析

简介：面向计算机相关专业学生与数据结构课程设计指导者的校园导航系统课程设计文档，围绕无向图建模、景点信息查询与任意两点最短路径求解展开，适合作为课程设计选题、实验报告撰写与答辩准备参考。压缩包内仅含1个doc文件，大小约187KB，集中呈现任务书、详细设计、调试与测试、时间复杂度分析、源程序清单及执行结果，并附C程序设计总结、致谢与参考文献。文档以邻接矩阵存储图结构，结合顺序表保存景点名称、代号和简介，采用Floyd算法实现最短路径查询，同时记录调试问题、测试结果分析与改进思路。已有67人学习或下载，可帮助读者梳理图结构表示、存储结构选择、算法实现、测试用例设计和报告规范，快速形成较完整的课程设计框架。

1. 校园导航系统课设包：10 个景点、28 条边，一份能直接跑通的《数据结构》课程设计

答辩前一晚最经典的翻车场景是这样的：把校园平面图抽象成 10 个景点、28 条路，输入「学生第二食堂」到「图书馆」能正常打印一串节点，反过来输入就变成颠倒的路径，甚至卡在某个循环里出不来。这份 doc 就是围绕这个问题攒出来的完整交付物——任务书、存储结构说明、算法设计思想、调试记录、时间复杂度分析、源程序清单全在里面，源码拆成 school.cpp、AdjMGraph.h、AdjMGraphCreat.h、SeqList.h、Floyd.h、Operation.h、Inquiry.h 七个文件，主体是「顺序表存景点 + 邻接矩阵存道路 + Floyd 求任意两点最短路」。

数据结构课程设计里，校园导航系统算是把图这一章吃透的标准题型：顶点带属性、边带权、要查询、要问路。它适合三类人——正在做图论课设、需要一份能编译能演示的参考实现；想把邻接矩阵和 Floyd 从纸面公式落到可运行代码；以及已经写完但路径打印一直不对、想找到问题根源的人。下面按「结构体怎么定 → 图怎么建 → 最短路怎么算怎么打印 → 坑在哪 → 怎么验收」的顺序走一遍。

2. 顶点用顺序表、边用邻接矩阵：10 个景点的图为什么不该上邻接表

2.1 三个结构体定下整份代码的数据契约

这套实现里所有后续逻辑都建立在四个结构体上，先把它们定死，后面的建图、查询、最短路才有共同语言。景点用定长字符数组而不是char *，是为了避开动态内存和深拷贝——课设规模下这点内存不值得省，但省下的是成片的malloc/free调试时间。code字段和数组下标刻意解耦：下标是程序内部寻址用的，代号是对外展示用的，两者分开之后，你调整景点顺序不必改菜单提示，也不会因为删掉一个景点就让所有边的 row/col 全部错位。

#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; /* 建图用的边集数组，一条记录就是一条有向边 */ typedef struct { int row; int col; int weight; } RowColWeight;

这里有个很多人踩过、但报告里从来不写的细节：name[20]在 GBK 编码下一个汉字占 2 字节，最多放 9 个汉字加结束符；换到 UTF-8 下一个汉字 3 字节，20 字节只够 6 个汉字加\0。像「学生第二食堂」这种 7 个汉字的景点名，在 UTF-8 源文件里用strcpy拷进去就会写穿 2 个字节，正好踩在相邻元素的code字段上——现象是查询时景点代号莫名其妙变成一个大数。稳妥做法是把name提到char name[32]，或者干脆统一用 GBK 存源文件，别在编码上赌运气。

Edge是 20×20 的 int 矩阵，算下来 1600 字节，对现代机器毫无压力；但它的意义不在省内存，而在于把「两点之间有没有路、路多长」变成一次O(1)的下标访问。Floyd 的三重循环整个建立在这个假设上，换任何别的存储结构，算法都得重写。

2.2 稠密还是稀疏：28 条边对 45 条上限这道算术题

选邻接矩阵还是邻接表，课设报告里最常见的错误答案是「邻接表省空间」，然后抄一段链表代码进去，最后卡在指针上出不来。正确的判断方式是先算密度：无向图 n 个顶点最多n(n-1)/2条边，这里是 10 个景点、上限 45 条，实际写了 28 条，密度 0.62，明显偏稠密。邻接表在这个规模下能省下的空间是「每个节点 8 字节 × 56 个节点 ≈ 448 字节」，而代价是要么手写链表节点、要么用数组模拟链表，调试成本翻几倍。

更关键的约束是任务本身：题目要求「任意两个景点之间的最短路径」，也就是全源最短路。Floyd 的输入天然就是一张权值矩阵，你就算用邻接表存图，最后也得先O(n²)展开成矩阵再喂进去，属于绕远路。所以这里的选型逻辑不是「矩阵比链表高级」，而是「稠密图 + 全源查询 + 小规模」三个条件同时成立，矩阵是唯一不别扭的选择。真到了几百个顶点、边只有几百条的稀疏路网，邻接表配堆优化 Dijkstra 才是正解，这一点在最后一章还会提到。

顶点之所以单独用顺序表而不是直接塞进AdjMGraph，是为了让「查景点信息」和「查最短路」共用同一份顶点数据：查询简介时扫的是vertices.list，打印路径时按下标回读的也是vertices.list，不会出现两份数据对不上的情况。

2.3 七个头文件的分层：把图操作和业务菜单切开

源码拆成七个文件不是摆设，它对应一条清晰的责任链：SeqList.h 管线性表，AdjMGraph.h 管图的结构体和基础操作，AdjMGraphCreat.h 负责建图，Floyd.h 只放算法，Inquiry.h 放两个查询函数，Operation.h 放菜单和交互封装，school.cpp 是唯一带main的入口。这样拆的好处是调试时能定位到层——路径算错去 Floyd.h，查不到景点去 Inquiry.h，界面乱跳去 Operation.h。

但原始代码里有一处写法在单文件编译下能过，一旦拆成多文件就链接报错：school.cpp 里先写AdjMGraph G;定义全局变量，然后才#include "Operation.h"，而 Operation.h 里的函数直接用了G。这等于让头文件依赖「包含顺序」，任何调整 include 顺序的改动都会炸。常规做法是在 AdjMGraph.h 里写extern AdjMGraph G;声明，在 school.cpp 里定义，头文件只管声明不管定义。

/* AdjMGraph.h 里：只声明，不定义 */ extern AdjMGraph G; /* school.cpp 里：唯一定义处 */ AdjMGraph G;

顺带说一句函数原型：Inquiry.h 里的Information和Path都按值接收AdjMGraph G，而AdjMGraph内部含一个 1600 字节的矩阵，每次调用都要整体压栈拷贝一次。10 个顶点的规模下感觉不到，但这是坏习惯——改成const AdjMGraph *G传指针，既省拷贝又能让编译器帮你挡住「函数里偷偷改图」的误操作。课设代码里这类「能跑但不对味」的地方，答辩时被追问的概率反而不低。

3. 把 28 条路写进矩阵：建图函数里必须做的三件事

3.1 边集数组怎么填：14 对无向边一条都不能少

建图这一步最容易被低估。原始代码的做法是准备一个RowColWeight rcw[]数组，把每条边写成{起点下标, 终点下标, 权值}一条记录，再配一个int n=10, e=28;告诉建图函数「10 个顶点、28 条边记录」。之所以是 28 而不是 14，是因为无向图的每条路要在矩阵里写两个位置：Edge[i][j]和Edge[j][i]。原始数据里确实成对出现了，比如{0,1,20}和{1,0,20}就是同一条路的两个方向。

/* 前 3 个景点之间的边，注意每条路都成对出现 */ RowColWeight rcw[] = { {0, 1, 20}, {0, 2, 30}, {0, 3, 35}, {1, 0, 20}, {1, 3, 20}, {2, 0, 30}, {2, 3, 15}, {2, 4, 30}, /* ... 其余 20 条同理，共 28 条记录 */ };

这段数组的隐式契约是：row/col必须严格对应DataType a[]里景点的下标顺序。你如果在中途插了一个新景点，把「图书馆」从下标 9 挪到下标 5，那么所有row/col为 9 的记录全部失效，程序不会报错，只会算出一条通往错误景点的路径——这是这套代码里最隐蔽的一类 bug，改完顶点表必须回头核对一遍边集。

3.2 初始化：先全填 MaxWeight，再把对角线置 0

建图函数要按「顶点表 → 矩阵初始化 → 逐条写边」三步走，顺序不能换。初始化必须先把整个矩阵填成MaxWeight表示不可达，再把Edge[i][i]置 0 表示自己到自己距离为零。这两步一旦漏掉，矩阵里会残留栈上的随机值，Floyd 跑出来的结果就是玄学——有时候对，有时候冒出一条根本不存在的近路。

void Creat(AdjMGraph *G, DataType v[], RowColWeight rcw[], int n, int e) { int i, j, k; /* 1. 顶点表整体拷贝，size 单独记 */ for (i = 0; i < n; i++) G->vertices.list[i] = v[i]; G->vertices.size = n; /* 2. 矩阵清零：对角线 0，其余视为不可达 */ for (i = 0; i < n; i++) for (j = 0; j < n; j++) G->Edge[i][j] = (i == j) ? 0 : MaxWeight; /* 3. 逐条写入边权，计数 */ G->numOfEdge = 0; for (k = 0; k < e; k++) { i = rcw[k].row; j = rcw[k].col; G->Edge[i][j] = rcw[k].weight; G->numOfEdge++; } }

参数说明：v[]是顶点数组，rcw[]是边集，n是顶点数，e是边记录条数（无向图要传双倍）。注意这个版本没有在函数内部做对称赋值，因为它依赖调用方在边集里成对写全。如果你的习惯是「一条路只写一次」，那就必须在循环里补一行G->Edge[j][i] = G->Edge[i][j];，两种策略二选一，混着用一定会出错——一半边成对、一半边单写，结果就是某些方向可达、反方向不可达，Floyd 会诚实地告诉你「从图书馆到操场没有路」。

numOfEdge这个字段在很多实现里被注释成「边数」，但无向图里它实际记的是有向边记录数。如果后面有「判断图是否连通」之类的需求，得先除以 2，这一点在报告里写清楚，属于加分项。

3.3 自检：建完图先打印矩阵和每个顶点的度

建图之后别急着跑最短路，先花十行代码打个自检，能省掉后面几小时的排查。检查两件事：矩阵是否对称，每个顶点的度是否和预期一致。对称性直接反映无向图的正确性，度则能快速发现漏写的边——比如你预期「老教」连了 4 条路，打印出来只有 3 条，那就回去数边集里跟下标 6 有关的记录。

void Check(AdjMGraph *G) { int i, j, deg; for (i = 0; i < G->vertices.size; i++) { deg = 0; for (j = 0; j < G->vertices.size; j++) { if (i != j && G->Edge[i][j] < MaxWeight) { deg++; /* 对称性检查：i->j 有边，j->i 也必须有，且权值相同 */ if (G->Edge[j][i] != G->Edge[i][j]) printf("非对称边: %d <-> %d\n", i, j); } } printf("%-12s 度=%d\n", G->vertices.list[i].name, deg); } printf("边记录数=%d，实际无向边数=%d\n", G->numOfEdge, G->numOfEdge / 2); }

这套自检还能顺手验证MaxWeight的取值是否合理。原始代码取 1000，如果某条真实路径的总长超过 1000，就会被误判为不可达；反过来，两个不连通点之间做加法得到 2000，不会小于 1000，所以不会凭空造出一条路。也就是说 1000 这个值只对「长路径」有风险，对「假连通」是安全的。校园里任意两点走下来一般不超过几百米量级，1000 够用，但报告里最好把这条假设点出来。

4. Floyd 三重循环与 path 回溯：最短路径算得对，还要打得对

4.1 cost、weight、path 三个矩阵各管什么

Floyd 的经典写法需要三张同尺寸的矩阵，很多人对着代码抄完还是不知道每张在干嘛。cost是输入，就是建好的邻接矩阵G.Edge，只读不改；weight是输出，weight[i][j]存最终的最短距离；path是辅助，path[i][j]存的是「i 到 j 的最短路上，经过哪个中转点」，取 -1 表示两点直达、不需要中转。三者的关系是：cost提供初始值，weight在递推中被不断松弛，path在每次松弛成功时记下当前的中转点 k。

void Floyd(int cost[][MaxVertices], int n, int weight[][MaxVertices], int path[][MaxVertices]) { int i, j, k; /* 初始化：结果矩阵直接拷输入，中转点全部标记为"无" */ 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; /* 记下这次的中转点 */ } } } } }

参数说明：n是实际顶点数而不是MaxVertices，传错会让未使用的下标参与运算，虽然结果一般不受影响，但会拖慢 n 倍——20³ 对 10³ 差 8 倍，规模小时无所谓，习惯要养好。cost里的不可达值参与加法是安全的，因为MaxWeight + MaxWeight一定大于任何单个MaxWeight，不会触发松弛。

4.2 为什么 k 必须是最外层循环

三重循环的嵌套顺序是这段代码唯一不能动的地方。k在最外层的含义是「本轮只允许经过顶点 k 中转」，经过 n 轮之后，任意两点之间的路径允许经过全部顶点，自然就是最优解。如果把k挪到内层，等于对每一对 (i, j) 都做一次「只允许经过当前 k」的松弛，之前轮次算出的中间结果会被反复覆盖，某些组合会算错，而且错得很隐蔽——小规模测试用例恰好能过，换一张图就崩。

这个顺序还带来一个副作用，恰好是正确实现路径回溯的关键：第 k 轮结束后，weight[i][k]和weight[k][j]已经是最终值，后面不会再变小，因此path[i][k]、path[k][j]也定格了。这意味着path[i][j] = k记下来的这条「拆成两段」的信息是永久有效的，递归下去一定能拼出完整路径。反过来说，如果实现里把path[i][j]记成k之外的东西，比如path[i][k]，递归就会走进死循环。

4.3 路径打印：把正序/逆序两个分支删掉，换成一个递归

原始代码在这块绕了远路。它用一个while (m != -1)循环从中转点往前倒推，靠if (j < k) k = m; else j = m;判断「这次该收哪一端」，把中转点一个个塞进value[]数组，最后再根据起点终点下标大小决定正序还是倒序打印。这套逻辑只在「顶点编号顺序恰好等于路径方向」时成立，换个编号方案就打印出一串乱序节点——报告里那句「逆序输出时得到的结果有点问题」，根因就在这。

正确的做法是把path的语义用递归表达出来：i到j的最短路若经过中转点k，那么路径就是「i 到 k 的最短路 + k + k 到 j 的最短路」。写出来只有五行，正序逆序问题自动消失。

/* 打印 i 到 j 之间的中转点，不含两端 */ static void PrintMid(int path[][MaxVertices], SeqList L, int i, int j) { int k = path[i][j]; if (k == -1) return; /* 直达，没有中转点 */ PrintMid(path, L, i, k); /* 左半段 */ printf("%s ——> ", L.list[k].name); PrintMid(path, L, k, j); /* 右半段 */ } void PrintPath(int path[][MaxVertices], SeqList L, int i, int j, int dist) { printf("最短距离：%d\n", dist); printf("%s ——> ", L.list[i].name); /* 起点 */ PrintMid(path, L, i, j); /* 中间节点 */ printf("%s\n", L.list[j].name); /* 终点 */ }

配套的查询函数还有一处必须补的防御：原始Path里int j, k;声明后没有初始化，靠strcmp匹配去赋值。一旦用户输入的景点名打错一个字，j和k就是栈上的随机值，随后weight[j][k]直接越界读，轻则打印垃圾数据，重则段错误。

int j = -1, k = -1; for (i = 0; i < G.vertices.size; i++) { if (strcmp(G.vertices.list[i].name, from) == 0) j = i; if (strcmp(G.vertices.list[i].name, to) == 0) k = i; } if (j == -1 || k == -1) { printf("景点名称有误，请重新输入\n"); return; } if (j == k) { printf("起点和终点相同，距离为 0\n"); return; } Floyd(G.Edge, G.vertices.size, weight, path); PrintPath(path, G.vertices, j, k, weight[j][k]);

这三个判断看起来啰嗦，但它们挡住了实际演示中最常见的三种输入：打错字、走神重复输入同一个景点、以及查一个不存在的景点。答辩现场被要求「随便输一个」的时候，能稳住就是分数。

5. 避坑与排查：这套课设代码最常翻车的五个点

5.1 五条血泪记录，按现象、原因、解决写

路径顺序错乱，只有直达路径是对的。现象是从 A 到 B 打印出一串节点，顺序跟实际走的路线对不上，有时还会重复打印同一个景点。原因是用while循环从path里倒推中转点，并且靠j < k这样的编号大小比较来决定收哪一端，隐含假设了「编号顺序等于路径方向」。解决办法是彻底删掉这段倒推逻辑，改成上面那个PrintMid递归，path的语义本来就是树形拆分，用递归表达最直接。

反向查询查不到，或者返回 1000 表示不可达。现象是 A 到 B 有结果，B 到 A 显示没有路径。原因是建图时只写了Edge[i][j]没写Edge[j][i]，边集里一条路只出现了一次。解决办法是先跑Check函数打印矩阵对称性，确认每对顶点双向都有权值；如果采用「一条路写一次」的边集风格，就在建图循环里补上对称赋值。

输入中文景点名查不到，或者控制台输出一堆乱码。现象是明明照着菜单上的名字敲的，程序说「不在提供范围内」；或者路径里的中文变成问号。原因有两层：一是scanf("%s", name)遇到空格就截断，景点名里带空格必然失败；二是源文件编码和终端代码页不一致，GBK 源文件在 UTF-8 终端下输出就是乱码。解决办法是统一编码，Windows 下用chcp 65001切终端代码页、源文件存 UTF-8，Linux 下确认 locale 设置；输入上改用fgets读整行再去掉换行符，或者干脆让用户输景点代号，绕开中文输入。

char buf[64]; fgets(buf, sizeof(buf), stdin); buf[strcspn(buf, "\n")] = '\0'; /* 去掉换行，保留空格 */

景点代号突然变成一个莫名其妙的大数。现象是查询简介时code打印出来是随机值，而name和introduction显示正常。原因是name[20]装不下 UTF-8 编码下的长景点名，strcpy写穿了 2 个字节，正好覆盖相邻结构体成员的code字段。解决办法是把name扩到 32 字节，或者用strncpy加手动补\0，别用strcpy。

程序越用越卡，退出菜单后行为异常。现象是查几次之后响应变慢，最后关不掉。原因很典型：Information1()和Path1()在末尾调用menu()递归回到主菜单，用户每操作一次就多压一层栈帧，操作几十次之后栈就吃不消了。解决办法是把menu()改成while (1)循环，各功能函数返回后继续循环，输入 0 时break退出，函数之间不再互相调用。

void menu(void) { int n; while (1) { printf("1.景点信息查询 2.最短路径查询 0.退出\n请选择："); if (scanf("%d", &n) != 1) break; if (n == 0) break; switch (n) { case 1: Information1(); break; case 2: Path1(); break; default: printf("无此选项\n"); } } }

5.2 一套能过验收的测试用例表

演示的时候最怕临时想不出查什么，提前把下面这张表抄在纸上，逐条走一遍，覆盖直达、中转、不可达、错误输入四类场景。表里的距离按前面 28 条边推算，实际跑出来的数值对不上就说明边集或对称赋值出了问题。

T4 是整张表里最有价值的一条：距离最长、中转点最多，路径打印的递归层级也最深，任何一处path记录错误都会在这里暴露。T6 专门用来抓「单向边」的漏网之鱼。T5 用来证明程序不会因为用户手抖就崩掉——这一条在验收时往往是加分项，因为它体现了对边界输入的处理意识。

6. 把 1000 换成 INF，再判断什么时候该换算法

原始代码用MaxWeight = 1000当无穷大，够用但不严谨。换成0x3f3f3f3f这种「两个相加不溢出 int」的值更稳，同时给 Floyd 内层加两个剪枝：跳过i == j的自比较，跳过weight[i][k] == INF的无效中转。前者省掉一批无意义的对角线运算，后者能防止不可达点作为中转参与松弛。

#define INF 0x3f3f3f3f for (k = 0; k < n; k++) for (i = 0; i < n; i++) { if (weight[i][k] == INF) continue; /* i 到 k 都不通，k 中转无意义 */ for (j = 0; j < n; j++) { if (i == j) continue; int t = weight[i][k] + weight[k][j]; if (t < weight[i][j]) { weight[i][j] = t; path[i][j] = k; } } }

改完之后记得把Creat里的初始化值一起换掉，两处不一致会导致矩阵里同时存在 1000 和 0x3f3f3f3f 两种「无穷」，比较逻辑立刻失效。

至于该不该换算法，我的判断标准很朴素：顶点数在 50 以内、需要「任意两点都能问」、查询次数不多，Floyd 就是最优解——代码短、没有堆、不用处理单源限制，O(n³)在 n=10 时只有 1000 次内层迭代，微秒级完成。反过来，如果景点涨到几百个、边却只有几百条，或者需求变成「实时导航、每次只问一个起点」，那 Dijkstra 配邻接表才是正路，Floyd 光是初始化矩阵的O(n²)就够呛。很多人喜欢在课设里堆两个算法对比，我更建议把一套 Floyd 的路径回溯讲透，比塞两套半成品强。

顺带一个效率上的小习惯：Floyd 其实只需要在程序启动、建完图之后跑一次，把weight和path存成全局矩阵，之后每次查询只做下标查找。原始代码是每次查询都重新调一遍Floyd，10 个顶点察觉不到，但它反映的是「算法调用位置」的认识问题，讲清楚这一点比优化几个时钟周期值钱。

从那以后我每次接这类图论课设，都强制自己先跑三件事：打印邻接矩阵看对称性、用一条最长路径验证递归打印、再拿一个打错的景点名试崩不崩。这三步走完，后面基本不会返工。希望帮到你。

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