ml_graph.java

已经编写好的数据结构课本程序可以减轻您的负担

/* =============== Program Description =============== */
/* 程序名称： ml_Graph.c                               */
/* 程序目的： 设计一个将图形转成多元邻接列表的程序。    */
/* Written By Kuo-Yu Huang. (WANT Studio.)             */
/* =================================================== */
#include <stdlib.h>
#define VertexNum 6		/* 定义顶点数 */

struct Edge
{
	int	Marked;
	int	Vertex1;
	int	Vertex2;
	struct	Edge	*Edge1;
	struct	Edge	*Edge2;
};
typedef	struct	Edge	*NextEdge;

struct Node			/* 声明图形顶点结构 */
{
	int	Vertex;		/* 邻接顶点数据 */
	struct	Edge	*Next;	/* 下一个邻接顶点 */
};
typedef	struct	Node	*Graph;	/* 定义图形结构 */
struct	Node	Head[VertexNum];/* 顶点数组 */

/* --------------------------------------------------- */
/* 建立邻接顶点至邻接列表内                            */
/* --------------------------------------------------- */
void Create_ML_Graph(int Vertex1,NextEdge New)
{
	NextEdge	Pointer;	/* 节点声明 */
	NextEdge	Previous;	/* 前一个节点 */

	Previous = NULL;

	Pointer = Head[Vertex1].Next;	/* 目前的节点 */

	while ( Pointer != NULL )	/* 到达列表尾端才结束循环 */
	{
		Previous = Pointer;
					/* 如果Vertex1为起始顶点 */
		if ( Pointer->Vertex1 == Vertex1 ) 
					/* 往Edge1的下一个节点 */
			Pointer = Pointer->Edge1;
		else
					/* 往Edge2的下一个节点 */
			Pointer = Pointer->Edge2;
	}
	if ( Previous == NULL )		/* 串连在Head之后 */
		Head[Vertex1].Next = New;
	else if ( Previous->Vertex1 == Vertex1 )
		Previous->Edge1 = New;	/* 串连在Edge1之后 */
	else
		Previous->Edge2 = New;	/* 串连在Edge2之后 */
}

/* --------------------------------------------------- */
/* 输出邻接列表内数据                                  */
/* --------------------------------------------------- */
void Print_ML_Graph(struct Node *Head)
{
	NextEdge	Pointer;		/* 节点声明 */

	Pointer = Head->Next;		/* Pointer指针设为首节点 */
	while (	Pointer != NULL )	/* 当节点为NULL结束循环 */
	{
		printf("(%d,%d)",Pointer->Vertex1,Pointer->Vertex2);
		if ( Head->Vertex == Pointer->Vertex1 )
			Pointer = Pointer->Edge1;	/* 往下一个节点 */
		else if ( Head->Vertex == Pointer->Vertex2 )
			Pointer = Pointer->Edge2;
	}
	printf("\n");
}

/* --------------------------------------------------- */
/* 主程序                                              */
/* --------------------------------------------------- */
void main ()
{
	int	Source;		/* 起始顶点 */
	int	Destination;	/* 终止顶点 */
	int	Choose;		/* 选项变数 */
	NextEdge	New;	/* 新节点 */
	int	i,j;

	for ( i=0;i<VertexNum;i++ )
	{
		Head[i].Vertex = i;
		Head[i].Next = NULL;
	}
		printf("1.Undirected Graph\n");
		printf("2.Directed Graph\n");
		printf("Please choose : ");/* 选择有向图形或无向图形 */
		scanf("%d",&Choose);
	while ( 1 )
	{
		printf("Please input the Edge's source : ");
		scanf("%d",&Source);
		if ( Source == -1 )
			break;

		printf("Please input the Edge's Destination : ");
		scanf("%d",&Destination);

					/* 错误：超出范围 */
		if ( Source >= VertexNum || Destination >= VertexNum)
			printf("@Error@ : Out of range!!\n");
		else			/* 调用建立邻接列表 */
		{
			New = (NextEdge) malloc(sizeof(struct Edge));
			if ( New != NULL )	/* 配置成功 */
			{
				New->Vertex1 = Source;		/* 邻近顶点 */
				New->Vertex2 = Destination;	/* 邻近顶点 */
				New->Edge1 = NULL;	/* 下一个邻接顶点指针 */
				New->Edge2 = NULL;	/* 下一个邻接顶点指针 */
				Create_ML_Graph(Source,New);
				if ( Choose == 1 )
					Create_ML_Graph(Destination,New);
			}
		}
	}
	printf("##Graph##\n");
	for ( i=0;i<VertexNum;i++)
	{
		printf("Vertex[%d] : ",i);
		Print_ML_Graph(&Head[i]);/* 调用输出多元邻接列表数据 */
	}
}