图的抽象数据类型实现

一、题目：图的抽象数据类型实现利用VC++的工作环境实现教材里图的基本抽象数据类型。按照课本的要求运用c语言以及数据结构课程所学的知识，设计合理的数据存储结果，实现图的基本操作。二、抽象数据类型定义以及各基本操作的简要描述ADTMGraph{数据对象：n=n是具有相同特征的数据元素集合，称为顶点集。数据关系：DR={v,w|v,w∈n且v,w表示从v指向w的弧}基本操作：CreateMGraph初始条件：n是图的顶点集，e是图的边集操作结果：按和n的e定义构造图GDestroyGraph初始条件:图G存在操作结果:销毁图GGetVex初始条件:图G存在，v是G中某个顶点操作结果:返回v的值LocateVex初始条件：图G存在，v和G中顶点有相同特征操作结果：若G中存在顶点v，则返回该顶点再图中的位置；否则返回空PutVex初始条件:图G存在，v是G中某个顶点操作结果:对v赋值uFirstAdjVex初始条件:图G存在，v是G中某个顶点*/操作结果:返回的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回空NextAdjVex初始条件:图G存在，v是G中某个顶点，w是v的邻接顶点操作结果:返回v（相对w）的下一个邻接顶点。若w是v的最后一个邻接点，则返回空InsertVex初始条件:图G存在,v和图G中顶点有相同特征操作结果:在图G中增添新顶点v(不增添与顶点相关的边,留待InsertArc()去做)DeleteVex初始条件:图G存在,v是G中某个顶点操作结果:删除G中顶点v及其相关的弧InsertArc初始条件:图G存在,v和W是G中两个顶点操作结果:在G中增添弧v,w1DeleteArc初始条件:图G存在,v和w是G中两个顶点操作结果:在G中删除弧v,wDFSTraverseM初始条件：图G存在操作结果：对图进行深度优先遍历BFSTraverseM初始条件：图G存在操作结果：对图进行广度优先遍历}ADTMGraph三、存储结构定义头文件：#includestdio.h#includestdlib.h#defineMaxLen10/*最大输入长度*/#defineFalse0#defineTrue1#defineErrorprintf#defineQueueSize30#defineNull0#defineOK1ypedefstruct{charvexs[MaxLen];intedges[MaxLen][MaxLen];intn,e;}MGraph;/*定义全局变量*/intvisited[10];/*辅助队列的定义*/typedefstruct{intfront;intrear;intcount;intdata[QueueSize];}CirQueue;voidInitQueue(CirQueue*Q){Q-front=Q-rear=0;Q-count=0;}2intQueueEmpty(CirQueue*Q){returnQ-count=QueueSize;}intQueueFull(CirQueue*Q){returnQ-count==QueueSize;}voidEnQueue(CirQueue*Q,intx){if(QueueFull(Q))Error(Queueoverflow);else{Q-count++;Q-data[Q-rear]=x;Q-rear=(Q-rear+1)%QueueSize;}//else}//EnQueue(CirQueue*Q,intx)intDeQueue(CirQueue*Q){inttemp;if(QueueEmpty(Q)){Error(Queueunderflow);returnNull;}//if(QueueEmpty(Q))else{temp=Q-data[Q-front];Q-count--;Q-front=(Q-front+1)%QueueSize;returntemp;}//else}//DeQueue(CirQueue*Q)3四、程序源代码voidCreateMGraph(MGraph&G){/*初始条件：n是图的顶点集，e是图的边集*//*操作结果：按和n的e定义构造图G*/inti,j,k;charch1,ch2;printf(\t\t请输入顶点数和边数(输入格式为:顶点数,边数):\n\t\t);scanf(%d,%d,&(G.n),&(G.e));printf(\t\t请输入顶点信息(字符型)每个顶点以回车作为结束:\n);for(i=0;iG.n;i++){getchar();printf(\t\t);scanf(%c,&(G.vexs[i]));}//for(i=0;iG.n;i++)for(i=0;iG.n;i++)for(j=0;jG.n;j++)G.edges[i][j]=0;printf(\t\t请输入每条边对应的两个顶点(输入格式为:i,j):\n);for(k=0;kG.e;k++){getchar();printf(\t\t请输入第%d条边的顶点:,k+1);scanf(%c,%c,&ch1,&ch2);for(i=0;ch1!=G.vexs[i];i++);for(j=0;ch2!=G.vexs[j];j++);G.edges[i][j]=1;}//for(k=0;kG.e;k++)}//CreateMGraph(MGraph&G)voidDestroyGraph(MGraph&G){/*初始条件:图G存在*//*操作结果:销毁图G*/inti,j;for(i=0;iG.n;i++)G.vexs[i]=Null;for(j=0;jG.n;j++){if(G.edges[i][j]){G.edges[i][j]=Null;}//if(G.edges[i][j])}//for(j=0;jG.n;j++)4G.n=0;//顶点数置零G.e=0;//弧数置零printf(\t\t图已销毁！\n);system(pause);}//DestroyGraph(MGraph&G)intGetVex(MGraphG){/*初始条件:图G存在，v是G中某个顶点*//*操作结果:返回v的值*/intv;printf(\t\t请输入要查找的顶点的序号以回车作为结束:\n);scanf(%d,&v);if(v0||vG.n)Error(没有该顶点);else{printf(第%d个顶点的值为:,v);printf(%c,G.vexs[v-1]);}//elseprintf(\n);printf(\n);system(pause);returnG.vexs[v-1];}//GetVex(MGraphG)intLocateVex(MGraphG,charv){/*初始条件：图G存在，v和G中顶点有相同特征*//*操作结果：若G中存在顶点v，则返回该顶点再图中的位置；否则返回空*/printf(\t\t请输入要查找的顶点信息(字符类型)以回车作为结束:\n);scanf(%c,&v);inti;for(i=0;i=G.n;++i)if(v==G.vexs[i]){printf(\t\t该接点在图中是第%d个顶点!\n,i+1);printf(\n);printf(\n);system(pause);returni+1;}//if(v==G.vexs[i])printf(\t\t没有与之匹配的顶点!\n);printf(\n);printf(\n);5system(pause);returnNull;}//LocateVex(MGraphG,charv)intPutVex(MGraph&G,charv,charu){/*初始条件:图G存在，v是G中某个顶点*//*操作结果:对v赋值u*/printf(\t\t请输入要查找的顶点信息(字符类型)以回车作为结束:\n);scanf(%c,&v);inti;for(i=0;i=G.n;++i)if(v==G.vexs[i]){printf(\t\t该接点已经找到,它在图中是第%d个顶点!\n,i+1);getchar();printf(\t\t请输入要赋给该顶点的值(字符类型)以回车作为结束:\n);scanf(%c,&u);G.vexs[i]=u;printf(\t\t已将%c顶点改为%c\n,v,u);printf(\n);printf(\n);system(pause);returnG.vexs[i];}//if(v==G.vexs[i])printf(\t\t查找不到该顶点!\n);printf(\n);printf(\n);system(pause);}//PutVex(MGraph&G,charv,charu)intFirstAdjVex(MGraphG,charv){/*初始条件:图G存在，v是G中某个顶点*//*操作结果:返回的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回空*/printf(\t\t请输入要查找的顶点信息(字符类型)以回车作为结束:\n);scanf(%c,&v);inti,j;for(i=0;iG.n;++i)for(j=0;jG.n;++j)if(v==G.vexs[i]&&G.edges[i][j]){printf(\t\t该顶点在图中是第%d个顶点!\n,i+1);printf(\t\t它的第一个邻接顶点是:%c\n,G.vexs[j]);printf(\n);6printf(\n);system(pause);returnG.vexs[j];}//if(v==G.vexs[i]&&G.edges[i][j])returnNull;}//FirstAdjVex(MGraphG,charv)intNextAdjVex(MGraphG,charv,charw){/*初始条件:图G存在，v是G中某个顶点，w是v的邻接顶点*//*操作结果:返回v（相对w）的下一个邻接顶点。若w是v的最后一个邻接点，则返回空*/printf(\t\t请输入要查找的顶点信息(字符类型)以回车作为结束:\n);scanf(%c,&v);inti,j,k,h=0,m=0;for(i=0;i=G.n&&!h;i++){if(v==G.vexs[i]){printf(\t\t该顶点在图中是第%d个顶点!\n,i+1);h=i;}}if(!(v==G.vexs[h])){printf(\t\t%c在图中不存在!\n,v);printf(\n);printf(\n);system(pause);returnNull;}getchar();printf(\t\t请输入%c的邻接顶点w的信息(字符类型)以回车作为结束:\n,v);scanf(%c,&w);for(j=0;j=G.n&&!m;j++){if(w==G.vexs[j]){printf(\t\t该顶点在图中是第%d个顶点!\n,j+1);m=j;}}if(!(w==G.vexs[m])){printf(\t\t%c在图中不存在!\n,w);7printf(\n);printf(\n);system(pause);returnNull;}if(!(G.edges[h][m])){printf(\t\t%c不是%c的邻接顶点!\n,w,v);printf(\n);printf(\n);system(pause);returnNull;}for(k=m+1;kG.n&&m;k++){if(G.edges[h][k]){printf(\t\t%c(相对%c)的下一个邻接顶点是:%c\n,v,w,G.vexs[k]);printf(\n);printf(\n);system(pause);returnG.vexs[k];}//if(G.edges[h][k])}//for(k=m+1;kG.n&&m;k++)printf(\t\t%c(相对%c)没有下一个邻接点!\n