释放链接列表中的上一个节点

Question

我编写了一个遍历链表的函数，找到“int frequency”值最小的节点，并在遍历整个列表后删除该节点。我的错误来自节点：'prev'。当我运行代码时，我得到一个错误说：“prev是一个空指针”。但是，如果我从节点声明中删除'= NULL'部分，我会收到一个编译错误：“prev is uninitialized”。

这是因为我需要为列表中的一个现有节点分配/指向prev吗？如果是这样，我怎么指向我要删除的节点之前的节点？ （我认为这是按照我的代码中的方式完成的，但显然不是。）

结构定义：

struct LetterFrequencyPair
{
    char character;
    int frequency;
    //Creating a pointer to point to the next child in the list
    struct BinaryTreeNode* next;
};

struct BinaryTreeNode
{
    //create a pointer to point to the LetterFrequencyPair
    struct LetterFrequencyPair* letter_frequency_pair;
    //create pointers to the children of the node
    struct BinaryTreeNode* leftChild;
    struct BinaryTreeNode* rightChild;
};

---

struct BinaryTreeNode* ret_lowestF()
{
    int val = 1000;
    struct LetterFrequencyPair* temp;
    struct LetterFrequencyPair* temp1 = NULL;
    struct LetterFrequencyPair* prev = NULL;
    struct LetterFrequencyPair* low = malloc(sizeof(struct 
    LetterFrequencyPair));

    struct BinaryTreeNode* lowest = malloc(sizeof(struct BinaryTreeNode));
    temp = root;
    if (temp == NULL)
    {
        printf("List is empty.\n");
    }
    else
    {
        while (temp != NULL)
        {
            printf("%c\t%d\n", temp->character, temp->frequency);

            if (val >> temp->frequency)
            {
                low = temp;
                lowest->letter_frequency_pair = low;
                val = low->frequency;
                temp1 = temp;
                prev->next = temp1;
            }

            temp = temp->next;
        }
    }
    prev->next = temp1->next;
    temp1->next = NULL;
    free(temp1);

    printf("lowest frequency node is: %c\t%d\n", low->character, low- 
            >frequency);

    return lowest;
}

Answer 1

当我运行代码时，我得到一个错误说：“prev是一个空指针”。但是，如果我从节点声明中删除'= NULL'部分，我会收到一个编译错误：“prev is uninitialized”。

嗯，是。虽然在几个地方你尝试分配给prev->next，但你没有在任何地方分配给prev本身，除非你想要计算它的初始值。当该变量是NULL时，或者它根本没有定义的值时，它不指向任何对象。在这种情况下，没有prev->next。

看起来您想使用prev来跟踪当前最小值之前的节点。当列表的头节点是当前最小值时，这会产生一些问题。在这种情况下，可以通过将prev设置为NULL并为该特殊情况编写额外的代码来解决这个问题，但通过引入人工的前任来回避这个问题会更容易和更清晰：

struct LetterFrequencyPair head = { .next = root };
struct LetterFrequencyPair *prev = &head;

请注意，无需动态分配头节点。就此而言，您不需要任何动态分配。目前，您的代码泄漏了它为low最初指向的内存泄漏，而lowest的分配和释放原始最低节点是浪费的。

您最终删除的节点可能会成为第一个节点。您在删除时不需要特殊处理;在这种情况下，head.next被设置（通过prev）指向新的第一个节点。但是，最后，您需要将其复制出来：

root = head.next;

如果第一个节点不是已删除的节点，则该分配没有净效果。

您的代码还有很多其他问题，超出了问题的范围，但这应该可以帮助您入门。