数据结构课程设计_校园导航问题(能通)

1、数据结构课程设计题 目: 校园导航问题 学 院： 班 级： 学 生 姓 名： 学 生 学 号： 指 导 教 师： 2012年 12月5日课程设计任务书姓名班级学号设计题目校园导航问题理论要点1、 利用数据结构中所学顶点、边路径、图、无向网知识，分别表示校园景点、景点距离、导航示意图，实现校园导航。2、 根据路径带权图分析最短路径，实现校园各景点的最短距离。设计目标1、实现校园景点信息查询。2、实现校园景点最短路径查询。3、可以实现直接退出系统。研究方法步骤1、 想出编写思路2、 开始编写程序3、 试着运行程序4、 检出错误程序5、 找到解决方法预期结果实现当初设计的目标，只是保证实现景点信息查

2、询和最短路径查询。计划与进步的安排1、2012年11月25日之前寻找到解决校园导航问题思路2、2012年11月30日之前必须编写出程序3、2012年12月01日之前检查程序的运行并找出错误程序4、2012年12月02日之前找到解决错误的方法5、2012年12月05日写出数据结构课程设计报告摘要 针对学校现代化的实现，为了来访我校的访客能够更方便的了解学校的景点，便于参观也减少导游人员的数量，于是编写了这个校园导航系统。随着现在科技的发展，智能化也不是一个名词，而是实在的随处可见的。算法设计与分析对于程序的实现起着非常重要的作用，思路才是程序的核心。我们完全可以乘科技发展的东风，智能化的新生活而

3、奋斗，努力实现我们理想的社会生活，相关知识的学习，给了我们这个条件，更好地服务方便了人们在较大校园面积的找地儿难问题。这个程序的实现加深了对数据结构算法的了解及C+的巩固，同时为我校加快智能化进程贡献一份力，为更面大学添砖加瓦。这个校园导航系统利用算法设计里的图来解决它将校园景点作为图的结点将景点间的路径作为图的边路径距离作为边的权值。这样一来求两景点间最短路径的问题就抽象成了求图中一结点到另一结点的问题。这也是计算机代替人工的一个实例也充分体现算法的重要。关键词 算法设计与分析，路径，权，无向图 目录摘要I课程设计题目11需求分析12概要设计13详细设计24调试分析125用户使用说明126测

4、试结果137 总结体会15参考文献16I数据结构课程设计校园导航问题1 需求分析1.1基本要求（a）设计校园平面图，在校园景点选10个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。（b）为来访客人提供图中任意景点相关信息的查询。（c）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。1.2基本输入(a)请使用服务：1.景点信息查询请按 1 键 2.景点最短路径查询请按 2 键 3.退出系统请按 3 键(b)景点简介查询（请输入110）。请输入查询景点编号：(c)景点最短路径查询。请输入要查询的两个景点的编号(1

5、->10的数字编号并用' '间隔):1.3输入范围使用服务：13，景点查询：110，景点最短路径查询：110。2 概要设计2.1主要思想校园导航模型是由景点和景点之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表景点，用图的边代表景点之间的路径，结点值代表景点信息，边的权值代表景点间的距离。结点值及边的权值用顺序表存储，所以需要设计一个顺序表类。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线为方便操作，所以给每个景点一个代码用结构体类型实现。计算路径长度和最短路线时可用狄克斯特拉Dijkastra算法实现。最后用switch选择语句

6、选择执行浏览推荐路线或查询最短路径并且主页面会简单描述景点的信息。 2.2程序的主要功能（1）查询功能： 查询两景点间的最短路径需要写求最短路径的函数来实现而对于最短路径用上图的边的权值问题由造图函数实现造图函数显示功能模块有说明。 （2）显示功能： 在校园导航系统的首页就要显示主要的选择菜单而菜单则由主函数调用主菜单和造图函数以及说明函数来实现。在进行查询两景点的路径时也会显示路径则有一个输出函数执行。（3）退出系统： 选择3可推出程序。 3详细设计程序设计具体如下：#include<iostream>#include<string>using namespace s

