【掲示板ご利用上の注意】

 ※題名は具体的に!
 ※学校の課題の丸投げ禁止!
 ※ソースの添付は「HTML変換ツール」で字下げ!
 ※返信の引用は最小限に!
 ※環境(OSとコンパイラ)や症状は具体的に詳しく!
 ※マルチポスト(多重投稿)は謹んで!

 詳しくはこちら



 本当はこんなに大きく書きたくはないのですが、なかなか守っていただけなくて…。
 守ってくださいね。お願いします。(by管理人)

C言語ソース⇒HTML形式ツール   掲示板2こちら


管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.18530

ハッシュ表のデータ衝突調査プログラム
投稿者---まさと(2004/12/06 19:29:33)


ハッシュ法を作成しています。
1000から2000個程のデータをハッシュ表に格納して衝突回数を調査するという課題を行っているのですが、
データ総数によってエラーが出てしまい、どうしようもなく困っています。
データが100程度ならなんとか、オペランドエラーが出なくなりますが、
総数を多くすると、エラーが出現します。
下にプログラムを貼り付けますので、良くない所をどんどん指摘、御教授
下さい。宜しくお願い致します。

エラー画面:行番号134:初期値エラー
      行番号136:'!='の演算項が不当
      行番号70:'='の左辺値オペランドが不当
ハッシュ表に格納するデータは[数字 文字列]がランダムに格納されているもので、データ総数は1000程度です。
環境はWindows Me、Ultra-C Pro2を使用しています。

データ例:
978 rejoice
743 duplicate
205 lantern
254 shed
631 chop
93 livestock
918 network
380 milestone
239 advocate
212 visibility
88 label
489 sociobiology
251 cram
932 synchronize
187 interconnect


/* ハッシュ法 */
/* ハッシュ関数:除算法(division method) */

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

#define HashSize 997        /*ハッシュ表サイズ*/
#define NameSize 20
#define TableSize 997

/*--ハッシュ表に格納するデータの構造体--*/
typedef struct cell{
  int number;
  char name[NameSize];
  struct cell *next;
} Data;

Data *hashtable[HashSize];    /*ハッシュ表*/
FILE *fp;

void MakeHashTable(void);
void Chaining(Data *, unsigned int);
unsigned int Hash(char *);
void PrintHash(void);
void PrintHashBunsan(void);
void Free(void);

int main(void)
{
  char buf[NameSize];
  MakeHashTable();
  PrintHash();
  PrintHashBunsan();
  Free();
  fclose(fp);
  return(0);
}

void MakeHashTable()
{
  Data *temp;
  int i;
  for(i=0; i<HashSize; i++)
    hashtable[i]=NULL;
  if((fp=fopen("word.txt", "r"))==NULL){
    printf("エラー\n");
    exit(1);
  }
  for(;;){
    temp=(Data *)malloc(sizeof(Data));
    if(fscanf(fp, "%d", &temp->number)!=EOF){
      fscanf(fp, "%s", temp->name);
      temp->next=NULL;
      Chaining(temp, Hash(temp->name));
      free(temp);
    }
    else{
      free(temp);
      break;
    }
  }
}

void Chaining(Data *temp, unsigned int f)
{
  Data *s;
  if(hashtable[f]==NULL){
    hashtable[f]=(Data *)malloc(sizeof(Data));
    *hashtable[f]=*temp;
  }
  else{
    s=hashtable[f];
    while(s->next)
      s=s->next;
    s->next=(Data *)malloc(sizeof(Data));
    *s->next=*temp;
    s->next->next=NULL;
  }
}

/*--ハッシュ関数:除算法(division method)--*/
unsigned int Hash(char *buf)
{
  unsigned int value;
  for(value=0; *buf!='\0'; buf++)
    value=*buf+value*11;
  return value%HashSize;        /*valueをHashSizeで割った剰余(valueとHashSizeは整数でなければならない)*/
}

