プログラムは基本的に、端末から入力された単語のアナグラムである特定の単語リスト内の文字列を検索します。次のアルゴリズムに従います。
- リスト内のすべての単語を並べ替える
- すべてのアナグラムが同じハッシュ値を持つように、並べ替えられた単語のハッシュ値を計算します
- ハッシュ テーブルを作成し、ハッシュ値、並べ替えられた単語、および実際の単語を格納して連鎖を開始します。
- ハッシュテーブルをチェックしてアナグラムを見つける
問題は、私のマシンでは完全に動作するが、他のコンピュータでは動作しないことです。ここにコードを含め、単語リストへのリンクを提供します。単語リストをダウンロードしてコンパイルしてチェックするように頼むのは大変だと思いますが、お知らせいただければ大変助かります。2.6.38-13-generic-pae で Ubuntu 11.04 を実行しています
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
typedef struct x
{
int hashvalue;
char dictword[100];
char ascending[100];
struct x *next;
} node;
char *sortWord(char *);
//double fact(int);
void main()
{
FILE *fp1, *fp2;
char ch1;
while(ch1!='q')
{
char *dictsort;
dictsort=(char *)malloc(100*sizeof(char));
fp1=fopen("wordlist.txt", "r");
char ch;
int i=0;
char *sortedword;
int hashindex;
long int n;
printf("Please enter size of hashtable or press Ctrl+C to break:\n");
scanf("%ld", &n);
node *hashtable[n];
node *temp;
char test1[50];
char *test;
printf("Please enter the word to find anagrams for:\n");
scanf("%s", test1);
test=sortWord(test1);
int testhash=hashfunction(test);
printf("Hash value of word is %d\n", testhash);
for(i=0;i<1000000;i++)
{
hashtable[i]=NULL;
}
temp=NULL;
while(!feof(fp1))
{ //printf("Seg fault here...\n");
//ch=getc(fp1);
fgets(dictsort, (100*sizeof(char)),fp1);
//puts(dictsort);
sortedword=(char *)malloc(sizeof(dictsort));
sortedword = sortWord(dictsort);
hashindex=hashfunction(sortedword);
if(hashtable[hashindex]==NULL){
hashtable[hashindex] = (node *)malloc(sizeof(node));
strcpy(hashtable[hashindex]->dictword,dictsort);
strcpy(hashtable[hashindex]->ascending,sortedword);
hashtable[hashindex]->hashvalue=hashindex;
hashtable[hashindex]->next=NULL;
}else{
temp = (node *)malloc(sizeof(node));
strcpy(temp->dictword,dictsort);
strcpy(temp->ascending,sortedword);
temp->hashvalue=hashindex;
temp->next=hashtable[hashindex];
hashtable[hashindex]=temp;
// free(temp);
}
//printf("%s", hashtable[hashindex]->dictword);
free(sortedword);
}
//for(i=0;i<100000;i++)
//{
node *print;
print=(node *)malloc(sizeof(node));
print=hashtable[testhash];
int chk;
while(print!=NULL)
{
chk=strcmp(print->ascending,test);
if(chk==0)
{
printf("%s\n", print->dictword);
print=print->next;
}
else
print=print->next;
}
free(print);
}
}
int hashfunction(char *sw){
int a=0,i=0;
int k,b,c;
int div=1000000;
int blah;
int hv;
for(i=0;sw[i]!='\0';i++){
a=sw[i];
//b=sw[i+1];
//c=sw[i+2];
if(a!=10&&b!=10)
{
k=a*fact(i);
b=k;
hv+=b;
}
}
hv=hv%div;
return hv;
}
char *sortWord(char *s)
{
int c, d = 0, length;
char *pointer, *result, ch;
FILE *fp;
length = strlen(s);
result = (char*)malloc(length+1);
pointer = s;
for ( ch = 'a' ; ch <= 'z' ; ch++ )
{
for ( c = 0 ; c < length ; c++ )
{
if ( *pointer == ch )
{
*(result+d) = *pointer;
d++;
}
pointer++;
}
pointer = s;
}
*(result+d) = '\0';
char *z;
z=(char *)malloc(length+1);
strcpy(z, result);
//fp=fopen("sortedlist.txt", "a");
//fprintf(fp, "%s\n", s);
//fclose(fp);
free(result);
//puts(s);
//return result;
return z;
//free(result);
}
int fact(int num)
{
int i;
int val=1;
for(i=num+1;i>=1;i--)
{
val=val*i;
}
return val%1000000;
}