В
new_node->next = NULL;
hash(new_node->word);
// Inserts word into linked list
if(hashtable[i] == 0)
{
hashtable[i] = new_node;
}
else if(hashtable[i] == new_node)
{
new_node->next = hashtable[i];
hashtable[i] = new_node;
}
вы не используете результат hash () и используете i вместо результата хешированияв качестве индекса в хеш-таблица , если N больше 26, вы читаете / записываете из хеш-таблица , в другом случае вы не помещаете слово в нужную записьпотому что первый в индексе 0, следующий в индексе 1 и т. д. независимо от их первой буквы
Примечание else if(hashtable[i] == new_node) никогда не бывает истинным и фактически никогда не достигает, потому что if(hashtable[i] == 0) всегда является истинным, поскольку вы ограничиваете количество слов дочитать
Должно быть что-то вроде этого с минимальными изменениями
int h = hash(new_node->word);
// Inserts word into linked list
if(hashtable[h] == 0)
{
hashtable[h] = new_node;
new_node->next = NULL;
}
else
{
new_node->next = hashtable[h];
hashtable[h] = new_node;
}
, но на самом деле его можно упростить до:
int h = hash(new_node->word);
new_node->next = hashtable[h];
hashtable[h] = new_node;
Примечание. Я полагаю, вы не читали несколькораз одно и то же слово (это словарь)
Делать
while (fscanf(file, "%s", word) != EOF)
опасно, потому что нет защиты, если прочитанное слово длиннее, чемДЛИНА
предположим, ДЛИНА - это 32 дел (слово может хранить на 32 символа больше конечного значения)l символ):
while (fscanf(file, "%32s", word) == 1)
Нет смысла использовать цикл:
for (int i = 0; i < N; i++ )
{
...
}
удалить его (но, конечно, не его тело), так:
while (fscanf(file, "%32s", word) == 1)
{
// Allocate memory for node for each new word
node *new_node = malloc(sizeof(node));
if (!new_node)
{
unload();
return false;
}
// Copies word into node
strcpy(new_node->word, word);
int h = hash(new_node->word);
new_node->next = hashtable[h];
hashtable[h] = new_node;
}
tte part
// Initialize hash table
for (int i = 0; i < N; i++)
{
hashtable[i] = NULL;
}
бесполезен, потому что hashtable будучи глобальным инициализируется с 0
Если выЧтобы перезагрузить словарь, вам необходимо освободить связанный список, прежде чем сбросить в NULL
утечки памяти
malloc in хеш бесполезен и создает только утечки памяти, удалите его:
// Hashes word to a number between 0 and 25, inclusive, based on its first letter
unsigned int hash(const char *word)
{
return tolower(word[0]) - 'a';
}
Предупреждение, если первая буква не z или AZ, индекс возврата не является допустимым индексом для hashtable
Для удобства чтения замените #define N 26 на #define N ('z' - 'a' + 1)
Предложение, добавляющее отсутствующие определения:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#define bool int
#define true 1
#define false 0
// Represents number of buckets in a hash table
#define N ('z' - 'a' + 1)
// Represent max word length
#define LENGTH 32
// Represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node * next;
}
node;
// Represents a hash table
node * hashtable[N];
// Hashes word to a number between 0 and 25, inclusive, based on its first letter
unsigned int hash(const char *word)
{
return tolower(word[0]) - 'a';
}
// probable goal : empty hashtable
void unload()
{
for (size_t i = 0; i != N; ++i) {
while (hashtable[i] != NULL) {
node * next = hashtable[i]->next;
free(hashtable[i]);
hashtable[i] = next;
}
}
}
// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
// Open dictionary
FILE * file = fopen(dictionary, "r");
if (file == NULL)
return false;
// Buffer for a word
char word[LENGTH + 1];
// Insert words into hash table
while (fscanf(file, "%32s", word) == 1)
{
if (isalpha(word[0])) {
// Allocate memory for node for each new word
node * new_node = malloc(sizeof(node));
if (!new_node)
{
unload();
return false;
}
// Copies word into node
strcpy(new_node->word, word);
int h = hash(new_node->word);
new_node->next = hashtable[h];
hashtable[h] = new_node;
}
}
// Close dictionary
fclose(file);
// Indicate success
return true;
}
int main(int argc, char ** argv)
{
if (argc != 2)
printf("Usage : %s <dictionary>\n", *argv);
else if (!load(argv[1]))
fprintf(stderr, "Error when loading '%s'\n", argv[1]);
else {
puts("dictionary content");
for (size_t i = 0; i != N; ++i) {
node * n = hashtable[i];
if (n != NULL) {
printf("%c :", i + 'a');
do {
printf(" %s", n->word);
n = n->next;
} while (n != NULL);
putchar('\n');
}
}
unload();
}
}
Компиляция и выполнение:
pi@raspberrypi:/tmp $ gcc -pedantic -Wextra -Wall d.c
pi@raspberrypi:/tmp $ cat d
alternate
bellow and
Below
dictionary
Hash main zombie
test
Zorro
pi@raspberrypi:/tmp $ ./a.out
Usage : ./a.out <dictionary>
pi@raspberrypi:/tmp $ ./a.out d
dictionary content
a : and alternate
b : Below bellow
d : dictionary
h : Hash
m : main
t : test
z : Zorro zombie
Исполнение под valgrind :
pi@raspberrypi:/tmp $ valgrind ./a.out d
==2370== Memcheck, a memory error detector
==2370== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2370== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==2370== Command: ./a.out d
==2370==
dictionary content
a : and alternate
b : Below bellow
d : dictionary
h : Hash
m : main
t : test
z : Zorro zombie
==2370==
==2370== HEAP SUMMARY:
==2370== in use at exit: 0 bytes in 0 blocks
==2370== total heap usage: 13 allocs, 13 frees, 5,872 bytes allocated
==2370==
==2370== All heap blocks were freed -- no leaks are possible
==2370==
==2370== For counts of detected and suppressed errors, rerun with: -v
==2370== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 3)