Ｃ言語関係掲示板過去ログ１２０４

過去ログ

No．１２０４　英単語出力の木構造

No.15743

英単語出力の木構造
投稿者---naru(2004/07/21 19:46:37)

こんばんわ毎回お世話になっております。今回木構造について、プログラムの勉強を進めております。今回作成しようとしておりますプログラムは、英単語を入力して、現在のノードの英単語に対して次のノードの英単語が辞書順で大きい場合、左の幹へ。小さい場合右へと作成されていく木構造を作っております。木構造の出力を表示するプログラムは作成できたのですが、木の高さを出力することがどうしてもできなくて、質問させていただきました。どうかよろしくお願いいたします。ソースは下記のものを用いました。


 #include <stdio.h>
  #include <string.h>

  struct tree_type{
          char data[20];
          struct tree_type *left, *right;
  };

typedef struct tree_type Tree;
  Tree *makenode( char *x, Tree *current );
  Tree *getmemory(void);
  void printnode(Tree *current, int depth );
  int inorder( Tree * );

  int main(void)
  {
       char x[20];
       int depth;
       Tree *root;
       root = NULL;
       while( scanf("%s", x) != EOF )
       {
          root = makenode( x,  root );
   }
      depth = 0;
      printnode( root, depth );
     
      printf("\n");

     return 0;
 }
//-----------------------------------------------------------------

  Tree *makenode( char *x, Tree *current )
  {
       if( current == NULL )
       {
              current = (Tree *)malloc(sizeof(Tree));
             strcpy( current->data, x );
           current->left = current->right = NULL;
    }
      else if( strcmp(current->data, x) > 0 )
    {
           current->left = makenode(x, current->left);
   }
    else if( strcmp(current->data, x) < 0 )
     {
           current->right = makenode(x, current->right);
     }
     return( current );
  }

//------------------------------------------------------------------
Tree *getmemory(void)
  {
      return( (Tree *)malloc(sizeof(Tree)) );
  }

//------------------------------------------------------------------
 void printnode(Tree *current, int depth )
  {
       int i;

      depth++;
      if( current->right== NULL )
    {
            for( i=1; i<=depth; i++) printf("     ");
            printf("%-20s\n", current->data);
    }
     else
    {
             printnode( current->right, depth );
           for( i=1; i<=depth; i++) printf("     ");
            printf("%-20s\n", current->data);
    }
      if( current->left!=NULL ) printnode( current->left, depth );
  }


//---------------------------------------------------------------------

No.15744		Re:英単語出力の木構造投稿者---ぽこ(2004/07/21 19:59:13)
		上手く動いているようですが。。どんな動作を期待して、どんな結果になるのでしょうか? #ただ単にdepthを出力するだけでは駄目?

No.15746		Re:英単語出力の木構造投稿者---naru(2004/07/21 20:17:35)
		>上手く動いているようですが。。 >どんな動作を期待して、どんな結果になるのでしょうか? > >#ただ単にdepthを出力するだけでは駄目? レスありがとうございます。このプログラム自体は正常に動くのですが、 main関数内のprintnode()の後にprintf関数を入れると、 printnode( root, depth ); printf("木の高さは,%dです\n",depth); printf("\n"); 結果は、 ------------------------------------------------------------ $ ./a.out word english get boy act foget Japanese America rain hot hut cap word rain hut hot get foget english cap boy act Japanese America 木の高さは,1073990033です ----------------------------------------------------------------- となり、木の高さを表示することができないのです。説明が不足していてすみません。

No.15748

Re:英単語出力の木構造
投稿者---ぽこ(2004/07/21 20:44:23)

なぜprintnode()の引数を表示すると駄目か、ということは
とりあえず置いといて、木の深さを求める関数を作ってみました。

printnode()へのマージはお任せします。

int getdepth(Tree* current)
{
    int right_depth;
    int left_depth;

    // 実体がない場合
    if(current == NULL) {
        return 0;
    }

    // 子供がいない場合
    if((current->left == NULL) && (current->right == NULL)) {
        return 1;
    }

    // 右の子の深さを調べる
    right_depth = getdepth(current->right);

    // 左の子の深さを調べる
    left_depth = getdepth(current->left);

    // より深い方を返す
        return right_depth > left_depth ? right_depth + 1: left_depth + 1;
}

