校园导游系统数据结构图.docx
- 文档编号:15798418
- 上传时间:2023-07-07
- 格式:DOCX
- 页数:41
- 大小:409.56KB
校园导游系统数据结构图.docx
《校园导游系统数据结构图.docx》由会员分享,可在线阅读,更多相关《校园导游系统数据结构图.docx(41页珍藏版)》请在冰点文库上搜索。
校园导游系统数据结构图
郵電學院
数据结构实验报告
题目:
校园导游系统
院系名称:
计算机学院
专业名称:
计算机科学与技术
班级:
1006
学生:
****
学号(8位):
*****
指导教师:
******
设计起止时间:
2011年12月12日~2011年12月16日
1.题目要求
1、设计学校的校园平面图,
地点(地点名称、地点介绍)不少于10个。
2、提供图中任意地点相关信息的查询。
3、提供图中任意地点的问路查询:
1)任意两个地点之间的一条最短(中转最少)的简单路径;
2)任意两个景点的最佳访问路线(带权)查询;
3)任意两个地点之间的所有路径。
4、地点和道路的扩充以及撤销;
地点基本信息的文件存储。
(附加:
加分题)
二.概要设计
1.功能模块的调用关系图
2.各个模块详细的功能描述。
1.首先,main()函数调用loge()函数,输出欢迎界面,然后调用showmenu()函数来选择用户所要进行的操作。
其中showmenu()函数就是一个菜单供使用者来选择他所要进行的相关操作,比如信息的查询,最短路径查询之类。
2.browser()函数,用于输出校园平面图,给用户提供校园的景点分布状况,方便用户选择景点参观。
3.Search()函数,用于查询用户所选的景点信息,用户需要输入要查询的景点编号,函数会对编号进行判断,如果是合法输入,则在屏幕上输出该景点的相关信息,包括景点名字,景点的相关介绍,否则返回重新输入。
4.SearchAllpath()函数,用于查询用户所选的任意两个景点间的所有路径,用户需要输入要查询的起始景点编号,函数会对编号进行判断,如果是合法输入,用户需要输入要查询的终点景点编号,函数会对编号进行判断,如果是合法输入,则在屏幕上输出输查询的两个景点间的所有路径,否则返回重新输入。
函数使用深度遍历DeepFirstSeach()查找路径。
5.Wellway()函数,用于查询用户所选的任意两个景点间的最短路径,用户需要输入要查询的起始景点编号,函数会对编号进行判断,如果是合法输入,用户需要输入要查询的终点景点编号,函数会对编号进行判断,如果是合法输入,则在屏幕上输出输查询的两个景点间的最短路径,否则返回重新输入。
函数的生成主体是迪杰斯特拉算法来计算出起点到终点之间的最短路径。
6.minway()函数,用于查询用户所选的任意两个景点间的最佳路径(即中转最少),用户需要输入要查询的起始景点编号,函数会对编号进行判断,如果是合法输入,用户需要输入要查询的终点景点编号,函数会对编号进行判断,如果是合法输入,则在屏幕上输出输查询的两个景点间的最短路径,否则返回重新输入。
7.CreatUDN()函数,创建的图,它是MGraph型,G->vexnum表示顶点的个数;G->arcnum表示边数。
CreatUDN()函数的功能就是实现图的创建,将已知的景点的一些信息,转换成图的信息,并进行存储。
三.详细设计(主要函数的程序流程图)
1.任意两个地点之间的一条最短(中转最少)的简单路径
利用遍历的思想,遍历图找出一条最佳最佳的的路径,让它遍历所有景点。
往下遍历,访问标志位,若访问过在下次就不用访问。
若找完一个分支在下次重新遍历。
zz[0]->zhi=m;
zz[0]->front=NULL;
flag[m]=1;
for(top=0;top<20;top++)
{
for(i=0;i<20;i++)
{
if(G->arcs[zz[top]->zhi][i].adj!
=INFINITY&&i==n)
{
printf("%s\n",G->vexs[n].name);
printf("%s\n",G->vexs[zz[top]->zhi].name);
zz[top]=zz[top]->front;
while(zz[top]!
=NULL)
{
printf("%s\n",G->vexs[zz[top]->zhi].name);
zz[top]=zz[top]->front;
}
getch();
return;
}
elseif(G->arcs[zz[top]->zhi][i].adj!
=INFINITY&&flag[i]==0)
{
zz[++j]->zhi=i;
zz[j]->front=zz[top];
flag[i]=1;
}
}
}
2.任意两个景点的最佳访问路线(带权)查询
利用迪杰特斯拉算法,求v0到其余顶点的最短路径D[],p[][]是用来存放各路径的权值,借助辅助数组final[]标志,是否当前顶点属于final(1,属于)。
for(v=0;v
{
final[v]=0;
D[v]=G->arcs[v0][v].adj;
for(w=0;w
p[v][w]=0;
if(D[v] { p[v][v0]=1;p[v][v]=1; } } D[v0]=0;final[v0]=1; for(i=1;i { min=INFINITY; for(w=0;w if(! final[w]) if(D[w] final[v]=1; for(w=0;w if(! final[w]&&(min+G->arcs[v][w].adj { D[w]=min+G->arcs[v][w].adj; for(x=0;x p[w][x]=p[v][x]; p[w][w]=1; } } v=v1; w1=v0; printf("%s",G->vexs[v0].name); do { flag=0;min=INFINITY; for(w=0;w { if(p[v][w]&&w! =v0) { flag=1; if(D[w] { j=w; min=D[w]; } } } 3.任意两个地点之间的所有路径 利用深度优先的思想,遍历图找出所有的路径,让它遍历所有景点。 利用递归的思想,往下历,访问标志位,若访问过在下次就不用访问。 { ints; if(v[k]==j)/*找到一条路径*/ { count++;/*路径的条数值加1*/ printf("第%d条: ",count); for(s=1;s printf("%s->",G->vexs[v[s]].name); printf("%s\n",G->vexs[v[s]].name); } for(s=1;s { if(s! =i)/*保证找到的是简单路径*/ { if(G->arcs[v[k]][s].adj! =INFINITY&&visited[s]==0) /*当vk与vs之间有边存在且vs未被访问过*/ { visited[s]=1;/*置访问标志位为1,即已访问的*/ v[k+1]=s;/*将顶点s加入到v数组中*/ DeepFirstSeach(G,i,j,k+1);/*递归调用之*/ visited[s]=0;/*重置访问标志位为0,即未访问的,以便该顶点能被重新使用*/ } } } }若找完一个分支在下次重新遍历。 递归调用 否 4.测试数据及运行结果 1.正常测试数据和运行结果 2.异常测试数据及运行结果 五.调试情况,设计技巧及体会 1.改进方案 本次实习设计总体上来说是成功的,我在规定的时间完成了老师交代的任务,并让程序能够运行起来,可以说大体上没有问题,当然在细节上还有需要改进的地方; 合理之处: ①对于老师所提出的问题要求很好并及时的解决了; ②程序运行整体上没有大的错误; ③对于各大模块划分清晰,知道先做什么后做什么; ④程序运行后界面漂亮,用户使用方便; ⑤合理恰当的把书上所学的关于图的知识应用到程序设计之中,使程序明了可读性较高。 不合理之处: ①程序之中存在一些小毛病,不能100%的运行无误; ②关于文件存储这一模块掌握的不是很好,所创建的图不能很好的保存到文件之中; ③程序设计中最短路径(中转最少)显示的时候是倒着显示 改进方案: 对于程序存在的小问题一个个的仔细排除,精尽量做到准确无误;对于文件和最短路径的设计应多参考相关书籍,找到合理正确的解决方法,将图存储到指定的文件中去,并且使最短路径在输出的时候能够以正确的顺序输出。 2.体会 这次课程设计给我的感触很多,课程设计没开始之前我总是在想今年的课程设计会不会象去年那样辛苦,但是这一周下来我当然也感到累,也有心情烦躁的时候,体会到调试成功时的那种喜悦。 课程设计之前老师让我们自己先想好设计思路,都要做哪些模块。 那天下午编了一下午,没什么成就弄得我很心烦,再想到快要考试,那种急于求成的心更迫切,自己很难平静。 第二天老师检查时我什麽都没有,看到同学的程序我开始着急了,但那会我只有一个念头我得从新开始,由于对图不是很了解,我就从读写模块开始,就使用简单的C语知识,那天早上将那两个模块给拿下了。 下机后我在寝室开始编程,开始进入真正的图部分,边思考怎样可以将它们联系起来,边进行调试。 对编程兴趣很浓,直到晚上十点我已经将老师的要求完成差不多。 这些日子是很辛苦,但我学到了很多东西,理解了图的运用,还和同学一起分享调试成功的那种喜悦,我完成的早,同学有问题会让我帮助,在帮他们的过程中我也学会了很多种不同的思想,让我对图有了更深刻的理解。 当然,我要感学校领导精心给我们安排的这次实习操作,更感我们的程序设计老师,是她给了我们一个相对轻松有趣的环境,让我们感到在设计中没有压力,在她的帮助下,我终于完成了本次课程设计的任务。 。 代码 #include #include #include #include #include #defineINFINITY10000/*无穷大*/ #defineMAX_VERTEX_NUM40 #defineMAX40 typedefstructArCell { intadj;//路径长度 }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedefstruct//图中顶点表示主要景点,存放景点的编号、名称、简介等信息,s { charname[30]; intnum; intx; inty; charintroduction[500];//简介 }infotype; structzui//最短路径记录结构体 { intzhi; structzui*front; }; typedefstruct { infotypevexs[MAX_VERTEX_NUM]; AdjMatrixarcs; intvexnum,arcnum; }MGraph; MGraphb; voidshowmenu(); voidloge();//启动动画 voidWellway(MGraph*);//计算任意两个景点之间的最短路径 MGraphInitGraph(void);//初始化 voidbrowser();//浏览校园全景 voidSearch(MGraph*G);//查看景点信息 MGraph*CreatUDN(MGraph*G);//创建图 voidSearchAllpath(MGraph*G);//查找两点间所有路径 voidminway(MGraph*G); MGraph*CreatUDN(MGraph*G); intopenfile(MGraph*G); intwritefile(MGraph*G); intwritefile(MGraph*G) { FILE*fp; inti; fp=fopen("xiaoyuanxinxi.txt","w"); if(fp==NULL) { printf("打开失败! "); returnFALSE; } for(i=0;i<20;i++) fwrite(&G,sizeof(MGraph),1,fp); returnTRUE; fclose(fp); } intopenfile(MGraph*G) { FILE*fp; inti=0; intt=0; fp=fopen("xiaoyuanxinxi.txt","r"); if(fp==NULL) { printf("文件为空,无景点信息,请按任意键返回添加! "); returnFALSE; } while(! feof(fp)) { fread(&G,sizeof(MGraph),i,fp); i++; } for(t=0;t { printf("%d%s%s",G->vexs[t].num,G->vexs[t].name,G->vexs[t].introduction); printf("\n"); } fclose(fp); returni; } voidmain(void) { intk; system("modecon: cols=140lines=130"); loge(); b=InitGraph(); system("cls"); printf("欢迎进入邮电大学校园导游咨询系统\n"); Sleep(1000); do { while (1) { showmenu(); printf("请选择: "); scanf("%d",&k); if(k<0||k>6) { printf("输入有误请重新输入\n"); scanf("%d",&k); } elsebreak; } switch(k) { case1: browser();system("cls");break; case2: Search(&b);system("cls");break; case3: SearchAllpath(&b);system("cls");break; case4: Wellway(&b);system("cls");break; case5: minway(&b);system("cls");break; case6: CreatUDN(&b);system("cls");break; case0: exit(0); } }while (1); } voidshowmenu() { printf("************************************\n"); printf("$主要景点列表$\n"); printf("$建议观看$\n"); printf("************************************\n"); printf("<12>田操场<09>西邮小湖\n"); printf("<2>教学楼A<14>体育馆\n"); printf("<3>教学楼B<10>图书馆\n"); printf("<5>1号实验楼<6>2号实验楼\n"); printf("<7>3号实验楼<11>校医院\n"); printf("<8>大学生活动中心<4>喷泉\n"); printf("<13>美食广场<15>苑\n"); printf("1.查看学校景点分布图\n"); printf("2.查询景点简介查询\n"); printf("3.查询某两个景点间所有的路径\n"); printf("4.任意两景点之间的最佳路径\n"); printf("5.任意两景点之间的最短路径\n"); printf("6.建图并保存到文件\n"); printf("0.退出\n"); } voidloge() { printf("\t\t\t\t\t\t\t"); printf("欢");Sleep(100); printf("迎");Sleep(100); printf("进");Sleep(100); printf("入");Sleep(100); printf("西");Sleep(100); printf("安");Sleep(100); printf("邮");Sleep(100); printf("电");Sleep(100); printf("大");Sleep(100); printf("学");Sleep(100); printf("校");Sleep(100); printf("园");Sleep(100); printf("导");Sleep(100); printf("游");Sleep(100); printf("系");Sleep(100); printf("统");Sleep(100); printf("\n"); } MGraphInitGraph() { MGraphG; inti,j; G.vexnum=20; G.arcnum=18; for(i=0;i G.vexs[i].num=i; strcpy(G.vexs[0].name,"大门"); strcpy(G.vexs[1].name,"行政楼"); strcpy(G.vexs[2].name,"教学楼A"); strcpy(G.vexs[3].name,"教学楼B"); strcpy(G.vexs[4].name,"喷泉"); strcpy(G.vexs[5].name,"一号实验楼"); strcpy(G.vexs[6].name,"二号实验楼"); strcpy(G.vexs[7].name,"三号实验楼"); strcpy(G.vexs[8].name,"大学生活动中心"); strcpy(G.vexs[9].name,"西邮小湖"); strcpy(G.vexs[10].name,"图书馆"); strcpy(G.vexs[11].name,"校医室"); strcpy(G.vexs[12].name,"田径场"); strcpy(G.vexs[13].name,"美食广场"); strcpy(G.vexs[14].name,"体育馆"); strcpy(G.vexs[15].name,"苑"); strcpy(G.vexs[16].name,"男生宿舍"); strcpy(G.vexs[17].name,"女生宿舍"); strcpy(G.vexs[18].name,"超市"); strcpy(G.vexs[19].name,"篮球场"); strcpy(G.vexs[0].introduction,"学校大门,出门坐车的地方门口有600,有616(到火车站)有321等,平常学生外出坐车的地方。 "); strcpy(G.vexs[1].introduction,"我只想说句脏话,因为我不熟,很少去,应该是行政的吧....遇此问题你可以关闭本系统了,答案...我也不清楚。 "); strcpy(G.vexs[2].introduction,"教学楼A,此教学楼上课率是80%以上,基本上绝大多数可都在这上。 "); strcpy(G.vexs[3].introduction,"教学楼B,除了教学楼A就是本楼了,也是上课的地方,只是一般上大课的时候来。 "); strcpy(G.vexs[4].introduction,"学校的小喷泉,只有节日或一些领导来的时候喷一下,对与学生使用价值不大,能不能看到看人品! 。 "); strcpy(G.vexs[5].introduction,"一号实验楼,我想想...好像是电子工程学院的,很多实验都在里面做。 "); strcpy(G.vexs[6].introduction,"二号实验楼,恩,是本院,计算机学院的,虽然去的少,(除了班长每天去导员那报道常去外,就是被导员叫去挨骂,其他一般没事不去)"); strcpy(G.vexs[7].introduction,"三号实验楼,哎,我真不清楚了,反正能做实验,不知道,用户关系统吧..."); strcpy(G.vexs[8].introduction,"各种演出,各种浪,各种蛋疼,都在这"); strcpy(G.vexs[9].introduction,"俗称**湖(和谐词),男女约会的地方,主席的大明湖畔。 "); strcpy(G.vexs[10].introduction,"恩,图书还行吧,找资料,上网(1元/小时),各种实习"); strcpy(G.vexs[11].introduction,"学校的医院,大家都懂得,医生技术差动不动就是挂点滴,还很贵。 设施...,不能多说...."); strcpy(G.vexs[12].introduction,"上体育课,举行运动会,还有个足球场。 "); strcpy(G.vexs[13].introduction,"一个吃饭的地方,味道还行,价格不是很贵,挺多人去的。 "); strcpy(G.vexs[14].introduction,"一般有个篮球赛什么的会在这举行,能坐挺多人的。 "); strcpy(G.vexs[15].introduction,"另一个吃饭的地方,相对美广,本人觉得稍微干净一点,价格可能略贵,但还能接受,我是比较喜欢来在。 ");
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 校园 导游 系统 数据 结构图