数据结构课程设计-校园导游咨询

1、.上海电力学院数据结构（C+）课程设计题目: 校园导游咨询 姓 名： 学 号： 院系： 计算机科学与技术学院 专业年级： 信息安全 2014 2016年7 月3 日目 录1.设计题目12.需求分析12.1运行环境12.2输入的形式和输入值的范围12.3 输出的形式描述12.4功能描述12.5测试数据13.概要设计23.1抽象数据类型定义描述23.2功能模块设计33.3 模块层次调用关系图34.详细设计45.调试分析76.测试结果87.附件9一、 设计题目校园导游咨询二、需求分析1）运行环境（软、硬件环境）电脑型号 X64 兼容 笔记本电脑 操作系统 Windows 8 编程环境 Microso

2、ft Visual Studio 20122）输入的形式和输入值的范围 内容形式范围景点代号int自然数 景点名称string所有字符景点介绍string所有字符Y坐标int正整数X坐标int正整数3）输出的形式描述 内容形式范围景点代号int自然数 景点名称string所有字符景点介绍string所有字符Y坐标int正整数X坐标int正整数最短路径4）功能描述 （1）设计学校的校园平面图，所含景点14个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 (2)为来访客人提供图中任意景点相关信息的查询。(3)为来访客人提供图中任意景点的问路查询，

3、即查询任意两个景点之间的一个最短的简单路径，并提示出各景点之间的方位关系，行走方向。 （5）测试数据景点编号景点名称景点介绍X坐标Y坐标1北校门学校北边的出入口10202北教学校北边的教学楼，包含北1到北420103崇德楼经管学院楼50104北图北边的图书馆，图书库40205北运动场北边的运动场，包含操场、健身房等40406行政楼计算机办公楼20407文化活动中心俗称H楼，有乒乓球桌、瑜伽房、社联值班室等20508南校门学校南边的出入口10609南教学校南边的教学楼，包含南1教到南4教206010南图学校南边的图书馆，主要自习406011大礼堂主要活动举办地506012大学生文化活动中心包含舞

4、厅、团委办公室等208013情人坡包含一个广场及网球场408014南体南边的体育馆2090距离邻接矩阵：0 20 999 999 999 25 999 40 999 999 999 999 999 99920 0 40 15 999 20 999 999 999 999 999 999 999 999999 40 0 25 999 999 999 999 999 999 40 999 999 999999 15 25 0 20 999 999 999 999 999 999 999 999 999999 999 999 20 0 20 999 999 999 20 15 999 999 999

5、25 20 999 999 20 0 10 20 999 999 999 999 999 999999 999 999 999 999 10 0 999 10 999 999 999 999 99940 999 999 999 999 20 999 0 999 999 999 10 999 999999 999 999 999 999 999 10 999 0 999 999 20 999 999999 999 999 999 20 999 999 999 999 0 10 999 20 999999 999 40 999 15 999 999 999 999 10 0 999 10 9999

6、99 999 999 999 999 999 999 10 20 999 999 0 20 10999 999 999 999 999 999 999 999 999 20 10 20 0 999999 999 999 999 999 999 999 999 999 999 999 10 999 0三、概要设计1）抽象数据类型定义描述（对各类的成员及成员函数进行抽象描述，参见书或ppt及实验） Class MGraph输入：代号、名称、介绍、X坐标、Y坐标前置条件：无动作：定义邻接矩阵输出：无后置条件：无 Class VertexNode输入：顶点名称，顶点信息，顶点介绍，顶点方位前置条件：定

7、义了Mgraph动作：定义顶点输出：无后置条件：无Class direction输入：定点的横（东西）、纵（南北）坐标前置条件：无动作：定义路径方位输出：无后置条件：无2）功能模块设计（如主程序模块设计） 1.主程序模块：连接调用各种子模块，使用循环等待用户操作，完成程序的基本操作实现功能。 2.菜单显示模块:生成每个菜单的显示界面，及开始的选择界面，是系统的实现更加简单清晰。 3.用户操作选择模块：由主程序调用函数，是用户的操作可以简单地完成。3）模块层次调用关系图 上海电力学院校园导游咨询系统主程序菜单问路查询信息显示所有景点方位信息最短路径Floyed算法返回某景点信息四、详细设计实现概

