企业官网建设流程全解析

简介：围绕《数据结构》课程设计中的校园导航系统，这份文档面向计算机专业学生及正在完成图论类课程设计的学习者，聚焦校园地图建模、景点信息查询与任意两点间最短路径求解等典型问题。压缩包仅含1个doc文件，约187KB，内容为完整的课程设计报告，而非零散代码片段。已有67人学习，适合作为同类题目的参考范例。文档从任务书、详细设计到调试测试逐层展开，给出邻接矩阵存储、顶点与边结构体设计、Floyd算法求最短路径及正序输出路径的处理思路，并附源程序清单与执行结果、时间复杂度分析、C程序设计总结和参考文献。读者可据此梳理从图结构选型、算法实现到测试排错与报告撰写的完整流程，对照完善自己的课程设计文档与程序实现。

1. 从东区到东湖能走通、反着查就乱套，这类 Bug 最磨人

做数据结构课程设计那阵子，校园导航系统的 Floyd 最短路径已经跑通了：输入“东区”和“东湖”，屏幕上端端正正打出东区 ——> 主楼 ——> 西体育馆 ——> 隧道 ——> 北大门 ——> 东湖，距离也对得上手算结果。可把起点终点一换，从东湖查回东区，中间那几个景点就开始乱序，有时候顺序整个反过来，有时候还漏掉一个中转点。程序不崩、不报错、编译零警告，就是结果不对，这种“算法没错、输出错乱”的故障最难查，因为它不给你任何提示，只能靠肉眼比对。这篇笔记就是从这个坑出发，把校园导航系统里最短路径类的几类典型故障拆开：路径还原为什么错、邻接矩阵怎么初始化、景点名为什么查不到、菜单为什么越点越慢。正在写图算法课程设计、或者线上路径规划功能突然返回异常路线的人，都能对号入座。

2. 最短路径顺序错乱：path 矩阵存的是中转点，不是上一步

2.1 先分清两个矩阵：一个存距离，一个存分叉点

Floyd 跑完之后会得到两张表，很多人只盯着第一张。weight[i][j]存的是 i 到 j 的最短距离，这个是大家都会看的；path[i][j]存的是“为了让 i 到 j 更短，最后一次经过的中转点 k 是谁”，这张表才是路径还原的全部依据。它的语义不是“i 的下一步是 k”，而是“i 到 j 这条路，在 k 这里被劈成了 i 到 k 和 k 到 j 两段”。理解错这一层，后面所有打印逻辑都会歪。

/* Floyd 核心：weight 存距离，path 存分叉点，-1 表示直达无中转 */ 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; /* 初始认为任意两点都直达 */ } } for (k = 0; k < n; k++) { /* k 必须最外层：每轮允许经过第 k 个点中转 */ for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { if (weight[i][k] + weight[k][j] < weight[i][j]) { weight[i][j] = weight[i][k] + weight[k][j]; path[i][j] = k; /* 记录本次生效的中转点 */ } } } } }

三个循环的顺序不能换。k 放最外层，含义是“第 k 轮循环结束时，任意两点之间如果走得更短，只允许借用编号 0 到 k 的顶点做中转”。这是 Floyd 动态规划的正确性来源。i、j 的顺序无所谓，但 k 一旦挪到内层，weight[i][k]和weight[k][j]可能在这一轮里刚被改过，结果就变成了另一套算法的近似值。

path[i][j] = k这一行每次覆盖的是“当前最优解对应的那个分叉点”。因为 k 从小到大枚举，后面的 k 会覆盖前面的 k，最终留下来的就是最后生效的那次分叉。这一点很关键：递归还原路径时，每次都从path[i][j]取分叉点，取到的必然是能把路径正确切开的那一个。

2.2 边找路径边改起点终点，是错乱的直接来源

原始代码的还原逻辑大致长这样：从path[j][k]取出中转点 m，把 m 记进value[]数组，然后根据j < k判断往哪半边继续找，循环直到 m 为 -1，最后再根据一次j < k决定value[]是从前往后打还是从后往前打。

/* 有问题的写法：靠顶点下标大小决定前进方向 */ m = path[j][k]; while (m != -1) { value[count] = m; if (j < k) k = m; /* 认为编号大的在后半段 */ else j = m; /* 认为编号小的在前半段 */ m = path[j][k]; count++; }

这里藏着三个问题，任何一个都足以让某组数据的结果出错。

第一个问题是j < k这个判断本身。它拿顶点编号大小去推断路径走向，隐含假设是“编号大的景点一定排在路径后面”。这组测试数据里恰好成立：东区编号小、东湖编号大，沿途景点编号基本递增。可一旦换一条路径，比如从编号 8 的小门走到编号 3 的物理楼，编号是递减的，判断分支立刻走反。