No.15753

Re:英単語出力の木構造
投稿者---naru(2004/07/21 21:26:13)

ありがとうございます。

// より深い方を返す
        return right_depth > left_depth ? right_depth + 1: left_depth + 1;

すみませんが、この部分がどういった操作を表しているのか
少し分からないです。勉強不足ですみませんが少し詳しく
教えていただけませんか。

No.15762		Re:英単語出力の木構造投稿者---ぽこ(2004/07/21 22:49:20)
		以下と同じ振る舞いです。 if(right_depth > left_depth) { return right_depth + 1; else { return left_depth + 1; } 右の子の深さと左の子の深さを比較し、大きいほうに自身の深さ(1)を足し、返しています。

No.15764		Re:英単語出力の木構造投稿者---naru(2004/07/21 22:56:35)
		>以下と同じ振る舞いです。 ><pre> if(right_depth > left_depth) { return right_depth + 1; else { return left_depth + 1; } </pre> >右の子の深さと左の子の深さを比較し、大きいほうに自身の深さ(1)を >足し、返しています。ありがとうございます。よく分かりました。ソースはうまく書けばきれいにまとめる事ができるのですね。ちょっとした感動です。

No.15745

Re:英単語出力の木構造
投稿者---ぽこ(2004/07/21 20:06:04)

あと、printnode()ですが、以下のように書いた方が
すっきりしますよ。

void 
printnode(Tree *current, int depth )
{
    int i;

    depth++;
    
    if(current == NULL) {
        return;
    }

    //右の子を出力
     printnode( current->right, depth );

    // 自身を出力
    for( i=1; i<=depth; i++) printf("     ");
    printf("%-20s\n", current->data);
      
    // 左の子を出力
    printnode( current->left, depth );
}

No.15747		Re:英単語出力の木構造投稿者---naru(2004/07/21 20:22:38)
		>あと、printnode()ですが、以下のように書いた方が >すっきりしますよ。 > ><pre> void printnode(Tree *current, int depth ) { int i; depth++; if(current == NULL) { return; } //右の子を出力 printnode( current->right, depth ); // 自身を出力 for( i=1; i<=depth; i++) printf(" "); printf("%-20s\n", current->data); // 左の子を出力 printnode( current->left, depth ); } </pre> なるほど、確かに私のは見にくいですね。ありがとうございます、勉強になります。

No.15749

Re:英単語出力の木構造
投稿者---NykR(2004/07/21 20:48:53)

> 木の高さを出力することがどうしてもできなくて、質問させていただきました。

depthの最大値をどこかに保存しておくといいです。

1.グローバル変数
2.呼び出し元のローカル変数に保存する。
ポインタをprintnodeに渡すか、戻り値で受け取る。
3.木のrootへのポインタと木の高さをメンバーとする構造体を作る。

2.あたりが簡単でいいと思います

int main(void)
{
    // ...snip
    printnode( root, depth, &maxdepth ); // printnodeの引数を一つ増やす
    printf("木の高さは,%dです\n",maxdepth);
    printf("\n");

    return 0;
}

あと

    for( i=1; i<=depth; i++) printf("     ");
    printf("%-20s\n", current->data);

は
printf("%*s%-20s\n", depth * 5, "", current->data);

としてもいいです。

No.15751		Re:英単語出力の木構造投稿者---naru(2004/07/21 21:07:59)
		> >depthの最大値をどこかに保存しておくといいです。 > >1.グローバル変数 >2.呼び出し元のローカル変数に保存する。 > ポインタをprintnodeに渡すか、戻り値で受け取る。 >3.木のrootへのポインタと木の高さをメンバーとする構造体を作る。 > >2.あたりが簡単でいいと思います > int main(void) { // ...snip printnode( root, depth, &maxdepth ); // printnodeの引数を一つ増やす printf("木の高さは,%dです\n",maxdepth); printf("\n"); return 0; } >あと ><pre> for( i=1; i<=depth; i++) printf(" "); printf("%-20s\n", current->data); は printf("%s%-20s\n", depth 5, "", current->data);</pre> > >としてもいいです。ありがとうございます。早速プログラムを直してみます。

No.15756

変更してみましたが・・
投稿者---naru(2004/07/21 21:48:18)

プログラムを以下のように変更してみました。

============================================================-

#include <stdio.h>
  #include <string.h>

struct tree_type{
  char data[20];
  struct tree_type *left, *right;
};

typedef struct tree_type Tree;
Tree *makenode( char *x, Tree *current );
Tree *getmemory(void);
void printnode(Tree *current, int depth,int maxdepth );
int inorder( Tree * );

int main(void)
{

  char x[20];
  int depth,maxdepth;
  Tree *root;
  root = NULL;
  while( scanf("%s", x) != EOF )
    {
      root = makenode( x,  root );
    }
  depth = 0;
  printnode( root, depth,&maxdepth );
  printf("木の高さは%d",maxdepth);
  printf("\n");

  return 0;
}
//-------------------------------------------------------------
Tree *makenode( char *x, Tree *current )
{
  if( current == NULL )
    {
      current = (Tree *)malloc(sizeof(Tree));
      strcpy( current->data, x );
      current->left = current->right = NULL;
    }
  else if( strcmp(current->data, x) > 0 )
    {
      current->left = makenode(x, current->left);
    }
  else if( strcmp(current->data, x) < 0 )
    {
      current->right = makenode(x, current->right);
    }
  return( current );
}

//------------------------------------------------------------------
Tree *getmemory(void)
{
  return( (Tree *)malloc(sizeof(Tree)) );
}

//----------------------------------------------------------------
void
printnode(Tree *current, int depth,int maxdepth )
{
  int i;

  depth++;

  if(current == NULL) {
    return;
  }
==========================================================
結果としましては、
==========================================================
$ ./a.out
tree
www
get
vod
vay
bin
make
find
fine
zoo
air
cluod
hat
               zoo
          www
               vod
                    vay
     tree
               make
                    hat
          get
                         fine
                    find
                         cluod
               bin
                    air
木の高さは1073990033
==========================================================
となりました。木の高さがうまく出力されていないのですがどういった問題があるのでしょうか？
また、警告としまして

treeshin1.c: 関数 `main' 内:
treeshin1.c:27: 警告: 引数 3 個の `printnode' を渡しますにより、キャストなしでポインタから整数を作りました

とでました。

No.15758

Re:変更してみましたが・・
投稿者---NykR(2004/07/21 22:06:00)

引用順を変えました。

また、警告としまして

treeshin1.c: 関数 `main' 内:
treeshin1.c:27: 警告: 引数 3 個の `printnode' を渡しますにより、キャストなしでポインタから整数を作りました

とでました。

printnode関数のプロトタイプは

void printnode(Tree *current, int depth,int maxdepth );

になっていますが、ポインタを渡すのですから、ポインタを受け取らなければなりません。

void printnode(Tree * current, int depth, int * maxdepth);

void
printnode(Tree *current, int depth,int maxdepth )
{
  int i;

  depth++;

  if(current == NULL) {
    return;
  }
==========================================================

最大値の保存はどこでやっているのでしょうか？

No.15759

Re:変更してみましたが・・
投稿者---naru(2004/07/21 22:27:11)

すみません。maxdepthについてのprintnode()が記載抜けしていました。
ポインタで渡すところ抜けていました。気をつけます。
変更後のソースは下記です。

#include <stdio.h>
  #include <string.h>

struct tree_type{
  char data[20];
  struct tree_type *left, *right;
};

typedef struct tree_type Tree;
Tree *makenode( char *x, Tree *current );
Tree *getmemory(void);
void printnode(Tree *current, int depth,int *maxdepth );
int inorder( Tree * );

int main(void)
{

  char x[20];
  int depth,maxdepth;
  Tree *root;
  root = NULL;
  while( scanf("%s", x) != EOF )
    {
      root = makenode( x,  root );
    }
  depth = 0;
  printnode( root, depth,&maxdepth );
  printf("木の高さは%d", maxdepth);
  printf("\n");

  return 0;
}
//-----------------------------------------------------------------

Tree *makenode( char *x, Tree *current )
{
  if( current == NULL )
    {
      current = (Tree *)malloc(sizeof(Tree));
      strcpy( current->data, x );
      current->left = current->right = NULL;
    }
  else if( strcmp(current->data, x) > 0 )
    {
      current->left = makenode(x, current->left);
    }
  else if( strcmp(current->data, x) < 0 )
    {
      current->right = makenode(x, current->right);
    }
  return( current );
}

//-----------------------------------------------------

Tree *getmemory(void)
{
  return( (Tree *)malloc(sizeof(Tree)) );
}

//------------------------------------------------------------------
void
printnode(Tree *current, int depth,int *maxdepth )
{
  int i;

  depth++;

  if(current == NULL) {
    return;
  }

  //右の子を出力
  printnode( current->right, depth,maxdepth );

  // 自身を出力
  for( i=1; i<=depth; i++) printf("     ");
  printf("%-20s\n", current->data);

  // 左の子を出力
  printnode( current->left, depth,maxdepth );
  *maxdepth = depth;
}



//---------------------------------------------------------------------

結果といたしましては、

$ ./a.out
tree
get
fight
dwnt
sdga
ga
ghryr
dgdd
ghffh
sdafg
dgd
dgdg
aagdgh
sdfg
     tree
               sdga
                              sdfg
                         sdafg
                    ghryr
                         ghffh
          get
                    ga
               fight
                    dwnt
                              dgdg
                         dgdd
                              dgd
                                   aagdgh
木の高さは1

となりました。明らかに木の高さは１では無いのですが、maxdepthで上手く最大値を読み込めていないのでしょうか？

No.15761		Re:変更してみましたが・・投稿者---NykR(2004/07/21 22:46:11)
		> 明らかに木の高さは１では無いのですが、maxdepthで上手く最大値を読み込めていないのでしょうか？ depthは増えたり減ったりします。ですから、maxdepthは、・depthが増えたとき。・maxdepthがdepthより小さいとき。にのみ変更するようにすればいいです。

No.15763		Re:変更してみましたが・・投稿者---naru(2004/07/21 22:53:02)
		>> 明らかに木の高さは１では無いのですが、maxdepthで上手く最大値を読み込めていないのでしょうか？ > >depthは増えたり減ったりします。 >ですから、maxdepthは、 > >・depthが増えたとき。 >・maxdepthがdepthより小さいとき。 > >にのみ変更するようにすればいいです。ありがとうございます。しかし、・depthが増えたとき。 >・maxdepthがdepthより小さいとき。とはどのようにすればよいのでしょうか？ printnode()の中でそんな細かな設定はできるのでしょうか？

No.15774

Re:変更してみましたが・・
投稿者---ニタチ(2004/07/22 09:45:40)

>>> 明らかに木の高さは１では無いのですが、maxdepthで上手く最大値を読み込めていないのでしょうか？

　printnode()ではどのように木をたどっていきますか？
　一番下までたどって・・・、最後は一番上のprintnode()で終わります。
　ですから、その時のdepth、つまり1が最後にmaxdepthに代入されますので、
　このままではどんなに木を深くしようが1になります。


>・depthが増えたとき。
>>・maxdepthがdepthより小さいとき。
>とはどのようにすればよいのでしょうか？
>printnode()の中でそんな細かな設定はできるのでしょうか？

　if文で・maxdepthがdepthより小さいとき、

    *maxdepth = depth;

　とすればいいと思います。

No.15775

Re:変更してみましたが・・
投稿者---ニタチ(2004/07/22 10:01:21)

あと、せっかく良いテクニックを教えていただいたので、
こちらも使ってみてはどうでしょうか？

  // 自身を出力
  for( i=1; i<=depth; i++) printf("     ");
  printf("%-20s\n", current->data);

                ↓

 // 自身を出力
 printf("%*s%-20s\n", depth * 5, " ", current->data);

No.15777

Re:変更してみましたが・・
投稿者---naru(2004/07/22 12:27:31)

あと、せっかく良いテクニックを教えていただいたので、
こちらも使ってみてはどうでしょうか？

  // 自身を出力
  for( i=1; i<=depth; i++) printf("     ");
  printf("%-20s\n", current->data);

                ↓

 // 自身を出力
 printf("%*s%-20s\n", depth * 5, " ", current->data);


こんにちわ。いつもありがとうございます。
いつもながら皆さんの知識には驚かされるばかりです。
プログラム頑張ってみます!!