みんなの「教えて(疑問・質問)」にみんなで「答える」Q&Aコミュニティ

こんにちはゲストさん。会員登録(無料)して質問・回答してみよう!

解決済みの質問

線形リストについて。

このたび線形リストを学習し、自分でサンプルコードを書くことにしました。
しかし、動かすことが出来ず、理解することが出来なかったため、ご相談致します。


コード:
#include <stdio.h>
#include <stdlib.h>
#define N 10

typedef struct node *link;
struct node { int item; link next; };

void main() {

int i;
link head ,t;

head = NULL;

//リストに要素を入れる。
for(i = 0,t = head; i < N; i++, t = t->next) {
t = malloc(sizeof *t);
t ->next = NULL;
t ->item = i;
}

//リストを表示する
for(t = head; t != NULL; t = t->next) {
printf("%d\n", t->item);
}

}

実行結果:
リストを表示するのfor文内、t->itemでエラー。

原因はheadを上手くポインタで指せていないことにあると思います。

お聞きしたいことは2点です。
1.なぜ意図したように上手く動かないのか。
2.このように動かしたい場合、何処を変更すれば良いのか。

以上です。

宜しくお願いします。

投稿日時 - 2011-04-28 15:42:23

QNo.6699911

困ってます

質問者が選んだベストアンサー

原因は、線形リストが繋がっていないから。
そもそも、tとheadがあるのは、リストの頭をheadとして持っておくためですよね?コピーの方しか、操作されていませんので、headはいつまでもNULLのままです。
ループの前に
head = (link)malloc(sizeof(*head));
で、最初のノードを作ってそのポインタをtへコピーするべきです。
さて、t->nextは、次のノードのポインタを持っていたいのですが、これにアクセスできる時点で、次のノードをアロケートしてポインタを代入しないといけません。
t=t->next
では、tをNULLにしてしまっています。この時点で前のt->nextに値を代入するチャンスが失われます。ここでつながりが切れるわけです。現在の方法では、アロケート結果のポインタを前の(親のと言った方が分かりやすい?)->nextに代入できているわけではありません。

head = (link)malloc(sizeof(*head));

//リストに要素を入れる。
for(i = 0,t = head; i < N; i++, t = t->next) {
//t=malloc(sizeof *t);
//t ->next = NULL;
t ->item = i;
t->next=malloc(sizeof *t);
}

としてみてください。でも、そうすると、最後に余計なノードが一つ無駄に出来ますよね?番兵もいなくなります。そこで、ここに、if文をかまして、最後はメモリ確保しないという手もありますが、カッコ悪い(非効率)ですね。
じゃあ、いっそのこと、そこのfor文をこのように書き換えたらどうでしょう?

i=0;
t=head;
do{
t ->item = i++;
if(i<N){
t->next=malloc(sizeof *t);
}else{
t->next=NULL;
}
}while((t=t->next)!=NULL);

投稿日時 - 2011-04-29 00:26:06

補足

ベストアンサーにする予定ですが、もう少し勉強したいので、少しの間回答できる状態にさせて下さい。

投稿日時 - 2011-04-29 02:29:14

お礼

大変わかりやすい回答ありがとうございます。
リンクが繋がっていないとのことですが、言われてみれば確かに繋がっていないようでした。

ただ、KAZUMI2003様の書き換たコードについてですが、
結局のところ、毎ループごとにif文が入っているので、効率は変わらないように思いますが、如何でしょうか。


最後に、動くように変更した私のサンプルコードを掲載致します。

void main() {

int i;
link head ,t;

head = malloc(sizeof(*head));

//リストに要素を入れる。
for(i = 0,t = head; i < N; i++, t = t->next) {
t->item = i;
if(i < N - 1) t ->next = malloc(sizeof(*head));
else t -> next = NULL;
}

//リストを表示する
for(t = head; t != NULL; t = t->next) {
printf("%d\n", t->item);
}

}

投稿日時 - 2011-04-29 02:24:58

このQ&Aは役に立ちましたか?

0人が「このQ&Aが役に立った」と投票しています

回答(7)

ANo.7

ほとんど解決しているようでアレですが、

>Microsoft Visual Studio 2005を使用したのですが、特にエラー文は出ず、強制終了となってしまいました。
>エラー文は出ませんが、意図しないメモリのアドレスにアクセスしたせいでしょう。

おそらくそういうことではなく、最初に提示されたコードでは、
headがNULLであるため、リスト表示のfor文ループを全く実行しなかったのでありましょう。

メモリーへの不正アクセスの場合は、それなりの落ち方をするはずで、
何もエラーが出ないということはまず考えられません。

投稿日時 - 2011-04-29 17:31:42

ANo.6

link *t;
としておけば

//リストに要素を入れる。
head = NULL;
for (i = 0, t = &head; i < N; ++i, t = &(*t)->next) {
*t = malloc(sizeof **t);
(*t) ->item = i;
}
*t = NULL;

//リストを表示する
for(t = &head; *t != NULL; t = &(*t)->next) {
printf("%d\n", (*t)->item);
}

って形になるね.

投稿日時 - 2011-04-29 03:33:11

ANo.5

うーむ、効率的にはあまり変わりませんね。
最初の意味は、ここにif文を入れると、for文の制御とif文でiの値を無駄に何回もチェックするのが、美しくないという意味でした。

また、提示したコードは、最初は次のように書いたのです。

while(1){
  t ->item = i++;
  if(i<N){
    t->next=malloc(sizeof *t);
    t=t->next;
  }else{
    t->next=NULL;
    break;
  }
}

でも、while(1)をbreakで抜けるなんて、人にアドバイスするには、あんまりなお行儀だと思ったものですから。

あと、No.4氏の言うように、ポインタへのポインタとして、操作すれば、問題は解決するけど、ものすごいコードの書き換えと、説明がめんどくさかったので、やめました。

投稿日時 - 2011-04-29 03:07:45

お礼

なるほど!
いろいろと考えて投稿して頂き、ありがとうございます!!

投稿日時 - 2011-05-13 04:02:11

ANo.4

t を link * として定義するという作戦もあります.

投稿日時 - 2011-04-29 02:14:46

お礼

linkは今ポインタ型だと思いますので、link *tだとstruct nodeとなるのでしょうか?

どうすればいいのかその先がわかりませんが、考えてみることにします。

投稿日時 - 2011-04-29 02:27:46

ANo.2

>リストを表示するのfor文内、t->itemでエラー。

「どのような」エラーが出るのか、詳しく書いてほしいなぁ、なんて思ったりしています。

投稿日時 - 2011-04-28 22:17:53

お礼

申し訳ございません。

Microsoft Visual Studio 2005を使用したのですが、特にエラー文は出ず、強制終了となってしまいました。

エラー文は出ませんが、意図しないメモリのアドレスにアクセスしたせいでしょう。

投稿日時 - 2011-04-29 02:11:38

ANo.1

リストそのものはうまく行ってそうに見えるんですが……

1.
tに値を入れてもheadは変わりません。
従ってリスト表示の際のt=headはt=NULLと同じことになります。

2.
headがNULLならheadにtを入れてやる、とか。
#ドコに書くかは言わずもがな。

投稿日時 - 2011-04-28 17:27:39

お礼

t=NULLとなるのはわかっていたのですが、
作成したソースで、リンクが繋がっていると勘違いしたのが諸悪の根源なようです。

投稿日時 - 2011-04-29 02:11:20