第二个问题是 j 和 k 在循环里被不断覆写。等循环结束，j、k 已经不是最初的起点和终点，而是路径上的某个中间点。后面那句if (j < k)拿被改过的值当依据，等于用一个已经失效的变量去决定输出方向，结果自然不稳定。

第三个问题是value[]的记录顺序和输出顺序。数组是按“从外向内”的顺序存的，打印时要么正着来要么倒着来，靠一个全局的 if 一次性翻转。这种写法只有在路径的中间点恰好单调排列时才正确，本质上是拿测试用例拟合出来的补丁，不是解法。

提示：凡是“正向对、反向错”的路径问题，先怀疑代码里有没有依赖顶点编号大小的假设，这一类 bug 占了图算法输出异常的多数。

2.3 用递归还原路径，顺序天然正确

正确的还原方式是把“打印 i 到 j 的路径”定义成一个递归问题：先打印 i 到 k 的路径，再打印 k 本身，最后把 j 交给调用方补上。因为递归是先深入到最底层再逐层返回，打印顺序天然就是路径的正向顺序，跟编号大小、跟起点终点谁大谁小完全无关。

/* 递归打印 i 到 j 之间的中转点，不含 j 本身 */ void PrintPath(int i, int j, int path[][MaxVertices], AdjMGraph *G) { int k = path[i][j]; if (k == -1) { /* 直达，递归到底，只打起点 */ printf("%s", G->vertices.list[i].name); return; } PrintPath(i, k, path, G); /* 先走前半段 i -> k */ printf(" ——> %s", G->vertices.list[k].name); /* 再打分叉点 k */ } /* 对外接口：判不可达 + 打距离 + 打完整路径 */ void ShowPath(int i, int j, int weight[][MaxVertices], int path[][MaxVertices], AdjMGraph *G) { if (weight[i][j] >= MaxWeight) { /* 距离仍是无穷大，说明不连通 */ printf("两地之间没有可通行的道路\n"); return; } printf("最短距离：%d 米\n路径：", weight[i][j]); PrintPath(i, j, path, G); printf(" ——> %s\n", G->vertices.list[j].name); /* 终点在这里补 */ }

参数含义要说清楚：i、j是起点和终点在顶点表里的下标，不是景点名称；path是 Floyd 填好的分叉点矩阵；G用来按下标反查景点名称。递归深度最多等于顶点数 n，10 个景点最多 10 层，完全不用担心栈。真正需要注意的是i == j的情况，此时path[i][i]是 -1，函数会打印一次起点，调用方再补一次终点，屏幕上就会出现“图书馆 ——> 图书馆”，所以在调用前要先判掉起点等于终点。这个分支不算错，只是用户体验上不好看，加一句if (i == j)单独提示即可。

这段递归和原来那套 while 循环的差别不只是“写法更短”。递归把“路径 = 起点 + 前半段 + 分叉点 + 后半段”这个结构直接表达出来了，而 while 循环版本把结构揉碎成了数组下标运算，一旦数据结构被破坏，错误就不可见。改完之后，正向、反向、绕路、不可达四种情况都能一次跑对，不再需要为“逆序输出”单独打补丁。

3. 距离算成 1000、路径直接断开：邻接矩阵的三个初始化陷阱

3.1 无边不能填 0，否则等于所有景点贴在一起

邻接矩阵的第一条铁律：自己到自己填 0，没有路的两个景点填一个足够大的数，有路的填权值。填 0 是最常见的翻车点。如果建图时忘记把整片矩阵先刷成“不通”，Edge数组里残留的是未初始化内存的随机值，某些格子可能正好是一个很小的数，Floyd 就会认为两个本来不通的景点之间有一条 3 米的秘密通道，然后一本正经地给你规划出一条现实中不存在的路线。

/* 建图：先全部置为不可达，再逐条写入真实道路 */ void Creat(AdjMGraph *G, DataType v[], RowColWeight rcw[], int n, int e) { int i, j; ListInitiate(&G->vertices); /* 顶点表清空 */ for (i = 0; i < n; i++) ListInsert(&G->vertices, i, v[i]); /* 10 个景点依次入表 */ G->numOfEdge = e; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { G->Edge[i][j] = (i == j) ? 0 : MaxWeight; /* 关键：先整体刷成不通 */ } } 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; /* 无向图成对写 */ } }

