校园导航系统数据结构课程设计

1、软件学院课程设计报告书课程名称设计题目专业班级学号姓名指导教师据结构校园导航系统软件10-01班1020010109李名扬徐娇月2021年1月目录1.设计时间22 .设计目的23 .设计任务24 .设计内容24.1 需求分析24.2总体设计34.3详细设计44.4测试与分析124.4.1测试124.4.2分析134.5附录145总结与展望206 .参考文献217 .成绩评定211设计时间2021/01/03至2021/01/062设计目的1 .加深对?数据结构?这一课程所学内容的进一步理解与稳固2 .通过完成课程设计,逐渐培养自己的编程水平；3 .培养给出题目后,构建框架,用计算机解决的水平；

2、4 .通过调试程序积累调试C程序设计的经验；3设计任务给出校园各主要建筑的名称信息及有线路联通的建筑之间的距离,利用校园导航系统计算出给定的起点到终点之间的最近距离及线路.4设计内容5 .1需求分析1 .程序所能到达的功能：(1) map输出辽宁工程技术大学平面图.(2) init()按相应编号输入各个节点内容,对相应路径赋值的函数.(3) menu()菜单函数(4) information()输出简介的函数(5) way()最短路径的输出函数(6) shortestpath()调用弗洛伊德和最短路径输出的函数(7) main()主函数2 .输入的形式和输入值的范围：输入数字和字母：字母：以s

3、查询最短路径；以i查询信息；以e退出程序.数字：从1到11输入.3 .输出的形式：从A到B得最短路径为：A-至卜C-至卜D-至IJ-B最短距离为：xxx米.4 .测试数据包括在正确的输入及输出结果及含有错误的输入及输出结果：当输入为：s111输出为：从浴池到静远楼的最短路径为：浴池-到-B寝室楼-到一-食堂-到一综合楼-到-静远楼最短距离为：180米.数据均为测试数据,与实际有误差,敬请谅解.当输入为：i1输出为：名称：浴池简介：洗澡,吃饭,超市,一应俱全当输入为：e输出为：谢谢使用！当输入为：i13输出为：输入有误！请输入查询地点的编号：5 .2总体设计1 .抽象数据类型定义有向网节点结构体

