数据结构{Data_Structure}

graph.c

/** Graph in C. Abreto<m@abreto.net>. 未完成. */
#include <stdlib.h>
#include <limits.h>

const size_t default_vertices = 30;	// 默认最大顶点数

typedef struct	// 结点数据类型
{
	int data;
}gmtx_vertices;

typedef struct	// 边数据类型
{
	int weight;
}gmtx_e;
const gmtx_e gmtx_zero = {0};
const gmtx_e gmtx_maxweight = {INT_MAX};

/**
 * 比较两个边数据大小
 * 
 * @返回: e1>e2时正数, e1==e2时0, e1<e2时负数.
 **/
int gmtx_e_cmp(gmtx_e e1, gmtx_e e2)
{
	return (e1.weight) - (e1.weight);
}

typedef struct			// 图的邻接矩阵结构定义
{
	size_t 			max_vertices;		// 图中最大顶点数
	int 			num_edges;			// 当前边数
	int 			num_vertices;		// 当前顶点数
	gmtx_vertices 	*vertices_list;		// 顶点表
	gmtx_e 			**edge;				// 邻接矩阵
}graphmtx, *p_graphmtx;

/**
 * 初始化图
 * 
 * 若sz为非整数则取默认最大顶点数.
 * 
 * @参数: p_graphmtx 操作图, size_t 最大顶点数
 **/
void graphmtx_init(p_graphmtx G, size_t sz)
{
	int i = 0, j = 0;
	G->max_vertices = (sz>0)?(sz):(default_vertices);
	G->vertices_list = (g_node *)malloc( G->max_vertices * sizeof(gmtx_vertices) );	// 创建顶点表数组
	G->edge = (g_edge **)malloc( G->max_vertices * sizeof(gmtx_e*) );			// 创建邻接矩阵数组
	for(i = 0;i < G->max_vertices;i++)
		*(G->edge + i) = (g_edge *)malloc( G->max_vertices * sizeof(gmtx_e) );
	for(i = 0;i < G->max_vertices;i++)	// 邻接矩阵初始化
		for(j = 0;j < G->max_vertices;j++)
			*( *(G->edge + i) + j ) = (i==j) ? gmtx_zero : gmtx_maxweight;
}