/*--ハッシュ表中の全データを表示--*/
void PrintHash(void)
{
  Data *s;
  int i;
  for(i=0; i<HashSize; i++){
    printf("[%d]\t", i);
    s=hashtable[i];
    while(s){
      printf("%4d %-16s\t -> ", s->number, s->name);
      s=s->next;
    }
    printf("(NULL)\n");
  }
}

/*--ハッシュ表のクリーンアップ--*/
void Free(void)
{
  int i;
  Data *s, *t;
  for(i=0; i<HashSize; i++){
    s=hashtable[i];
    while(s){
      t=s->next;
      free(s);
      s=t;
    }
  }
}





void PrintHashBunsan(void)
{
  int i, total=0;
  int table[TableSize];
  
  for(i=0; i<TableSize; i++)
    table[i]=0;
  for(i=0; i<HashSize; i++){
    Data ptr=hashtable[i];
    int n=0;
    if(ptr!=NULL){
      for(; ptr!=NULL; ptr=ptr->next)
        n++;
    }
    total+=n;
    if(n<TableSize){
      table[n]++;
    }
    else{
      fprintf(stderr, "table size error%d\n", n);
    }
  }
  for(i=0; i<TableSize; i++){
    if(!(i%8))
      putchar('\n');
    printf("%3d:%3d", i, table[i]);
  }
  printf("\n 合計 %d 個\n", total);
}





この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:ハッシュ表のデータ衝突調査プログラム 18531 RAPT 2004/12/06 20:34:06
<子記事> Re:ハッシュ表のデータ衝突調査プログラム 18533 nop 2004/12/06 21:17:59


No.18531

Re:ハッシュ表のデータ衝突調査プログラム
投稿者---RAPT(2004/12/06 20:34:06)


ってか、データ数云々以前に、コンパイルエラーが出ますが。
# Windows2000sp4/VC++6.0sp6/Console-App/Warning-Level:4

Data ptr=hashtable[i];
hashtableの型は Data* 型、ptr の型は Data 型。
char buf[NameSize];
使用されていません…。



この投稿にコメントする

削除パスワード

No.18532

Re:ハッシュ表のデータ衝突調査プログラム
投稿者---まさと(2004/12/06 21:10:28)


>
ってか、データ数云々以前に、コンパイルエラーが出ますが。
# Windows2000sp4/VC++6.0sp6/Console-App/Warning-Level:4

Data ptr=hashtable[i];
hashtableの型は Data* 型、ptr の型は Data 型。
char buf[NameSize];
使用されていません…。


hashtable、ptrの型は解決しましたが、
まだ、'!='の演算項が不当、'='の左辺値オペランドが不当と出てしまいます。
フローチャートも作成しましたが、
コンパイラエラーと出て、何が原因なのかわかりません。
誠に申し訳ございませんが、御教授お願い致します。


/* ハッシュ法 */
/* ハッシュ関数:除算法(division method) */

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

#define HashSize 150        /*ハッシュ表サイズ*/
#define NameSize 20
#define TableSize 150

/*--ハッシュ表に格納するデータの構造体--*/
typedef struct cell{
  int number;
  char name[NameSize];
  struct cell *next;
} Data;

Data *hashtable[HashSize];    /*ハッシュ表*/
FILE *fp;

void MakeHashTable(void);
void Chaining(Data *, unsigned int);
unsigned int Hash(char *);
void PrintHash(void);
void PrintHashBunsan(void);
void Free(void);

int main(void)
{
  MakeHashTable();
  PrintHash();
  PrintHashBunsan();
  Free();
  fclose(fp);
  return(0);
}

void MakeHashTable()
{
  Data *temp;
  int i;
  for(i=0; i<HashSize; i++)
    hashtable[i]=NULL;
  if((fp=fopen("word.txt", "r"))==NULL){
    printf("エラー\n");
    exit(1);
  }
  for(;;){
    temp=(Data *)malloc(sizeof(Data));
    if(fscanf(fp, "%d", &temp->number)!=EOF){
      fscanf(fp, "%s", temp->name);
      temp->next=NULL;
      Chaining(temp, Hash(temp->name));
      free(temp);
    }
    else{
      free(temp);
      break;
    }
  }
}

