1

メンバ std::list を持つクラス "Class" があります。そのリスト/ツリーで項目、具体的には特定の名前の項目を検索したいと考えています。私のクラスの基本的な表現は次のとおりです。

#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() が検索元に「最も近い」アイテムを返すことです。たとえば、これが私のツリーの場合、各文字はリスト階層の 1 つのレベルを表し、各数字はアイテムの「値」を表します。findItem(3) が C(3) ではなく B(3) を返すようにします。

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

4 に答える 4

4

幅優先検索を使用します。クエリ値と等しくないノードにアクセスすると、そのノードをキューの後ろにプッシュします。最初にキューの先頭からノードを処理します。最初に見つかった一致は、ルートに最も近いものになります。

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;
}
于 2009-04-16T21:10:32.973 に答える
2

幅優先検索スタイルを行う場合、つまり、最初にすべての B を調べ、次にすべての C を調べるなどすると、一致ノードが自動的に最も近くなります。

于 2009-04-16T21:11:24.890 に答える
1

BFS (Breadth Search First)の実行に興味があるようです。これを実装する最も簡単な方法は、再帰ではなく、FIFOキューを使用して、最後にテストする要素に隣接要素を追加し、キューから最初の要素を抽出して次のチェックを実行することです。

挿入の順序は [ A(1), B(2), B(3), C(3), ... ] となり、C(3) をテストする前に B(3) が見つかります。

于 2009-04-16T21:14:28.190 に答える
1

幅優先検索を求めているようです。

あなたの質問は宿題に関連している可能性があると思うので、ここでは詳細を明かしません.

于 2009-04-16T21:09:59.107 に答える