0

所以我在一个夏天的 OO 课上，我们需要编写一个函数来从链表的中间删除一个节点。我真的很接近，但有一些问题。我的代码成功地遍历了链表，但是一旦循环找到节点，实际上删除节点就会出现问题。到目前为止，这是我的功能：

template< class NODETYPE >
bool List< NODETYPE >::removeMiddle( NODETYPE &value, int i )
{
    ListNode <NODETYPE> * tempPtr = firstPtr;
    ListNode <NODETYPE> * prevPtr ;
    int counter=1;

    if ( isEmpty() )
        return false;
    if (i <= 0)
        return false;

    while (tempPtr != 0 && counter < i){
        counter++;
        if ( firstPtr == lastPtr )
        firstPtr = lastPtr = 0;
    else
        firstPtr = firstPtr->nextPtr;
            prevPtr = tempPtr;
            tempPtr = tempPtr->nextPtr;
        }

        if (counter == i){
            value = tempPtr->data;  // data being removed
            delete tempPtr;
        }
    }

    return true;
    RecordCounter--;
}
4

3 回答 3

3

您忘记更改前一个节点，使其不再指向您删除的节点。

你想要的东西（很大程度上）类似于：

if ( counter == i-1 ) //next node is the one you want to delete
{
    aux = tempPtr->nextPtr->nextPtr;   //retain next next node
    delete tempPtr->nextPtr;           //delete next node
    tempPtr->nextPtr = aux;            //current node now points to the node after the deleted one
}
于 2012-07-30T02:17:52.137 回答
2

我的第一个猜测是你没有保持列表的完整性。虽然我对 C++ 很生疏。

您正在删除 tempPtr 并跟踪 prevPtr... 但在删除后没有重新链接列表的两半。

prevPtr->nextPtr = tempPtr->nextPtr
于 2012-07-30T02:17:55.637 回答
0

您忘记调整列表中的链接。之后节点仍然存在delete，但现在它无效。哎呀！

这个功能很有用：

NODETYPE* unlink( NODETYPE*& pNode )
{
    NODETYPE* const result = pNode;

    pNode = pNode->nextPtr;
    return result;
}

调用它传递nextPtr指向要删除的节点的 。你得到一个指向节点的指针，列表重新链接，因此节点不再在列表中。现在您可以delete使用该节点。

如果您只有一个直接指向要删除的节点的指针，并且列表是单链接的，该怎么办？好吧，Donald Knuth 曾经在他的《计算机编程艺术》中提出这个问题（如果我没记错的话）。一种解决方案是与下一个节点交换数据，然后删除下一个节点。

于 2012-07-30T02:26:08.110 回答