void Chaining(Data *temp, unsigned int f)
{
  Data *s;
  if(hashtable[f]==NULL){
    hashtable[f]=(Data *)malloc(sizeof(Data));
    *hashtable[f]=*temp;
  }
  else{
    s=hashtable[f];
    while(s->next)
      s=s->next;
    s->next=(Data *)malloc(sizeof(Data));
    *s->next=*temp;
    s->next->next=NULL;
  }
}

/*--ハッシュ関数:除算法(division method)--*/
unsigned int Hash(char *buf)
{
  unsigned int value;
  for(value=0; *buf!='\0'; buf++)
    value=*buf+value*11;
  return value%HashSize;        /*valueをHashSizeで割った剰余(valueとHashSizeは整数でなければならない)*/
}

/*--ハッシュ表中の全データを表示--*/
void PrintHash(void)
{
  Data *s;
  int i;
  for(i=0; i<HashSize; i++){
    printf("[%d]\t", i);
    s=hashtable[i];
    while(s){
      printf("%4d %-16s\t -> ", s->number, s->name);
      s=s->next;
    }
    printf("(NULL)\n");
  }
}

/*--ハッシュ表のクリーンアップ--*/
void Free(void)
{
  int i;
  Data *s, *t;
  for(i=0; i<HashSize; i++){
    s=hashtable[i];
    while(s){
      t=s->next;
      free(s);
      s=t;
    }
  }
}





void PrintHashBunsan(void)
{
  int i, total=0;
  int table[TableSize];
  
  for(i=0; i<TableSize; i++)
    table[i]=0;
  for(i=0; i<HashSize; i++){
    Data *ptr=hashtable[i];
    int n=0;
    if(*ptr!=NULL){
      for(; *ptr!=NULL; *ptr=*ptr->next)
        n++;
    }
    total+=n;
    if(n<TableSize){
      table[n]++;
    }
    else{
      fprintf(stderr, "table size error%d\n", n);
    }
  }
  for(i=0; i<TableSize; i++){
    if(!(i%8))
      putchar('\n');
    printf("%3d:%3d", i, table[i]);
  }
  printf("\n 合計 %d 個\n", total);
}



この投稿にコメントする

削除パスワード

No.18536

Re:ハッシュ表のデータ衝突調査プログラム
投稿者---RAPT(2004/12/06 21:39:37)


な〜んで、余計な事するかなぁ。
if(*ptr!=NULL){ for(; *ptr!=NULL
ptr の宣言部だけ修正すればその2つのコンパイルエラーも取れたのに…。 if(ptr!=NULL){ for(; ptr!=NULL 構造体とポインタの理解が甘いっ、甘すぎるっ!! ってか、な〜んで、コンパイルエラーのメッセージを素直に受け止めない? そのまま読めば分かるはず。



この投稿にコメントする

削除パスワード

No.18537

Re:ハッシュ表のデータ衝突調査プログラム
投稿者---まさと(2004/12/06 21:53:05)


>
な〜んで、余計な事するかなぁ。
if(*ptr!=NULL){ for(; *ptr!=NULL
ptr の宣言部だけ修正すればその2つのコンパイルエラーも取れたのに…。 if(ptr!=NULL){ for(; ptr!=NULL 構造体とポインタの理解が甘いっ、甘すぎるっ!! ってか、な〜んで、コンパイルエラーのメッセージを素直に受け止めない? そのまま読めば分かるはず。


誠に申し訳ございません。お恥ずかしい限りです。
構造体とポインタの勉強がまだまだ至らなく、もっと勉強しなければと感じています。
後は、もうひとつのエラーですが、これもいろいろ工夫しているのですが、
チェイン関数の中で、どうもうまくいきません。


この投稿にコメントする

削除パスワード

No.18533

Re:ハッシュ表のデータ衝突調査プログラム
投稿者---nop(2004/12/06 21:17:59)


>Data ptr=hashtable[i];
>if(ptr!=NULL){

構造体そのものに、「!=」は適用出来ないだろ…。


# エラーメッセージはよく読め。


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