MaxWeight取 1000 是有讲究的。这组数据里最大单边权是 35，10 个景点就算绕最远的路，总长也不会超过 350，1000 留了足够余量。如果哪天把权值单位从“抽象距离”改成“米”，单边动辄三四百米，1000 立刻就不够用了，Floyd 会把一条真实的长路径误判成“比无穷大还长”，从而拒绝更新，最后查询结果仍然停在 1000。改数据的同时必须重新评估这个常量，它不是一个随手写的魔法数字。

3.2 无向图的边要写两遍，漏一半就变成单行道

校园里的路都是双向的，但邻接矩阵不会自动帮你对称。边表里写一条{0, 1, 20}，只代表“0 号景点能到 1 号景点”，反方向仍然是MaxWeight。表现出的现象特别有迷惑性：从学生第二食堂查男生宿舍，路径正常；从男生宿舍查学生第二食堂，直接提示不连通。很多人第一反应是 Floyd 写错了，实际上是建图阶段就少了一半信息。

原始代码的边表里，每条边都成对出现，{0,1,20}和{1,0,20}各写一条，这是对的。但手工维护这种对称性非常脆弱，后续增删景点时漏写一条，故障就会在某个特定方向上冒出来。我一般会在建图函数里只写一次，让代码自动补反向边，就像上面那段G->Edge[rcw[i].col][rcw[i].row] = rcw[i].weight;。这样边表里每条路只写一遍，e = 28也就变成了实际道路条数 14 的两倍，数量关系更清楚。

如果用自动补反向边的方式，边表长度要跟着改，numOfEdge的语义也要统一。这一点在课程设计的报告里容易被追问，建议在注释里写清楚“rcw 中每条记录代表一条双向道路”，避免自己和读者理解不一致。

注意：判断图是否对称，最省事的办法是遍历矩阵比较Edge[i][j]和Edge[j][i]，一旦发现不等，说明建图阶段就有问题，不用往下查 Floyd。

3.3 无穷大用 INT_MAX 会溢出，判定条件也得跟着改

有人觉得 1000 不够“无穷”，换成INT_MAX更严谨，结果算出来的距离是负数。原因很直接：weight[i][k] + weight[k][j]在两个都是INT_MAX的时候会溢出，变成一个很大的负数，而负数永远小于当前距离，于是 Floyd 认为找到了一条负距离的捷径，把weight和path一起写坏。

正确的做法有两条路。一条是继续用有限的MaxWeight，前提是保证它大于图中任意一条可能路径的长度之和，10 个景点、最大边权 35 的场景下 1000 足够安全，这也是原始代码的做法。另一条是坚持用极大值，但在松弛前加判断：

/* 用极大值时，必须先判两端可达，再相加 */ if (weight[i][k] != MaxWeight && weight[k][j] != MaxWeight && weight[i][k] + weight[k][j] < weight[i][j]) { weight[i][j] = weight[i][k] + weight[k][j]; path[i][j] = k; }

两个条件缺一不可。少了前半段，溢出照样发生；少了后半段，本来就直达的短路径会被后面一轮更长的路覆盖。这段判断只在用极大值表示不通时才需要，用有限MaxWeight时可以省掉，但代价是要维护好那个常量的取值范围。我倾向于保留判断，因为它把“不通”这件事显式表达出来了，读代码的人一眼能看出意图，不用去反推 1000 这个数字是怎么来的。

4. 输入景点名提示“不在所提供范围内”：字符串匹配的四个失手点

4.1 scanf("%s") 遇空格就停，带空格的景点名永远查不到

scanf("%s", name)读到第一个空白字符就收手，剩下的内容留在输入缓冲区里。景点名里只要带空格，比如“东区 食堂”，实际存进name的只有“东区”，后面用strcmp去跟完整名称比对，永远不相等，于是走进“找不到该景点”的分支。更麻烦的是，残留的“食堂”会被下一次输入读取到，造成连锁误判，用户看到的现象是“第一次查不到，第二次查了个完全不相干的地方”。

/* 读一整行，去掉尾部换行，再比对 */ char buf[64]; if (fgets(buf, sizeof(buf), stdin) != NULL) { buf[strcspn(buf, "\n")] = '\0'; /* 把换行换成结束符 */ } Information(G, buf);

fgets会把换行符一起读进来，必须用strcspn或strlen手动裁掉，否则缓冲区里存的是“图书馆\n”，跟“图书馆”比对还是不等。sizeof(buf)传的是整个数组大小，fgets最多读sizeof(buf) - 1个字符再加结束符，不会越界，这是它比scanf安全的地方。缓冲区大小 64 字节，在 GBK 编码下够放 31 个汉字，在 UTF-8 下也够放 21 个，对景点名来说绰绰有余。

