为链表类型数据结构实现"deleting algorithm"

Question

这是我编写的删除函数，用于在需要时从我的链表中删除一些节点。

链表按字母顺序存储

使用下面的函数，当我尝试删除链表的第一个元素（名为 head）时，当我尝试打印链表（使用 print 函数）和程序时出现运行时错误崩溃。我知道这可能是由于没有创建新的头节点造成的。但我不知道如何解决这个问题。这可能很简单，但无法弄清楚。你能帮忙吗:)

这是删除函数：

 void deleteName(someStruct * &head, string name)
{
    someStruct * ptr = head;
    someStruct * previous;

    if(head == NULL)
    {
        cout << "empty";
    }
    else if(head->name == name)
    {
        ptr = head;
        head = head->next;
        delete head;
    }
    else
    {
        while (ptr -> name != name)
        {
            previous = ptr;
            ptr = ptr->next;
        }
        previous->next = ptr->next;
        delete ptr;
    }
}

这是打印函数：

void Print(someStruct * head)
{
    someStruct * pointer = head;
    //List is empty
    if(head == NULL)
    {
        cout << "List is empty" << endl;
    }
    else
    {
        while(pointer != NULL)
        {
            cout << pointer->name;
            cout << pointer->points << endl;
            pointer = pointer->next;
        }
    }
}

Answer 1

else if(head->name == name)
{
    ptr = head;
    head = head->next;
    delete head;
}

这个：

将head的旧值保存为ptr，是正确的
推进 inout 参数 head，这也是正确的
完全忽略ptr，其中包含要删除的旧节点，而是删除当前列表头，使inout参数head指向已删除的节点.

这个位不正确。

只需将 delete head 更改为 delete ptr。

注意以供将来参考：好的构造方法是使用不需要删除的本地哨兵节点。这删除了 head 的特殊情况（通过添加永远无法删除临时头部的不变量）并简化了代码。

void deleteName(someStruct * &head, string name)
{
    if(!head) {
        cout << "empty";
        return;
    }

    someStruct tmphead;
    tmphead.next = head;

    for (someStruct *prev = &tmphead; prev->next; prev = prev->next) {
        if (prev->next->name == name) {
            auto todelete = prev->next;
            prev->next = todelete->next;
            delete todelete;
            // if there can be only one match, just bail out
            break;
            // otherwise, if there can be many, go round again
            // but remember to check whether prev->next is null
            // if (!prev->next) break;
        }
    }

    head = tmphead.next;
}

如果您的 someStruct 太大或太复杂而无法使用这样的临时头，您可以对临时本地头指针执行相同操作，并使 prev 成为指向指针的指针.

Answer 2

else if 块中的 delete head 是问题所在。

将块更改为此：

else if(head->name == name) {
    //ptr = head; You don't have to. You already have initialized ptr with head
    head = head->next;
    delete ptr; //Delete prt not head, head is now the next node which you assigned in previous line
}

Answer 3

else if(head->name == name){
   ptr = head;
   head = head -> next;
   delete ptr;  // change to this statement n you're good to go
}

为链表类型数据结构实现"deleting algorithm"

Implementing "deleting algorithm" for linked list type data structures

c++

algorithm

linked-list

delete-operator

singly-linked-list