c - 从图创建邻接表的两种实现

Question

对于以下图形声明(我无法更改 - 赋值；也存在宏，因为我不允许对图形使用“.”和“->”运算符)

#include <string.h>
#include <stdlib.h>
#define TAG(vp)   ((vp)->tag)
#define LABEL(vp) ((vp)->label)  
#define EDGE(vp)  ((vp)->edge)

typedef struct vertex 
{
    char tag;
    char *label;
    struct vertex *edge[1];
}
vertex, *vp;

以及这个邻接列表的声明(对于这个和所有下一个代码我可以做任何我想做的事情)

typedef struct adjList
{
    vp node;
    struct adjList *next;
}
adjList;

我编写了两个版本的函数，该函数必须从图创建邻接列表表示。他们都使用这个函数来创建一个列表。

adjList *createList (vp graph)
{
    int i;
    adjList *result, *ptr, *ptr2;
    if (graph)
    {
        result = malloc (sizeof (adjList));
        result->node = graph;
        ptr2 = result;
        for (i = 0; EDGE (graph)[i]; ++i)
        {
            ptr = malloc (sizeof (adjList));
            ptr->node = EDGE (graph)[i];
            ptr2->next = ptr;
            ptr2 = ptr;
        }
        ptr2->next = NULL;
    }
    return result;
}

第一个返回邻接列表数组(作为双指针)，但仅对一个节点及其子节点执行此操作(我还没有弄清楚如何使用此工作函数返回完整表示)

adjList **createLists (vp graph)
{
    int i;
    adjList **result;
    result = malloc (sizeof (adjList *));
    result[0] = createList (graph);
    for (i = 0; EDGE (graph)[i]; ++i)
    {
        result = realloc (result, sizeof (adjList *) * (i + 2));
        result[i + 1] = createList (EDGE (graph)[i]);
    }
    result = realloc (result, sizeof (adjList *) * (i + 2));
    result[i + 1] = NULL;
    return result;
}

第二个会产生段错误。基本上，它创建了一个空列表数组，但使用这个逻辑我将创建完整的表示。

void createListsHelper (adjList **result, vp graph, int *index) /* index stores an index in an array to create there next list */
{
    int i;
    if (graph)
    {
        result = realloc (result, sizeof (adjList *) * (*index + 2));
        result[*index] = createList (graph);
        for (i = 0; EDGE (graph)[i]; ++i)
        {
            ++(*index);
            createListsHelper (result, EDGE (graph)[i], index);
        }
    }
}

adjList **createLists (vp graph)
{
    adjList **result = malloc (sizeof (adjList *));
    int *index = malloc (sizeof (int));
    *index = 0;
    createListsHelper (result, graph, index);
    result[*index + 1] = NULL;
    return result;
}

我怎样才能改变其中一个，以便它们能够正常工作。

提前致谢。

注意:我使用以下“main”来测试它们。

int main()
{
    int i;
    adjList **list, *ptr;
    vp test;
    test = malloc (sizeof (vertex) + 4 * sizeof (vp));
    LABEL (test) = malloc (sizeof (char) * 2);
    LABEL (test)[0] = 'a';
    LABEL (test)[1] = '\0';
    for (i = 0; i < 3; ++i)
    {
        EDGE (test)[i] = malloc (sizeof (vertex));
    }
    LABEL (EDGE (test)[0]) = malloc (sizeof (char) * 2);
    LABEL (EDGE (test)[0])[0] = 'b';
    LABEL (EDGE (test)[0])[1] = '\0';
    LABEL (EDGE (test)[1]) = malloc (sizeof (char) * 2);
    LABEL (EDGE (test)[1])[0] = 'c';
    LABEL (EDGE (test)[1])[1] = '\0';
    LABEL (EDGE (test)[2]) = malloc (sizeof (char) * 2);
    LABEL (EDGE (test)[2])[0] = 'd';
    LABEL (EDGE (test)[2])[1] = '\0';
    EDGE (test)[3] = NULL;
    EDGE (EDGE (test)[0])[0] = NULL;
    EDGE (EDGE (test)[1])[0] = NULL;
    EDGE (EDGE (test)[2])[0] = NULL;
    list = createLists2 (test);
    for (i = 0; list[i]; ++i)
    {
        for (ptr = list[i]; ptr; ptr = ptr->next)
        {
            printf ("%c ", LABEL (ptr->node)[0]);
        }
        printf ("\n");
    }
    return 0;
}

Answer 1

void createListsHelper (adjList **result, vp graph, int *index) /* index stores an index in an array to create there next list */
{
    int i;
    if (graph)
    {
        result = realloc (result, sizeof (adjList *) * (*index + 2));

由于 result 是按值传递的(每个参数在 C 中都是按值传递的)，因此此修改不会影响调用中的 result功能。这一行

createListsHelper (result, graph, index);
result[*index + 1] = NULL; /* <<< */

调用 UB(因为 result 仍然指向 1 int 的数组，并且您正在访问第二个元素)。