图的邻接矩阵建立
#include <stdio.h>#include <string.h>
#include <malloc.h>
#include <stdlib.h>
typedef char vertextype[4];
typedef enum{dg,dn,ug,un}graphkind;/*图的类型,有向图,无向图,有向网,无向网*/
typedef struct
{
int adj;/*对于无权图,用1表示相邻,用0表示不相邻,对于带权图,存储权值*/
char *info;/*与弧相关的信息*/
}arcnode,adjmatrix[50][50];
typedef struct/*图的类型定义*/
{
vertextype vex[50];/*用于存储顶点*/
adjmatrix arc;/*邻接矩阵,存储边或弧的信息*/
int vexnum,arcnum;/*顶点数和边的数目*/
graphkind kind;/*图的类型*/
}mgraph;
void creategraph(mgraph *n)/*采用邻接矩阵创建有向网*/
{
int i,j,k,w,infoflag,len;
char s[50];
vertextype v1,v2;
printf("请输入有向网N的顶点数,弧数,弧的信息(是1,否0)\n");
scanf("%d,%d,%d",&(*n).vexnum,&(*n).arcnum,&infoflag);
printf("请输入%d个顶点的值\n",n->vexnum);
for(i=0;i<n->vexnum;i++)/*创建一个数组,用于保存网的各个顶点*/
scanf("%s",n->vex[i]);
for(i=0;i<n->vexnum;i++)
for(j=0;j<n->vexnum;j++)
{
n->arc[i][j].adj=10000;
n->arc[i][j].info=NULL;/*弧的信息初始化为空*/
}
printf("请输入%d条弧的弧尾,弧头 权值:\n",n->arcnum);
for(k=0;k<n->arcnum;k++)
{
scanf("%s%s%d",v1,v2,&w);/*输入两个顶点和弧的权值*/
i=locatevertex(*n,v1);
j=locatevertex(*n,v2);
n->arc[i][j].adj=w;
if(infoflag)/*如果弧包含其他信息*/
{
printf("请输入弧的信息\n");
gets(s);
len=strlen(s);
if(len)
{
n->arc[i][j].info=(char *)malloc((len+1)*sizeof(char));
strcpy(n->arc[i][j].info,s);
}
}
}
n->kind=dn;/*图的类型为有向网*/
}
int locatevertex(mgraph n,vertextype v)
{/*在顶点向量中查找顶点V,找到返回向量中的序号,否则返回-1*/
int i;
for(i=0;i<n.vexnum;++i)
if(strcmp(n.vex[i],v)==0)
return i;
return -1;
}
void destorygraph(mgraph *n)
{/*销毁网*/
int i,j;
for(i=0;i<n->vexnum;i++)/*释放弧的相关信息*/
for(j=0;j<n->vexnum;j)
if(n->arc[i][j].adj!=10000)/*如果存在弧*/
if(n->arc[i][j].info!=NULL)/*如果弧有相关信息,释放该信息所占用的空间*/
{
free(n->arc[i][j].info);
n->arc[i][j].info=NULL;
}
n->vexnum=0;/*讲网的顶点数置为0*/
n->arcnum=0;/*将网的弧的数目置为0*/
}
void display(mgraph n)
{
int i,j;
printf("有向网具有%d个顶点和%d条弧,顶点一次是:",n.vexnum,n.arcnum);
for(i=0;i<n.vexnum;++i)/*输出网的顶点*/
printf("%s ",n.vex[i]);
printf("\n有向网N的:\n");
printf("序号I");/*输出网N的弧*/
for(i=0;i<n.vexnum;i++)
printf("%8d",i);
printf("\n");
for(i=0;i<n.vexnum;i++)
{
printf("%8d",i);
for(j=0;j<n.vexnum;j++)
printf("%8d",n.arc[i][j].adj);
printf("\n");
}
}
void main()
{
mgraph n;
printf("创建一个网:\n");
creategraph(&n);
printf("输出网的顶点和弧\n");
display(n);
printf("销毁网\n");
destorygraph(&n);
}