【大话数据结构C语言】39 图的存储结构（邻接表）

我的公众号是【CodeAllen】，程序员技术交流①群：736386324,转载请注明出处

上一篇说的临接矩阵是不错的图存储结构，但是对于边数相对顶点较少的图，这种结构是存在对存储空间极大浪费的

因此可以考虑另外一种存储结构：比如把数组和链表结合一起来存储

临接表无向图的处理方法：

1.图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便

2.图中每个顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以我们选择用单链表来存储

临接表有向图的处理方法：

以把顶点当弧尾建立的临接表，这样很容易可以得到每个顶点的出度

临接表网的处理方法：

对于带权值的网图，可以在边表结点定义中在增加一个数据域来存储权值即可

代码实现：

      #define MAXVEX 100
      typedef struct EdgeNode         // 边表结点
      {
          int adjvex;                 // 邻接点域，存储该顶点对应的下标
          int weight;                 // 用于存储权值，对于非网图可以不需要
          struct EdgeNode *next;      // 链域，指向下一个邻接点
      } EdgeNode;
      typedef struct VertexNode       // 顶点表结点
      {
          char data;                  // 顶点域，存储顶点信息
          EdgeNode *firstEdge;        // 边表头指针
      } VertexNode, AdjList[MAXVEX];
      typedef struct
      {
          AdjList adjList;
          int numVertexes, numEdges;  // 图中当前顶点数和边数
      } GraphAdjList;
      // 建立图的邻接表结构
      void CreateALGraph(GraphAdjList *G)
      {
          int i, j, k;
          EdgeNode *e;
          printf("请输入顶点数和边数：\n");
          scanf("%d %d", &G->numVertexes, &G->numEdges);
          // 读取顶点信息，建立顶点表
          for( i=0; i < G->numVertexes; i++ )
          {
              scanf("%c", &G->adjList[i].data);
              G->adjList[i].firstEdge = NULL;     // 初始化置为空表
          }
          for( k=0; k < G->numEdges; k++ )
          {
              printf("请输入边(Vi,Vj)上的顶点序号：\n");
              scanf("%d %d", &i, &j);
              e = (EdgeNode *)malloc(sizeof(EdgeNode));
              e->adjvex = j;                      // 邻接序号为j
              e->next = G->adjList[i].firstEdge;
              G->adjList[i].firstEdge = e;
              e = (EdgeNode *)malloc(sizeof(EdgeNode));
              e->adjvex = i;                      // 邻接序号为i
              e->next = G->adjList[j].firstEdge;
              G->adjList[j].firstEdge = e;
          }
      }
  
 

文章来源: allen5g.blog.csdn.net，作者：CodeAllen的博客，版权归原作者所有，如需转载，请联系作者。

原文链接：allen5g.blog.csdn.net/article/details/116310626