正在从链接列表的中间删除c++

Question

我的链表中的RemoveMid函数有问题。。代码看起来不错，没有语法错误，但当我调用此函数时，程序停止工作。。我认为函数的逻辑有问题。我希望你能帮我改正。这是RemoveMid函数的实现

template<typename T>
bool LinkedList<T>::RemoveMid(T& target)
{
    Node<T> *current = new Node<T>;
    bool found = false;
    current = start;
    while(current != NULL && !found)
    {
        if(current->next->info == target)
            found = true;
        if(!found)
            current = current->next;
    }
    if(found)
    {
        Node<T> *Ptr;
        Ptr = current->next;
        current = current->next;
        delete Ptr;
        return true;
    }
    else
        cout<<"target not foundn";
}

Answer 1

我猜这是一个Singly Linked List（也就是说，它只向前），因为您没有Previous指针。考虑到这一点：

template<typename T> bool LinkedList<T>::Remove(T& target) // name changed as removing from anywhere in a linked list is effectively the same
{
    Node<T>* current = start; // your allocation caused a memory leak here
    Node<T>* previous = NULL;
    bool found = false;
    while(current != NULL)
    {
        if (current->info == target) // you should be looking at the current node, not the next node
        {
            found = true;
            break;
        }
        previous = current;
        current = current->next;
    }
    if (found)
    {
        if (previous == NULL)  // deleting head node
        {
            start = current->next;
        }
        else
        {
            previous->next = current->next;
        }
        delete current;
    }
    else
    {
        cout<<"target not foundn";
    }
    return found;
}

Answer 2

这是一个正常工作的版本（我认为；不过我还没有测试过，根据我的经验，未测试的软件有缺陷），它似乎与最初的意图相似（即，删除第一个元素时没有特殊情况）：

template<typename T>
bool LinkedList<T>::RemoveMid(T const& target)
{
    for (Node<T> **current(&this->start); *current; current = &(*current)->next) {
        if ((*current)->info == target) {
            std::auto_ptr<Node<T>> tmp(*current);
            *current = (*current)->next;
            return true;
        }
    }
    std::cout<<"target not foundn";
    return false;
}

Answer 3

这个代码有很多问题：

1. 您正在此处检查链接列表中的next节点if(current->next->info == target)，这将错过您的start节点
2. 将new Node<T>分配给current指针，然后在两行后将start重新分配给它
3. 然后，您错误地将next节点删除为使用Ptr = current->next;找到的节点，然后使用delete Ptr删除两行
4. 在分配给要删除的节点的行之间，有一个指向要delete的节点的指针

可能还有更多的错误，但修复所有这些都是一个良好的开端。

Answer 4

我想有几个地方我不了解

      Node<T> *current = new Node<T>;

为什么要将新节点分配给当前节点，因为无论如何都会将当前节点分配为启动节点？

其次，

    if(current->next->info == target)
        found = true;

为什么使用current->next而不是current？并且current->next可能为NULL，这使得current->next->info无效。

顺便说一句，你为什么不使用STL提供的链表呢？

Answer 5

关于您的错误：此分配current = current->next;应为current->next = current->next->next;，因为如果删除当前节点之后的节点，则希望当前节点（current->next）指向删除的节点（current->next->next）之后的节点

此外，代码可能存在一些问题。首先，如果仍然找不到节点，并且current->next是NULL（current指向最后一个元素），那么current->next->info将使程序崩溃，显然在这种情况下current->next->info是非法的。此外，您可能会考虑在cout 之后添加return false;

Answer 6

这里有一个更好的代码版本。更少的变量和所有。试试看它现在是否有效。：）

template<typename T>
bool LinkedList<T>::RemoveMid(T& target)
{
    Node<T> *current = new Node<T>;
    current = start;
    while(current != NULL)
    {
        if(current->next->info == target)
            break; //stops while loop = faster since the whole list doesnt have to be parsed once we found the target
        current = current->next;
    }
    if(current!=NULL)
    {
        current->next = current->next->next; //we "unlinked" target from the list and linked the rest of list instead
        return true;
    }
    else
        cout<<"target not foundn";
}