C言語関係掲示板

過去ログ

No.963 2分探索木を用いて指定のデータを探索

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

2分探索木について
投稿者---バリアブル(2004/02/03 02:08:56)


2分探索木を用いて指定のデータを探索するプログラムを作成中なのですが、分からないことがあります。下記のプログラムを実行するとエラーが出ます。そのエラーは関数に渡す引数が構造体なのに対して再帰関数の呼び出しの1つ目の部分がint型になっている部分です。どうやって間違いを正せばいいのか分からなくて、悩んでます。
プログラム作成の条件としては、
1.構造体配列を使う
2.再帰関数を使う
です。
説明が足りてないかもしれないので、どんどん聞いてください。
どうかご指摘お願いします。m(_ _)m

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

struct node{
    int left;
    char name[20];
    int right;
}a;

struct node *search(struct node *root,char *x);

main(void)
{
    char key[20];
    struct node *p_data;
    
    struct node *root;
    struct node a[]={
        {1,"machilda",2},{3,"candy",4},{5,"rolla",-1},{-1,"ann",-1},
        {6,"emy",7},{-1,"nancy",-1},{-1,"eluza",-1},{-1,"lisa",-1}
    };
    
    root=a;
    
    printf("指定のデータ(名前):");
    scanf("%s",key);
    
    p_data=search(root,key);
    
    printf("%s",p_data->name);
    
}

struct node *search(struct node *root,char *x)
{
    int n;
    
    n=strcmp(root->name,x);
    
    if(root->left==-1 || root->right==-1 || n==0){
        return root;
    }
    else{
        if(n>0){
            search(root->left,x);←この部分でエラー
        }
        else{
            search(root->right,x);←この部分でエラー

        }
    }   
}



No.12437

Re:2分探索木について
投稿者---こば(2004/02/03 03:43:36)


>struct node *search(struct node *root,char *x)
>・・・
> search(root->left,x);←この部分でエラー

引数がnodeポインタなのだからintを渡しても受付けてもらえないかも
たぶん&root[root->left]のようなイメージでお使いなのだと思いますが
次の検索データのポインタを渡してしまったら、
配列位置(root->left)の意味がなくなるので、
引数には配列と検索位置(配列位置)が別個に必要かもしれません。
それと関数を抜ける場合の戻値も忘れないで下さいね。

間違ってたらごめんなさい。

No.12438

Re:2分探索木について
投稿者---あかま(2004/02/03 08:50:40)


struct node *search(struct node *root,char *x)
のようにポインタで渡すなら
普通は構造体へのポインタが必要になりますので、int型ではなく
struct node{
    struct node *left;
    char name[20];
    struct node *right;
}a;

となります。
でも意外とa[]のように配列で宣言して、添え字で次のノードを表してもいけそうですね。
ノードの追加はできませんが。
とりあえずエラーが出ないように修正しときました。


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

struct node{
    int left;
    char name[20];
    int right;
};
struct node a[]={
        {1,"machilda",2},{3,"candy",4},{5,"rolla",-1},{-1,"ann",-1},
        {6,"emy",7},{-1,"nancy",-1},{-1,"eluza",-1},{-1,"lisa",-1}
};

struct node *search(struct node *root,char *x);

main(void)
{
    char key[20];
    struct node *p_data;
    
    struct node *root;
    
    root=a;
    
    printf("指定のデータ(名前):");
    scanf("%s",key);
    
    p_data=search(root,key);
    
    printf("%s",p_data->name);
    
}

struct node *search(struct node *root,char *x)
{
    int n;
    
    n=strcmp(root->name,x);
    
    if(root->left==-1 || root->right==-1 || n==0){
        return root;
    }
    else{
        if(n>0){
            search(&a[root->left],x);
        }
        else{
            search(&a[root->right],x);
        }
    }
}

で、search()は戻り値返すのがうまく行かない気がするんだけど、きっちり帰ってきてうまくいくなぁ。
search(&a[root->left],x);
のあと再帰で帰ってきて戻り値はどうなるのって思ったんだけど。
ワタシが寝ぼけてるのかしら。。。

手元の環境gcc


No.12447

Re:2分探索木について
投稿者---バリアブル(2004/02/03 17:29:30)


こばさん、あかまさんありがとうございました。

指摘されて初めて気付いたのですが再帰関数の戻り値がなかったですね。
でもプログラムはちゃんと動くんですよね・・・なんでだろ?
参考書などの2分木探索を見ても、戻り値は書かれていないですし・・・。
プログラムが動けばいいのかな。

それとあかまさんプログラムを修正していただきありがとうございます。
あと、
if(root->left==-1 || root->right==-1 || n==0)
の 一つ目の ||(または) の部分を &&(かつ) に変えないといけませんでした。
そうしないと『nancy』と入力しても『rolla』と表示されてしまったので。

大変参考になりました。
アドバイスを頂いたお二方、どうもありがとうございました。
また、なにかありましたらよろしくお願いします。