90222


このプログラムを実行したときに挿入してない値を探索した場合、segmentation faultが出ます。原因はなんでしょうか？

[code]

    #include <stdio.h>
    #include <stdlib.h>
    
    // キー比較関数の定義
    #define keycmp(x, y)  ((x)-(y))
    
    // KEY 型を定義（正体は int 型）
    typedef int KEY;
    
    // NODE型の構造体定義
    typedef struct node {
        struct    node    *left, *right;  // 左右部分木へのポインタ
        KEY       key;                    // データ部
    } NODE;
    
    // 各種関数のプロトタイプ宣言
    void init(void);
    NODE *insert( NODE node );
    int delete(KEY key);
    
    void clear(void);
    void dispsub(NODE *p);
    void disp(int n);
    
    // 探索関数のプロトタイプ宣言
    NODE *search( KEY key);
    
    // ツリーのルートを保持するポインタ変数の宣言
    NODE    *root;
    
    // 使用可能なノードの最大数を定数として宣言
    #define     N   31
    
    // 表確認関数で使用する変数の宣言
    int         exist[N+1];
    NODE        x[N+1];
    
    //------------------------------
    //    メイン関数（対話的な動作確認用）
    //------------------------------
    int    main(void)
    {
        char    buff[8];
        int        succeeded;
        KEY        key;
        NODE    node, *resNode;
        
        // 木の初期化
        init();
        
        // メニューループ
        while( 1 ){
            
            // メニュー表示と選択
            printf("Sn: 探索，In: 挿入，Dn: 削除, Q: 終了 ? ");
            gets(buff);
            key = atoi(&buff[1]);
            
            // メニュー形式による処理分岐
            switch( buff[0] ){
                    
                    // (1) 探索の場合
                case 'S':    case 's':
                    
                    // 探索関数を呼ぶ
                    resNode = search(key);
                    
                    // 結果を表示する
                    if( resNode != NULL )
                        printf("\nキー %d を見つけました．\n", resNode->key);
                    else
                        printf("\nキー %d は見つかりません．\n", resNode->key);
                    break;
                    
                    //(2) 挿入の場合
                case 'I':    case 'i' :
                    
                    // 挿入関数を呼ぶ
                    node.key = key;
                    resNode = insert( node );
                    
                    // 結果を表示する
                    if( resNode != NULL )
                        printf("キー %d を挿入しました．\n", key);
                    else
                        printf("キー %d は挿入済みです．\n", key);
                    break;
                    
                    //(3) 削除の場合
                case 'D':    case 'd':
                    
                    // 削除関数を呼ぶ
                    succeeded = delete( key );
                    
                    // 結果を表示する
                    if( succeeded )
                        printf("キー %d を削除しました．\n", key);
                    else
                        printf("キー %d を削除できません．\n", key);
                    break;
    
                    //(4) 終了の場合
                case 'Q':    case 'q':
                    return 0;
                    
                    // その他の入力を無視する
                    
            }
            // ２分探索木を表示する
            clear();
            dispsub(root);
            disp(N);
        }
        
        return 0;
    }
    
    //------------------------------
    //  初期化関数
    //------------------------------
    void init(void)
    {
        root = NULL;
    }
    
    //------------------------------
    //  挿入関数
    //------------------------------
    NODE *insert( NODE node )
    {
        NODE    **pp, *pos;
        int        res;
        
        pp = &root;
        
        while( *pp != NULL ) {
            res = keycmp( node.key, (*pp)->key );
            if( res == 0 )        return NULL;
            else    if( res < 0 )    pp = &(*pp)->left;
            else    pp = &(*pp)->right;
        }
        
        /* ノード型のメモリを確保する（確保できなければ終了する） */
        if( (pos = malloc(sizeof(NODE))) == NULL )    exit(1);
        
        *pos = node;
        pos->left = pos->right = NULL;
        *pp = pos;
        return    pos;
    }
    
    //------------------------------
    //  削除関数
    //------------------------------
    int delete(KEY key)
    {
        NODE    **pp, **qq, *q, *r;
        int        res;
        
        pp = &root;
        
        while( *pp != NULL){
            
            res = keycmp( key, (*pp)->key );
            
            if( res == 0 ){
                q = *pp;
                if( q->left == NULL ){
                    *pp = q->right;
                    free(q);
                } else if( q->right == NULL ){
                    *pp = q->left;
                    free(q);
                } else {
                    qq = &q->left;
                    while( (*qq)->right != NULL )    qq = &(*qq)->right;
                    q->key = (*qq)->key;
                    r = *qq;
                    *qq = (*qq)->left;
                    free(r);
                }
                return    1;
                
            } else    if( res < 0 )    pp = &(*pp)->left;
            else            pp = &(*pp)->right;
        }
        return    0;
    }
    
    //====================================
    //  これ以降は動作結果の確認用の関数群
    //====================================
    
    //------------------------------
    //  関数 dispsub 用の補助関数
    //------------------------------
    void clear(void)
    {
        int    i;
        for( i=1; i<=N; i++)
            exist[i] = 0;
    }
    
    //------------------------------
    //  関数 disp 用の補助関数
    // ------------------------------
    void dispsub(NODE *p)
    {
        static    int    number = 1 ;
        
        if( p == NULL )        return;
        if( number > N )     return;
        
        exist[number] = 1;
        x[number].key = p->key;
        number *= 2;
        dispsub(p->left);
        number++;
        dispsub(p->right);
        number /= 2;
    }
    
    //------------------------------
    //  表示関数
    // ------------------------------
    void disp(int n)
    {
        int    i, k, count, margin, padding;
        k = 1;    i = 1;    margin = 8;
        
        while( margin <= n )    margin*=2;
        
        while( i<=n ){
            if( i==k ){
                count = margin;
                padding = margin*2 - 2;
                k *= 2;
                margin /= 2;
                putchar('\n');
            } else
                count = padding >= 0 ? padding : 0;
            
            while( count-- )    putchar(' ');
            
            if( exist[i] )    printf("%2d", x[i].key);
            else    printf("--");
            i++;
        }
        putchar('\n');
    }
    
    //====================================
    //    ２分木の探索関数
    //====================================
    
    NODE *search( KEY key)
    {
        NODE *v;
        v=root; //rootにより初期位置を格納
        int res;
        res = keycmp( key, v->key ); //keyを比較
        while(v!=NULL){
            if(res==0){ //渡された値と一致している場合
                return(v);
            }
            if(res>0){ //渡された値より大きい場合
                printf("%d ",v->key);//探索経過表示
                v=v->right;
    
            }
            else{ //渡された値より小さい場合
                printf("%d ",v->key);//探索経過表示
                v=v->left;
            }
        }
        free(v);
        return NULL; //vが当てはまらない場合NULLを返す
    }
    
