如何从链表中删除一个节点

Question

我希望对两个节点执行二进制操作，将结果存储在一个节点中并消除另一个节点。这是我的代码：

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <math.h>

    struct n{
        double value;
        char op;
        struct n *next;
    };

    void delete(struct n *head);
    void add_item(struct n **ptr, double *data);

    int main(){
        struct n *head = NULL;
        double result;
        add_item(&head, 5);
        add_item(&head, 3);
        head->op = '*';
        result = (head->next)->value * head->value;
        (head->next)->value = result;
        delete(head);
        printf("%lf\n",head->value);
        free(head); 
        return 0;        
    }

    void add_item(struct n **ptr, double *data)
    {
            struct n *item = malloc(sizeof *item);

            item->value = *data;
            item->next = *ptr;
            item->op = '?';
            *ptr = item;
    }

    void delete(struct n *head)
    {
        struct n *temp;
        temp = head->next;
        head->next = temp->next;
        free(temp);
    }

在这个例子中，我有一个像这样的列表3 -> 5 -> NUll。我想得到这个15 -> NUll。当我尝试打印剩余节点的值时，我得到的是3而不是15。

- Michaelangelo Meucci

---

你展示的代码接近于一个[mcve]，但还不够接近。head是什么？你包含了哪些头文件？ - Some programmer dude

想一想，当你直接执行(head->next)->value = result;，然后紧接着执行delete(head)时会发生什么，这将无条件删除列表中的第二个节点。 - Some programmer dude

我解决你的问题的方法是创建一个函数，它可以从列表中移除（但不删除）“头”节点，并返回它。然后，您可以两次删除头以获取它们的值，执行所需的操作，并添加一个新节点以显示结果。将列表视为堆栈（具有推入和弹出操作）。 - Some programmer dude

你的“删除”操作没有更改头节点的值。它仍然指向你打算删除的相同元素。 - William Pursell

很确定你的意思是 void delete(struct n **head) {struct n *tmp; tmp=(*head)->next; free(*head) ;*head=tmp;}。 - William Pursell

@WilliamPursell 我忘了 head->next = temp->next; 但是我真的释放了第二个节点占用的位置吗？我的意思是有没有一种方法可以丢弃它所有的内容？ - Michaelangelo Meucci

Answer 1

这两个函数都是无效的。

对于函数add_item，您没有通过引用传递数据（而且通过引用传递数据也没有意义）。

    add_item(&head, 5);
    add_item(&head, 3);

因此，该函数应该被声明和定义如下：

void add_item(struct n **ptr, double data)
{
        struct n *item = malloc(sizeof *item);

        item->value = data;
        item->next = *ptr;
        item->op = '?';
        *ptr = item;
}

你需要通过引用将头节点传递给delete函数。

void delete(struct n **head)
{
    if ( *head )
    {
        struct n *temp = *head;
        *head = ( *head )->next;
        free( temp );
    }
}

然后像这样调用

delete( &head );

当我尝试打印剩余节点的值时，结果是3而不是15。

这是因为你删除了头结点之后的节点，而不是删除头结点，即使你在头结点之后的节点中写入了操作的结果。

(head->next)->value = result;

这是您更新后的程序。

#include <stdio.h>
#include <stdlib.h>

    struct n{
        double value;
        char op;
        struct n *next;
    };

    void delete(struct n **head);
    void add_item(struct n **ptr, double data);

    int main(){
        struct n *head = NULL;
        double result;
        add_item(&head, 5);
        add_item(&head, 3);
        head->op = '*';
        result = (head->next)->value * head->value;
        (head->next)->value = result;
        delete(&head);
        printf("%lf\n",head->value);
        free(head); 
        return 0;        
    }

void add_item(struct n **ptr, double data)
{
        struct n *item = malloc(sizeof *item);

        item->value = data;
        item->next = *ptr;
        item->op = '?';
        *ptr = item;
}

void delete(struct n **head)
{
    if ( *head )
    {
        struct n *temp = *head;
        *head = ( *head )->next;
        free( temp );
    }
}

它的输出为

15.000000

- Vlad from Moscow

---

我得到了“错误：无效的初始化器结构n temp = *head;” - Michaelangelo Meucci

@MichaelangeloMeucci，你按照我展示的方式传递了头指针并声明了参数为struct n **head吗？请确认是否已经成功删除。 - Vlad from Moscow

@MichaelangeloMeucci 噢，对不起。有一个打字错误。函数内应该是 struct n *temp = *head;。 - Vlad from Moscow

我得到了 free(): double free detected in tcache 2。 - Michaelangelo Meucci

@MichaelangeloMeucci 显示所有在主函数中调用 delete 和 free 的语句。 - Vlad from Moscow

@MichaelangeloMeucci 你能否只是复制粘贴我展示的代码，还是这太难了？ - Vlad from Moscow

Answer 2

通常情况下，与 C 语言类似，如果一个函数要有能力通过参数列表修改传递给它的对象，必须传递该对象的地址，而不是对象本身。（在此阅读更多信息）

在这个例子中，如果要更改对象 "head"，则需要将其 &head 的地址而不是对象本身传递给函数。因此，以下声明：

delete(head); //passing the object will not allow it to be changed

应该更改为

delete(&head); //The object's address is passed, allowing the object to be changed

由于传递的对象被创建为指针：struct n *head = NULL;，因此delete函数的原型需要在其参数中容纳指针的地址。这可以通过指向指针的指针来实现：

void delete(struct n **head);//accommodates the address of a pointer object

然后，在delete函数内部，处理对象本身（现在是*head）以进行更改。

   void delete(struct n **head)
    {
        if (*head == NULL) return;
        struct n *temp = *head;
        *head = temp->next;//point head to next node
        free(temp);//free old head
    }

相反，对于你的void add_item(struct n **ptr, double *data);函数，data不需要被改变，只需在函数体内使用。实际上，在你的代码中调用它的方式是正确的，并无需更改数据：

add_item(&head, 5);  // 2nd argument passes object directly, i.e. not an address

因此，由于该函数需要数据本身而不是指向数据的指针，请更改原型以适应：

void add_item(struct n **ptr, double data);

根据需求修改代码主体内的代码。

- ryyker