---------------------------graph.h--------------------
/*一个最简单图实现，只提供了最基本的接口
*用数组存储的无向图，本代码用到c99新增的bool类型。
*建议使用dev c++4.9.9.0编译该代码*/
#ifndef GRAPH_H
#define GRAPH_H
/*函数返回状态*/
#ifndef OK
#define OK 1 /*成功*/
#define ERR -1 /*失败*/
#endif
/*定义函数中可能用到最大最小值*/
#ifndef MAX
#define MAX 100
#define MIN 0
#endif
/**/
typedef int status; /*函数返回状态*/
typedef int elemtype; /*用户根据需要更改此数据类型*/
typedef struct {
elemtype date; /*图顶点存储的数据*/
int arcn; /*图顶点的度数*/
} date;/*图的顶点*/
typedef bool adjmatrix[ MAX ][ MAX ];/*图的关系矩阵类型*/
typedef struct {
date vec[ MAX ]; /*存储顶点的向量*/
adjmatrix arcs; /*图的关系矩阵*/
int node_number, arc_number;/*顶点和边的数目*/
} graph;/*一个图类型定义*/
status creategraph( graph *gptr ); /*建立一个图*/
int find_gnode( const graph*, const elemtype ); /*查找一个顶点*/
status print_graph( const graph *gptr ); /*打印*/
#endif
---------------------graph.c-------------------------------------------
#include <stdio.h>
#include "graph.h"
status creategraph( graph *gptr ) /*建立图*/
{
int i, j, k;
if( gptr == NULL ) /*如果指针为空*/
return ERR;
printf( "请输入顶点个数：" );
scanf( "%d", &gptr->node_number );
printf( "请输入边数：" );
scanf( "%d", &gptr->arc_number );
printf( "请输入%d个数据：", gptr->node_number );
for( i = 0; i < gptr->node_number; ++i )
{/*初始化并设置数据向量*/
scanf( "%d", &gptr->vec[i].date );
gptr->vec[i].arcn = 0;
}
for( i = 0; i < gptr->node_number; ++i )
for( j = 0; j < gptr->node_number; ++j )
gptr->arcs[i][j] = false; /*初始化关系矩阵*/
for( k = 0; k < gptr->arc_number; ++k )
{/*设计关系矩阵*/
elemtype a, b;
printf( "请输入相邻的节点的数据：" );
scanf( "%d %d", &a, &b );
i = find_gnode( gptr, a );
j = find_gnode( gptr, b );
if( ( i < 0 ) || ( j < 0 ) )
return ERR;
gptr->arcs[i][j] = gptr->arcs[j][i] = true;
}
for( i = 0; i < gptr->node_number; ++i )
for( j = 0; j < gptr->node_number; ++j )
gptr->vec[i].arcn += gptr->arcs[i][j];
/*计算每个顶点的度*/
return OK;
}
int find_gnode( const graph *gptr, const elemtype date )
{ /*查找顶点*/
int i;
if( gptr == NULL ) /*如果指针为空，返回负值*/
return -1;
for( i = 0; i < gptr->node_number; ++i )
if( date == gptr->vec[i].date )
return i;
return -1; /*没找到也返回负值*/
}
status print_graph( const graph *gptr )/*打印*/
{
int i, j;
if( gptr == NULL )
return ERR;
printf( "图中存储数据（节点度数）如下：\n" );
for( i = 0; i < gptr->node_number; ++i )
printf("%d(%d)\t", gptr->vec[i].date, gptr->vec[i].arcn );
printf( "\n" );
printf( "图的关系矩阵如下：\n" );
for( i = 0; i < gptr->node_number; ++i )
{ for( j = 0; j < gptr->node_number; ++j )
printf( "%d\t", gptr->arcs[i][j] );
printf( "\n" );
}
return OK;
}
