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

1、淮 海 工 学 院 计算机工程学院课程设计报告设计名称： 数据结构课程设计 选题名称： 全国著名景点导游咨询 姓 名： * 学 号： 201* 专业班级： 软件工程 软件1* 系 （院）： 计算机工程学院 设计时间： 201*.12.24201*.1.4 设计地点： 软件工程实验室、教室 成绩：指导教师评语： 签名： 年 月 日数据结构课程设计报告 第 18 页，共 页1课程设计目的1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方

2、法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。2课程设计任务与要求：任务根据教材数据结构-C语言描述（耿国华主编）和参考书数据结构题集（C语言版）（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。设计题目从任务书所列选题表中选取，每班每题不得超过2人。学生自选课题学生原则上可以结合个人爱好自选课题，要求课题有一定的深度与难度，有一定的算法复杂性，能够巩固数

3、据结构课程所学的知识。学生自选课题需在18周前报课程设计指导教师批准方可生效。要求：1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。 2、.设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。3、程序设计语言推荐使用C/C+，程序书写规范，源程序需加必要的注释;4、每位同学需提交可独立运行的程序；5 、每位同学需独立提交设计报告书（每人一份）

4、，要求编排格式统一、规范、内容充实，不少于10页（代码不算）；6、课程设计实践作为培养学生动手能力的一种手段，单独考核。 3课程设计说明书一 需求分析（1）查询各景点的相关信息；（2）查询图中任意两个景点间的最短路径（3）查询图中任意两个景点间的最经济路径（4）根据游客计划的旅游费，为游客推荐最节省的旅游线路与景点二 概要设计定义数据类型，包括景点的所有信息。typedef structint num; /顶点编号 char nameMAXSIZE; /顶点名称 char introductionMAXLEN; /顶点信息描述VertexType; /顶点的结构定义typedef struct

5、 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

