校园导游系统

西安郵電學院数据结构课程设计报告题目：校园导游系统系部名称：计算机系专业名称：软件工程班级：0604班学号：04065139学生姓名：高孟迪指导教师：王春梅时间：2008年6月1日实验目的对自己学过的知识进一步的加深理解，对数据结构的算法思想要有更深的理解。通过课程设计，学会通过系统分析、系统设计、编程调试，写实验报告等环节，进一步掌握应用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的应用。学会综合运用数据结构课程中学到的几种典型数据结构，如链表，栈，队列，以及程序设计语言〔C语言〕，自行实现一个较为完整的应用系统的设计与开发。课程设计内容根本要求：校园平面图〔景点、路径等信息〕存储选取校园或某景区中多个具有代表性景点，抽象成无向带权图。可采用邻接表或邻接多重表存储。查询图中任意景点的相关信息查询道路信息〔道路类别、沿途景色等〕查询任意两个景点之间的一条最短的简单路径利用迪杰斯特拉或弗洛伊德算法确定最短路径从某个景点出发给出访问所有景点的最正确行走方案利用深度优先和广度优先搜索遍历图查询任意两景点之间的所有路径〔选做〕需求分析现在大多数的学校由于不断的扩张，这也就使得学校不得不建立的更大。这也就为人们拜访学校造成了很大的不便。人们往往不熟悉学校，找个东西，或某处带来了极大的不便。往往要花很多时间在这一方面。然而要是有一个学校导游系统这将给乘客带来极大的方便，使人们一下就能了解到这个学校的大致的情况。功能：这个系统给用户提供查询景点，浏览路径，寻找最正确的方案到达目的地，还提供了最正确路径。实现的目标：实现对某一个学校的校园导游系统。概要设计系统结构图系统分析：用的图的算法进行构造，用邻接表建立图，然后再用深度优先遍历进行搜索，查找所需的路径。再用迪杰特斯拉算法求出两个景点之间的最正确路径。结构图：功能模块说明2.1创立图(InitGraph):建立无向图，把学校的景点及景点的信息，连接起来建立邻接表采用链式加顺式存储。浏览学校的全景〔Browser〕：列出学校的所有的景点。寻找最正确路径〔DFSTraverse：〕：输入一个景点，会吧所有都浏览一边，并找出最正确的路径。最短路径〔ShortPath〕:求出起点和终点的最正确路径，并求出最正确路径的长度。遍历出某一起点到终点的所有路径〔SearchAllPath〕：找出所有路径，利用深度优先遍历。详细设计5.1创立图：5.2浏览学校全景用数组存放这个学校的全部景点，在通过遍历数组打印出学校的所有景点及其信息。寻找最正确路径〔DFSTraverse〕:利用深度优先的思想，遍历图找出一条最正确最正确的的路径，让它遍历所有景点。利用递归的思想，往下遍历，访问标志位，假设访问过在下次就不用访问。假设找完一个分支在下次重新遍历。5.4最短路径〔ShortPath〕:利用迪杰特斯拉算法，求v0到其余顶点的最短路径path[],distance[]是用来存放各路径的权值，借助辅助数组s[]标志,是否当前顶点属于S(1,属于)。5.5遍历出某一起点到终点的所有路径〔SearchAllPath〕:利用图的深度优先遍历，利用访问标志位。path[]记录路径，visited[]设访问标志，v起点，des终点，length，代表的是访问景点的长度。假设碰见死路或者不同的路，那么从上一个景点，从新扫描。运行结果：主界面：学校全景：某一起点的最正确路径:一个起点的所有路径：学校的图:六、调试情况，设计技巧及体会这次课程设计给我的感触很多，课程设计没开始之前我总是在想今年的课程设计会不会象去年那样辛苦，但是这两周下来我当然也感到累，也有心情烦躁的时候，体会到调试成功使的那种喜悦。课程设计之前老师让我们自己先将设计思路写好，都做了哪些模块，第一天要检查。我当时是在电脑上写了，那天下午编了一下午，没什么成就弄得我很心烦，再想到快要考试，那种急于求成的心更迫切，自己很难平静。第二天老师检查时我什麽都没有看到同学的程序我开始着急了，但那会我只有一个念头我得从新开始，由于对图不是很了解，我就从读写模块开始，就使用简单的C语知识，那天早上将那两个模块给拿下了。下机后我在寝室开始编程，开始进入真正的图局部，边思考怎样可以将它们联系起来，边进行调试。对编程兴趣很浓，直到晚上十点我已经将老师的要求完成差不多。这些日子是很辛苦，但我学到了很多东西，和同学一起分享调试成功的那种喜悦，我完成的早，同学有问题会让我帮助，在帮他们的过程中我也学会了很多种不同的思想，让我对图有了更深刻的理解。当然，我要感谢我们的程序设计老师，是她给了我们一个相对轻松有趣的环境，让我们感到在设计中没有压力,在她的帮助下,我终于完成了本次课程设计的任务七、参考文献《C语言程序设计》王曙燕等科学出版社《数据结构——使用C语言》陈一华等电子科技大学出版社《数据结构——C语言描述》耿国华高等教育出版社《数据结构〔C语言版》严蔚敏，吴伟民清华大学出版社八．程序源代码#include"stdio.h"#include"stdlib.h"#include"string.h"#include"iostream.h"#defineMAX40#defineMAXEDGE500typedefstructArcNode{ intdata;//该弧所得指向的顶点的位置 ArcNode*nextarc;//指向下一条弧的指针}ArcNode,*ArcLink;typedefstructVNode//顶点信息{ charname[30]; intnum;charintroduction[100]; ArcLinkfirstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX+1];typedefstructALGraph{ AdjListvdata; intvexnum,arcnum;//图的顶点数和弧数}ALGraph;intEdge[MAX][MAX];//用来存放路径的权值intn,e;voidCreateGraph(AdjList&g)//创立图{//从文件读入图的信息，包括景点信息，和路的信息FILE*fp; intnum; charname[20]; charinformation[100]; inti=1; inta,b,weight;ArcLinkp,q;//定义一条边的两个端点的临时指针 fp=fopen("tuxinxi.txt","r");//翻开图信息文件 if(fp==NULL) { printf("图信息文件不能翻开."); exit(0); } for(i=1;i<=n;i++)//对路的权值进行初始化 { for(intj=1;j<=n;j++) { if(i==j)Edge[i][j]=0;//主对角线上的(自己对自己付为零); else Edge[i][j]=MAXEDGE; } } for(i=1;i<=n;i++)//初始化邻接表， { g[i].firstarc=NULL; }for(i=1;i<=n;i++)//从文件读入顶点的信息{fscanf(fp,"%d",&num); g[i].num=num; fscanf(fp,"%s",name); strcpy(g[i].name,name); fscanf(fp,"%s",information); strcpy(g[i].introduction,information); }for(intj=1;j<=e;j++)//从文件中读入边的信息{ fscanf(fp,"%d",&a); fscanf(fp,"%d",&b); fscanf(fp,"%d",&weight); Edge[a][b]=weight; Edge[b][a]=weight; p=(ArcLink)malloc(sizeof(ArcNode));//为顶点申请空间 p->data=a; p->nextarc=g[b].firstarc; g[b].firstarc=p;//把p插进来 q=(ArcLink)malloc(sizeof(ArcNode)); q->data=b; q->nextarc=g[a].firstarc; g[a].firstarc=q;} fclose(fp);}voidBrowser(AdjListG)//浏览整个景点{ intv; printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n"); printf("┃编号┃景点名称┃简介┃\n"); for(v=1;v<=n;v++) printf("┃%-4d┃%-16s┃%-56s┃\n",G[v].num,G[v].name,G[v].introduction);printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");}intGetWeight(intv1,intv2)//得到两个景点之间的路的权值{ if(v1<0||v1>n||v2<0||v2>n) { printf("该地点不存在！！"); return0; } returnEdge[v1][v2];}voidDIJ(AdjListG,intv0,intdistance[],intpath[])//迪杰特斯拉算法{//求v0到其余顶点的最短路径path[],distance[]是用来存放各路径的权值//借助辅助数组s[]标志,是否当前顶点属于S(1,属于) int*s=newint[n]; intminDis=0,i=0,j=0,u=0; for(i=1;i<=n;i++)//初始化distance[],s[],path[] { distance[i]=GetWeight(v0,i); s[i]=0; if(i!=v0&&distance[i]<MAXEDGE)path[i]=v0; elsepath[i]=-1;//v0到v0为-1 } s[v0]=1;//v0入s集 distance[v0]=0;//v0到v0的距离为零 for(i=1;i<n;i++)// {//开始主循环，每次求得v0到某个顶点v的最短距离，并将v并入s中 minDis=MAXEDGE;//当前所知v0顶点的最近距离，并设初值为MAXEGDE intu=v0;//把v0给u for(j=1;j<=n;j++) { if(!s[j]&&distance[j]<minDis)//查找属于s[]并且求最小的路径 { u=j;//在s[]一直往下找 minDis=distance[j];//赋给最小路径 } } s[u]=1;//离v0最近的景点，入s[] for(j=1;j<=n;j++)//更新当前最短路径及距离 { if(!s[j]&&GetWeight(u,j)<MAXEDGE) { intnewdist=distance[u]+GetWeight(u,j); if(newdist<distance[j]) { distance[j]=newdist; path[j]=u;//记录下寻找最短的路 } } } }}voidShortPath(AdjListg)//求两点的最短路径{intqidian,zhongdian; intdistance[MAX]; intpath[MAX]; intminPath=0; intway[MAX]; intq=0;intpre=0; printf("\n"); printf("请输入要查询的景点的起点，终点:"); scanf("%d,%d",&qidian,&zhongdian); DIJ(g,qidian,distance,path); intw=zhongdian;while(w!=qidian)//遍历path[]并把到终点的路存放在way[]中{q++;way[q]=path[w];w=path[w];}printf("路径为:");//输出路径for(intj=q;j>=1;j--){printf("%s-->",g[way[j]].name);}printf("%s",g[zhongdian].name);printf("\n");printf("最短路径为%d",distance[zhongdian]);printf("\n");}voidSerach(AdjListG)//查询景点信息{intk,flag=1; while(flag) { printf("请输入要查询的景点编号:"); scanf("%d",&k); if(k<0||k>n) { printf("景点编号不存在!请重新输入景点编号:"); scanf("%d",&k); } if(k>=0&&k<=n) flag=0; } printf("┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n"); printf("┃编号┃景点名称┃简介┃\n"); printf("┃%-4d┃%-16s┃%-56s┃\n",G[k].num,G[k].name,G[k].introduction); printf("┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");}voidDFS(AdjListg,intv,intvisited[])//从v个顶点深度优先搜索{ ArcLinkp; intw; visited[v]=1;//做上访问过的标记 printf("%s->",g[v].name); p=g[v].firstarc;//取该顶点链表 while(p)//遍历该链表 { w=p->data; if(visited[w]==0) DFS(g,w,visited); p=p->nextarc; }}voidDFSTraverse(AdjListg)//深度优先遍历{ intvisited[MAX+1]; intv; intnum,count=1; for(v=1;v<=n;v++) { visited[v]=0;//初始化标志位 } printf("请输入你要开始的景点:"); scanf("%d",&num); while(count<=n) {v=num; if(visited[v]==0) { DFS(g,v,visited);//对尚未访问的顶点调用ＤＦＳ v++; } count++; }}voidPrintPath(AdjListg,intpath[],intlength)//打印路径{ for(inti=0;i<length;i++) { printf("%s-->",g[path[i]].name); } printf("\n");}voidSearchAllPath(AdjListG,intpath[],intvisited[],intv,intdes,intlength){ //利用深度优先遍历，path[]记录路径，visited[]设访问标志，v起点，des终点，length，代表的是访问景点的长度if(visited[v])return;//假设所有的景点都访问过，那么终止 path[length-1]=v;//开始记录路径 if(v==des)//假设找到终点那么，打印路径 { PrintPath(G,path,length); } else { visited[v]=1; for(inti=1;i<=n;i++) if(GetWeight(v,i)!=MAXEDGE&&!visited[i])//两个景点之间有路，并且还未访问过，那么深度遍历 { SearchAllPath(G,path,visited,i,des,length+1); } visited[v]=0; }}voidInitGraph(AdjList&g)//初始化图的景点{ printf("请输入图中的顶点数:"); scanf("%d",&n);printf("请输入道路的数目:"); scanf("%d",&e); printf("\n"); printf("用户可以自己写文件创立图的信息."); CreateGraph(g);}charMenu()//主菜单{ charc;intflag; do{ printf("\n西安邮电学院导游图\n"); printf("┏━━━━━━━━━━━━━━━━━━━━┓\n"); printf("┃1.创立导游系统|\n");printf("┃2.浏览校园全景┃\n");printf("┃3.寻找某一起点的最正确路径┃\n"); printf("┃4.选择出发点和目的地┃\n"); printf("┃5.查看景点信息┃\n");printf("┃6.浏览出一个起点的所有路径┃\n");printf("┃7.浏览校园图┃\n"); printf("┃8.退出系统┃\n"); printf("┗━━━━━━━━━━━━━━━━━━━━┛\n");printf("请选择(1--8)-:");scanf("%c",&c);if(c=='1'||c=='2'||c=='3'||c=='4'||c=='5'||c=='6'||c=='7'||c=='8') flag=0; if(flag) printf("输入错误,请重新选择."); getchar(); }while(flag);returnc;}voidnarrate(AdjListg)/*说明函数*/{ inti,k=0; printf("\n\t\t*****************欢送使用校园导游程序***************\n"); printf("\t__________________________________________________________________\n"); printf("\t\t景点名称\t\t|\t景点描述\n"); printf("\t________________________________|_________________________________\n"); for(i=1;i<=n;i++) { printf("\t%c(%2d)%-10s\t\t|\t%-25s%c\n",2,i,g[i].name,g[i].introduction,2);/*输出景点列表*/ k=k+1; } printf("\t________________________________|_________________________________\n");}voidPrintTU(){printf("西安邮电学院图");printf("\n"); printf("正门"); printf("\n"); printf("//||\\\\"); printf("\n"); printf("//||\\行政楼======"); printf("\n"); printf("//喷泉\\||||"); printf("\n"); printf("根底教学楼||\\||||"); printf("\n"); printf("||||\\||||"); printf("\n"); printf("||||\\||||"); printf("\n"); printf("||||\\||||"); printf("\n"); printf("实验楼||大学生活动中心||"); printf("\n"); printf("||||||\\||"); printf("\n"); printf("||||||\\||"); printf("\n"); printf("||====图书馆==人工湖\\||"); printf("\n"); printf("||||\\||"); printf("\n"); printf("||||\\||"); printf("\n"); printf("||||\\||"); printf("\n"); printf("||||======东门"); printf("\n"); printf("||"); printf("\n"); printf("||"); printf("\n"); printf("操场==========体育馆"); printf("\n"); printf("\\||"); printf("\n");printf("\\||"); printf("\n"); printf("\\||"); printf("\n"); printf("\\||"); printf("\n"); printf("\\||"); printf("\n"); printf("\\||"); printf("\n"); printf("\\||"); printf("\n"); printf("========食堂"); printf("\n"); printf("||"); printf("\n"); printf("||"); printf("\n"); printf("||============宿舍"); printf("\n");}voidmain()//主函数{AdjListg;intv0,v1,i;intvisited[MAX]; intpath[MAX]; charc;system("color5f");do