die Anzahl der Knoten einer doppelt verknüpften Liste mit Rekursion

Question

Hier ist, was ich bisher getan:

struct rep_list { 
    struct node *head; 
    struct node *tail; 
} 

typedef rep_list *list; 

int length(const list lst) { 
    if (lst->head == NULL) { 
     return 0; 
    } 
    else { 
     lst->head = lst->head->next; 
     return 1 + length(lst); 
    } 
} 

Dies funktioniert, aber der Kopf der Liste die Funktion akzeptiert als ein Parameter geändert wird. Ich weiß nicht, wie ich das beheben soll.

Ich bin nicht erlaubt, die Funktionsdefinition zu ändern, so dass es immer eine Listenvariable akzeptieren sollte.

Irgendwelche Ideen?

EDIT: Ich habe versucht, was Tyler S in den Kommentaren vorgeschlagen, aber ich stieß auf ein anderes Problem. Wenn ich am Anfang eine Variable node * anlege, sollte sie auf lst-> head zeigen. Aber dann ändert jeder rekursive Aufruf der Funktion den Wert zurück in lst-> head und ich kann mich nicht vorwärts bewegen.

Answer 1

Sie benötigen keinen lokalen Knoten: Ändern Sie nicht den Listenkopf. Übergeben Sie stattdessen den Zeiger als den Rekursionskopf.

int length(const list lst) { 
    if (lst->head == NULL) { 
     return 0; 
    } 
    else { 
     return 1 + length(lst->head-next); 
    } 
} 

---

ich sehe. Okay; Das wird wegen der gewählten Darstellung etwas klobig. Sie benötigen eine temporäre Variable, um die verbleibende Liste zu enthalten. Dies schließt einen Wechsel des Kopfes ein.

int length(const list lst) { 
    if (lst->head == NULL) { 
     return 0; 
    } 
    else { 
     new_lst = new(list) 
     new_lst->head = lst->head->next; 
     var result = 1 + length(new_lst); 
     free(new_lst) 
     return result 
    } 
} 

Bei jeder Rekursion Schritt erstellen Sie eine neue Liste Objekt, um es in die zweite Element der aktuellen Liste zeigen und weiter. Macht das die Arbeit für Sie?

Answer 2

Obwohl diese Lösung klobig ist und ich es hasse, ist es die einzige Möglichkeit, das zu erreichen, was Sie fordern, ohne die Methodensignatur zu ändern. Wir erstellen eine temporäreals Mitglied Daten der Klasse und ändern sie beim Start.

struct rep_list { 
    struct node *head; 
    struct node *tail; 
} 

node *temp = NULL; 
bool didSetHead = false; 

typedef rep_list *list; 

int length(const list lst) { 
    if ((didSetHead) && (lst->head != temp)) { 
     temp = lst->head; 
     didSetHead = false; 
    } 
    if (temp == NULL) { 
     didSetHead = true; 
     return 0; 
    } 
    else { 
     temp = temp->next; 
     return 1 + length(temp); 
    } 
} 

Bitte beachten Sie, ich habe diesen Code nicht getestet und Sie müssen möglicherweise mit ein bisschen spielen, aber die Idee wird funktionieren.