C言語関係掲示板

過去ログ

No.1141 個数に上限のない多分木をつくる

[戻る] [ホームページ]
No.14536

多分木をつくる
投稿者---prontera(2004/06/10 01:00:59)


多分木を用いた文字列処理の課題をやっています。
そこで質問なのですが、

struct STR {
    char record[32];           // レコード名
    char string[32];           // 格納した文字列
};
struct NODE {
    char name[32];             // ノード名
    struct STR *str[16];       // 文字列レコードへのポインタ
    struct NODE *NextNode[16]; // 次ノードへのポインタ
};


このような構造体を定義して作成しています。
仕様では

「複数個のノードを保持できるが、保持できる個数に上限を用いても良い」

とあります。
見ての通り保持できる子ノードは16個になっていますが上限を決めずに
処理を行う方法が思いつきません。課題は上限有りでも問題ないのですが
どうやればいいのか知りたいです。どなたかご教授お願いいたします。


No.14537

Re:多分木をつくる
投稿者---あかま(2004/06/10 02:10:27)


struct NODE {
    char name[32];             // ノード名
    struct STR *str[16];       // 文字列レコードへのポインタ
    int node_num;//次ノードの格納数
    int node_max;//次ノードの最大数
    struct NODE **NextNode; // 次ノードへのポインタ
};

な感じに変更して、
node_numがnude_maxに追いついた時はrealloc

if(node_num >= node_max)
    p->NextNode = realloc(p->NextNode,sizeof(struct NODE *)*(node_max *=2));
    



No.14538

Re:多分木をつくる
投稿者---prontera(2004/06/10 02:47:45)


>node_numがnude_maxに追いついた時はrealloc

>if(node_num >= node_max)
> p->NextNode = realloc(p->NextNode,sizeof(struct NODE *)*(node_max *=2));

上のコードの意味は

ノード保持数が最大数以上になったら
今まで指していた領域(構造体)の数を2倍にして
元の領域を指していたポインタを返す

でよろしいですか?いまいち自信が無いので…


No.14539

Re:多分木をつくる
投稿者---あかま(2004/06/10 03:35:59)



>ノード保持数が最大数以上になったら
>今まで指していた領域(構造体)の数を2倍にして
ここまでok。
>元の領域を指していたポインタを返す
元の領域かどうかはわかりませんが、reallocが元の情報をコピーした領域ではあります。
http://www9.plala.or.jp/sgwr-t/lib/realloc.html


No.14577

Re:多分木をつくる
投稿者---prontera(2004/06/12 08:51:05)


>struct NODE {
>    char name[32];             // ノード名
>    struct STR *str[16];       // 文字列レコードへのポインタ
>    int node_num;//次ノードの格納数
>    int node_max;//次ノードの最大数
>    struct NODE **NextNode; // 次ノードへのポインタ
>};


また質問なのですが、なぜNextNodeへは二重間接参照になっているのですか?

</pre>


No.14589

Re:多分木をつくる
投稿者---あかま(2004/06/12 14:38:23)


>また質問なのですが、なぜNextNodeへは二重間接参照になっているのですか?
ポインタのポインタのが便利だから。

struct NODE {
    char name[32];             // ノード名
    struct STR *str[16];       // 文字列レコードへのポインタ
    int node_num;//次ノードの格納数
    int node_max;//次ノードの最大数
    struct NODE **NextNode; // 次ノードへのポインタ
};

if(node_num >= node_max)
    p->NextNode = realloc(p->NextNode,sizeof(struct NODE *)*16);
    
で元のプログラムとほぼ同様、
p->NextNnode[i]
で次のノードへの"ポインタ"が取り出せる。プログラムの変更点も少なめ。


struct NODE *NextNode; // 次ノードへのポインタ
p->NextNode = realloc(p->NextNode,sizeof(struct NODE)*16);
にして
次のノードを直接確保してもいいけどかなり無駄っぽい。
&融通が利かない(木の編集がしにくい)ので。

まーほんとはそこまで考えてなかったけど。ただ単に配列を動的に確保してみただけ。



No.14544

Re:多分木をつくる
投稿者---NykR(2004/06/10 09:20:42)


>上限を決めずに
>処理を行う方法が思いつきません。

