算法与数据结构综合实习校园导航系统.docx
- 文档编号:17038963
- 上传时间:2023-07-21
- 格式:DOCX
- 页数:30
- 大小:55.06KB
算法与数据结构综合实习校园导航系统.docx
《算法与数据结构综合实习校园导航系统.docx》由会员分享,可在线阅读,更多相关《算法与数据结构综合实习校园导航系统.docx(30页珍藏版)》请在冰点文库上搜索。
算法与数据结构综合实习校园导航系统
算法与数据结构综合实习
——校园导航系统
姓名
学号
班级
联系电话
指导教师
实习日期2010年9月13日
一、需求分析
本文论述的校园导航系统是为校园参观者或导游者提供的一种便捷的交通查询系统,该系统主要解决了校园参观者或导游者在进行采访或参观时所遇到的校园路径方向问题,为此,设计该系统能够给带来他们一种比较方便快捷的导航帮助。
本文论述了校园导航查询系统开发的目标和实现的功能,并重点介绍了需求分析、概要设计、详细设计、调试分析和测试结果的全过程。
在描述系统分析和系统设计过程中,为了使该系统的开发过程具有规范化,为此,本文确定了开发系统的指导思想:
一、运用了规范化的设计思想。
二、从实际应用出发,为求实用。
三、运用数据结构里所涉及到的算法思想进行设计开发,开发一个适宜查询学校的相关信以及校园场所和景点之间的最短路径的方向导航系统。
四、校园导航查询系统的开发方法总结如下:
(1)调查,了解学校各个场所与场所或者是各个景点与景点之间的信息,路径和距离,从外来人员或者参观者和走访者的角度出发,该如何设计才能满足用户需求。
(2)分析,对调查得到的数据进行分析,根据其要求实现的功能分析系统结构和界面将实现的基本功能。
(3)设计与开发,设计系统界面并编辑实现其各个功能的代码。
(4)调试,在设计完成后,调试系统运行的状况,修改完善系统,然后进行测试。
二、概要设计
(1)抽象数据类型
ADTGraph{
数据对象V:
V具有相同特性的数组元素的集合,称为顶点集。
数据关系R:
R={VR}
VR={
基本操作P:
CreateGraph(&G,V,VR);
初始条件:
V是图的顶点集,VR是图中弧的集合。
操作结果:
按V和VR的定义构造图G。
DistroyGraph(&G)
初始条件:
图G存在
操作结果:
销毁图G
LocateVex(G,u);
初始条件:
图G存在,u和G中顶点有相同的特征。
操作结果:
若存在顶点u,则返回该顶点在图中的位置;否则返回其他信息。
GetVex(G,u);
初始条件:
图G存在,u是图中的顶点。
操作结果:
返回u的值。
InsertVex(&G,v);
初始条件:
图G存在,v和图中的顶点有相同的特性。
操作结果:
在图G中新增顶点v.
InsertArc(&G,v,w);
初始条件:
图G存在,v和w是图中的顶点。
操作结果:
在图G中增添弧
}ADTGraph
(2)程序中包含的函数
Main()
Cmd()
MGraphInitGraph()
Menu()
Browser()
Floyd()
Search()
LocateVex()
Print()
(3)各函数之间关系如下:
Print函数
Cmd函数
MGraphInitGraph函数
三、详细设计
(1)目录函数
voidcmd(void)
{
inti;
b=InitGraph();
Menu();
scanf("%d",&i);
while(i!
=5)
{
switch(i)
{
case1:
system("cls");Browser(&b);Menu();break;
case2:
system("cls");Floyd(&b);Menu();break;
case3:
system("cls");Search(&b);Menu();break;
case4:
exit
(1);break;
default:
break;
}
scanf("%d",&i);
}
}
(2)邻接矩阵的建立
MGraphInitGraph(void)
{
MGraphG;
inti,j;
G.vexnum=10;
G.arcnum=14;
for(i=0;i G.vexs[i].num=i; strcpy(G.vexs[0].name,"综合食堂"); strcpy(G.vexs[0].introduction,"新建的食堂,里面聚集了全国各色美味"); strcpy(G.vexs[1].name,"春晖楼"); strcpy(G.vexs[1].introduction,"教师办公场所,楼高12层,各种设施齐全"); strcpy(G.vexs[2].name,"5号学生宿舍楼"); strcpy(G.vexs[2].introduction,"男生宿舍楼"); strcpy(G.vexs[3].name,"校医院"); strcpy(G.vexs[3].introduction,"校医院,设施不是很齐全,只能看小病,收费较贵"); strcpy(G.vexs[4].name,"图书馆"); strcpy(G.vexs[4].introduction,"藏书60万册,设施良好,2楼为电子阅览室,环境幽雅"); strcpy(G.vexs[5].name,"足球场"); strcpy(G.vexs[5].introduction,"现代化塑胶跑道,人造草坪,适宜锻炼身体的场所"); strcpy(G.vexs[6].name,"沁园"); strcpy(G.vexs[6].introduction,"绿树成荫,适宜休息和读书"); strcpy(G.vexs[7].name,"主教学楼"); strcpy(G.vexs[7].introduction,"学院最大的教学楼,共5层,环形建筑,适宜学习"); strcpy(G.vexs[8].name,"西教学楼"); strcpy(G.vexs[8].introduction,"学院第二大教学楼,环境较差"); strcpy(G.vexs[9].name,"多媒体楼"); strcpy(G.vexs[9].introduction,"多媒体教学场所,设施先进,环境良好"); for(i=0;i for(j=0;j G.arcs[i][j].adj=INFINITY; G.arcs[0][1].adj=100; G.arcs[0][2].adj=200; G.arcs[0][6].adj=400; G.arcs[1][7].adj=300; G.arcs[2][3].adj=120; G.arcs[3][6].adj=220; G.arcs[3][4].adj=100; G.arcs[4][5].adj=300; G.arcs[4][9].adj=250; G.arcs[5][9].adj=350; G.arcs[6][7].adj=60; G.arcs[6][9].adj=200; G.arcs[7][8].adj=50; G.arcs[8][9].adj=20; for(i=0;i for(j=0;j G.arcs[j][i].adj=G.arcs[i][j].adj; returnG; }//InitGraphend (3)输出菜单函数 voidMenu() { printf("\n石家庄铁道学院导游图\n"); printf("┏━━━━━━━━━━━━━━━━━━━━┓\n"); printf("┃1.查看校园全景┃\n"); printf("┃2.查看游览路线┃\n"); printf("┃3.查看景点信息┃\n"); printf("┃4.退出系统┃\n"); printf("┗━━━━━━━━━━━━━━━━━━━━┛\n"); printf("Option-: "); } (4)输出图的函数 voidBrowser(MGraph*G) { printf("*******************************************************************************************************************\n"); printf("*┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓*\n"); printf("*┃┃*\n"); printf("*┃教师住宅区┃*\n"); printf("*┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛*\n"); printf("**\n"); printf("*━┏━━┓┏━━━━━┓┏━━━━━━━━━━━┓┏━━━┓*\n"); printf("*━━体育┃实┃┃┃┃绿化一公寓┃┏━━┓┏━━┓┃幼儿园┃*\n"); printf("*━━部┃验┃┃第九┃┃环卫洗浴┃11公寓10公寓┗━━━┛*\n"); printf("*━标━┏━┛楼┃┃实验楼┃12┃中心中心***┃┗━━┛┗━━┛清真*\n"); printf("*━准━┃┃┃┃┃*篮*┃┏━━━━┓************\n"); printf("*━田━┃机械工程┃青┗━━━━━┛┃消费*球*┃┃9栋公寓┃13*一食堂**\n"); printf("*━径━┃实验中心┃┏━━━━━┓┃樱花林合作社*场*┃┗━━━━┛******\n"); printf("*━场━┗━━━━┛┃第三实验楼┃┃***┃*草坪*排球场*二三食堂**\n"); printf("*━━*━━━┓9┗━━━━━┛┗━━━━━━━━━━━┛************************\n"); printf("*━━*┃811┏━━┓┏━━┓┏━━━┓*\n"); printf("*━━*游泳馆┃┏━━━━━┓┏━━━━┓┃8公寓7公寓┃┃6公寓┃*\n"); printf("***********━*┃┃第二┃┏━━━━━┓┃正在建设┃┗━━┛┗━━┛┗━━━┛*\n"); printf("*200米*┏━━*┃藏┃实验楼┃┃研究生院┃┃的基础教┃┏━━┓┏━━┓┏━━━┓*\n"); printf("*轮滑场*┃训练房┃┃图书馆┃┃第五教学楼┃┃学大楼┃┃5公寓4公寓┃┃研公寓┃*\n"); printf("***********┗━━━┓体育馆┃┗━━━━━┛┗━━━━━┛┗━━━━┛┗━━┛┗━━┛┗━━━┛*\n"); printf("*━━┓━━━━┓┗━━━━┛4752*********┓*\n"); printf("*篮球场┃实训车间┃┏━━━━━┓*********************┏━┓┏━━┓****************青┃*\n"); printf("*┃┃┃第┃*世***┃┃┃┃*泽篮**综合春┃*\n"); printf("*排球场┃┃┃三碑┃*纪沁园*10*翠园*┃试┃┃┃*园国旗球**苑┃*\n"); printf("*网┃┃┃教┃路*钟***┃验┃┃礼堂┃*场**********┛*\n"); printf("*球┃┃┃学┃**************┃楼┃┃┃***************┏━━━┓*\n"); printf("*场┃工程训练┃┃楼┃┏━━━━━┓*********┗━┛┗━━┛┏━━━━━┓┃13公寓┃*\n"); printf("*━━━┛中心┃┃┃┃┃┏━━━━━┓┏━━━━┓1┃东西办公楼┃┗━━━┛*\n"); printf("*培训楼┃┃第二教学楼┃┃第一教学楼┃┃第四教学楼┃┃公寓医院┃┗━━━━━┛┏━━━┓*\n"); printf("*━━━━━━━━━┛┗━━━━━┛┗━━━━━┛┗━━━━━┛┗━━━━┛┏━━━━━┓┃12公寓┃*\n"); printf("*┏━━━━┏━━━━━360┃开元楼┃┗━━━┛*\n"); printf("*┏━━━┓┃┏━━━┃┏━━━━┏━━━━┓┏━━━━━━━┓┗━━━━━┛┏━━━━━┓*\n"); printf("*┃印刷厂┃┃┃工程机械┃┃运输服务**┃教材中心┃┃艺术交流中心┃┃保卫处┃*\n"); printf("*┗━━━┛┃┃修理厂┃┃中心*大门*┗━━━━┛┗**************┛┗━━━━━┛*\n"); printf("*******************************************************************************************************************\n"); }//menuend (5)求最短路径 voidFloyd(MGraph*G) { intv,u,i,w,k,j,flag=1,p[10][10][10],D[10][10]; for(v=0;v for(w=0;w { D[v][w]=G->arcs[v][w].adj; for(u=0;u p[v][w][u]=0; if(D[v][w] { p[v][w][v]=1;p[v][w][w]=1; } } for(u=0;u for(v=0;v for(w=0;w if(D[v][u]+D[u][w] { D[v][w]=D[v][u]+D[u][w]; for(i=0;i p[v][w][i]=p[v][u][i]||p[u][w][i]; } while(flag) { printf("请输入出发点和目的地的编号: "); scanf("%d%d",&k,&j); if(k<0||k>G->vexnum||j<0||j>G->vexnum) { printf("景点编号不存在! 请重新输入出发点和目的地的编号: "); scanf("%d%d",&k,&j); } if(k>=0&&k flag=0; } printf("%s",G->vexs[k].name); for(u=0;u if(p[k][j][u]&&k! =u&&j! =u) printf("-->%s",G->vexs[u].name); printf("-->%s",G->vexs[j].name); printf("总路线长%dm\n",D[k][j]); }//Floydend (6)查询景点的函数 voidSearch(MGraph*G) { intk,flag=1; while(flag) { printf("请输入要查询的景点编号: "); scanf("%d",&k); if(k<0||k>G->vexnum) { printf("景点编号不存在! 请重新输入景点编号: "); scanf("%d",&k); } if(k>=0&&k flag=0; } printf("%-16s┃%-56s┃\n",G->vexs[k].num,G->vexs[k].name,G->vexs[k].introduction); }//Searchend (7)初始化图形 intLocateVex(MGraph*G,char*v) { intc=-1,i; for(i=0;i if(strcmp(v,G->vexs[i].name)==0) {c=i;break;} returnc; } MGraph*CreatUDN(MGraph*G)//初始化图形,接受用户输入 { inti,j,k,w; charv1[20],v2[20]; printf("请输入图的顶点数,弧数: "); scanf("%d%d",&G->vexnum,&G->arcnum); printf("请输入景点的编号: 、名称、简介: \n"); for(i=0;i { printf("景点编号: "); scanf("%d",&G->vexs->num); printf("景点名称: "); scanf("%s",G->vexs[i].name); printf("景点简介: "); scanf("%s",G->vexs->introduction); } for(i=0;i for(j=0;j G->arcs[i][j].adj=INFINITY; printf("请输入路径长度: \n"); for(k=0;k { printf("第%d条边: \n",k+1); printf("景点对(x,y): "); scanf("%s",v1); scanf("%s",v2); printf("路径长度: "); scanf("%d",&w); i=LocateVex(G,v1); j=LocateVex(G,v2); if(i>=0&&j>=0) { G->arcs[i][j].adj=w; G->arcs[j][i]=G->arcs[i][j]; } } returnG; } (8)打印输出函数 voidprint(MGraph*G) { intv,w,t=0; for(v=0;v for(w=0;w {if(G->arcs[v][w].adj==INFINITY) printf("∞"); elseprintf("%-7d",G->arcs[v][w].adj); t++; if(t%G->vexnum==0) printf("\n"); } } 四、调试分析 (1)刚开始运行时语法逻辑出错,在执行的时候,有的时候出现死循环,有的时候屏幕出现null和乱码,原因主要是数据的初始值设定不一致,还有在屏幕输出这块printf时有一处的i没有写导致在屏幕输出一些乱码,其原因是由于i是各个景点的和场所的编号,如果不写就会被默认为系统里的地址编号输出一大串的长乱码,于是出现了这个问题。 (2)还有就是出现了变量定义错误的问题。 其间编写程序时参考了数据结构书,并按照上面给的函数类型定义的,后来发现运行起来一直有错误,后来问了其他同学才知道书上给的是伪码,用途只是让我们更好的了解算法的构成和实现,对于函数及变量类型的定义并不是正确的,于是在了解了事实之后,立刻将变量定义类型改正过来,再次编译时程序在此处就不再报错。 (3)算法的编写不全面,漏掉个别语句,如在调试的时候检查发现写迪杰斯特拉(DijkStra)算法的时候并没有写完整,造成输出结果不正确;开始查找错误的时候并不知道错在哪里,但经过与书本上的算法进行核对并与同学讨论后,才找出问题根源所在。 (4)以上是在程序编写过程中遇到的主要问题,当然还存在很多小问题,但那都是调试的时候常碰到的,比如在某个语句前或者后漏写“;”;还有是函数没有预先声明;前面函数名的书写和后面不一致;多加定义了某些变量等等。 这些小问题都是比较熟悉的问题,开始进行调试的时候都会出现,好多都是由于粗心大意造成的,对于这些小问题只要多加留意就可以避免再犯。 五、用户使用说明 使用步骤: (1)选择菜单上的任意选项,输入编号; (2)若选择1,弹出事先绘好的学校内大致位置框图; (3)若选择2,输入查询的起始点和终点; (4)若选择3,输入查询景点的编码,从1到12; (5)若选择4,退出程序。 五、测试结果 输入: (1)Option—: 1 (2) [1]Option—: 2 请输入出发点和目的地点的编号: 47 [2]Option—: 2 请输入出发点和目的地点的编号: 142 [3]Option—: 4 输入错误,请重新输入: (数字1-4)2 (3) Option—: 3 [1]Option—: 3 请输入您要查询的景点编号: 5 [2]Option—: 3 请输入您要查询的景点编号: 15 景点编号不存在,请重新输入景点编号(数字1-13): 请输入终点: 9 (4)Option—: 4 输出: (1) 展示一幅校园内大致位置框图。 (2) [1]图书馆西教学楼多媒体楼主教学楼 [2]输入的景点编号不存! 在请重新输入出发点和目的地点编号: (3) [1]|5|足球场|现代化塑胶跑道,人造草坪,适宜锻炼身体的场所 [2]|9|多媒体楼|多媒体教学场所,设施先进,环境良好 (4)Pressanykeytocontinue 七、总结 通过这次数据结构的实习,我学到了很多,感觉自己能力也提高了不少。 而且坚信只要自己下定决心,不放弃探索和研究,也一定能做出来。 这次实习不仅使我回顾了C语言和数据结构知识,巩固和加强了对语言及算法的了解,同时对以前学过的知识进行了查漏补缺,为以后的进一步学习打下了坚实的基础。 程序附录: #defineINFINITY10000/*无穷大*/ #defineMAX_VERTEX_NUM40 #defineMAX40 #include #include #include #include typedefstructArCell { intadj;//路径长度 }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedefstruct//图中顶点表示主要景点,存放景点的编号、名称、简介等信息, { charnam
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 数据结构 综合 实习 校园 导航系统
![提示](https://static.bingdoc.com/images/bang_tan.gif)