数据结构课程设计--校园导游程序.doc

武汉长江工商学院计算机科学与技术系项目名称： 校园导游程序 学生姓名： 朱捷 学号： 1203090120 班级： 12801 指导教师： 刘莹 2013年12月9日目录1.课程设计的目的与意义11.1课程设计的目的11.2课程设计的意义12.系统功能描述及设计13.系统存储结构及描述34.系统功能实现及算法描述54.1校园景点信息的录入54.2查询图中任意两个景点间的最短路径64.3查询图中任意一个景点到其他景点的所有路径74.4查询任意两景点间的所有路径85. 系统性能测试95.1 主界面95.2浏览校园全景95.3查询图中任意两个景点间的最短路径105.4查询图中任意一点到其他景点间的所有路径105.5查询任意两个景点间的所有路径116.设计小结11参考文献11源代码清单121.课程设计的目的与意义1.1课程设计的目的随着社会的发展，人们对生活的也要求越来越高，从以前的一切都用手用笔的时代到了一切都可以用机器代替的时代。现在的大学校园越来越大了，对于对新学校不熟悉和对于外来着更好的参观和游览学校，特做了这个校园导游图，它能输出所有校园景点的简介供用户参考，并且能找到两个景点间最短路径，让用户少走弯路和冤枉路，而且还可以找到一个景点到其他景点的最短路径，可以提供使用者最好的游览路径。更多的功能将会在后续继续加入。1.2课程设计的意义巩固和加深学生对数据结构的基本知识的理解和掌握,掌握C语言编程和程序调试的基本技能。利用数据结构进行基本的软件设计,掌握书写程序设计说明文档的能力，提高运用数据结构解决实际问题的能力。培养我们综合运用所学知识的能力和锻炼实践的能力,能够做到善于发现,提出,分析和解决实际问题。同时，进一步加深、巩固我们所学专业课程（数据结构实用教程）的基本理论知识,如语句嵌套和循环，分支等结运用，理论联系实际，进一步培养学生综合分析问题和解决问题的能力。掌握运用C语言独立地编写、调试应用程序和进行其它相关设计的技能，扩展自己的知识面，充分发挥广大同学的潜力，提高程序开发能力，使我们通过这次课程设计而得到全面的锻炼。2.系统功能描述及设计整个系统主要包含三个大的模块（功能模块图见下图2-1）菜单1：浏览校园全景，该功能的实现是通过编程着将所有信息事先录入系统中，当用户选择时，会输出学校所有的景点，编号及简介。菜单2：查询任意两景点间的所有路径。这个是根据弗洛伊德算法改编而来，该算法能很方便的找出用户所输入的两景点间的最短路径。当然，当你输入的景点编号不存在时，就回提示重新输入，知道输入的两个点都符合要求才会找出最短路径。菜单3：查询一个景点到其他所有景点的最短路径。该系统能通过你所在的位置找出到其他所有景点的最短路径。很方便的满足客户需要到达其他景点的路径。菜单4：查询图中任意两景点间的所有路径。有了这个功能，用户可以很方便的找到图中任意连个景点间的所有路径。这样用户就可以选择自己中意的路径来到达自己的目的地了。菜单5：退出整个系统。图2-1系统功能描述3.系统存储结构及描述下面将给出程序代码的部分代码，将详细介绍系统的存储结构。如：struct infotypechar name20;int num;char introduction100;weighttype maxvalue;struct Mgraph infotype vexsMAXVER; /定义存储定点信息的数组类型 infotype arcsMAXVERMAXVER; /定义存储邻接矩阵的数组类型 int vexnum,arcnum;该存储结构：在上面的结构体中，包含了图中所需的景点名，景点个数，景点简介，而且存储了边数，还利用数组来存储两景点间是否有边，而且还包含了两景点间的权值。for(i=0;iG.vexnum;i+) G.vexsi.num=i;strcpy(G.,弘德楼);strcpy(G.roduction,学生公寓，主要为考研学生准备，环境良好。);上面简单的几行代码就存储了一个景点的编号，名称，简介for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij.maxvalue=FARMAX; G.arcs01.maxvalue=70; for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsji.maxvalue=G.arcsij.maxvalue;上面的代码利用了两个for循环很快的定义出了任意两个景点的关系，如是否存在边，存在边权值是大小（没有边则为事先定义的最大值，存在边则直接输入权值），同时也作出了无向图应有的特点，及是双向的，并且两边权值相等。上面整个信息的录入存储了整个系统需要的数据，包括景点个数，边数，名称，简介，距离。有了这个函数，方便以后所有的需要数据的地方来调用它。4.系统功能实现及算法描述4.1校园景点信息的录入 该功能的实现是通过利用定义好的变数，定点数，景点名，景点编号，景点间权值的，一次输入G.，G.roduction，G.arcsii.maxvalue,而i，j的取值范围是由G.vexnum和G.arcnum确定的。图4-1：图4-1校园景点信息的录入4.2查询图中任意两个景点间的最短路径 该功能是利用弗洛伊德算法如果从k到j有边，则存在一条长度为arcskj的路径，该路径不一定是最短路径。考虑路径（k,u,j）是否存在，若存在，比较（k,j）和（k,u,j）的长度，取较短者为从k到j的中间点序号不大于0的最短路径。以此类推，每次增加一个点，从而求出任意两点间的最短路径。这样，经过n次比较后，所求得的必为从k到j的最短路径。按此方法，可以同时求得任意两点间的最短路径。流程图如下4-2：4-2查询图中任意两个景点间的最短路径4.3查询图中任意一个景点到其他景点的所有路径 这个功能的实现是通过数组存储所有右边的路径，然后根据用户输入的一个景点的编号找到该景点与其他景点右边的景点，然后以右边的其他景点为起点，重复上述流程，直到找完每个景点即结束程序。如图4-3：图4-3查询图中任意一个景点到其他景点的所有路径4.4查询任意两景点间的所有路径 该功能是通过用户输入的两个景点的编号找到对应的景点名，然后以第一个点作为起点向其他点找边，当边的权值小于最大值时，说明存在边，即可保存在数组中，直到找到终点对应的编号即为一天路径，循环上述过程，直到出现重复路径即结束函数，跳出循环。如图图4-4：图4-4查询任意两景点间的所有路径5. 系统性能测试5.1 主界面当程序成功被打开时会出现如图5-1所示的界面，该界面相当于一个菜单，用户可以根据自己的需求选择数字。“1”浏览所有景点的信息，“2”找出任意两景点间所有路径，“3”找到一个景点到其他景点间的所有路径，“4”退出系统 ，下面是“请选择，输入1-5键：”的字样。如图5-1：图5-1主界面测试图5.2浏览校园全景当用户选择1时，程序即会根据之前存储好的信息输出景点间的所有信息，供用户浏览及参考。运行效果如下5-2图片所示。图5-2浏览校园全景5.3查询图中任意两个景点间的最短路径 当用户选择2时，则会进入该系统，系统会提示“请输入两个景点的编号”，当你输入的景点不符合要求时，会提示重新输入如10和2，当符合要求是，系统则会输入最短路径，如我输入了2和4，如图5-3：图5-3查询图中任意两个景点间的最短路径5.4查询图中任意一点到其他景点间的所有路径当用户输入3是，则会进入该系统，此时系统会提示输入你要选择的景点编号，当不合要求时，同样会提示请再次输入，直到符合要求为止，如我输入了20，之后又输入了了15，最后输入5，才输入路径。如图5-4：图5-4查询图中任意一点到其他景点间的所有路径5.5查询任意两个景点间的所有路径当用户选择4时即可进入该系统，系统会提示用户输入要查询的两个景点的编号。相同的当有编号不存在时，系统会提示重新输入正确的编号，如我输入了一个2和10时，系统会提示输入有误，请重新输入，最后我输入了2和7，则输出了所有路径：如图5-5所示。图5-5查询任意两个景点间的所有路径6.设计小结 通过几周的课程设计，我学到了很多东西：（1）对自己所学的数据结构有了更熟练的运用和更深刻的了解。（2）提高了我的动手能力，学会了自觉主动地查找文献知识，如到图书馆翻阅书籍和上网查阅等。（3）提高了自己的办事效率，面对挑战不退缩，敢于迎韧而上，除此还学会了遇事沉着冷静，认真思考，逻辑清晰的列出解决方案。（4）提高了我对市场的了解，使自己很好的将市场与C语言程序设计相结合，使自己能学以致用，联系实际生活。（5）学会了感恩，了解到老师和父母对我们的付出都很大。参考文献1 徐孝凯数据结构使用教程清华大学出版社：徐培忠，20062 徐孝凯C+语言基础清华大学出版社：徐培忠，19993 徐孝凯数据结构使用教程习题参考解答清华大学出版社：徐培忠，20064 胡成松C语言课程设计北京高等教育出版社：林孝平，20065 刘云计算机网络实用教程北京高等教育出版社：徐培忠，2004 6 徐孝凯数据结构课程设计清华大学出版社：徐培忠，2006源代码清单#include#include #include#include#include#define FARMAX 1000typedef int weighttype; /定义边上权值的类型const int MAXVER=10; /定义图的最多顶点数typedef int adjmatrixtypeMAXVER; /定义adjmatrix为存储邻接矩阵的数组类型struct infotypechar name20;int num;char introduction100;weighttype maxvalue;struct Mgraph infotype vexsMAXVER; /定义存储定点信息的数组类型 infotype arcsMAXVERMAXVER; /定义存储邻接矩阵的数组类型 int vexnum,arcnum;void jiben(Mgraph &G)int i,j;G.vexnum=8;G.arcnum=10;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.,图书馆); 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.maxvalue=FARMAX; G.arcs01.maxvalue=70; G.arcs04.maxvalue=40; G.arcs15.maxvalue=30; G.arcs13.maxvalue=60; G.arcs23.maxvalue=20; G.arcs34.maxvalue=30; G.arcs45.maxvalue=40; G.arcs47.maxvalue=80; G.arcs57.maxvalue=50; G.arcs67.maxvalue=30; for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsji.maxvalue=G.arcsij.maxvalue;void menu() / 菜单coutendl 武汉长江工商学院校园导游图 endl;cout endl; cout 1.浏览校园全景 endl; cout 2.查询图中任意两个景点间的最短路径 endl; cout 3.查询图中一个景点到其他所有景点的最短路径 endl;cout 4.查询任意两景点间的所有路径 endl; cout 5.退出系统 endl; cout endl;cout 请输入你的选择： endl;void information(Mgraph G) /简介cout endl; cout 编号景点名称 简介 endl;cout endl; for(int i=0;iG.vexnum;i+)printf( %-4d%-14s%-52sn,G.vexsi.num,G.,G.roduction);cout endl;void Floyd(Mgraph G) /两点间最短路径 int v,u,i,w,k,j,flag=1,p888,D88; for(v=0;vG.vexnum;v+) for(w=0;wG.vexnum;w+) Dvw=G.arcsvw.maxvalue; for(u=0;uG.vexnum;u+) pvwu=0; if(DvwFARMAX) pvwv=1;pvww=1; for(u=0;uG.vexnum;u+) for(v=0;vG.vexnum;v+) for(w=0;wG.vexnum;w+) if(Dvu+DuwDvw) Dvw=Dvu+Duw; for(i=0;iG.vexnum;i+) pvwi=pvui|puwi; while(flag) coutkj; if(kG.vexnum|jG.vexnum) coutkj; if(k=0 & k=0 & jG.vexnum) flag=0; coutG.; for(u=0;uG.vexnum;u+) if(pkju&k!=u&j!=u) coutG.; coutG.; cout 总路线长Dkjm;void farf(Mgraph G) /一点到其他所有路径int v,w,i,min,t=0,x,flag=1,v0;int final16, D16, p1616;while(flag)coutv0;if(v0G.vexnum)coutv0; if(v0=0&v0G.vexnum) flag=0; for(v=0;vG.vexnum;v+) finalv=0; Dv=G.arcsv0v.maxvalue; for(w=0;wG.vexnum;w+) pvw=0; if(DvFARMAX) pvv0=1;pvv=1; Dv0=0;finalv0=1; for(i=1;iG.vexnum;i+) min=FARMAX; for(w=0;wG.vexnum;w+) if(!finalw) if(Dwmin)v=w;min=Dw; finalv=1; for(w=0;wG.vexnum;w+) if(!finalw&(min+G.arcsvw.maxvalueDw) Dw=min+G.arcsvw.maxvalue; for(x=0;xG.vexnum;x+) pwx=pvx; pww=1; for(v=0;vG.vexnum;v+) if(v0!=v) coutG.; for(w=0;wG.vexnum;w+) if(pvw&w!=v0) coutG.vexnum-1&v0!=v) cout 总路线长Dvmendl; int DMAXVER;int visitedMAXVER;int a=0;void path(Mgraph G,int i,int j,int k)int s;if(Dk=j)a+;cout第a条路径为:;for(s=1;sk;s+)coutG.vexsD;coutG.vexsD;coutendl;elses=1;while(sG.vexnum