C言語関係掲示板

過去ログ

No８９５　木構造　先に葉を作ってから根に繋げたい

[戻る]　[ホームページ]
No.557
木構造の自己参照型構造体について
投稿者---CALLET(2003/10/22 16:50:06)


はじめましてm(__)m
題名のとおり今、木構造な自己参照型構造体のプログラムを作成しています。
ここで、ちょっと問題がおきたのですが、子から親、つまり先に葉を作ってから根に繋げていく事はできないのでしょうか？
以下がぼくの考えたソースです。
#include <stdio.h>
#include <stdlib.h>
#define N 10

/*自己参照型構造体Tree*/
typedef struct Tree{
	int data;
	struct Tree *right;
	struct Tree *left;
}Tree;

/*プロトタイプ宣言*/
void print(Tree *oya);
Tree* dainyu(Tree *oya,int i,int a[]);
void alloc(Tree *oya);

int main(void){
	
	Tree oya;				/*親の構造体*/
	int i;				/*カウンタ変数*/
	int a[N] = {1,2,3,4,5,6,7,8,9,10};	/*データ*/

	alloc(&oya);
	for (i = 0;i < N - 1;i++){
		oya.left = dainyu(&oya,i,a);
	}
	print(&oya);
	return(0);
}

/*領域の確保*/
void alloc(Tree *oya){
	
	oya = malloc(sizeof(Tree));
	if (oya == NULL){
		printf("malloc error\n");
		exit(1);
	}
	oya->right = NULL;
	oya->left = NULL;
}

/*データを格納*/
Tree* dainyu(Tree *oya,int i,int a[]){
	
	Tree left;	/*子の構造体*/
	Tree right;	/*同上*/
	
	alloc(&left);
	alloc(&right);
	left.data = a[i];
	right.data = a[i+1];
	oya->left = &left;
	oya->right = &right;
	return(oya);
}

/*格納したデータを表示*/
void print(Tree *oya){
	if (oya->left != NULL){
		print(oya->left);
	}
	if (oya->right != NULL){
		print(oya->right);
	}
	printf("%d\n",oya->data);
}

これを実行すると、print関数中で無限ループになってしまいます（＾＾；
つたないソースなので、色々とおかしい所があると思うのでご指摘お願いしますm(__)m
No.558
Re:木構造の自己参照型構造体について
投稿者---たいちう(2003/10/22 17:09:54)


１つめ：
main()のoya.left = dainyu(&oya,i,a);と
dainyu()のreturn(oya);が矛盾。

これによって、oya.left = &oyaになるので、
print()で無限ループになるのでしょう。
main()でdainyu()の戻り値を代入する必要はありません。

２つめ：
Tree leftとrightは、dainyu()の中でのみ有効です。
Tree *left とポインタを使い、allocも書き換えるべき。

３つめ：
プログラム終了時にfreeしましょう。

まだあるかも。
No.559
Re:木構造の自己参照型構造体について
投稿者---CALLET(2003/10/22 18:48:57)


>１つめ：
>main()のoya.left = dainyu(&oya,i,a);と
>dainyu()のreturn(oya);が矛盾。
>
>これによって、oya.left = &oyaになるので、
>print()で無限ループになるのでしょう。
>main()でdainyu()の戻り値を代入する必要はありません。

なるほど（＾＾；
ここが原因だったんですね（＾＾；

>２つめ：
>Tree leftとrightは、dainyu()の中でのみ有効です。
>Tree *left とポインタを使い、allocも書き換えるべき。

すいません、かなり初歩的なミスしてました（＾＾；

>３つめ：
>プログラム終了時にfreeしましょう。

言われてからその存在を知りました（＾＾；
もっとよく勉強しておかないとダメですね（＾＾；

>まだあるかも。

気づきましたらまたご指摘おねがいしますm(__)m

早いレスありがとうございました（＾＾
ご指摘を参考に頑張って直してみます（＾＾
No.560
Re:木構造の自己参照型構造体について
投稿者---CALLET(2003/10/22 22:11:36)


