0

Seg-faults seem to be the bane of my existence. I've tried running valgrind and using printf functions to find the line(s) of code that are causing the seg-fault in my implementation of speller, but to no avail. The flaw probably lies in my implementation and/or use of linked lists and the hash table, but I don't know why it is happening. Also, side question: In the hash table, are all nodes of the array table[] just pointers to the first elements of linked lists, or does each node in table[] also have a word associated with it?


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

#include "dictionary.h"

int wordcount = 0;

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// Number of buckets in hash table
const unsigned int N = 17576;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    int index = hash(word);
    node *tmp = malloc(sizeof(node));
    tmp = table[index];
    while (tmp != NULL)
    {
        if (strcasecmp(word, tmp->word) == 0)
        {
            return true;
        }
        tmp = tmp->next;
    }
    printf("z");
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    int letter0 = (int)toupper(word[0]) - 65;
    int letter1 = (int)toupper(word[1]) - 65;
    int letter2 = (int)toupper(word[2]) - 65;
    int x = (letter0 * 26 * 26) + (letter1 * 26) + letter2;
    return x;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    FILE* file = fopen(dictionary, "r");
    if (file == NULL)
    {
    return false;
    }
    else
    {
        while (1)
        {
            char* word = malloc(LENGTH + 1);
            if (fscanf(file, "%s", word) == EOF)
            {
                break;
            }
            node *n = malloc(sizeof(node));
            if (n == NULL)
            {
                return false;
            }
            strcpy(n->word, word);
            n->next = NULL;
            int index = hash(word);
            if (table[index] == NULL)
            {
                table[index] = n;
                wordcount++;
            }
            else
            {
                n->next = table[index];
                table[index] = n;
                wordcount++;
            }
        }
    }
    printf("z");
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    return wordcount;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int i = 0; i < N; i++)
    {
        node *tmp1 = table[i];
        node *tmp2 = table[i];
        while (tmp2 != NULL)
        {
            tmp2 = tmp2->next;
            free(tmp1);
            tmp1 = tmp2;
        }
    }
    return true;
} ```

1

Your code is very nice and neat congratulations. Your problem resides in your hash function. When passed a string of less than 3 caracters returns a negative value, so when you try to use it as index in your load() function it yells at you :) You got it right. The array table[] are just pointers to nod structs.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .