图的抽象数据类型实现.doc

题目：图的抽象数据类型实现 利用VC++的工作环境实现教材里图的基本抽象数据类型。按照课本的要求运用c语言以及数据结构课程所学的知识，设计合理的数据存储结果，实现图的基本操作。 抽象数据类型定义以及各基本操作的简要描述 ADT MGraph{ 数据对象：n=n是具有相同特征的数据元素集合，称为顶点集。 数据关系：DR={v,w|v,w∈n且v,w表示从v指向w的弧} 基本操作： CreateMGraph 初始条件：n是图的顶点集，e是图的边集 操作结果：按和n的e定义构造图G DestroyGraph 初始条件: 图G存在 操作结果: 销毁图G GetVex 初始条件: 图G存在，v是G中某个顶点 操作结果: 返回v的值 LocateVex 初始条件：图G存在，v和G中顶点有相同特征 操作结果：若G中存在顶点v，则返回该顶点再图中的位置；否则返回空 PutVex 初始条件: 图G存在，v是G中某个顶点 操作结果: 对v赋值u FirstAdjVex 初始条件: 图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,w DeleteArc 初始条件: 图G存在,v和w是G中两个顶点 操作结果: 在G中删除弧v,w DFSTraverseM 初始条件：图G存在 操作结果：对图进行深度优先遍历 BFSTraverseM 初始条件：图G存在 操作结果：对图进行广度优先遍历 }ADT MGraph 存储结构定义 头文件：#includestdio.h #includestdlib.h #define MaxLen 10/*最大输入长度*/ #define False 0 #define True 1 #define Error printf #define QueueSize 30 #define Null 0 #define OK 1 ypedef struct { char vexs[MaxLen]; int edges[MaxLen][MaxLen]; int n,e; }MGraph; /*定义全局变量*/ int visited[10]; /*辅助队列的定义*/ typedef struct { int front; int rear; int count; int data[QueueSize]; }CirQueue; void InitQueue(CirQueue *Q) { Q-front=Q-rear=0; Q-count=0; } int QueueEmpty(CirQueue *Q) { return Q-count=QueueSize; } int QueueFull(CirQueue *Q) { return Q-count==QueueSize; } void EnQueue(CirQueue *Q,int x) { if (QueueFull(Q)) Error(Queue overflow); else { Q-count++; Q-data[Q-rear]=x; Q-rear=(Q-rear+1)%QueueSize; }//else }//EnQueue(CirQueue *Q,int x) int DeQueue(CirQueue *Q) { int temp; if(QueueEmpty(Q)) { Error(Queue underflow); return Null; }//if(QueueEmpty(Q)) else { temp=Q-data[Q-front]; Q-count--; Q-front=(Q-front+1)%QueueSize; return temp; }//else }//DeQueue(CirQueue *Q)  程序源代码 void CreateMGraph(MGraph G) { /* 初始条件：n是图的顶点集，e是图的边集*/