淮海工学院数据结构课程设计报告书——全国著名景点导游咨询

1、淮 海 工 学 院 计算机工程学院课程设计报告设计名称： 数据结构课程设计 选题名称： 全国著名景点导游咨询 姓 名： 学 号： 110913121 专业班级： 软件工程 软件091 系 （院）： 计算机工程学院 设计时间： 2010.12.202010.12.31 设计地点： 软件工程实验室、教室 成绩：指导教师评语： 签名： 年 月 日数据结构课程设计报告 第 17 页，共 16 页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）用户输入某一景点，以及想前往的另一个景点，提供出这两个景点间的最短路径及两个景点间的最经济路径。二 概要设计定义数据类型，包括景点的所有信息。typedef

5、 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) /打

6、印两个景点的路径及最短距离void shortestdistance ();/查询图中任意两个景点间的最短路径void surfe() /用surf算法求两个景点的最经济距离void printpathe(int i,int j) /打印两个景点的路径及最短距离void cheapestdistance ();/查询图中任意两个景点间的最经济路径void main();/该程序主界面三 详细设计1.定义结构体和全局变量typedef structint num;/顶点编号 char nameMAXSIZE;/顶点名称 char introductionMAXLEN;/顶点信息描述VertexT

7、ype;/顶点的结构定义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

8、,6,7,8,9;char *b9=/*各个景点名称*/;/字符串指针数组,用来给每个顶点的名称进行赋值char *c9=/*字符串指针数组,用来给每个顶点的简介信息进行赋值*/;UDN e; e.vexnum=9;/网中顶点的个数为9e.arcnum=14;/网中边的个数为14for(int s=0;s<e.vexnum;s+)e.vexss.num=as;/给每个顶点一个编号strcpy(,bs);/通过字符串复制函数给每个顶点一个名称strcpy(roduction,cs);/通过字符串复制函数给每个顶点加上信息3. 查询各景点的相关信

9、息void introduction(UDN e)/ 查询各景点的相关信息int i;cout<<"请输入您要查询的城市序号："<<endl; cin>>i;for(int j=0;j<e.vexnum;j+)if(i=e.vexsj.num)/在网中找到其编号与输入的顶点编号相同的顶点 cout<<<<"的简介为"<<endl;cout<<roduction<<endl;4. 查询图中任意两个景点间的最短路

10、径void shortestdistance ();/查询图中任意两个景点间的最短路径 int i,j;cout<<"请输入您要查询的两座旅游城市的编号(19)并用空格间隔"<<endl;cin>>i;cin>>j;if(i>MAXV|i<=0|j>MAXV|j<0)cout<<"对不起，您的输入有误！"<<endl;cout<<"请输入您要查询的两座旅游城市的编号(19)并用空格间隔"<<endl;cin>&

