掲示板利用宣言

 次のフォームをすべてチェックしてからご利用ください。

 私は

 題名と投稿者名は具体的に書きます。
 課題の丸投げはしません。
 ソースの添付は「HTML変換ツール」で字下げします。
 返信の引用は最小限にします。
 環境(OSとコンパイラ)や症状は具体的に詳しく書きます。
 返信の付いた投稿は削除しません。
 マルチポスト(多重投稿)はしません。

掲示板2

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

No.27513

ハッシュ関数
投稿者---TAK(2006/07/05 00:59:21)


ハッシュ法によるデータ登録と検索を行うプログラムの作成です。

(1)ハッシュテーブルを初期化するプログラムを作成する。
初期化は構造体itemのname欄にスペースと終端記号を入れ、birth欄には0を入れるものとする。

(2)名前と誕生年をハッシュテーブルに格納する。
(3)名前snameをkeyとしてハッシュテーブルを検索する関数をhash_searchを作成する。この関数の返り値は同じ名前の入っているテーブルのインデックスとする。さらに、名前の比較を行った回数をstep(ポインタで受け渡し)に入れる。

ハッシュテーブルに入力するデータは、ファイルから読み込むので、hash.dat として下記のソースからコピペしてファイルを作成してください。

プログラムを実行し、検索するとエラーしか出ません。
原因が分からないので教えてください。

間違っている場所は、たぶんhash_searchだけだと思います。

#include<stdio.h> 
#include<stdlib.h> 
#define MAXLEN 81 
#define MAXITEM 137 

struct item { 
  char name[21]; 
  int birth; 
  }; 

int getline(char s[], int lim) 
{ 
 int count; 
 int ch=0; 

  count=0; 
   while( count<lim &&(ch = getchar()) !='#' &&ch !='\n'){ 
    s[count++] =ch; 
       } 
    s[count]='\0'; 
      if(ch =='#'){ 
       return -1; 
            } 
     return count; 
} 



int hash_fun(char* v) 
{ 
 int x,i,nch; 
  x=0; 
  i=0; 
  nch=0; 

 while(v[i]!='\0'){ 
  if('A'<=v[i] && v[i]<= 'Z') { 
   nch=v[i]-'A'+26; 

    }
   else if('a'<=v[i] && v[i]<= 'z') { 
    nch=v[i]-'a'; 

   }
     else { 
      x=-1; 
      return x; 
     } 
  i++; 
  x=52*x+nch; 
 } 
 if(x<0) 
   x=(-x); 
 return(x%MAXITEM); 
} 

void strcopy(char *from,char *to) 
{ 
  while((*to++ = *from++)!= '\0'){ 
    ; 
  } 
} 

int strcompare(char *a,char *b) 
{ 
  while(*a == *b){ 
    if(*a == 0) 
      return (0); 
    a++;b++; 
  } 
  if(*a<*b) 
    return(-1); 
  else 
    return(1); 
} 


void initialize(struct item table[],int max) 
{ 
  int i; 
  for(i=0;i<max;i++){ 
    table[i].name[0]= ' '; 
    table[i].name[1]='\0'; 
    table[i].birth=0; 
  } 
} 



void enter_hash(struct item table[],int max, char name[],int year) 
{ 
  int x; 
  x=hash_fun(name); 
  while(strcompare(table[x].name," ")!=0){ 
    x=(x+1)%max; 
  } 
  strcopy(name,table[x].name); 
  table[x].birth=year; 
} 

int hash_search(struct item table[],int max, char sname[], int *step) 
{ 
  int k,kk; 
  k=kk=hash_fun(sname); 
  *step=1; 
  while(table[k].name!= sname){ 
    k=(k+1)%max; 

    (*step)++; 
    if(k==kk) { 
      return -1; 
    } 
  } 
  return k; 

} 
int main(void) 
{ 
  int i,k,nch,cnt,step,year; 
  char key[21]; 
  struct item hash_table[MAXITEM]; 
  char filename[31],name[21]; 
  FILE *fpin; 

 //Initialize the hash table. 

  initialize(hash_table,MAXITEM); 

//Input data int hash table from data file. 

  printf("n>>>Input the mane of a data file.:"); 
  nch=getline(filename,30); 
  printf("File name = %s\n",filename); 

  if((fpin = fopen(filename,"r"))==NULL){ 
    printf("File is not open!!\n"); 
    exit(1); 
  } 
  while((cnt = fscanf(fpin,"%s %d",name,&year))!= EOF){ 
    if(cnt==2){ 
      enter_hash(hash_table,MAXITEM,name,year); 
    } 
    else { 
      printf("Data error!!\n"); 
    } 
  } 
  fclose(fpin); 

//Print out hash_table. 

  printf("\n*** Hash Table *** \n"); 
  for (i=0; i<MAXITEM; i++){ 
    printf("No. %3d : Name= %s \t: Birth Year = %d\n",i,hash_table[i].name,hash_table[i].birth); 
  } 

//Search hash_table. 

  printf("\n\nWhen terminate this process, input '#'and RET.\nInput asearch name. :"); 
 while((nch =getline(key,20))>0){ 
   k=hash_search(hash_table,MAXITEM,key,&step); 
   if(k>0){ 
     printf("Name= %s Birth Year = %d Step=%d\n",hash_table[k].name,hash_table[k].birth, step); 
   } 
   else{ 
     printf("There is no name that coincides with the name (%s)!!\n",key); 
   } 
   printf("\n When terminate this process, inpu '#'and RET.\nInput a search name. : "); 
 } 
 return 0; 
} 