すいません、やっぱりわかりません(^^;
一つ目の問題がどうしても解決できません。
このプログラムだとまず子を作って、それを後で作った親にくっつけてから
またその親を後で作った親の子としなければなりませんよね？
その過程でどうしても先ほど指摘していただいた問題が起きてしまいます。
どうやって解決すればよいのでしょうか？
お願いしますm(__)m
No.561
Re:木構造の自己参照型構造体について
投稿者---かずま(2003/10/22 22:42:50)


どんな木を作ろうとしているのですか？
具体的に説明してください。

例えば、こんなふうにとか。
                  oya
                   |
        +----------+----------+
        |                     |
        |               +-----+-----+
        |               |           |
    +---+---+       +---+---+       |
    |       |       |       |       |
  +-+-+   +-+-+   +-+-+   +-+-+   +-+-+
  |   |   |   |   |   |   |   |   |   |
  1   2   3   4   5   6   7   8   9  10

No.565
Re:木構造の自己参照型構造体について
投稿者---CALLET(2003/10/22 23:21:00)


>どんな木を作ろうとしているのですか？
>具体的に説明してください。

えと、とりあえず作ろうとしているのは以下のような木です。
                      oya
                       |
                     +-+-+
                     |   |
                     9   10
                     |
                   +-+-+
                   |   |
                   8   9
                   |
                 +-+-+
                 |   |
                 7   8
                 |
               +-+-+
               |   |
               6   7
               |
             +-+-+
             |   |
             5   6
             |
           +-+-+
           |   |
           4   5
           |
         +-+-+
         |   |
         3   4
         |   
       +-+-+ 
       |   | 
       2   3
       |   
     +-+-+ 
     |   | 
     1   2

ただ、ぼくは別にこの木が作りたいのではなく、木を以下のように作りたいので、木の形にこだわりはありません。
    oya            oya            oya             oya
     |              |              |               |
   +-+-+    →    +-+-+    →    +-+-+     →    +-+-+　　･･･････
   |   |          |   |          |   |           |   |
   1   2          2   3          3   4           4   5
                  |              |               |
                +-+-+          +-+-+           +-+-+
                |   |          |   |           |   |
                1   2          2   3           3   4
                               |               |
                             +-+-+           +-+-+
                             |   |           |   |
                             1   2           2   3
                                             |
                                           +-+-+
                                           |   |
                                           1   2

それではおねがいしますm(__)m
No.566
Re:木構造の自己参照型構造体について
投稿者---かずま(2003/10/23 03:11:04)		 


#include <stdio.h>
#include <stdlib.h>

#define N  10

typedef struct Tree {
    int data;
    struct Tree *right;
    struct Tree *left;
} Tree;

void print(Tree *oya);
Tree *dainyu(Tree *oya, int i, int a[]);
Tree *alloc(int data, Tree *left, Tree *right);

int main(void)
{
    static int a[N] = {1,2,3,4,5,6,7,8,9,10};
    int i;
    Tree *oya = alloc(0, NULL, NULL);

    for (i = 0; i < N - 1; i++)
        oya = dainyu(oya, i, a);
    print(oya);
    return 0;
}

Tree *alloc(int data, Tree *left, Tree *right)
{
    Tree *oya = malloc(sizeof(Tree));
    if (oya == NULL) puts("out of memory"), exit(1);
    oya->data  = data;
    oya->right = right;
    oya->left  = left;
    return oya;
}

Tree *dainyu(Tree *oya, int i, int a[])
{
    oya->data = a[i];
    return alloc(0, oya, alloc(a[i+1], NULL, NULL));
}

void print(Tree *oya)
{
    if (oya->left  != NULL) print(oya->left);
    if (oya->right != NULL) print(oya->right);
    printf(" %d", oya->data);
}

No.568
Re:木構造の自己参照型構造体について
投稿者---CALLET(2003/10/23 14:52:26)


ありがとうございます（＾＾
既存の親を新しい親にしようと思うからいけなかったんですね（＾＾；
たいちうさま、かずまさまありがとうございましたm(__)m
No.615
Re:木構造の自己参照型構造体について
投稿者---かずま(2003/11/05 11:44:53)


> 既存の親を新しい親にしようと思うからいけなかったんですね（＾＾；

違います。次のように書けば、既存の親を新しい親にすることもできます。
Tree *dainyu(Tree *oya, int i, int a[])
{
    oya->left = alloc(a[i], oya->left, oya->right);
    oya->right = alloc(a[i+1], NULL, NULL);
    return oya;
}

No.664
Re:Re:木構造の自己参照型構造体について
投稿者---ceybord(2003/11/15 15:04:19)


いずれにしても、リスト構造をプログラムで書くのは難しいですね。
ポインタの知識がないとプログラムできないし、
ポインタの知識があっても、参照の構造を作らないといけないというのが厄介なところです。
リスト構造を学ぶには、メモリ参照の使い方と、リスト構造の概念の二つをよく把握すべきなのです。
それにしても、構造体変数のポインタの指す値の参照って、どうして分かりにくい表記(アロー記号)になるのでしょう？ほかと同じように*を使えばよさそうなものだと思うのですが、これには何か秘密があるのでしょうか？
No.666
Re:Re:木構造の自己参照型構造体について
投稿者---YuO(2003/11/15 15:46:28)


>それにしても、構造体変数のポインタの指す値の参照って、どうして分かりにくい表記(アロー記号)になるのでしょう？
>ほかと同じように*を使えばよさそうなものだと思うのですが、これには何か秘密があるのでしょうか？

struct foo { int bar };

があるとして，
struct foo * p

と宣言されているとき，
p->bar

は
(*p).bar

の略記です。


p.barで参照できないのは，コンパイラを作るときに簡単にするためだった，という話があります。

まぁ，.と->の使い分けがあったことはC++で意味をもつようになりましたが……。