再掲:C言語の課題で悩んでいます。

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
kew
記事: 9
登録日時: 9年前

再掲:C言語の課題で悩んでいます。

#1

投稿記事 by kew » 9年前

ハッシュ表に2次元平面上の1点を表現した構造体をデータとして登録する関数を作り、0~9999までの一様乱数を発生させ、それを構造体に代入し、得られた構造体を上記の関数を用いてハッシュ表に登録したいのですが、セグメンテーションフォルトが出てうまくいきません。いろいろと考えて試してみたのですが、解決できませんでした。
自分で考えたプログラムを載せておきます。

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#define B 10000
#define A 100

コード:

typedef struct _point{
  int x;
  int y;
}POINT;

typedef struct h_cell{
  POINT data;
  struct h_cell *next;
}CELL;

CELL H[B];
CELL *head[B];


CELL insert_cell_top(POINT p,int a){
  CELL *new_cell;

  new_cell=(CELL*)malloc(sizeof(CELL));
  new_cell->data=p;
  new_cell->next=head[a];
  head[a]=new_cell;

  return *new_cell;
}

int h(POINT p){  
  return (p.x)*(p.y)%B;
}

int insert_hash(POINT p){
  CELL *a;
  int b=h(p);
  H[b]=*head[b];
  a=&H[b];
  while(a->next!=NULL){
    if(a->data.x!=p.x && a->data.y!=p.y){
      H[b]=insert_cell_top(p,b);
      a=a->next;
      return 1;
    }
    else return 0;
  }
  return 0;
}
    
int search_hash(POINT p){
  int b=h(p);
  CELL *a;
  a=&H[b];
  while(a->next!=NULL){
    if(a->data.x==p.x && a->data.y==p.y){
      return 1;
      a=a->next;
    }else return 0;
  }
  return 0;
}

void hash_status(){
  int i,j=0;
  int max,min;
  CELL *a;
  for(i=0;i<B;i++){
    a=&H[i];
    while(a->next!=NULL)

    printf("Number of H[%d]'s data=%d\n",i,j);
    printf("H[%d]'smax=%d,min=%d\n",i,max,min);
  }
}

int main(void){
  int i,j,X;
  srand((unsigned)time(NULL));
  POINT a[A];
  for(j=0;j<A;j++){
    a[j].x=0;
    a[j].y=0;
  }
  for(i=0;i<A;i++){
    a[i].x=rand()%9999;
    a[i].y=rand()%9999;
    insert_hash(a[i]);
  }
  
 
  
  return 0;
}

box
記事: 2002
登録日時: 14年前

Re: 再掲:C言語の課題で悩んでいます。

#2

投稿記事 by box » 9年前

どっちの投稿にコメントしたらいいのか悩んでいます。が、便宜上、こっちに回答します。
kkkという名前がちょっといやなので。
さて、セグメンテーションフォールトの件は、いったん置いておくとして…。
kew さんが書きました:0~9999までの一様乱数を発生させ
そうなっていないように見えます。というのは、
kew さんが書きました:

コード:

    a[i].x=rand()%9999;
    a[i].y=rand()%9999;
このコードでは、9999は発生しないからです。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

アバター
みけCAT
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:

Re: 再掲:C言語の課題で悩んでいます。

#3

投稿記事 by みけCAT » 9年前

insert_hash関数とsearch_hash関数の中に、ループと見せかけて必ず1回目でreturnする部分がありますね。
詳しく見ていませんが、何かの間違いの疑いがあります。
kew さんが書きました:セグメンテーションフォルトが出てうまくいきません。
少なくとも、デバッガなどでどこで落ちているかを確認しましたか?
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
みけCAT
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:

Re: 再掲:C言語の課題で悩んでいます。

#4

投稿記事 by みけCAT » 9年前

headは明示的に初期化されていないポインタ型の静的変数なので、ヌルポインタで初期化されます。
これの要素をinsert_hash関数内でデリファレンスしていますが、これは未定義動作なので、やってはいけません。
また、hash_status関数ではH[0].nextがNULLの場合は未初期化の自動変数minおよびmaxの値を使って未定義動作になり、H[0].nextがNULLでない場合は無限ループになります。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

kew
記事: 9
登録日時: 9年前

