再帰的なデータ構造

とりあえず手持ちのありあわせのデータを置くだけなら、単純な struct でいいでしょう。でも、グラフ構造をもつようなデータを扱う場合は、再帰的な struct の定義を行う必要があります。今回は、簡単な線形リスト構造をつくってみましょう。こんなのです。

このデータは、next という自分自身と同じデータ構造へのpointerをもち、さらに field0, field1 というデータ領域も持っています。こういった場合は、単に

struct ListA {
    struct ListA * next;
    int field0;
    double field1;
};

などと書くだけです。typedef も一緒にしたいなら、

typedef struct ListA {
    struct ListA * next;  /* まだ typedef は終わっていないので */
    int field0;
    double field1;
} ListA_t, * ListA_tp;
------ あるいは -------
typedef struct ListA ListA_t, * ListA_tp; /* 先に typedef しましょ */
struct ListA {
    ListA_tp next;
    int field0;
    double field1;
};

という感じです。データ構造のイメージさえ描けていれば、なにも難しいことはありません。アクセスする方も

    ListA_tp head;
    int headField   = head->field0;
    int secondField = head->next->field0;
    int thirdField  = head->next->next->field0;

でOKです。

たとえば、今度は tree 構造を考えてみましょう。2分木(binary tree)の場合、親からは左右の子供(例えば lchild と rchild)がいればいいわけです。あと、例えば、(int val)とかいうデータを格納しておきましょう。こんな場合も、

typedef struct Tree {
    struct Tree * lchild;  /* まだ typedef は終わっていないので */
    struct Tree * rchild;  /* まだ typedef は終わっていないので */
    int val;
} Tree_t, * Tree_tp;
------ あるいは -------
typedef struct Tree Tree_t, * Tree_tp; /* 先に typedef しましょ */
struct Tree {
    Tree_tp lchild;
    Tree_tp rchild;
    int val;
};

でOKです。アクセスもこんな感じでおしまい。

    Tree_tp root;
   int lchildVal = root->lchild->val;
   int rchildVal = root->rchild->val;
   int lchildOfrchildVal 
                 = root->rchild->lchild->val;

2001.11.19/ Tomio KAMADA: kamada@cs.kobe-u.ac.jp