递归删除双向链表Ç即使项目++

问题描述：

这里是同样的问题，我问： deleting even nodes from a doubly link list c++递归删除双向链表Ç即使项目++

不同的是，我想明白什么是错我的代码。我不想只是接受一种完全不同的方法，而不明白为什么我的代码不起作用。以下是我的代码的两个版本，我想知道两者的问题。他们都给我分段错误。

int removeEven(node *&head) 
{ 
if(!head)    //Base case: end of list reached 
    return 0; 
int count = removeEven(head->next);  //Recurse to end of list 
if(head->data % 2 != 0) 
    return count; 
else{ 
    ++count; 
    if(head->next){ 
     head->next->previous = head->previous; 
    } 
    if(head->previous){ 
     head->previous->next = head->next; 
    } if(!(head->previous)){ 
     node* temp = head; 
     head = head->next; 
     delete temp; 
    } 
    else 
     delete head; 
} 
return count; 
}

第二个将count = 0作为默认参数。

int removeEven(node *&head, int count) 
if(head && head->data % 2 != 0) //not null, not even 
{ 
    removeEven(head->next, count); 
} 
else if(head != NULL){  //not null, yes even 
    ++count; 
    if(head->next) 
     head->next->previous = head->previous; 
    if(head->previous) 
     head->previous->next = head->next; 
    node* temp = head; 
    head = head->next; 
    delete temp; 
    removeEven(head, count); 
} 
    return count;  //base case: null 
}

答

int removeEven(node *&head) 
{ 
    if(!head)    //Base case: end of list reached 
    return 0; 
    int count = removeEven(head->next);  //Recurse to end of list 
    if(head->data % 2 != 0) 
    return count; 
    else{ 
    ++count; 
    // CORRECT WAY!!! copy the old pointer in a temp 
    node *t = head; 
    if(head->next){ 
     head->next->previous = head->previous; 
    } 
    if(head->previous){ 
     // WARNING!!! here you are ACTUALLY modifying head to nullptr 
     head->previous->next = head->next; 
    } 
    // CORRECT WAY!!! delete the temp pointer 
    delete t; 
    // WARNING!!! here you are trying to access a nullptr in head 
    // if(!(head->previous)){ 
    // node* temp = head; 
    // head = head->next; 
    // delete temp; 
    // } 
    // else 
    // delete head; 
    } 
    return count; 
}

我已经通过的valgrind和gdb

valgrind ./a.out 
==2729== Memcheck, a memory error detector 
==2729== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al. 
==2729== Using Valgrind-3.10.0 and LibVEX; rerun with -h for copyright info 
==2729== Command: ./a.out 
==2729== 
[9] [8] [7] [6] [5] [4] [3] [2] [1] [0] 
==2729== Invalid read of size 8 
==2729== at 0x4008F5: removeEven(node*&) (list1.cpp:26) 
==2729== by 0x40087A: removeEven(node*&) (list1.cpp:15) 
==2729== by 0x40087A: removeEven(node*&) (list1.cpp:15) 
==2729== by 0x40087A: removeEven(node*&) (list1.cpp:15) 
==2729== by 0x40087A: removeEven(node*&) (list1.cpp:15) 
==2729== by 0x40087A: removeEven(node*&) (list1.cpp:15) 
==2729== by 0x40087A: removeEven(node*&) (list1.cpp:15) 
==2729== by 0x40087A: removeEven(node*&) (list1.cpp:15) 
==2729== by 0x40087A: removeEven(node*&) (list1.cpp:15) 
==2729== by 0x40087A: removeEven(node*&) (list1.cpp:15) 
==2729== by 0x400AFD: main (list1.cpp:81) 
==2729== Address 0x10 is not stack'd, malloc'd or (recently) free'd 
==2729== 
==2729== 
==2729== Process terminating with default action of signal 11 (SIGSEGV) 
==2729== Access not within mapped region at address 0x10 
==2729== at 0x4008F5: removeEven(node*&) (list1.cpp:26) 
==2729== by 0x40087A: removeEven(node*&) (list1.cpp:15) 
==2729== by 0x40087A: removeEven(node*&) (list1.cpp:15) 
==2729== by 0x40087A: removeEven(node*&) (list1.cpp:15) 
==2729== by 0x40087A: removeEven(node*&) (list1.cpp:15) 
==2729== by 0x40087A: removeEven(node*&) (list1.cpp:15) 
==2729== by 0x40087A: removeEven(node*&) (list1.cpp:15) 
==2729== by 0x40087A: removeEven(node*&) (list1.cpp:15) 
==2729== by 0x40087A: removeEven(node*&) (list1.cpp:15) 
==2729== by 0x40087A: removeEven(node*&) (list1.cpp:15) 
==2729== by 0x400AFD: main (list1.cpp:81) 
==2729== If you believe this happened as a result of a stack 
==2729== overflow in your program's main thread (unlikely but 
==2729== possible), you can try to increase the size of the 
==2729== main thread stack using the --main-stacksize= flag. 
==2729== The main thread stack size used in this run was 8720384. 
==2729== 
==2729== HEAP SUMMARY: 
==2729==  in use at exit: 240 bytes in 10 blocks 
==2729== total heap usage: 10 allocs, 0 frees, 240 bytes allocated 
==2729== 
==2729== LEAK SUMMARY: 
==2729== definitely lost: 24 bytes in 1 blocks 
==2729== indirectly lost: 0 bytes in 0 blocks 
==2729==  possibly lost: 0 bytes in 0 blocks 
==2729== still reachable: 216 bytes in 9 blocks 
==2729==   suppressed: 0 bytes in 0 blocks 
==2729== Rerun with --leak-check=full to see details of leaked memory 
==2729== 
==2729== For counts of detected and suppressed errors, rerun with: -v 
==2729== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0) 

Compilation segmentation fault at Fri Jul 28 09:46:51

请查看关于错误的评论以及正确的方法。 –

不幸的是，它仍然无法正常工作。它说./main中的错误免费或腐败，并给我一个回溯和内存映射。 GDB给出SIGABRT –

而且，我不明白这里有什么区别： node * t = head; if（head-> next） head-> next-> previous = head-> previous; if（head-> previous） head-> previous-> next = head-> next; 删除t; 如何删除与删除头不同的东西？在分配t = head后，头部未被修改。 –

答

得到了根本原因的提示我测试你的代码清单开始为偶数项，它失败。教授提供的所有测试案例都以一个偶数项开始。这里是解决方案：

int removeEven(node *&head) 
{ 
if(!head)    //Base case: end of list reached 
    return 0; 
int count = removeEven(head->next);  //Recurse to end of list 
if(head->data % 2 != 0) 
    return count; 
else{ 
    ++count; 
    node *t = head; 
    if(head->next) 
     head->next->previous = head->previous; 
    if(head->previous) 
     head->previous->next = head->next; 
    if(head && !head->previous) 
     head = head->next; 
    delete t; 
} 
return count; 
}

的问题是，如果头节点被删除的实际原头指针会迷路。现在我检查我们是否在实际的头部，因为head-> previous应该是NULL，然后在删除之前将实际的头指针设置到列表中的下一个节点。

递归删除双向链表Ç即使项目++

相关推荐