c++ - 从双向链表c++中删除偶数节点

Question

我试图通过递归删除甚至在双向链表中的节点。问题是它删除了节点，但在删除的节点空间中仍然显示垃圾。

这是输出:

这是原始列​​表:2 -> 2 -> 23 -> 2 -> 78 -> 5 -> 2

此列表包含 7 个项目

偶数的个数是:5

移除的偶数节点数为:5

结果列表是... 23 -> 5

***************删除偶数后，我得到了这个，你遇到同样的问题吗？*************** *************************

现在向后:5 -> 27303024 -> 27302960 -> 23 -> 27302928 -> 0

此列表包含 2 个项目

所有数据的总和为:28

int removeEven(node*& head) {
    // double pointer to use the address of pointer head
    node ** deleteNode = &head;
    //if is the end of the list stop
    if(head==NULL)
        return 0;
    //if is even
    if((*deleteNode) -> data %2==0)
    {
        node * helper = *deleteNode;
        *deleteNode = helper -> next;
        delete helper;

        return 1+ removeEven(helper -> next);
    }   
    //but if is an odd number
    else if ((*deleteNode) -> data %2)
    {
        //traverse to the next node
        deleteNode = &(*deleteNode)->next;
        //calls itself so that we can start againg to check in the new node.
        return removeEven(head -> next);
    }
}

有人告诉我像这样更改函数会有帮助，但我遇到了很多错误请帮忙

---

//Remove even numbers
node* recfunremoveEven(node *head,node *prevnode, int* count) //helper function for remove even nodes
{
    if(head==NULL)
        return NULL;
    if(head->data %2 == 0) //data is even
    {
        *count+=1;
        free(head);
        node* next = recfunremoveEven(head->next,head,&count); //recursive call
        if(prevnode)
        {
            prevnode->next = next;
            next->previous = prevnode;
        }
        return next;
    }
    return recfunremoveEven(head->next,&count);
}

int removeEven(node*& head)
{
    int count=0;
    recfunremoveEven(head,&count);
    return count;
}

---

编译时出现以下错误:

g++ -g -std=c++11 -o proftest dlist.h dlist.cpp main.cpp supplied.o

dlist.cpp: In function ‘node* recfunremoveEven(node*, node*, int*)’:

dlist.cpp:30:53: error: cannot convert ‘int**’ to ‘int*’ for argument ‘3’ to ‘node* recfunremoveEven(node*, node*, int*)’ node* next = recfunremoveEven(head->next,head,&count); //recursive call ^

dlist.cpp:38:42: error: cannot convert ‘int**’ to ‘node*’ for argument ‘2’ to ‘node* recfunremoveEven(node*, node*, int*)’ return recfunremoveEven(head->next,&count); ^

dlist.cpp: In function ‘int removeEven(node*&)’: dlist.cpp:45:29: error: cannot convert ‘int*’ to ‘node*’ for argument ‘2’ to ‘node* recfunremoveEven(node*, node*, int*)’ recfunremoveEven(head,&count);

这是 .h 文件，以防有人需要查看它

//doubly linked list
#include <iostream>
#include <cstring>
#include <cctype>
#include <cstdlib>


struct node
{
    int data;
    node * previous;
    node * next;
};

/* These functions are already written and can be called to test out your code */
void build(node * & head);  //supplied
void display(node * head);  //supplied
void destroy(node * &head); //supplied
//Recursively compute and return the number of nodes that contain even number
//in the doubly linked list
int countEven(node *head);
//Recursively remove all the nodes that contain even number in the doubly linked list
//and return the number of nodes removed 
int removeEven(node*& head);

Answer 1

在 free(head) 之后，您不能取消引用 head，但您可以。

您还在不应该(递归时)的地方添加了一些 &，并且在几个函数调用中遗漏了一个参数。

但我认为您绕过“上一个”节点会使事情过于复杂。

需要处理三种情况:

1. 列表为空，
2. 第一个节点是奇数，
3. 第一个节点是偶数。

第一种情况很简单。
第二个和第三个非常相似:

• 从列表的其余部分递归地删除偶数节点。
• 调整该删除结果的 previous 指针。
• 如果 head 是偶数，删除它并增加计数。
• 返回 head(如果它是奇数)或递归的结果(如果 head 是偶数)。

我相信这应该可以做到(当心 - 未经测试):

node* removeEvenWorker(node* head, int* count)
{
    // Case 1
    if (head == nullptr)
    {
        *count = 0;
        return head;
    }

    // Recurse
    node* rest = removeEvenWorker(head->next, count);

    // Cases 2 & 3: Set up the first node.
    if (head->data % 2 != 0)
    {
        // Keep 'head'; link the recursive result to it.
        if (rest != nullptr)
        {
            rest->previous = head;
        }
        head->next = rest;
        return head;
    }
    else
    {
        // Discard 'head'
        if (rest != nullptr)
        {
            rest->previous = nullptr;
        }
        free(head);
        *count += 1;
        return rest;
    }

}

并调用它:

int removeEven(node*& head)
{
    int count = 0;
    head = removeEvenWorker(head, &count);
    return count;
}