ハッシュテーブルを用いて英和辞典を作成するプログラムをCで書いています。
コードは以下の通りです。
C
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #define NEW(p, n){p = malloc((n)*sizeof(p[0]));} typedef char* String; //後々使いやすくするため、ここでStringタイプを定義しちゃいます //英和辞書用のオブジェクトです(英語の見出しと日本語の意味のペア) typedef struct slobj_{ struct slobj_* next; String key; String jpn; }* slobj; //連結リスト typedef struct{ slobj head; slobj tail; }* slist; typedef struct{ int n; //ハッシュに格納されている要素数 int m; //ハッシュ表のサイズ slist* T; //リストの配列 } hash; //ハッシュ関数 int hfunc(hash H, String key){ int h=0, i=0; while (key[i] != 0){ h = h*101+key[i]; //ハッシュ値を計算 i++; } return abs(h) % H.m; //非負の値にして、表のサイズで割った余り } //文字列の長さを求める int string_len(String str){ int len=0; while(str[len]!=0){ len++; } return len; } //文字列を標準入力から読む String string_input(void){ int i, len; char buf[1000]; String str; scanf("%999s", buf); len = string_len(buf); NEW(str, len+1); for(i=0; i<len; i++){ str[i]=buf[i]; } str[len] = 0; return str; } //文字列が同じかどうかを判定する関数 int string_compare(String p, String q){ int c1, c2; int i=0; while(1){ c1=p[i]; c2=q[i]; if(c1<c2) return -1; if(c1>c2) return 1; if(c1==0) break; i++; } return 0; } //新しい連結リストを作成 slist slist_new(void){ slist L; NEW(L, 1); L -> head = NULL; L -> tail = NULL; return L; } //新しいリスト要素(つまり英和辞典における英語の見出しと対応する日本語のペア) slobj slobj_new(String x, String y){ slobj p; NEW(p, 1); p -> key = x; p -> jpn = y; p -> next = NULL; return p; } //連結リストの先頭に挿入 void slist_insert_head(slist L, slobj p){ p -> next = L -> head; L -> head = p; } //連結リストの末尾に挿入 void slist_insert_tail(slist L, slobj p){ if(L -> head == NULL){ L -> tail = p; L -> head = p; } else if(L -> head == L -> tail){ L -> tail = p; L -> head -> next = p; } else{ L -> tail -> next = p; L -> tail = p; } } //連結リストをプリント void slist_print(slist L) { slobj p; p = L->head; while (p != NULL){ if(string_compare(p->jpn, "NO")==0){ printf("%s\n", p->jpn); } else{ printf("%s %s\n", p -> key, p -> jpn); } p = p-> next; } } //表のサイズがmのハッシュ表を作る hash hash_new(int m){ hash H; int i; NEW(H.T, m); H.m = m; for(i=0; i<= m-1; i++){ H.T[i]=slist_new(); } return H; } //キーがkeyである要素を返す slobj hash_search(hash H, String key){ int h=hfunc(H, key); return H.T[h]->head; } void hash_insert(hash H, slobj obj){ int h=hfunc(H, obj->key); slist_insert_tail(H.T[h], obj); } void slist_free(slist L){ slobj p, q, r; p = L->head; q = p->next; while (q != NULL){ r = q; q = q-> next; free(p); p = r; } free(p); free(L); } void hash_free(hash H){ int i; for(i = 0; i <= H.m-1; i++){ if(H.T[i] -> head != NULL){ slist_free(H.T[i]); } } free(H.T); } int main(){ int i, j, k, n; String eng, jpn, s; double v; slobj p, r; hash H; slist L=slist_new(); //ここに出力する実数を格納していく int m=81239; //数千から数万程度の素数がいいらしい //ここから英和辞典を作成します。 scanf("%d", &n); //英和辞典に記録していく英語日本語ペアの数 H=hash_new(m); H.n = n; //英語日本語ペアを順次入れていく for(i=1; i<=n; i++){ eng=string_input(); jpn=string_input(); p=slobj_new(eng, jpn); hash_insert(H, p); } //ここからはkeyを入力していきます。各keyに対応する英和辞典の見出しがある場合はそのkeyおよびそれに対応する日本語を、ない場合は-1と出力します scanf("%d", &k);//以後の問い合わせの数 for(j=1; j<=k; j++){ s=string_input(); r=hash_search(H, s); if(r==NULL){ r=slobj_new(NULL, "NO"); } slist_insert_tail(L, r); } slist_print(L); slist_free(L); hash_free(H); return 0; }
こちらのコードだと、例えば
4 coffee コーヒー milk 牛乳 water 水 milkcoffee ミルクコーヒー 5 mizu milk coffe milkcoffee sake
のような比較的小さめなインプットだと正しい結果が出るのですが、それに対して
1021 hq め meayl かヨはみカヘ cvscxggb まねとそカらほ fnf ンホろトこ jprep うかフハホ vy ンてうすぬのて cqpev ム ffmznim テヲちりロちコ (中略) 992 jdysejw hit gqlakd xxy dburfwkbk xwpw aucltz (中略)
のような長いインプットだと、間違ったkeyに対応する見出しが何個か出力されてしまい、正しく動作しないようです。
自分で調べててみたところ、どうもハッシュ関数を改良したほうがよさそうなので、mの値を数万程度ではなく数百万程度の素数に変えるなどをしてみました。しかし、mにどのような値を入れてもうまくいきません。
どこを改良するべきか、アドバイスいただけるでしょうか。宜しくお願いします。
編集：
衝突が起きる場合を想定して書き直しましたが、今度は同じスロットの要素を出力するときにおかしくなります。
C
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <math.h> #define NEW(p, n){p = malloc((n)*sizeof(p[0]));} typedef char* String; //後々使いやすくするため、ここでStringタイプを定義しちゃいます //英和辞書用のオブジェクトです(英語の見出しと日本語の意味のペア) typedef struct slobj_{ struct slobj_* next; String key; String jpn; }* slobj; //連結リスト typedef struct{ slobj head; slobj tail; }* slist; typedef struct{ int n; //ハッシュに格納されている要素数 int m; //ハッシュ表のサイズ slist* T; //リストの配列 } hash; ハッシュ関数 int hfunc(hash H, String key){ int h=0, i=0; while (key[i] != 0){ h = h*3659+key[i]; //ハッシュ値を計算 i++; } return abs(h) % H.m; //非負の値にして、表のサイズで割った余り //return 1; //ハッシュ関数が全て同じ値を出す場合で実験してみました。 } //文字列の長さを求める int string_len(String str){ int len=0; while(str[len]!=0){ len++; } return len; } //文字列を標準入力から読む String string_input(void){ int i, len; char buf[1000]; String str; scanf("%999s", buf); len = string_len(buf); NEW(str, len+1); for(i=0; i<len; i++){ str[i]=buf[i]; } str[len] = 0; return str; } //文字列が同じかどうかを判定する関数 int string_compare(String p, String q){ int c1, c2; int i=0; while(1){ c1=p[i]; c2=q[i]; if(c1<c2) return -1; if(c1>c2) return 1; if(c1==0) break; i++; } return 0; } //新しい連結リストを作成 slist slist_new(void){ slist L; NEW(L, 1); L -> head = NULL; L -> tail = NULL; return L; } //新しいリスト要素(つまり英和辞典における英語の見出しと対応する日本語のペア) slobj slobj_new(String x, String y){ slobj p; NEW(p, 1); p -> key = x; p -> jpn = y; p -> next = NULL; return p; } //連結リストの先頭に挿入 void slist_insert_head(slist L, slobj p){ p -> next = L -> head; L -> head = p; } //連結リストの末尾に挿入 void slist_insert_tail(slist L, slobj p){ if(L -> head == NULL){ L -> tail = p; L -> head = p; } else if(L -> head == L -> tail){ L -> tail = p; L -> head -> next = p; } else{ L -> tail -> next = p; L -> tail = p; } } //連結リストをプリント void slist_print(slist L) { slobj p; p = L->head; while (p != NULL){ if(string_compare(p->jpn, "NO")==0){ printf("%s\n", p->jpn); } else{ printf("%s %s\n", p -> key, p -> jpn); } p = p-> next; } } //表のサイズがmのハッシュ表を作る hash hash_new(int m){ hash H; int i; NEW(H.T, m); H.m = m; for(i=0; i<= m-1; i++){ H.T[i]=slist_new(); } return H; } //キーがkeyである要素を返す slobj hash_search(hash H, String key){ slobj p; int h=hfunc(H, key); p = H.T[h]->head; while(p!=NULL){ if(string_compare(p->key, key)==0){ //keyと一致するような要素を同じスロットにあるリストから探索していきます return p; } p = p->next; } return p; } //ハッシュに入力する関数。同じスロットにハッシュされたすべての要素が連結リストに格納されるようにします。 void hash_insert(hash H, slobj obj){ int h=hfunc(H, obj->key); slist_insert_head(H.T[h], obj); } void slist_free(slist L){ slobj p, q, r; p = L->head; q = p->next; while (q != NULL){ r = q; q = q-> next; free(p); p = r; } free(p); free(L); } void hash_free(hash H){ int i; for(i = 0; i <= H.m-1; i++){ if(H.T[i] -> head != NULL){ slist_free(H.T[i]); } } free(H.T); } int main(){ int i, j, k, n; String eng, jpn, s; double v; slobj p, r; hash H; slist L=slist_new(); //ここに出力する実数を格納していく int m=81239; //数千から数万程度の素数がいいらしい //ここから英和辞典を作成します。 scanf("%d", &n); //英和辞典に記録していく英語日本語ペアの数 H=hash_new(m); H.n = n; //英語日本語ペアを順次入れていく for(i=1; i<=n; i++){ eng=string_input(); jpn=string_input(); p=slobj_new(eng, jpn); hash_insert(H, p); } //ここからはkeyを入力していきます。各keyに対応する英和辞典の見出しがある場合はそのkeyおよびそれに対応する日本語を、ない場合は-1と出力します scanf("%d", &k);//以後の問い合わせの数 for(j=1; j<=k; j++){ s=string_input(); r=hash_search(H, s); if(r==NULL){ r=slobj_new(NULL, "NO"); } slist_insert_tail(L, r); } slist_print(L); //slist_free(L); //hash_free(H); return 0; }
例えば、ハッシュ関数が常に1を出力するよう変更し、
3 coffee コーヒー milk 牛乳 water 水 2 milk coffee
という入力にした場合、
milk 牛乳 coffee コーヒー milk 牛乳 coffee コーヒー milk 牛乳 coffee コーヒー ・ ・ ・
が延々と続いてしまうのです！！！！！
編集2:
ごめんなさい、よく考えたらr=hash_search(H, s);→slist_insert_tail(L, r);のときは次のリストの要素を指すポインタもそのままコピーされるのですから、そりゃ無限ループになりますよね、、、
もう少し考えます
まだ回答がついていません
会員登録して回答してみよう
