アルゴリズム 線形リスト

質問

最近リストについて習い始めました。入力したデータと同順に並ぶリストを作成しようと思い、コードを打ったのですが…動作中止の表示がでてしまいました。どこが間違っているのか、ずっと悪戦苦闘して組んでいるのですが、全く出口が見えてきません。何が間違えているのか、はたまた根本的に違うのか、ご指導して頂けると有難いです。
以下、コードです。

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

struct hito{
char name[20];
int age;
struct hito *next;
};

void main(void){
struct hito *p, *head, *dummy;
char new_name[20];
int new_age;
dummy = (struct hito *)malloc(sizeof(struct hito));

head = dummy;

dummy->next = p;
dummy = p;

while (scanf("%s %d" , new_name, &new_age) != EOF) {
p = (struct hito *)malloc(sizeof(struct hito));
strcpy(p->name, new_name);
p->age = new_age;
p->next = head;
head = p;
}

while(p != NULL) {
printf("\t%-20s %3d\n" , p->name, p->age);
p = p->next; }
}

回答No.5

6yemon · ベストアンサー

> でも、こうすると可笑しくなりますね。考え方自体が間違えていますかね。

しょうがないなぁ（苦笑）。前より良くなりましたが、ループの中の
head = p;
p->next = head;
この処理がおかしいです。
こういう処理は慣れるまでややこしく感じるものです。私も経験あります。二通り示しますので、動きが飲み込めるまでじっくりトレースしてみてください。やってることは同じです。

