線状リストの作成中に代入ができません

Question

質問内容はタイトルと同じです。なぜ、代入ができないのかを教えてください。リストの追加位置はtopの末尾です。

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

typedef struct data_ {
    char key;
    struct data_ *next;
}data;

struct queue{
        data *top, *rear;
};

void enqueue (struct queue *q, char key);



int main(){
    
    struct queue q;
    
    enqueue(&q, 'a');
    
    printf("%c\n",q.top->key);
    printf("%c\n",q.rear->key);
    
    return 0;
}

void enqueue (struct queue *q, char key){
    
    data *new = malloc(sizeof(data));
    if (new == NULL) {
        printf("ERROR\n");
        exit(1);
    }
    new->key = key;
    q->rear = new;
    data* tail = q->top;
    
    while (tail != NULL) {
        
         tail=tail->next;
    }
    
    tail = new;/**代入ができていない**/
}

Comments

[episteme]

rearはキューの末尾を指してるんですよね?
ならばrearのうしろに繋げばいい。tailって必要ですか?

Answer 1

原因は大きく分けて3つ有ります

1. main関数内struct queue q; この時点ではq.top及びq.rearは未初期化です

enqueue()内部でq->topをコピーしたtailとNULLを比較していますが、未初期化のために正しく動作しません（未定義動作です）。NULLを初期値として代入しておく必要が有ります（初期化用の関数（もしくは初期化したものを返す関数）を作ると便利です）

1. tail = new;/**代入ができていない**/ これだとenqueue()のローカル変数tailを書き換えただけなのでqには何の変更も起きないです
2. enqueue()内でリストが空の場合に場合分けが必要です

• q->topがNULL（リストが空）の場合にはq->topとq->rearがnewを指すようにしなければなりません
• それ以外の場合、q->rear->nextはnewを指すように、q->rearはnewを指すように要素を追加します
• q->rearがあるのでwhileループでtopから順に末尾要素をたどる必要はありません
  （rearを使わない実装であればwhileでたどる必要が有ります。）

以上をまとめるとこんな感じのコードになると思います（初期化関数は面倒だったので作ってないです）
wandbox

---

ところで、newという語はC++で動的確保の予約語（mallocの代わりみたいなものです）になっていて誤解を招きやすいので、別の変数名に置き換えることをおすすめします

Comments

[tyu_ru_cpp]

ありゃ、他回答者さんとかぶっちゃった

[GAKU_SAY]

わかりやすい解説とアドバイスをありがとうございます。c＋＋でnewが動的確保に使えることは存じております。

Answer 2

struct queueu q の q を初期化していないのに、
enqueue の中で q->rear = new; で rear を参照しています。
enqueue の中のローカル変数 tail に何を代入しようと、
enqueue を終了すると tail は無くなります。

data は typedef して、queue は typedef しないのですか？

#include <stdio.h>
#include <stdlib.h>  // malloc, exit

typedef struct data_ {
    char key;
    struct data_ *next;
} data;

typedef struct queue {
    data *top, *rear;
} queue;

void enqueue(queue *q, char key);

int main(void)
{
    queue q = { 0 };  // q.top = q.rear = NULL;

    enqueue(&q, 'a');
    enqueue(&q, 'b');
    enqueue(&q, 'c');

    printf("%c\n", q.top->key);
    printf("%c\n", q.rear->key);
}

void enqueue(queue *q, char key)
{
    data *new = malloc(sizeof(data));
    if (new == NULL) puts("ERROR"), exit(1);
    new->key = key;
	new->next = NULL;
	if (q->top == NULL) q->top = q->rear = new;
	else q->rear = q->rear->next = new;
}

Comments

[GAKU_SAY]

この回答の場合、c\ncと出力されると思います。ただ、今回はリスト内で文字がtopから見てabcとなっていて欲しいです。

[episteme]

a
c
と出力されますよ?