この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> hash.dat 27514 TAK 2006/07/05 00:59:54
<子記事> Re:ハッシュ関数 27530 shu 2006/07/05 11:00:43


No.27514

hash.dat
投稿者---TAK(2006/07/05 00:59:54)


/****hash.dat****
Akaiwa 1956
Akashi 1937
Asano 1995
Ikeda 1953
Ichinose 1948
Inoue 2000
Imamura 1967
Iwashiro 1927
Uematu 1981
Utunomiya 1931
Umeda 1986
Ookubo 1927
Oonishi 1977
Oono 1962
Onoda 1994
Oohara 1958
Oomae 1983
Okazaki 1925
Okajima 1943
Okada 1975
Okushima 1958
Kajiya 1965
Kataoka 1985
Kaneoka 1983
Kanayama 2001
Kaneko 1994
Kojima 1970
Kamisaki 1955
Kawamoto 1989
Kitaguchi 1962
Kimura 1973
Kumano 1929
Kutani 1987
Kodera 1908
Kobori 1955
Goto 1967
Kondou 1943
Saitou 1986
Sakai 1983
Sakajiri 1950
Sakamoto 1938
Sakurada 1993
Sanada 1980
Sawada 1930
Shiomi 1972
Shibata 1979
Shimada 1922
Shimomura 1981
Shirai 1940
Suzuki 1969
Senda 1982
Takatori 1988
Takahashi 1961
Takeshita 2002
Taketsuji 1927
Takemura 1999
Takemoto 1937
Tanaka 1996
Tani 1942
Terada 1958
Terasaki 1992
Tsujii 1923
Tsuda 1917
Tsutsui 1953
Torii 1961
Tonomura 1986
Nakai 1944
Nakao 1972
Nakano 1968
Nakamura 1935
Nagao 1928
Natuyama 1938
Nishihama 1990
Nishihara 1951
Nishihata 1971
Noda 1983
Hamada 1941
Hayashi 2003
Bandou 1919
Higashida 1971
Hirabayashi 1933
Fujimoto 1939
Furutani 1980
Hoshi 1921
Hoshino 1929
Maekawa 1960
Matsumoto 1952
Miura 1974
Mizushima 1950
Mihara 1918
Miyakoshi 1921
Murakami 1960
Murata 1933
Mori 1987
Yano 1994
Yahata 1981
Yamazaki 1970
Yamamoto 1934
Yokoe 1955
Yokoyama 1944
Watanabe 1966
Watanuki 1973
Wada 1979

******************/




この投稿にコメントする

削除パスワード

No.27515

実行結果
投稿者---TAK(2006/07/05 01:00:57)


実行結果の例は次の通りです。

*** Hash Table ***
No. 0 : Name = : Birth Year = 0
No. 1 : Name = Kimura : Birth Year = 1973
No. 2 : Name = Kojima : Birth Year = 1970
(略)
No. 134 : Name = Okushima : Birth Year = 1958
No. 135 : Name = Taketsuji : Birth Year = 1927
No. 136 : Name = : Birth Year = 0


When terminate this process, input '#'and RET.
Input asearch name. :Fujimoto
Name = Fujimoto Birth Year = 1939 Step= 2

When terminate this process, input '#'and RET.
Input asearch name. :Nanjo
There is no name that coincides with the name (Nanjo)!!


この投稿にコメントする

削除パスワード

No.27517

Re:実行結果
投稿者---επιστημη(2006/07/05 06:15:46)


>実行結果の例は次の通りです。
>...
>When terminate this process, input '#'and RET.
>Input asearch name. :Fujimoto
>Name = Fujimoto Birth Year = 1939 Step= 2
>
>When terminate this process, input '#'and RET.
>Input asearch name. :Nanjo
>There is no name that coincides with the name (Nanjo)!!

ちゃんと動いてるやないの。



この投稿にコメントする

削除パスワード

No.27519

Re:実行結果
投稿者---επιστημη(2006/07/05 06:55:09)


ああ、ごめん。実行結果の"例"ね。

答: hash_search中の文字列比較が間違っています。



この投稿にコメントする

削除パスワード

No.27518

Re:実行結果
投稿者---ぽへぇ(2006/07/05 06:26:40)


> while(table[k].name!= sname){
ここ。これでは文字列の比較はただしくできない。



この投稿にコメントする

削除パスワード

No.27522

Re:実行結果
投稿者---acid(2006/07/05 09:04:31)


一番よくあるミスですね。
strcmpを使いましょう。


この投稿にコメントする

削除パスワード

No.27530

Re:ハッシュ関数
投稿者---shu(2006/07/05 11:00:43)


関数の群れが、main関数より上にあって読みづらい。
インデントが変。
コメントは、日本語で。
getline(),strcopy(),strcompare()は、自作しなくてもいい。
変数の宣言は、より重要なものを上に、左に。

解かり難いところの、解かり難さを解消する。
解かり易いところの、解かり易さを読み取る。


この投稿にコメントする

削除パスワード

No.27549

Re:ハッシュ関数
投稿者---επιστημη(2006/07/05 22:36:36)


>関数の群れが、main関数より上にあって読みづらい。

これはヒトによるんじゃないかしら。
僕は低レイヤのものほど上に書きます。



この投稿にコメントする

削除パスワード

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