校园导游程序的设计与实现课程设计.doc

海南大学课程名称 数据结构（基于C语言）课程设计 题 目 校园导游程序的设计与实现 院 系 信息科学技术学院班 级 通信工程B班 软件专题训练任务书软件专题训练题目校园导游程序姓名学号专业班级组别组长同组成员 指导教师吴泽辉专题训练目的通过校园导游程序的设计与实现，熟1练掌7握图型结构在实际问题中的应用。专题训练环境运行环境为Visual C+ 6.0课程设计任务和要求设计校园导游程序，基本要求：1咨询以用户和计算机的对话方式进行，由用户输入起始点和终点，输出信息：最短路径是多少？并指出所经过的场所。2、计算并记录从校门口到各个场所的最短路径，即求单源点到其它各个场所的最短路径。3、提供校园中任意场所的问路查询，即求任意两点之间的最短路径。参考文献1、严蔚敏等. 数据结构（C语言版）. 清华大学出版社20042、谭浩强. C语言程序设计. 清华大学出版社. 20023、李春保. 数据结构教程上机实验指导. 清华大学出版社. 2005校园导游程序 一、简介1设计目的：通过校园导游程序的设计与实现，熟练掌握图型结构在实际问题中的应用。2问题的描述：设计一个校园模拟导游程序，为新生或来访的客人通过与机器的“对话“提供最短路径的信息查询服务。 1任意选取n个场所，构成一个无向带权图，图中顶点表示场所，边上的权值表示两点间的距离，图的存储结构可采用带权的邻接矩阵。2咨询以用户和计算机的对话方式进行，由用户输入起始点和终点，输出信息：最短路径是多少？并指出所经过的场所。3、计算并记录从校门口到各个场所的最短路径，即求单源点到其它各个场所的最短路径。4、提供校园中任意场所的问路查询，即求任意两点之间的最短路径。二、数据结构的设计：由于各个场所通过校园中的道路相连，各个场所和连接它们的道路构成了整个校园的地理环境，所以使用图这种数据结构对他们去进行描述。以图中的顶点表示校园内各个场所，应包含场所名称、代号、简介等信息；以边表示连接各个场所的道路，应包含路径的长度等信息；顶点和边均使用结构体定义，整个图的数据结构采用教材中介绍的带权的邻接矩阵方法。 二、数据结构的设计：typedef struct ArCellint adj; /路径长度ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /图中顶点表示主要景点，存放景点的序号、名称、介绍等信息，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,&i); while(i!=4) switch(i) case 1:Browser(&b);Menu();break; case 2:ShortestPath_DIJ(&b);Menu();break; case 3:Floyd(&b);Menu();break; case 4:exit(1);break; default: printf(输入序号不存在,请重新输入);break; scanf(%d,&i); MGraph InitGraph(void) MGraph G; int i,j; G.vexnum=10; G.arcnum=14; for(i=0;iG.vexnum;i+) G.vexsi.num=i; strcpy(G.,海南大学北门); strcpy(G.roduction,高大威武); strcpy(G.,文化柱); strcpy(G.roduction,海大学子健康成长，激情飞扬的地方); strcpy(G.,图书楼); strcpy(G.roduction,藏书丰富，设施良好，知识的摇篮); strcpy(G.,3号教学楼); strcpy(G.roduction,海大学子努力学习，坚持向上的场所 ); strcpy(G.,第一田径场); strcpy(G.roduction,标准化跑道，适宜锻炼身体的场所); strcpy(G.,男生宿舍楼); strcpy(G.roduction,房间设施良好，标准六人间); strcpy(G.,海大餐厅); strcpy(G.roduction,厅内卫生整洁，环境宜人); strcpy(G.,联谊馆); strcpy(G.roduction,内有乒乓球馆，排球馆，室内篮球馆等设施); strcpy(G.,女生宿舍楼); strcpy(G.roduction,房间设施良好，标准六人间); strcpy(G.,海大东门); strcpy(G.roduction,外有建设银行); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij.adj=INFINITY; G.arcs01.adj=100; G.arcs02.adj=80; G.arcs06.adj=100; G.arcs17.adj=120; G.arcs23.adj=50; G.arcs36.adj=110; G.arcs34.adj=150; G.arcs45.adj=60; G.arcs49.adj=280; G.arcs59.adj=250; G.arcs67.adj=190; G.arcs69.adj=180; G.arcs78.adj=130; G.arcs89.adj=100; for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsji.adj=G.arcsij.adj; return G;/InitGraph end用的是一个switch语句实现输入不同的序号操作选项，调用不同的函数进入不同的操作板块/ 迪杰斯特拉算法计,v0为始点void ShortestPath_DIJ(MGraph * G) int v,w,i,min,t=0,x,flag=1,v0; int final20, D20, p2020; while(flag) printf(请输入起始点序号:); scanf(%d,&v0); if(v0G-vexnum) printf(输入错误，景点序号不存在!请再次输入景点序号:); scanf(%d,&v0); if(v0=0&v0vexnum) flag=0; for(v=0;vvexnum;v+) finalv=0; Dv=G-arcsv0v.adj; for(w=0;wvexnum;w+) pvw=0; if(DvINFINITY) pvv0=1;pvv=1; Dv0=0;finalv0=1; for(i=1;ivexnum;i+) min=INFINITY; for(w=0;wvexnum;w+) if(!finalw) if(Dwmin)v=w;min=Dw; finalv=1; for(w=0;wvexnum;w+) if(!finalw&(min+G-arcsvw.adjarcsvw.adj; for(x=0;xvexnum;x+) pwx=pvx; pww=1; for(v=0;vvexnum;v+) if(v0!=v) printf(%s,G-); for(w=0;wvexnum;w+) if(pvw&w!=v0) printf(-%s,G-); t+; if(tG-vexnum-1&v0!=v)printf( 总路线长%dmnn,Dv); /ShortestPath_DIJ endvoid Floyd(MGraph *G) int v,u,i,w,k,j,flag=1,p101010,D1010; for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) Dvw=G-arcsvw.adj; for(u=0;uvexnum;u+) pvwu=0; if(DvwINFINITY) pvwv=1;pvww=1; for(u=0;uvexnum;u+) for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) if(Dvu+DuwDvw) Dvw=Dvu+Duw; for(i=0;ivexnum;i+) pvwi=pvui|puwi; while(flag) printf(请输入始点和终点的序号:); scanf(%d%d,&k,&j); if(kG-vexnum|jG-vexnum) printf(景点序号错误!请再次输入始点和终点的序号:); scanf(%d%d,&k,&j); if(k=0&kvexnum&j=0&jvexnum) flag=0; printf(%s,G-); for(u=0;uvexnum;u+) if(pkju&k!=u&j!=u) printf(-%s,G-); printf(-%s,G-); printf( 总路线长%dmn,Dkj);/Floyd endint LocateVex(MGraph *G,char* v) int c=-1,i; for(i=0;ivexnum;i+) if(strcmp(v,G-)=0) c=i;break; return c;MGraph * CreatUDN(MGraph *G) int i,j,k,w; char v120,v220; printf(输入图的顶点数,弧数:); scanf(%d%d,&G-vexnum,&G-arcnum); printf(输入景点的编号:、名称、介绍:n); for(i=0;ivexnum;i+) printf(景点序号:); scanf(%d,&G-vexs-num); printf(景点名称:); scanf(%s,G-); 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):); scanf(%s,v1); scanf(%s,v2); printf(路径长度:); scanf(%d,&w); i=LocateVex(G,v1); j=LocateVex(G,v2); if(i=0&j=0) G-arcsij.adj=w; G-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); 旅客进行查询：1. 查看校园各景点2. 查看所有游览线路； 3. 选择始点和终点 4. 退出程序三、功能（函数）设计：一本程序从总体上分为四个功能模块，分别为： (1)查看校园各景点，这一功能主要为来客提供要查的信息。（2） 查看所有游览线路,这一功能主要提供来客所要到达目的地的所有的线路，方便选择最短的的路线。（3）选择始点和终点 ，这一功能的实现为了找出所走线路中的最短路径（4）. 退出程序二，流程图如下（1） 程序功能介绍和操作提示模块选项操作菜单查看校园各景点查看所有游览路线选择始点和终点退出程序（2）查看所有游览线路开始用求迪杰斯特拉算法出中转最少的路径输入v0,vv0,v合理v0=v递归调用此算法输出中转最少的路径v0,v直接到达结束NYYNYN权值小于无穷带权最少的路径（3） 选择始点和终点开始初始化pathij,distij用弗洛伊德算法计算最小路径输入vi,vjvi,vj合理输出最短路径结束NYYY YNdistik+distkj distijdistij=distik+distkj;pathij=JoinList(pathik,pathkj);调用JoinList()和Addtail()四、界面设计：本程序界面本着易于操作简单整洁而不失美观的理念，采用数字对应功能选项，结合详细的操作提示，使得操作方便快捷，界面清晰明朗。 函数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）从各个景点中任意选择两景点之间的最短距离（4）查询完毕，退出程序2、运行与测试期间遇到的问题及其解决办法。1. 对文件的输入、输出打开方式不够熟悉，导致输入输出信息有误，后参照教材等材料进行修改，使得程序正常进行； 2. 删除函数中循环使用不当，导致运行结果及写入文件结果错误，经修改后恢复正常； 3. 经过反复修改测试运行，程序功能基本实现，基本完成题目要求。 。七、设计后的思考：1.首先经过这一个星期的紧张而又充实的课程设计，是我对数据结构这一门课程的相关知识有了全面深刻的认识，尤其是对图这一数据结构的相关知识掌握的更加全面和牢固，特别是对迪