c语言校园导游系统课程设计

《c语言校园导游系统课程设计》由会员分享，可在线阅读，更多相关《c语言校园导游系统课程设计（21页珍藏版）》请在金锄头文库上搜索。

1、海南大学课程名称课程名称数据结构数据结构（基于基于 C 语言）课程设计语言）课程设计题题目目校园导游程序的设计与实现校园导游程序的设计与实现院院系系信息科学技术学院信息科学技术学院班班级级通信工程通信工程 B B 班班学生姓名学生姓名史兵全史兵全指导教师指导教师吴泽辉吴泽辉日日期期 2014.12.15.-2015.1.2014.12.15.-2015.1.7 7软件专题训练任务书软件专题训练任务书软件专题训练题目校园导游程序姓名史兵全学号20121613310 116专业班级12 级通信 B 班组别组长同组成 员 指导教 师吴泽辉专题训 练目的通过校园导游程序的设计与实现， 熟 1 练掌 7

2、 握图型结构在实际问题 中的应用。专题训 练环境运行环境为 Visual C+ 6.0课程设 计任务 和要求设计校园导游程序，基本要求：1咨询以用户和计算机的对话方式进行，由用户输入起始点和终点，输出信息：最短路径是多少？并指出所经过的场所。2、计算并记录从校门口到各个场所的最短路径，即求单源点到其它各个场所的最短路径。3、提供校园中任意场所的问路查询，即求任意两点之间的最短路径。参考 文献1、严蔚敏等. 数据结构（C 语言版）. 清华大学出版社 2004 2、谭浩强. C 语言程序设计. 清华大学出版社. 2002 3、李春保. 数据结构教程上机实验指导. 清华大学出版社. 2005校园导游

3、程序校园导游程序一、简介一、简介1设计目的：通过校园导游程序的设计与实现，熟练掌握图型结构在实际问题中的应用。2问题的描述：设计一个校园模拟导游程序，为新生或来访的客人通过与机器的“对话“提供最短路径的信息查询服务。 1任意选取 n 个场所，构成一个无向带权图，图中顶点表示场所，边上的权值表示两点间的距离，图的存储结构可采用带权的邻接矩阵。2咨询以用户和计算机的对话方式进行，由用户输入起始点和终点，输出信息：最短路径是多少？并指出所经过的场所。3、计算并记录从校门口到各个场所的最短路径，即求单源点到其它各个场所的最短路径。4、提供校园中任意场所的问路查询，即求任意两点之间的最短路径。二、数据结

4、构的设计：二、数据结构的设计：由于各个场所通过校园中的道路相连， 各个场所和连接它们的道路构成了整个校园的地理环境， 所以使用图这种数据结构对他们去进行描述。以图中的顶点表示校园内各个场所，应包含场所名称、代号、简介等信息；以边表示连接各个场所的道路，应包含路径的长度等信息；顶点和边均使用结构体定义，整个图的数据结构采用教材中介绍的带权的邻接矩阵方法。二、数据结构的设计：二、数据结构的设计：typedef struct ArCellint adj;/路径长度ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct/图中顶点表示主要景

