C言語関係掲示板

過去ログ

No640 線形リストを使ってエラトステネスのふるい

[戻る] [ホームページ]
No.6840

線形リストを使ってエラトステネスのふるい
投稿者---BEE(2003/05/28 01:10:48)


こんにちは。
線形リストを使って、エラトステネスのふるいを再現する
プログラムを作れ、という問題を出されまして、
線形リストというものに対して理解がどうもはっきりせず、
よろしければご教授お願いしたく、書き込ませていただく次第です。

以下のようにほとんどが与えられていて、
少しだけ書き足せば完成するようになっているのですが、
どうもうまくいきません。
私がやった方法ではコンパイルは出来ても、
実行するとDOS窓が強制終了してしまいます。

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

struct data_list {
  struct data_list *next;
  int    data;
};

/*線形リストの要素としてデータを加えていく関数*/
struct data_list *add_data_to_list(struct data_list *list, int data);
/*線形リストの要素の中から任意のデータを消去する関数*/
struct data_list *delete_data_from_list(struct data_list *list, int data);
/*線形リストの要素を順に表示していく関数*/
void print_list(struct data_list *arg);
/*一応自分で考えてみた、線形リストの中で次の要素へと移動させる関数*/
struct data_list *move_next(struct data_list *next);


void main (void) {
  int m,n;
  struct data_list root;
  
  root.next = NULL;
  /*ここから私が考えた部分です*/
  /*線形リストの要素として、2から1000までを格納*/
  for (n = 2; n < 1001; n++) {
    root.next = add_data_to_list(root.next, n);
  }
  /*2から1000までの999回をみていくfor文*/
  for(m=0;m<999;m++){
	  /*要素がNULLで無い、つまり素数でなければ*/
	  if(root.next!=NULL){
		  /*素数の倍数で1000以下の数字を要素から除く*/
    for(n=2;root.data*n<1001;n++){
      root.next = delete_data_from_list(root.next, root.data*n);
    }
	/*次の要素へ*/
    root.next=move_next(root.next);
  }
  else{
	  /*要素がNULLの時、次の要素へ*/
	 root.next = move_next(root.next);
	 }
	}
	/*ここまでが考えたものです*/
  print_list(root.next);
}




struct data_list *add_data_to_list(struct data_list *list, int data)
{
  struct data_list *t;
  
  t = (struct data_list *) malloc(sizeof(struct data_list));
  t->next = list;
  t->data = data;
  list = t;
  return list;
}



struct data_list *delete_data_from_list(struct data_list *list, int data)
{
            struct data_list *t;
            if (list == NULL) {
	      return list;
	    }

if (list->data == data) {
  if (list->next == NULL) {
    free(list);
    return NULL;
  }
  else {
    t = list->next;
    free(list);
    return t;
  }
}
list->next = delete_data_from_list(list->next, data);
return list;
}




void print_list(struct data_list *arg)
{
  if (arg == NULL) return;
  print_list(arg->next);
  printf("%p : %d\n", arg, arg->data);
}

struct data_list *move_next(struct data_list *next){
	/*線形リストの次の要素へ移動*/
	return next->next;
}


WindowsME、Borland C++5.5でコンパイルしました。

No.6848

Re:線形リストを使ってエラトステネスのふるい
投稿者---大学生1(2003/05/28 11:56:25)


>>if(root.next!=NULL)
{
・・・
}
else{
/*要素がNULLの時、次の要素へ*/
root.next = move_next(root.next);
}

ここの条件が全部NULLになってるようです。
ためしにroot.nextの前にprintfでerrorとでも出力してみてください。
それとroot.next = move_next(root.next);この部分も
おかしいようです。



No.6873

Re:線形リストを使ってエラトステネスのふるい
投稿者---BEE(2003/05/28 20:56:59)


>ここの条件が全部NULLになってるようです。
>ためしにroot.nextの前にprintfでerrorとでも出力してみてください。

if(root.next!=NULL){
		  printf("error\n");
		  /*素数の倍数で1000以下の数字を要素から除く*/
    for(n=2;root.data*n<1001;n++){
      root.next = delete_data_from_list(root.next, root.data*n);
    }
	/*次の要素へ*/
    root.next=move_next(root.next);
  }


