1

我的链表中的 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 found\n";

}
4

6 回答 6

1

我猜这是一个单链表（也就是说，它只会向前），因为你没有 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 found\n";
    }

    return found;
}
于 2013-08-26T14:43:24.793 回答
1

这是正常工作的版本（我认为；不过，我还没有对其进行测试，并且根据我的经验，未经测试的软件有问题）似乎类似于最初的意图（即，删除第一个元素时没有特殊情况）：

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 found\n";
    return false;
}
于 2013-08-26T15:23:06.487 回答
0

这段代码有很多问题：

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

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

于 2013-08-26T14:43:19.267 回答
0

我觉得有几个地方看不懂

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

为什么要为 current 分配一个新节点，因为 current 无论如何都会被分配启动？

第二，

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

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

BTW，你为什么不使用 STL 提供的链表呢？

于 2013-08-26T14:47:21.977 回答
0

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

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

于 2013-08-26T14:47:44.740 回答
-2

Here is a better version of your code. Less variables and all. Try it and see if it works now. :)

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 found\n";
}
于 2013-08-26T14:53:55.973 回答