3

以下に示すようなマルチレベルのデータ構造を実装しようとしています。

object {
   object A {
          child {
               myChild;
          };
          child 1 {
               mychild;
          };
   };
   object B {
         child {
         };
   };
};

私のアプローチは、以下に示すように、リンクされたリストを使用してこれを実装することです。

typedef struct node_s {
    struct node_s *next;
    struct node_s *first_child;
    struct node_s *parent;
    char *text;
} node_t;

上記のリストを STAILQ (sys/queue.h linux) に変換すると、

typedef struct node_s {
    char *text;
    ....;
} node_t;

typedef struct list_s {
    STAILQ_ENTRY(list_s) link;
    node_t *first_child;
    node_t *parent;
    node_t *next;
    int level;
} list_t;

typedef STAILQ_HEAD(list_head_s, list_s) list_head_t;

リンクされたリストまたはリンクされたリストを使用する以外に、これを実装する他のより良い方法があるかどうかを提案してください。

4

1 に答える 1

2

あなたが表現している構造は、リンクされたリストというよりもツリーです。これは、各ノードが0個以上の子を持つ可能性があるノードのコレクションであり、ルートを除くすべてのノードが1つの親を持つことになります。

使用している表現スキームは、通常、ツリーの左子右兄弟表現と呼ばれます。各ノードにその子の明示的なリストを格納させるのではなく、その子の 1 つへのポインターを格納し、次に子をリンク リストを介してリンクします。リンクされた質問と回答で述べたように、これにはメモリが不足している場合にいくつかの利点がありますが、特定のノードの特定の子を検索するのに必要な時間が長くなります。

この構造を表現する方法は他にもたくさんありますが、それをどのように行うかはあなた次第です。1 つのオプションは、子の名前をキーとするある種の連想配列構造に子を格納することです (たとえば、ハッシュ テーブルや平衡二分探索木)。これにより、名前が指定された特定の子を見つけるのがはるかに高速になりますが、メモリ使用量が少し増加します。もう 1 つのオプションは、リンクされたリストを各ノードの子にスレッド化するのではなく、すべての子の明示的な配列を使用することです。これにより、より多くの割り当てが必要になりますが、特定のノードに子を簡単に追加できます。

お役に立てれば！

于 2013-05-27T21:18:00.713 に答える