Come posso ricorsivamente cercare una lista di liste per un elemento, ottenendo il match “più vicino”

Question

Ho una classe "Class", che ha uno std :: membro lista, voglio cercare quella lista / albero per un elemento, in particolare un elemento con un nome specifico. Una rappresentazione di base della mia classe è la seguente:

#include <list>
#include <string>
class Class {
    std::string _name;
    std::list<Class*> _members;
public:
    Class(const std::string& name) : _name(name) {}
    void addMember(Class* member) { _members.push_back(member); }
    const std::string& name() const { return _name; }
    const std::list members() const { return _members; }
    Class* findItem(const std::string& name) const { ... }
};

ho potuto solo fare qualcosa di simile in Class :: FindItem:

Class* Class::findItem(const std::string& n) const {
    std::list<Class>::const_iteratior i;
    for(i=_members.begin(); i!=_members.end(); ++i)
        if((*i)->name() == n) return *i;
    for(i=_members.begin(); i!=_members.end(); ++i) {
      Class* cls = (*i)->findItem(n);
      if(cls) return cls;
    }
    return 0;
}

Ma, quello che voglio che accada è per FindItem () per restituire l'articolo "più vicino" a quello ricercato da. Per esempio, se questo è il mio albero, con ogni lettera rappresenta un livello nella gerarchia lista e ogni numero che rappresenta gli oggetti "di valore". Voglio FindItem (3) per tornare B (3), piuttosto che C (3).

                        A(1)
                        |
        ----------------------------------
        B(2)                           B(3)
         |                                |
---------------------                   -----
C(3)             C(4)                    C(4)
                 |                         |
            ----------------           ----------
            D(5)  D(6)  D(7)           D(5)  D(6)

Answer 1

ampiezza di ricerca . Come si accede a un nodo che non è uguale al valore di query, si preme il nodo sul retro della coda. nodi di processo dalla parte anteriore della coda prima. La prima partita a trovare sarà quello più vicino alla radice.

Class* Class::findItem(const std::string& n) const {
    std::list<Class>::const_iteratior i;
    std::queue<Class*> q;
    q.push(this);
    while (!q.empty()) {
        Class *c = q.front(); q.pop();
        if (c->name() == n) return c;
        for(i=c->_members.begin(); i!=c->_members.end(); ++i)
            q.push(i);
    }
    return NULL;
}

Answer 2

Se lo fate breadth-first-search stile , cioè primo sguardo tutte le Bs, poi tutto il Cs, ecc, il nodo partita sarà automaticamente il più vicino.

Answer 3

Sembra come se siete interessati a condurre una BFS (Larghezza Ricerca First ). Il modo più semplice di attuazione non è per la ricorsione, ma piuttosto con un rel="nofollow coda FIFO dove si aggiungono gli elementi vicini a quella che si sta testando, alla fine, ed estrarre il primo elemento dalla coda per eseguire il controllo successivo.

L'ordine delle inserzioni sarebbe [A (1), B (2), B (3), C (3), ...] e troverete B (3) prima di testare C (3).

Answer 4

Sembra che si sta chiedendo un Larghezza-prima ricerca .

Penso che la tua domanda può essere correlato ad un compito per casa, quindi non voglio rivelare maggiori dettagli qui.