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

typedef struct nod{
    int data;
    struct nod *left,*right;
}NOD;

NOD * generate(NOD * root)
{
    NOD *r,*p;
    int d=-1,value,line,position,i,f,v;
    if(root==NULL)
    {
        do{
            printf("Would you like to create the root node?\n\n1 - yes\n0 - no\n");
            scanf("%d",&d);
            switch(d)
            {
                case 1:
                    printf("Value=");
                    scanf("%d",&value);
                    root=add_root(value);
                    break;
                case 0:
                    return NULL;
                    break;
                default:
                    printf("Command unrecognized!\n");
                    break;
            }
        } while(d==-1);
        if(root!=NULL)
                printf("Root node successfully created!\n");
        else
            printf("Error: could not create root node!\n");
        d=-1;
        do{
            printf("Continue adding nodes?\n\n1 - yes\n0 - no\n");
            scanf("%d",&d);
            switch(d)
            {
                case 1:
                    printf("Insert the line and the position of the node you wish to add (root node has line=0, position=0)\nLine=");
                    scanf("%d",&line);
                    printf("Position ( less or equal with 2^$line-1 )=");
                    scanf("%d",&position);
                    printf("Value=");
                    scanf("%d",&value);
                    r=p=root;
                    for(i=line-1;i=0;i--)  
                    {
                        f=power(2,i);
                        if(position & f == f)   // if the i-(st,nd,rd,th) bit of "position" is 1, then (position & f == f) is true and *r will go right
                        {
                            p=r;
                            r=r->right;
                            v=1;
                        }
                        else
                        {
                            p=r;
                            r=r->left;
                            v=0;
                        }
                    }
                    if(v==0)
                        p=add_left(&r,value);
                    if(v==1)
                        p=add_right(&r,value);

                    break;
                case 0:
                    return root;
                    break;
                default:
                    printf("Command unrecognized!\n");
                    break;
            }
        } while(d==-1);
    }
    else
    {
        ...
    }

NOD * add_left(NOD **p,int value)
{
    NOD * r;
    r=malloc(sizeof(NOD));
    r->data=value;
    r->left=NULL;
    r->right=NULL;
    (*p)->left=r;
    return r;
}

NOD * add_right(NOD **p,int value)
{
    NOD * r;
    r=malloc(sizeof(NOD));
    r->data=value;
    r->left=NULL;
    r->right=NULL;
    (*p)->right=r;
    return r;
}

NOD * add_root(int value)
{
    NOD * x;
    x=malloc(sizeof(NOD));
    x->data=value;
    x->left=NULL;
    x->right=NULL;
    return x;
}

}
int main() {
    NOD *root=NULL;
    root=generate(root);
    return 0;
}

二分木を作成するプログラムを作成しようとしましたが、SIGSEGVセグメンテーション違反が発生し続け、その理由がわかりません。私が間違ったことを教えてください。

if(position & f == f)   // if the i-(st,nd,rd,th) bit of "*position*" is 1,
                        // then (position & f == f) is true and *r will go right

この部分についてどう思いますか？

  • lineはツリーのレベルです（rootにはline = 0があります）

  • positionは、ノードの左から右への位置です（ルートの位置は0です）。

4

2 に答える 2

3

あなたはすでに問題のある部分を太字にしています：

if(position & f == f)

==よりも優先度が高い&ため、次のように解析されます。

if(position & (f == f))

if (position & 1)そして、あなたが望むものではなく、と同じです。

さらに、ループ条件が間違っています

for(i=line-1;i=0;i--)

テストはおそらくである必要がありますi >= 0。そうでない場合、ループは実行されません（i = 00と評価される割り当てです）。

これらが修正され、ループが実行された場合、最初の反復rがnullポインターになった後、次のループの反復により、でクラッシュが発生しますr = r->right;。または、ループが1回だけ繰り返される場合は、add_left(&r,value);（またはadd_right）アクセスしようとしている最後から2番目の行のnullポインターを逆参照します。そのleft（またはright）ポインタ：

NOD * add_left(NOD **p,int value)
{
    NOD * r;
    r=malloc(sizeof(NOD));
    r->data=value;
    r->left=NULL;
    r->right=NULL;
    (*p)->left=r;          // *p == NULL here
    return r;
}
于 2012-05-27T23:52:30.783 に答える
0

この行で

for(i=line-1;i=0;i--)

私はあなたが意味したと思います

for(i=line-1;i!=0;i--)

それ以外の場合、ループは実行されません（i=0に評価されfalseます）。これによりv、未定義の値が発生します（初期化されないため）。これによりセグメンテーション違反が発生する可能性はほとんどありませんが、ルートの左右のサブツリーを上書きすると、メモリリークが発生します。

また、デフォルトのswitchブランチはスキャンされた値を変更しませんd。つまり、ルートを続行しますNULL（チェックするエラーブランチroot != NULLは関数を終了しません）。

于 2012-05-28T00:23:26.647 に答える