0

我正在尝试为有序链表编写删除算法。搜索和遍历我认为我已经失败但删除让我很适应。每次都会崩溃。有人可以帮我解决这个问题吗？

我有一个指向我的类中ListNode调用的结构的私有指针。该结构包含、和。如果找到并删除了要删除的节点，或者没有找到，该函数返回。headTestLLListNodeint Keydouble dataValueListNode *nexttruefalse

我的代码：

bool TestLL::Delete(int Key)
{
    ListNode *back = NULL, *temp = head;
    //Search for the node to delete
    while ((temp != NULL) && (key != temp -> key))
        //advance the pointers
        back = temp;
        temp = temp->next;
    }

    //Check for node to delete not being found
    if (temp == NULL)
    {
        return false;
    }
    //Check for deleting the head of the list
    else if (back == NULL) // I'm very unsure of my else if and else
    {
        delete temp;
    }
    else // Remove node other than at the head
    {
        delete temp;
    }

    //deallocate memory used by the removed node
    free(temp);
    return true;
}
4

2 回答 2

0

在同一个指针上同时使用delete和使用free绝对是一个问题。

  • 如果您用于new分配内存，请使用delete
  • 如果您使用过malloc，请提醒自己您正在使用 C++ 并将其替换为new.

如果back == NULL，这意味着：

  • head是NULL（在这种情况下，只是return false）或
  • 第一个元素是我们要删除的元素（在这种情况下，您需要head从列表中删除元素，即head = head->next; delete temp;）

如果temp == NULL，这意味着未找到该元素 - 您正确地只是return false在这里。

如果temp != NULL，则需要删除temp: back->next = temp->next; delete temp;。

但仅使用指向指针的指针似乎更简单：

bool TestLL::deleteKey(int key)
{
    ListNode **current = &head;
    while (*current != NULL)
    {
        if ((*current)->key == key)
        {
            ListNode *temp = *current;
            *current = (*current)->next;
            delete temp;
            return true;
        }
        current = &(*current)->next;
    }
    return false;
}
于 2013-10-19T16:52:06.417 回答
0

例如，该功能可能看起来像以下方式（未经测试）

bool TestLL::Delete( int key )
{
    ListNode *prev = nullptr, *current = head;

    while ( current && !( current->key == key ) )
    {
        prev = current;
        current = current->next;
    }

    if ( !current ) return false;

    if ( prev ) prev->next = current->next;
    else head = head->next;

    delete current;

    return true;
}
于 2013-10-19T13:24:58.917 回答