8、要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。=以下为guide.cpp文件中对guide.h文件中类的所有成员函数的定义等= #include<iostream> #include<iomanip> #include"guide.h" using namespace std;template <class T>MGraph<T>:MGraph()/a为景点代号，b为景点名称，c为景点信息，x为景点方位信息的横坐标，y为景点方位信息的纵坐标/s为存放景点邻接矩阵信息的一维数组，根据其对称性可以用公式赋

9、值给二维数组arcint s=0, 20, 0, 999, 40, 0, 999, 15, 25, 0, 999, 999, 999, 20, 0, 25, 20, 999, 999, 20, 0, 999, 999, 999, 999, 999, 10, 0, 40, 999, 999, 999, 999, 20, 999, 0, 999, 999, 999, 999, 999, 999, 10, 999, 0, 999, 999, 999, 999, 20, 999, 999, 999, 999, 0, 999, 999, 40, 999, 15, 999, 999, 999, 999,

10、10, 0, 999, 999, 999, 999, 999, 999, 999, 10, 20, 999, 999, 0, 999, 999, 999, 999, 999, 999, 999, 999, 999, 20, 10, 20, 0, 999, 999, 999, 999, 999, 999, 999, 999, 999, 999, 999, 10, 999, 0,;int a=1,2,3,4,5,6,7,8,9,10,11,12,13,14;char* b="北校门","北教","崇德楼","北图",&

11、quot;北运动场","行政楼","文化活动中心","南校门","南教","南图","大礼堂","大学生文化活动中心","情人坡","南体"char* c="学校北边的出入口","学校北边的教学楼，包含北1到北4","经管学院楼","北边的图书馆，图书库","北边的运动场，包含操场、健身房等","计

12、算机办公楼","俗称H楼，有乒乓球桌、瑜伽房、社联值班室等","学校南边的出入口","学校南边的教学楼，包含南1教到南4教","学校南边的图书馆，主要自习","主要活动举办地","包含舞厅、团委办公室等","包含一个广场及网球场","南边的体育馆"int x=10,20,50,40,40,20,20,10,20,40,50,20,40,20;int y=20,10,10,20,40,40,50,60,60,60,60,80,8

