1

私はこのクラスを持っています:

class obj
{
public:

    obj()
        : parent(nullptr),
        depth(0)
    {   }

    obj* parent;
    list<obj> children;
    int depth;  // Used only for this example
};

データ構造を埋めるために、次のような再帰関数を使用します。

void recursive(obj& parent)
{
    if(parent.depth == 1)
        return;

    obj son;
    son.parent = &parent;
    son.depth = parent.depth + 1;

    recursive(son);

    parent.children.push_back(son);
}

たとえば、次のようにします。

obj root;
recursive(root);

注意を払うと、再帰関数のテストが次のようになっていることがわかります。

if(parent.depth == n)
    return;

このコードでn >= 2は機能しません (「孫」の親の格納されたアドレスなどはroot->son->son、再帰関数を終了すると有効なアドレスではなくなります)。

この問題を解決する 1 つの方法はlist<obj*> children、値のリストの代わりにポインターのリスト ( )を使用することです。

void recursive(obj& parent)
{
    if(parent.depth == 2)
        return;

    obj* son_ptr = new obj();
    son_ptr->parent = &parent;
    son_ptr->depth = parent.depth + 1;

    recursive(*son);

    parent.children.push_back(son_ptr);
}

同じ作業を行い、objポインターのリストではなく値のリストに s を格納する別の方法はありますか?

4

2 に答える 2

4

さらに子を作成する前に、オブジェクトのアドレスを修正するだけの問題ではありませんか? そのためには、最初にそれらを子リストに入れ、次に再帰します...

void recursive(obj& parent, int n)
{
    if (parent.depth == n)
        return;

    obj son;
    son.parent = &parent;
    son.depth = parent.depth + 1;
    parent.children.push_back(son);

    recursive(parent.children.back(), n);
}
于 2012-07-04T22:36:40.597 に答える
1

objのインスタンスがobj表現されたオブジェクトの ID を定義するのではなく、その ID を定義するように、一意の ID を に格納することを検討してください。これを行うと、objポインターを保存する代わりに、ID を保存して関連する をリンクする可能性があります。

たとえば、クラスを変更してフィールドobjを含めることができます。intid

class obj {
public:
    obj()
        : parent(nullptr),
          depth(0)
    {
        // Not thread-safe; would need to get protected if multi-threaded
        id = nextId++;
    }

    static int nextId;

    int id;
    int parentId;
    list<int> childrenIds;

    int depth;  // Used only for this example
};

obj新しい論理的な「もの」を表すために new を作成するときはいつでも、idフィールドに新しい一意の値を割り当てることができます。obj関連する「もの」を表す間の関係を確立したい場合、たとえば、ポインタ フィールドparentIdの代わりにフィールドを使用できます。parent

void recursive(obj& parent)
{
    if (parent.depth == 1) {
        return;
    }

    obj son;
    son.parentId = parent.id;
    son.depth = parent.depth + 1;

    recursive(son);

    parent.childrenIds.push_back(son.id);
}

リンクをたどりたい場合、これにはより多くの作業が必要です: 親へのポインターをたどる代わりに、管理しているグローバルリストでobjを検索する必要があります (問題の を検索します)。objobjparentId

もちろん、これは、これらobjの が実際に表しているものと、達成しようとしているより広い目標に大きく依存します...

于 2012-07-04T22:03:52.297 に答える