6、(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 vex

7、sMAXV;/顶点向量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.v

8、exnum=9;/网中顶点的个数为9e.arcnum=14;/网中边的个数为14for(int s=0;s<e.vexnum;s+)e.vexss.num=as;/给每个顶点一个编号strcpy(,bs);/通过字符串复制函数给每个顶点一个名称strcpy(roduction,cs);/通过字符串复制函数给每个顶点加上信息3. 查询各景点的相关信息void introduction(UDN e)/ 查询各景点的相关信息int i;cout<<"请输入您要查询的城市序号："<<endl; cin>

9、;>i;for(int j=0;j<e.vexnum;j+)if(i=e.vexsj.num)/在网中找到其编号与输入的顶点编号相同的顶点 cout<<<<"的简介为"<<endl;cout<<roduction<<endl;4. 查询图中任意两个景点间的最短路径void shortestdistance ();/查询图中任意两个景点间的最短路径 int i,j;cout<<"请输入您要查询的两座旅游城市的编号(19)并用空格间隔&qu

10、ot;<<endl;cin>>i;cin>>j;if(i>MAXV|i<=0|j>MAXV|j<0)cout<<"对不起，您的输入有误！"<<endl;cout<<"请输入您要查询的两座旅游城市的编号(19)并用空格间隔"<<endl;cin>>i;cin>>j;elsesurf();printpath(i,j); 5. 用surf算法求两个景点的最短距离void surf() /用surf算法求两个景点的最短距离int i

11、,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<=MAXV;j+)if(shortestij>(shortestik+shortestkj)shortestij=shortestik+shortestkj;pathij=k;pathji=k;6. 打印两个景点的路径及最短距离void printpath(int i,int j) /打印两个景点的路径及最短

12、距离int a,b;a=i;b=j;cout<<"-"<<endl;cout<<"您要查询的两景点间最短路径是:"<<endl; if(shortestij!=INF) if(i<j)cout<<b;while(pathij!=0) /把i到j的路径上所有经过的景点按逆序打印出来cout<<"<-"<<pathij; if(i<j)j=pathij;elsei=pathij;cout<<"<-"&

13、lt;<a<<endl; cout<<a<<"到"<<b<<"的最短路径是"<<shortestab<<"公里"<<endl;cout<<"-"<<endl;elsecout<<a; while(pathij!=0) /把i到j的路径上所有经过的景点按顺序打印出来cout<<"->"<<pathij; if(i<j)j=pa

14、thij;elsei=pathij;cout<<"->"<<b<<endl;cout<<a<<"到"<<b<<"的最短路径是"<<shortestab<<"公里"<<endl;cout<<"-"<<endl;elsecout<<"输入错误！不存在此路！"<<endl; cout<<"

15、-"<<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. 函数主要调用关系图四

16、 设计与调试分析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. 用户输入

17、2即可查询两景点间的最短路径。4. 用户输入3即可查询两景点间的最经济路径。5. 用户输入4即可退出本界面。六 测试成果1.系统主菜单：2.查询各大城市的简介：3.查询两个景点间的最短路线： 4.查询两景点间最经济的路线：5.退出系统七 附录（源程序清单）#include<iostream.h>#include<string.h>#include<stdlib.h>#define MAXV 9#define MAXSIZE 20#define MAXLEN 500#define INF 32767/定义全局变量int costdistanceMAXVMAXV

18、;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&l

19、t;<" *旅游城市：*"<<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<<

20、"请输入您要查询的城市序号："<<endl; cin>>i;if(i<1|i>10)cout<<"对不起，您的输入有误！"<<endl<<endl;elsefor(int j=0;j<e.vexnum;j+)if(i=e.vexsj.num)cout<<"-"<<endl;cout<<<<"的简介为"<<endl;cout<<e.vexsj.i

21、ntroduction<<endl;cout<<"-"<<endl; cout<<"请问您是否需要继续查询？是请输入Y，否请输入N。"<<endl;char a;cin>>a;if(a='N'|a='n')break;else if(a='Y'|a='y');else cout<<"对不起，您的输入有误！"<<endl;void surf() /用surf算法求两个景点的最短距

22、离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<=MAXV;j+)if(shortestij>(shortestik+shortestkj) shortestij=shortestik+shortestkj;pathij=k;pathji=k;void printpath(int i,int j) /打印两个景点的路径及最短距离int a,b;a

23、=i;b=j;cout<<"-"<<endl;cout<<"您要查询的两景点间最短路径是:"<<endl; if(shortestij!=INF) if(i<j)cout<<b;while(pathij!=0)cout<<"<-"<<pathij; if(i<j)j=pathij;elsei=pathij;cout<<"<-"<<a<<endl; cout<<a

24、<<"到"<<b<<"的最短路径是"<<shortestab<<"公里"<<endl;cout<<"-"<<endl;elsecout<<a; while(pathij!=0) cout<<"->"<<pathij; if(i<j)j=pathij;elsei=pathij;cout<<"->"<<b&l

25、t;<endl;cout<<a<<"到"<<b<<"的最短路径是"<<shortestab<<"公里"<<endl;cout<<"-"<<endl;elsecout<<"输入错误！不存在此路！"<<endl; cout<<"-"<<endl;void shortestdistance ()/查询图中任意两个景点间的最

26、短路径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;c

27、out<<"请输入您要查询的两座旅游城市的编号(19)并用空格间隔"<<endl;cin>>i;cin>>j;if(i>MAXV|i<=0|j>MAXV|j<0)cout<<"对不起，您的输入有误！"<<endl;elsesurf();printpath(i,j);cout<<"请问您是否需要继续查询？是请输入Y，否请输入N。"<<endl;char a;cin>>a;if(a='N'|a

28、='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+)fo

29、r(j=1;j<=MAXV;j+)if(cheapestij>(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(i<j)cout&

30、lt;<b;while(pathij!=0) cout<<"<-"<<pathij; if(i<j)j=pathij;elsei=pathij;cout<<"<-"<<a<<endl;cout<<a<<"->"<<b<<"最经济路径花费是:"<<cheapestab<<"元"<<endl;cout<<"

31、-"<<endl;elsecout<<a;while(pathij!=0) cout<<"->"<<pathij; if(i<j)j=pathij;elsei=pathij;cout<<"->"<<b<<endl; cout<<a<<"->"<<b<<"最经济路径花费是:"<<cheapestab<<"元"&

32、lt;<endl; cout<<"-"<<endl;elsecout<<"输入错误！不存在此路！"<<endl; cout<<"-"<<endl;void cheapestdistance() /查询图中任意两个景点间的最经济路径cout<<" *旅游城市：*"<<endl;cout<<" *"<<endl;cout<<" 1.哈尔滨 2.北京 3.

33、苏州"<<endl;cout<<" 4.三亚 5.广州 6.武汉"<<endl;cout<<" 7.成都 8.昆明 9.拉萨"<<endl;cout<<" *"<<endl;while(1)int i,j;cout<<"请输入您要查询的两座旅游城市的编号(19)并用空格间隔"<<endl;cin>>i;cin>>j;if(i>MAXV|i<=0|j>MAXV

34、|j<0)cout<<"对不起，您的输入有误！"<<endl;cout<<"请输入您要查询的两座旅游城市的编号(19)并用空格间隔"<<endl;cin>>i;cin>>j;elsesurfe();printpathe(i,j);cout<<"请问您是否需要继续查询？是请输入Y，否请输入N。"<<endl;char a;cin>>a;if(a='N'|a='n')break;else if(

35、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=13

36、78; costdistance24=costdistance42=3451;costdistance25=costdistance52=2294; costdistance26=costdistance62=1450;costdistance27=costdistance72=2211; costdistance28=costdistance82=1122;costdistance29=costdistance92=4064; costdistance35=costdistance53=1878;costdistance45=costdistance54=1157; costdistance

37、56=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+)fo

38、r(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; costmon

39、ey35=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;

40、char *b9="哈尔滨","北京","苏州","三亚","广州","武汉","成都","昆明","拉萨"char *c9="中国著名的历史文化名城和旅游城市，素有共和国长子、冰城、冰城夏都等美称。","中国首都，它荟萃了元、明、清以来的中华文化,是世界上拥有世界文化遗产最多的城市。","苏州是江苏省经济、对外贸易、工商业和物流中心，也是重要的文化、艺术、教育和交通

41、中心。","三亚是海南著名的热带海滨旅游城市和海港。","广州是全国著名的华侨之乡，也是全国华侨最多的大城市，于2010年成功举办广州亚运会。","华中地区最大都市及中心城市，中国长江中下游特大城市。","成都市，简称蓉，别称锦城、锦官城，自古被誉为天府之国。","我国重要的旅游、商贸城市、西部地区重要的中心城市，亦是滇中城市群的核心圈！","拉萨作为西藏自治区首府，是一座具有1300年历史的古城。"UDN e;e.vexnum=9;e.arcnum=14;for(

42、int s=0;s<e.vexnum;s+)e.vexss.num=as;strcpy(,bs);strcpy(roduction,cs);int choose;while(1)system("cls");cout<<endl;cout<<" 全国著名景点导游咨询系统 "<<endl;cout<<endl;cout<<" *"<<endl;cout<<" * *"<<e

43、ndl;cout<<" * 1.查询旅游景点相关信息 *"<<endl;cout<<" * 2.查询两景点间的最短路径 *"<<endl;cout<<" * 3.查询两景点间的最经济路径 *"<<endl;cout<<" * 4.退出 *"<<endl;cout<<" * *"<<endl;cout<<" *"<<endl;cout<<" 请输入您想进行的操作序号： "<<endl;cin>>choose;switch(choose)case 1:introduction(e);break;case 2:sh