Linked List（線形リスト）を使ったデータのソート

質問

大学の、Cの課題で、困っています。
どこが違うのか教えていただけたら嬉しいです。

【課題】

１行に１つの数値データを、複数行入力すると、
このデータを１行ずつ読んでいって、それをひとつの構造体として保持し、
数値データの小さい順にリンクされるようなLinked Listとなるようにプログラムを作る。

入力したデータが数値だったら、Linked Listを先頭から巡り、それを挿入すべき場所を見つける。
そしてデータを格納するための構造体の領域をmalloc関数で確保し、そこにデータを入れ、実際にリストに挿入する。
読み込むべき入力データが無くなったら、最後にLinked Listで保持しているデータを１行ずつ書き出してみる。

【変な結果が出るプログラム】

#include<stdio.h>

main()
{
int c, n, *nextp;

void *malloc(size_t size);
struct listdata{
int i;
struct listdata *nextp;
};
struct listdata *hajime;
struct listdata *pointer;

hajime = NULL;

while ( ( c = getchar() ) != EOF ){
if ( '0' <= c && c <= '9' ){
n = n * 10 + ( n - '0' );
}
pointer = ( struct listdata *) malloc ( sizeof (struct listdata) );
pointer -> i = n;
hajime = pointer -> nextp;
}
printf ( "%d\n", nextp );
pointer = hajime;
while ( pointer != NULL ){
printf ( " %d\n", pointer -> i );
pointer = pointer -> nextp;
}
}

よろしくお願いします(>_<)

回答No.16

noname#89477 · ベストアンサー

#14のsakatomoです。

＞for文の処理が終わってからも、最後にi++をしているということですね
そうではなくて、i=0～4の5回繰り返した直後(iが4の時)、i++を実行してiが5になったために繰り返し処理を終了したのです。
つまり、i++はその条件を満たした時のみfor文の最後に行われ、i<5の判定は繰り返し処理の最初に行われるからです。
（i>5の判定は6回(0～5)行われます）

＞for文の後にNULLになる意味がわかりました
これもpが最後にNULLで終わると考えるよりは、pがNULLになったから終わったと考えるのが正しいと思います。

お礼

あー！！
そっか、そうですよね！
だから、for文が終わるんですね。
アホでごめんなさい。。

ありがとうございます。

本当に、いろいろ勉強になりました。
とても感謝しています。
何にもお返しができないのが残念です。
本当にありがとうございました！

回答No.15

BLUEPIXY

#14>不快な思いをされたようでしたら、お詫び申し上げます。
いえいえ、問題ないです。
同じようなアルゴリズムを使えば同じようなソースになるというのはしょうがないですしね。
アルゴリズムとしては普通で、大いばりでオレが考えたなんていうほどのものでもないですし、むしろ、アルゴリズムとして合ってると確証が得られて少し嬉しいですね。
表現の方法は色々あって、やり方もこれ以外にも色々あると思いますので、逆に質問者さんが、これしかないみたいに思われないといいなと思います。

回答No.14

noname#89477

#13のsakatomoです。
インデント（段落）が付けられないため非常に見にくいソースで大変ですが、一生懸命にご理解されている様子がうかがえて大変うれしく思っております。
例を挙げて説明したいと思います。

線形リストに便宜的に(p1,p2,p3)が登録されており(p1->i < p2->i < p3->i)の関係にあるとします。
今たとえばnewをp2とp3の間に入れたいとします。
その時にはbefには前回のpのポインタ(p2)がセットされています。
つまりhalunahさんのプログラムではこれ(p2)をカウントして探し出していたのですが、(new->i > p->i)の関係にある場合(つまりfor文による繰り返しが継続されている状態)にp(p2)をberに代入して保存しているのです。