Re: 再掲:C言語の課題で悩んでいます。

#5

投稿記事 by kew » 9年前

ハッシュ表に座標データを登録する処理はできたのですが、各ハッシュに登録されている要素の個数を求める処理がうまくいきません。ある1つのハッシュについて調べ終わった後に、次のハッシュについて調べるようにする処理がうまくいっていないのだと思います。
今自分で書いてみたものは

コード:

void hash_status(){
  int i,j=0,m,n;
  int A[B];
  double ave,p;
  CELL *a;
  int max=0,min=0;

  for(i=0;i<B;i++){
    a=&H[i];
    while(a!=NULL){
      A[i]++;
      a=a->next;
    }
  }
 
  max=0;
  min=0;
  for(m=0;m<B;m++){
    if(A[m]>=max)max=A[m];
    if(A[m]<=min)min=A[m];
    
  }
  for(m=0;m<B;m++){
    n+=A[m];
  }
  ave=n/B;
  
  for(m=0;m<B;m++){
    p+=(ave-A[m])*(ave-A[m]);
  }

  printf("varience=%f\n",(double)p/B);
  printf("max=%d,min=%d\n",max,min);

}
    
で、この関数の最初のfor文の部分がわからない箇所です。
最終的にすべてのハッシュについて調べ終わった後に要素数の最大値最小値分散を求めたいので、各要素数は配列に格納するようにしたいです。

コード:

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
#define B 10000
#define L 10

typedef struct _point{
  int x;
  int y;
}POINT;

typedef struct h_cell{
  POINT data;
  struct h_cell *next;
}CELL;

CELL H[B];


CELL *insert_cell_to_list_top(CELL *head,POINT p){
  CELL *new_cell;

  new_cell=(CELL*)malloc(sizeof(CELL));
  new_cell->data=p;
  new_cell->next=head;

  return new_cell;
}

int h(POINT p){  
  return (p.x+p.y)%B;
}

int insert_hash(POINT p){
  int b=h(p);
  CELL *a=&H[b];
  if(a!=NULL){
    while(a!=NULL){
      if(a->data.x==p.x && a->data.y==p.y){
	return 0;
      }
      a=a->next;
    }
  }else
    {
    H[b]=*insert_cell_to_list_top(&H[b],p);
    return 1;
    }
  return 0;
}
    
int search_hash(POINT p){
  int b=h(p);
  CELL *a;
  a=&H[b];
  while(a!=NULL){
    if(a->data.x==p.x && a->data.y==p.y){
      return 1;
      a=a->next;
    }else return 0;
  }
  return 0;
}

void hash_status(){
  int i,j=0,m,n;
  int A[B];
  double ave,p;
  CELL *a;
  int max=0,min=0;

  for(i=0;i<B;i++){
    a=&H[i];
    while(a!=NULL){
      A[i]++;
      a=a->next;
    }
  }
 
  max=0;
  min=0;
  for(m=0;m<B;m++){
    if(A[m]>=max)max=A[m];
    if(A[m]<=min)min=A[m];
    
  }
  for(m=0;m<B;m++){
    n+=A[m];
  }
  ave=n/B;
  
  for(m=0;m<B;m++){
    p+=(ave-A[m])*(ave-A[m]);
  }

  printf("varience=%f\n",(double)p/B);
  printf("max=%d,min=%d\n",max,min);

}
    

int main(void){
  int i,j,X;
  srand((unsigned)time(NULL));
  POINT *d;
  d=(POINT*)malloc(sizeof(POINT)*L);

  clock_t start,end;
  start=clock();
  for(i=0;i<L;i++){
    d[i].x=rand()%9999;
    d[i].y=rand()%9999;
    printf("%d,%d\n",d[i].x,d[i].y);
    X=insert_hash(d[i]);
  }
  end=clock();
  hash_status();
  printf("%f sec\n",(double)(end-start)/CLOCKS_PER_SEC);
  return 0;
}

アバター
みけCAT
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:

Re: 再掲:C言語の課題で悩んでいます。

#6

投稿記事 by みけCAT » 9年前

hash_status関数において自動変数A, m, pが初期化の前に値を読み取られ、使用されています。
これは未定義動作になるので、やってはいけません。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

閉鎖

“C言語何でも質問掲示板” へ戻る