数据结构旅游区导航图课程设计报告书.doc

.《数据结构课程设计》报告题 目 旅游区导游图 专 业 计算机科学与技术班 级 （2）班 学 生 ### 13 旅游区导游图题目容问题描述：设某个旅游区共有n个旅游景点（n≥10）,每个旅游景点都和相邻的m个旅游景点（m≥2，m

⑹ 设计一个菜单，上述操作要求都作为菜单中的主要菜单项⒈ 本人完成的工作 完成的工作：首先是用邻接矩阵的存储形式建立无向带权图，然后将邻接矩阵转换为邻接链表，最后用狄克斯特拉函数求出后面的三道有关最短路径的小题，设计主函数⒉ 所采用的数据结构邻接矩阵的数据结构，包括（弧/边的结构定义、图的结构定义）邻接链表的数据结构，包括（弧/边的结点定义、邻接表头结点定义、图的结构定义）数据结构的定义//邻接矩阵结构体typedef struct { char vex1, vex2 ; /* 弧或边所依附的两个顶点 */int ArcVal ; /* 弧或边的权值 */}ArcType ; /* 弧或边的结构定义 */typedef struct{ int vexnum, arcnum ; /* 图的当前顶点数和弧数 */ char vexs[MAXVEX] ; /* 顶点向量 */ int adj[MAXVEX][MAXVEX];}MGraph ; /* 图的结构定义 *///邻接链表结构体typedef struct ANode //弧的结点结构类型{ int adjvex; //该弧的终点位置int info; //该弧的相关信息,这里用于存放权值struct ANode *nextarc; //指向下一条弧的指针} ArcNode;typedef struct Vnode //邻接表头结点的类型{ char data; //顶点信息ArcNode *firstarc; //指向第一条弧} VNode;typedef struct { VNode AdjList[MAXVEX];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->vexs[k]==vp) return(k) ; 开始k=0返回-1k<=顶点总数？G->vexs[k]==vp？返回k结束k++ return(-1) ; /* 图中无此顶点 */} N N Y Y往图中增加顶点的函数void AddVertex(MGraph *G, char vp) /* 往图的顶点数组中增加顶点 */{ int k, j ; if (G->vexnum>=MAXVEX) printf("图中顶点数已达到最多 !\n"); else { if (LocateVex(G, vp)==-1) { k=G->vexnum ; G->vexs[G->vexnum++]=vp ; for (j=0 ; jvexnum ; j++) { G->adj[j][k]=INFINITY ; G->adj[k][j]=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->adj[k][j]=arc->ArcVal ; G->adj[j][k]=arc->ArcVal ; /* 是无向图或带权的无向图,需对称赋值 */开始给两个顶点之间加上权值边数加一判断弧所依托的两个顶点是否存在结束 }}输出图的顶点矩阵和邻接矩阵void output_graphic(MGraph *G) /* 输出图的顶点矩阵和邻接矩阵 */{ int k, j ;printf("图的顶点如下：\n") ; for (k=0; kvexnum; k++)printf("%4c",G->vexs[k]) ;printf("\n\n") ;printf("图的邻接矩阵如下：\n") ; for (k=0; kvexnum; k++){ for (j=0; jvexnum; j++)输出**判断两个顶点之间是否存在连通j++输出权值开始结束j=0k=0k++k=0输出第k个顶点判断j是否小于顶点总数判断k是否小于顶点总数判断k是否小于顶点总数k++if (G->adj[k][j]==INFINITY) printf("%4s","**") ;else printf("%4d",G->adj[k][j]) ;printf("\n\n") ;} } Y N Y N Y以邻接矩阵作为图的存储结构建立图MGraph *create_graph()/* 以邻接矩阵作为图的存储结构建立图 */{ char inchar[100], enchar[100],fvex,lvex ;int count=0;int weight ; 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=w。