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 ...を追跡していますが、削除後にリストの2つの半分を再リンクしていません。

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そのノードをすることができます。

削除するノードへの直接のポインターしかなく、リストが単独でリンクされている場合はどうすればよいですか？ええと、ドナルド・クヌースはかつて彼のThe Art of Computer Programmingの演習としてそれを尋ねました（私が正しく思い出せば）。1つの解決策は、データを次のノードと交換してから、次のノードを削除することです。

于 2012-07-30T02:26:08.110 に答える