C:从带有链表和哈希表的txt文件实现的字典无法找到文件中存在的单词

Question

请原谅本文中的任何错误，因为这是我在这里的第一篇文章，但请指出。

我对 C 还很陌生，但我正在尝试通过哈希表从 txt 文件实现一个字典，该文件每行都有一个单词，但每当我尝试搜索一个单词时，它都找不到它存在于文件中。

你能帮我找出我做错了什么吗？

以下两个文件:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define tab_size 29                  /* table size */
#define word_len 24                  /* max length of word */

.h 文件:

/* structure to be used for each word */

typedef struct list {
      char *word;                  
      struct list *next;         
} WORD;

.c 文件:

/* create table */ 

WORD **create_tab(int size) {
       int i = 0;
       WORD **hash_tab;
       hash_tab = malloc(sizeof(*hash_tab) * size);    /*allocate memory */
       for (; i<size; i++)              /* initialize elements */
              hash_tab[i]=NULL;
return hash_tab;
}


/* search for word in table; returns 1 if found, 0 otherwise */

int search(WORD **tb, char *w) {
      WORD *htmp/*, *hprv*/;
      unsigned long hash = (hash_f(w) % tab_size);     /* hash_f is Dan Bernstein's hash function; modulo by tab_size to make sure it fits */  
      for (htmp = tb[hash]; (htmp != NULL) && (strcmp(htmp->word, w) != 0); / htmp = htmp->next)      /* follow chained array of respective cell until word is found or until the end */
      {
        ;
      }
      if (htmp == NULL) return 0;
return 1;
}


/* insert new WORD with word w at the beginning of the chained array of the respective cell */

void insert(WORD **ht, char *w) {
   WORD *htmp;
   unsigned long hash = (hash_f(w) % tab_size);     /* hash_f is Dan Bernstein's hash function; modulo by tab_size to make sure it fits */
   htmp = malloc( sizeof(*htmp) );      /* allocate memory for new WORD */
   htmp->word = calloc(word_len+1,sizeof(char));    /* allocate memory for new word with  max word length plus one character to make sure there's no buffer overflow in the next line*/
   strncpy(htmp->word, w, word_len);             /* copy w to word */  
   htmp->next = ht[hash];                   /* new WORD now points to content of the respective table cell */
   ht[hash] = htmp;                /* table cell now points to new WORD */
}

/* receive empty table and create the whole dictionary in memory word by word */

WORD **make(WORD **dic;) {  
      char w[word_len];         
      FILE *dictionary;    
      dictionary = fopen("dictionary.txt","r");                   
      while ((fgets( w, word_len, dictionary )) != NULL)    
          insert(dic, w);                    
      fclose(dictionary);  
return dic;
}



int main() {
     WORD **dic;
     char w[word_len];
     dic = create_tab(tab_size);     /* create the table */
     dic = make(dic);                   /* insert all entrys of dictionary in table */
     printf("Insert a word in lowercase: \n"); 
     if ((scanf("%s",w)) == 0) return 0;    /* if I didn't somehow verify the scanf it would return an error */
     else if (search(dic, w) == 1) printf("The word %s exists in the dictionary \n",w);
          else printf("The word %s does not exist in the dictionary",w);
return 0;
}

我尝试了几种方法，其中一些基于以下链接，但这种情况总是会发生。此版本基于上一版本。

Quick Way to Implement Dictionary in C http://www.sparknotes.com/cs/searching/hashtables/section3.rhtml http://www.seg.rmit.edu.au/code/zwh-ipl/hashtable.c

Answer 1

问题1

这是不对的。

   hash_tab = malloc(sizeof(WORD) * size);    /*allocate memory */

应该是

   hash_tab = malloc(sizeof(WORD*) * size);    /*allocate memory */

为了避免此类错误，您应该养成使用的习惯

   hash_tab = malloc(sizeof(*hash_tab) * size);    /*allocate memory */

问题2

  for (; i<tab_size; i++)              /* initialize elements */
          hash_tab[i]=NULL;

应该是

  for (; i<size; i++)              /* initialize elements */
          hash_tab[i]=NULL;

这是一个潜在的问题。如果 size 和 tab_size 恰好相等，那么在您的情况下这可能不是真正的问题。但出于风格问题，您应该使用第二个代码块。