Как я могу рекурсивно искать список списков для элемента, получая «самое близкое» соответствие - PullRequest
Новая
       20

Как я могу рекурсивно искать список списков для элемента, получая «самое близкое» соответствие

1 голос
/ 17 апреля 2009

Это может потребовать небольшого объяснения, поэтому, пожалуйста, держись со мной. У меня есть класс "Class", который имеет член std :: list, я хочу найти этот список / дерево для предмета, в частности предмет с определенным именем. Основное представление моего класса выглядит следующим образом. 


#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 { ... }
};

Я мог бы просто сделать что-то подобное в 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;
}

Но я хочу, чтобы findItem () возвратил «ближайший» элемент к тому, из которого производился поиск. Например, если это мое дерево, где каждая буква представляет один уровень в иерархии списка, а каждое число представляет значение элемента. Я хочу, чтобы findItem (3) возвращал B (3), а не C (3). 

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

Если я не объясняю себя ясно, пожалуйста, дайте мне знать, и я постараюсь.

Ответы [ 4 ]

4 голосов
/ 17 апреля 2009

Используйте поиск в ширину . Получая доступ к узлу, который не равен значению запроса, вы помещаете этот узел в конец очереди. Сначала обработайте узлы в начале очереди. Первое совпадение, которое вы найдете, будет ближайшим к корню. 

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;
}
2 голосов
/ 17 апреля 2009

Если вы сделаете это стиль поиска в ширину , то есть сначала посмотрите на все буквы B, затем на все буквы C и т. Д., Ваш узел соответствия автоматически будет ближайшим.

1 голос
/ 17 апреля 2009

Кажется, что вы заинтересованы в выполнении BFS (Breadth Search First). Самый простой способ реализовать это - не с помощью рекурсии, а с помощью очереди FIFO , в которой вы добавляете соседние элементы к тому, который вы тестируете в конце, и извлекаете первый элемент из очереди для выполнения следующего проверьте.

Порядок вставок будет [A (1), B (2), B (3), C (3), ...], и вы найдете B (3) перед проверкой C (3).

1 голос
/ 17 апреля 2009

Звучит так, будто вы запрашиваете Поиск в ширину .

Я думаю, что ваш вопрос может быть связан с домашним заданием, поэтому я не буду разглашать более подробную информацию здесь.

...