7、td;#define MaxVertexNum 50 /*景点个数最大50*/#define MAXCOST 1000 /*定义路径的无穷大*/#define T 8 /*目前景点个数*/typedef struct char name20; /*景点名称*/ char number15; /*景点代号*/ char introduce100; /*景点简介*/Elemtype;typedef struct int num; /*顶点编号*/ Elemtype date; /*顶点信息*/Vertex; /*定义顶点*/typedef struct Vertex vexsMaxVertexNu

8、m; /*存放顶点的一维数组,数组第零个单元没有用上*/ unsigned int edgesMaxVertexNumMaxVertexNum; /*存放路径的长度*/ int n,e;MGraph;MGraph MGr; /*全局变量,定义MGr为MGraph类型*/int shortestMaxVertexNumMaxVertexNum; /*定义全局变量存贮最小路径*/int pathMaxVertexNumMaxVertexNum; /*定义存贮路径*/void init() int i,j; MGr.vexs1.num=1; strcpy(MG,&q

9、uot;学校北门"); strcpy(MGr.vexs1.date.number,"001"); strcpy(MGroduce,"没见过开几次，可能你将来当主席了给你开"); MGr.vexs2.num=2; strcpy(MG,"教学主楼"); strcpy(MGr.vexs2.date.number,"002"); strcpy(MGroduce,"学校主教学楼，我们上课的地方。")

10、; MGr.vexs3.num=3; strcpy(MG,"科技大厦"); strcpy(MGr.vexs3.date.number,"003"); strcpy(MGroduce,"上课、上自习的地方。"); MGr.vexs4.num=4; strcpy(MG,"图书馆"); strcpy(MGr.vexs4.date.number,"004"); strcpy(MGr.vexs4.date.

11、introduce,"借书自习的地方。"); MGr.vexs5.num=5; strcpy(MG,"体育场"); strcpy(MGr.vexs5.date.number,"005"); strcpy(MGroduce,"举办运动会的地方。"); MGr.vexs6.num=6; strcpy(MG,"第十八公寓"); strcpy(MGr.vexs6.date.number,"006

12、"); strcpy(MGroduce,"帅哥住的地方。"); MGr.vexs7.num=7; strcpy(MG,"信息报告大厅"); strcpy(MGr.vexs7.date.number,"007"); strcpy(MGroduce,"开会、开讲座的地方。"); MGr.vexs8.num=8; strcpy(MG,"东湖"); strcpy(

13、MGr.vexs8.date.number,"008"); strcpy(MGroduce,"散心的好地方，风景优美。"); MGr.vexs9.num=9; strcpy(MG,"沁芳园"); strcpy(MGr.vexs9.date.number,"009"); strcpy(MGroduce,"吃饭的首选之地。"); MGr.vexs10.num=10; strcpy(MGr.vexs10.

14、,"理学院"); strcpy(MGr.vexs10.date.number,"010"); strcpy(MGroduce,"帅哥所在的院系。小六也在"); for(i=1;i<=T;i+) for(j=1;j<=T;j+) MGr.edgesij=MAXCOST; for(i=1;i<=T;i+) shortestii=0; /*初始化*/ MGr.edges12=MGr.edges21=100; MGr.edges25=MGr.edges52=50; MGr.

15、edges13=MGr.edges31=200; MGr.edges28=MGr.edges82=1500; MGr.edges57=MGr.edges75=50; MGr.edges78=MGr.edges87=700; MGr.edges67=MGr.edges76=500; MGr.edges34=MGr.edges43=50; MGr.edges46=MGr.edges64=450; MGr.edges49=MGr.edges94=20; MGr.edges310=MGr.edges103=10; MGr.edges11=MGr.edges22=MGr.edges33=MGr.edge

16、s44=MGr.edges55=0; MGr.edges66=MGr.edges77=MGr.edges88=MGr.edges99=MGr.edges1010=0; void introduce() int n; cout<<"请输入查询景点编号："<<endl; cin>>n; switch(n) case 1: cout<<"景点编号："<<MGr.vexs1.date.number<<"景点名称："<<MG;

17、cout<<"景点简介："<<MGroduce<<endl; break; case 2: cout<<"景点编号："<<MGr.vexs2.date.number<<"景点名称："<<MG; cout<<"景点简介："<<MGroduce<<endl; break; case 3: cout<

18、<"景点编号："<<MGr.vexs3.date.number<<"景点名称："<<MG; cout<<"景点简介："<<MGroduce<<endl; break; case 4: cout<<"景点编号："<<MGr.vexs4.date.number<<"景点名称："<<MGr.vexs4.date.

19、name; cout<<"景点简介："<<MGroduce<<endl; break; case 5: cout<<"景点编号："<<MGr.vexs5.date.number<<"景点名称："<<MG; cout<<"景点简介："<<MGroduce<<endl; break; case 6: co

20、ut<<"景点编号："<<MGr.vexs6.date.number<<"景点名称："<<MG; cout<<"景点简介："<<MGroduce<<endl; break; case 7: cout<<"景点编号："<<MGr.vexs7.date.number<<"景点名称："<<MGr.vexs7

21、.; cout<<"景点简介："<<MGroduce<<endl; break; case 8: cout<<"景点编号："<<MGr.vexs8.date.number<<"景点名称："<<MG; cout<<"景点简介："<<MGroduce<<endl; break; case

22、 9: cout<<"景点编号："<<MGr.vexs9.date.number<<"景点名称："<<MG; cout<<"景点简介："<<MGroduce<<endl; break; case 10: cout<<"景点编号："<<MGr.vexs10.date.number<<"景点名称："<<M

23、G; cout<<"景点简介："<<MGroduce<<endl; break; default: cout<<"输入序号错误。" break; void floyd() int i,j,k; for(i=1;i<=T;i+) for(j=1;j<=T;j+) shortestij=MGr.edgesij; pathij=0; /*初始化数组*/ for(k=1;k<=T;k+) for(i=1;i<=T;i+)

24、for(j=1;j<=T;j+) if(shortestij>(shortestik+shortestkj) shortestij=shortestik+shortestkj; pathij=k; pathji=k;/*记录经过的路径*/ /end_if /end_forvoid display(int i,int j)/* 打印两个景点的路径及最短距离 */ int a,b; a=i; b=j; cout<<"您要查询的两景点间最短路径是:nn" if(shortestij!=MaxVertexNum) if(i<j) cout<<

25、;b; while(pathij!=0) /* 把i到j的路径上所有经过的景点按逆序打印出来*/ cout<<"<-"<<pathij; if(i<j) j=pathij; else i=pathji; cout<<"<-"<<a; cout<<"nn" cout<<a<<"->"<<b<<"最短距离是"<<shortestab<<"

26、;米"<<"nn" else cout<<a; while(pathij!=0) /* 把i到j的路径上所有经过的景点按顺序打印出来*/ cout<<"->"<<pathij; if(i<j) j=pathij; else i=pathji; cout<<"->"<<b; cout<<"nn" cout<<a<<"->"<<b<<&

27、quot;最短距离是:"<<shortestab<<"米nn"<<endl; else cout<<"输入错误！不存在此路！nn" /*display*/int shortestdistance()/*要查找的两景点的最短距离*/ int i,j; cout<<"请输入要查询的两个景点的编号(1->10的数字编号并用' '间隔):" cin>>i>>j; if(i>T|i<=0|j>T|j<0)

28、cout<<"输入信息错误！nn" cout<<" 请输入要查询的两个景点的编号(1->10的数字编号并用' '间隔):n" cin>>i>>j; else floyd(); display(i,j); return 1;/*shortestdistance*/ int main()system("color 2f"); char k; init(); cout<<"*n" cout<<"* Welcome *n

29、" cout<<"* *n" cout<<"* 黑科技校园导游咨询 *n" cout<<"* *n" cout<<"* 学生：高旭强 班级：数学11-1班 学号：21 *n" cout<<"*n" while(1) cout<<"1.景点信息查询请按 1 键n" cout<<"2.景点最短路径查询请按 2 键n" cout<<"3.退出系统请按 3 键n" cout<<"请选择服务:" cin>>k; switch(k) case '1': cout<<"景点简介查询（请输入110）。" introduce(); break; case '2': cout<<"景点最短路径查询。" shortestdistance(); break; case '3': exit(0);