C++: Verwenden von Rekursion, um ein int in einer Liste zu finden - Wann

Question

Ich versuche, rekursiv durch jeden Knoten in einer List-Klasse zu suchen, ob eine bestimmte Ganzzahl in einem der Knoten in der Liste vorhanden ist.

Dies ist meine Header-Datei:

class List 
{ 
public: 
    bool find(int d) const { return false; } 
private: 
    Node *head; 

    bool findNode(const Node*, int) const; 
}; 

Hier ist der Code für zwei Funktionen:

bool List::find(int d) const 
{ 
    return findNode(head, d); 
} 

bool List::findNode(const Node* n, int d) const 
{ 
    if (n == NULL) 
     return false; 
    else if (n->data == d) 
     return true; 
    else 
     findNode(n->next, d); 
} 

Nun meine Frage hier ist: Habe ich mich verdammen, indem Sie die if (n == NULL) Anweisung in der findNode Funktion damit es immer falsch zurückkehrt? Ich glaube nicht, dass ich das tun muss, wenn ich bereits return false in der Header-Datei habe. Sollte ich diese Linie entfernen, und gibt es einen besseren Weg, dies zu tun?

Answer 1

Die if (n == NULL) return false ist gut, weil es nur passiert, wenn Sie das Ende der Liste erreicht haben und Sie sollten false zurückgeben.

Die erste Frage, die ich sehe, ist, dass die Linie findNode(n->next, d);return findNode(n->next, d);

Der zweite sein sollte, ist, dass Sie die Funktion Körper für find() aus dem Header-Datei entfernen müssen. Sie können den Funktionskörper nicht zweimal definieren.

Somit ist der vollständige Code ist:

class List 
{ 
public: 
    bool find(int d) const; 
private: 
    Node *head; 
    bool findNode(const Node*, int) const; 
}; 

bool List::find(int d) const 
{ 
    return findNode(head, d); 
} 

bool List::findNode(const Node* n, int d) const 
{ 
    if (n == NULL) 
     return false; 
    else if (n->data == d) 
     return true; 
    else 
     return findNode(n->next, d); 
} 

Answer 2

Sie müssen die NULL-Prüfung wie das ist, wie Sie das Ende der Liste zu bestimmen. Ich schätze, du versuchst das als Übung, sonst brauchst du hier offensichtlich keine Rekursion.