论坛 › 萌新交流区 › 关于图的十字链表存储

hhhh还好还好 发表于 2018-8-22 01:53:46

关于图的十字链表存储

以下是一个图的十字链表的创建代码，代码是我网上拷贝的，是正确的。我的疑问在于十字链表的链接方法，照着这个代码画了好几遍图也没懂，感觉自己思路很混乱。求大佬们详细的讲解。（问题在代码中有注释）



typedef struct VexNode{
    int data;
    ArcBox *firIn;
    ArcBox *firOut;
}VexNode;


typedef struct ArcBox{
    int headVex,tailVex;
    ArcBox *hLink;*tLink;
}ArcBox;


typedef struct{
    VexNode List;
    int vexnums,arcnums;
}Graph;

int LocalVex(int data,Graph* G){
    for(int i=0;i<G->vexnums;i++){
      if(G->List.data==data)
            return i;
    }
    return -1;
}


void create(Graph* G)
{
    int x,y;
    printf("请输入顶点的个数的边的数量:");
    scanf("%d%d",&G->vexnums,&G->arcnums);

    for(int i = 0;i<G->vexnums;i++)
    {
      printf("输入顶点，建立顶点表:");
      //建立顶点表
      scanf("%d",&G->List.data);
      //初始化in和out指针
      G->List.firIn=G->List.firOut=NULL;
    }

    int x,y;
    for(int i=0;i<G->arcnums;i++)
    {
      printf("读入(vi-vj):");
      scanf("%d%d",&x,&y);
      ArcBox *A = (ArcBox)malloc(sizeof(ArcBox));
      int k,j;
      k = LocalVex(x,G);//k是弧尾的位置
      j = LocalVex(y,G);//j是弧头的位置

      A->headVex = j;
      A->tailVex = k;
      A->hLink = G->List.firIn;       //就是从这里开始的4条代码，我照着代码画了图，感觉是类似双向链表的结构，我仔细想了好久也没懂为什么要这样做，而且画到后面发现无法结束，也就是到后面没有任何一个节点的指针域是指向NULL的。
      A->tLink = G->List.firOut;
      G->List.firOut = A;
      G->List.firIn = A;
    }
}

claws0n 发表于 2018-8-22 12:49:04

本帖最后由 claws0n 于 2018-8-22 12:50 编辑

没问题吗？怪怪的
typedef struct VexNode
{
    int data;
    ArcBox *firIn;
    ArcBox *firOut;
}VexNode;

typedef struct ArcBox
{
    int headVex,tailVex;
    ArcBox *hLink,*tLink; // *hLink;*tLink;
}ArcBox;

typedef struct
{
    VexNode List;
    int vexnums, arcnums;
}Graph;

int LocalVex(int data, Graph* G)
{
    for(int i = 0; i < G->vexnums; i++)
        {
      if(G->List.data == data)
            return i;
    }
    return -1;
}

void create(Graph* G)
{
    int x, y, i;// i
    printf("请输入顶点的个数的边的数量:");
    scanf("%d %d", &G->vexnums, &G->arcnums);

    for(i = 0; i < G->vexnums; i++)    // 保留 C 的方法
    {
      printf("输入顶点，建立顶点表:");
      //建立顶点表
      scanf("%d", &G->List.data);
      //初始化in和out指针
      G->List->firIn = G->List->firOut = NULL;
    }

//    int x, y;// 重复声明
    for(i = 0; i < G->arcnums; i++)
    {
      printf("读入(vi-vj):");
      scanf("%d %d",&x, &y);
      ArcBox *A = (ArcBox)malloc(sizeof(ArcBox));
      int k, j;
      k = LocalVex(x, G);//k是弧尾的位置
      j = LocalVex(y, G);//j是弧头的位置

      A->headVex = j;
      A->tailVex = k;
      A->hLink = G->List.firIn;
        A->tLink = G->List.firOut;
      G->List.firOut = A;
      G->List.firIn = A;
    }
}

hhhh还好还好 发表于 2018-8-22 22:02:06

claws0n 发表于 2018-8-22 12:49
没问题吗？怪怪的

打扰了，我有东西看错了，自己的一个小疏忽。。。。。。。我就说怎么总也无法建立表呢。。。。。。

查看完整版本: 关于图的十字链表存储