(a) ループの中では、「一つ前に作られた構造体」の next フィールドに、今malloc()した構造体のアドレスをセットしなくてはならない。即ち
p = (struct hito *)malloc(...
... // メモリを割当て、構造体の中身をセットする
prev->next = p; // 一つ前の構造体に今のpをポイントさせる
prev = p; // 次の「一つ前」は今のp
ということを繰り返せばよい（prev は "previous"「以前の」から）。この場合 head は、ポインタではなく、ダミーの構造体にするほうが都合がよいです。肝心な所は次のようになります(細部は省略)。

struct hito head; // 先頭となるダミーの構造体。ポインタではない
struct hito *p, *prev; // 作業用ポインタ

prev = &head; // 最初はダミー構造体をポイントする
while (scanf(... // データを入力
p = malloc(... // 新たな構造体を割当て
... // name, new_ageをセットする
prev->next = p; // 「一つ前」が「今」をポイントする
prev = p; // 次の「一つ前」は今の p
}
prev->next = NULL; // ここで終端

次のような for 文で表示すれば、head から辿るのだ、という事をはっきりさせることができます。
for (p = head.next; p != NULL; p = p->next)
printf(省略, p->name, p->new_age);

(b) head は構造体にしたくない、あくまでポインタ…というなら prev ポインタが struct hito *head ポインタをポイントしてからループに入るという手があります。この場合、prev の役目は一つ前のnextフィールドをポイントすることです。具体的には次の通り。
struct hito *p, *head;
struct hito **prev; // ポインタへのポインタ
...
prev = &head; // head は「一つ前の next」である
while (scanf(...
p = malloc(...
...
*prev = p; // 一つ前の next に最新の p をポイントさせる
prev = &p->next; // 次は今の p->next をポイントする
}
*prev = NULL; // ここで終端

これを表示するループは次の通り。
for (p = head; p != NULL; p = p->next)
printf(...

No.4の回答でも動作するはずですが、ループの中にif文があるのが少し美しくない（大したことじゃないけどw）。if文が必要なのは、ループの一回目が特殊だから。上記二例はループに入る前を工夫することで、一回目も二回め以降と同じ手順で繰り返せるようになっています（if文が要らない）。

お礼

返信が遅くなり申し訳ありません。
トレースしながらやってみました。わかったようなわかっていないような感じです。結構時間をかけたのですが…飲み込みが悪くてすみません。他のプログラムもトレースして慣れようと思います。
お手数かけてすみません。
ご回答ありがとうございました。

回答No.4

rangdon

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

struct hito{
char name[20];
int age;
struct hito *next;
};

int main(void){
struct hito *p, *head, *q;
char new_name[20];
int new_age;
int flag = 1;

while (scanf("%s %d" , new_name, &new_age) != EOF) {
p = (struct hito *)malloc(sizeof(struct hito));

strcpy(p->name, new_name);
p->age = new_age;

if (flag) {
head = p;
flag = 0;
} else {
q->next = p;
}

q = p;
}

q->next = NULL;
p = head;

while (p != NULL) {
printf("\t%-20s %3d\n" , p->name, p->age);
p = p->next;
}

return 0;
}

回答No.3

mk48a

＞動作中止の表示がでてしまいました
どんな表示ですか？

dummyは何のために入れているのでしょうか？

＞dummy->next = p;
この時点でpは未定義です。

＞while(p != NULL) {
リストの終端のnextメンバにNULLを入れていないので、この条件で終了しないかと思います。

while()の中でリストに構造体を登録する際に、1番目とそれ以降で処理を分けたら良いと思います。

また、
＞入力したデータと同順に並ぶリストを作成しようと思い
このプログラムだと、
3->2->1
の、ような感じで最後に入力した要素が先頭になりますが良いのですか？

補足

ご回答ありがとうございます。
>動作中止の表示とは、英悟で書いてあってわからなかったのですか、継続、中断、停止の処理を選ぶメッセージボックスが立ち上がりました。
>dummyはダミーを使って区切るため…？あまりよくわからずに使っています。（そうした方がいい、と書いてあったので）
>while()の中でリストに構造体を登録する際に、1番目とそれ以降で処理を分けたら良いと思います。
dummyとその他の処理で区別をする、ということですよね。
＞入力したデータと同順に並ぶリストを作成しようと思い
このプログラムだと、
3->2->1
の、ような感じで最後に入力した要素が先頭になりますが良いのですか？
そうなるんですか！？ポインタを辿って入れた順番通りのコードが作りたいんですが。逆の考えですかね。

回答No.2

6yemon

dummy->next = p;

この p は初期化されてませんから、何処へ飛んで行くかは神のみぞ知る、です。問題はそれだけではないのですが、ともかく
while (scanf...
のループに入る前の処理を見直す必要があると私は見ます。
例えば、dummy = (struct hito *)malloc(sizeof(struct hito));
でダミーの構造体を作っていますが、これは必須ではありません。

リスト構造は図に描いて見ると良いです。
ソースコードだけ見ていても気づかないことが、図に描くと間違いに気づくものです。

まず、構造体が３個程度ある（scanf()で三行読み込んだ）場合を図に描いてみましょう。第一ステップは、大まかな一般的な姿を具体的にイメージする事。
次に、構造体が一個しかない（一行だけ読んだ）場合を図に描いてみましょう。そして、その構造体のnextポインタの値が何であればよいか、考えましょう。

さらに、構造体が二つある場合も図に描きます。それで、各nextポインタにどういう値がセットされればよいかを考えましょう。さらに構造体が一つも無い場合にどうであればよいかも考えます。そうしているうちに、
・どういう操作を繰り返せばよいか
・最初はどうすればよいか
・最後はどうすればよいか
具体的なイメージが沸いてきます。

補足

ご回答ありがとうございます。アドバイスを受けてリストの構造体を図に描いて見ました。単体だけでの動きを考えると整理がつきました。確かにダミーは要らない気がしたので、省いて次のコードを書きました。

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

struct hito{
char name[20];
int age;
struct hito *next;
};

void main(void){
struct hito *p, *head;
char new_name[20];
int new_age;

head = NULL;

while (scanf("%s %d" , new_name, &new_age) != EOF) {
p = (struct hito *)malloc(sizeof(struct hito));
strcpy(p->name, new_name);
p->age = new_age;
head = p;
p->next = head;
}

p->next = NULL;

while(p != NULL) {
printf("\t%-20s %3d\n" , p->name, p->age);
p = p->next; /* pはpの次のポインタを指し示す */
}
}

でも、こうすると可笑しくなりますね。考え方自体が間違えていますかね。

回答No.1

asuncion

dummyが何のためにあるのかわかりません。
なくても同じではないでしょうか。

お礼

ご回答ありがとうございます。
初めはdummy無しのコードを書いていたのですが、うまくいかず、色々と調べた所ダミーを作って入れる、という方法を見つけたので、見よう見まねで入れて見ました。
無くても同じような気はするのですが、如何せん理解できていないので何とも答えられないです。