[已解决]关于图的十字链表存储

hhhh还好还好

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



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


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


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

int LocalVex(int data,Graph* G){
    for(int i=0;i<G->vexnums;i++){  
        if(G->List[i].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[i].data);
        //初始化in和out指针
        G->List[i].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[j].firIn;       //就是从这里开始的4条代码，我照着代码画了图，感觉是类似双向链表的结构，我仔细想了好久也没懂为什么要这样做，而且画到后面发现无法结束，也就是到后面没有任何一个节点的指针域是指向NULL的。
        A->tLink = G->List[k].firOut;
        G->List[k].firOut = A;
        G->List[j].firIn = A;
    }
}

最佳答案

月排行榜 / 总排行榜

claws0n

2018-8-22 12:49:04

没问题吗？怪怪的

1. typedef struct VexNode
   
2. {
   
3.     int data;
   
4.     ArcBox *firIn;
   
5.     ArcBox *firOut;
   
6. }VexNode;
   
7. 
   
8. typedef struct ArcBox
   
9. {
   
10.     int headVex,tailVex;
    
11.     ArcBox *hLink,*tLink; // *hLink;*tLink;
    
12. }ArcBox;
    
13. 
    
14. typedef struct
    
15. {
    
16.     VexNode List[100];
    
17.     int vexnums, arcnums;
    
18. }Graph;
    
19. 
    
20. int LocalVex(int data, Graph* G)
    
21. {
    
22.     for(int i = 0; i < G->vexnums; i++)
    
23.         {  
    
24.         if(G->List[i].data == data)
    
25.             return i;  
    
26.     }  
    
27.     return -1;  
    
28. }
    
29. 
    
30. void create(Graph* G)
    
31. {
    
32.     int x, y, i;  // i
    
33.     printf("请输入顶点的个数的边的数量:");
    
34.     scanf("%d %d", &G->vexnums, &G->arcnums);
    
35. 
    
36.     for(i = 0; i < G->vexnums; i++)    // 保留 C 的方法
    
37.     {
    
38.         printf("输入顶点，建立顶点表:");
    
39.         //建立顶点表
    
40.         scanf("%d", &G->List[i].data);
    
41.         //初始化in和out指针
    
42.         G->List[i]->firIn = G->List->firOut = NULL;
    
43.     }
    
44. 
    
45. //    int x, y;  // 重复声明
    
46.     for(i = 0; i < G->arcnums; i++)
    
47.     {
    
48.         printf("读入(vi-vj):");
    
49.         scanf("%d %d",&x, &y);
    
50.         ArcBox *A = (ArcBox)malloc(sizeof(ArcBox));
    
51.         int k, j;
    
52.         k = LocalVex(x, G);//k是弧尾的位置
    
53.         j = LocalVex(y, G);//j是弧头的位置
    
54. 
    
55.         A->headVex = j;
    
56.         A->tailVex = k;
    
57.         A->hLink = G->List[j].firIn;
    
58.         A->tLink = G->List[k].firOut;
    
59.         G->List[k].firOut = A;
    
60.         G->List[j].firIn = A;
    
61.     }
    
62. }

复制代码

跳转到最佳答案楼层

claws0n

没问题吗？怪怪的

1. typedef struct VexNode
   
2. {
   
3.     int data;
   
4.     ArcBox *firIn;
   
5.     ArcBox *firOut;
   
6. }VexNode;
   
7. 
   
8. typedef struct ArcBox
   
9. {
   
10.     int headVex,tailVex;
    
11.     ArcBox *hLink,*tLink; // *hLink;*tLink;
    
12. }ArcBox;
    
13. 
    
14. typedef struct
    
15. {
    
16.     VexNode List[100];
    
17.     int vexnums, arcnums;
    
18. }Graph;
    
19. 
    
20. int LocalVex(int data, Graph* G)
    
21. {
    
22.     for(int i = 0; i < G->vexnums; i++)
    
23.         {  
    
24.         if(G->List[i].data == data)
    
25.             return i;  
    
26.     }  
    
27.     return -1;  
    
28. }
    
29. 
    
30. void create(Graph* G)
    
31. {
    
32.     int x, y, i;  // i
    
33.     printf("请输入顶点的个数的边的数量:");
    
34.     scanf("%d %d", &G->vexnums, &G->arcnums);
    
35. 
    
36.     for(i = 0; i < G->vexnums; i++)    // 保留 C 的方法
    
37.     {
    
38.         printf("输入顶点，建立顶点表:");
    
39.         //建立顶点表
    
40.         scanf("%d", &G->List[i].data);
    
41.         //初始化in和out指针
    
42.         G->List[i]->firIn = G->List->firOut = NULL;
    
43.     }
    
44. 
    
45. //    int x, y;  // 重复声明
    
46.     for(i = 0; i < G->arcnums; i++)
    
47.     {
    
48.         printf("读入(vi-vj):");
    
49.         scanf("%d %d",&x, &y);
    
50.         ArcBox *A = (ArcBox)malloc(sizeof(ArcBox));
    
51.         int k, j;
    
52.         k = LocalVex(x, G);//k是弧尾的位置
    
53.         j = LocalVex(y, G);//j是弧头的位置
    
54. 
    
55.         A->headVex = j;
    
56.         A->tailVex = k;
    
57.         A->hLink = G->List[j].firIn;
    
58.         A->tLink = G->List[k].firOut;
    
59.         G->List[k].firOut = A;
    
60.         G->List[j].firIn = A;
    
61.     }
    
62. }

复制代码

hhhh还好还好

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

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