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

1、软件学院课程设计报告书课程名称数据结构设计题目校园导航系统专业班级软件11-04班学号1020010429姓名张鸿雷指导教师刘亮2013年1月1设计时间22设计目的23设计任务24设计内容24.1 需求分析24.2 总体设计34.3 详细设计54.4 测试与分析164.4.1 测试164.4.2 分析184.5 附录185总结与展望25参考文献26成绩评定261设计时间2013年1月20日至2013年1月23日2设计目的数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设计的技术基础。数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。23设计任务要求学生掌握

2、数据结构的应用、算法的编写、类C语言的算法转换成C程序并上机调试的基本方法。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。14设计内容题目：校园导航系统设计任务：给出校园各主要建筑的名称信息及有线路联通的建筑之间的距离，利用校园导航系统计算出给定的起点到终点之间的最近距离及线路。设计要求：1、 输入各建筑信息及线路信息，构建图。2、 计算给定起点到终点之间最近距离的进行线路。3、 输出线路及总距离。4.1 需求分析1 .程序所能达到的功能；(1) CreateDN(MGr

3、aph*G)创建有向网G,储存学校的各个景点。(2) ShortPath(MGraphG,intv0,intpMAX_VMAX_V,intd)求的有向网G中某个顶点到其余顶点的最短路径及其带权长度。(3) menu()目录函数，按照要求选择相应的功能。2、输入的形式和输入值的范围首先输入导航功能号，只能在x至y之间进行选择；要实现两点之间最短路径导航，需输入起点和终点号，输入的起点和终点号在所给景点号里选择；要实现某点到其他点的最短路径，需输入这个顶点号，顶点号也是在所给的景点号里选择。3、输出的形式学校的所有景点，某个景点到其他景点的最短路径，或者两个景点之间的最短路径4、测试数据：输入导航

4、功能x输入起始点和终点号0和16,输出正确的最短路径和路径长度；重新选择导航功能。选择导航功能y,输入，出发点2,输出景点2的简介。选择导航功能3,退出导航系统。若要实现导航功能x时输入错误，输出时就无路经。重新输入起始点，结束点。若要实现功能2时输入错误，就会提示不存在这个地方。4.2 总体设计1、说明本程序中用到的所有抽象数据类型的定义2ADTGraph数据对象V:V是具有相同特性的数据元素的集合，称为顶点集.数据关系R:R=VRVR=(v,w)|v,wCV且P(v,w),<v,w>表示从v到w的弧,谓词P(v,w)定义了弧<v,w>的意义和信息3基本操作P:Int

5、CreateDN(MGraph*G)操作结果：创造有向网GovoidShortpath(MGraphG,intv0,intpMAX_VMAX_V,intd)初始条件：有向网G已创建。操作结果：有向网G的V0定点到其余定点V的最短路径Pv及其带权长度Dv0若Pvw为True,则w是从V0到V当前求得最短路径上的顶点。Finalv为True当且仅当VCS,即已经求得从V0到V的最短路径。voidmenu()初始条件：有向网G已创建。操作结果：选择相应的功能。2、说明主程序的流程图4.2-2主程序流程图3.各程序模块之间的层次(调用)关系主程序模块求最短路径模块构建有向网模块图4,2-3各程序模块之

6、间的层次(调用)关系4.3详细设计从流程图中可以看出来，主函数读取用户指令，根据指令调用函数，最终得到用户想要查询的信息。11) 采用邻接表存储结构，定义的抽象数据类型：2) typedefstructArCell存放构造图的权值(intadj;ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;3) typedefstruct图中顶点表示主要景点，存放景点的编号、名称、简介等信息，charname30;intnum;charintroduction100;infotype;4) typedefstructinfotypevexsMAX_VERTEX_NU

