c - 如何正确添加到链表数组？

Question

我正在制作一个由链表实现的图表，我发现自己有点困惑，因为我确信我没有正确遍历链表。

// A structure to represent an adjacency list node
typedef struct AdjListNode
{
    char data;
    int distance;
    struct AdjListNode* next;
} AdjListNode;

// A structure to represent an adjacency list
typedef struct AdjList
{
    char data;
    struct AdjListNode* head;  // pointer to head node of list
} AdjList;

// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be the number of vertices in graph.
typedef struct Graph
{
    int NumberOfNodes;
    struct AdjList* array;
} Graph;

所以我正在制作一个包含数组的图表，数组的每个元素都指向一个链接列表。

但是，当我尝试输出所有元素时，它只打印紧邻头部的元素，例如:

A->B5
B->E6
C->A8
D->C2
E->D7

所以将它们添加到链接列表时出现错误，因为它应该是

A->B5->D5-C7
B->E6->E4
C->A8
D->C2->B6->A2
E->D7

这是函数的一个片段，它将节点添加到图表中，我相信 else 语句有错误

    for(i =0; i < G->NumberOfNodes ; i++)
    {
        if(G->array[i].data == from)
        { // if the letter from the primary array matches the letter that needs to be added to
            if(G->array[i].head == NULL)
            { // if the head node of the linked list is empty simply just and the element there
                G->array[i].head = malloc(sizeof(AdjListNode));
                G->array[i].head->data = to;
                G->array[i].head->distance = number;
                G->array[i].head->next = NULL;
            }
            else
            {    // if the head is not empty then this will find another position for it
                AdjListNode* looker;

                looker = G->array[i].head;

                while(looker != NULL)
                {
                    looker = looker->next; // pointing to the next position
                }

                looker = malloc(sizeof(AdjListNode)); // placing the element on that position
                looker->data = to;
                looker->distance = number;
                looker->next = NULL;

                free(looker);
            }
        }
    }

Answer 1

这是错误的:

AdjListNode* looker;
looker = G->array[i].head;
while(looker != NULL){
    looker = looker->next; // pointing to the next position
}

looker = malloc(sizeof(AdjListNode)); // placing the element on that position
looker->data = to;
looker->distance = number;
looker->next = NULL;
free(looker);

它绝对不会改变 G->array[i].head 引用的链表。它将指针移动到链表的末尾(最多有一个节点)。然后它什么也不做(怎么可能？你所拥有的只是一个指向任何东西的指针)，然后简单地分配一些内存，设置节点，然后立即释放它。

如果你想链接到链表的尾部，你必须通过找到链表中的最后一个指针来实现。一种方法是使用双指针，作为额外的好处，它也可以减轻特殊的空头情况。您的整个 for 循环至少看起来是可行的:

for(i =0; i < G->NumberOfNodes ; i++)
{
    if(G->array[i].data == from)
    {
        AdjListNode** pp = &(G->array[i].head);
        while (*pp)
            pp = &(*pp)->next;

        *pp = malloc(sizeof(**pp));
        (*pp)->data = to;
        (*pp)->distance = number;
        (*pp)->next = NULL;
    }
}

在进入此弹幕之前，每个槽中的 head 指针为 NULL 是关键，希望原因显而易见。

祝你好运。