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

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


【課題】

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

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


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

#include<stdio.h>

main()
{
intc, n, *nextp;

void *malloc(size_t size);
structlistdata{
inti;
structlistdata *nextp;
};
structlistdata *hajime;
structlistdata *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.6 回答者： BLUEPIXY 回答日時： 2006/03/03 18:37

#5は、マイナスの数値がチェックではじかれる！

と思ったら、もとのプログラムもマイナスの数値を許可しないからいいか・

No.5 回答者： BLUEPIXY 回答日時： 2006/03/03 18:33

どこが違うと言うより、未完成なので言うことナス。

サンプルを作ってみました。
/*
１行に１つの数値データを、１行ずつ入力し、それをひとつの構造体として保持し、数値データの小さい順にリンクされるようなLinked Listとなるプログラム。

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

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

#define BUFFSIZE 16

int isNumber(char *str){ /* 数値かどうかをチェックする、チェックが甘い？ */
char c;

while('\0'!=(c=*str++)){
if(!(isdigit(c) || isspace(c))) /* 数値または空白文字以外だったらFALSE */
return 0;
}
return 1; /* OK */
}

/* *root が保持するリストに n を挿入する */
void insert(struct listdata **root, int n){
struct listdata *newPointer, *pointer, *prep;

/* n 用の構造体の確保 */
newPointer=(struct listdata *)malloc( sizeof(struct listdata));
if(newPointer==NULL){
fprintf(stderr, "新しいメモリを確保できませんでした。\n");
exit(EXIT_FAILURE);
}
newPointer->i = n;
newPointer->nextp = NULL;

if(*root == NULL){ /* リストがまだ無い */
*root = newPointer; /* 自分自身がリストの先頭になる */
} else {
prep=NULL; /* prep は、直前のポインタ */
for(pointer=*root;pointer!=NULL;pointer=pointer->nextp){
if(pointer->i > n){ /* 自分より大きいものがあった(挿入位置) */
if(prep==NULL){ /* 直前のポインタがない */
newPointer->nextp=pointer; /* 自分が先頭になる */
*root=newPointer; /* 先頭位置を保持するポインタを自分にする */
} else {
newPointer->nextp=prep->nextp; /* 自分の後ろに前のポインタの後ろをくっつける */
prep->nextp=newPointer; /* 前のポインタの後ろに自分をくっつける */
}
return ; /* 挿入できたので終了 */
}
prep=pointer; /* 現在のポインタを次回の前のポインタにする */
}
prep->nextp=newPointer; /* 挿入できなかったので、最後に追加する */
}
}

/* 指定されたポインタからリストの最後までを表示 */
void print(struct listdata *root){
struct listdata *p;

for(p=root;p!=NULL;p=p->nextp){
printf("%d ",p->i);
}
}

int main(void){
int n;
char buff[BUFFSIZE];

struct listdata *hajime=NULL; /* リストの先頭を保持する */

while(NULL!=fgets(buff, BUFFSIZE, stdin)){ /* 一行読込 */
if(isNumber(buff)){ /* 数値か？ */
n=atoi(buff); /* 数値化 */
insert(&hajime, n); /* リストの適切な位置に挿入 */
}
}
print(hajime); /* リストの表示 */

return 0;
}

この回答へのお礼

すごい！
１から書いてくださったんですか！
ありがとうございます。
当たり前かもしれませんが、ちゃんと動きました！

でも、私には書いてあることがさっぱりわからないので、
ちゃんと１から勉強しようと思います…
課題の期限も延びたので。

勉強して、わかってきたところで、これを見てみて、
それでもわからないところがあったら、
また質問させていただきます。

ありがとうございました。

お礼日時：2006/03/04 02:17

No.4 回答者： sakatomo 回答日時： 2006/03/03 13:45

質問とはあまり関係ない部分もあるので気が引けるのですが、私が初心者の方にいつも言っていることを書かせていただきます。

（つまり質問者に対してだけではなく）

コメントは、１行１行すべてに入れる必要はないですが、「動作」ではなく「機能」を説明しないとダメです。
これだけでは何を言っているのかわからないと思います。
min = sec / 60;
×　// secを60で割る（動作の説明）
○　// 秒を分に変換（機能の説明）