13、0,90;int i,j;vertexNum=18;arcNum=30; for(i=0;i<vertexNum;i+)adjlisti.vex=ai;adjlisti.vexname=bi;adjlisti.vexinf=ci;adjlisti.dir.ln=xi;adjlisti.dir.col=yi;for (i=0; i<vertexNum; i+)/初始化邻接矩阵for (j=0; j<vertexNum; j+)arcij=arcji=s(i*(i+1)/2+j; /根据s的对称性，将一维数组中的数据赋给二维数组arc template<class T>

14、;void MGraph<T>:printvexname() int i;for(i=0;i<vertexNum;i+)cout<<adjlisti.vex<<""<<adjlisti.vexname<<endl;template<class T>void MGraph<T>:printvexinf(int i) cout<<i<<""<<adjlisti.vexname<<":"<<a

15、djlisti.vexinf<<endl;template<class T>void MGraph<T>: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(dx>0)/即j在i的东边cout<<"向东"<<dx*100<<"m，"elsecout<<&q

16、uot;向西"<<dx*(0-100)<<"m，"if(nb>0)/即j在i的南边cout<<"向南"<<nb*100<<"m"else cout<<"向北"<<nb*(0-100)<<"m"template<class T>void MGraph<T>:Root(int p,int q) if (Pathpq>0) Root(p,Pathpq); Roo

17、t(Pathpq,q); else Linekkk=q; kkk+; template<class T>void MGraph<T>:printroad(int i,int j) int p,q,m,k,item1,item2; for(p=0;p<vertexNum;p+)for(q=0;q<vertexNum;q+) Distpq=arcpq;/邻接矩阵赋值for(k=0;k<vertexNum;k+) for(p=0;p<vertexNum;p+) if (Distpk>0) for(q=0;q<vertexNum;q+) if

18、 (Distkq>0)if(Distpq>Distpk+Distkq)|(Distpq=0)&&(p!=q)Distpq=Distpk+Distkq; Pathpq=k;cout<<"n=n"cout<<"从"<<adjlisti.vexname<<"到"<<adjlistj.vexname<<"的最短路径为："<<endl;cout<<adjlisti.vexname; kkk=2; Roo

19、t(i,j); item2=Line2; cout<<"->" printdir(i,item2);cout<<"->"<<adjlistitem2.vexname; for(m=3;m<=kkk-1;m+) item1=Linem; cout<<"->"printdir(item1-1,item1);cout<<endl;cout<<"n=n" =以下为main.cpp文件中主函数的实现= #include<io

20、stream> #include"guide.cpp" using namespace std;int funcchoice()/系统功能选择页面 int choice;cout<<"="<<endl; cout<<" 欢迎进入校园导游咨询平台"<<endl; cout<<" 1-显示校园所有景点信息"<<endl; cout<<" 2-查询校园景点信息"<<endl; cout<<

21、" 3-问路查询系统"<<endl; cout<<" 4-退出导游资讯平台"<<endl;cout<<"="<<endl; cout<<"请输入要选择的功能号：" cin>>choice; return choice; void main() MGraph<char*> mg; int funcchoice(); int fc; while(1)fc=funcchoice(); if(fc=1) else if(fc=2

22、) int i; int i;for(i=0;i<mg.vertexNum;i+)mg.printvexinf(i);号："cout<<endl<<"请输入所要查询景点代else if(fc=4)break; cin>>i>>j;mg.printroad(i,j);cin>>i;mg.printvexinf(i);else if(fc=3) int i,j;mg.printvexname();cout<<"请输入两景点代号（我们将把elsecout<<"输入有误，请

23、重新输入！"<<endl; 五、调试分析包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、经验体会。调试时屡次显示中断，后经反复检查发现原来是在定义时景点代号是从0开始的，而在输入景点名称时是从1开始想，所以导致程序运行中断。偶尔会忘记调用函数类模块template<class T>，有些类中或者函数中涉及函数类模块的调用，但忘记标注会导致编译错误。我的解决方法是在写程序中，一旦写到“T”，就立刻到前面找类模块的定义，如果发现没写就赶紧补上。容易将类或函数名中的大写字母错写成小写字母，有时甚至导致编译正确，连接错误，error不能指出错误的情况发

24、生，使程序查对过程较长，我的解决办法是，以后在编程中应尽量使用统一的书写形式，如全部大写或全部小写。Floyed算法的时间空间复杂性分析：本程序中的Floyed算法对邻接矩阵每一个元素都进行了N（N即为景点个数）遍比较，所以时间复杂度是O(N3)；存放两点间最短路径前驱结点的path矩阵占用了N*N的空间，所以时间复杂度是O(N2)。六、测试结果 七 、附录：程序设计源代码#include<iostream>#include<iomanip>using namespace std;const int MaxSize=18;const int INFINITY=999;/

25、最大值无穷class direction;template <class T> class MGraph;template <class T>class VertexNode/定义头结点friend class MGraph<T> public:int vex;/顶点名称T vexname;/顶点名称T vexinf;/顶点信息direction dir;/存放顶点方位信息的direction类的dir。;class directionpublic:int ln;/存放在方向图中的横坐标，表示东西int col;/存放在方向图中的纵坐标，表示南北;templ

26、ate <class T>class MGraph/定义无向图的邻接矩阵public:MGraph(); /构造函数，初始化具有n个顶点的图void pvexname();/显示所有景点及景点代号void pvexinf(int i);/显示代号为i景点的名称及信息void proad(int i,int j);/显示景点ij的最短路径方案信息void pdir(int i,int j);/显示景点i到j的方向信息，如“向东m，向南m”VertexNode<T> adjlistMaxSize; /存放景点全部信息的景点类数组int vertexNum,arcNum; /

27、图的顶点数和边数void Root(int p,int q);/递归寻找pq间的最短路径int PathMaxSizeMaxSize,DistMaxSizeMaxSize;/创建Path和Dist分别存放两点间最短路径的前驱节点，两点间最短路径长度int LineMaxSize;/Line存放路径int kkk;/Line数组的标记private:T vertexMaxSize; /存放图中顶点的数组int arcMaxSizeMaxSize;/存放图中边的数组;template <class T>MGraph<T>:MGraph()/a为景点代号，b为景点名称，c为景

28、点信息，x为景点方位信息的横坐标，y为景点方位信息的纵坐标/s为存放景点邻接矩阵信息的一维数组，根据其对称性可以用公式赋值给二维数组arcint s=0, 20, 0, 999, 40, 0, 999, 15, 25, 0, 999, 999, 999, 20, 0, 25, 20, 999, 999, 20, 0, 999, 999, 999, 999, 999, 10, 0, 40, 999, 999, 999, 999, 20, 999, 0, 999, 999, 999, 999, 999, 999, 10, 999, 0, 999, 999, 999, 999, 20, 999, 9

29、99, 999, 999, 0, 999, 999, 40, 999, 15, 999, 999, 999, 999, 10, 0, 999, 999, 999, 999, 999, 999, 999, 10, 20, 999, 999, 0, 999, 999, 999, 999, 999, 999, 999, 999, 999, 20, 10, 20, 0, 999, 999, 999, 999, 999, 999, 999, 999, 999, 999, 999, 10, 999, 0,;int a=0,1,2,3,4,5,6,7,8,9,10,11,12,13;char* b=&quo

30、t;北校门","北教","崇德楼","北图","北运动场","行政楼","文化活动中心","南校门","南教","南图","大礼堂","大学生文化活动中心","情人坡","南体"char* c="学校北边的出入口","学校北边的教学楼，包含北到北","经管学院楼",&q

31、uot;北边的图书馆，图书库","北边的运动场，包含操场、健身房等","计算机办公楼","俗称H楼，有乒乓球桌、瑜伽房、社联值班室等","学校南边的出入口","学校南边的教学楼，包含南教到南教","学校南边的图书馆，主要自习","主要活动举办地","包含舞厅、团委办公室等","包含一个广场及网球场","南边的体育馆"int x=10,20,50,40,40,20,20,10,20,40,

32、50,20,40,20;int y=20,10,10,20,40,40,50,60,60,60,60,80,80,90;int i,j;vertexNum=14;arcNum=30; for(i=0;i<vertexNum;i+)adjlisti.vex=ai;adjlisti.vexname=bi;adjlisti.vexinf=ci;adjlisti.dir.ln=xi;adjlisti.dir.col=yi;for (i=0; i<vertexNum; i+)/初始化邻接矩阵for (j=0; j<vertexNum; j+)arcij=arcji=s(i*(i+1)/

33、2+j; /根据s的对称性，将一维数组中的数据赋给二维数组arc template<class T>void MGraph<T>:pvexname()int i;for(i=0;i<vertexNum;i+)cout<<adjlisti.vex<<" "<<adjlisti.vexname<<endl;template<class T>void MGraph<T>:pvexinf(int i)cout<<i<<" "<<

34、;adjlisti.vexname<<":"<<adjlisti.vexinf<<endl;template<class T>void MGraph<T>:pdir(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(dx>0)/即j在i的东边cout<<"向东"<<dx*100

35、<<"m，"elsecout<<"向西"<<dx*(0-100)<<"m，"if(nb>0)/即j在i的南边cout<<"向南"<<nb*100<<"m"elsecout<<"向北"<<nb*(0-100)<<"m"template<class T>void MGraph<T>:Root(int p,int

36、q) if (Pathpq>0) Root(p,Pathpq); Root(Pathpq,q); else Linekkk=q; kkk+; template<class T>void MGraph<T>:proad(int i,int j)int p,q,m,k,item1,item2;for(p=0;p<vertexNum;p+)for(q=0;q<vertexNum;q+)Distpq=arcpq;/邻接矩阵赋值for(k=0;k<vertexNum;k+) for(p=0;p<vertexNum;p+)if (Distpk>0) for(q=0;q<vertexNum;q+) if (Distkq>0) if (Distpq>Distpk+Distkq)|(Distpq=0)&&(p!=q) Distpq=Distpk+Distkq; Pathpq=k; cout<<"n=n"cout<<"从"<<adjlisti.vexname<<"到"<<adjlistj.vexname<<&quo