4.2 缓冲区残留和编码不一致，strcmp 永远不等于 0

比空格更隐蔽的是残留数据。前面用scanf读过菜单选项，用户敲的那个回车还留在缓冲区里，紧接着fgets一读，直接读到空行，传给查询函数的是一串空白。表现就是“我明明输入了景点名，程序说没找到”。解决办法是在切换输入方式的地方清一次缓冲区，或者全程统一用fgets读、再用sscanf或atoi解析数字，不要混着来。

编码问题也值得提一句。同一个景点名，源文件用什么编码保存、终端用什么编码显示，两边不一致时strcmp比的是字节而不是字，看起来一模一样的两个字符串可能相差一个字节。常见现象是：景点名在菜单里显示正常，复制粘贴进去却查不到。这类问题用肉眼看不出来，把两个字符串的长度和每个字节打出来一比对就清楚了。

/* 排查用：把输入串和表内串的字节打出来对比 */ printf("输入长度=%zu\n", strlen(name)); for (i = 0; name[i] != '\0'; i++) printf("%02X ", (unsigned char)name[i]); printf("\n");

还有一个容易被忽略的点：DataType里char name[20]只有 20 字节。GBK 下一个汉字占 2 字节，最多放 9 个汉字；UTF-8 下一个汉字占 3 字节，最多放 6 个。景点名一旦超过这个长度，strcpy或scanf会直接写穿数组，破坏相邻的code和introduction字段，症状是“查询能查到，但代号变成了乱码”。把数组放大到 64 字节，成本几乎为零。

4.3 扫描循环的边界，决定提示走哪条分支

查询函数的骨架是“从头扫到尾，找到就输出，扫完还没找到就提示”。这个逻辑本身没问题，问题出在“怎么判断没找到”。原始写法是在循环外拿循环变量i跟size比较，如果循环内部break了，i停在命中位置，i == size不成立，走输出分支；如果循环自然结束，i == size成立，走提示分支。这套逻辑在size > 0时正确，但如果顶点表为空，i根本没被赋值，比较的是一个未初始化的变量。

/* 用一个显式的命中标记，比复用循环变量可靠 */ int index = -1; for (i = 0; i < G.vertices.size; i++) { if (strcmp(G.vertices.list[i].name, name) == 0) { index = i; break; } } if (index == -1) { printf("未找到景点[%s]，请检查名称是否与菜单一致\n", name); return; } printf("名称：%s\n代号：%d\n简介：%s\n", G.vertices.list[index].name, G.vertices.list[index].code, G.vertices.list[index].introduction);

index初始化为 -1，命中就赋值，扫完还是 -1 就是没找到。这样判断依据和循环变量彻底解耦，顶点表为空、循环提前退出、命中在最后一位，三种情况都不会误判。提示信息里把用户输入的原始字符串打出来，也非常有用，用户自己就能发现是不是多打了一个空格或者打错了字。

5. 点几次菜单就卡死、输错一个字符就刷屏：交互与内存的常见问题

5.1 每次操作完递归调 menu()，点几十次就栈溢出

原始代码里，查询函数执行完最后一行是menu();，菜单函数又在选完分支后调用查询函数。表面上看是“操作完自动回到菜单”，实际上每一次操作都在调用栈上压了一层新的menu，旧的那层永远不返回。操作十次就叠十层，操作一百次就叠一百层，叠到一定深度程序直接崩溃，或者在某些环境里表现为“点了几下突然没反应”。

/* 改成循环 + 唯一出口，栈深度恒定为 1 */ void menu(void) { int choice; while (1) { printf("\n1. 景点信息查询 2. 最短路径查询 0. 退出\n请选择："); if (scanf("%d", &choice) != 1) { /* 非数字输入 */ while (getchar() != '\n') ; /* 清掉这一行剩余字符 */ printf("请输入数字 0/1/2\n"); continue; } switch (choice) { case 1: Information1(); break; case 2: Path1(); break; case 0: return; /* 唯一出口 */ default: printf("没有这个选项，请重新选择\n"); } } }

while (1)配一个return退出，所有分支执行完自然回到循环开头，不产生任何新的栈帧。查询函数里也不要再调menu()，只负责把活干完返回。这样改完之后，点一百次和点一次的内存占用完全一样，“用久了变卡”的现象直接消失。

5.2 scanf 不检查返回值，输错一个字母就无限刷屏

