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

上海电力学院数据结构（C++）课程设计题目:校园导游咨询姓名：学号：院系：计算机科学与技术学院专业年级：信息安全20142016年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兼容笔记本电脑操作系统Windows8编程环境MicrosoftVisualStudio20122）输入的形式和输入值的范围内容形式范围景点代号int自然数景点名称string所有字符景点介绍string所有字符Y坐标int正整数X坐标int正整数3）输出的形式描述内容形式范围景点代号int自然数景点名称string所有字符景点介绍string所有字符Y坐标int正整数X坐标int正整数最短路径4）功能描述（1）设计学校的校园平面图，所含景点14个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。(2)为来访客人提供图中任意景点相关信息的查询。(3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一个最短的简单路径，并提示出各景点之间的方位关系，行走方向。（5）测试数据景点编号景点名称景点介绍X坐标Y坐标1北校门学校北边的出入口10202北教学校北边的教学楼，包含北1到北420103崇德楼经管学院楼50104北图北边的图书馆，图书库40205北运动场北边的运动场，包含操场、健身房等40406行政楼计算机办公楼20407文化活动中心俗称H楼，有乒乓球桌、瑜伽房、社联值班室等20508南校门学校南边的出入口10609南教学校南边的教学楼，包含南1教到南4教206010南图学校南边的图书馆，主要自习406011大礼堂主要活动举办地506012大学生文化活动中心包含舞厅、团委办公室等208013情人坡包含一个广场及网球场408014南体南边的体育馆2090距离邻接矩阵：

020999999999259994099999999999999999920040159992099999999999999999999999999940025999999999999999999409999999999991525020999999999999999999999999999999999999200209999999992015999999999252099999920010209999999999999999999999999999999991009991099999999999999940999999999999209990999999999109999999999999999999999991099909999992099999999999999999920999999999999010999209999999994099915999999999999100999109999999999999999999991020999999020109999999999999999999999999992010200999999999999999999999999999999999999109990三、概要设计1）抽象数据类型定义描述（对各类的成员及成员函数进行抽象描述，参见书或ppt及实验）ClassMGraph输入：代号、名称、介绍、X坐标、Y坐标前置条件：无动作：定义邻接矩阵输出：无后置条件：无ClassVertexNode输入：顶点名称，顶点信息，顶点介绍，顶点方位前置条件：定义了Mgraph动作：定义顶点输出：无后置条件：无Classdirection输入：定点的横（东西）、纵（南北）坐标前置条件：无动作：定义路径方位输出：无后置条件：无2）功能模块设计（如主程序模块设计）1.主程序模块：连接调用各种子模块，使用循环等待用户操作，完成程序的基本操作实现功能。2.菜单显示模块:生成每个菜单的显示界面，及开始的选择界面，是系统的实现更加简单清晰。3.用户操作选择模块：由主程序调用函数，是用户的操作可以简单地完成。3）模块层次调用关系图上海电力学院校园导游咨询系统上海电力学院校园导游咨询系统主程序菜单主程序菜单问路查询信息显示所有景点问路查询信息显示所有景点方位信息最短路径Floyed方位信息最短路径Floyed算法返回某景点信息四、详细设计实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。==============以下为guide.cpp文件中对guide.h文件中类的所有成员函数的定义等==============#include<iostream>#include<iomanip>#include"guide.h"usingnamespacestd;template<classT>MGraph<T>::MGraph()//a[]为景点代号，b[]为景点名称，c[]为景点信息，x[]为景点方位信息的横坐标，y[]为景点方位信息的纵坐标//s[]为存放景点邻接矩阵信息的一维数组，根据其对称性可以用公式赋值给二维数组arc[][]{ints[]={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,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,};inta[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14};char*b[]={"北校门","北教","崇德楼","北图","北运动场","行政楼","文化活动中心","南校门","南教","南图","大礼堂","大学生文化活动中心","情人坡","南体"};char*c[]={"学校北边的出入口","学校北边的教学楼，包含北1到北4","经管学院楼","北边的图书馆，图书库","北边的运动场，包含操场、健身房等","计算机办公楼","俗称H楼，有乒乓球桌、瑜伽房、社联值班室等","学校南边的出入口","学校南边的教学楼，包含南1教到南4教","学校南边的图书馆，主要自习","主要活动举办地","包含舞厅、团委办公室等","包含一个广场及网球场","南边的体育馆"};intx[]={10,20,50,40,40,20,20,10,20,40,50,20,40,20};inty[]={20,10,10,20,40,40,50,60,60,60,60,80,80,90};inti,j;vertexNum=18;arcNum=30;for(i=0;i<vertexNum;i++){adjlist[i].vex=a[i];adjlist[i].vexname=b[i];adjlist[i].vexinf=c[i];adjlist[i].dir.ln=x[i];adjlist[i].dir.col=y[i];}for(i=0;i<vertexNum;i++)//初始化邻接矩阵for(j=0;j<vertexNum;j++)arc[i][j]=arc[j][i]=s[(i*(i+1))/2+j];//根据s[]的对称性，将一维数组中的数据赋给二维数组arc[][]}template<classT>voidMGraph<T>::printvexname(){inti;for(i=0;i<vertexNum;i++)cout<<adjlist[i].vex<<""<<adjlist[i].vexname<<endl;;}template<classT>voidMGraph<T>::printvexinf(inti){cout<<i<<""<<adjlist[i].vexname<<":"<<adjlist[i].vexinf<<endl;}template<classT>voidMGraph<T>::printdir(inti,intj){intdx,nb;//临时存放i与j之间的南北东西关系j在i的哪边？？dx=adjlist[j].dir.col-adjlist[i].dir.col;nb=adjlist[j].dir.ln-adjlist[i].dir.ln;if(dx>0)//即j在i的东边cout<<"向东"<<dx*100<<"m，";elsecout<<"向西"<<dx*(0-100)<<"m，";if(nb>0)//即j在i的南边cout<<"向南"<<nb*100<<"m";elsecout<<"向北"<<nb*(0-100)<<"m";}template<classT>voidMGraph<T>::Root(intp,intq){if(Path[p][q]>0){Root(p,Path[p][q]);Root(Path[p][q],q);}else{Line[kkk]=q;kkk++;}}template<classT>voidMGraph<T>::printroad(inti,intj){intp,q,m,k,item1,item2;for(p=0;p<vertexNum;p++)for(q=0;q<vertexNum;q++)Dist[p][q]=arc[p][q];//邻接矩阵赋值for(k=0;k<vertexNum;k++)for(p=0;p<vertexNum;p++)if(Dist[p][k]>0)for(q=0;q<vertexNum;q++)if(Dist[k][q]>0)if(((Dist[p][q]>Dist[p][k]+Dist[k][q])||(Dist[p][q]==0))&&(p!=q)){Dist[p][q]=Dist[p][k]+Dist[k][q];Path[p][q]=k;}cout<<"\n=====================================================\n";cout<<"从"<<adjlist[i].vexname<<"到"<<adjlist[j].vexname<<"的最短路径为："<<endl;cout<<adjlist[i].vexname;kkk=2;Root(i,j);item2=Line[2];cout<<"-->";printdir(i,item2);cout<<"-->"<<adjlist[item2].vexname;for(m=3;m<=kkk-1;m++){item1=Line[m];cout<<"-->";printdir(item1-1,item1);}cout<<endl;cout<<"\n=====================================================\n";}========================以下为main.cpp文件中主函数的实现==========================#include<iostream>#include"guide.cpp"usingnamespacestd;intfuncchoice()//系统功能选择页面{intchoice;cout<<"=============================================================="<<endl;cout<<"欢迎进入校园导游咨询平台"<<endl;cout<<"1--显示校园所有景点信息"<<endl;cout<<"2--查询校园景点信息"<<endl;cout<<"3--问路查询系统"<<endl;cout<<"4--退出导游资讯平台"<<endl;cout<<"=============================================================="<<endl;cout<<"请输入要选择的功能号：";cin>>choice;returnchoice;}voidmain(){MGraph<char*>mg;intfuncchoice();intfc;while(1){fc=funcchoice();if(fc==1){}elseif(fc==2){inti;inti;for(i=0;i<mg.vertexNum;i++)mg.printvexinf(i);号：";cout<<endl<<"请输入所要查询景点代}elseif(fc==4)break;cin>>i>>j;mg.printroad(i,j);}cin>>i;mg.printvexinf(i);elseif(fc==3){inti,j;mg.printvexname();cout<<"请输入两景点代号（我们将把elsecout<<"输入有误，请重新输入！"<<endl;}}五、调试分析包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、经验体会。调试时屡次显示中断，后经反复检查发现原来是在定义时景点代号是从0开始的，而在输入景点名称时是从1开始想，所以导致程序运行中断。偶尔会忘记调用函数类模块template<classT>，有些类中或者函数中涉及函数类模块的调用，但忘记标注会导致编译错误。我的解决方法是在写程序中，一旦写到“T”，就立刻到前面找类模块的定义，如果发现没写就赶紧补上。容易将类或函数名中的大写字母错写成小写字母，有时甚至导致编译正确，连接错误，error不能指出错误的情况发生，使程序查对过程较长，我的解决办法是，以后在编程中应尽量使用统一的书写形式，如全部大写或全部小写。Floyed算法的时间空间复杂性分析：本程序中的Floyed算法对邻接矩阵每一个元素都进行了N（N即为景点个数）遍比较，所以时间复杂度是O(N^3)；存放两点间最短路径前驱结点的path[][]矩阵占用了N*N的空间，所以时间复杂度是O(N^2)。六、测试结果七、附录：程序设计源代码#include<iostream>#include<iomanip>usingnamespacestd;constintMaxSize=18;constintINFINITY=999;//最大值无穷classdirection;template<classT>classMGraph;template<classT>classVertexNode//定义头结点{friendclassMGraph<T>;public:intvex;//顶点名称Tvexname;//顶点名称Tvexinf;//顶点信息directiondir;//存放顶点方位信息的direction类的dir。};classdirection{public:intln;//存放在方向图中的横坐标，表示东西intcol;//存放在方向图中的纵坐标，表示南北};template<classT>classMGraph//定义无向图的邻接矩阵{public:MGraph();//构造函数，初始化具有n个顶点的图voidpvexname();//显示所有景点及景点代号voidpvexinf(inti);//显示代号为i景点的名称及信息voidproad(inti,intj);//显示景点i~j的最短路径方案信息voidpdir(inti,intj);//显示景点i到j的方向信息，如“向东m，向南m”VertexNode<T>adjlist[MaxSize];//存放景点全部信息的景点类数组intvertexNum,arcNum;//图的顶点数和边数voidRoot(intp,intq);//递归寻找pq间的最短路径intPath[MaxSize][MaxSize],Dist[MaxSize][MaxSize];//创建Path和Dist分别存放两点间最短路径的前驱节点，两点间最短路径长度intLine[MaxSize];//Line存放路径intkkk;//Line[]数组的标记private:Tvertex[MaxSize];//存放图中顶点的数组intarc[MaxSize][MaxSize];//存放图中边的数组};template<classT>MGraph<T>::MGraph()//a[]为景点代号，b[]为景点名称，c[]为景点信息，x[]为景点方位信息的横坐标，y[]为景点方位信息的纵坐标//s[]为存放景点邻接矩阵信息的一维数组，根据其对称性可以用公式赋值给二维数组arc[][]{ints[]={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,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,};inta[]={0,1,2,3,4,5,6,7,8,9,10,11,12,13};char*b[]={"北校门","北教","崇德楼","北图","北运动场","行政楼","文化活动中心","南校门","南教","南图","大礼堂","大学生文化活动中心","情人坡","南体"};char*c[]={"学校北边的出入口","学校北边的教学楼，包含北到北","经管学院楼","北边的图书馆，图书库","北边的运动场，包含操场、健身房等","计算机办公楼","俗称H楼，有乒乓球桌、瑜伽房、社联值班室等","学校南边的出入口","学校南边的教学楼，包含南教到南教","学校南边的图书馆，主要自习","主要活动举办地","包含舞厅、团委办公室等","包含一个广场及网球场","南边的体育馆"};intx[]={10,20,50,40,40,20,20,10,20,40,50,20,40,20};inty[]={20,10,10,20,40,40,50,60,60,60,60,80,80,90};inti,j;vertexNum=14;arcNum=30;for(i=0;i<vertexNum;i++){adjlist[i].vex=a[i];adjlist[i].vexname=b[i];adjlist[i].vexinf=c[i];adjlist[i].dir.ln=x[i];adjlist[i].dir.col=y[i];}for(i=0;i<vertexNum;i++)//初始化邻接矩阵for(j=0;j<vertexNum;j++)arc[i][j]=arc[j][i]=s[(i*(i+1))/2+j];//根据s[]的对称性，将一维数组中的数据赋给二维数组arc[][]}template<classT>voidMGraph<T>::pvexname(){inti;for(i=0;i<vertexNum;i++)cout<<adjlist[i].vex<<""<<adjlist[i].vexname<<endl;;}template<classT>voidMGraph<T>::pvexinf(inti){cout<<i<<""<<adjlist[i].vexname<<":"<<adjlist[i].vexinf<<endl;}template<classT>voidMGraph<T>::pdir(inti,intj){intdx,nb;//临时存放i与j之间的南北东西关系j在i的哪边？？dx=adjlist[j].dir.col-adjlist[i].dir.col;nb=adjlist[j].dir.ln-adjlist[i].dir.ln;if(dx>0)//即j在i的东边cout<<"向东"<<dx*100<<"m，";elsecout<<"向西"<<dx*(0-100)<<"m，";if(nb>0)//即j在i的南边cout<<"向南"<<nb*100<<"m";elsecout<<"向北"<<nb*(0-100)<<"m";}template<classT>voidMGraph<T>::Root(intp,intq){if(Path[p][q]>0){Root(p,Path[p][q]);Root(Path[p][q],q);}else{Line[kkk]=q;kkk++;}}template<classT>voidMGraph<T>::proad(inti,intj){intp,q,m,k,item1,item2;for(p=0;p<vertexNum;p++)for(q=0;q<vertexNum;q++)Dist[p][q]=arc[p][q];//邻接矩阵赋值for(k=0;k<vertexNum;k++)for(p=0;p<vertexNum;p++)if(Dist[p][k]>0)for(q=0;q<vertexNum;q++)if(Dist[k][q]>0)if(((Dist[p][q]>Dist[p][k]+Dist[k][q])||(Dist[p][q]==0))&&(p!=q)){Dist[p][q]=Dist[p][k]+Dist[k][q];Path[p][q]=k;}cout<<"\n=====================================================\n";cout<<"从"<<adjlist[i].vexname<<"到"<<adjlist[j].vexname<<"的最短路径为："<<endl;cout<<adjlist[i].vexname;kkk=2;Root(i,j);item2=Line[2];cout<<"-->";pdir(i,item2);cout<<"-->"<<adjlist[item2].vexname;for(m=3;m<=kkk-1;m++){item1=Line[m];cout<<"-->";pdir(item1-1,item1);cout<<"-->"<<adjlist[item1].vexname;}cout<<endl;cout<<"\n=====================================================\n";}intfuncchoice()//系统功能选择页面{intchoice;cout<<"=============================================================="<<endl;cout<<"欢迎进入校园导游咨询平台"<<endl;cout<<"1--显示校园所有景点信息"<<endl;cout<<"2--查询校园景点信息"<<endl;cout<<"3--问路查询系统"<<endl;cout<<"4--退出导游资讯平台"<<endl;cout<<"=============================================================="<<endl;cout<<"请输入要选择的功能号：";cin>>choice;returnchoice;}voidmain(){MGraph<char*>mg;intfuncchoice();intfc;while(1){fc=funcchoice();if(fc==1){inti;for(i=0;i<mg.vertexNum;i++)mg.pvexinf(i);}elseif(fc==2){inti;mg.pvexname();cout<<endl<<"请输入所要查询景点代号：";cin>>i;mg.pvexinf(i);}elseif(fc==3){inti,j;mg.pvexname();cout<<"请输入两景点代号（我们将把最短路线反馈予您）：";cin>>i>>j;ad(i,j);}elseif(fc==4)break;elsecout<<"输入有误，请重新输入！"<<endl;}}基于C8051F单片机直流电动机反馈控制系统的设计与研究基于单片机的嵌入式Web服务器的研究MOTOROLA单片机MC68HC（8）05PV8/A内嵌EEPROM的工艺和制程方法及对良率的影响研究基于模糊控制的电阻钎焊单片机温度控制系统的研制基于MCS-51系列单片机的通用控制模块的研究基于单片机实现的供暖系统最佳启停自校正（STR）调节器单片机控制的二级倒立摆系统的研究基于增强型51系列单片机的TCP/IP协议栈的实现基于单片机的蓄电池自动监测系统基于32位嵌入式单片机系统的图像采集与处理技术的研究基于单片机的作物营养诊断专家系统的研究基于单片机的交流伺服电机运动控制系统研究与开发基于单片机的泵管内壁硬度测试仪的研制基于单片机的自动找平控制系统研究基于C8051F040单片机的嵌入式系统开发基于单片机的液压动力系统状态监测仪开发模糊Smith智能控制方法的研究及其单片机实现一种基于单片机的轴快流CO〈,2〉激光器的手持控制面板的研制基于双单片机冲床数控系统的研究基于CYGNAL单片机的在线间歇式浊度仪的研制基于单片机的喷油泵试验台控制器的研制基于单片机的软起动器的研究和设计基于单片机控制的高速快走丝电火花线切割机床短循环走丝方式研究基于单片机的机电产品控制系统开发基于PIC单片机的智能手机充电器基于单片机的实时内核设计及其应用研究基于单片机的远程抄表系统的设计与研究基于单片机的烟气二氧化硫浓度检测仪的研制基于微型光谱仪的单片机系统单片机系统软件构件开发的技术研究基于单片机的液体点滴速度自动检测仪的研制基于单片机系统的多功能温度测量仪的研制基于PIC单片机的电能采集终端的设计和应用基于单片机的光纤光栅解调仪的研制气压式线性摩擦焊机单片机控制系统的研制基于单片机的数字磁通门传感器基于单片机的旋转变压器-数字转换器的研究基于单片机的光纤Bragg光栅解调系统的研究单片机控制的便携式多功能乳腺治疗仪的研制基于C8051F020单片机的多生理信号检测仪基于单片机的电机运动控制系统设计Pico专用单片机核的可测性设计研究基于MCS-51单片机的热量计基于双单片机的智能遥测微型气象站MCS-51单片机构建机器人的实践研究基于单片机的轮轨力检测基于单片机的GPS定位仪的研究与实现基于单片机的电液伺服控制系统用于单片机系统的MMC卡文件系统研制基于单片机的时控和计数系统性能优化的研究基于单片机和CPLD的粗光栅位移测量系统研究单片机控制的后备式方波UPS提升高职学生单片机应用能力的探究基于单片机控制的自动低频减载装置研究基于单片机控制的水下焊接电源的研究基于单片机的多通道数据采集系统基于uPSD3234单片机的氚表面污染测量仪的研制基于单片机的红外测油仪的研究96系列单片机仿真器研究与设计基于单片机的单晶金刚石刀具刃磨设备的数控改造基于单片机的温度智能控制系统的设计与实现基于MSP430单片机的电梯门机控制器的研制基于单片机的气体测漏仪的研究基于三菱M16C/6N系列单片机的CAN/USB协议转换器基于单片机和DSP的变压器油色谱在线监测技术研究基于单片机的膛壁温度报警系统设计基于AVR单片机的低压无功补偿控制器的设计基于单片机船舶电力推进电机监测系统基于单片机网络的振动信号的采集系统基于单片机的大容量数据存储技术的应用研究基于单片机的叠图机研究与教学方法实践基于单片机嵌入式Web服务器技术的研究及实现基于AT89S52单片机的通用数据采集系统基于单片机的多道脉冲幅度分析仪研究机器人旋转电弧传感角焊缝跟踪单片机控制系统基于单片机的控制系统在PLC虚拟教学实验中的应用研究基于单片机系统的网络通信研究与应用基于PIC16F877单片机的莫尔斯码自动译码系统设计与研究基于单片机的模糊控制器在工业电阻炉上的应用研究基于双单片机冲床数控系统的研究与开发基于Cygnal单片机的μC/OS-Ⅱ的研究基于单片机的一体化智能差示扫描量热仪系统研究基于TCP/IP协议的单片机与Internet互联的研究与实现变频调速液压电梯单片机控制器的研究基于单片机γ-免疫计数器自动换样功能的研究与实现基于单片机的倒立摆控制系统设计与实现单片机嵌入式以太网防盗报警系统