课程设计说明书课程名称：专业：班级：设计人：目录1需求分析说明 (2)1.1 问题重述 (2)1.2测试数据 (3)1.2.1正常数据 (3)1.2.2边缘数据（易错数据） (4)2概要设计说明 (6)2.1 程序的逻辑结构与存储结构 (6)2.2数据的具体存储方式概述 (6)2.3用到的函数概述 (6)3详细设计说明 (8)3.1程序的流程图 (8)3.2程序的具体实现 (11)4调试分析 (13)4.1正常数据的测试 (13)4.2边缘数据的测试 (17)5课程设计总结 (22)1需求分析说明1.1 问题重述要求采用一定的数据结构表示出学校的校园景点平面图，并且能够回答有关景点信息的查询、浏览路径的选择等问题。
具体要求如下：程序输入的第一行应为数据的组数。
每组数据的第一行为3个整数placeNum、pathNum、operatorNum，分别对应校园景点的数量、景点间道路的数量、查询请求数量。
随后的一行为景点编号从1开始的placeNum个100以内的整数，依次代表每个景点的好玩度。
之后又有pathNum行，每行有3个整数，依次代表起始景点、终止景点、景点路径长度。
最后又operatorNum行，每行有一个整数代表操作数。
如果操作数为0，则继续输入一个景点place和要增加的好玩度addfavor，代表将place景点和与该景点直接连通的好玩度提高addfavor。
如果操作数为1，则继续输入一个景点place，代表查询景点place 的好玩度。
如果操作数为2，则继续输入一个起始景点startPlace、终止景点endPlace、道路长度weight，代表在startPlace、endPlace之间建立一条长度为weight的直接通路。
如果操作数为3，则继续输入一个起始景点startPlace、终止景点endPlace，代表查询startPlace、endPlace之间的最短道路距离。
如果两景点间不连通则输出”No such path.”。
以上每次查询操作都输出一行。
1.2测试数据1.2.1正常数据第一组：15 3 575 34 22 83 771 3 404 5 95 2 521 50 4 23 1 42 3 5 773 1 4第二组：14 4 666 42 87 691 2 111 3 234 2 93 4 191 30 1 101 33 1 43 2 31 41.2.2边缘数据（易错数据）第一组：14 3 410 20 30 401 2 101 3 201 2 203 1 22 13 303 1 33 1 4第二组：13 1 510 20 301 2 101 12 23 203 1 30 1 101 32概要设计说明2.1 程序的逻辑结构与存储结构题目要求表示出学校的校园景点平面图，因此在逻辑结构上我们可以用图来表示。
又因为景点与景点之间的道路有长度信息，所以我们用图中的无向网作为数据结构。
无向网中的顶点表示各景点，其中存有景点的编号等信息，网中的边表示景点之间的道路，其中可以存放道路的信息。
在存储结构上我们可以采用图的邻接矩阵和邻接表。
由于之后题目要求可以查询某景点到另一景点的最短路径。
因此我们采用图的邻接矩阵作为存储结构。
2.2数据的具体存储方式概述定义结构体AMGraph用于储存景点数目、各景点的关系及道路长度，内部有邻接矩阵、int类型的变量VexNum代表顶点数目。
int类型数组favorNum用于存储每个景点的游客好玩度。
int 类型二维数组favorMatrix用于标记存储景点录入完成后的直接连通的景点。
2.3用到的函数概述void InitMatrix(AMGraph &G){...}:图的初始化函数，将图的邻接矩阵初始化，主对角线元素全部为0，其他元素全部为MaxInt。
void ShortPath_Floyd(AMGraph &G，int startPlace, int endPlace){...}：部分弗洛伊德函数，形参有需要查询最短路径的图和起始景点，终止景点。
作用为单独对某些增加的道路所连的两景点实现部分弗洛伊德算法，将弗洛伊德算法的时间复杂度由O(n3)变为O(n2)。
该函数的思想如下：因为所有景点间只有两个景点的道路长度发生了变化，而起始景点startPlace到其他景点的道路长度没有变化且终止景点endPlace到其他景点的道路长度没有变化。
所以只有其他景点通过startPlace或者endPlace到达别的景点的最短路径发生了变化。
因此我们就可以把原弗洛伊德算法里的三个循环变量去掉一个中间变量，将其替换为startPlace和endPlace。
函数也就变成了最外层循环控制起点，内层循环控制终点的嵌套二层for循环。
3详细设计说明3.1程序的流程图3.2程序的具体实现程序开始后，首先输入数据组数caseNum。
caseNum不减为0则开始以下循环，否则结束程序。
①输入景点数placeNum、道路数pathNum、操作数operNum。
②初始化favorNum、favorMatrix，调用初始化图的函数。
③循环placeNum次输入各景点的好玩度。
④循环pathNum次输入起始景点、终止景点、道路长度。
判断如果图中已经存在比该长度小的道路长度则继续输入，否则并将其存入图G中。
⑤循环operNum次输入操作数operatorNum，执行以下判断。
Ⅰ.如果operatorNum = 0则输入景点place、要增加的好感度addFavor。
先将place自己的好感度增加addFavor。
favorNum[place] +=addFavor;循环placeNum次，判断favorMatrix里从place到各景点是否是直接连通的。
如果是连通的，favorNum里直接连通的景点的好玩度都加addFavor。
否则继续判断下一个景点。
Ⅱ.如果operatorNum = 1则输入景点place。
输出该景点的好感度favorNum[place]。
Ⅲ.如果operatorNum = 2则输入起始景点startPlace、终止景点endPlace、道路长度weight。
判断如果图中已经存在比该长度小的道路长度则继续，否则并将其存入图G中。
调用部分弗洛伊德函数，单独计算修改后的最短路径。
判断图的邻接矩阵arcs[startPlace][endPlace]是否为0或者为MaxInt。
若是，则输出No such path.否则，输出最短路径。
Ⅳ.如果operatorNum = 3则输入起始景点startPlace、终止景点endPlace，判断更新最短路径标志flag是否为1。
如果为1，则调用部分弗洛伊德函数。
令flag=0。
否则继续执行。
判断图的邻接矩阵arcs[startPlace][endPlace]是否为0或者为MaxInt。
若是，则输出No such path.否则，输出最短路径。
4调试分析4.1正常数据的测试第一组输入：15 3 575 34 22 83 771 3 404 5 95 2 521 50 4 23 1 42 3 5 773 1 4输出：Case #1:5 : 77No such path.1 -> 4 : 126分析：输入为1组数据。
一共5个景点，景点间共3条道路，有5次查询请求。
从1景点到5景点的好玩度依次是75 34 22 83 77。
景点1到3的道路长度为40，景点4到5的道路长度为9，景点5到2的道路长度为52。
操作数为1，输入为景点5。
代表查询景点5的好玩度，输出5的好玩度为77。
操作数为0，输入为景点4，需增加的好玩度为2。
代表4和与4直接连通的景点好玩度都增加2。
所以4和5的好玩度分别增加为85、79。
操作数为3，输入起始景点1、终止景点4。
代表查询景点1到4的最短路径。
所以输出”No such path.”。
操作数为2，输入起始景点3、终止景点5、道路长度77。
代表在景点3和5之间新建长度为77的通路。
操作数为3，输入起始景点1、终止景点4。
代表查询景点1到4的最短路径。
因为上面新建了一条道路，导致1和4连通。
所以输出最短路径126。
第二组输入：14 4 666 42 87 691 2 111 3 234 2 93 4 191 30 1 101 33 1 43 2 31 4输出：3 : 873 : 971 -> 4 : 202 ->3 ：284 ：69分析：输入为1组数据。
一共4个景点，景点间共4条道路，有6次查询请求。
从1景点到4景点的好玩度依次是66 42 87 69。
景点1到2的道路长度为11，景点1到3的道路长度为23，景点4到2的道路长度为9，景点3到4的道路长度为19。
操作数为1，输入为景点3。
代表查询景点3的好玩度，输出3的好玩度为87。
操作数为0，输入为景点1，需增加的好玩度为10。
代表1和与1直接连通的景点好玩度都增加10。
所以1、2和3的好玩度分别增加为76、52、97。
操作数为1，输入为景点3。
代表查询景点3的好玩度，输出3的好玩度为97。
操作数为3，输入起始景点1、终止景点4。
代表查询景点1到4的最短路径。
所以输出最短路径20。
操作数为3，输入起始景点2、终止景点3。
代表查询景点2到3的最短路径。
所以输出最短路径28。
操作数为1，输入为景点4。
代表查询景点4的好玩度，输出4的好玩度为69。
4.2边缘数据的测试第一组输入：14 3 410 20 30 401 2 101 3 201 2 203 1 22 13 303 1 33 1 4输出：1 ->2 : 10 1 ->3 : 20 No such path.分析：输入为1组数据。
一共4个景点，景点间共3条道路，有4次查询请求。
从1景点到4景点的好玩度依次是10 20 30 40。
景点1到2的道路长度为10，景点1到3的道路长度为20，景点1到2间还有1条长度为20的道路。
注意在计算最短路径时应用10计算，长路径不能覆盖短路径。
操作数为3，输入起始景点1、终止景点2。
代表查询景点1到2的最短路径。
所以输出最短路径10。
操作数为2，输入起始景点1、终止景点3、道路长度30。
代表在景点1和3之间新建长度为30的通路。
但由于1和3之间已经有长度为20的道路了，所以在计算最短路径时应用20计算。
操作数为3，输入起始景点1、终止景点4。
代表查询景点1到4的最短路径。
所以输出“No such path.”。
第二组：输入：13 1 510 20 301 2 101 12 23 203 1 30 1 101 3输出：1 : 101 -> 3 : 30 3 : 30分析：输入为1组数据。