そして、この質問で言えば
「このデータを１行ずつ読んでいって」
「数値データの小さい順にリンク」
「入力したデータが数値だったら」
「Linked Listを先頭から巡り」
「それを挿入すべき場所を見つける」
などをどこでやっているかをコメントとして付け加えるべきです。

するとNo.3の方が指摘されているように、EOFの判定は行の判定ではなく入力の終了（Winでは、^Zでしたっけ？）を示しますから、１行入力の処理が抜けていることがわかります。（小さい順も同様ですが）

特に日本の場合は、言語記述が英語(?)なので日本語でのコメントが重要です。

No.3 回答者： wohaokele#2 回答日時： 2006/03/03 11:26

こんにちは。

大筋で #1 さんの仰られている通りだと思いますが、幾つか気が付いたので少々...

(1) 記述のソースでは、【課題】の下記をそれぞれ満たしていませんね。
　(a) このデータを１行ずつ読んでいって、..
　(b) 数値データの小さい順にリンク..

(2) int n は初期化されていない上、利用されている部分も何かおかしいような気がします。

(3) int *nextp も未初期化で、その用途は不明です^^)

上記辺りに重点をおいて、もう一度考えてみてください。

同様に、ご健闘を祈ります^^)

この回答へのお礼

アドバイスありがとうございます！

そうですね、１行ずつ読んでいってないですね…

if ( '0' <= c && c <= '9' ){
n = n * 10 + ( n - '0' );
} の後に、
else if ( c == '\n' ){
で、どうにかすればいいんですね。

あと、ソートっぽいこともしてませんね。ほんとだ。

あ～全然だめですね。
何をやってるのかわかりませんね。

はい、がんばります！！　ありがとうございます。

お礼日時：2006/03/04 02:43

No.2 回答者： sakatomo 回答日時： 2006/03/03 09:06

は～い、今回だけですよ。

（ってもったい付けるつもりはないですが）

hajime->nextp = pointer;　は
pointer -> i = n;　の後に入れたらいいです。
但し、その前に
if(hajime != NULL)
とNULLチェックが必要です。

また、memset()は、
memset(pointer, 0, sizeof( *pointer ) );
とします。
よく初心者の方は sizeof()のところを
sizeof(pointer)　としがちですが、ポインターのサイズではなく実体のサイズを指定しなければいけません。
もし、* に慣れていないのであれば
memset(pointer, 0, sizeof( struct listdata ) );
でもいいです。
入れる場所は、malloc()をした直後がいいでしょう。

最後に、今はいいですが１つ１つすべての動きを理解しないと、自作のプログラムはいつになっても作れませんので、これからしっかりと覚えてください。

ご健闘をお祈りいたします。

この回答へのお礼

あ～なんてみなさん親切なんでしょ！
本当にありがとうございます。

言われたとおりにやってみたのですが、
pointerが宣言されていませんと言われます。
int *pointer;
と書いたら、型が矛盾しますと言われました。
もう、やっぱり初めから勉強するしかない気がしてきました。

sakatomoさんのおっしゃるとおりです(>_<)
今は思いっきりその場しのぎです。
今日、やっとgetchar()とputchar()の本当の意味を理解したところです。
ゆっくり進んでいきたいと思います。。

お礼日時：2006/03/04 02:32

No.1 回答者： sakatomo 回答日時： 2006/03/03 05:42

どのような現象かわからないので、違うかも知れませんが、pointer->nextp の設定が抜けている気がします。

具体的には、
hajime->nextp = pointer; // 前のpointerに取得したpointerをセット
です。（一番最初はセットできませんが）

またmalloc()で取得したメモリ内容は値が不定ですので、memset()で0クリアした方がいいです。

あと人に見せるのであれば、どんな小さなプログラムでもコメントを入れるようにした方が解決が早いです。
（異常終了するとか、動作するけど値が違う、とかの事象もね）

この回答への補足

回答してくださって、ありがとうございます！！

でも、どこにその「memset(...)」と「hajime->nextp = pointer;」を入れたらいいか、わかりません。
ごめんなさい…

具体的に、どこの後に入れたらいいかと、
memset()の中身をどうしたらいいのか教えていただけますか？

よくわからないまま、
*memset(malloc, ' ', 0);
と書いてみたら、文法エラーになりました。
全然わかっていなくて、すみません。
手取り足取りお願いします。

それから、コメントですね。
そうですね、これからわかる部分は入れてみようと思います。

補足日時：2006/03/03 06:28