使用 free 删除节点

Question

当我在 deleteAlternateNodes() 中使用 delete p 时，出现运行时错误。但是，当我使用 free(p) 时，代码工作正常。这是什么原因？

Node 包含数据和指向下一个节点的指针：

#include <iostream>
    
class Node {
public:
    int data;
    Node * next;
    
    Node(int data){
        this -> data = data;
        this -> next = NULL;
    }
    
    ~Node() {
        if(next) {
            delete next;
        }
    }
};

这是我遇到错误的函数。

void deleteAlternateNodes(Node *head) {
    //Write your code here
    Node *p =head;
    Node *q =NULL;
    if(p->next == NULL)
    {
        return;
    }
    while(p!=NULL)
    {
        q=p;
        p=p->next;
        q->next = p->next;
        
        free(p);
        p = q->next;
    }
}

Node* takeinput() {
    int data;
    cin >> data;
    Node *head = NULL, *tail = NULL;
    while(data != -1){
        Node *newNode = new Node(data);
        if(head == NULL) {
            head = newNode;
            tail = newNode;
        }
        else{
            tail -> next = newNode;
            tail = newNode;
        }
        cin >> data;
    }
    return head;
}

print()只是一个打印节点的函数。

int main() {
    Node *head = takeinput();
    deleteAlternateNodes(head);
    print(head);
    delete head;
    return 0;
}

请区分free()和delete。

Answer 1

如果内存是用 new 分配的，它必须用 delete 释放。这是语言的要求。使用 free() 在技术上是未定义的行为（即您的程序无效）。

通过使用 free()，您将其释放给错误的内存管理例程。

free() 明显缺失的副作用是它不调用析构函数。

这里发生了什么：

if(p->next == NULL)
{
    return;
}

如果你的列表是空的？

这行看起来很有趣：

 q->next = p->next;


  Before:

      p          q
     ########    ######## 
     # next # -> # next # ->  // null
     ########    ########  
                           
  After 
      p          q
     ########    ######## 
     # next # -> # next # -| 
     ######## |  ########  |
              |            |
              --------------

你应该列出三个项目。然后画出这条线对你的列表的作用。

这一行看起来也有问题：

 p = q->next;

Answer 2

你的代码有很多问题。

您的 deleteAlternateNodes() 函数完全损坏，并导致 未定义的行为 ，这就是您的代码崩溃的原因。

具体来说：

它不处理 head 对于空列表为 NULL 的情况。
在 while 循环中，当 p 到达列表中的最后一个节点时，循环将 p 设置为 NULL，然后立即尝试访问p->next.
当 delete'ing a Node 时，您不会先清除它的 next 指针。因此，当第一个循环迭代销毁列表中的第二个节点时，您的 ~Node() 析构函数 递归销毁列表中的所有剩余节点 ！但是您的循环不知道列表已被销毁，因此它会尝试继续访问现在已销毁的节点，因此会出现运行时错误。
switching to free() 出现来解决这个问题，因为free()不会调用~Node()析构函数，就像 delete 一样。但是，现在您引入了一种不同类型的 未定义行为 ，因为使用 new 创建的对象必须使用 delete 而不是 free() 来销毁。混合内存管理器是 未定义的行为——即，使用 new 和 free()，malloc() 和 delete，等等。

试试这个：

void deleteAlternateNodes(Node *head) {
    Node *p = head, *q;
    while ((p != NULL) && (p->next != NULL)) {
        q = p->next;
        p->next = q->next;
        q->next = NULL;
        delete q;
        p = p->next;
    }
}

Online Demo

话虽如此，我怎么强调都不过分地强调为什么递归地销毁是一个非常糟糕的想法。不仅是因为上面解释的问题，还因为如果列表中有很多节点，那么您可能会溢出调用堆栈，导致不同类型的崩溃。

在循环中销毁节点时，您确实需要迭代循环而不是递归循环。但是您不能在 ~Node() 析构函数本身内部实现迭代循环，因此您应该实现一个单独的 List class 来创建和销毁 Node 列表。然后它可以在销毁列表中的节点时使用迭代循环。

例如：

#include <iostream>
    
class Node {
public:
    int data;
    Node *next;
    
    Node(int data) : data(data), next(NULL) {}
};

class LinkedList {
private:
    Node *head, *tail;

public:
    LinkedList() : head(NULL), tail(NULL) {}

    // disabling these just for demonstration purposes,
    // but you really should implement them properly...
    LinkedList(const LinkedList&) = delete;
    LinkedList& operator=(const LinkedList&) = delete;
    //

    ~LinkedList() {
        Node *p = head, *n;
        while (p) {
            n = p->next;
            delete p;
            p = n;
        }
    }

    Node* add(int data) {
        Node *newNode = new Node(data);
        if (!head) {
            head = newNode;
        }
        if (tail) {
            tail->next = newNode;
        }
        tail = newNode;
        return newNode;
    }
    
    void print() const {
        // print the nodes as needed ...
    }

    void deleteAlternateNodes() {
        Node *p = head, *q;
        while ((p != NULL) && (p->next != NULL)) {
            q = p->next;
            p->next = q->next;
            if (tail == q) tail = p;
            delete q;
            p = p->next;
        }
    }
};

int main() {
    LinkedList ll;

    int data;
    while ((cin >> data) && (data != -1)) {
        ll.add(data);
    }

    ll.print();
    ll.deleteAlternateNodes();
    ll.print();

    return 0;
}

Online Demo

使用 free 删除节点

deleting node using free

c++

memory