C语言数据结构——图的邻接表

柔情只为你懂 2021-11-26 14:54 384阅读 0赞

[  转载地址：][Link 1][https://blog.csdn.net/qq\_39630587/article/details/77409869][Link 1]

![邻接表结构][SouthEast]  
**邻接表数据结构类型如下：**

#define MaxVertices 100 
    typedef struct node     //建立边表
    {
        int adjvex;         //该边所指向的节点位置
        node* next;         //指向下一条边
    //    int info;         //可用存储该边的权值
    } ArcNode;
    typedef struct          //建立顶点表
    {
        int data;
        ArcNode *first;
    } VerNode;
    typedef struct          //建立邻接表
    {
        VerNode adjList[MaxVertices];     //邻接表的顶点
        int n,e;                          //总顶点数和边数
    } AdjList;

**注：边表为链表结构，插入元素有头插法和尾插法两种，这里以头插法为例。**

对应的，我们得到如下的结构：  
![邻接表数据结构][SouthEast 1]  
我们以无向图为例：  
![无向图][SouthEast 2]  
写出相应的邻接矩阵：  
![邻接表实际][SouthEast 3]

--------------------

** 运行结果：（输入从0开始）**

![20190723104056577.png][]

**邻接表生成函数：**

void CreateGraph(AdjList *L)          //生成邻接表
    {
        int i,a,b;
        ArcNode *s;                       //声明一个边表类型的指针
        printf("请输入总顶点和总边数:\n");
        scanf("%d %d",&L->n,&L->e);
        printf("建立顶点表:\n");
        for(i=0; i<L->n; i++)
        {
            scanf("%d",&L->adjList[i].data);    //给顶点的数据域赋初值
            L->adjList[i].first = NULL;         //初始顶点表的指针域置空
        }
        //采用头插法创建
        printf("建立边表:\n");
        for(i=0; i<L->e; i++)
        {
            //输入顶点从0开始
            printf("请输入有连接的顶点:\n");
            scanf("%d %d",&a,&b);
    //输入顶点大于0
    //        a-=1;
    //        b-=1;
            //无向图和邻接矩阵的无向图一样,是对称的
            s = (ArcNode*)malloc(sizeof(ArcNode));  //为新建边表申请堆空间
            s->adjvex = b;                          //边表的数据域赋初值，指示边表的节点位置
            s->next = L->adjList[a].first;          //头插法
            L->adjList[a].first = s;
    
            s = (ArcNode*)malloc(sizeof(ArcNode));
            s->adjvex = a;
            s->next = L->adjList[b].first;
            L->adjList[b].first = s;
        }
    }

**邻接表打印函数：**

void DisGraph(AdjList *L)
    {
        for(i=0;i<L->n;i++)
        {
    //      printf("%d->",i+1);
            printf("%d->",i);  //输入从0开始
            while(1)
            {
                if(L->adjList[i].first == NULL)
                {
                    printf("^");
                    break;
                }
    //            printf("%d->",L->adjList[i].first->adjvex+1);
                printf("%d->",L->adjList[i].first->adjvex);  //输入从0开始
                L->adjList[i].first = L->adjList[i].first->next;
            }
            printf("\n");
        }
    
    }

**注：①②处是由于边表的顺序是对应的是顶点表数组的顺序，所以起始数组为G->adjlist\[0\],但是按照人们的输入习惯，我们从1开始，所以对于每个输入的i，j进行减1处理存储，再对于输出的G->adjlist\[i\].edgenext->adjvex进行加1处理，保证输入输出的统一性**

--------------------

具体代码实现：

#include <stdio.h>
    #include <stdlib.h>
    #define MaxVertices 100
    typedef struct node     //建立边表
    {
        int adjvex;         //该边所指向的节点位置
        node* next;         //指向下一条边
    //    int info;         //可用存储该边的权值
    } ArcNode;
    typedef struct          //建立顶点表
    {
        int data;
        ArcNode *first;
    } VerNode;
    typedef struct          //建立邻接表
    {
        VerNode adjList[MaxVertices];     //邻接表的顶点
        int n,e;                          //总顶点数和边数
    } AdjList;
    void CreateGraph(AdjList *L)          //生成邻接表
    {
        int i,a,b;
        ArcNode *s;                       //声明一个边表类型的指针
        printf("请输入总顶点和总边数:\n");
        scanf("%d %d",&L->n,&L->e);
        printf("建立顶点表:\n");
        for(i=0; i<L->n; i++)
        {
            scanf("%d",&L->adjList[i].data);    //给顶点的数据域赋初值
            L->adjList[i].first = NULL;         //初始顶点表的指针域置空
        }
        //采用头插法创建
        printf("建立边表:\n");
        for(i=0; i<L->e; i++)
        {
            //输入顶点从0开始
            printf("请输入有连接的顶点:\n");
            scanf("%d %d",&a,&b);
    //输入顶点大于0
    //        a-=1;
    //        b-=1;
            //无向图和邻接矩阵的无向图一样,是对称的
            s = (ArcNode*)malloc(sizeof(ArcNode));  //为新建边表申请堆空间
            s->adjvex = b;                          //边表的数据域赋初值，指示边表的节点位置
            s->next = L->adjList[a].first;          //头插法
            L->adjList[a].first = s;
    
            s = (ArcNode*)malloc(sizeof(ArcNode));
            s->adjvex = a;
            s->next = L->adjList[b].first;
            L->adjList[b].first = s;
        }
    }
    void DisGraph(AdjList *L)
    {
        int i;
        for(i=0;i<L->n;i++)
        {
    //      printf("%d->",i+1);
            printf("%d->",i);  //输入从0开始
            while(1)
            {
                if(L->adjList[i].first == NULL)
                {
                    printf("^");
                    break;
                }
    //            printf("%d->",L->adjList[i].first->adjvex+1);
                printf("%d->",L->adjList[i].first->adjvex);  //输入从0开始
                L->adjList[i].first = L->adjList[i].first->next;
            }
            printf("\n");
        }
    
    }
    int main()
    {
        AdjList *L = (AdjList*)malloc(sizeof(AdjList));     //为邻接表申请堆空间
        CreateGraph(L);
        DisGraph(L);
    }

![wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==][wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw]

# 邻接表有向图 #

![20190723104223923.png][]![wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==][wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw]

**运行结果：**

![2019072310460695.png][]![wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==][wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw]

**加入权值后：**

![20190723105030144.png][]![wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==][wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw]

**邻接表生成函数：**

void CreateGraph(AdjList *L) {
        int i,a,b;
        ArcNode *s;
        printf("请输入总顶点数和边数:\n");
        scanf("%d %d",&L->n,&L->e);
        printf("建立顶点表:\n");
        for(i=0;i<L->n;i++)
        {
            scanf("%d",&L->adjList[i].data);
            L->adjList[i].first = NULL;
        }
        printf("建立边表:\n");
        for(i=0;i<L->e;i++)
        {
            printf("请输入有连接的顶点:\n");
            scanf("%d %d",&a,&b);
            //输入从1开始
            a-=1;
            b-=1;
    
            s = (ArcNode*)malloc(sizeof(ArcNode));
            s->adjvex = b;
            s->next = L->adjList[a].first;
            L->adjList[a].first = s;
        }
    }

![wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==][wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw]

**全部代码：**

#include <stdio.h>
    #include <stdlib.h>
    #define MaxVertices 100
    typedef struct node //边表 { 
        int adjvex;
        node* next;
        //int info; //存储权值
    }ArcNode;
    typedef struct //顶点表 { 
        int data;
        ArcNode* first;
    }VerNode;
    typedef struct //邻接表 { 
        VerNode adjList[MaxVertices];
        int n,e;
    }AdjList;
    void CreateGraph(AdjList *L) {
        int i,a,b;
        ArcNode *s;
        printf("请输入总顶点数和边数:\n");
        scanf("%d %d",&L->n,&L->e);
        printf("建立顶点表:\n");
        for(i=0;i<L->n;i++)
        {
            scanf("%d",&L->adjList[i].data);
            L->adjList[i].first = NULL;
        }
        printf("建立边表:\n");
        for(i=0;i<L->e;i++)
        {
            printf("请输入有连接的顶点:\n");
            scanf("%d %d",&a,&b);
            //输入从1开始
            a-=1;
            b-=1;
    
            s = (ArcNode*)malloc(sizeof(ArcNode));
            s->adjvex = b;
            s->next = L->adjList[a].first;
            L->adjList[a].first = s;
        }
    }
    void DisGraph(AdjList *L) {
        int i;
        for(i=0;i<L->n;i++)
        {
            printf("%d->",i+1);
            while(1)
            {
                if(L->adjList[i].first == NULL)
                {
                    printf("^");
                    break;
                }
                printf("%d->",L->adjList[i].first->adjvex+1);
                L->adjList[i].first = L->adjList[i].first->next;
            }
            printf("\n");
        }
    }
    int main() {
        AdjList *L = (AdjList*)malloc(sizeof(AdjList));
        CreateGraph(L);
        DisGraph(L);
    }

![wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==][wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw]

[Link 1]: https://blog.csdn.net/qq_39630587/article/details/77409869
[SouthEast]: /images/20211126/fd1f66af6ada4a55956f31cf8b415390.png
[SouthEast 1]: /images/20211126/a0072e6f3e2f4423a56287e22d065fb1.png
[SouthEast 2]: /images/20211126/9717835c89ac44309e5bb99d3ed6043e.png
[SouthEast 3]: /images/20211126/e9f0568642cb4aa099f90bf03ae75fa0.png
[20190723104056577.png]: /images/20211126/eea8b1287aa14852af53009e6086fc34.png
[wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw]: 
[20190723104223923.png]: https://img-blog.csdnimg.cn/20190723104223923.png
[2019072310460695.png]: https://img-blog.csdnimg.cn/2019072310460695.png
[20190723105030144.png]: https://img-blog.csdnimg.cn/20190723105030144.png