4、类型typedefstruct(charname10;intnumber;charintroduce100;vertex;2 .主程序模块的整体流程A1、进入主函数,调用init,map和menu函数.menu2、选择“s",调用shortestpath函数,并同时调用floyd和way函数.并返回调用函数.3、选择"i",调用information函数.并返回调用menu函数.4、选择“e,退出.3 .各模块调用关系如下:4 .3详细设计1 .有向网节点结构体类型定义：typedefstiuctcharname10;intnumber;charintroduce

5、100;(vertex;2 .主程序和其它主要函数伪码算法1)主程序intmain./*主函数*/(chari;printf("ttt欢送使用辽宁工程技术大学导航系统nn)；init();map()；/*输出地图,提示使用者*/while(1)(i=menu();switch(i)(case：shortestpath();break;case'i:information();break;case'e:printf(z,nnntttt谢谢使用！n);return(0);default:printf"输入错误！n"break;2赋值init函数void

6、initinti,j;/*从41到73行,对平面图中的各个地点信息进行输入,运用strcpy函数*/ver1.number=1;,"浴池"roduce,“洗澡,吃饭,超市,一应具全n"ver2.number-2;,"老操场;roduce,“思念一下学长们的艰苦生活n"ver3.number=3;,“新体育场;roduce,“假草,球门,尽情施展脚法的好地方n"ve

7、r4.number=4;,"B寝室楼"roduce,“女寝,不解释n"ver5.number=5;,一食堂；roduce,"饭呐,不好吃n；ver6.number=6;,综合楼;roduce,超市,有日用品,各种食品,还有各种营业厅,眼镜店,书店,水果店n；ver7.number=7;,“南大门；roduce,“学校最宏伟的建

8、筑,校友捐赠n"ver8.number=8;,"A寝室楼;roduce,“男寝,我的家n"ver9.number=9;,“尔雅"；roduce,教学楼,有我最爱的411,是根底教学部老师大展身手的地方n"ver10.number=10;,"耘慧楼;roduce,“教学楼,各种上机实验的地方n"ver11.number=11;strcpyver11.n

9、ame,"静远楼;roduce,教学楼,内涵图书馆,足够惊喜n；fori=l;i<=Num;i+/*对存储距离的距离矩阵取值进行初始化,全定义为最大*/forj=l;j<=Num;j+edgeij=Maxedge;fori=l;iNum;i+/*对存储距离的矩阵的取值进行正确赋值,由于我校均往返可达,顾对路径正反同时赋值*/edgeEiZiJ=0;edgel2=edge21=20;edge23=edge32=50;edge25=edge52=50;edge34=edge43=100;edge36=edge63=300;edgel4=edge4

10、l=20;edge45=edge54=30;edge56=edge65=10;edge67=edge761=200;edge6ll=edgell6=120;edge48=edge84=10;edge89=edge98=250;edge910=edge109=50;edge10ll=edgell10=50;edge7ll=edgell7=100;3)输出辽宁工程技术大学平面图的map函数voidmap./*辽宁工程技术大学平面图,给使用程序者以直观熟悉*/printfCtt辽宇工程技术大学大学平面图(括号内为相对应的数字编号)nn);printf(浴池老体育场新体育场一-n)；printffII

11、In)；printffIIn)；printffB寝室楼(4)一食堂(5)综合楼(6)一南大门n");printff|n)；printf(A寝室楼(8)|n)；printf(I|n)；printf(z,尔雅楼耘慧楼(10)静远楼(ll)nn");)4)菜单menu函数charmenu./*菜单函数*/(chari;printf("输入“s以查询最短路径n)；printf("输入“i以查询信息n")；printf("输入“e以退出程序n");printf(请输入对应的英文小写字母,谢谢：nt");scanf("

12、;%s'&i);returni;5)输出地点信息的information函数voidinformation()/*输出简介函数*/inti;while(l)(printf(请输入查询地点的编号：nt")；scanf("%d",&i);if(i<=Num&&i>=l)printf("n名称:%sn#简介:%sn",,roduce);return;)elseprintf("输入有误！");)6)最短路径floyd函数voidfloyd()/*弗

13、洛伊德算法*/(inti=l,j=l,k=l,l=l;for(i=1;i<=Num;i+)for(j=1；j<=Num;j+)(shortestij=edgeij|;pathiU=0;)for(k=l;k<=Num;k+)(for(i=1;i<=Num;i+)for(j=1:j<=Num;j+)if(shortestij>(shortestik+shortestkj)(shortestij=(shortestik+shortestkj);pathiU=pathUJi=k;)7)输出路径way算法voidway(inti,intj)/*最短路径的输出*/(in

14、tk=O,a=i,b=j;if(shortestij!=Maxedge)(printf("n%>y<%s®J%s的最短路径为:n",,);printf("%s",);while(pathij!=O)(ktpathi皿；while(pathik!=0)(k=pathik;)printf(n-lj-%s');i=k;)printf("-到-%s;n",verjLname);printf("n最短距离为:%d米.n",s

15、hortestab);printf(n数据均为测试数据,与实际有误差,敬请谅解Ann)；)elseprintf("从s不能到达$.",,);)8)调用floyd和way的最短路径shortestpath算法voidshortestpath()/*寻找最短路径*/inti=O,j=O;while(l)(printf("请输入要查询的两点的编号：(以空格间隔)");scanf("%d%d",&i,&j);if(i<=Num&&i>0&&j<

16、;=Num&&j>0)(floyd();way(i,j);return;)3.函数的调用关系main1initmapmenui.Seshortestpathinformationfloydexitway4. 4测试与分析4.4.1测试1)翻开程序后,出现我校平面图和菜单项选择项,如下图D:CYuVanbinwwtemp.exe欢送使用辽宁工程麻天学导航系统辽宁工程技术大学大学平面图(括号内为相对应的数字编号)浴池老体育场新体育场B寝室楼(4)-食堂(5)综合楼(6)南大门IIA寝室楼(8)III一尔雅楼耘慧楼(1.)静远楼(11)输入“s以查询最短路径输入“i以查询信息输

17、入"以退出程序请输入对应的英文小写字母,谢谢：2)选“i,查询对应地点的信息,如输入“3,而后会继续输出菜单,如下图输入“5以查询最短路径输入以查询信息输入飞'以退出程序清输入对应的英文小写字母,谢谢；*1请输入查询地点的编号,30名称：新体育场工简介：假草,球门,尽情施展脚法的好地方输入“b以查询最短路径输入"i以查询信息输入“6以退出程序请输入对应的英文小写字母,谢谢：3)选“s,查询两点之间的信息,如输入“111,而后会继续输出菜单,如下图输入以查询最短路径输入“i以查询信息输入%"以退出程序请输入对应的英文小写字母,谢谢：请输入要查询的两点的编号：

18、以空格间隔111从浴池到静远楼的最座路径为：浴池-到-B寝室楼-到一一食堂-到一综合楼-到-静远楼;最短距离为；180米.数据均为测试数据,与实际有误差,敬请谅解、输入以查询最短路径输入"i以查询信息输入“e以退出程序请输入对应的英文小写字母,谢谢：4选“e,推出程序,如下图输入力"以查询最短路径输入“i以查询信息输入%以退出程序请输入对应的英文小写字母,谢谢；谢谢使用!Pressanykeytocontinue4.4.2分析1 .本次作业的核心是利用弗洛伊德算法计算给定有向网中两点最短距离；给出有向网中所要求点的信息.在调试过程中,除了简单语法错误外,就是对弗洛伊德算法的

19、理解和实现,以及菜单的设置,这是我以前没有实现过的.出于简单化,并没有对有向图中各个点进行输入,而是在程序中直接赋值.2 .在对各个功能操作的实现上,由于有弗洛伊德算法时间复杂度大多数是0n3,空间上增加了二维数组,空间复杂度为o(n+s).4.5附录源程序代码及必要注释.#include<stdio.h>#inckide<string.h>#defineNum11/*测试使用H一个地点,直接定义*/#defineMaxedge32760/*最大£巨离次/typedefstruct/*定义对各个地点信息存储的结构体类型*/(charname10;intnumb

20、er;charintroduce(100;(vertex;vertexverNum;/*定义结构体数组*/intedgeNumNum;intshortestNumNum;intpathNumNum;voidmap./*辽宁工程技术大学平面图,给使用程序者以直观熟悉*/(printf(、t辽宇工程技术大学大学平面图(括号内为相对应的数字编号)nn)；printf("浴池(1)老体育场(2)新体育场printf("IIIln");printf("IIIln");printf("B寝室楼(4)-食堂(5)综合楼(6)南大门")；p

21、rintf("Il'n)；printf("A寝室楼(8)ln");printf("Iln");printf("尔雅楼(9)耘慧楼(10)静远楼(11)nn)；voidinit()intij;/*从41到73行,对平面图中的各个地点信息进行输入,运用strcpy函数*/ver1.number=1;strcpyver1Lname,浴池roduceJ洗澡,吃饭,超市,一应具全n"ver2.number=2;strcpyver2.vame,"老操场"

22、roduceJ思念一下学长们的艰苦生活n"ver3.number=3;,新体育场roduceJ假草,球门,尽情施展脚法的好地方n"ver4.number=4;,HB寝室楼；roducej女寝,不解释n"ver5.number=5;/一食堂''；roduce,饭呐,不好吃n"ver6.number=6;,"综合楼strcpyver

23、6.introduce,"超市,有日用品,各种食品,还有各种营业厅,眼镜店,书店,水果店n；ver7.number=7;J南大门roduce,"学校最宏伟的建筑,校友捐赠n"ver8.number=8;,"A寝室楼,；roduce,"男寝,我的家n"ver9.number=9;,尔雅roduce,"教学楼,有我最爱的411,是根底教学部老师大展身手的地方

24、n"ver10.number=10:strcpy(,"耘慧楼)strcpy(roduce,"教学楼,各种上机实验的地方n")；ver11.number=11;strcpy(,"静远楼strcpy(roduce,"教学楼,内涵图书馆,足够惊喜n");for(i=l;i<=Num;i+)/*对存储距离的距离矩阵取值进行初始化,全定义为最大*/for(j=l;j<=Num;j+)edgeij=Maxedge;)for(i=l;iv=Num;i+

25、)/*对存储距离的矩阵的取值进行正确赋值,由于我校均往返可达,顾对路径正反同时赋值*/edgeii=0;)edgel2=edge2l=20;edge23=edge32=50;edge25=edge52=50;edge34=edge43=100;edge36=edge63=300;edge14=edge4l=20;edge45=edge54=30;edge56=edge65=10;edge67=edge76=200;edge61l=edgell6=120;edge48=edge84=10;edge89=edge98=250;edge910=edge109=50;edge1011=edgelll0

26、=50;edge711=edgell7=l00;)charmenu()/*菜单函数*/(chari;printf("输入“s以查询最短路径n)；printf("输入“i以查询信息n)；printf("输入“e以退出程序n)；printf(请输入对应的英文小写字母,谢谢：nf);scanf("%s",&i);returni;)voidinformation()/*输出简介函数*/inti;while(l)(printf(请输入查询地点的编号：iif);scanf("%d",&i);if(i<=Num&am

27、p;&i>=l)printf("n名称:%sn#简介:%sn",,roduce);return;)else(printf("输入有误！)voidfloyd./*弗洛伊德算法*/(inti=l,j=l,k=l,l=l;for(i=1;i<=Num;i+)for(j=l;j<=Num;j+)shortestij=edgeij;pathiU=O;)for(k=l;k<=Num;k+)for(i=l;i<=Num;i+)for(j=l;j<=Num;j+)if(shortestij>(sh

28、ortestik+shortestkj)(shortestij=(shortestik+shortestk|j);pathiUl=pathUi=k;)voidway(inti,intj)/*最短路径的输出*/intk=O,a=i,b=j;if(shortestij!=Maxedge)(printf("n%M%s到$的最短路径为:n",,);printf(1,%s",);while(pathij!=O)k=pathiU；while(pathik!=O)k=pathik;1printf("-®J-%s');i=k;)printf("-到-%s;n",);printf("n最短距离为:%d米.n",shortestab);printf(n数据均为测试数据,与实际有误差,敬请谅解Ann);elseprintf("从s不能到达$.",,)