

Aizu Online JudgeのALDS1_3_Cの問題を解いています。

[双方向連結リスト | アルゴリズムとデータ構造 | Aizu Online
Judge](http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_C&lang=jp)

原因不明のエラーに悩んでいます。以下がソースコードになります。

[code]

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define QUEUE_SIZE 2000000
    #define next(x) ((x + 1) % QUEUE_SIZE)
    
    struct job {
        char *command;
        int key;
    } jobs[QUEUE_SIZE];
    
    struct cell {
        int key;
        struct cell *prev;
        struct cell *next;
    } head;
    
    int front, rear;
    
    void init(void);
    void enqueue(char *command,  int key);
    struct job dequeue(void);
    void insert(int key);
    void delete(int key);
    void deleteFirst(void);
    void deleteLast(void);
    
    int main(void)
    {
        int n, key;
        char *command;
        struct cell *p;
    
        scanf("%d", &n);
        init();
        for (int i = 0; i < n; i++) {
            scanf("%s %d", command, &key);
            enqueue(command, key);
        }
    
        while (front != rear) {
            struct job deq = dequeue();
            if (deq.command == "insert") {
                insert(deq.key);
            } else if (deq.command == "delete") {
                delete(deq.key);
            } else if (deq.command == "deleteFirst") {
                deleteFirst();
            } else if (deq.command == "deleteLast") {
                deleteLast();
            } else {
                exit(1);
            }
        }
    
        // リスト出力
        for (p = head.next; p != NULL; p = p->next) {
            printf("%d ", p->key);
        }
        printf("\n");
        return 0;
    }
    
    void init(void)
    {
        front = rear = 0;
    }
    
    void enqueue(char *command, int key)
    {
        if (next(rear) == front) {
            fprintf(stderr, "queue is full.");
            exit(1);
        }
        jobs[rear].command = (char *)malloc(sizeof(char) * sizeof(command) + 1);
        strcpy(jobs[rear].command, command);
        jobs[rear].key = key;
        rear = next(rear);
    }
    
    struct job dequeue()
    {
        struct job deq;
        if (front == rear) {
            fprintf(stderr, "queue is empty.\n");
            exit(1);
        }
        deq = jobs[front];
        front = next(front);
        return deq;
    }
    
    void insert(int key)
    {
        struct cell *new;
        new->key = key;
        new->next = head.next;
        new->prev = &head;
        head.next = new;
    }
    
    void delete(int key)
    {
        struct cell *p;
        if (head.next == NULL) {
            fprintf(stderr, "doubly linked list is empty.\n");
            exit(1);
        }
        p = head.next;
        while (p != NULL && p->key != key) {
            p = p->next;
        }
        p->prev->next = p->next;
        p->next->prev = p->prev;
    }
    
    void deleteFirst()
    {
        if (head.next == NULL) {
            fprintf(stderr, "doubly linked list is empty.\n");
            exit(1);
        }
        head.next->next->prev = &head;
        head.next = head.next->next;
    }
    
    void deleteLast()
    {
        if (head.next == NULL) {
            fprintf(stderr, "doubly linked list is empty.\n");
            exit(1);
        }
        struct cell *p;
        p = head.next;
        while (p->next != NULL) {
            p = p->next;
        }
        p->prev->next = NULL;
    }
    
[/code]

ここで、main関数内でstruct job
型の変数を宣言すると、scanf関数で入力を受け取れなくなります。試しにmain関数のwhile文以下をコメントアウトして、実行すると受け取れました。main関数内でstruct
job型の変数を宣言すると、途端に2つ目のscanf関数で入力を受け取れなくなるのです。解決策を教えて下さい。


CC BY-SA 4.0
2019-04-29T10:31:18.603
54566
2019-04-29T16:34:02.737
2019-04-29T16:34:02.737
3060
20241
question
c アルゴリズム
キューを使った双方向リストに関するプロセス処理


