删除单向链表的列表

Question

我正在练习数据结构，我已经实现了一个创建单链表、添加到列表和删除列表的代码。我真的很想知道我的删除列表功能是否真的在做它应该做的事情。我认为这是因为当我尝试在删除后打印列表时它崩溃了。因此，关于确保删除我的列表的任何建议或关于改进我的代码的任何其他建议。说到动态分配内存，我还是有点菜鸟。

typedef struct node {
    int data;
    node* next;
}* nodePtr;

nodePtr addToList(nodePtr head, int data) {
    nodePtr newItem = new node; //create a new item 

    newItem->data = data; //assign the data to the new item 
    newItem->next = head; //point to head

    return newItem; //return the new head
}

void deleteList(nodePtr head) {
    if (head == nullptr) {
        return;
    }
    else {
        deleteList(head->next);
        delete head;
        head = nullptr;
    }
}

void Print(nodePtr n) {
    while (n != nullptr) {
        cout << n->data << " ";
        n = n->next;
    }
}

int main() {
    nodePtr head = new node;
    nodePtr second = new node;
    nodePtr third = new node;

    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = nullptr;

    Print(head);
    cout << endl;

    head = addToList(head, 0);

    Print(head);
    cout << endl;

    deleteList(head);

    return 0;
}

Answer 1

当你打电话时：

deleteList(head);

head 在该语句之后将不等于 NULL。相反，您需要执行以下操作：

deleteList(head);
head = NULL;

或：

void deleteList(nodePtr & head) {
    if (head == nullptr) {
        return;
    }
    else {
        deleteList(head->next);
        delete head;
        head = nullptr;
    }
}

请注意，我们为 deleteList 使用了一个引用参数。

Answer 2

除了 Bill 的回答中指出的一个小警告外，您的函数大部分都是正确的。

我只是想指出您并不真的需要递归来删除列表。这是另一种方法。

while(head != nullptr) {
    node *deleteMe = head;
    head = head->next;
    delete deleteMe;
}

Answer 3

我会添加这样的东西来清理代码：

nodePtr create_node(int n) {
   nodePtr p = new node;
   assert (p != NULL);
   p -> data = n;
   p -> next = NULL;
}

这样，您可以使用如下循环来清理用于测试的主要函数：

for (int i = 0; i < 10; ++i) {
   nodePtr p = create_node(i);
   head = addToList(head, p);
}

然后通过引用传递你的头指针，所以你最终会得到这样的东西：

nodePtr addToList(nodePtr&head, nodePtr newItem) {
    newItem->next = head; //point to head
    head = newItem;
}

这些几乎只是样式更改，但它可以更轻松地测试您的程序，而不是在您的主函数中单独创建节点，并且它使代码看起来更清晰一些。您可以做的另一件事是首先尝试迭代删除此列表，一旦您实现递归删除可能更有意义。

要实际调试它并检查您是否正确地释放内存，最好的方法是使用调试器，您可以添加 assert() 来验证空值，但值得检查 gdb 之类的东西（用于命令线）： https://www.cs.cmu.edu/~gilpin/tutorial/。该教程实际上用于调试链表的内存分配，因此可能会有所帮助。

删除单向链表的列表

Delete list of Singly linked list

c++

singly-linked-list