scanf("%d", &choice)遇到字母时返回 0，字母本身留在缓冲区里没被消费。如果代码不检查返回值、直接进 switch，choice保持上一次的旧值，用户会看到同一条查询结果反复刷屏；如果外层是循环，字母永远读不掉，就变成死循环。上面那段代码里if (scanf(...) != 1)和while (getchar() != '\n')配成一对，前者负责发现异常，后者负责把这一行垃圾数据清干净，缺一不可。只清一次getchar()是不够的，用户可能敲了一串字符，必须清到换行为止。

同样的检查要加在所有读数字的地方。课程设计里还有个典型场景：查询最短路径时连续读两个景点名，如果中途输入异常，后一个读到的可能是上一次的残留，错误被放大成“路径算出 0 米”。宁可多写几行校验，也别指望用户输入永远规范。

5.3 剩下的三个坑：全角标点、数组越界、顶点数对不上

第一个坑是全角标点。代码里混进中文引号、全角分号、全角括号，编译报错的位置往往指向下一行，让人以为逻辑写错了，实际是上一行藏了个看不见的全角字符。这类错误在从文档里复制代码时特别高发，血泪经验是：编译报错提示“缺分号”但你明明看到有分号，就把那一行删掉重敲一遍。

第二个坑是路径记录数组越界。用value[MaxVertices]存中转点，count一路自增没有边界检查，路径上中转点一多就写穿数组。10 个顶点的场景下最多 8 个中转点，看起来安全，但如果哪天把景点扩到 20 个，count就可能超过MaxVertices。要么把数组开得足够大，要么在自增前加if (count < MaxVertices)。

第三个坑是顶点数、边数和实际数组长度对不上。n = 10、e = 28是手写的常量，景点表里加了第 11 个景点却忘了改n，Floyd 就只算前 10 个，新景点在查询时永远“不连通”。这类问题不会报错，只会表现为“某个景点怎么查都不对”。比较稳妥的写法是用sizeof(a) / sizeof(a[0])自动算顶点数，边数同理，让人工维护的常量少一个是一个。

6. 快速定位最短路径异常：先验矩阵，再看分叉点，最后手工对一条

图算法的故障排查有个好处：中间结果全是矩阵，随时可以打出来看，不用像并发问题那样靠猜。我现在的习惯是三步走，绝大多数路径异常在第二步就能定位。

第一步，验邻接矩阵。把建图之后的Edge矩阵完整打印出来，重点看三件事：对角线是不是全 0，Edge[i][j]和Edge[j][i]是否相等，不该通的地方是不是真的等于MaxWeight。这一步能挡掉初始化漏刷、无向边漏写、权值填错这三类问题，它们占了建图阶段故障的绝大多数。矩阵不大，10 个景点也就 100 个数字，扫一眼就能看出有没有异常值。

第二步，验path矩阵。路径顺序错乱，九成出在这张表的使用方式上，而不是表本身。打印path之后，随便挑一对景点，看path[i][j]是不是落在一条合理的中转点上。如果表本身正常，而输出还是乱，问题就在还原代码，直接换成第 2 章那段递归函数即可。

第三步，手工对一条最短路径。挑三类用例：一条直达边，验证距离是否等于权值、路径是否只有起终点；一条两跳路径，验证中转点是否被正确打印；一对不连通的景点，验证提示分支是否走到。三类都过，基本可以认为功能正确。如果时间允许，再补一条“反向查询”，起点终点对调，距离应当完全相等，路径应当完全相反。这个对称性检查不需要任何额外数据，却能立刻暴露方向相关的 bug。

/* 自检函数：建图后调用一次，把可疑点直接打出来 */ void CheckGraph(AdjMGraph *G) { int i, j, err = 0; for (i = 0; i < G->vertices.size; i++) { if (G->Edge[i][i] != 0) { /* 对角线必须是 0 */ printf("顶点 %d 自环权值异常：%d\n", i, G->Edge[i][i]); err++; } for (j = i + 1; j < G->vertices.size; j++) { if (G->Edge[i][j] != G->Edge[j][i]) { /* 无向图必须对称 */ printf("边[%d][%d]=%d 与 边[%d][%d]=%d 不对称\n", i, j, G->Edge[i][j], j, i, G->Edge[j][i]); err++; } } } printf("自检结束，可疑项 %d 个\n", err); }

这个函数只做静态检查，不涉及 Floyd，跑一次就能把建图问题筛干净。从那以后，我每次写完建图代码，都强制先跑一遍自检，再去看最短路径结果——毕竟路径算错的时候，你永远不知道是算法写歪了还是数据本身就脏，先排除数据问题，能省掉一大半兜圈子的时间。希望这些排查顺序，能帮你少熬两个晚上。

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