adjmgraph.h

数据结构课程设计：“构造可以使n个城市连接的最小生成树”算法的实现！非常不错！

/*顺序表头文件*/
//结构体定义
typedef struct
{
	DataType list[MaxSize];
	int size;
}SeqList;
//初始化
void ListInitiate(SeqList *L)
{
	L->size=0;
}
//求当前数据个数
int ListLength(SeqList L)
{
	return L.size;
}
//插入数据元素
int ListInsert(SeqList *L,int i,DataType x)
{
	int j;
	if(L->size >=MaxSize)
	{
		printf("顺序表已满无法插入！\n");
		return 0;
	}
	else if(i<0||i>L->size)
	{
		printf("参数i不合法！\n");
		return 0;
	}
	else 
	{
		for(j=L->size;j>i;j--)
			L->list[j]=L->list[j-1];
		L->list[i]=x;
		L->size ++;
		return 1;
	}
}
//删除数据元素
int ListDelete(SeqList *L,int i,DataType *x)
{
	int j;
	if(L->size<=0)
	{
		printf("顺序表已空无数据元素可删！\n");
		return 0;
	}
	else if(i<0||i>L->size -1)
	{
		printf("参数i不合法");
		return 0;
	}
	else
	{
		*x=L->list[i];
		for(j=i+1;j<=L->size-1;j++)
			L->list[j-1]=L->list[j];
		L->size--;
		return 1;
	}
}
//取数据元素
int ListGet(SeqList L,int i,DataType *x)
{
	if(i<0||i>L.size -1)
	{
		printf("参数i不合法！\n");
		return 0;
	}
	else
	{
		*x=L.list[i];
		return 1;
	}
}


/*图的创建函数设计*/
typedef struct
{
	int row;
	int col;
	int weight;
}RowColWeight;

typedef struct
{
	SeqList Vertices;
	int edge[MaxVertices][MaxVertices];
	int numOfEdges;
}AdjMGraph;





/*图的邻接矩阵表示*/


void Initiate(AdjMGraph *G,int n)
{
	int i,j;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
	{
		if(i==j) 
			G->edge[i][j]=0;
		else 
			G->edge[i][j]=MaxWeight;
	}

	G->numOfEdges=0;
	ListInitiate(&G->Vertices);
}


void InsertVertex(AdjMGraph *G,DataType vertex)
{
	ListInsert(&G->Vertices,G->Vertices.size,vertex);
}


void InsertEdge(AdjMGraph *G,int v1,int v2,int weight)
{
	if(v1<0||v1>G->Vertices.size||v2<0||v2>G->Vertices.size)
	{
		printf("参数v1或v2越界出错！\n");
		exit(1);
	}

	G->edge[v1][v2]=weight;
	G->numOfEdges++;
}

void DeleteEdge(AdjMGraph *G,int v1,int v2)
{
	if(v1<0||v1>G->Vertices.size||v2<0||v2>G->Vertices.size||v1==v2)
	{
		printf("参数V1或v2越界出错！\n");
		exit(1);
	}

	if(G->edge[v1][v2]==MaxWeight||v1==v2)
	{
		printf("该边不存在！\n");
		exit(0);
	}

	G->edge[v1][v2]=MaxWeight;
	G->numOfEdges--;
}


void DeleteVerten(AdjMGraph *G,int v)
{
	int n=ListLength(G->Vertices),i,j;
	DataType x;

	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if( (i==v||j==v) && G->edge[i][j]>0 && G->edge[i][j]>MaxWeight )
				G->numOfEdges--;
			for(i=v;i<n;i++)
				for(j=0;j<n;j++)
					G->edge[i][j]=G->edge[i+1][j];
				for(i=0;i<n;i++)
					for(j=v;j<n;j++)
						G->edge[i][j]=G->edge[i][j+1];
					ListDelete(&G->Vertices,v,&x);
}


int GetFirstVex(AdjMGraph G,int v)
{
	int col;

	if(v<0||v>G.Vertices.size)
	{
		printf("参数V1越界出错！\n");
		exit(1);
	}

	for(col=0;col<G.Vertices.size;col++)
		if(G.edge[v][col]>0 && G.edge[v][col]<MaxWeight)
			return col;
		return -1;
}


int GetNextVex(AdjMGraph G, int v1,int v2)
{
	int col;
	 
	if(v1<0||v1>G.Vertices.size||v2<0||v2>G.Vertices.size)
	{
		printf("参数V1或v2越界出错！\n");
		exit(1);
	}

	for(col=v2+1;col<G.Vertices.size;col++)
		if(G.edge[v1][col]>0&&G.edge[v1][col]<<MaxWeight)
			return col;
	return -1;
}


void CreatGraph(AdjMGraph *G,DataType V[],int n,RowColWeight E[],int e)
{
	int i,k;
	 
	Initiate(G,n);

	for(i=0;i<n;i++)
		InsertVertex(G,V[i]);

	for(k=0;k<e;k++)
		InsertEdge(G,E[k].row,E[k].col,E[k].weight );
}