数据结构课程设计实验报告《校园导游咨询系统》内含程序源代码 运行截图.doc

《数据结构课程设计实验报告《校园导游咨询系统》内含程序源代码 运行截图.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计实验报告《校园导游咨询系统》内含程序源代码 运行截图.doc（24页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、上海电力学院数据结构C+课程设计题目: 校园导游咨询 学生姓名： 学 号： 院系： 专业年级： 2011年7月1日一、设计题目校园导游咨询；1、 实验目的（1）熟练掌握图的创建及遍历基本操作算法。（2） 熟练掌握最短路径算法。（3）利用图的遍历和最短路径求解技术，设计一个校园导游程序，为来访的客人提供各种信息查询服务。2、 实验内容【问题描述】设计一个校园导游程序，为来访的客人提供各种信息查询服务。【基本要求】 (1)设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 (2)为来访客人提供图中任意景

2、点相关信息的查询。 (3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一个最短的简单路径。【测试数据】由读者根据实际情况指定。【实现提示】一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。【选作内容】 (6)扩充每个景点的邻接景点的方向等信息，使得路径查询结果能提供详尽的导向信息。二、小组成员分工说明略三、需求分析1）运行环境（软、硬件环境）硬件环境：windows2000、windows XP、windows7 皆可；软件环境：Microsoft (R) Developer Studio (2)2）输入的形式和输入值的范围输入形式：整形

3、数据（景点代号、路径长度、地图上的方位信息），字符串（景点名称及简介）；输入值范围：景点代号为：整形017（共18个景点）路径长度为：整形110（两景点间距离，以近似1：:100m比例换算，最远1km）景点名称字符串长度：整形115（景点名称）字符串长度为：字符数组150（对景点进行简要介绍）景点在地图方位图上的位置：整形0103）输出的形式描述景点代号、景点名称、信息的关联以cout形式输出，告知来访客人，以便查询；景点信息查询结果的输出形式为cout字符串；两景点间最短路径输出形式为cout字符串 符号、以及嵌套的printroad（）函数以显示路径信息及方位信息，方便客人获取最佳路线；4

4、）功能描述 (1)设计学校的校园平面图，所含景点18个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。(2)为来访客人提供图中任意景点相关信息的查询。(3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一个最短的简单路径，并提示出各景点之间的方位关系，行走方向。5）测试数据输入功能选择号码，进入各项功能界面；根据功能界面的提示输入所要查询的内容：如，在查询景点功能界面需要根据提示输入所需查询的景点代号；在问路查询功能界面需要根据提示输入起点终点的景点代号。四、概要设计1）抽象数据类型定义描述（对各类的成员及成员函数进行抽象描述，

5、参见书或ppt及实验）#includeusing namespace std;const int MaxSize=18;const int INFINITY=65535;/最大值无穷class direction;template class MGraph;template class VertexNode/定义景点结点，存储景点信息friend class MGraph;public:int vex;/景点名称T vexname;/景点名称T vexinf;/景点信息direction dir;/存放景点方位信息的direction类的dir。;class directionpublic:i

6、nt ln;/存放在方向图中的横坐标，表示东西int col;/存放在方向图中的纵坐标，表示南北;template class MGraph/定义无向图的邻接矩阵public: MGraph(); /构造函数，初始化具有n个顶点的图void printvexname();/显示所有景点及景点代号void printvexinf(int i);/显示代号为i景点的名称及信息void printroad(int i,int j);/显示景点ij的最短路径方案信息void printdir(int i,int j);/显示景点i到j的方向信息，如“向东100m，向南200m”VertexNode a

7、djlistMaxSize; /存放景点全部信息的 景点类数组 int vertexNum,arcNum; /图的顶点数和边数void Root(int p,int q);/递归寻找pq间的最短路径int PathMaxSizeMaxSize,DistMaxSizeMaxSize;/创建Path和Dist分别存放两点间最短路径的前驱节点，两点间最短路径长度int LineMaxSize;/Line存放路径int kkk;/在floyed算法中，做Line数组的标记private: T vertexMaxSize; /存放图中顶点的数组 int arcMaxSizeMaxSize;/存放图中边的

8、数组;2）功能模块设计（如主程序模块设计）int funcchoice()/系统功能选择页面int choice;cout=endl;cout 欢迎进入校园导游咨询平台endl;cout 1-显示校园所有景点信息endl;cout 2-查询校园景点信息endl;cout 3-问路查询系统endl;cout 4-退出导游资讯平台endl;cout=endl;coutchoice;return choice;3）模块层次调用关系图主程序菜单模式问路模块printroad(int i,int j)查询信息模块printvexname()显示所有景点信息模块printvexinf(int i)方位信息

9、模块printdir(int p,int q)最短路径模块Floyed递归算法Root(int p,int q)返回某景点信息模块printvexinf(int i)五、详细设计实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。=以下为guide.cpp文件中对guide.h文件中类的所有成员函数的定义等=#include#include#includeguide.husing namespace std;template MGraph:MGraph()/a为景点代号，b为景点名称，c为景点信息，d为景点方位信息的横坐标，e为景点方位信息的纵坐标，s为存放景点邻接矩

10、阵信息的一维数组，根据其对称性可以用公式赋值给二维数组arcint s=0,1,0,0,2,0,0,0,2,0,0,0,2,3,0,0,0,0,4,2,0,0,0,0,0,2,3,0,0,0,0,0,2,3,1,0,0,0,2,0,2,0,0,2,0,4,0,2,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,2,0,1,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,

11、0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,4,4,0,0,2,0;int a=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17;char* b=南门,实验楼,南图,大活,睿思楼,大礼堂,南4教,知行楼,国交楼,南3教,南2教,南1教,北图,北3教,北4教,北2教,北1教,北门;char* c=南校区正门,物理实验楼,南校区图书馆,大学生活动中心,教师办公楼、医务室及留学生公寓,大礼堂，用于举办各种文艺演出,南校区第4教学楼,实习基地，计算机房等,国际交流中心，教职工餐

12、厅,南校区第3教学楼,南校区第2教学楼,南校区第1教学楼,北校区图书馆,北校区第3教学楼,北校区第4教学楼,北校区第2教学楼,北校区第1教学楼,北校区正门;int d=8,6,4,4,1,0,0,1,3,4,6,8,4,3,2,3,5,8;int e=8,8,8,10,8,10,7,6,6,6,6,6,3,1,0,0,0,2;int i,j;vertexNum=18;arcNum=30; for(i=0;ivertexNum;i+)adjlisti.vex=ai;adjlisti.vexname=bi;adjlisti.vexinf=ci;adjlisti.dir.ln=di;adjlisti

13、.dir.col=ei;for (i=0; ivertexNum; i+)/初始化邻接矩阵for (j=0; jvertexNum; j+)arcij=arcji=s(i*(i+1)/2+j; /根据s的对称性，将一维数组中的数据赋给二维数组arctemplatevoid MGraph:printvexname()int i;for(i=0;ivertexNum;i+)coutadjlisti.vex adjlisti.vexnameendl;templatevoid MGraph:printvexinf(int i)couti adjlisti.vexname:adjlisti.vexinf

14、endl;templatevoid MGraph:printdir(int i,int j)int dx,nb;/临时存放i与j之间的南北东西关系 j在i的哪边？dx=adjlistj.dir.col-adjlisti.dir.col;nb=adjlistj.dir.ln-adjlisti.dir.ln;if(dx0)/即j在i的东边cout向东dx*100m，;elsecout向西dx*(0-100)0)/即j在i的南边cout向南nb*100m;elsecout向北nb*(0-100)m;templatevoid MGraph:Root(int p,int q) if (Pathpq0)

15、Root(p,Pathpq); Root(Pathpq,q); else Linekkk=q; kkk+; templatevoid MGraph:printroad(int i,int j)int p,q,m,k,item1,item2;for(p=0;pvertexNum;p+)for(q=0;qvertexNum;q+)Distpq=arcpq;/邻接矩阵赋值for(k=0;kvertexNum;k+) for(p=0;p0) for(q=0;q0) if (DistpqDistpk+Distkq)|(Distpq=0)&(p!=q) Distpq=Distpk+Distkq; Path

16、pq=k; coutn=n;cout从adjlisti.vexname到adjlistj.vexname的最短路径为：endl;coutadjlisti.vexname;kkk=2;Root(i,j);item2=Line2;cout;printdir(i,item2);coutadjlistitem2.vexname;for(m=3;m=kkk-1;m+)item1=Linem;cout;printdir(item1-1,item1);coutadjlistitem1.vexname;coutendl;coutn=n;=以下为main.cpp文件中主函数的实现=#include#includ

17、eguide.cppusing namespace std;int funcchoice()/系统功能选择页面int choice;cout=endl;cout 欢迎进入校园导游咨询平台endl;cout 1-显示校园所有景点信息endl;cout 2-查询校园景点信息endl;cout 3-问路查询系统endl;cout 4-退出导游资讯平台endl;cout=endl;coutchoice;return choice;void main()MGraph mg;int funcchoice();int fc;while(1)fc=funcchoice();if(fc=1)int i;for(

18、i=0;img.vertexNum;i+)mg.printvexinf(i);else if(fc=2)int i;mg.printvexname();coutendli;mg.printvexinf(i);else if(fc=3)int i,j;mg.printvexname();coutij;mg.printroad(i,j);else if(fc=4)break;elsecout输入有误，请重新输入！endl;六、调试分析遇到的问题及解决的办法：在调试过程中，最常见到的问题有以下几种：1、忘记调用函数类模块template，有些类中或者函数中涉及函数类模块的调用，但忘记标注会导致编译错

19、误。我的解决方法是在写程序中，一旦写到“T”，就立刻到前面找类模块的定义，如果发现没写就赶紧补上；2、容易混淆指针和对象，若将p定义为指针，则调用p所指向的类的函数时应该用“-”，若p为对象则可直接用“.”调用类中的共有接口函数。针对该问题，我的解决办法是在纸上写明各个类及类中的成员函数，标清类型等，这样一目了然，写程序的时候查对起来也方便；3、容易将类或函数名中的大写字母错写成小写字母，有时甚至导致编译正确，连接错误，error不能指出错误的情况发生，使程序查对过程较长，我的解决办法是，以后在编程中应尽量使用统一的书写形式，如全部大写或全部小写；4、“=”的应用，很多时候是不能直接用“=”赋

20、值的，要注意等号两边的类型是否一致，是否可以用=赋值等；5、虽然已经养成了在写多句函数的时候，先把花括号一起打上，但改程序的过程中还是会有粗心导致花括号不成对等情况出现，编译中自己很难根据error提示找到问题所在，是同学帮我检查到的，这提醒我在日后检查error时也要注意花括号是否完整，而且我的一个习惯有益于这个错误的查找，那就是格式对齐，格式对齐可以让程序一目了然，检查花括号也变得简单轻松很多；6、运行程序后对程序进行改动，改动后运行程序时应将之前的运行界面关闭才可以继续；Floyed算法的时间空间复杂性分析： 本程序中的Floyed算法对邻接矩阵每一个元素都进行了N（N即为景点个数）遍比

21、较，所以时间复杂度是O(N3)；存放两点间最短路径前驱结点的path矩阵占用了N*N的空间，所以时间复杂度是O(N2)。经验体会：在涉及矩阵等算法的时候，一定要注意下标是否是0开始的，对称的邻接矩阵赋值给arcij的同时不要忘记赋值给arcji。七、 用户使用说明详细列出每一步的操作说明。（一）打开Microsoft (R) Developer Studio（二）新建一个工程（三）选择“an empty project”并单击“完成”（四）在工程内新建一个header file用于存放类的定义（五）新建一个source file用于存放类的实现，函数定义（六）新建一个source file用于

22、编写主函数八、 测试结果构造函数中已经将校园景点的代号、名称、简介等信息全部设好，只需根据主页面提示输入功能号，即可查询景点信息；在查询校园景点信息时，页面会显示各个景点的名称及代号，方便来访者查询景点使用问路查询系统时，页面显示各景点代号及名称，方便来访者输入查询信息。在该模块中，还设计了各景点在地图上的分布矩阵，根据景点的方位信息，输出两景点间的距离方向信息可以让来访者更容易找到这些景点及线路使用完程序后 输入4号功能键即可退出附录：代码(ps:该校园导游咨询系统没有输入值，所有信息是都在class MGraph的构造函数中传输的，且校园景点信息皆为【上海电力学院】景点信息。请大家注意，直

23、接从文章copy到visual stutio中会出现中文字符，注意删除，推荐大家在一行语句的分号后面，点出光标，按一下delete键，然后按一下enter键，完成visual stutio的自动对齐，这样程序看起来一目了然，更易于操作和更改)【问题描述】设计一个校园导游程序，为来访的客人提供各种信息查询服务。【基本要求】(1)设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。(2)为来访客人提供图中任意景点相关信息的查询。(3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一个最短的

24、简单路径。【选作内容】(6)扩充每个景点的邻接景点的方向等信息，使得路径查询结果能提供详尽的导向信息。*【以下为类的定义】*#include#includeusing namespace std;const int MaxSize=18;const int INFINITY=65535;/最大值无穷class direction;template class MGraph;template class VertexNode/定义头结点friend class MGraph; public:int vex;/顶点名称T vexname;/顶点名称T vexinf;/顶点信息direction d

25、ir;/存放顶点方位信息的direction类的dir。;class directionpublic:int ln;/存放在方向图中的横坐标，表示东西int col;/存放在方向图中的纵坐标，表示南北;template class MGraph/定义无向图的邻接矩阵public:MGraph(); /构造函数，初始化具有n个顶点的图void printvexname();/显示所有景点及景点代号void printvexinf(int i);/显示代号为i景点的名称及信息void printroad(int i,int j);/显示景点ij的最短路径方案信息void printdir(int

26、i,int j);/显示景点i到j的方向信息，如“向东100m，向南200m”VertexNode adjlistMaxSize; /存放景点全部信息的 景点类数组int vertexNum,arcNum; /图的顶点数和边数void Root(int p,int q);/递归寻找pq间的最短路径int PathMaxSizeMaxSize,DistMaxSizeMaxSize;/创建Path和Dist分别存放两点间最短路径的前驱节点，两点间最短路径长度int LineMaxSize;/Line存放路径int kkk;/Line数组的标记private:T vertexMaxSize; /存放

27、图中顶点的数组int arcMaxSizeMaxSize;/存放图中边的数组;*【以下为类的实现 即类函数的定义】*template MGraph:MGraph()/a为景点代号，b为景点名称，c为景点信息，d为景点方位信息的横坐标，e为景点方位信息的纵坐标/s为存放景点邻接矩阵信息的一维数组，根据其对称性可以用公式赋值给二维数组arcint s=0,1,0,0,2,0,0,0,2,0,0,0,2,3,0,0,0,0,4,2,0,0,0,0,0,2,3,0,0,0,0,0,2,3,1,0,0,0,2,0,2,0,0,2,0,4,0,2,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0

28、,0,2,0,1,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,4,4,0,0,2,0;int a=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17;char* b=南门,实验楼,南图,大活,睿思楼,大礼堂,南4教,

29、知行楼,国交楼,南3教,南2教,南1教,北图,北3教,北4教,北2教,北1教,北门;char* c=南校区正门,物理实验楼,南校区图书馆,大学生活动中心,教师办公楼、医务室及留学生公寓,大礼堂，用于举办各种文艺演出,南校区第4教学楼,实习基地，计算机房等,国际交流中心，教职工餐厅,南校区第3教学楼,南校区第2教学楼,南校区第1教学楼,北校区图书馆,北校区第3教学楼,北校区第4教学楼,北校区第2教学楼,北校区第1教学楼,北校区正门;int d=8,6,4,4,1,0,0,1,3,4,6,8,4,3,2,3,5,8;int e=8,8,8,10,8,10,7,6,6,6,6,6,3,1,0,0,0

30、,2;int i,j;vertexNum=18;arcNum=30; for(i=0;ivertexNum;i+)adjlisti.vex=ai;adjlisti.vexname=bi;adjlisti.vexinf=ci;adjlisti.dir.ln=di;adjlisti.dir.col=ei;for (i=0; ivertexNum; i+)/初始化邻接矩阵for (j=0; jvertexNum; j+)arcij=arcji=s(i*(i+1)/2+j; /根据s的对称性，将一维数组中的数据赋给二维数组arc templatevoid MGraph:printvexname()in

31、t i;for(i=0;ivertexNum;i+)coutadjlisti.vex adjlisti.vexnameendl;templatevoid MGraph:printvexinf(int i)couti adjlisti.vexname:adjlisti.vexinfendl;templatevoid MGraph:printdir(int i,int j)int dx,nb;/临时存放i与j之间的南北东西关系 j在i的哪边？dx=adjlistj.dir.col-adjlisti.dir.col;nb=adjlistj.dir.ln-adjlisti.dir.ln;if(dx0)

32、/即j在i的东边cout向东dx*100m，;elsecout向西dx*(0-100)0)/即j在i的南边cout向南nb*100m;elsecout向北nb*(0-100)m;templatevoid MGraph:Root(int p,int q) if (Pathpq0) Root(p,Pathpq); Root(Pathpq,q); else Linekkk=q; kkk+; templatevoid MGraph:printroad(int i,int j)int p,q,m,k,item1,item2;for(p=0;pvertexNum;p+)for(q=0;qvertexNum

33、;q+)Distpq=arcpq;/邻接矩阵赋值for(k=0;kvertexNum;k+) for(p=0;p0) for(q=0;q0) if (DistpqDistpk+Distkq)|(Distpq=0)&(p!=q) Distpq=Distpk+Distkq; Pathpq=k; coutn=n;cout从adjlisti.vexname到adjlistj.vexname的最短路径为：endl;coutadjlisti.vexname;kkk=2;Root(i,j);item2=Line2;cout;printdir(i,item2);coutadjlistitem2.vexname

34、;for(m=3;m=kkk-1;m+)item1=Linem;cout;printdir(item1-1,item1);coutadjlistitem1.vexname;coutendl;coutn=n;*【以下为主函数】*int funcchoice()/系统功能选择页面int choice;cout=endl;cout 欢迎进入校园导游咨询平台endl;cout 1-显示校园所有景点信息endl;cout 2-查询校园景点信息endl;cout 3-问路查询系统endl;cout 4-退出导游资讯平台endl;cout=endl;coutchoice;return choice;void main()MGraph mg;int funcchoice();int fc;while(1)fc=funcchoice();if(fc=1)int i;for(i=0;img.vertexNum;i+)mg.printvexinf(i);else if(fc=2)int i;mg.printvexname();coutendli;mg.printvexinf(i);else if(fc=3)int i,j;mg.printvexname();coutij;mg.printroad(i,j);else if(fc=4)break;elsecout输入有误，请重新输入！endl;