递归方法C++

Question

我正在练习链接列表结构，我已经使用该算法编写了一个程序。在程序中有一个递归方法来删除链表的每个元素。但是，该方法崩溃。

void exit() 
{ 
    Person* person = phead; 
    exterminateStartingFrom(person); 
} 

void exterminateStartingFrom(Person* person) 
{ 
    Person* nextperson; 
    nextperson = person->getNext(); 
    if(nextperson){ 
     exterminateStartingFrom(nextperson); 
    } 
    delete person; 
} 

此方法在用户想要退出时运行。 “头脑”代表人员名单的第一个元素。问题表现为：双重释放或腐败（fasttop）

这里是类人：

class Person { 
private: 
    std::string firstname; 
    std::string lastname; 
    int age; 
    Person* next; 

public: 
    Person(std::string, std::string, int); 
    void printDescription(); 
    void printFirstname(); 
    void printLastname(); 
    void printAge(); 
    void setNext(Person*); 
    Person* getNext(); 


}; 

感谢。

Answer 1

是你的单子单向还是双向？如果您有双向列表（不仅指向下一个元素而且还指向前一个元素），并且调用析构函数，则可能还会删除previous和next字段指示的元素。当递归返回一级并且你想删除倒数第二个元素时，你会得到错误。

Answer 2

如果不知道如何构建或删除Person对象，很难说清楚。您的错误消息意味着您要删除相同的实体两次，或者您正在删除未分配的内容。可能试图打印您尝试删除的地址，以便您可以检查是否存在多次删除的相同地址？

还处理您传递给递归方法的指针是nill的情况。

Answer 3

以下是我采取的方法。自然这是有点人为的，因为我不知道你的实际功能。我也用一个初始的全局变量来代表pHead，并使用超出范围的年龄来表示列表的头部。

对于列表的头部，我使用了一个特殊的构造函数。

但是，在这个快速而肮脏的实现中，有更好的方法可以做到这一点，我需要一些东西来表明在递归过程中退出时我知道什么时候我一直支持列表的头部。

#include <string> 

class Person { 
private: 
    std::string firstname; 
    std::string lastname; 
    int age; 
    Person* next; 

public: 
    Person (void);       // constructor for the pHead 
    ~Person (void); 
    Person(std::string, std::string, int); // standard constructor used 
    std::string getFirstname(void) { return firstname; }; 
    std::string getLastname(void) { return lastname; } 
    void setNext(Person *newNext) { next = newNext; } 
    Person* getNext() { return next; } 
    Person *addToListAt (Person *personList); 
    void addToListAtEnd (Person *personList); 
    void Person::insertListAfter (Person *personList); 
    bool isHeadOfList (void); 
}; 

Person pHead = Person(); 

// special constructor used to create the head to a linked list 
Person::Person() 
{ 
    age = -1; 
    next = 0; 
} 

// standard constructor used to create a list item. 
Person::Person (std::string sFirstName, std::string sLastName, int myAge) 
{ 
    if (myAge < 0) myAge = 0; 
    firstname = sFirstName; 
    lastname = sLastName; 
    age = myAge; 
    next = 0; 
} 

Person::~Person() 
{ 
    next = 0; 
    age = 0; 
} 

void exterminateStartingFrom(Person* person) 
{ 
    Person* nextPerson; 
    nextPerson = person->getNext(); 
    if(nextPerson){ 
     exterminateStartingFrom(nextPerson); 
    } 

    if (! person->isHeadOfList()) 
     delete person; 
} 

Person *Person::addToListAt (Person *personList) 
{ 
    Person* nextPerson; 
    nextPerson = personList->getNext(); 
    personList->setNext (this); 
    return nextPerson; 
} 

void Person::insertListAfter (Person *personList) 
{ 
    Person* nextPerson; 
    nextPerson = personList->getNext(); 
    personList->setNext (this); 
    next = nextPerson; 
} 

void Person::addToListAtEnd (Person *personList) 
{ 
    Person* nextperson; 
    nextperson = personList->getNext(); 
    if(nextperson){ 
     addToListAtEnd (nextperson); 
    } else { 
     personList->setNext (this); 
    } 
} 

bool Person::isHeadOfList (void) 
{ 
    // we use a special age to represent the head of the list 
    // the head does not contain any data except for point to first item 
    // in the list. 
    return (age < 0); 
} 

int main(int argc, char * argv[]) 
{ 
    Person *newPerson = new Person("first_1", "last_1", 11); 
    newPerson->addToListAtEnd (&pHead); 
    newPerson = new Person("first_2", "last_2", 22); 
    newPerson->addToListAtEnd (&pHead); 
    newPerson = new Person("first_3", "last_3", 33); 
    newPerson->addToListAtEnd (&pHead); 

    Person *itemPerson = pHead.getNext(); 
    newPerson = new Person("first_11", "last_11", 12); 

    newPerson->insertListAfter (itemPerson); 

    exterminateStartingFrom(&pHead); 
    return 0; 
}