C语言数据结构创建邻接表

Love The Way You Lie 2022-01-22 11:17 216阅读 0赞

/\*  
\*创建邻接表（链式存储）  
\*输入顶点信息  
\*输入每个边的下标  
\*创建以每一个顶点为起点的单向链表  
\*以顶点数输出链表中的数据  
\*/

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define VERTEXNUM 100
    #define ERROR 0
    #define OK  1
    typedef char * VertexType;//字符串的字符串定义
    typedef struct edgenode
    {
        int adjvex;//邻接点的下标
         struct edgenode*next;//指向下一个邻接点的指针域
    }EdgeNode;//边的结构体
    typedef struct vnode
    {
        EdgeNode*firstedge;
        //指向第一个邻接点的指针 类型为邻接边的结构体类型相同
        VertexType *vertex;
        //顶点的信息
    
    }Vnode;//顶点结构体
    typedef struct algraph
    {
        Vnode adjlist[VERTEXNUM];//顶点数组
        int n,e;//图的边数和点数
    }ALGraph;//图的邻接表的结构体
    int create_algraph(ALGraph *G);//邻接表的创建
    void test_algraph();//测试函数
    int locate(ALGraph*G,VertexType *vex);//顶点的名称的定位函数
    void main()
    {
       test();//测试函数
    
    }
    int create_algraph(ALGraph *G)//邻接表的创建
    {
        int i,j;
        int x1,x2;//临时下标变量
        EdgeNode*enode;//创建边的结构体指针
    
        VertexType vex1,vex2;
        printf("请输入图的边数:\n");
          scanf("%d",&G->e);
          printf("请输入图的点数:\n");
           scanf("%d",&G->n);
           //初始化图的顶点信息
           for(i=0;i<G->n;i++)
           {
               G->adjlist[i].vertex=(VertexType)malloc(sizeof(char)*10);
               printf("顶点%d：",i+1);
               scanf("%s",G->adjlist[i].vertex);
               G->adjlist[i].firstedge=NULL;
            }
            //创建边的信息
            for(i=0;i<G->e;i++)
            {
                vex1=(VertexType)malloc(sizeof(char)*10);
                 vex2=(VertexType)malloc(sizeof(char)*10);
                printf("请输入顶点：");
                 scanf("%s",vex1);
                 printf("请输入邻接点：");
                 scanf("%s",vex2);
                  x1= locate(G,vex1);
                  x2= locate(G,vex2);
                  if(x1==-1||x2==-1)
                      return ERROR;
                      else
                      {
                          enode=(EdgeNode*)malloc(sizeof(EdgeNode));
                          enode->adjvex=x2;
                          enode->next=G->adjlist[x1].firstedge;
                            G->adjlist[x1].firstedge=enode;
                    }
            }
            return OK;
    }
    int locate(ALGraph*G,VertexType *vex)//顶点的名
    {
        int index=0;
        while(index<G->n)
        {
            if(strcmp(vex,G->adjlist[index].vertex)==0)
                break;
              else
                index++;
        }
        return (index==G->n ? -1 : index);
    }
    void test()//测试函数
    {
        ALGraph*G;
        int i;
        int result;
        Vnode vnode;
        EdgeNode* enode;
        G=(ALGraph*)malloc(sizeof(ALGraph));
         result=create_algraph(G);
         if(result!=0)
         {
             for(i=0;i<G->n;i++)
             {
                 vnode=G->adjlist[i];
                 printf("顶点：");
                  printf("%s",vnode.vertex);
                  enode=vnode.firstedge;
                  while(enode)
                  {
                      printf("->%d",enode->adjvex);
                      enode=enode->next;
                  }
                  printf("\n");
             }
         }
    
    }