数据结构旅游区导航图课程设计.docx

数据结构课程设计报告内容及其格式数据结构课程设计报告题 目 旅游区导游图 专 业 计算机科学与技术 班 级 （2）班 学 生 # 13 旅游区导游图题目内容问题描述：设某个旅游区共有n个旅游景点（n10）,每个旅游景点都和相邻的m个旅游景点（m2，m<n）有直接的道路（有对应的距离）相通，请设计一个简易的旅游区导游系统。以(Vi ,Vj ,d)的形式从键盘输入建立该旅游区的旅游景点图，其中：Vi和Vj表示两个不同的旅游景点，d表示这两个景点之间的道路距离；该旅游景点图采用邻接矩阵存储结构(数组)。实现要求： 旅游景点图的输出：分别以邻接矩阵、邻接链表的方式输出该旅游景点图。 相邻景点查询：假设对于每个景点，设置有简易的信息查询，要求能给出与该景点相邻的所有景点(有直接的道路相通)及对应的距离。 景点路线查询：假设对于每个景点，设置有景点路线查询，要求能给出从该景点出发到任一其它景点的最短简单路径及距离。 景点路线综合查询：对于该旅游区的任意两个景点，找出它们之间的最短简单路径及距离。 最佳旅游路线确定：假设该旅游区的入口也是出口，请确定一条最佳的旅游线路，该线路必须经过所有的旅游景点（有些景点可以重复经过）且走的路最短。 设计一个菜单，上述操作要求都作为菜单中的主要菜单项。 本人完成的工作 完成的工作：首先是用邻接矩阵的存储形式建立无向带权图，然后将邻接矩阵转换为邻接链表，最后用狄克斯特拉函数求出后面的三道有关最短路径的小题，设计主函数。 所采用的数据结构邻接矩阵的数据结构，包括（弧/边的结构定义、图的结构定义）邻接链表的数据结构，包括（弧/边的结点定义、邻接表头结点定义、图的结构定义）数据结构的定义/邻接矩阵结构体typedef struct char vex1, vex2 ; /* 弧或边所依附的两个顶点 */int ArcVal ; /* 弧或边的权值 */ArcType ; /* 弧或边的结构定义 */typedef struct int vexnum, arcnum ; /* 图的当前顶点数和弧数 */char vexsMAXVEX ; /* 顶点向量 */int adjMAXVEXMAXVEX;MGraph ; /* 图的结构定义 */邻接链表结构体typedef struct ANode /弧的结点结构类型 int adjvex; /该弧的终点位置int info; /该弧的相关信息,这里用于存放权值struct ANode *nextarc; /指向下一条弧的指针 ArcNode;typedef struct Vnode /邻接表头结点的类型 char data; /顶点信息ArcNode *firstarc; /指向第一条弧 VNode;typedef struct VNode AdjListMAXVEX;int vexnum,arcnum; /图中顶点数n和边数e ALGraph; /图的邻接表类型 所设计的函数对于每个主要函数必须给出所采用的算法思想和程序框图；邻接矩阵和邻接链表初始化函数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) ; 图中顶点定位的函数，判断顶点是否重复输入了int LocateVex(MGraph *G, char vp) /* 图中顶点的定位，若图中有顶点vp，返回其在顶点数组的下标值 */ int k ;for (k=0; k<=G->vexnum; k+)if (G->vexsk=vp) return(k) ; 开始k=0返回-1k<=顶点总数？G->vexsk=vp？返回k结束k+return(-1) ; /* 图中无此顶点 */ N N Y Y 往图中增加顶点的函数void AddVertex(MGraph *G, char vp) /* 往图的顶点数组中增加顶点 */ int k, j ;if (G->vexnum>=MAXVEX)printf("图中顶点数已达到最多 !n"); elseif (LocateVex(G, vp)=-1) k=G->vexnum ; G->vexsG->vexnum+=vp ;for (j=0 ; j<G->vexnum ; j+) G->adjjk=INFINITY ;G->adjkj=INFINITY ;/* 是带权的有向图或无向图 */开始把这个点跟其他所有点建立关系，为INFINITY，表示不存在连通关系新增加一个顶点给k赋值=顶点总数调用函数LocateVex，判断顶点是否有重复判断顶点数目是否已经超过最大值结束 N Y N Y 往图的邻接矩阵中添加边(弧)void AddArc(MGraph *G , ArcType *arc) /* 往图的邻接矩阵中添加边(弧) */ int k=0, j=0;k=LocateVex(G, arc->vex1) ;j=LocateVex(G, arc->vex2) ;if (k=-1|j=-1)printf("边或弧的顶点不存在，错误 !n") ; else G->arcnum+ ;G->adjkj=arc->ArcVal ;G->adjjk=arc->ArcVal ;/* 是无向图或带权的无向图,需对称赋值 */开始给两个顶点之间加上权值边数加一判断弧所依托的两个顶点是否存在结束输出图的顶点矩阵和邻接矩阵void output_graphic(MGraph *G) /* 输出图的顶点矩阵和邻接矩阵 */ int k, j ;printf("图的顶点如下：n") ; for (k=0; k<G->vexnum; k+)printf("%4c",G->vexsk) ;printf("nn") ;printf("图的邻接矩阵如下：n") ; for (k=0; k<G->vexnum; k+)for (j=0; j<G->vexnum; j+)输出*判断两个顶点之间是否存在连通j+输出权值开始结束j=0k=0k+k=0输出第k个顶点判断j是否小于顶点总数判断k是否小于顶点总数判断k是否小于顶点总数k+if (G->adjkj=INFINITY) printf("%4s","*") ;else printf("%4d",G->adjkj) ;printf("nn") ; Y N Y N Y以邻接矩阵作为图的存储结构建立图MGraph *create_graph()/* 以邻接矩阵作为图的存储结构建立图 */ char inchar100, enchar100,fvex,lvex ;int count=0;int weight ; MGraph *G;ArcType *arc ;printf("首先进行图的初始化!nn") ;G=(MGraph *)malloc(sizeof(MGraph) ;G=Init_MGraph() ;arc=(ArcType *)malloc(sizeof(ArcType) ; printf("n请以(顶点,顶点,权值)的形式输入图的边(或弧)，第一个顶点是?表示结束：n") ; while(1) scanf("%s",inchar) ;fvex=inchar0 ; /* 输入第一个顶点，?结束 */ if (fvex='?') break ; else AddVertex(G, fvex) ; scanf("%s",enchar) ;lvex=enchar0 ;AddVertex(G, lvex) ; scanf("%d",&weight) ; /* 输入第二个顶点和权值 */ arc->vex1=fvex ; arc->vex2=lvex ; arc->ArcVal=weight ; AddArc(G, arc) ; printf("n请继续输入下一条边(或弧)!n") ; return(G) ;将邻接矩阵g转换成邻接表GALGraph *MGraphToALGraph(MGraph *g,ALGraph *G)int i,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->vexnum;i+)G->AdjListi.firstarc = NULL;for (i=0;i<n;i+) /检查邻接矩阵中每个元素 for (j=n-1;j>=0;j-)if (g->adjij!=INFINITY) /邻接矩阵的当前元素不为 p=(ArcNode *)malloc(sizeof(ArcNode); /创建一个结点*pG->AdjListj.data=g->vexsj;p->adjvex = g->vexsj;p->info=g->adjij;p->nextarc=G->AdjListi.firstarc; /将*p链到链表后G->AdjListi.firstarc=p;return G;j-给邻接点赋上邻接矩阵对应的顶点i+判断两顶点之间是否有连通头结点数组指针指向相连通的邻接点给邻接边赋上权值结束开始返回邻接表G把邻接矩阵的顶点总数赋值给邻接链表的顶点总数把邻接矩阵的边总数赋值给邻接链表的边总数把顶点总数赋值给nj=n-1i=0用循环结构把每一个顶点的头指针初始化j>=0?i<n?邻接链表的输出void output_graphic_c(MGraph *g,ALGraph *G)int i;ArcNode *p;for (i=0;i<g->vexnum;i+)printf("%c",G->AdjListi.data) ; p=G->AdjListi.firstarc;while(p!=NULL) printf("%s","->") ;printf("(%c,%d)",p->adjvex,p->info) ;p=p->nextarc ;printf("nn");相邻景点查询并输出void output_Find_ALGraph(ALGraph *G) /* 相邻景点查询并输出 */int j;ArcNode *p; printf("请输入你要查询的景点(下标值):n");scanf("%d",&j); p=G->AdjListj.firstarc;while(p)printf("景点%c到景点%c的距离是%d (该两个景点之间有直接的道路相通)n",G->AdjListj.data,p->adjvex,p->info);p=p->nextarc;开始结束输出两个顶点之间的距离把该景点在数组中的邻接边的头指针赋值给p输入景点对应的下标值判断邻接边单链表的结点指针是否为空p指向下一个结点指针printf("nn"); 景点路线查询：假设对于每个景点，设置有景点路线查询，要求能给出从该景点出发到任一其它景点的最短简单路径及距离。void Dijkstra_One(ALGraph *G, MGraph *g,int v0,int distance, int pre) / 带权图G从顶点v0到其他定点的最短距离distance和最短路径前驱结点的下标preint w;int S30,i,j,k,p,min;printf("你所要开始查询的景点是:%cn",G->AdjListv0.data);for(i=0;i<g->vexnum;i+)distancei=g->adjv0i;Si=0;if(distancei< INFINITY)prei=v0;else prei=-1; Sv0=1; /顶点v0已加入到集合S中for(i=0;i<g->vexnum;i+)min=INFINITY;for(j=0;j<g->vexnum;j+)if(!Sj&&distancej<min) min=distancej;k=j;Sk=1; /将找到的顶点加入到集合S中for(w=0;w<g->vexnum;w+) / /修改集合T中顶点的距离值if(!Sw&&distancew>distancek+g->adjkw)distancew=distancek+g->adjkw;prew=k; printf("查询结果:n");for(j=0;j<g->vexnum;j+) /输出结果if(prej!=-1) printf("从景点%c到景点%c",G->AdjListv0.data,g->vexsj);p=prej;printf("的最短距离是: %d",distancej);printf(" 途中经过的景点有:");while(p!=-1)printf(" %c",g->vexsp);p=prep;printf("n"); else if(j!=v0) printf("n%c到%c : no path",g->vexsj,g->vexsv0);开始用循环结构实现各数组的初始化输入要查询景点的下标值定义最短路径的终点集数组S置S=v0求出当前最小的distj值w=0将第j个顶点放入S中结束从v0到w的最短路径中，w的前一个顶点是k判断w是否小于顶点总数从V0出发中间只经过集合S中的顶点而到达Vw的所有路径中长度最小的路径长度distancew是否大于distancew+边adjkw的值从V0出发到w的最短距离distancew= 从V0出发到w的最短距离distancek+边adjkw的权值w+查询结果输出 N Y景点路线综合查询：对于该旅游区的任意两个景点，找出它们之间的最短简单路径及距离。void Dijkstra_Two(ALGraph *G, MGraph *g,int v0,int distance, int pre) / 带权图G从顶点v0到其他定点的最短距离distance和最短路径前驱结点的下标preint w;int S30,i,j,k,p,min,d;printf("你所要开始查询的开始景点是:%cnn",G->AdjListv0.data);for(i=0;i<g->vexnum;i+)distancei=g->adjv0i;Si=0;if(distancei< INFINITY)prei=v0;else prei=-1; Sv0=1; /顶点v0已加入到集合S中for(i=0;i<g->vexnum;i+)min=INFINITY;for(j=0;j<g->vexnum;j+)if(!Sj&&distancej<min) min=distancej;k=j;Sk=1; /将找到的顶点加入到集合S中for(w=0;w<g->vexnum;w+) / /修改集合T中顶点的距离值if(!Sw&&distancew>distancek+g->adjkw)distancew=distancek+g->adjkw;prew=k; printf("输入你要查询的另外一个景点(下标值):");scanf("%d",&d);printf("你要查询的另外一个景点是:%cn",g->vexsd);printf("n查询结果:n"); /输出结果if(pred!=-1) printf("从景点%c到景点%c",G->AdjListv0.data,g->vexsd);p=pred;printf("的最短距离是: %d",distanced);printf(" 途中经过的景点有:");while(p!=-1)printf(" %c",g->vexsp);p=prep;开始用循环结构实现各数组的初始化输入要查询景点的下标值定义最短路径的终点集数组S置S=v0printf("n"); 求出当前最小的distj值w=0将第j个顶点放入S中结束从v0到w的最短路径中，w的前一个顶点是k判断w是否小于顶点总数从V0出发中间只经过集合S中的顶点而到达Vw的所有路径中长度最小的路径长度distancew是否大于distancew+边adjkw的值从V0出发到w的最短距离distancew= 从V0出发到w的最短距离distancek+边adjkw的权值w+输入要查询另外一景点的下标值查询结果输出最佳旅游路线确定：假设该旅游区的入口也是出口，请确定一条最佳的旅游线路，该线路必须经过所有的旅游景点（有些景点可以重复经过）且走的路最短。void dfs_path(ALGraph *g,int src,int cur,int vis,GPath *cur_path,GPath * min_path)if(vissrc)if(cur_path->count=g->vexnum)if(cur_path->value<min_path->value)memcpy(min_path,cur_path,sizeof(GPath);/*由cur_path所指内存区域复制sizeof(GPath)个字节到min_path所指内存区域*/return;return;ArcNode * node =g->AdjListcur.firstarc;for(;node!=NULL; node=node->nextarc)/*起始条件为node =g->AdjListcur.firstarc*/char adj=node->adjvex;int index=LocateVex(g,adj);if(visindex=0)cur_path->vertexcur_path->count+=index;cur_path->value+=node->info;visindex=1;dfs_path(g,src,index,vis,cur_path,min_path);cur_path->count-;cur_path->value-=node->info;结束判断vp是否存在弧头顶点数据元素=LocateVexx(g,adj)最小生成树权值加递归开始把顶点的值vp复制给adj把邻接表数组的头指针赋值给node用循环结构复制cur_pat的内存到min_path判断邻接表指针是否为空node指向下一个结点visindex=0; Y N N Yvoid best_path(ALGraph *g,int src)int visMAXVEX;memset(vis,0,sizeof(vis);GPath cur_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)int i=0;printf("n最佳旅游路线景点下标值是:n");for(i=0; i<min_path.count; i+) printf("%d ->",min_path.vertexi);printf("n");printf("n最佳旅游路线景点是:n");for(i=0; i<min_path.count; i+) printf("%c-> ",g->AdjListmin_path.vertexi.data);printf("n");elseprintf("建立的图中没有最佳路径n");主函数void main() int n, opse,v0,i;int distanceMAXVEX,pre2*MAXVEX,pathMAXVEX;ALGraph *G; MGraph *M; do printf("nn请选择对图的操作要求:nn");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("nn");do scanf("%d",&opse);while (opse<1|opse>8);switch (opse)case 1: M=(MGraph *)malloc(sizeof(MGraph) ; M=create_graph() ; printf("nn"); break ;case 2: printf("n您所建立的图是：n") ;output_graphic(M) ; break ;case 3: printf(" 图G的邻接矩阵转换成邻接表:n"); G = MGraphToALGraph(M,G); output_graphic_c(M,G); break ;case 4: printf("n相邻景点是：n") ;output_Find_ALGraph(G);break ;case 5: printf("n最短简单路径及距离是：n") ;scanf(" %d",&v0);Dijkstra _One(G,M,v0,distance,pre);break ;case 6:printf("两个景点之间的最短距离(下标值):");scanf(" %d",&v0);Dijkstra _Two(G,M,v0,distance,pre);break;case 7:printf("最佳路径(下标值):");Dijkstra(M,0,distance,path);printf("从结点%c到其他各结点的最短距离为:n",M->vexs0);for(i=1;i<M->vexnum;i+)printf("到结点%c的最短距离为%d:n",M->vexsi,distancei);printf("从结点%c到其他各结点最短路径的前一结点为:n",M->vexs0);for(i=1;i<M->vexnum;i+)if(pathi!=-1)printf("到结点%c的前一结点为%c:n",M->vexsi,M->vexspathi);break; while(opse!=8);开始请选择对图的操作要求n<=30？菜单输出*n=0n+调用create_graph()，建立图breakbreakbreak调用MGraphToALGraph()，把邻接矩阵转换为邻接链表调用output_graphic()邻接矩阵的输出调用output_graphic_c()邻接矩阵的输出 结束调用output_Find_ALGraph()输出相邻景点breakbreak调用dijkshort_Two（）函数，查找两个景点间的最短距离调用dijkshort_One（）函数，查找最短简单路径和距离breakbreak调用Dijkstra（）函数，查找最佳路径 每个题目都必须有运行时的输入数据（随机产生的数据要求输出显示），运行的输出结果。建立邻接矩阵：邻接矩阵输出：邻接链表输出：相邻景点查询：从某点出发到另外所有点最短简单路径及距离：两个景点之间的最短距离：最佳路径： 每个函数中应给出尽可能详细