Rekursiv berechnen Sie die Anzahl der Knoten in einer kreisförmigen verketteten Liste mit nur Kopfzeiger

Question

Ich schreibe diese Funktion als Teil der Hausaufgaben. Wäre nicht so eine große Sache, wenn es einen Schwanzzeiger enthalten würde und der meiste Code von meinem Ausbilder zur Verfügung gestellt und in eine Objektdatei eingeschlossen wurde, also habe ich nicht die Implementierung, um einzuschließen. Wie auch immer, aus irgendeinem Grund wird der Basisfall in meiner Funktion nie erreicht. Kann mir jemand sagen, warum das Looping hält?

#include "clist.h" 
#include <iostream> 

using namespace std; 

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

//Iteratively compute and return the number of nodes in the circular linked list 
int count(node* head) 
{ 
    int nodeTotal = 1; 
    node* temp = head; 
    while(temp->next != head) 
    { 
     nodeTotal++; 
     temp = temp->next; 
    } 
    return nodeTotal; 
} 


//Recursively compute and return the number of nodes in the circular linked list 
int countR(node* head) 
{ 
    node* temp = head; 
    if(temp->next == head) 
     return 0; 
    else 
     return 1 + countR(temp->next); 
} 


//Iteratively compute and return the sum of the ints contained in the circular linked list 
int sum(node* head) 
{ 
    int valuesTotal = 2; 
    node* temp = head; 
    while(temp->next != head) 
    { 
     valuesTotal += temp->data; 
     temp = temp->next; 
    } 
    return valuesTotal; 
} 

int main() 
{ 
    node* head{nullptr}; 

    /* Builds a circular linked list with a random number of nodes 
    *containing randomly-chosen numbers. 
    */ 
    build(head); 

    display(head); 

    // PUT YOUR CODE HERE to call the functions assigned, 
    // and print out the results. For example, 
    // 
    // cout << "iterative sum: " << sum(head) << endl; 
    // 
    // The code for your functions should be in clist.cpp. 
    cout << "\nIterative node count: " << count(head) << endl; 
    cout << "Iterative sum: " << sum(head) << endl; 
    cout << "Recursive node count: " << countR(head) << endl; 

    // When called the 2nd time, this also prints the total 
    // of the numbers in the nodes. 
    display(head); 




    int  nNodesFreed{0}; 
    node* n{head}; 
    node* temp; 

    while(n != head || ! nNodesFreed) { 
     temp = n->next; 
     delete n; 
     n = temp; 
     nNodesFreed++; 

     } 
    cout << "# nodes freed: " << nNodesFreed << endl; 

    //destroy(head); 

    return 0; 
} 

Answer 1

Ihre Stopp-Bedingung nicht funktioniert, weil jedes Mal, wenn Sie einen rekursiven Anruf zu tätigen, Sie mit einem neuen head Zeiger beginnen. Also, lassen Sie uns sagen, dass Sie mit einer verknüpften Liste wie folgt beginnen:

Beim ersten Aufruf, Sie passieren A (na ja, die Adresse von A), und es wird geprüft, ob A == B. Es ist nicht, es führt also einen rekursiven Aufruf durch, der B passiert. Bei diesem Aufruf prüft er, ob B == C ist. Das schlägt fehl, also führt er einen rekursiven Aufruf durch. C prüft, ob C == D. Das scheitert, also prüft er, ob D = = E. Das scheitert, also prüft es, ob E == A. Das scheitert, also prüft es, ob A == B ist. Das schlägt immer noch fehl, also geht es weiter ...

Und rund herum geht es. Wo es aufhört, weiß niemand!