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

《数据结构》课程设计报告内容及其格式《数据结构课程设计》报告题目旅游区导游图专业计算机科学与技术班级（2）班学生###《数据结构》课程设计报告内容及其格式13旅游区导游图题目内容问题描述：设某个旅游区共有n个旅游景点（n≥10）,每个旅游景点都和相邻的m个旅游景点（m≥2，mn）有直接的道路（有对应的距离）相通，请设计一个简易的旅游区导游系统。以(Vi,Vj,d)的形式从键盘输入建立该旅游区的旅游景点图，其中：Vi和Vj表示两个不同的旅游景点，d表示这两个景点之间的道路距离；该旅游景点图采用邻接矩阵存储结构(数组)。实现要求：⑴旅游景点图的输出：分别以邻接矩阵、邻接链表的方式输出该旅游景点图。⑵相邻景点查询：假设对于每个景点，设置有简易的信息查询，要求能给出与该景点相邻的所有景点(有直接的道路相通)及对应的距离。⑶景点路线查询：假设对于每个景点，设置有景点路线查询，要求能给出从该景点出发到任一其它景点的最短简单路径及距离。⑷景点路线综合查询：对于该旅游区的任意两个景点，找出它们之间的最短简《数据结构》课程设计报告内容及其格式单路径及距离。⑸最佳旅游路线确定：假设该旅游区的入口也是出口，请确定一条最佳的旅游线路，该线路必须经过所有的旅游景点（有些景点可以重复经过）且走的路最短。⑹设计一个菜单，上述操作要求都作为菜单中的主要菜单项。⒈本人完成的工作完成的工作：首先是用邻接矩阵的存储形式建立无向带权图，然后将邻接矩阵转换为邻接链表，最后用狄克斯特拉函数求出后面的三道有关最短路径的小题，设计主函数。⒉所采用的数据结构邻接矩阵的数据结构，包括（弧/边的结构定义、图的结构定义）邻接链表的数据结构，包括（弧/边的结点定义、邻接表头结点定义、图的结构定义）数据结构的定义//邻接矩阵结构体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;//图的邻接表类型⒊所设计的函数对于每个主要函数必须给出所采用的算法思想和程序框图；邻接矩阵和邻接链表初始化函数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);/*图中无此顶点*/}NNYY往图中增加顶点的函数voidAddVertex(MGraph*G,charvp)/*往图的顶点数组中增加顶点*/开始k=0返回-1k=顶点总数？G-vexs[k]==vp？返回k结束k++《数据结构》课程设计报告内容及其格式{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;jG-vexnum;j++){G-adj[j][k]=INFINITY;G-adj[k][j]=INFINITY;/*是带权的有向图或无向图*/}}}}NYNY开始把这个点跟其他所有点建立关系，为INFINITY，表示不存在连通关系新增加一个顶点给k赋值=顶点总数调用函数LocateVex，判断顶点是否有重复判断顶点数目是否已经超过最大值结束《数据结构》课程设计报告内容及其格式往图的邻接矩阵中添加边(弧)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;kG-vexnum;k++)printf(%4c,G-vexs[k]);printf(\n\n);printf(图的邻接矩阵如下：\n);for(k=0;kG-vexnum;k++){for(j=0;jG-vexnum;j++)if(G-adj[k][j]==INFINITY)printf(%4s,**);elseprintf(%4d,G-adj[k][j]);printf(\n\n);}}YNYN判断两个顶点之j++开始结束j=0k=0k++k=0输出第k个顶点判断j是否小于顶点总数判断k是否小于顶点总数判断k是否小于顶点总数k++《数据结构》课程设计报告内容及其格式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转换成邻接表GALGraph*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;iG-vexnum;i++)G-AdjList[i].firstarc=NULL;for(i=0;in;i++)//检查邻接矩阵中每个元素{for(j=n-1;j=0;j--)if(g-adj[i][j]!=INFINITY)//邻接矩阵的当前元素不为{p=(ArcNode*)malloc(sizeof(ArcNode));//创建一个结点*pG-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;}i++判断两顶点之结束开始返回邻接表G把邻接矩阵的顶点总数赋值给邻接链表的顶点总数把邻接矩阵的边总数赋值给邻接链表的边总数把顶点总数赋值给nj=n-1i=0用循环结构把每一个顶点的头指针初始化j=0?in?《数据结构》课程设计报告内容及其格式邻接链表的输出voidoutput_graphic_c(MGraph*g,ALGraph*G){inti;ArcNode*p;for(i=0;ig-vexnum;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);}开始结束输出两个顶点之间的距离把该景点在数组中的邻接边的头指针赋值给p输入景点对应的下标值判断邻接边单链表的结点指针是否为空p指向下一个结点指针《数据结构》课程设计报告内容及其格式景点路线查询：假设对于每个景点，设置有景点路线查询，要求能给出从该景点出发到任一其它景点的最短简单路径及距离。voidDijkstra_One(ALGraph*G,MGraph*g,intv0,intdistance[],intpre[]){//带权图G从顶点v0到其他定点的最短距离distance和最短路径前驱结点的下标preintw;intS[30],i,j,k,p,min;printf(你所要开始查询的景点是:%c\n,G-AdjList[v0].data);for(i=0;ig-vexnum;i++){distance[i]=g-adj[v0][i];S[i]=0;if(dist