このようにする、ということでしょうか。
こうすると、errorが表示されて、
DOS窓が強制終了されてしまいました。

>それとroot.next = move_next(root.next);この部分も
>おかしいようです。

上のことを考えると、やはりここがおかしいのだと思うのですが、
線形リストにおいて次の要素に移るにはどうすればよいのか、
色々なホームページで説明を見てみたのですが、
どうもしっくりせず、とりあえず次のような関数に変えてみました。

struct data_list *move_next(struct data_list *next){
	/*線形リストの次の要素へ移動*/
	
    struct data_list *p;
    p = malloc(sizeof(struct data_list)); /* 新しいデータ */

    p->next = next;
    next=p;
	return next;
}


このようにすると、強制終了はしなくなったのですが、
よく分からない数値が膨大に表示されてしまいました。
何が問題なのでしょうか…。

No.6880

Re:線形リストを使ってエラトステネスのふるい
投稿者---BB(2003/05/28 22:04:05)


>線形リストにおいて次の要素に移るにはどうすればよいのか、
次の要素に移るというのがよくわかりませんが、わざわざそう考えなくてもよいのでは?
main関数の中でdelete_data_from_list関数で素数の倍数を消していくだけでいいのではないでしょうか。
あと、root.dataにはどういう値が入っているんでしょうね・・・


No.6882

Re:線形リストを使ってエラトステネスのふるい
投稿者---TDa(2003/05/28 22:32:22)


