【大话数据结构C语言】40 图的存储结构（十字链表）

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

十字链表的好处就是把邻接表和逆邻接表整合到了一起，这样就又容易找到以Vi为尾的弧，又容易找到以Vi为头的弧，因而容易求得顶点的出度和入度

十字链表的构建过程转化为 C 语言代码为：

      #define MAX_VERTEX_NUM 20
      #define InfoType int//图中弧包含信息的数据类型
      #define VertexType int
      typedef struct ArcBox{
         int tailvex,headvex;//弧尾、弧头对应顶点在数组中的位置下标
         struct ArcBox *hlik,*tlink;//分别指向弧头相同和弧尾相同的下一个弧
          InfoType *info;//存储弧相关信息的指针
      }ArcBox;
      typedef struct VexNode{
          VertexType data;//顶点的数据域
          ArcBox *firstin,*firstout;//指向以该顶点为弧头和弧尾的链表首个结点
      }VexNode;
      typedef struct {
          VexNode xlist[MAX_VERTEX_NUM];//存储顶点的一维数组
         int vexnum,arcnum;//记录图的顶点数和弧数
      }OLGraph;
      int LocateVex(OLGraph * G,VertexType v){
         int i=0;
         //遍历一维数组，找到变量v
         for (; i<G->vexnum; i++) {
             if (G->xlist[i].data==v) {
                 break;
              }
          }
         //如果找不到，输出提示语句，返回 -1
         if (i>G->vexnum) {
             printf("no such vertex.\n");
             return -1;
          }
         return i;
      }
      //构建十字链表函数
      void CreateDG(OLGraph *G){
         //输入有向图的顶点数和弧数
         scanf("%d,%d",&(G->vexnum),&(G->arcnum));
         //使用一维数组存储顶点数据，初始化指针域为NULL
         for (int i=0; i<G->vexnum; i++) {
             scanf("%d",&(G->xlist[i].data));
              G->xlist[i].firstin=NULL;
              G->xlist[i].firstout=NULL;
          }
         //构建十字链表
         for (int k=0;k<G->arcnum; k++) {
             int v1,v2;
             scanf("%d,%d",&v1,&v2);
             //确定v1、v2在数组中的位置下标
             int i=LocateVex(G, v1);
             int j=LocateVex(G, v2);
             //建立弧的结点
              ArcBox * p=(ArcBox*)malloc(sizeof(ArcBox));
              p->tailvex=i;
              p->headvex=j;
             //采用头插法插入新的p结点
              p->hlik=G->xlist[j].firstin;
              p->tlink=G->xlist[i].firstout;
              G->xlist[j].firstin=G->xlist[i].firstout=p;
          }
      }
  
 

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

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