もし、わかりにくい場合には
bef = p;
を削除して
for ( p=head ; p!=NULL ; bef = p, p=p->next ){
と書き換えることもできます、こうすると更新前のpをbefに保存しているのがわかりやすくなる反面、コメントが入れにくくなります。
（これをカンマオペレーションと言いますが、",(カンマ)"で区切ることで複数の文を連続して動作させられます）

それから(p == NULL)の判定ですが、これはfor文の( ;p != NULL; )の判定の真逆の判定になります。
for文から抜ける条件は、上記NULLによる判定の他にnewを挿入後のbreakによる場合があるためです。
つまり(p==NULL)であるということは、線形リスト中に未挿入の状態(new->iが最大値)にあることを意味しています。
なぜならば、(p==NULL)になるのは(p = p3->next)の時だけだからです。
そしてこの時には、befにはp3がセットされていますのでp3->nextにnewをセットすれば線形リストの最後にnewがセットされることになります。

それから最後に、良く見てみたら#5のBLUEPIXYさんのプログラムとロジックがほとんど同じになっていました。
もちろん盗用ではなくオリジナルなのですが、インデントの付かないソースは私にとって非常に難解であるためBLUEPIXYさんのソースを解読する技術がなかったことによるものです。
不快な思いをされたようでしたら、お詫び申し上げます。
と言うことで、BLUEPIXYさんの書かれたプログラムが関数化した最終的な模範解答であると思います。

補足

なるほど～！！
次のために、bef = p; と書いていたんですね。
よくわかりました！ありがとうございます。

p == NULL のことですが、
未挿入の状態のとき、なぜ、p == NULL になっているのかが、わからなかったのは、
初めに、p = NULL;と書いているわけでもないし、
for ( p=head ; p!=NULL ; p=p->next ){
を、途中でbreakせずに最後まで全部まわした場合、p!=NULLの状態で終わるから、
pは、p3を指していることになって、NULLではないと思っていたからだったのですが、

今、簡単なfor文で試してみたら、
たとえば、
for ( i=0 ; i<5 ; i++ ){
～～
}
printf ( "%d", i );
と書くと、iは、4とプリントされると思っていたのが、5と出たので、納得しました。
基本的なことがわかっていなかったようです。
for文の処理が終わってからも、最後にi++をしているということですね。
それなら、p!=NULLで終わったはずのpが、for文の後にNULLになる意味がわかりました。

でも、sakatomoさんの説明してくださった
「for文の( ;p != NULL; )の判定の真逆の判定」という考え方とはまた違う気がするのですが、
この考え方で合っていますか？

回答No.13

noname#89477

sakatomoです。
実際にコンパイル＆リンクして実行してみました。
特に動作が不安定ではないようでしたが。
それからコンパイル時に"warning"がたぶん出ていると思うのですが、
#include<stdlib.h>
が必要です。

せっかくコンパイルして動かしてみたので、チョットソースをいじってみましたので、参考にしていただければ幸いです。
なるべくわかりやすくするには、無駄な変数の使用を減らして、判定処理を少なくするのがポイントです。
n,m,j,*next,*pointerを使わないようにして、その代わりに*bef(直前のポインタ)を使うようにしました。
それからどうでもいいことですが、コメントは"//"を使った方が"*/"が抜けていたときのトラブルを考えるとリスクが少なくて済みます。
（最近のCは、ほとんど"//"が使えますから）

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

void main()
{
int c, b; //n, m, j, *next;

struct listdata {
int i;
struct listdata *next;
};

struct listdata *head, *new_, *p, *bef; // *pointer,

/* ↑　*headは常にリストの先頭、*new_は新しく入ってきた数値をまず入れておくところ、*pointerは代入用、*pはfor文用 */

head = new_ = NULL; // pointer =
b = 0; //n = m = 0;

while ( ( c = getchar() ) != EOF ){
if ( '0' <= c && c <= '9' ){
b = b * 10 + c - '0';
} else if ( c == '\n' ){
//m++;
new_ = ( struct listdata *) malloc ( sizeof(struct listdata) );
new_->i = b;
new_->next = NULL;

if ( head == NULL ){ /* リストが空だったら */
head = new_;
} else { /* リストに１つ以上入っていたら */
for ( p=head ; p!=NULL ; p=p->next ){ /* headの次から今まで入ったものまで */
if ( new_->i <= p->i ){
if(p == head){
/*----- （最小値）先頭に挿入 */
new_->next = head; /* headの前にnew_を入れて */
head = new_; /* それをheadにする */
}
else {
/*----- 途中に挿入 */
bef->next = new_; /* 新領域(new_)のポインタを直前(bef)の次ポインタにセット */
new_->next = p; /* 直後(p)ポインタを新領域(new_)の次ポインタにセット */
}
break; /* 挿入済みなのでループから抜ける */
}
bef = p; /* 直前のポインタを保存(bef->next を変える場合に使用) */
}

if(p==NULL){
/*----- （最大値）末尾に挿入 */
bef->next = new_; /* 新領域(new_)のポインタを直前(bef)の次ポインタにセット */
}
}
b = 0; //n = 0;
}
}

printf ( "\n" );
for ( p=head ; p!=NULL ; p=p->next ){
printf ( "%d\n", p->i );
}
printf ( "\n" );
}

それから関数の作り方を覚えたら、入力の部分やnewの挿入の部分を関数化することで綺麗な機能分けになると思います。
簡単なプログラムを簡潔に組めないと、難しいプログラムを簡潔に組むことはできません。
もちろん、halunahさんがここまでプログラムを組めるようになっただけでも、スゴイことですよ。

お礼

とってもシンプルになりましたねぇ！
ちゃんと動きました。ありがとうございます。

でも、わからないところが２つあります。
いくら考えてもわかりません。教えてください。

/*----- 途中に挿入 */
bef->next = new_; 　/* 新領域(new_)のポインタを直前(bef)の次ポインタにセット */
new_->next = p; 　/* 直後(p)ポインタを新領域(new_)の次ポインタにセット */

の後に、

bef = p; 　/* 直前のポインタを保存(bef->next を変える場合に使用) */

というのがありますが、
この３行は、
befの次をnewにして、その次にnewより大きかったpが来るようにして、
その後、pをbefに代入するということですよね？
そうすると、pの次がnewで、その次がまたpとなってしまう気がするのですが、、
でもちゃんと動いていますよね…不思議です。

もうひとつ、

if(p==NULL){
bef->next = new_;

これは、直前にfor文で、最後、pは!=NULLのところ（それまでで１番大きい数の入っている構造体）
を指していると思うのですが、p==NULLの場合というのはあるのでしょうか？
また、bef->next = new_; の、befはどこで、リンクリストの最後だと定義されているのですか？

なかなか解決しなくて、申し訳ありません。
教えてください。よろしくお願いします。

関数の作り方、この間わかりました。そうですね、使ってみようと思います。
ありがとうございます。

補足

あ、わかりました！　すみません。

途中に挿入したら、break;するから、
bef = p;　は関係ないんですね。
それで、p == NULL の時、bef->next = new_;　とする意味はわかりました。
でも、new_がどれよりも大きかった時は、p == NULL であるというのが、なぜかわかりません。

それから、
/*----- 途中に挿入 */
bef->next = new_; 　/* 新領域(new_)のポインタを直前(bef)の次ポインタにセット */
new_->next = p; 　/* 直後(p)ポインタを新領域(new_)の次ポインタにセット */

これの、befがどこから出てきたのかわかりません。
befは、何のnextなのか書いていないのに、なぜちゃんと繋がるのでしょうか？

よろしくお願いします。

回答No.12

BLUEPIXY

>もし、どこか間違いに気付いたら、コメントをお願いします。
3,6,9,2,5
とか
3,3,3,3,2
とかの場合をトレースしてみるといいかも。
少なくとも、
for ( p=head->next ; p!=NULL ; p=p->next ){
でリストをたどっている時にリストを変更したら、
ループの継続はできるとは限らないことに注意
また、リストを挿入する条件として、
if ( new->i <= p->i ){
のようにイコールの場合があってはまずいのじゃないか？

お礼

そうですね、
if ( new->i <= p->i ){　のイコールがあると、
２回同じものが入ってしまいますね。
ありがとうございます！

>リストをたどっている時にリストを変更したら、
>ループの継続はできるとは限らないことに注意

たしかに。。
だったら、変更した直後にbreak;すればいいと思ってやってみましたが、変わりませんでした。
とにかく、今まで入っているものより大きい数値が入ってきたり、同じ数値が入ってきたりすると、おかしくなるようなので、for文の中を考えなおします。

数学より難しいかもしれませんね、Ｃ言語って。

回答No.11

noname#89477

#10のsakatomoです。
チョット私も言い方が・・・(^_^;
変数には「定義文」と「実行文」とがあります。
（実行文とは、#10で"使用"と言っていたものです）
定義文は実行文よりも先に1回だけしておく必要があります。
pointerの場合
struct listdata *pointer;
が線形情報ポインタの定義文となります。
malloc(),memset()にしても、これらは関数の呼び出しになりますので「実行文」となります。
（補足説明として、
int i = 3;
といった書き方がありますが、こちらは定義文と実行文がいっしょになったものと言えます。
またC++になると、newとかを使いますがこのへんは定義文?実行文?の切り分けが微妙です)

＞１から自分でプログラムを書くことができました
それはおめでとうございます。
＞正しい結果が出る時と出ない時
こういうのが一番やっかいなんですよね。
（でもコンパイル＆リンクできたってことですからスゴイ）
＞先生に聞いてみます
懐かしい言葉の響き

一度覚えてしまえば、この苦労を繰り返すことはありませんから、少しずつガンバってください。

補足

わかりました！今気付きました！
memset()をmalloc()した後に入れろと言われて、
私はよくわからないまま、
最初の方の、void *malloc(size_t size);の後に入れてしまったから、ああいうことになったのでした。
pointer = ～～～ malloc(～);の後ということだったんですね。アホでした。。

そうですよね、実行文ですよね。
あー解決。お騒がせいたしました。

あはは、「先生に聞いてみます」って懐かしいですか～。
それが、今日、先生が時間なくて教えてもらえませんでした。
というわけで、ふたたび添削お願いできたらと思います。

#include<stdio.h>

main()
{
int c, b, n, m, j, *next;

struct listdata {
int i;
struct listdata *next;
};

struct listdata *head, *pointer, *new, *p;

/* ↑　*headは常にリストの先頭、*newは新しく入ってきた数値をまず入れておくところ、*pointerは代入用、*pはfor文用 */

head = pointer = new = NULL;
b = n = m = 0;

while ( ( c = getchar() ) != EOF ){

if ( '0' <= c && c <= '9' ){
b = b * 10 + c - '0';

} else if ( c == '\n' ){
m++;
new = ( struct listdata *) malloc ( sizeof(struct listdata) );
new->i = b;
new->next = NULL;

if ( head == NULL ){ /* リストが空だったら */
head = new;

} else { /* リストに１つ以上入っていたら */
if ( new->i < head->i ){ /* headより小さかったら */
new->next = head; /* headの前にnewを入れて */
head = new; /* それをheadにする */
} else {
for ( p=head->next ; p!=NULL ; p=p->next ){ /* headの次から今まで入ったものまで */
if ( new->i <= p->i ){
pointer = head;
for ( j=0 ; j<n ; j++ ){ /* pointerを、newを入れたい所の前に設定 */
pointer = pointer->next;
}
new->next = pointer->next; /* pointerとその次の間にnewを入れる */
pointer->next = new;
} else {
n++; /* newがpより大きい時、nが増える */
}
}
if ( n == m-2 ){ /* newがどれよりも大きかった時、nは、headとnew以外の構造体の数 */
pointer = head;
for ( j=0 ; j<n ; j++ ){
pointer = pointer->next; /* pointerを最後尾に設定 */
}
pointer->next = new; /* 最後尾の次にnewを付け加える */
}
}
}
b = n = 0;
}
}

printf ( "\n" );
for ( p=head ; p!=NULL ; p=p->next ){
printf ( "%d\n", p->i );
}
printf ( "\n" );
}

もし、どこか間違いに気付いたら、コメントをお願いします。

回答No.10

noname#89477

#8のsakatomoです。
無視していたわけではなく、答えに悩んでいて遅れてしまいました。

＞pointerを最初に使うところ
変数(pointer)には、定義と使用（参照、代入）があります。
そのような意味での「使われている」なので、最初に「使用」されているのは
pointer = ( struct listdata *) malloc ( sizeof (struct listdata) ); // 線形情報領域の確保＆アドレスの代入
という意味です。

質問の主旨から外れますが、開発マシンはWindowsではないのですか？

補足

sakatomoさん、
長い間付き合ってくださって、本当にありがとうございます！

では、memsetのところは、定義の部類に入るんですか。
たしかに使用ではないですね。参照のような気もしますが…

そうなんです、Macです。色々とやりにくいです。。

話は戻りますが、
今日、リスト構造のことがようやく理解でき、
１から自分でプログラムを書くことができました。
でも、正しい結果が出る時と出ない時があります。
いくら見直しても、どういう時におかしくなるのかわからないので、明日先生に聞いてみます。
先生が教えてくれなかったりわからなかったりしたら、また助けを求めるかもしれません。
その時はよろしくお願いします(>_<)

回答No.9

noname#89477

ごめんなさい。No.2のsakatomoです。

肝心なことを書くのを忘れていました。
「pointerが宣言されていませんと言われます」
などのエラーをコンパイルエラーと言いますが、これは必ず最初に出てくるものから解決していかないといけません。（つまり上の行から）

つまり最初に変数定義があって、初めてその変数を使用することができるからです。

まず、コンパイルエラーを取って動かしてからが本当のデバッグ（確認テスト）になります。
（現在はたぶん机上デバッグ？）
動くようになれば、たとえばprintf()などで動きや値がわかりますので（デバッガを使う手もありますが）とにかくコンパイルエラーを早急に取ることを期待いたします。

補足

もう、後ろの方は、消してしまって、
最初の動作の部分だけをprintfで確認したりすればいいんですね。

ちなみに、デバッグ？は、
毎回、Fetchでアップロードしてtelnetで試しています。

回答No.8

noname#89477

どうも、sakatomoです。
最初覚えることが多いし、それぞれの関連を考えるのが大変だと思いますが、少しずつ覚えていけば必ずわかるようになるので、ガンバってください。
もう、No.5さんの方がサンプル（正解？）をＵｐされているのでいいのかも知れませんが、No.2に対する返信をしたいと思います。（回答にはなっていませんが）

「pointerが宣言されていませんと言われます」とのことですが、pointer の宣言は
struct listdata *pointer;
と、すでにされているハズです。
スペルミスなのか、struct listdataの定義ですでにエラーが出ているのか。

また、int *pointer; を定義したらすでに
struct listdata *pointer;
で定義されているのですから、２重定義エラーになるはずです。（たぶん）

また「pointerが宣言されていませんと言われます」は最初にpointer が使われているのは、
pointer = ( struct listdata *) malloc ( sizeof (struct listdata) );
ですので、ここでまず出ているはずです。

実際に見られるわけではないので、お互いにじれったい部分がありますが、根気強くガンバってください。
ご健闘をお祈りいたします。

補足

すぐに回答してくださったのに、
反応が遅くなって申し訳ありません。

そうですよね、int *pointer; では、
二重に定義してしまうことになりますよね。

でも、
memset(pointer, 0, sizeof( *pointer ) );
が、pointerを最初に使うところではないのですか？
これの前にpointerを定義しないといけないのかなと思ったのですが、そういうわけではないのでしょうか？

回答No.7

BLUEPIXY

>でも、私には書いてあることがさっぱりわからないので、
がっくりｏｒｚ
Linked List に挿入するということは、どういうことか、図でも描いてみるといいかも・

あと、mallocしたメモリは、解放するべきということがあるかもしれない。

回答No.6

BLUEPIXY

#5は、マイナスの数値がチェックではじかれる！
と思ったら、もとのプログラムもマイナスの数値を許可しないからいいか・