11、gt;i;cin>>j;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<=MAXV;j+)if(shortestij>(shortestik+shortestkj)/用path记录从

12、i到j的最短路径上点j的前驱点的序号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(i<j)cout<<b;while(pathij!=0) /把i

13、到j的路径上所有经过的景点按逆序打印出来cout<<"<-"<<pathij; if(i<j)j=pathij;elsei=pathij;cout<<"<-"<<a<<endl; cout<<a<<"到"<<b<<"的最短路径是"<<shortestab<<"公里"<<endl;cout<<"-"<

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

15、quot;<<endl;cout<<"-"<<endl;elsecout<<"输入错误！不存在此路！"<<endl; cout<<"-"<<endl;7. 查询图中任意两个景点间的最经济路径void cheapestdistance ();/查询图中任意两个景点间的最经济路径 /同最短路径算法8.主程序switch(choose) case 1:introduction(e);break; case 2:shortestdistance ( );bre

16、ak; case 3:cheapestdistance ( );break; case 4:break; default:cout<<"请输入正确的序号!"<<endl;break;四 设计与调试分析1. 进入测试界面，输入1即可查询旅游景点相关信息，再选择2北京，即显示出“中国首都，它荟萃了元、明、清以来的中华文化,是世界上拥有世界文化遗产最多的城市。”2. 输入2即可查询两景点间的最短路径，如输入1 3，即从哈尔滨到苏州，显示出哈尔滨到苏州的最短路径为2475公里。3. 输入3即可查询两景点间的最经济路径，如输入2 5，即从北京到广州，显示出从北

17、京到广州的最经济路径为253元。五 用户手册1.用户进入全国著名景点导游咨询界面。2.用户输入1即可查询旅游景点相关信息。3.用户输入2即可查询两景点间的最短路径。4.用户输入3即可查询两景点间的最经济路径。5.用户输入4即可退出本界面。六 测试成果 七 附录（源程序清单）#include<iostream.h>#include<string.h>#include <stdlib.h>#define MAXV 9/最多顶点个数#define MAXSIZE 20/字符串成员name的最大长度#define MAXLEN 500/字符串成员introducti

18、on的最大长度#define INF 32767/表示极大值，即/定义全局变量int costdistanceMAXVMAXV;/边的值/距离int shortestMAXVMAXV;/两点间的最短距离int costmoneyMAXVMAXV;/边的值-行程费用int cheapestMAXVMAXV;/两点int pathMAXVMAXV;/经过的景点typedef structint num;/顶点编号 char nameMAXSIZE;/顶点名称 char introductionMAXLEN;/顶点信息描述VertexType;/顶点的结构定义typedef struct UDNin

19、t edgesMAXVMAXV;/网的邻接矩阵存储 int vexnum,arcnum;/图的顶点数和弧数 VertexType vexsMAXV;/顶点向量UDN;/网的结构定义void introduction(UDN e)/ 查询各景点的相关信息cout<<" *旅游城市：*"<<endl;cout<<" *"<<endl;cout<<" 1.哈尔滨 2.北京 3.苏州"<<endl;cout<<" 4.三亚 5.广州 6.武汉&quo

20、t;<<endl;cout<<" 7.成都 8.昆明 9.拉萨"<<endl;cout<<" *"<<endl;while(1)int i;cout<<"请输入您要查询的城市序号："<<endl; cin>>i;for(int j=0;j<e.vexnum;j+)if(i=e.vexsj.num)/在网中找到其编号与输入的顶点编号相同的顶点cout<<"-"<<endl;cout<&l

21、t;<<"的简介为"<<endl;cout<<roduction<<endl;cout<<"-"<<endl; cout<<"请问您是否需要继续查询？是请输入Y，否请输入N。"<<endl;char a;cin>>a;if(a='N'|a='n')break;void surf() /用surf算法求两个景点的最短距离int i,j,k;for(i=1

22、;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) /用path记录从i到j的最短路径上点j的前驱点的序号shortestij=shortestik+shortestkj;pathij=k;pathji=k;void printpath(int i,int j) /打印两个景点的路径及最短距离

23、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<<"<-"<

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

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

26、quot;<<endl;void shortestdistance ()/查询图中任意两个景点间的最经济路径cout<<" *旅游城市：*"<<endl;cout<<" *"<<endl;cout<<" 1.哈尔滨 2.北京 3.苏州"<<endl;cout<<" 4.三亚 5.广州 6.武汉"<<endl;cout<<" 7.成都 8.昆明 9.拉萨"<<endl

27、;cout<<" *"<<endl;while(1)int i,j;cout<<"请输入您要查询的两座旅游城市的编号(19)并用空格间隔"<<endl;cin>>i;cin>>j;if(i>MAXV|i<=0|j>MAXV|j<0)cout<<"对不起，您的输入有误！"<<endl;cout<<"请输入您要查询的两座旅游城市的编号(19)并用空格间隔"<<endl;cin&

28、gt;>i;cin>>j;elsesurf();printpath(i,j);cout<<"请问您是否需要继续查询？是请输入Y，否请输入N。"<<endl;char a;cin>>a;if(a='N'|a='n')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<=M

29、AXV;k+)for(i=1;i<=MAXV;i+)for(j=1;j<=MAXV;j+)if(cheapestij>(cheapestik+cheapestkj) /用path记录从i到j的最短路径上点j的前驱点的序号cheapestij=cheapestik+cheapestkj;pathij=k;pathji=k;void printpathe(int i,int j) /打印两个景点的路径及最短距离int a,b;a=i;b=j;cout<<"-"<<endl;cout<<"您要查询的两景点间最经济路径

30、是:"<<endl; if(cheapestij!=INF) if(i<j)cout<<b;while(pathij!=0) /把i到j的路径上所有经过的景点按逆序打印出来cout<<"<-"<<pathij; if(i<j)j=pathij;elsei=pathij;cout<<"<-"<<a<<endl;cout<<a<<"->"<<b<<"最经济路径

31、花费是:"<<cheapestab<<"元"<<endl;cout<<"-"<<endl;elsecout<<a;while(pathij!=0) /*把i到j的路径上所有经过的景点按顺序打印出来*/cout<<"->"<<pathij; if(i<j)j=pathij;elsei=pathij;cout<<"->"<<b<<endl; cout<&l

32、t;a<<"->"<<b<<"最经济路径花费是:"<<cheapestab<<"元"<<endl; cout<<"-"<<endl;elsecout<<"输入错误！不存在此路！"<<endl; cout<<"-"<<endl;void cheapestdistance() /查询图中任意两个景点间的最经济路径cout<&l

33、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,j;cout<<&q

34、uot;请输入您要查询的两座旅游城市的编号(19)并用空格间隔"<<endl;cin>>i;cin>>j;if(i>MAXV|i<=0|j>MAXV|j<0)cout<<"对不起，您的输入有误！"<<endl;cout<<"请输入您要查询的两座旅游城市的编号(19)并用空格间隔"<<endl;cin>>i;cin>>j;elsesurfe();printpathe(i,j);cout<<"请问

35、您是否需要继续查询？是请输入Y，否请输入N。"<<endl;char a;cin>>a;if(a='N'|a='n')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;costdist

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

37、5=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;

38、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;c

39、ostmoney45=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="哈尔滨"

40、,"北京","苏州","三亚","广州","武汉","成都","昆明","拉萨"char *c9="中国著名的历史文化名城和旅游城市，素有共和国长子、冰城、冰城夏都等美称。","中国首都，它荟萃了元、明、清以来的中华文化,是世界上拥有世界文化遗产最多的城市。","苏州是江苏省的经济、对外贸易、工商业和物流中心，也是重要的文化、艺术、教育和交通中心。","三亚是海南著名的热带海滨旅游城市和海港。","广州是全国著名的华侨之乡，也是全国华侨最多的大城市，于2010年成功举办广州亚运会。","华中地区最大都市及中心城市，中国长江中下游特大城市。","成都市，简称蓉，别称锦城、锦官城，自古被誉为天府之国。","我国重要的旅游、商贸城市、西部地区重要的中心城市，亦是滇中城市群的核心圈！","拉萨作为西藏自治区首府，是一座具有1300年历史的古城。"UDN e;e.vexnum=9;/网中顶点的个数为9e.arcnum=14;/网中边的