3

ボードを確認しましたが、これに関するヘルプは見つかりませんでした。基本的な場合と一般的な場合を考えると、再帰関数を実装するのは簡単だと思いますが、これは私のやり方ではうまくいきません。リンクされたリストの末尾に到達するまで、リストを反復処理することになっています。次のノードが NULL の場合、最後のノードに値を格納し、そのノードを削除して、値を返す必要があります。したがって、再帰的に実行されることを除いて、dequeue メソッドに似ています。私は何を間違っていますか？

int LinkedList::removeTailRec(Node *n)
{
    // check for the base case(s)
    if(n->next == NULL)
    {
        Node *tmp = new Node();
        tmp = n;
        int val = n->value;
        tmp = NULL;
        return val;
    }
    else
        return removeTailRec(n->next);

    // else call the recursive method
}
4

4 に答える 4

5

まず、nullptrNULL の代わりに使用することをお勧めします。

次に、コードに。実際には、リストから何も削除していません。

if(n->next == NULL)
{
    Node *tmp = new Node();
                ^^^^^^^^^^
    //Useless, and dangerous. This memory is never free'd

    tmp = n;
    int val = n->value;
    tmp = NULL;
    ^^^^^^^^^^
    //You just set a local variable to NULL, you're not deleting anything

    return val;
}

ノードを削除する場合は、前のノードへの参照を保持する必要があります (たとえば、二重にリンクされたリストを持つ、つまり、各ノードの次の要素へのポインターと前の要素へのポインターを持つ、または前のノードで直接作業します)。

この前のノードを に設定し、ノードの値nextをnullptr保存してからNodeポインタを削除します。

これを行う 1 つの方法は、次のノードへのポインターを操作することです。

int LinkedList::removeTailRec(Node *n)
{
    //EDIT: Adding a check for n validity
    if(!n){
        //Here, you should have a way of detecting 
        //a call to your method with a null pointer
        return 0;
    }

    Node* nextNode = n->next;
    // check for the base case(s)
    if(nextNode->next == nullptr)
    {
        //Get the next node value
        int val = nextNode->value;

        //Set the current node next member to nullptr
        n->next = nullptr;

        //Free the last node
        delete nextNode;

        return val;
    }
    else{
        return removeTailRec(n->next);
    }

    // else call the recursive method
}
于 2013-05-24T07:40:58.600 に答える
1

結果を保存していますが、リンクされたリストから削除していません。結果を別の変数 (ポインター: 結果) で返すことができます。

Node* getTail(Node *n,int *result){
    //u can even free the memory
    if(!n->next)
    {
       result=n->value;
       return NULL;
    }
    n->next=getTail(n->next,result);
}

または、他の方法で行うことができます

int getTail(Node *n)
{
    if(!n) return 0;
    if(n->next)
    {
        if(!n->next->next)
        {
            Node *frnode=n->next;
            int result=n->next->value;
            n->next=NULL;
            delete frnode;
            return result;
        }
     getTail(n->next);
}
于 2013-05-24T07:40:22.427 に答える
0

n がテール ノードの場合、ノード n の前のノードの次のフィールドを NULL に設定する必要があります。

于 2013-05-24T07:38:39.750 に答える