그래프에 대한 C 구조, 구조 이해에 도움이

Question

그래프로 표현하기 위해 C로 데이터 구조를 만들려고합니다.

http://pine.cs.yale.edu/pinewiki/C/Graphs

그것은 아주 좋은 출발점이 날 것으로 보인다 :이 매우 유용한 링크를 발견했다. 하지만 데이터 구조를 이해하는데 약간의 문제가 있습니다.

struct graph { 
    int n;    /* number of vertices */ 
    int m;    /* number of edges */ 
    struct successors { 
     int d;   /* number of successors */ 
     int len;  /* number of slots in array */ 
     char is_sorted; /* true if list is already sorted */ 
     int list[1]; /* actual list of successors */ 
    } *alist[1]; 
}; 

은 이런 식으로하고 있지으로 구조체의 후임자가 선언 된 이유를 이해할 수없는

:

struct graph { 
    int n;    /* number of vertices */ 
    int m;    /* number of edges */ 
    struct successors { 
     int d;   /* number of successors */ 
     int len;  /* number of slots in array */ 
     char is_sorted; /* true if list is already sorted */ 
     int *list; /* actual list of successors */ 
    } *alist; 
}; 

나는 그래프 만들기 위해 필연의 기능에서 볼 수 있듯이 :

을

Graph 
graph_create(int n) 
{ 
    Graph g; 
    int i; 

    g = malloc(sizeof(struct graph) + sizeof(struct successors *) * (n-1)); 
    assert(g); 

    g->n = n; 
    g->m = 0; 

    for(i = 0; i < n; i++) { 
     g->alist[i] = malloc(sizeof(struct successors)); 
     assert(g->alist[i]); 

     g->alist[i]->d = 0; 
     g->alist[i]->len = 1; 
     g->alist[i]->is_sorted= 1; 
    } 

    return g; 
} 

그것은 alist에 대해 더 많은 공백을 할당하고 왜 alist [1]로 선언하는지 이해할 수 없습니다. 어떻게 작동하는지 설명해 주시겠습니까?

나는 혼란 스럽기 때문에 질문이 분명하기를 바랍니다.

Answer 1

struct successors { 
    /* 
    */ 
    int list[1]; /* actual list of successors */ 
} *alist[1]; 

이중 간접 사용 (각 포인터 OP */& 첨자 연산자 [] 간접 레벨은 및 추가 메모리 액세스 요구) malloc D '로 각각의 인덱스를 사용하도록 alist 부재에있다.

struct successors { 
    /* 
    */ 
    int *list; /* actual list of successors */ 
} *alist; 

아니요. 귀하의 링크에서 또한

: 링크 코드를 꽤 많이 가지고

/* basic directed graph type */ 
typedef struct graph *Graph; 

.

->list이 사용 된 방법을 완전히 이해하지 못했지만 원래 방법은 int *의 공간 만 예약하고 원래는 포인터와 대상을 모두 예약합니다 int.

는

g = malloc(sizeof(struct graph) + sizeof(struct successors *) * (n-1)); 

의 할당은 allocs successors *successors는 각각의 객체는 (이론)보다 조잡 int 년대 가리 키도록 확장 될 수있다.