連結リストとか木とか可変長配列のような上限のないコレクションを使えばいいです。
struct NODE;
struct CELL {
    struct NODE *NextNode;
    struct CELL *next;
};

struct NODE {
    char name[32];
    struct STR *str[16];
    struct CELL *ListHead;
};



No.14569

Re:多分木をつくる
投稿者---塗り壁(2004/06/11 17:19:56)


pronteraさん、今日は。趣味で数学的なプログラムを
作っている塗り壁と申します。余り時間が無いのでヒントだけ。
私はノード数が数千万、子ノードの数が少ないのは0、多いのは数百に達するような木を使っています。
このような規模の木を効率よく構成する為には「長男次弟構造」を使います。
木のノードだけのメモリーで十分でリンクの為の余計なメモリーも不要です。データ構造とアルゴリズムの基本ですので、その方面の文献を見てください。


No.14578

Re:多分木をつくる
投稿者---prontera(2004/06/12 08:55:54)


>pronteraさん、今日は。趣味で数学的なプログラムを
>作っている塗り壁と申します。余り時間が無いのでヒントだけ。
>私はノード数が数千万、子ノードの数が少ないのは0、多いのは数百に達するような木を使っています。
>このような規模の木を効率よく構成する為には「長男次弟構造」を使います。
>木のノードだけのメモリーで十分でリンクの為の余計なメモリーも不要です。データ構造とアルゴリズムの基本ですので、その方面の文献を見てください。

調べてみました。一般的な木を二分木式の表現にに変換 という考えでしょうか。
なるほど…たしかに木のノードだけで表せそうですね。
C++のソースしか見つけられなかったのですがCでのコードも考えてみます。
このような表現があったことを初めて知りました。情報ありがとうございます。


No.14579

Re:多分木をつくる
投稿者---prontera(2004/06/12 09:19:43)


struct NODE {
    struct NODE *elder;   // 長男ノードへのポインタ
    struct NODE *younger; // 次弟ノードへのポインタ
    char *string;         // ノード名・レコード名・文字列など
};


こんな感じでしょうか?あまり自信ないですが…


No.14581

Re:多分木をつくる
投稿者---塗り壁(2004/06/12 12:02:59)


>
struct NODE {
    struct NODE *elder;   // 長男ノードへのポインタ
    struct NODE *younger; // 次弟ノードへのポインタ
    char *string;         // ノード名・レコード名・文字列など
};

>
>こんな感じでしょうか?あまり自信ないですが…

そのとおりです。あとは、ノード間のリンクの張り方、辿り方に注意するだけです。

ついでに2件。
1 文字列をどのように扱うのか分かりませんが、保存と検索だけだったら
この多分木をベースにトライ(TRIE)を溝築すれば検索が超高速化できます。

参考文献  データ構造とアルゴリズム 培風館  A.V.Aho等著

2 '//'はC++のコメントだと言うことはご存知ですね。私は普段C++
を使っていますので気になりませんが、ここはC言語限定のようなので
念のため指摘。


No.14584

Re:多分木をつくる
投稿者---NykR(2004/06/12 12:25:52)


>2 '//'はC++のコメントだと言うことはご存知ですね。私は普段C++
>を使っていますので気になりませんが、ここはC言語限定のようなので
>念のため指摘。

ISOでもJISでもANSIでも、C++スタイルのコメントをCで使うことは今では正式に認められています。


No.14588

Re:多分木をつくる
投稿者---prontera(2004/06/12 13:01:16)


>2 '//'はC++のコメントだと言うことはご存知ですね。私は普段C++
>を使っていますので気になりませんが、ここはC言語限定のようなので
>念のため指摘。

本来は/* 〜 */だったですね。
学校の環境では'//'が通るのでつい書いてしまいました。
C言語関係掲示板ということなのでもう少し気をつけて書き込みします。


No.14603

Re:多分木をつくる
投稿者---NykR(2004/06/13 14:36:57)


>本来は/* 〜 */だったですね。
>学校の環境では'//'が通るのでつい書いてしまいました。
>C言語関係掲示板ということなのでもう少し気をつけて書き込みします。

ですから、'//'は、Cの正しいコメントだと言っているのですが。