いわゆる「メモリ破壊」が発生していることの副作用と考えます。  
以下の箇所で「`command`」がポインタで、かつ初期化していないため、`scanf()`の結果が異常な場所に格納されているため、後続の処理が正常に動作しないものと予想します。

変数`command`を配列として宣言するか、`malloc()`等で動的に確保した領域を指すように修正することで、事象は解消するものと思います。

[code]

        int n, key;
        char *command;
        struct cell *p;
    
        scanf("%d", &n);
        init();
        for (int i = 0; i < n; i++) {
            scanf("%s %d", command, &key);
            enqueue(command, key);
        }
    
[/code]

* * *

なお、以下の比較文も実装が誤っているので、`strcmp()`等で文字列比較する必要があると思います。

[code]

           if (deq.command == "insert") {
                insert(deq.key);
            } else if (deq.command == "delete") {
                delete(deq.key);
            } else if (deq.command == "deleteFirst") {
                deleteFirst();
            } else if (deq.command == "deleteLast") {
                deleteLast();
            } else {
                exit(1);
            }
    
[/code]


CC BY-SA 4.0
2019-04-29T11:32:57.863
54570
2019-04-29T11:32:57.863
20098
54566
answer


最初に宣言しておきますが、以下の説明通りの修正を行っても、あなたのコードは期待通りのキューとしての動作を行うようにはなりません。

(全部説明しながら修正していくと、C言語の教科書のポインタの説明部分と、データ構造の教科書のダブルリンクキューの説明部分をほとんどそのまま引き移した超長文になりそうなので、以下は未初期化のポインタ参照に話を絞りました。)

とりあえず致命的に悪いのは`main`内のこの行です。

[code]

    char *command;
    
[/code]

ここであなたは`command`を`char
*`型のポインタとして宣言しているのですが、その後一度もこのポインタの値を初期化しないままで、ポインタの参照先を書き換えるような処理が走っています。

[code]

        scanf("%s %d", command, &key);
    
[/code]

`command`が初期化されないままということは、システムに存在するメモリのどこを指しているのかまったくわからない状態です。そのままで`scanf`を実行すればシステムのメモリのどこかが壊れることになります。「main関数内でstruct
job型の変数を宣言すると」動作が変わったということですが、そんなことはもうたまたまで、上記の`scanf`が一度でも走った瞬間にどこかのメモリが壊れてしまい、以後の動作は予測不可能(不運な場合は動いているように見えることもある)になります。

`main`内の`command`の宣言は、例えば次のようにすべきでしょう。

[code]

    char command[32]; //#実際の領域を確保。未初期化のポインタを使っては絶対にダメ。
    
[/code]

* * *

あなたのコード、他にも未初期化のポインタを使っている箇所があります。

[code]

    void insert(int key)
    {
        struct cell *new;
        new->key = key;
        new->next = head.next;
        new->prev = &head;
        head.next = new;
    }
    
[/code]

`insert`関数内の`new`は`struct cell
*`型のポインタとして宣言されていますが、またもや初期化されていません。他のポインタに長期に保存されることになるアドレスをローカルな配列にしては困るので、`malloc`で動的に領域を割り当てるべきところでしょう。

[code]

    void insert(int key) {
        struct cell *new = (struct cell *)malloc(sizeof(struct cell)); //#
        new->key = key;
        new->next = head.next;
        new->prev = &head;
        head.next = new;
    }
    
[/code]

(当然割り当てたメモリはどこかで解放しないといけません。)

* * *

他にも  
\- 文字列比較に`strcmp`を使わず`==`を使っている (user20098 さんの回答の後半)  
\- 文字列(`struct cell`内の`command`)用`malloc`のサイズ計算が間違えている  
\- ...  
等々、まだまだ動くようにするためにはあちこち書き換えなければいけないでしょう。

上記の未定義ポインタの参照に関する修正を行えば、もう少し動作が安定するはずなので、少しずつ問題点を取り除いていってください。


CC BY-SA 4.0
2019-04-29T11:46:28.137
54571
2019-04-29T12:44:46.910
2019-04-29T12:44:46.910
13972
13972
54566
answer