资源描述：
《图的抽象数据类型实现.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、一、题目：图的抽象数据类型实现利用VC++的工作环境实现教材里图的基本抽象数据类型。按照课本的要求运用c语言以及数据结构课程所学的知识，设计合理的数据存储结果，实现图的基本操作。二、抽象数据类型定义以及各基本操作的简要描述ADTMGraph{数据对象：n=n是具有相同特征的数据元素集合，称为顶点集。数据关系：DR={
2、v,w∈n且表示从v指向w的弧}基本操作：CreateMGraph初始条件：n是图的顶点集，e是图的边集操作结果：按和n的e定义构造图GDestroyGraph初始条件:图G存在
3、操作结果:销毁图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）的下一个邻接
4、顶点。若w是v的最后一个邻接点，则返回空InsertVex初始条件:图G存在,v和图G中顶点有相同特征操作结果:在图G中增添新顶点v(不增添与顶点相关的边,留待InsertArc()去做)DeleteVex初始条件:图G存在,v是G中某个顶点操作结果:删除G中顶点v及其相关的弧InsertArc初始条件:图G存在,v和W是G中两个顶点操作结果:在G中增添弧DeleteArc初始条件:图G存在,v和w是G中两个顶点操作结果:在G中删除弧DFSTraverseM初始条件：图G存在操作结果：对图进行
5、深度优先遍历BFSTraverseM初始条件：图G存在操作结果：对图进行广度优先遍历}ADTMGraph一、存储结构定义头文件：#include#include#defineMaxLen10/*最大输入长度*/#defineFalse0#defineTrue1#defineErrorprintf#defineQueueSize30#defineNull0#defineOK1ypedefstruct{charvexs[MaxLen];intedges[MaxLen][MaxLe
6、n];intn,e;}MGraph;/*定义全局变量*/intvisited[10];/*辅助队列的定义*/typedefstruct{intfront;intrear;intcount;intdata[QueueSize];}CirQueue;voidInitQueue(CirQueue*Q){Q->front=Q->rear=0;Q->count=0;}intQueueEmpty(CirQueue*Q){returnQ->count=QueueSize;}intQueueFull(CirQueue*Q){re
7、turnQ->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("Queueunderf
8、low");returnNull;}//if(QueueEmpty(Q))else{temp=Q->data[Q->front];Q->count--;Q->front=(Q->front+1)%QueueSize;returntemp;}//else}//DeQueue(CirQueue*Q)一、程序源代码voidCreateMGraph(MGraph&G){/*初始条件：n是图的顶点集，e是图的边集*//*操作结果：按和n的e定义构造图G*/inti,j,k;charch1,ch2;printf("tt请
9、输入顶点数和边数(输入格式为:顶点数,边数):tt");scanf("%d,%d",&(G.n),&(G.e));printf("tt请输入顶点信息(字符型)每个顶点以回车作为结束:");for(i=0;i
