CS50 pset5哈希表检查问题

-1

我的任务是实现一个程序，该程序将字典转换为数据结构并对其进行拼写检查。我设法用一个简单的链表完成它，但是当我尝试使用散列表时，我得到了错误的结果。我找到了很多拼错的单词，我不知道什么是错的。CS50 pset5哈希表检查问题

typedef struct node 
{ 
char word[LENGTH+1]; 
struct node *next; 
} 
node; 
node *hashtable[150000] = {NULL};

的检查功能：

int i = hash(word); 
node *cursor = hashtable[i]; 

while(cursor!=NULL) 
{ 
    if(strcasecmp(cursor->word, word) == 0) 
    { 
     return true; 
    } 
    else 
    { 
     cursor = cursor->next; 
    } 
} 
return false;

我已经尝试设置W->旁边NULL，这使绝对没有什么区别。所以我摆脱了它。

装载到哈希表

// open dictionary file and ensure it worked 
FILE *d = fopen(dictionary, "r"); 
if(d==NULL) 
{ 
    printf("File wont open"); 
    return false; 
}; 


// initiate loop for putting all words into array, untile the end of dictionary. 
while(fscanf(d, "%s", word) != EOF) 
{ 
    //create a new node and ensure it worked 
    node *w = malloc(sizeof(node)); 
    if(w ==NULL) 
    { 
     unload(); 
     return false; 
    } 

    //coppy word from dictionary to node. w->word is a pointer to char in a node created above. 
    strcpy(w->word, word); 

    //get hash code and stor in i. 
    long i = hash(word); 


    //place the node in hashtable in correct place. 
    if(hashtable[i]->next==NULL) 
    { 
     hashtable[i]->next = w; 
    } 
    else 
    { 
     w->next = hashtable[i]->next; 
     hashtable[i]->next = w; 
    } 
} 
fclose(d); 
return true;

而一个散列函数：

long hash = 0; 

    for (int counter = 0; str[counter]!='\0'; counter++) 
    { 
     hash = (str[counter] + (hash << 6) + (hash << 16) - hash)%150000;//150000=size of hashtable 
    } 
    return hash;

来源

2017-02-21 ishamael

节点是什么样的，你如何初始化它的成员？例如'malloc'之后，不能保证'w-> next'是'NULL'。并且'w-> word'是一个指针还是一个'char'数组？您可以编辑问题以添加更多信息。 –

原来，这strcasecmp在检查功能，是区分大小写的。根据this site它不应该。

在手动将所有字符更改为要检查的单词中的小写字母之后，所有内容均按原样运行。

来源

2017-02-21 19:40:54 ishamael

CS50 pset5哈希表检查问题

回答

相关问题