1、3设计任务给出校园各主要建筑的名称信息及有线路联通的建筑之间的距离,利用校园导航系统计算出给定的起点到终点之间的最近距离及线路。4 设计内容 需求分析 1程序所能达到的功能:(1) map输出辽宁工程技术大学平面图。(2) init()按相应编号输入各个节点内容,对相应路径赋值的函数。(3) menu()菜单函数(4) information()输出简介的函数(5) way()最短路径的输出函数(6) shortestpath()调用弗洛伊德和最短路径输出的函数(7) main()主函数2输入的形式和输入值的范围:输入数字和字母: 字母:以s查询最短路径;以i查询信息;以e退出程序。 数字:从
2、1到11输入。3输出的形式:从A到B得最短路径为: A-到-C-到-D-到-B 最短距离为:xxx米。4测试数据包括在正确的输入及输出结果及含有错误的输入及输出结果:当输入为:s 1 11 输出为:从浴池到静远楼的最短路径为: 浴池-到-B寝室楼-到-一食堂-到-综合楼-到-静远楼180米。 数据均为测试数据,与实际有误差,敬请谅解。i 1 名称:浴池 简介:洗澡,吃饭,超市,一应俱全e 输出为:谢谢使用!i 13 输入有误!请输入查询地点的编号: 总体设计1抽象数据类型定义有向网节点结构体类型typedef struct char name10 ; int number; char intr
3、oduce100;vertex;2主程序模块的整体流程 1、进入主函数,调用init,map和menu函数。2、选择“s”,调用shortestpath函数,并同时调用floyd和way函数。并返回调用menu函数。3、选择“i”,调用information函数。4、选择“e”,退出。3.各模块调用关系如下:详细设计1.有向网节点结构体类型定义:2. 主程序和其它主要函数伪码算法1)主程序int main()/*主函数*/ char i; printf(ttt欢迎使用辽宁工程技术大学导航系统nn); init(); map();/*输出地图,提示使用者*/ while (1) i=menu()
4、; switch(i) case s:shortestpath();break;iinformation();eprintf(nnntttt谢谢使用!nreturn(0); default :输入错误! 2)赋值init函数void init() int i,j;/*从41到73行,对平面图中的各个地点信息进行输入,运用strcpy函数*/ ver1.number =1; strcpy(ver1.name,浴池 strcpy(ver1.introduce,洗澡,吃饭,超市,一应具全n ver2.number =2; strcpy(ver2.name,老操场 strcpy(ver2.introd
5、uce,怀念一下学长们的艰苦生活n ver3.number =3; strcpy(ver3.name,新体育场 strcpy(ver3.introduce,假草,球门,尽情施展脚法的好地方n ver4.number =4; strcpy(ver4.name,B寝室楼 strcpy(ver4.introduce,女寝,不解释n ver5.number =5; strcpy(ver5.name,一食堂 strcpy(ver5.introduce,饭呐,不好吃n ver6.number =6; strcpy(ver6.name,综合楼 strcpy(ver6.introduce,超市,有日用品,各种
6、食品,还有各种营业厅,眼镜店,书店,水果店n ver7.number =7; strcpy(ver7.name,南大门 strcpy(ver7.introduce,学校最宏伟的建筑,校友捐赠n ver8.number =8; strcpy(ver8.name,A寝室楼 strcpy(ver8.introduce,男寝,我的家n ver9.number =9; strcpy(ver9.name,尔雅 strcpy(ver9.introduce,教学楼,有我最爱的411,是基础教学部老师大展身手的地方n ver10.number =10; strcpy(ver10.name,耘慧楼 strcpy(
7、ver10.introduce,教学楼,各种上机实验的地方n ver11.number =11; strcpy(ver11.name,静远楼 strcpy(ver11.introduce,教学楼,内涵图书馆,足够惊喜n for(i=1;i=Num;i+)/*对存储距离的距离矩阵取值进行初始化,全定义为最大*/ for(j=1;jj+) edgeij=Maxedge;i+)/*对存储距离的矩阵的取值进行正确赋值,由于我校均来回可达,顾对路径正反同时赋值*/ edgeii=0; edge12=edge21=20; edge23=edge32=50; edge25=edge52=50; edge34
8、=edge43=100; edge36=edge63=300; edge14=edge41=20; edge45=edge54=30; edge56=edge65=10; edge67=edge76=200; edge611=edge116=120; edge48=edge84=10; edge89=edge98=250; edge910=edge109=50; edge1011=edge1110=50; edge711=edge117=100;3)输出辽宁工程技术大学平面图的map函数void map()/*辽宁工程技术大学平面图,给使用程序者以直观认识*/tt辽宁工程技术大学大学平面图(括
9、号内为相对应的数字编号)nn 浴池(1)老体育场(2)新体育场(3)n | | | |n B寝室楼(4)一食堂(5)综合楼(6)南大门(7)n | |n A寝室楼(8) |n 尔雅楼(9)耘慧楼(10)静远楼(11)nn4)菜单menu函数char menu()/*菜单函数*/输入“s”以查询最短路径n输入“i”以查询信息n输入“e”以退出程序n请输入对应的英文小写字母,谢谢:nt scanf(%s,&i); return i;5)输出地点信息的information函数void information()/*输出简介函数*/ int i; while(1)%d if(i=1) printf(
10、n名称:%sn#简介:%sn,veri.name,veri.introduce); return; else6)最短路径floyd函数void floyd()/*弗洛伊德算法*/ int i=1,j=1,k=1,l=1;i+) for(j=1; shortestij=edgeij; pathij=0; for(k=1;k(shortestik+shortestkj) shortestij=(shortestik+shortestkj); pathij=pathji=k; 7)输出路径way算法void way(int i,int j)/*最短路径的输出*/ int k=0,a=i,b=j; i
11、f(shortestij!=Maxedge) printf(n%从%s到%s的最短路径为:,veri.name,verj.name);,veri.name); while(pathij!=0) k=pathij; while(pathik! k=pathik;-到-%s,verk.name); i=k;-到-%s;,verj.name );n最短距离为:%d米。,shortestab);n数据均为测试数据,与实际有误差,敬请谅解.nn else从%s不能到达%s。,veri.name ,verj.name );8)调用floyd和way的最短路径shortestpath算法void short
12、estpath()/*寻找最短路径*/ int i=0,j=0;请输入要查询的两点的编号:(以空格间隔) scanf(%d%di,&j);0&j0) floyd(); way(i,j);3. 函数的调用关系exit测试与分析测试1)打开程序后,出现我校平面图和菜单选项,如图所示2)选“i”,查询对应地点的信息,如输入“3”,而后会继续输出菜单,如图所示3)选“s”,查询两点之间的信息,如输入“1 11”,而后会继续输出菜单,如图所示4)选“e”,推出程序,如图所示分析1.本次作业的核心是利用弗洛伊德算法计算给定有向网中两点最短距离;给出有向网中所要求点的信息。在调试过程中,除了简单语法错误外,
13、就是对弗洛伊德算法的理解和实现,以及菜单的设置,这是我以前没有实现过的。出于简单化,并没有对有向图中各个点进行输入,而是在程序中直接赋值。2.在对各个功能操作的实现上,由于有弗洛伊德算法时间复杂度大多数是O(n3),空间上增加了二维数组,空间复杂度为O(n+s)。 附录源程序代码及必要注释。#include#define Num 11/*测试使用十一个地点,直接定义*/#define Maxedge 32760/*最大距离*/typedef struct/*定义对各个地点信息存储的结构体类型*/vertex verNum;/*定义结构体数组*/int edgeNumNum;int shortestNumNum;int pathNumNum; ,