將單詞存儲到哈希表中

Question

我有一個文件，其中包含一個txt文件中的英文單詞，每個單詞換行。我使用load和unload函數將所有單詞存儲到散列表（單獨的鏈接）中，並將它們從內存中卸載，但遇到了一些問題。

功能（main.c中的代碼是正確的）：

負載：

#include <stdbool.h> 
#include <string.h> 
#include <stdlib.h> 
#include <ctype.h> 
#include <stdio.h> 

#include "dictionary.h" 

#define SIZE 26 

typedef struct node 
{ 
    char word[LENGTH+1]; 
    struct node *next; 
}node; 

unsigned int hash_num = 0; 
node *hashtable[SIZE]; //26 letters in alphabet 

node *head = NULL; 

// hashfunction 
unsigned int hash(char const *key) 
{ 
    unsigned int hash= tolower(key[0]) - 'a'; 
    return hash % SIZE; 
} 

/** 
* Loads dictionary into memory. Returns true if successful else false. 
*/ 
bool load(const char* dictionary) 
{ 

    unsigned int hash_index=0; 

    FILE *fp = fopen(dictionary, "r"); 
    if(fp == NULL) 
    { 
     fprintf(stderr, "Couldn't open %s",dictionary); 
     return false; 
    } 

    //dictionary 


    while(!feof(fp)) 
    { 
     node *temp = malloc(sizeof(node)); 
     if (temp == NULL) 
     { 
      unload(); 
      fclose(fp); 
      return false; 
     } 


     if(fscanf(fp , "%s", temp->word) == 1) //storing word of dictionary in my new_node -> word 
     { 
      hash_index = hash(temp->word); 
      head= hashtable[hash_index]; //head always points to first element of linked list (containting word of dictionary) 


      temp->next = head; 
      head = temp;   


      hash_num++; 
     } 
     else //if fscanf couldn't store the word (return 0) 
     { 
      free(temp); //free last temp 
      break; 
     } 
    } 

    fclose(fp); 
    return true; 

} 

卸載：

bool unload(void) 
{ 

    for(int i=0; i<SIZE; i++) 
    { 
     if(hashtable[i] != NULL)  //if hashtable isn't NULL (has nodes) 
     { 
      node *cursor = hashtable[i];  //cursor points at head of individual linked list 
      while(cursor != NULL)  //free them 
      { 
       node *temp = cursor; 
       cursor = cursor->next; 
       free(temp); 
      } 
     } 
    } 

    return true; 
} 

誰能告訴我如果邏輯 是正確的？每當我運行valgrind時，它告訴我所有的節點都已分配，但只有3個free'd。

total heap usage: 143,094 allocs, 3 frees, 8,014,288 bytes allocated 
LEAK SUMMARY: 
==15903== definitely lost: 8,013,040 bytes in 143,090 blocks 
==15903== indirectly lost: 0 bytes in 0 blocks 
==15903==  possibly lost: 0 bytes in 0 blocks 

Answer 1

當檢查提供的源代碼（缺失「dictionary.h」），主要的問題是定位在load()功能。

問題1（主） - 所述hashtable[]添加新單詞/節點（計算hash_index = hash(temp->word);之後）時從不更新。

存儲更新後的鏈表（如管理反轉），就必須更新hashtable[hash_index]與新節點 指針（分配temp節點） 。

temp->next = head; 
head = temp; 

hashtable[hash_index] = head; // update the hashtable[] pointer 

hash_num++; 

沒有全局變量head替代的解決方案。

temp->next = hashtable[hash_index]; //head always points to first element... 
hashtable[hash_index] = temp; // update the hashtable[] pointer 

hash_num++; 

而不是

temp->next = head; 
head = temp; 

hash_num++; 

問題2（小） - 在hashtable[SIZE]永遠不會初始化。

在unload()功能，在for循環中，如果條件 if(hashtable[i] != NULL)假定陣列的每個產品 初始化爲NULL。

在開頭添加load()函數，或者在調用它之前添加一個for循環來初始化每個指針。

for(int i=0; i<SIZE; i++) 
{ 
    hashtable[i] = NULL; 
} 

問題3（潛在的錯誤來源） - 通過評審的建議，使用head，聲明爲一個全局變量node *head = NULL;可能是錯誤的潛在來源。

在load()函數，變量head被用作臨時存儲 但軟件運行過程中可以存儲的值。如果執行讀取操作 之前沒有衆所周知的寫入操作，則即使編譯未檢測到 錯誤或警告，結果 也可能是意外錯誤。

最好的辦法是減少全局變量的數量，儘可能多地達到 。

增強（反向鏈接列表） - 因爲管理鏈表在前面添加新項目，這裏是在結尾處添加新項目的解決方案。

node *first = hashtable[hash_index]; 
if (first == NULL) { 
    hashtable[hash_index] = temp; 
} 
else { 
    temp->next = NULL; // ending the list 
    while (first->next!=NULL) { 
     first = first->next; // loop until last node 
    } 
    first->next = temp; // linking to the last node 
} 

hash_num++; 

而不是

head= hashtable[hash_index]; //head always points to first element ... 

temp->next = head; 
head = temp;   

hash_num++;