リスト構造体のソート

[ぴかちゅう]

コード:

#include<stdio.h>

#define N 8 //最大値

typedef struct node{
        int value;
        struct node *next;
    }node_t;
    
node_t *list = NULL;

void sort_list(void){
    node_t *prev;
    node_t *node;
    node_t *keep;
    keep->value = N+1;
    while (keep->next->value == N){
        node = list;
        while (node->next == NULL){
            if(node->value < keep->value){
                keep = node;
            }
            prev = node;
            node = node->next;
        }
        prev->next = keep->next;
        node = list;
        while(node->value == keep->value+1){
            node = node->next;
        }
        keep->next = node;
    }
    keep->next->next = NULL;
}

Illegal instruction (core dumped)が出ます。コードの概要は１～８の数値（数値に被り無し）がint valueに入っており、適当な順番でリスト構造を持っています（該当コードは割愛。正しく動作すること確認済）。これをvalueの値で昇順に並べかえたいです。keepが最小値になるようリストを検索し、該当のノードをリストから削除。その後にkeepより1つ大きいvalueを持つノードを最小値削除後のリストから検索しkeepの後ろに繋げる。これを繰り返せばリストが昇順になるようノードをつなげ直すことができると考えました。

[みけCAT]

16行目

コード:

keep->value = N+1;

において、ローカル変数 keep を初期化せずにデリファレンスしているため、
変な所にアクセスしてしまい、危険です。

19行目

コード:

while (node->next == NULL){

のループにおいて、最初にこの条件が真であった場合、24行目

コード:

node = node->next;

によって node の値が NULL となり、19行目に戻った時にNULLをデリファレンスしてしまい危険です。
また、この条件が偽であった場合、prev が初期化されていない状態で26行目

コード:

prev->next = keep->next;

を実行してしまい、危険です。

例えばこんな感じでやるといいと思います。

コード:

void sort_list(void) {
    node_t head; /* 未ソートの要素 */
    node_t *result = NULL; /* ソート済みの要素 */
    head.next = list;
    /* 未ソートの要素が無くなるまで繰り返す */
    while (head.next != NULL) {
        node_t *maxNodeParent = &head; /* 最大値を持つノードの前のノード */
        node_t *maxNode;
        node_t *cur;
        /* 未ソートの要素の中でvalueが最大のものを検索する */
        for (cur = &head; cur->next != NULL; cur = cur->next) {
            if (maxNodeParent->next->value < cur->next->value) {
                /* 最大値の情報を更新する */
                maxNodeParent = cur;
            }
        }
        /* valueが最大のノードを未ソートの要素のリストから切り離し、 */
        maxNode = maxNodeParent->next;
        maxNodeParent->next = maxNode->next;
        /* ソート済みの要素の先頭に接続する */
        maxNode->next = result;
        result = maxNode;
    }
    /* ソート結果を書き戻す */
    list = result;
}

動作確認用

コード:

void print_list(void) {
    node_t* cur = list;
    if (cur == NULL) return;
    for (;;) {
        printf("%d", cur->value);
        if (cur->next == NULL) {
            putchar('\n');
            return;
        }
        putchar(' ');
        cur = cur->next;
    }
}

int main(void) {
    node_t nodes[N];
    int i;
    for (i = 0; i < N; i++) {
        if (scanf("%d", &nodes[i].value) != 1) return 1;
        nodes[i].next = i + 1 < N ? &nodes[i + 1] : NULL;
    }
    list = &nodes[0];
    print_list();
    sort_list();
    print_list();
    return 0;
}

[ぴかちゅう]

返信ありがとうございます。初期化にちゃんと配慮できていなかったのと、while文について初歩的なミスをしていることに気が付きました。
そのうえで改めてコード見て頂きたいです。わがままで申し訳にないのですが、実際に正しくソートができるか否かより、自分のコードのどこがまずくてエラー出ているかの原因を改めて教えて頂えると幸いです。

コード:

void sort_list(void){
    node_t *prev = NULL;
    node_t *node = NULL;
    node_t *keep = NULL;
    keep->value = N+1;
    while (keep->next->value != N){
        node = list;
        while (node->next != NULL){
            if(node->value < keep->value){
                keep = node;
            }
            prev = node;
            node = node->next;
        }
        prev->next = keep->next;
        node = list;
        while(node->value != keep->value+1){
            node = node->next;
        }
        keep->next = node;
    }
    keep->next->next = NULL;
}

エラーはIllegal instruction (core dumped)です

[みけCAT]

keep に NULL を代入した状態で

コード:

keep->value = N+1;

を実行しているため、通常の環境では不正な場所にアクセスしたとして強制終了になる可能性が高いでしょう。
デリファレンスしてその結果を評価するポインタは、
有効なオブジェクトを指していなければならず、例えば以下であってはいけません。
・NULL
・未初期化
・無効になった領域 (free()により開放された領域、スコープを抜けた後の静的でないローカル変数など)

[あたっしゅ]

デバッガー や 統合環境のデバッグ機能 を使わないのですか ?

統合環境 Visual Studio 2022 であれば、
カーソル位置まで実行は[Ctrl]+[F10]
ステップ実行(ステップ・イン)は [F11]
ステップ・オーバーは [F10]
です。

デバッガーを使わないのであれば

コード:

void sort_list(void){
    printf( "関数 sort_list に突入\n" );  
    node_t *prev = NULL;
    printf( "A 地点を通過\n" );  
    node_t *node = NULL;
    printf( "B 地点を通過\n" );  
    node_t *keep = NULL;
    printf( "C 地点を通過\n" );
    keep->value = N+1;
    printf( "D 地点を通過\n" );
    while (keep->next->value != N){
        printf( "while ループ内に突入\n" );
        node = list;
        printf( "E 地点を通過\n" );

とでもやって、どこで実行時エラーが出るか、絞りましょう。

Visual Studio 2022 でやったら、コンパイル時に、ちゃんと警告でるじゃん。

とりあえず、今は、ここまで。

[あたっしゅ]

#1＞ コードの概要は１～８の数値（数値に被り無し）がint valueに入っており、適当な順番でリスト構造を持っています（該当コードは割愛。正しく動作すること確認済）。

略さないで up してください。