数据结构旅游区导航图课件设计.docx
- 文档编号:16387972
- 上传时间:2023-07-13
- 格式:DOCX
- 页数:55
- 大小:726.05KB
数据结构旅游区导航图课件设计.docx
《数据结构旅游区导航图课件设计.docx》由会员分享,可在线阅读,更多相关《数据结构旅游区导航图课件设计.docx(55页珍藏版)》请在冰点文库上搜索。
数据结构旅游区导航图课件设计
《数据结构课程设计》报告
题目旅游区导游图
专业计算机科学与技术
班级
(2)班
学生###
13旅游区导游图
题目内容
问题描述:
设某个旅游区共有n个旅游景点(n≥10),每个旅游景点都和相邻的m个旅游景点(m≥2,m 以(Vi,Vj,d)的形式从键盘输入建立该旅游区的旅游景点图,其中: Vi和Vj表示两个不同的旅游景点,d表示这两个景点之间的道路距离;该旅游景点图采用邻接矩阵存储结构(数组)。 实现要求: ⑴旅游景点图的输出: 分别以邻接矩阵、邻接链表的方式输出该旅游景点图。 ⑵相邻景点查询: 假设对于每个景点,设置有简易的信息查询,要求能给出与该景点相邻的所有景点(有直接的道路相通)及对应的距离。 ⑶景点路线查询: 假设对于每个景点,设置有景点路线查询,要求能给出从该景点出发到任一其它景点的最短简单路径及距离。 ⑷景点路线综合查询: 对于该旅游区的任意两个景点,找出它们之间的最短简单路径及距离。 ⑸最佳旅游路线确定: 假设该旅游区的入口也是出口,请确定一条最佳的旅游线路,该线路必须经过所有的旅游景点(有些景点可以重复经过)且走的路最短。 ⑹设计一个菜单,上述操作要求都作为菜单中的主要菜单项。 1本人完成的工作 完成的工作: 首先是用邻接矩阵的存储形式建立无向带权图,然后将邻接矩阵转换为邻接链表,最后用狄克斯特拉函数求出后面的三道有关最短路径的小题,设计主函数。 2所采用的数据结构 邻接矩阵的数据结构,包括(弧/边的结构定义、图的结构定义) 邻接链表的数据结构,包括(弧/边的结点定义、邻接表头结点定义、图的结构定义) 数据结构的定义 //邻接矩阵结构体 typedefstruct {charvex1,vex2;/*弧或边所依附的两个顶点*/ intArcVal;/*弧或边的权值*/ }ArcType;/*弧或边的结构定义*/ typedefstruct { intvexnum,arcnum;/*图的当前顶点数和弧数*/ charvexs[MAXVEX];/*顶点向量*/ intadj[MAXVEX][MAXVEX]; }MGraph;/*图的结构定义*/ //邻接链表结构体 typedefstructANode//弧的结点结构类型 {intadjvex;//该弧的终点位置 intinfo;//该弧的相关信息,这里用于存放权值 structANode*nextarc;//指向下一条弧的指针 }ArcNode; typedefstructVnode//邻接表头结点的类型 { chardata;//顶点信息 ArcNode*firstarc;//指向第一条弧 }VNode; typedefstruct { VNodeAdjList[MAXVEX]; intvexnum,arcnum;//图中顶点数n和边数e }ALGraph;//图的邻接表类型 3所设计的函数 对于每个主要函数必须给出所采用的算法思想和程序框图; 邻接矩阵和邻接链表初始化函数 MGraph*Init_MGraph() /*图的初始化*/ { MGraph*G; G=(MGraph*)malloc(sizeof(MGraph)); G->vexnum=0;G->arcnum=0;/*初始化顶点数、边数*/ return(G); } ALGraph*Init_ALGraph() /*图的初始化*/ { ALGraph*G; G=(ALGraph*)malloc(sizeof(ALGraph)); G->vexnum=0; G->arcnum=0;/*初始化顶点数*/ return(G); } 图中顶点定位的函数,判断顶点是否重复输入了 intLocateVex(MGraph*G,charvp) /*图中顶点的定位,若图中有顶点vp,返回其在顶点数组的下标值*/ { intk; for(k=0;k<=G->vexnum;k++) if(G->vexs[k]==vp)return(k); return(-1);/*图中无此顶点*/ } N NY Y 往图中增加顶点的函数 voidAddVertex(MGraph*G,charvp) /*往图的顶点数组中增加顶点*/ { intk,j; if(G->vexnum>=MAXVEX) printf("图中顶点数已达到最多! \n"); else { if(LocateVex(G,vp)==-1) { k=G->vexnum;G->vexs[G->vexnum++]=vp; for(j=0;j { G->adj[j][k]=INFINITY; G->adj[k][j]=INFINITY; /*是带权的有向图或无向图*/ } } } } N Y NY 往图的邻接矩阵中添加边(弧) voidAddArc(MGraph*G,ArcType*arc) /*往图的邻接矩阵中添加边(弧)*/ { intk=0,j=0; k=LocateVex(G,arc->vex1); j=LocateVex(G,arc->vex2); if(k==-1||j==-1) printf("边或弧的顶点不存在,错误! \n"); else { G->arcnum++; G->adj[k][j]=arc->ArcVal; G->adj[j][k]=arc->ArcVal; /*是无向图或带权的无向图,需对称赋值*/ } } 输出图的顶点矩阵和邻接矩阵 voidoutput_graphic(MGraph*G) /*输出图的顶点矩阵和邻接矩阵*/ { intk,j; printf("图的顶点如下: \n"); for(k=0;k printf("%4c",G->vexs[k]); printf("\n\n"); printf("图的邻接矩阵如下: \n"); for(k=0;k { for(j=0;j if(G->adj[k][j]==INFINITY) printf("%4s","**"); else printf("%4d",G->adj[k][j]); printf("\n\n"); } } YN YN Y 以邻接矩阵作为图的存储结构建立图 MGraph*create_graph() /*以邻接矩阵作为图的存储结构建立图*/ { charinchar[100],enchar[100],fvex,lvex; intcount=0; intweight; MGraph*G; ArcType*arc; printf("首先进行图的初始化! ! \n\n"); G=(MGraph*)malloc(sizeof(MGraph)); G=Init_MGraph(); arc=(ArcType*)malloc(sizeof(ArcType)); printf("\n请以(顶点,顶点,权值)的形式输入图的边(或弧),第一个顶点是? 表示结束: \n"); while (1) { scanf("%s",inchar);fvex=inchar[0];/*输入第一个顶点,? 结束*/ if(fvex=='? ')break; else { AddVertex(G,fvex); scanf("%s",enchar);lvex=enchar[0];AddVertex(G,lvex); scanf("%d",&weight);/*输入第二个顶点和权值*/ arc->vex1=fvex;arc->vex2=lvex; arc->ArcVal=weight;AddArc(G,arc); printf("\n请继续输入下一条边(或弧)! ! \n"); } } return(G); } 将邻接矩阵g转换成邻接表G ALGraph*MGraphToALGraph(MGraph*g,ALGraph*G) { inti,j,n=g->vexnum;//n为顶点数 ArcNode*p; G=(ALGraph*)malloc(sizeof(ALGraph)); G->arcnum=g->arcnum; G->vexnum=g->vexnum; for(i=0;i G->AdjList[i].firstarc=NULL; for(i=0;i { for(j=n-1;j>=0;j--) if(g->adj[i][j]! =INFINITY)//邻接矩阵的当前元素不为 { p=(ArcNode*)malloc(sizeof(ArcNode));//创建一个结点*p G->AdjList[j].data=g->vexs[j]; p->adjvex=g->vexs[j]; p->info=g->adj[i][j]; p->nextarc=G->AdjList[i].firstarc;//将*p链到链表后 G->AdjList[i].firstarc=p; } } returnG; } 邻接链表的输出 voidoutput_graphic_c(MGraph*g,ALGraph*G) { inti; ArcNode*p; for(i=0;i { printf("%c",G->AdjList[i].data); p=G->AdjList[i].firstarc; while(p! =NULL) { printf("%s","->"); printf("(%c,%d)",p->adjvex,p->info); p=p->nextarc; } printf("\n\n"); } } 相邻景点查询并输出 voidoutput_Find_ALGraph(ALGraph*G) {/*相邻景点查询并输出*/ intj; ArcNode*p; printf("请输入你要查询的景点(下标值): \n"); scanf("%d",&j); p=G->AdjList[j].firstarc; while(p) { printf("景点%c到景点%c的距离是%d(该两个景点之间有直接的道路相通)\n",G->AdjList[j].data,p->adjvex,p->info); p=p->nextarc; } printf("\n\n"); } 景点路线查询: 假设对于每个景点,设置有景点路线查询,要求能给出从该景点出发到任一其它景点的最短简单路径及距离。 voidDijkstra_One(ALGraph*G,MGraph*g,intv0,intdistance[],intpre[]) {//带权图G从顶点v0到其他定点的最短距离distance和最短路径前驱结点的下标pre intw; intS[30],i,j,k,p,min; printf("你所要开始查询的景点是: %c\n",G->AdjList[v0].data); for(i=0;i { distance[i]=g->adj[v0][i]; S[i]=0; if(distance[i] pre[i]=v0; else pre[i]=-1; } S[v0]=1;//顶点v0已加入到集合S中 for(i=0;i { min=INFINITY; for(j=0;j { if(! S[j]&&distance[j] { min=distance[j]; k=j; } } S[k]=1;///将找到的顶点加入到集合S中 for(w=0;w if(! S[w]&&distance[w]>distance[k]+g->adj[k][w]) { distance[w]=distance[k]+g->adj[k][w]; pre[w]=k; } } printf("查询结果: \n"); for(j=0;j if(pre[j]! =-1) { printf("从景点%c到景点%c",G->AdjList[v0].data,g->vexs[j]); p=pre[j]; printf("的最短距离是: %d",distance[j]); printf("途中经过的景点有: "); while(p! =-1) { printf("%c",g->vexs[p]); p=pre[p]; } printf("\n"); } elseif(j! =v0) printf("\n%c到%c: nopath",g->vexs[j],g->vexs[v0]); } N Y 景点路线综合查询: 对于该旅游区的任意两个景点,找出它们之间的最短简单路径及距离。 voidDijkstra_Two(ALGraph*G,MGraph*g,intv0,intdistance[],intpre[]){ //带权图G从顶点v0到其他定点的最短距离distance和最短路径前驱结点的下标pre intw; intS[30],i,j,k,p,min,d; printf("你所要开始查询的开始景点是: %c\n\n",G->AdjList[v0].data); for(i=0;i { distance[i]=g->adj[v0][i]; S[i]=0; if(distance[i] pre[i]=v0; else pre[i]=-1; } S[v0]=1;//顶点v0已加入到集合S中 for(i=0;i { min=INFINITY; for(j=0;j { if(! S[j]&&distance[j] { min=distance[j]; k=j; } } S[k]=1;///将找到的顶点加入到集合S中 for(w=0;w if(! S[w]&&distance[w]>distance[k]+g->adj[k][w]) { distance[w]=distance[k]+g->adj[k][w]; pre[w]=k; } } printf("输入你要查询的另外一个景点(下标值): "); scanf("%d",&d); printf("你要查询的另外一个景点是: %c\n",g->vexs[d]); printf("\n查询结果: \n");//输出结果 if(pre[d]! =-1) { printf("从景点%c到景点%c",G->AdjList[v0].data,g->vexs[d]); p=pre[d]; printf("的最短距离是: %d",distance[d]); printf("途中经过的景点有: "); while(p! =-1) { printf("%c",g->vexs[p]); p=pre[p]; } printf("\n"); } } 最佳旅游路线确定: 假设该旅游区的入口也是出口,请确定一条最佳的旅游线路,该线路必须经过所有的旅游景点(有些景点可以重复经过)且走的路最短。 voiddfs_path(ALGraph*g,intsrc,intcur,intvis[],GPath*cur_path,GPath*min_path) { if(vis[src]) { if(cur_path->count==g->vexnum) { if(cur_path->value { memcpy(min_path,cur_path,sizeof(GPath));/*由cur_path所指内存区域复制sizeof(GPath)个字节到min_path所指内存区域*/ return; } } return; } ArcNode*node=g->AdjList[cur].firstarc; for(;node! =NULL;node=node->nextarc)/*起始条件为node=g->AdjList[cur].firstarc*/ { charadj=node->adjvex; intindex=LocateVex(g,adj); if(vis[index]==0) { cur_path->vertex[cur_path->count++]=index; cur_path->value+=node->info; vis[index]=1; dfs_path(g,src,index,vis,cur_path,min_path); cur_path->count--; cur_path->value-=node->info; vis[index]=0; } } } YN NY voidbest_path(ALGraph*g,intsrc) { intvis[MAXVEX]; memset(vis,0,sizeof(vis)); GPathcur_path,min_path; memset(&cur_path,0,sizeof(GPath));/*将cur_path所指向的某一块内存中的每个字节的内容全部设置为0指定的ASCII值, 块的大小由第三个参数指定,这个函数通常为新申请的内存做初始化工作,其返回值为指向cur_path的指针。 */ memset(&min_path,0,sizeof(GPath));/*将min_path所指向的某一块内存中的每个字节的内容全部设置为0指定的ASCII值, 块的大小由第三个参数指定,这个函数通常为新申请的内存做初始化工作,其返回值为指向min_path的指针。 */ min_path.value=INFINITY; dfs_path(g,src,src,vis,&cur_path,&min_path); if(min_path.value! =INFINITY) { inti=0; printf("\n最佳旅游路线景点下标值是: \n"); for(i=0;i { printf("%d->",min_path.vertex[i]); } printf("\n"); printf("\n最佳旅游路线景点是: \n"); for(i=0;i { printf("%c->",g->AdjList[min_path.vertex[i]].data); } printf("\n"); }else { printf("建立的图中没有最佳路径\n"); } } 主函数 voidmain() { intn,opse,v0,i; intdistance[MAXVEX],pre[2*MAXVEX],path[MAXVEX]; ALGraph*G; MGraph*M; do {printf("\n\n请选择对图的操作要求: \n\n"); for(n=0;n<=30;n++) printf("*"); printf("\n*"); printf("1----建立图的邻接矩阵"); printf("2----图的邻接矩阵的输出"); printf("*\n"); printf("\n*"); printf("3----图的邻接链表的输出"); printf("4----相邻景点查询"); printf("*\n"); printf("\n*"); printf("5----从某点出发到另外所有点最短简单路径及距离"); printf("*\n"); printf("\n*"); printf("6----两个景点之间的最短距离(下标值)"); printf("*\n"); printf("\n*"); printf("7----最佳路径"); printf("8----退出"); printf("*\n"); for(n=0;n<=30;n++) printf("*"); printf("\n\n"); do {scanf("%d",&o
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 旅游区 导航 课件 设计