5、点，存放景点的序号、名称、介绍等信息，char name30;int num;char introduction100;/简介infotype;typedef structinfotype vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;MGraph;MGraph b;void cmd(void)int i;b=InitGraph();Menu();scanf(“%d“,while(i!=4)switch(i)case 1:Browser(Menu();break;case 2:ShortestPath_DIJ(Menu();break;

6、case 3:Floyd(Menu();break;case 4:exit(1);break;default: printf(“输入序号不存在,请重新输入“);break;scanf(“%d“,MGraph InitGraph(void)MGraph G;int i,j;G.vexnum=10;G.arcnum=14;for(i=0;iG-vexnum)printf(“输入错误， 景点序号不存在!请再次输入景点序号:“);scanf(“%d“,if(v0=0for(v=0;vvexnum;v+)finalv=0;Dv=G-arcsv0v.adj;for(w=0;wvexnum;w+)pvw=0

7、;if(Dvvexnum;i+)min=INFINITY;for(w=0;wvexnum;w+)if(!finalw)if(Dwvexnum;w+)if(!finalwfor(x=0;xvexnum;x+)pwx=pvx;pww=1;for(v=0;vvexnum;v+)if(v0!=v) printf(“%s“,G-vexsv0.name);for(w=0;wvexnum;w+)if(pvwt+;if(tG-vexnum-1/ShortestPath_DIJendvoid Floyd(MGraph *G)int v,u,i,w,k,j,flag=1,p101010,D1010;for(v=0

8、;vvexnum;v+)for(w=0;wvexnum;w+)Dvw=G-arcsvw.adj;for(u=0;uvexnum;u+)pvwu=0;if(Dvwvexnum;u+)for(v=0;vvexnum;v+)for(w=0;wvexnum;w+)if(Dvu+Duwvexnum;i+)pvwi=pvui|puwi;while(flag)printf(“请输入始点和终点的序号:“);scanf(“%d%d“,if(kG-vexnum|jG-vexnum)printf(“景点序号错误!请再次输入始点和终点的序号:“);scanf(“%d%d“,if(k=0printf(“%s“,G-ve

9、xsk.name);for(u=0;uvexnum;u+)if(pkjuprintf(“%s“,G-vexsj.name);printf(“ 总路线长%dmn“,Dkj);/Floyd endint LocateVex(MGraph *G,char* v)int c=-1,i;for(i=0;ivexnum;i+)if(strcmp(v,G-vexsi.name)=0)c=i;break;return c;MGraph * CreatUDN(MGraph *G)int i,j,k,w;char v120,v220;printf(“输入图的顶点数,弧数:“);scanf(“%d%d“,print

10、f(“输入景点的编号:、名称、介绍:n“);for(i=0;ivexnum;i+)printf(“景点序号:“);scanf(“%d“,printf(“景点名称:“);scanf(“%s“,G-vexsi.name);printf(“景点介绍:“);scanf(“%s“,G-vexs-introduction);for(i=0;ivexnum;i+)for(j=0;jvexnum;j+)G-arcsij.adj=INFINITY;printf(“请输入路径长度:n“);for(k=0;karcnum;k+)printf(“第%d 条边:n“,k+1);printf(“景点对(x,y):“);s

11、canf(“%s“,v1);scanf(“%s“,v2);printf(“路径长度:“);scanf(“%d“,i=LocateVex(G,v1);j=LocateVex(G,v2);if(i=0G-arcsji=G-arcsij;return G;void print(MGraph *G)int v,w,t=0;for(v=0;vvexnum;v+)for(w=0;wvexnum;w+)if(G-arcsvw.adj=INFINITY)printf(“);else printf(“%-7d“,G-arcsvw.adj);t+;if(t%G-vexnum=0)printf(“n“);旅客进行查

12、询：1. 查看校园各景点 2. 查看所有游览线路； 3. 选择始点和终点 4. 退出程序三、功能（函数）设计：三、功能（函数）设计：一一本程序从总体上分为四个功能模块，分别为： (1)查看校园各景点，这一功能主要为来客提供要查的信息。 （2） 查看所有游览线路,这一功能主要提供来客所要到达目的地的所有的线路，方便选择最短的的路线。 （3）选择始点和终点 ，这一功能的实现为了找出所走线路中的最短路径（4）. 退出程序二，流程图如下（1）程序功能介绍和操作提示模块选项操作菜 单查看校园各 景点查看所有游 览路线选择始点 和终点退出程序（2）查看所有游览线路开始用求迪杰斯特拉算 法出中转最少的路输入

13、 v0,vv0,v 合理v0=v递归调用此算法输出中转最少的路径v0,v 直接到达结束NYYN YN权值小于无穷带权最少的路径（3）选择始点和终点开始初始化 pathij,distij用弗洛伊德算法 计算最小路径输入 vi,vjvi,vj 合理输出最短路径结束NYYNdistik+distkj distijdistij=distik+distkj; pathij=JoinList(pathik,pathk j);调用 JoinList()和 Addtail()四、界面设计：四、界面设计：本程序界面本着易于操作简单整洁而不失美观的理念， 采用数字对应功能选项， 结合详细的操作提示， 使得操作方便

14、快捷， 界面清晰明朗。函数 MGraph InitGraph():初始化图。函数 void Menu()：创建菜单。函数 void Browser(MGraph *G)：浏览全景。函数 void Search(MGraph *G)：查询某点信息。函数 void Floyd(MGraph *G)：查询任意两点之间的最短路径。函数 void ShortestPath_DIJ(MGraph * G)：查询校门口到其他各点之间的最短路径六、运行与测试：六、运行与测试：1、测试的数据及其结果：（1）浏览各景点选项功能（2）选择查看校门口到各个景点的最短路径（3）从各个景点中任意选择两景点之间的最短距离（

15、4）查询完毕，退出程序2、运行与测试期间遇到的问题及其解决办法。1. 对文件的输入、输出打开方式不够熟悉，导致输入输出信息有误，后参照教材等材料进行修改，使得程序正常进行；2. 删除函数中循环使用不当，导致运行结果及写入文件结果错误，经修改后恢复正常；3. 经过反复修改测试运行，程序功能基本实现，基本完成题目要求。七、设计后的思考：七、设计后的思考：1.首先经过这一个星期的紧张而又充实的课程设计，是我对数据结构这一门课程的相关知识有了全面深刻的认识， 尤其是对图这一数据结构的相关知识掌握的更加全面和牢固， 特别是对迪杰斯特拉算法的思想和具体实现更是经历了从不知所云到熟练运用的学习过程， 同时也全面而又系统的复习了 C+相关知识。 2.此次课程设计最大的收获可以说是全面掌握了数据结构图的相关知识。 虽说图这一章也是数据结构的终点，但是由于考试只考一些算法的思想，对具体的实现没有做要求，因此课程设计之前我对迪杰斯特拉算法可以说是一窍不通，更谈不上了解。经过几天的探索和同学的指点，终