C语言数据结构创建有向图的邻接矩阵-顺序存储

电玩女神 2022-01-22 11:23 244阅读 0赞

/\*  
\*顺序储存有向图邻接矩阵  
\*定义一个边的权值的二维数组  
\*定义一个点的一维数组  
\*创建一个邻接矩阵  
\*输出这个邻接矩阵  
\*/

#include<stdio.h>
     #include<string.h>
     #include<stdlib.h>
     #define MAXVERTEX 100//顶点数
     #define ERROR 0
     #define OK 1
     typedef   char * VertexType;//顶点数据类型
     typedef int ArcType;//权值数据类型
     typedef int Statu;//返回值的数据类型
     typedef enum{
    
       DG,//有向图
       UDG,//无向图
       DN,//有向网
       UDN//无向网
     }GraphKind;//图的枚举类型
     typedef struct
     {
         VertexType vertex[MAXVERTEX];//点的一维数组
         ArcType arcs[MAXVERTEX][MAXVERTEX];//权值的二维数组
           int vertexcount;//点数
           int arccount;//边数
           GraphKind kind;//图的类型
    }Mtrix_Graph;//图的结构体类型
    Statu create_matrixgraph(Mtrix_Graph*G);//创建邻接矩阵
     void test();//测试函数
     int locate_graph(Mtrix_Graph*G,VertexType vex);//返回名称在数组中的下标（定位函数）
     void main()
     {
         test();//测试函数
    
     }
     Statu create_matrixgraph(Mtrix_Graph*G)//创建邻接矩阵
     {
         G->kind=UDG;//表明是无向图  （UDG代表有向图）
         int i;
         int j;
        int x,y;
         printf("输入图的顶点数:");
         scanf("%d",&G->vertexcount);
         printf("输入图的边数:");
           scanf("%d",&G->arccount);
             printf("请依次输入顶点的信息:\n");
             for( i=0;i<G->vertexcount;i++)
             {
                 G->vertex[i]=(VertexType)malloc(sizeof(char)*10);//分配内存空间
                 printf("顶点%d：",i+1);
                 scanf("%s",G->vertex[i]);
            }
            for(i=0;i<G->vertexcount;i++)//邻接矩阵初始化
                  for(j=0;j<G->vertexcount;j++)
                      G->arcs[i][j]=0;
                       //输入边的顶点位置 创建邻接矩阵
                      for( i=0;i<G->arccount;i++)
                      {
                          VertexType vex1=(VertexType)malloc(sizeof(char)*10);
                          //创建临时字符串变量
                           VertexType vex2=(VertexType)malloc(sizeof(char)*10);
                          printf("顶点：");
                            scanf("%s",vex1);
                            printf("临接点：");
                            scanf("%s",vex2);
                              x=locate_graph(G,vex1);
                              y=locate_graph(G,vex2);
                            if(x==-1||y==-1)
                                return ERROR;
                                else{
                            G->arcs[x][y]=1;
                            //G->arcs[y][x]=G->arcs[x][y];//无向图对称原因
                            free(vex1);//临时变量释放空间
                            free(vex2);
                                }
                    }
              return OK;
    }
    int  locate_graph(Mtrix_Graph*G,VertexType vex)//返回名称在数组中的下标
    {
        int index=0;
        while(index<G->vertexcount)
        {
            if(strcmp(vex,G->vertex[index])==0)
            {
                break;
            }
            else
                index++;
        }
         return index==G->vertexcount?-1:index;
    
    }
    void test()//测试函数
    {
        Mtrix_Graph *G;
        int i,j;
        G=(Mtrix_Graph*)malloc(sizeof(Mtrix_Graph));
       Statu result =create_matrixgraph(G);
        if(result==ERROR)
        {
            printf("创建邻接矩阵失败:\n");
             return ;
        }
        printf("打印一个邻接矩阵:\n");
            printf("\t");//格式控制最上面的一行字母和矩阵数字对齐
           for(i=0;i<G->vertexcount;i++)
            {
                printf("\t%s",G->vertex[i]);//输出第一行的字母
    
            }
            printf("\n");//第一行字母打印完之后换行
            for(i=0;i<G->vertexcount;i++)
            {
                printf("\t%s",G->vertex[i]);//输出每一行的第一个字母 \t 缩进八个字节
                for(j=0;j<G->vertexcount;j++)
                    printf("\t%d",G->arcs[i][j]);//缩进八个字节
                   printf("\n");//输入每一行之后换行
            }
    
    
    
    
    
    
    
    }