Хранение слов в хэш-таблице

Question

У меня есть файл, содержащий английские слова в txt-файле, каждое слово в новой строке. Я новичок в C. Я использую функции 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 свободных.

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 (Main) - 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(), в течение-цикла, если условие if(hashtable[i] != NULL) предполагает, что каждый элемент массива инициализируется NULL.

Добавить в начале функцию load() или перед ее вызовом, для цикла, чтобы инициализировать каждый указатель.

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

Задача 3 (Потенциальная ошибка Источник), - как предполагают, по рецензента, использование head, объявленный как глобальная переменная node *head = NULL; может быть потенциальным источником ошибки.

В функции load(), переменная head используется в качестве временного хранения , но может хранить значение во время запуска программного обеспечения. Если операция чтения выполняется без хорошо известной операции записи, результат может быть непредвиденной ошибкой, даже если компиляция не обнаруживает ошибку или предупреждение .

Лучший способ - уменьшить число глобальных переменных до .

Enhancement (Обратный связанный список) - потому что удались связной список добавлять новые элементы в передней, здесь есть решение, чтобы добавить новые элементы, в конце концов.

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++;