申し訳ないですがコードの意味がよくわかっていません。でも
/*2から1000までの999回をみていくfor文*/
for(m=0;m<999;m++){
と言う部分が有りますがこれが'?'です。

リストを最初から最後まで舐めるイディオムが有って
今のリスト構造ならこうです。

struct data_list *p;
for (p = list; p->next != NULL; p = p->next) { ... }

配列をループで繰り返すイディオムと似たような形をしていると思います。
リストは配列と違いサイズも固定ではないですし、途中で削除も簡単です。
というよりそういうデータのためのものです。データ構造が保たれていれば
上記のforループで常にリストのはじめから最後まで繰り返し処理ができます。

No.6884

Re:線形リストを使ってエラトステネスのふるい
投稿者---BEE(2003/05/28 23:01:02)


>>BBさん

>main関数の中でdelete_data_from_list関数で素数の倍数を消していくだけでいいのではないでしょうか。

確かにそのとおりですね。
素数を求めて、その倍数を消していけば早かったですね。
BBさんのアドバイスを元に、
prime_check という素数かどうかを判定するプログラムを
作って、以下のようにしてみたところ、うまくいきました。
ありがとうございました。

for(m=2;m<1001;m++){
	  if(prime_check(m)==1){
		  /*素数の倍数で1000以下の数字を要素から除く*/
    for(n=2;m*n<1001;n++){
      root.next = delete_data_from_list(root.next, m*n);
    }
  }
 }


ところで、
>あと、root.dataにはどういう値が入っているんでしょうね・・・
とは、どういう意味でしょう?
root.dataには、最初はそれぞれ
2〜1000が入っていて、その後、素数のみが残っている、
そういうことでよろしいのでしょうか。

>>TDaさん

>/*2から1000までの999回をみていくfor文*/
> for(m=0;m<999;m++){
>と言う部分が有りますがこれが'?'です。

すみません、表現をとても分かりにくいものにしてしまっていました。
これは、各線形リストの要素である2〜1000について、
その数字が素数の倍数なら、繰り返し文の中で既に消されているはずなので、
消されていればNULLになっている→NULLでなければ素数、
そういう作業を999回、つまり、2〜1000まで一つずつチェックしていく、
ということです。
これも分かりにくく、申し訳ないですが…。


>リストを最初から最後まで舐めるイディオムが有って
>今のリスト構造ならこうです。
>
>struct data_list *p;
>for (p = list; p->next != NULL; p = p->next) { ... }
>
>配列をループで繰り返すイディオムと似たような形をしていると思います。
>リストは配列と違いサイズも固定ではないですし、途中で削除も簡単です。
>というよりそういうデータのためのものです。データ構造が保たれていれば
>上記のforループで常にリストのはじめから最後まで繰り返し処理ができます。

なるほど。
僕が伺いたかった動作が、まさにTDaさんの書いてくださったものです。
p=p->next という記述に違和感を感じるのですが、
これはfor文中で使うのであれば良いのでしょうか。
僕も、このp=p->nextという記述を一度してみたのですが
(main関数内でwhile文中に)、
そうすると、確か「不正な構造体の演算」と言われてしまったのですが…。



No.6886

Re:線形リストを使ってエラトステネスのふるい
投稿者---BB(2003/05/29 00:06:03)


>>あと、root.dataにはどういう値が入っているんでしょうね・・・
>とは、どういう意味でしょう?
>root.dataには、最初はそれぞれ
>2〜1000が入っていて、その後、素数のみが残っている、
>そういうことでよろしいのでしょうか。

もうできたのならいいんですが、root.dataに2〜1000が入るんじゃなくて、
root.next->dataに入るって事を言いたかったわけで・・・
ちなみにroot.dataには出力してみるとわかりますが1ばっかりです。
だから、最初のがだめだったんでは?

あと、雑談になりますが、H先生の課題はいつもむずかしいですな〜w

No.6889

Re:線形リストを使ってエラトステネスのふるい
投稿者---BEE(2003/05/29 01:41:39)


>もうできたのならいいんですが、root.dataに2〜1000が入るんじゃなくて、
>root.next->dataに入るって事を言いたかったわけで・・・
>ちなみにroot.dataには出力してみるとわかりますが1ばっかりです。
>だから、最初のがだめだったんでは?

あ、なるほど。
僕が言いたかったのは、
各root.dataに2,3…,1000が入っているということでして。
つまり、root.next->data , root.next->next->data…
に入っている、ということですよね?
それが、僕が最初に書いたプログラムの失敗原因になるのでしょうか。


>あと、雑談になりますが、H先生の課題はいつもむずかしいですな〜w

ほんとにそうですね〜。
毎回もの凄い時間悩まされます…。

No.6893

Re:線形リストを使ってエラトステネスのふるい
投稿者---TDa(2003/05/29 09:06:06)


>p=p->next という記述に違和感を感じるのですが、
これはもう慣れです。i = i + 1;は数学の感覚からするとおかしいですよ。

さて課題は一応できているようですが線形リストの扱いに不慣れのようでしたの
で私もコーディングしてみました。全部だと長くなるのでプロトタイプ宣言と
mainだけにします。2重ループの内側が今ひとつスマートに書けなかったのです
が、、、、。

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

typedef struct data_list {
    struct data_list *next;
    int    data;
} List;

/*線形リストの要素としてデータを加えていく関数*/
List *addData(List *list, int data);
/*引数の次の要素を削除する関数*/
int deleteData(List *p);
/*線形リストの要素を順に表示していく関数*/
void printList(List *p);
/*リストの解放*/
void freeList(List *list);

int main (void)
{
    int i, baisu;
    List root = { NULL, 0xdeadbeef /* dammy */};
    List *p, *q, *prev;
    

    /*線形リストの要素として、2から1000までを格納*/
    for (i = 1000; i >= 2; --i) {
        root.next = addData(root.next, i);
    }
    
    for (p = root.next; p; p = p->next) {
        q = p->next;
        prev = p;
        baisu = (p->data) * 2;
        while (q) {
            
            if (baisu < q->data)
                baisu += p->data;   /* リストの数値の方が大きくなったら割る数を大きくする */
            
            if (baisu == q->data) {
                /*素数の倍数と一致するものはリストから削除*/
                q = q->next;
                deleteData(prev);
                baisu += p->data;
            } else {
                /*ポインタを進める*/
                prev = q;
                q = q->next;
            }
        }
    }

    printList(root.next);
    
    freeList(root.next);
    
    return 0;
}


No.6921

Re:線形リストを使ってエラトステネスのふるい
投稿者---BEE(2003/05/29 20:49:03)


なるほど…、こんなソースを書けばよいのですね…、
といいたいところなのですが、
やはり私は、線形リストの使い方についてまだまだ理解が足りないようです。

>if (baisu < q->data)
>baisu += p->data; /* リストの数値の方が大きくなったら割る数を大きく
>する */
>if (baisu == q->data) {
> /*素数の倍数と一致するものはリストから削除*/
> q = q->next;
> deleteData(prev);
> baisu += p->data;
> }

この部分について、確信をもてないのですが…、
これはつまり、1000から順に、
1000*2を消去(出来ない)、999*2を消去(出来ない)…3*333を消去、
2*500を消去…2*2を消去、と、
p->data*2が1000を超えない限り、それを消していく、
ということでよろしいのでしょうか。



No.6923

Re:線形リストを使ってエラトステネスのふるい
投稿者---TDa(2003/05/29 21:16:03)



>>if (baisu < q->data)
>>baisu += p->data; /* リストの数値の方が大きくなったら割る数を大きく
>>する */
>>if (baisu == q->data) {
>> /*素数の倍数と一致するものはリストから削除*/
>> q = q->next;
>> deleteData(prev);
>> baisu += p->data;
>> }
>
>この部分について、確信をもてないのですが…、
>これはつまり、1000から順に、
>1000*2を消去(出来ない)、999*2を消去(出来ない)…3*333を消去、
>2*500を消去…2*2を消去、と、
>p->data*2が1000を超えない限り、それを消していく、
>ということでよろしいのでしょうか。

コードの一部だけでかえって混乱させてしまったようです。私のコードではリストは1000から2までを要素にしています。なのでrootからたどると2,3,4...とな
るのです。
そして私のコードではエラツステネスのふるいの動作をほぼそのままやっていま
す。
外のループではリストの頭から要素一つを選びます。
内側ではその数の倍数でそれ以降の数が割り切れるかテストします。
割り切れた時はその要素を削除します。割り切れないときはポインタをすすめます。

長くなって悪い気もしますがコードの残り部分です。前回のコードとあわせれば
コンパイル、実行できます。デバッガを使うか、whileの内側に
printf("%d, %d, %d\n", q->data, q->next->data, q->next->next->data);
getchar();
のようなコードを置いて変数の変化を追うと動きがわかると思います。

List *addData(List *list, int data)
/* =============================================
    引数dataをリストに格納
    リストの先頭に新たな要素が加わる。
    リストの先頭を返す
  ============================================== */
{
    List *t;
    
    t =  malloc(sizeof(List));
    t->next = list;
    t->data = data;
    list = t;
    
    return list;
}

int deleteData(List *prev)
/* =================================================
    prevが指している次の要素を削除する
   ================================================= */
{
    List *p;

    /* prevの次がNULLなら1を返して抜ける */
    if (!prev->next)
        return 1;
    p = prev->next;
    prev->next = p->next;
    free(p);

    return 0;
}

void printList(List *list)
/* =================================================
    Listの内容を表示
   ================================================= */
{
    List *p;
    int line;
    
    /* リストが空の場合 */
    if (list == NULL) {
        printf("リストは空です。\n");
        return;
    }
    
    /* lineでカウントして5つ表示ごとに改行する */
    for (p = list, line = 1; p; p = p->next, ++line) {
        printf("% 8d", p->data);
        if (line == 5) {
            putchar('\n');
            line = 0;
        }
    }
}

/*リストの解放*/
void freeList(List *list)
{
    List *tmp, *p;
    
    p = list;
    while (p){
        tmp = p;
        p = p->next;
        free(tmp);
    }
}




No.6927

Re:線形リストを使ってエラトステネスのふるい
投稿者---BEE(2003/05/29 22:54:20)


詳しいご説明、恐れ入ります。
とても分かりやすく、大変参考になります。

>コードの一部だけでかえって混乱させてしまったようです。私のコードではリス>トは1000から2までを要素にしています。なのでrootからたどると2,3,4...と
>なるのです。

つまり、add関数はrootに向かって戻っていき、
delete関数を含む繰り返しの部分では、rootから進んでいく、
ということで良いのでしょうか。

>デバッガを使うか、whileの内側に
>printf("%d, %d, %d\n", q->data, q->next->data, q->next->next->data);
>getchar();
>のようなコードを置いて変数の変化を追うと動きがわかると思います。
>
なるほど。変数の動き、確認してみますね。

本当にありがとうございます。