公园导游图课程设计.docx
- 文档编号:14804304
- 上传时间:2023-06-27
- 格式:DOCX
- 页数:13
- 大小:79.64KB
公园导游图课程设计.docx
《公园导游图课程设计.docx》由会员分享,可在线阅读,更多相关《公园导游图课程设计.docx(13页珍藏版)》请在冰点文库上搜索。
公园导游图课程设计
课程设计
题目
公园导游图
专业
网络工程
班级
1班
姓名
尹颖
指导老师
孙菁
2014
年
12
月
28
日
课程设计任务书
2014~2015学年第1学期
学生姓名:
尹颖吴东旭许益强葛溆李永康朱世豪
专业班级:
12网络工程
指导教师:
孙菁
一、课程设计题目:
公园导游图
二、课程设计内容
给出一张某公园的导游图,游客通过终端询问可知:
从某一景点到另一景点的最短路径。
游客从公园大门进入,选一条最佳路线,使游客可以不重复地游览各景点,最后回到出口(出口就在入口旁边)。
三、进度安排
1.初步完成总体设计,搭好框架,确定人机对话的界面,确定函数个数;
2.完成最低要求:
建立一个文件,包括5个景点情况,能完成遍历功能;
3.进一步要求:
进一步扩充景点数目,画出景点图,有兴趣的同学可以自己扩充系统功能。
四、基本要求
1.界面友好,函数功能要划分好
2.总体设计应画一流程图
3.程序要加必要的注释
4.要提供程序测试方案
5.程序一定要经得起测试,宁可功能少一些,也要能运行起来,不能运行的程序是没有价值的。
摘要
摘要
计算机解决一个具体问题时,大致需要经过下列几个步骤:
首先要从具体问题中抽象出一个适当的数学模型,然后设计一个解此数学模型的算法(Algorithm),最后编出程序、进行测试、调整直至得到最终解答。
寻求数学模型的实质是分析问题,从中提取操作的对象,并找出这些操作对象之间含有的关系,然后用数学的语言加以描述。
计算机算法与数据的结构密切相关,算法无不依附于具体的数据结构,数据结构直接关系到算法的选择和效率。
运算是由计算机来完成,这就要设计相应的插入、删除和修改的算法。
也就是说,数据结构还需要给出每种结构类型所定义的各种运算的算法。
1.问题描述
1.1图的存储结构
图的存储方式很多,这里用的是邻接矩阵的方式。
为了适合用C语言描述,以下假定顶点序号从0开始,即图G的顶点集的一般形式是V(G)={v0,vi,…,Vn-1}。
图的邻接矩阵表示法
(1)用邻接矩阵表示顶点之间的相邻关系;
(2)用一个顺序表来储存顶点信息
图的邻接矩阵(AdacencyMatrix)
设G=(V,E)是具有n个顶点的图,则G的邻接矩阵是具有如下性质的n阶方阵:
若G是网络,则邻接矩阵可定义为:
1.2求最短路径
给定一个带权有向图G=(V,E),其中每条边的权是一个非负实数。
另外,还给定V中的一个顶点,称为源。
现在我们要计算从源到所有其他各顶点的最短路径长度。
这里的长度是指路上各边权之和。
这个问题通常称为单源最短路径问题。
单源最短路径问题
Dijkstra提出按各顶点与源点v间的路径长度的递增次序,生成到各顶点的最短路径的算法。
既先求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依次类推,直到从源点v到其它各顶点的最短路径全部求出为止。
1.3求最小生成树
对于连通的带权图(连通网)G,其生成树也是带权的。
生成树T各边的权值总和称为该树的权,记作:
Te,W(u,v)
TE表示T的边集
w(u,v)表示边(u,v)的权。
权最小的生成树称为G的最小生成树(MinimumSpanningTree)。
最小生成树可简记为MST。
最小生成树性质:
设G=(V,E)是一个连通网络,U是顶点集V的一个真子集。
若(u,v)是G中一条“一个端点在U中(例如:
u∈U),另一个端点不在U中的边(例如:
v∈V-U),且(u,v)具有最小权值,则一定存在G的一棵最小生成树包括此边(u,v)。
2.系统分析
2.1系统流程
本系统主要是实现图的最短路径问题
系统相关抽象数据类型
图的邻接矩阵存储结构形式说明
#defineMaxVertexNuml00统设计
系统功能
提供无向图的生成,并保证了该无向图为一个无向网,同时也提供了计算最短距离的迪杰斯特拉算法,以及图的遍历。
主要函数说明
本系统用了一个类来实现程序,里面包含了4个对象,即voidgraph:
:
picture();voidgraph:
:
creatp(graph&t);voidgraph:
:
floyd(graph&t,constintn);voidgraph:
:
bfs(grapht)
主要算法说明
无向网的建立
由于图的结构比较复杂,任意两个顶点之间都可能存在联系,因此无法以数据元素在存储区中的物理位置来表示元素之间的关系,即图没有顺序映像的存储结构,但可以借助数组的数据类型表示元素之间的关系。
另一方面,用多重链表表示图是自然的事,它是一种最简单的这式映像结构,聚聚以一个由一个数据域和多个指针域存储该顶点,其中数据域存储该顶点的信息,指针域存储指向其邻接点的指针.
数组表示法
用两个数组分别存储数据元素的信息和数据元素这间的关系的信息。
以二维数组表示有N个顶点的图时,需存放N个顶点信息和N2个弧信息的存储量。
算法
Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法。
Floyd算法适用于APSP(AllPairsShortestPaths),是一种动态规划算法,稠密图效果最佳,边权可正可负。
此算法简单有效,由于三重循环结构紧凑,对于稠密图,效率要高于执行|V|次Dijkstra算法。
优点:
容易理解,可以算出任意两个节点之间的最短距离,代码编写简单;
缺点:
时间复杂度比较高,不适合计算大量数据。
4.心得体会
当今世界,C语言作为国际上广泛流行的通用程序设计语言,在计算机的研究和应用中已展现出强大的生命力。
C语言兼顾了诸多高级语言的特点,是一种典型的结构化程序设计语言,它处理能力强,使用灵活方便,应用面广,具有良好的可移植性。
而数据结构-作为C语言使用的途径学科,也是计算机学科的一门核心课程.虽然我们学C语言和数据结构已快一年了,但一直都注重理论概念,而实际上机操作却不多.很感谢这次的课程设计,它使我更加深刻地体会到多看专业书、多学习专业知识的重要性,只有掌握了一定量的专业知识才能得心应手地解决诸多问题;另外,在课程设计过程中,我遇到了很多棘手的问题,好几次都差点放弃了,但最终还是坚持下来了,所以我懂得了,做任何事都要有耐心,不要一遇到困难就退缩;当遇到那么多的问题时,我自己能解决的并不多,大部分都是通过和小组同学讨论而解决的。
所以,在学习和工作中要时刻谨记“团结”二字,它好比通向成功的铺路石,不可或缺。
在编程过程中,有编得很顺利的,也有很多不顺利的,正如人生的道路是曲折的,但正是因为曲折人生才光彩夺目,在人生的路上,总遇到重重困难,但正是因为这些困难我们才变的更加坚强,才能够不断地提高自己,充实自己,最后达到我们理想的彼岸。
感谢孙老师在授课期间对我们严厉的态度和严格的管理,才造就了今天的我们。
在课程设计过程中,我们几乎每个小组都遇到了不同程度的问题,但老师都细心指导,耐心地为我们讲解。
老师认真负责的工作态度,对我们这次的课程设计得以顺利完成发挥了不可估量的作用。
最后,再一次感谢在这次课程设计中对我给予帮助的老师和同学。
通过这次课程设计,我们不光收获了知识,还收获了友谊和欢乐。
附录1源程序
#include<>
constintn=5;园入口2.海盗船丨"< cout<<"丨3.方舟湖4.龙王山丨"< cout<<"丨5.公园出口丨"< cout<<"-------------------------"< cout<<"以下是公园的路径图"< cout<<"9"< cout<<"2-------------4"< cout<<"|**丨"< cout<<"|4*5*丨"< cout<<"|**丨"< cout<<"3|*丨2"< cout<<"|*3丨"< cout<<"|**丨"< cout<<"|*10*3丨"< cout<<"1----5"< cout<<"入口出口"< cout<<"下面是景点与景点之间的距离和介绍: "< cout<<"1.公园入口->2.海盗船距离为: 3"< cout<<"1.公园入口->3.方舟湖距离为: 10"< cout<<"2.水族馆->4.龙王山距离为: 9"< cout<<"2.水族馆->3.方舟湖距离为: 4"< cout<<"3.摩天轮->4.龙王山距离为: 5"< cout<<"4.动物园->5.公园出口距离为: 2"< cout<<"3.摩天轮->5.公园出口距离为: 3"< } voidgraph: : creatp(graph&t) { inti,j; for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i==j)[i][j]=0;i][j] if((i! =j)&&(a[i][j] [i][j]=i; else[i][j]=0; } for(intk=1;k<=n;k++) { for(inti=1;i<=n;i++) for(intj=1;j<=n;j++) if[i][k]+[k][j]<[i][j]) { [i][j]=[i][k]+[k][j]; [i][j]=[k][j]; } } } voidgraph: : bfs(grapht)//从顶点i出发实现广度搜索搜索n { intj,i;//f,r分别为队列头,尾指针 charch; cout<<"请输入一个你想去的地方: "; cin>>i; while(i<=5) { if(i==1)cout<<"这里就是你要去的地方拉! ! "< else { for(j=1;j<=n;j++) { if(i! =j) { cout<<"距离为"<<[i][j]<<": "; intnext=[i][j]; cout< while(next! =i) { cout<<"--"< next=[i][next]; } cout<<"--"< } } cout<<"等我推荐一条最佳路径供你返回吧(y/n): "; } cin>>ch; if(ch=='y') { if(i==2)cout<<"2--3--5"< if(i==3)cout<<"3--5"< if(i==4)cout<<"4--5"< cout<<"请问你想去游览公园全景吗(y/n): "< cin>>ch; if(ch=='y') cout<<"请走路线"< cout<<"你还想去别的地方吗? (y/n)"; cin>>ch; if(ch=='y') {cout<<"请输入一个你想去的地方: "; cin>>i;} if(ch! ='y') { cout<<"*****退出程序*****"< cout<<"欢迎下次再来"< break; } } elsebreak; } } intmain() { grapht; (); (t); (t,n); (t); } 附录二: 测试数据 图1—1 图1—2 参考文献 [1]严蔚敏吴伟民著数据结构(C语言版)清华大学出版1999年第一版 [2]谭浩强著C程序设计清华大学出版社1999年第二版 课程设计成绩评定表 姓名 性别 专业班级 课程设计题目: 课程设计答辩或质疑记录: 成绩评定依据: 最终评定成绩(以优、良、中、及格、不及格评定) 指导教师签字: 年月日
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 公园 导游 课程设计