7、M;AdjMatrixarcs;intvexnum,arcnum;MGraph;MGraphb;2.主程序以及主要函数21)主函数voidmain(void)(system("color5f");/*修改控制台的颜色信息，改为白字蓝底的模式*/system("modecon:cols=140lines=130");/*设置批处理运行时窗口大小的*/cmd();2)cmdS数通过这个函数实现选择服务项目的内容voidcmd(void)(chark;b=InitGraph();show1();Menu();while(1)(scanf("n%c&q

8、uot;,&k);switch(k)(case'x':system("cls");show1();Menu();list();ShortestPath_DIJ(&b);printf("欢迎您的使用n");printf("n请您继续选择服务:");break;case'y':system("cls");Menu();list();Search(&b);printf("欢迎您的使用n");printf("n请您继续选择服务:"

9、;);break;case'z':system("cls");printf("1n"printf("感谢使用1n"printf("辽宁工程技术大学1n"printf("智能导航系统1n"printf("1n"exit(0);defaultprintf("输入信息错误！n请输入x或y或z.n");break;3)计算最短路径的迪杰斯特拉算法实现1voidShortestPath_DIJ(MGraph*G)intv,w,i,min,t=0,x,

10、flag=1,v0,v1,have100,k;intfinal20,D20,p2323;while(flag)(printf("请输入起始景点编号:n");scanf("%dH,&v0);if(v0<0|v0>G->vexnum)printf("景点编号不存在！");printf("请输入终止景点编号:n");scanf("%d",&v1);if(v1<0|v1>G>vexnum)printf("景点编号不存在!");if(v0>

11、;=0&&/0<G>vexnun&&/1>=0&&/1<G>vexnum)flag=0;for(v=0;v<G>vexnum;+v)(finalv=0;Dv=G>arcsv0v.adj;for(w=0;w<G>vexnum;+w)pvw=INFINITY;if(Dv<INFINITY)(pvv0=1;pvv=1;Dv0=0;finalv0=1;have0=v0;for(i=1;i<G>vexnum;+i)(min=INFINITY;for(w=0;w<G>v

12、exnum;+w)if(!finalw)if(Dw<min)(v=w;min=Dw;finalv=1;havek=v;k+;for(w=0;w<G>vexnum;+w)if(!finalw&&(min+(G->arcsvw.adj)<Dw)(Dw=min+G->arcsvw.adj;for(x=0;x<G->vexnum;x+)Pwx=pvx;pww=1;for(i=0;i<G->vexnum;i+)(if(pv1havei=1)printf("->%s”,G->);i

13、f(v1-v0)=1)printf("n路径长度：dn",G->arcsv0v1);elseprintf("n路径长度:%dn",Dv1);/ShortestPath_DIJend4)查找函数的建立实现用户对景点查找的实现：voidSearch(MGraph*G)intk,flag=1;while(flag)printf("请输入要查询的景点编号:");scanf("%d",&k);if(k<0|k>G>vexnum)printf("景点编号不存在！请重新输入景点编号:&q

14、uot;);scanf("%d",&k);if(k>=0&&k<G->vexnum)flag=0;printf("111n");printf("|编号|景点名称|简介In");printf("|%-4d|%-16s|%-58s|n",G->vexsk.num,G->,G>roduction);printf("1111n");/Searchend5)对要进行浏览的地区的平面图输出10voidshow1

15、()printf("tt欢迎使用辽丁工程技术大学智能导航系统n"printf("ttt辽丁工程技术大学的户岛校区平向图nn");printf("t学校北门n");printf("t1n");printf("ti行政楼静远楼n");printf("t11n");printf("t1耘慧楼n");printf("t11n");printf("t11n");printf("t体育场尔雅楼n");prin

16、tf("t11n");printf("t二食堂n");printf("t11n");printf("tD楼1n");printf("tE楼一|n");printf("tC楼1n");printf("t11n");printf("t小体育场，篮球场综合楼小拱桥n");printf("t11n");printf("t一食堂1n");printf("t浴池瞅Aftn");)6)用户根

17、据显示的学校景点序号，查询景点信息:voidlist()(printf("学校景点列表:n");printf("0:学校南门");11printf（"1:静远楼"）;printf（"2:耘慧楼"）;printf（"3:尔雅楼"）;printf（"4:小拱桥n"）;printf（"5:A楼"）;printf（"6:B楼"）;printf（"7:一食堂"）;printf（"8:综合楼n"）;print

18、f（"9:行政楼"）;printf（"10:体育场"）;printf（"11:二食堂"）;printf（"12:D楼"）;printf（"13:E楼n"）;printf（"14:C楼"）;printf（"15:浴池"）;printf（"16:篮球场、足球场nn"）;7）目录函数对本系统提供的服务进行提示，以便用户使用:voidMenu（）printf（"n辽宁工程技术大学的产岛校区导游图n"）;printf（&quo

19、t;1n"）;printf（"|x.选择出发点和目的地In"）;printf（"Iy.查看景点信息In"）;printf（"|乙退出系统In"）;printf（"11n"）;printf（"请选择服务"）;128)对无向网的构建以便于实现本系统的功能MGraphInitGraph(void)(MGraphG;inti,j;Gvexnum=17;顶点是17个Garcnum=25;/弧线有25个for(i=0;i<Gvexnum;i+)Gvexsi.num=i;strcpy(G.ve

20、,"学校北门")；strcpy(G.roduction,"学校的正门，行政楼局局耸立，气势宏伟");strcpy(G.,"静远楼");strcpy(G.vexs1"V.introduction,"电控、电信学院用楼，设有图书馆、阅览室等。);strcpy(G.,"耘总楼")；strcpy(G.roduction,”软件、XW学院用楼，设有若干机房，为同学提供更多方便。”)；strcpy(G.vexs3.n

21、ame,"尔雅楼");strcpy(G.roduction,"学生上课、自习的地方。");strcpy(G.,"小拱桥");strcpy(G.roduction,"连接生活区和教学区的桥。");strcpy(G.,"A楼")；strcpy(G.roduction,"男生宿舍");strcpy(G.,"B楼")；strcpy(G.vexs6.in

22、troduction,"女生宿舍");strcpy(G.,"一食堂");strcpy(G.roduction,"食堂，可用饭+吃饭");strcpy(G.,"综合楼");strcpy(G.roduction,"校区内的百货大楼");13strcpy(G.,"行W8");strcpy(G.roduction,”学校行政办公场所，校区最高的建筑"strcpy

23、(G.,"体育场")；strcpy(G.roduction,"运动会举办地");strcpy(G.,"二食堂")；strcpy(Gstrcpy(G.roduction,”校区最实惠的食堂，内后回民餐厅").name,"D楼")；strcpy(Gstrcpy(G.roduction,"男生宿舍");.name,"E楼")；strcpy(G

24、strcpy(G.roduction,"男生宿舍");.name,"C楼")；strcpy(Gstrcpy(G.roduction,"女生宿舍");.name,"浴池")；strcpy(G.roduction,"学生洗澡的地方");strcpy(G.,"篮球场、足球场");strcpy(G.roduction,"比赛以及学生运动的地方&q

25、uot;);for(i=0;i<Gvexnum;i+)for(j=0;j<Gvexnum;j+)Garcsij.adj=INFINITY;G.arcs01.adj=50;G.arcs12.adj=15;G.arcs13.adj=40;G.arcs23.adj=30;G.arcs03.adj=90;G.arcs34.adj=30;G.arcs49.adj=1000;G.arcs45.adj=20;G.arcs56.adj=10;G.arcs67.adj=8;14G.arcs68.adj=12;G.arcs78.adj=7;G.arcs09.adj=30;G.arcs910.adj=5

26、00;G.arcs1011.adj=25;G.arcs1112.adj=8;G.arcs1213.adj=5;G.arcs1314.adj=10;G.arcs1214.adj=10;G.arcs1415.adj=150;G.arcs1516.adj=3;G.arcs515.adj=150;G.arcs415.adj=30;G.arcs111.adj=300;G.arcs814.adj=40;for(i=0;i<Gvexnum;i+).adj;for(j=0;j<Gvexnum;j+)Garcsji.adj=GarcsijreturnG;/InitGraphend153.函数的调用关

27、系图。31、4.4测试与分析4.4.1 测试图4.3-3函数的调用关系图16输入导航功能xt选体服务学馋量点列表:_再夜莆n售圆至2：茬慧楼3：尔雅楼4：小拱桥二月楼6二B楼7：一福堂野综合楼:行政楼工加诔育场11二二春堂12：l4S13：E楼41C楼1口浴池1公篮球场.足球场睛输入起始景点编号:输入起始点和终点号0和16,输出正确的最短路径和路径长度；重新选择导航功能。请输入起始景点编号:请输入终止景点编号:路径长度二153：，学校南门尔雅楼一小拱桥一浴池一篮球场、足球场欢迎您的使用请您继续选择服务：选择导火能y,输入，出发点2,输出景点2的简介。i输入要杳询的景点编号n桐号景点名你静远程简

28、介电控，电信学院用楼，设有图书馆.闾览室等,欢迎您的使用请您嬲续选择服务，选择导力能3,退出导航系统辽大学智能导航系统PriBss己nykeytocontinue若要实现导航功能x时输入错误，输出时就无路经。重新输入起始点，结束点胃输入起始景点编号:卷输入终止景点编号：L12景点编号不存在!请输入起始景点编号*若要实现功能2时输入错误，就会提示不存在这个地方。174.4.2 分析1.调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；在调试的过程中发现在导航功能2中缺少判断语句，使得输入错误顶点时，没有提示出现错误的运行结果，在进行导航功能2之前加一个判断语句就可以了。这次的程序

29、设计主要是设计求最短路径的算法，这个算法比较复杂，我根据书上算法一步步地进行分析，并通过请教同学和上网查相关程序，花费了很长时间在使得这个算法能正常运行。4.5附录123#defineINFINITY10000#defineMAX_VERTEX_NUM40#defineMAX40#include<stdlib.h>#include<stdio.h>#include<conio.h>#include<string.h>typedefstructArCellintadj;/*路径长度*/ArCell,AdjMatrixMAX_VERTEX_NUMMA

30、X_VERTEX_NUM;typedefstruct/*图中顶点表示主要景点，存放景点的编号、名称、简介等信息/charname30;intnum;charintroduction100;/*简介*/infotype;typedefstructinfotypevexsMAX_VERTEX_NUM;AdjMatrixarcs;intvexnum,arcnum;MGraph;MGraphb;voidcmd(void);MGraphInitGraph(void);voidshow1();18voidvoidvoidvoidlist();Menu(void);ShortestPath_DIJ(MGra

31、ph*G);Search(MGraph*G);intLocateVex(MGraph*G,char*v);/*主函数*/voidmain(void)system("color5r);/*修改控制台的颜色信息，改为白字蓝底的模式*/system("modecon:cols=140lines=130");/*设置批处理运行时窗口大小的*/cmd();/*自定义函数*/*cmd函数(根据目录选择要进行的项目voidcmd(void)chark;b=InitGraph();show1();Menu();while(1)scanf("n%c",&

32、k);switch(k)case'x':system("cls");show1();Menu();list();ShortestPath_DIJ(&b);printf(")*/欢迎您的使用n");printf("n请您继续选择服务:");break;case'y':system("cls");Menu();list();Search(&b);printf("欢迎您的使用n");printf("n请您继续选择服务:");break

33、;19case'z':system("cls");printf("1n")printf("|感谢使用In")printf("|辽宁工程技术大学In")printf("|智能导航系统In")printf("11n")exit(0);default:printf("输入信息错误！n请输入x或y或z.n");break;/*迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径，v0为起点*/voidShortestPath_DIJ(MGraph*G

34、).intv,w,i,min,t=0,x,flag=1,v0,v1,have100,k;intfinal20,D20,p2323;while(flag)printf("请输入起始景点编号:n");scanf("%d",&v0);if(v0<0|v0>G->vexnum)printf("景点编号不存在！");printf("请输入终止景点编号:n");scanf("%d",&v1);if(v1<0|v1>G>vexnum)printf("

35、;景点编号不存在!");if(v0>=0&&v0<G->vexnum&&v1>=0&&v1<G>vexnum)flag=0;for(v=0;v<G>vexnum;+v)finalv=0;Dv=G>arcsv0v.adj;for(w=0;w<G>vexnum;+w)pvw=INFINITY;if(Dv<INFINITY)20pvv0=1;pvv=1;)Dv0=0;finalv0=1;have0=v0;for(i=1;i<G>vexnum;+i)(min=I

36、NFINITY;for(w=0;w<G>vexnum;+w)if(!finalw)if(Dw<min)(v=w;min=Dw;)finalv=1;havek=v;k+;for(w=0;w<G>vexnum;+w)if(!finalw&&(min+(G->arcsvw.adj)<Dw)(Dw=min+G->arcsvw.adj;for(x=0;x<G->vexnum;x+)Pwx=pvx;pww=1;)for(i=0;i<G->vexnum;i+)(if(pv1havei=1)printf("-&g

37、t;%s”,G->);)if(v1-v0)=1)printf("n路径长度：dn",G->arcsv0v1);elseprintf("n路径长度：dn",Dv1);ShortestPath_DIJend/*查找函数的建立*/voidSearch(MGraph*G)intk,flag=1;while(flag)21(printf("请输入要查询的景点编号:");scanf("%dH,&k);if(k<0|k>G>vexnum)(printf("景点编号

38、不存在！请重新输入景点编号:");scanf("%d",&k);if(k>=0&&k<G->vexnum)flag=0;printf("111n");printf("|编号|景点名称|简介In");printf("|%-4d|%-16s|%-58s|n",G->vexsk.num,G->,G>roduction);printf("1111n");/Searchendvoidshow1()p

39、rintf("tt欢迎使用辽宁工程技术大学智能导航系统n"printf("ttt让了，槎及木大学胡产岛校区半回囹nn");printf("t学校北门n");printf("t1n");printf("t行政楼静远楼n");printf("t1n");printf("t1耘慧楼n");printf("t1n");printf("t1n");printf("t体育场尔雅楼n");printf(&quo

40、t;t1n");printf("t二食堂n");printf("t1n");printf("tD楼1n");printf("tE楼一n");printf("tC楼n");printf("t1n");printf("t小体育场，篮球场综合楼小拱桥n");printf("t11n");printf("t1一食堂n");printf("t浴池瞅Aftn");22）voidlist（）（prin

41、tf（"学校景点列表:n"）;printf（"0:学校南门"）;printf（"1:静远楼"）;printf（"2:耘慧楼"）;printf（"3:尔雅楼"）;printf（"4:小拱桥n"）;printf（"5:A楼"）;printf（"6:B楼"）;printf（"7:一食堂"）;printf（"8:综合楼n"）;printf（"9:行政楼"）;printf（"1

42、0:体育场"）;printf（"11:二食堂"）;printf（"12:D楼"）;printf（"13:E楼n"）;printf（"14:C楼"）;printf（"15:浴池"）;printf（"16:篮球场、足球场nn"）;）/*目录函数的构建*/voidMenu（）（printf（"n辽宁工程技术大学的产岛校区导游图n"）;printf（"1n"）printf（"|x.选择出发点和目的地In"）prin

43、tf（"Iy.查看景点信息In"）printf（"|乙退出系统In"）printf（"11n"）printf（"请选择服务"）;）/*MGraph函数（图的构建）*/MGraphInitGraph（void）（MGraphG;inti,j;Gvexnum=17;顶点是17个Garcnum=25;/弧线有25个for（i=0;i<Gvexnum;i+）Gvexsi.num=i;strcpy（G.,"学校北门"）;strcpy（G.roduction,&q

44、uot;学校的正门，行政楼高高耸立，气势宏伟"）;23strcpy(G.,"静远楼");strcpy(G.roduction,"电控、电信学院用楼，设有图书馆、长4览室等。);strcpy(G.,"耘总楼"）；strcpy(G.roduction,"软件、工商学院用楼，设有若干机房,为同学提供更多方便。”）；strcpy(G.,"尔雅楼")；strcpy(G.roduction,"学

45、生上课、自习的地方。"）；strcpy(G.,"小拱桥")；strcpy(G.roduction,"连接生活区和教学区的桥。"）；strcpy(G.,"A楼")；strcpy(G.roduction,"男生宿舍"）；strcpy(G.,"B楼")；strcpy(G.roduction,"女生宿舍"）；strcpy(G.,"一

46、食堂")；strcpy(G.roduction,"食堂，可用饭卡吃饭"）;strcpy(G.,"综合楼")；strcpy(G.roduction,"校区内的百货大楼"）;strcpy(G.,"行政楼")；strcpy(G.roduction,"学校行政办公场所，校区最高的建筑")；strcpy(G.,"体育场"）；strcpy(G.roduction,”运动会举办地"）;strcp