#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");/*输出网Ｎ的弧*/
   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);
}