3

我检查了董事会，找不到任何帮助。我发现在给定基本情况和一般情况的情况下实现递归函数很容易，但这并不像我那样工作。我应该迭代一个列表，直到我到达一个链表的尾部。如果下一个节点为 NULL，那么我必须将值存储在最后一个节点，删除该节点，然后返回该值。所以它类似于出队方法，除了它是递归执行的。我究竟做错了什么？

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

首先，我建议您使用nullptr而不是 NULL。

然后，进入您的代码。您实际上并没有从列表中删除任何内容。

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指针。

一种方法是使用指向下一个节点的指针：

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 回答
1

您没有删除代码中的最后一个节点，而是在此处泄漏了另一个（临时）节点。要删除最后一个节点，您必须将前一个节点中的链接归零。您的代码应如下所示

...
if (n == NULL || n->next == NULL)
    throw std::out_of_range("node");
if(n->next->next == NULL)
{
    int val = n->next->value;
    delete n->next;
    n->next = NULL;
    return val;
}
else ...

请注意，c++ 不是一种函数式语言，并且没有对尾递归进行优化，因此在实际应用程序中，随着列表变得足够大，您最终会因堆栈溢出而失败 =) 使用 Haskell 或 Erlang 进行这种编程风格, 在 c++ 中使用for或while.

于 2013-05-24T07:43:33.387 回答
0

当 n 是尾节点时，您应该将节点 n 的前一个节点的下一个字段设置为 NULL。

于 2013-05-24T07:38:39.750 回答