[/code]

実行例

[code]

    Sn: 探索，In: 挿入，Dn: 削除, Q: 終了 ? i56
    キー 56 を挿入しました．
    
                                    56
                    --                              --
            --              --              --              --
        --      --      --      --      --      --      --      --
      --  --  --  --  --  --  --  --  --  --  --  --  --  --  --  --
    Sn: 探索，In: 挿入，Dn: 削除, Q: 終了 ? i32
    キー 32 を挿入しました．
    
                                    56
                    32                              --
            --              --              --              --
        --      --      --      --      --      --      --      --
      --  --  --  --  --  --  --  --  --  --  --  --  --  --  --  --
    Sn: 探索，In: 挿入，Dn: 削除, Q: 終了 ? s22
    zsh: segmentation fault 
    
[/code]


CC BY-SA 4.0
2022-07-26T16:01:14.800
90218
2022-07-27T01:54:40.930
2022-07-27T01:29:45.363
53702
53702
question
c
２分木探索のプログラムで segmentation fault が発生する場合がある


以下の部分で発生していますね。

[code]

            case 'S':    case 's':
                
                // 探索関数を呼ぶ
                resNode = search(key);
                
                // 結果を表示する
                if( resNode != NULL )
                    printf("\nキー %d を見つけました．\n", resNode->key);
                else
                    printf("\nキー %d は見つかりません．\n", resNode->key);//-->この行
                break;
    
[/code]

`if( resNode != NULL
)`の`else`の部分であるので、`resNode`は`NULL`なのに`resNode->key`にアクセスしているために発生しています。

対処は以下のように`resNode->`の部分は削って`key`だけにすることでしょう。

[code]

    printf("\nキー %d は見つかりません．\n", key);
    
[/code]


CC BY-SA 4.0
2022-07-27T01:41:36.163
90222
2022-07-27T01:54:40.930
2022-07-27T01:54:40.930
26370
26370
90218
answer