题 专 班 学《数据结构课程设计》报告目旅游区导游图业计算机科学与技术级 生###13旅游区导游图题目容问题描述：设某个旅游区共有n个旅游景点（n习0），每个旅游景点都和相邻的m个旅 游景点（m±2, m
1. 本人完成的工作完成的工作：首先是用邻接矩阵的存储形式建立无向带权图，然后将邻接矩阵 转换为邻接链表，最后用狄克斯特拉函数求出后面的三道有关最短路径的小题, 设计主函数2. 所采用的数据结构邻接矩阵的数据结构，包括（弧/边的结构定义、图的结构定义） 邻接链表的数据结构，包括（弧/边的结点定义、邻接表头结点 定义、图的结构定义）数据结构的定义〃邻接矩阵结构体typedef struct{ char vexl, 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;} ALGraph:〃指向下一条弧的指针//邻接表头结点的类型〃顶点信息//指向第一条弧//图中顶点数n和边数e//图的邻接表类型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);}图中顶点定位的函数，判断顶点是否重复输入了int LocateVex(MGraph *G, char vp)/*图中顶点的定位，若图中有顶点vp,返回其在顶点数组的下标值*/{int k ;for (k=0; k<=G->vexnum; k++)if (G->vexs [k] =vp) return (k);int k, j ;if (G->vexnum>=MAXVEX)printff图中顶点数己达到最多！\n〃)；else{if (LocateVex(G, vp)==-l)(k=G->vexnum ; G->vexs[G->vexnum++]=vp ;for (j=0 ; jvexnum ; j++){G->adj[j][k]=INFINITY ;G->adj[k][j]=INFINITY ;/*是带权的有向图或无向图*/结束往图的邻接矩阵中添加边(弧)void AddArc(MGraph *G , ArcType *arc)/*往图的邻接矩阵中添加边(弧)*/(int k=0, j=0;k=LocateVex(G, arc-〉vexl) ;j=LocateVex(G, arc->vex2) ;if (k=-l | | j=T)printf C边或弧的顶点不存在，错误！\n");elseG->arcnum++ ;G->adj[k][j]=arc->ArcVal ;G->adj[j][k]=arc->ArcVal ;/*是无向图或带权的无向图，需对称赋值*/输出图的顶点矩阵和邻接矩阵void output_graphic(MGraph *G)/*输出图的顶点矩阵和邻接矩阵 */{int k, j ;printf C图的顶点如下：\n");for (k=0; kvexnum; k++)printf("%4c”, G->vexs[k]);printf("\n\n");printff图的邻接矩阵如下：\n〃)；for (k=0; kvexnum; k++)for (j=0; jvexnum; j++) if (G->adj[k][j]==INFINITY)业il幽;由;人TiH上'当以邻接矩阵作为图的存储结构建立图MGraph *create_graph()/*以邻接矩阵作为图的存储结构建立图*/(char inchar[100], enchar[100], fvex, Ivex ;int count=0;int weight ;MGraph *G;ArcType *arc ;printf Cz首先进行图的初始化！ ！\n\n〃)；G=(MGraph *)malloc(sizeof(MGraph));G=Init_MGraph ();arc=(ArcType *)malloc(sizeof(ArcType));printf C\n请以(顶点，顶点，权值)的形式输入图的边(或弧)，第一个顶 点是?表示结束：\n〃)；while (1){scanf (，，%s，/, inchar) ;fvex=inchar [0] ; /* 输入第一个顶点，?结束*/if (fvex==, ?') break ;elseAddVertex(G, fvex);scanf("%s”, enchar) ;lvex=enchar[0] ;AddVertex(G, Ivex);scanf &weight) ; /*输入第二个顶点和权值*/arc->vexl=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;ivexnum;i++)G->AdjList[i]. firstarc = NULL;for (i=0;i=0; j—)if (g->adj[i][j]!INFINITY) //邻接矩阵的当前元素不为p= (ArcNode *)malloc(sizeof (ArcNode)); //创建一个结点*p G->AdjList [j]. data=g->vexsEj];p->adjvex = g->vexs[j];))return G;p->info=g->adj[i][j];p->nextarc=G->AdjList [i]. firstarc; //将*?链到链表后G->AdjList [i]. firstarc=p;邻接链表的输出void output_graphic_c(MGraph *g, ALGraph *G)(int i;ArcNode *p;for (i=0;ivexnum;i++)(printf("%c”, G~>AdjList[i]. data);p=G->AdjList[i]. firstare;while (p!=NULL)(printf("%s",;printf (〃 (%c, %d)”, p->adjvex, p->info);p=p->nextarc ;}相邻景点查询并输出void output_Find_ALGraph(ALGraph *G)( /*相邻景点查询并输出 */int j;ArcNode *p;printf (，z请输入你要查询的景点(下标值)：\n");scanf &j);p=G->AdjList[j]. firstare;while (p)(printf C景点%c到景点%c的距离是%(1 (该两个景点之间有直接的道路 相通)\n”, G->AdjList [j]. data, p->adjvex, p->info);景点路线查询：假设对于每个景点，设置有景点路线查询，要求能给出从该景 点出发到任一其它景点的最短简单路径及距离。
void Dijkstra_One(ALGraph *G, MGraph *g, int vO, int distance[], int pre[]){ //带权图G从顶点vO到其他定点的最短距离distance和最短路径前驱结 点的下标preint w;int S[30], i, j, k, p, min;printf ("你所要开始查询的景点是:％c\n”, G->AdjList[vO]. data);for (i=0;ivexnum;i++){distance[i]=g->adj[vO][i]:S[i]=0;if (distance [i]< INFINITY)pre[i]=v。
