数据结构课程设计报告-全国著名景点导游咨询01.doc

淮 海 工 学 院 计算机工程学院课程设计报告设计名称： 数据结构课程设计 选题名称： 全国著名景点导游咨询 姓 名： * 学 号： 201* 专业班级： 软件工程 软件1* 系 （院）： 计算机工程学院 设计时间： 201*.12.24201*.1.4 设计地点： 软件工程实验室、教室 成绩：指导教师评语： 签名： 年 月 日数据结构课程设计报告 第 18 页，共 页1课程设计目的1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。2课程设计任务与要求：任务根据教材数据结构-C语言描述（耿国华主编）和参考书数据结构题集（C语言版）（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。设计题目从任务书所列选题表中选取，每班每题不得超过2人。学生自选课题学生原则上可以结合个人爱好自选课题，要求课题有一定的深度与难度，有一定的算法复杂性，能够巩固数据结构课程所学的知识。学生自选课题需在18周前报课程设计指导教师批准方可生效。要求：1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。 2、.设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。3、程序设计语言推荐使用C/C+，程序书写规范，源程序需加必要的注释;4、每位同学需提交可独立运行的程序；5 、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）；6、课程设计实践作为培养学生动手能力的一种手段，单独考核。 3课程设计说明书一 需求分析（1）查询各景点的相关信息；（2）查询图中任意两个景点间的最短路径（3）查询图中任意两个景点间的最经济路径（4）根据游客计划的旅游费，为游客推荐最节省的旅游线路与景点二 概要设计定义数据类型，包括景点的所有信息。typedef structint num; /顶点编号 char nameMAXSIZE; /顶点名称 char introductionMAXLEN; /顶点信息描述VertexType; /顶点的结构定义typedef struct UDNint edgesMAXVMAXV; /网的邻接矩阵存储 int vexnum,arcnum; /图的顶点数和弧数 VertexType vexsMAXV; /顶点向量UDN; /网的结构定义void introduction(UDN e) / 查询各景点的相关信息void surf() /用surf算法求两个景点的最短距离void printpath(int i,int j) /打印两个景点的路径及最短距离void shortestdistance (); /查询图中任意两个景点间的最短路径void surfe() /用surf算法求两个景点的最经济距离void printpathe(int i,int j) /打印两个景点的路径及最短距离void cheapestdistance (); /查询图中任意两个景点间的最经济路径void main(); /该程序主界面三 详细设计1.定义结构体和全局变量typedef structint num;/顶点编号 char nameMAXSIZE;/顶点名称 char introductionMAXLEN;/顶点信息描述VertexType;/顶点的结构定义typedef struct UDNint edgesMAXVMAXV;/网的邻接矩阵存储 int vexnum,arcnum;/图的顶点数和弧数 VertexType vexsMAXV;/顶点向量UDN;/网的结构定义int costdistanceMAXVMAXV;/边的值/距离int shortestMAXVMAXV;/两点间的最短距离int costmoneyMAXVMAXV;/边的值-行程费用int cheapestMAXVMAXV;/两点int pathMAXVMAXV;/经过的景点2.创建全国旅游景点的无向图int i,j;int a9=1,2,3,4,5,6,7,8,9;char *b9=/*各个景点名称*/;/字符串指针数组,用来给每个顶点的名称进行赋值char *c9=/*字符串指针数组,用来给每个顶点的简介信息进行赋值*/;UDN e; e.vexnum=9;/网中顶点的个数为9e.arcnum=14;/网中边的个数为14for(int s=0;se.vexnum;s+)e.vexss.num=as;/给每个顶点一个编号strcpy(,bs);/通过字符串复制函数给每个顶点一个名称strcpy(roduction,cs);/通过字符串复制函数给每个顶点加上信息3. 查询各景点的相关信息void introduction(UDN e)/ 查询各景点的相关信息int i;cout请输入您要查询的城市序号：i;for(int j=0;je.vexnum;j+)if(i=e.vexsj.num)/在网中找到其编号与输入的顶点编号相同的顶点 的简介为endl;roductionendl;4. 查询图中任意两个景点间的最短路径void shortestdistance ();/查询图中任意两个景点间的最短路径 int i,j;cout请输入您要查询的两座旅游城市的编号(19)并用空格间隔i;cinj;if(iMAXV|iMAXV|j0)cout对不起，您的输入有误！endl;cout请输入您要查询的两座旅游城市的编号(19)并用空格间隔i;cinj;elsesurf();printpath(i,j); 5. 用surf算法求两个景点的最短距离void surf() /用surf算法求两个景点的最短距离int i,j,k;for(i=1;i=MAXV;i+)for(j=1;j=MAXV;j+)shortestij=costdistanceij;pathij=0;for(k=1;k=MAXV;k+)for(i=1;i=MAXV;i+) for(j=1;j(shortestik+shortestkj)shortestij=shortestik+shortestkj;pathij=k;pathji=k;6. 打印两个景点的路径及最短距离void printpath(int i,int j) /打印两个景点的路径及最短距离int a,b;a=i;b=j;cout-endl;cout您要查询的两景点间最短路径是:endl; if(shortestij!=INF) if(ij)coutb;while(pathij!=0) /把i到j的路径上所有经过的景点按逆序打印出来cout-pathij; if(ij)j=pathij;elsei=pathij;cout-aendl; couta到b的最短路径是shortestab公里endl;cout-endl;elsecouta; while(pathij!=0) /把i到j的路径上所有经过的景点按顺序打印出来coutpathij; if(ij)j=pathij;elsei=pathij;coutbendl;couta到b的最短路径是shortestab公里endl;cout-endl;elsecout输入错误！不存在此路！endl; cout-endl;7. 查询图中任意两个景点间的最经济路径void cheapestdistance ();/查询图中任意两个景点间的最经济路径 /同最短路径算法8. 主程序switch(choose) case 1:introduction(e);break; case 2:shortestdistance ( );break; case 3:cheapestdistance ( );break; case 4:break; default:cout请输入正确的序号!endl;break;9. 函数主要调用关系图四 设计与调试分析1. 进入测试界面，输入1即可查询旅游景点相关信息，再选择2北京，即显示出“中国首都，它荟萃了元、明、清以来的中华文化,是世界上拥有世界文化遗产最多的城市。”2. 输入2即可查询两景点间的最短路径，如输入1 3，即从哈尔滨到苏州，显示出哈尔滨到苏州的最短路径为2475公里。3. 输入3即可查询两景点间的最经济路径，如输入2 5，即从北京到广州，显示出从北京到广州的最经济路径为253元。五 用户手册运行环境：win XP/Vista/7, Microsoft Visual C+ 6.01. 用户进入全国著名景点导游咨询界面。2. 用户输入1即可查询旅游景点相关信息。3. 用户输入2即可查询两景点间的最短路径。4. 用户输入3即可查询两景点间的最经济路径。5. 用户输入4即可退出本界面。六 测试成果1.系统主菜单：2.查询各大城市的简介：3.查询两个景点间的最短路线： 4.查询两景点间最经济的路线：5.退出系统七 附录（源程序清单）#include#include#include#define MAXV 9#define MAXSIZE 20#define MAXLEN 500#define INF 32767/定义全局变量int costdistanceMAXVMAXV;int shortestMAXVMAXV;int costmoneyMAXVMAXV;int cheapestMAXVMAXV;int pathMAXVMAXV;typedef structint num; char nameMAXSIZE; char introductionMAXLEN;int printpathMAXLEN;VertexType;typedef struct UDNint edgesMAXVMAXV; int vexnum,arcnum; VertexType vexsMAXV;UDN;void introduction(UDN e)/ 查询各景点的相关信息cout *旅游城市：*endl;cout *endl;cout 1.哈尔滨 2.北京 3.苏州endl;cout 4.三亚 5.广州 6.武汉endl;cout 7.成都 8.昆明 9.拉萨endl;cout *endl;while(1)int i;cout请输入您要查询的城市序号：i;if(i10)cout对不起，您的输入有误！endlendl;elsefor(int j=0;je.vexnum;j+)if(i=e.vexsj.num)cout-endl;的简介为endl;roductionendl;cout-endl; cout请问您是否需要继续查询？是请输入Y，否请输入N。a;if(a=N|a=n)break;else if(a=Y|a=y);else cout对不起，您的输入有误！endl;void surf() /用surf算法求两个景点的最短距离int i,j,k;for(i=1;i=MAXV;i+)for(j=1;j=MAXV;j+)shortestij=costdistanceij;pathij=0;for(k=1;k=MAXV;k+)for(i=1;i=MAXV;i+)for(j=1;j(shortestik+shortestkj) shortestij=shortestik+shortestkj;pathij=k;pathji=k;void printpath(int i,int j) /打印两个景点的路径及最短距离int a,b;a=i;b=j;cout-endl;cout您要查询的两景点间最短路径是:endl; if(shortestij!=INF) if(ij)coutb;while(pathij!=0)cout-pathij; if(ij)j=pathij;elsei=pathij;cout-aendl; couta到b的最短路径是shortestab公里endl;cout-endl;elsecouta; while(pathij!=0) coutpathij; if(ij)j=pathij;elsei=pathij;coutbendl;couta到b的最短路径是shortestab公里endl;cout-endl;elsecout输入错误！不存在此路！endl; cout-endl;void shortestdistance ()/查询图中任意两个景点间的最短路径cout *旅游城市：*endl;cout *endl;cout 1.哈尔滨 2.北京 3.苏州endl;cout 4.三亚 5.广州 6.武汉endl;cout 7.成都 8.昆明 9.拉萨endl;cout *endl;while(1)int i,j;cout请输入您要查询的两座旅游城市的编号(19)并用空格间隔i;cinj;if(iMAXV|iMAXV|j0)cout对不起，您的输入有误！endl;elsesurf();printpath(i,j);cout请问您是否需要继续查询？是请输入Y，否请输入N。a;if(a=N|a=n)break;else if(a=Y|a=y);else cout对不起，您的输入有误endl; shortestdistance ();break;void surfe() /用surfe算法求两个景点的最经济路径int i,j,k;for(i=1;i=MAXV;i+)for(j=1;j=MAXV;j+)cheapestij=costmoneyij;pathij=0;for(k=1;k=MAXV;k+)for(i=1;i=MAXV;i+)for(j=1;j(cheapestik+cheapestkj) cheapestij=cheapestik+cheapestkj;pathij=k;pathji=k;void printpathe(int i,int j) /打印两个景点的路径及最经济路径int a,b;a=i;b=j;cout-endl;cout您要查询的两景点间最经济路径是:endl; if(cheapestij!=INF) if(ij)coutb;while(pathij!=0) cout-pathij; if(ij)j=pathij;elsei=pathij;cout-aendl;coutab最经济路径花费是:cheapestab元endl;cout-endl;elsecouta;while(pathij!=0) coutpathij; if(ij)j=pathij;elsei=pathij;coutbendl; coutab最经济路径花费是:cheapestab元endl; cout-endl;elsecout输入错误！不存在此路！endl; cout-endl;void cheapestdistance() /查询图中任意两个景点间的最经济路径cout *旅游城市：*endl;cout *endl;cout 1.哈尔滨 2.北京 3.苏州endl;cout 4.三亚 5.广州 6.武汉endl;cout 7.成都 8.昆明 9.拉萨endl;cout *endl;while(1)int i,j;cout请输入您要查询的两座旅游城市的编号(19)并用空格间隔i;cinj;if(iMAXV|iMAXV|j0)cout对不起，您的输入有误！endl;cout请输入您要查询的两座旅游城市的编号(19)并用空格间隔i;cinj;elsesurfe();printpathe(i,j);cout请问您是否需要继续查询？是请输入Y，否请输入N。a;if(a=N|a=n)break;else if(a=Y|a=y);else cout对不起，您的输入有误！endl; cheapestdistance();break;void main()/该程序主界面int i,j;for(i=0;i=MAXV;i+)for(j=0;j=MAXV;j+)costdistanceij=INF;costdistance12=costdistance21=1278; costdistance13=costdistance31=2475;costdistance23=costdistance32=1378; costdistance24=costdistance42=3451;costdistance25=costdistance52=2294; costdistance26=costdistance62=1450;costdistance27=costdistance72=2211; costdistance28=costdistance82=1122;costdistance29=costdistance92=4064; costdistance35=costdistance53=1878;costdistance45=costdistance54=1157; costdistance56=costdistance65=1500;costdistance58=costdistance85=1637; costdistance67=costdistance76=1122;costdistance78=costdistance87=1133;costdistance11=costdistance22=costdistance33=costdistance44=costdistance55=0;costdistance66=costdistance77=costdistance88=costdistance99=0;int p,q;for(p=0;p=MAXV;p+)for(q=0;q=MAXV;q+)costmoneypq=INF;costmoney12=costmoney21=140; costmoney13=costmoney31=266;costmoney23=costmoney32=150; costmoney24=costmoney42=432;costmoney25=costmoney52=253; costmoney26=costmoney62=150;costmoney27=costmoney72=266; costmoney28=costmoney82=320;costmoney29=costmoney92=389; costmoney35=costmoney53=275;costmoney45=costmoney54=209; costmoney56=costmoney65=200;costmoney58=costmoney85=194; costmoney67=costmoney76=200;costmoney78=costmoney87=143;costmoney11=costmoney22=costmoney33=costmoney44=costmoney55=0;costmoney66=costmoney77=costmoney88=costmoney99=0;int a9=1,2,3,4,5,6,7,8,9;char *b9=哈尔滨,北京,苏州,三亚,广州,武汉,成都,昆明,拉萨;char *c9=中国著名的历史文化名城和旅游城市，素有共和国长子、冰城、冰城夏都等美称。,中国首都，它荟萃了元、明、清以来的中华文化,是世界上拥有世界文化遗产最多的城市。,苏州是江苏省经济、对外贸易、工商业和物流中心，也是重要的文化、艺术、教育和交通中心。,三亚是海南著名的热带海滨旅游城市和海港。,广州是全国著名的华侨之乡，也是全国华侨最多的大城市，于2010年成功举办广州亚运会。,华中地区最大都市及中心城市，中国长江中下游特大城市。,成都市，简称蓉，别称锦城、锦官城，自古被誉为天府之国。,我国重要的旅游、商贸城市、西部地区重要的中心城市，亦是滇中城市群的核心圈！,拉萨作为西藏自治区首府，是一座具有1300年历史的古城。;UDN e;e.vexnum=9;e.arcnum=14;for(int s=0;se.vexnum;s+)e.vexss.num=as;strcpy(,bs);strcpy(roduction,cs);int choose;while(1)system(cls);coutendl;cout 全国著名景点导游咨询系统 endl;coutendl;cout *endl;cout * *endl;cout * 1.查询旅游景点相关信息 *endl;cout * 2.查询两景点间的最短路径 *endl;cout * 3.查询两景点间的最经济路径 *endl;cout * 4.退出 *endl;cout * *endl;cout *endl;cout 请输入您想进行的操作序号： choose;switch(choose)case 1:introduction(e);break;case 2:shortestdistance ( );break;case 3:cheapestdistance ( );break;case 4:break;default:cout请输入正确的序号!endl;break; cout-endl;cout请问您是否需要返回主程序？是请输入Y，否请输入N。a;if(a=N|a=n)cout 感谢您使用全国著名景点导游咨询系统endl;co