图的抽象数据类型实现

一、 题目：图的抽象数据类型实现 利用VC++的工作环境实现教材里图的基本抽象数据类型。按照课本的要求运用c语言以及数据结构课程所学的知识，设计合理的数据存储结果，实现图的基本操作。 二、 抽象数据类型定义以及各基本操作的简要描述 ADT MGraph{ 数据对象：n=n是具有相同特征的数据元素集合，称为顶点集。 数据关系：DR={|v,w∈n且表示从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中增添弧 DeleteArc 初始条件: 图G存在,v和w是G中两个顶点 操作结果: 在G中删除弧 DFSTraverseM 初始条件：图G存在 操作结果：对图进行深度优先遍历 BFSTraverseM 初始条件：图G存在 操作结果：对图进行广度优先遍历 }ADT MGraph

#include
#include
#define MaxLen 10
#define False 0
#define True 1
#define Error printf
#define QueueSize 30
#define Null 0
#define OK 1
typedef struct
{
	char vexs[MaxLen];
	int edges[MaxLen][MaxLen];
	int ne;
}MGraph;
int  visited[10];
void CreateMGraph（MGraph &G）;
void DestroyGraph（MGraph &G）;
int LocateVex（MGraph Gchar v）;
int GetVex（MGraph G）;
int PutVex（MGraph &Gchar vchar u）;
int FirstAdjVex（MGraph Gchar v）;
int NextAdjVex（MGraph Gchar vchar w）;
void InsertVex（MGraph &Gchar v）;
int DeleteVex（MGraph &Gchar v）;
int InsertArc（MGraph &Gchar vchar w）;
int DeleteArc（MGraph &Gchar vchar w）;
void BFSTraverseM（MGraph G）;
void DFSTraverseM（MGraph G）;
void DFsM（MGraph Gint i）;
void BFSM（MGraph Gint i）;

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 *Qint x）
{
	if （QueueFull（Q））
		Error（“Queue overflow“）;
	else
	{
		Q->count++;
		Q->data[Q->rear]=x;
		Q->rear=（Q->rear+1）%QueueSize;
	}//else   
}//EnQueue（CirQueue *Qint 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）

int main（）
{
	printf（“\t**************************************************************\n“）;
	printf（“\t   *计算机学院网络工程三班*--------*张菲*--*学号3107007062*\n“）;
	printf（“\t**************************************************************\n“）;
	MGraph Ga;
	char muvw;
	int ijk;
	G=a;
	printf（“\n*建立一个有向图的邻接矩阵表示*\n“）;
	CreateMGraph（G）;
	printf（“\n已建立一个图的邻接矩阵存储\n“）;
	for（i=0;i	{  for（j=0;j	printf（“%10d“G.edges[i][j]）;
	printf（“\n“）;                
	}//for（i=0;i	printf（“\n“）;
	system（“pause“）; 
	getchar（）;
	m=‘y‘;
	while （m==‘y‘）
	{
		printf（“\n\n\n\n\n\n\t\t图子系统\n“）;
		printf（“\t\t计算机学院网络工程三班--------张菲\n“）;
		printf（“\t\t**********************************************\n“）;
		printf（“\t\t*         1-----重建邻接矩阵                 *\n“）;
		printf（“\t\t*         2-----销毁图                       *\n“）;
		printf（“\t\t*         3-----查找顶点v位置                *\n“）;
		printf（“\t\t*         4-----返回顶点v的值                *\n“）;
		printf（“\t\t*         5-----对顶点v赋值                  *\n“）;
		printf（“\t\t*         6-----返回顶点v的第一个邻接点      *\n“）;
		printf（“\t\t*         7-----返回v相对w的下一个邻接点     *\n“）;
		printf（“\t\t*         8-----插入顶点v                    *\n“）;
		printf（“\t\t*         9-----删除顶点v                    *\n“）;
		printf（“\t\t*         10----插入边                       *\n“）;
		printf（“\t\t*         11----删除边                       *\n“）;
		

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     505856  2009-07-03 00:12  课程设计报告.doc

     文件      78112  2009-07-02 20:15  课程设计报告.docx

     文件     135453  1998-06-15 00:00  analysing\analy\1.cpp

     文件         33  2009-06-29 19:11  analysing\analy\1.txt

     文件      77093  1998-06-15 00:00  analysing\analy\2.CPP

     文件      89786  1998-06-15 00:00  analysing\analy\3.CPP

     文件      91269  1998-06-15 00:00  analysing\analy\4.CPP

     文件     109417  1998-06-15 00:00  analysing\analy\5.CPP

     文件     115208  1998-06-15 00:00  analysing\analy\6.CPP

     文件     115208  1998-06-15 00:00  analysing\analy\7.cpp

     文件       3667  2009-07-02 23:56  analysing\analy\analy.c

     文件       4328  2009-06-25 21:55  analysing\analy\analy.dsp

     文件        535  2009-06-05 21:57  analysing\analy\analy.dsw

     文件       5997  2009-07-02 23:04  analysing\analy\analy.h

     文件      41984  2009-06-29 22:10  analysing\analy\analy.ncb

     文件      49664  2009-06-29 22:10  analysing\analy\analy.opt

     文件       1321  2009-07-02 23:56  analysing\analy\analy.plg

     文件     135453  1998-06-15 00:00  analysing\analy\Debug\1.CPP

     文件      70167  1998-06-15 00:00  analysing\analy\Debug\10.cpp

     文件      64028  1998-06-15 00:00  analysing\analy\Debug\11.cpp

     文件      77093  1998-06-15 00:00  analysing\analy\Debug\2.CPP

     文件      91269  1998-06-15 00:00  analysing\analy\Debug\4.CPP

     文件     109417  1998-06-15 00:00  analysing\analy\Debug\5.CPP

     文件     115208  1998-06-15 00:00  analysing\analy\Debug\6.CPP

     文件     115208  1998-06-15 00:00  analysing\analy\Debug\7.cpp

     文件      72980  1998-06-15 00:00  analysing\analy\Debug\8.cpp

     文件      61600  1998-06-15 00:00  analysing\analy\Debug\9.cpp

     文件      58368  2009-06-29 21:13  analysing\analy\Debug\analy.bsc

     文件     196715  2009-07-02 23:56  analysing\analy\Debug\analy.exe

     文件     203160  2009-07-02 23:56  analysing\analy\Debug\analy.ilk

............此处省略45个文件信息