遞歸方法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; 
}