0

this is my dictionary.c implementation. I think the problem is speller since I've been printing my hash values from hash. I also have not yet implemented unload since I think I'm having some conceptual difficulties with pointers and want to resolve this issue first.

// Implements a dictionary's functionality

#include <stdbool.h>

#include "dictionary.h"

// 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 = 2500;

// Hash table
node *table[N];

int s = 0; //size of dictionary

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // TODO
    int i = hash(word);
    node *cursor = table[i];
    while(cursor->next != NULL)
    {
        if (strcasecmp(cursor->word, word) == 0)
        {
            return true;
        }
        cursor = cursor->next;
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{

    //hash function retrieved from http://www.cse.yorku.ca/~oz/hash.html
    unsigned int hash = 5381;
    int c;

    while ((c = *word++))
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    //printf("%i\n",hash%N);
    return (hash % N);
    //return 0;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // TODO
    /*for ( int x = 0; x < N; x++){
        table[x]->next = NULL;
    }*/

    FILE *dict = fopen(dictionary, "r"); //open dictionary file to dict ptr
    if (!dict) //check if dict file opened
    {
        return false;
    }

    char tmp[LENGTH + 1];

    while (fgets(tmp, LENGTH, dict))
    {
        int hsh = hash(tmp); //hash the word
        node *n = malloc(sizeof(node)); //allocate node for word
        if (n == NULL)
        {
            return false;
        }
        strcpy(n->word, tmp); //put word in new node
        //n->next = NULL;

        n->next = table[hsh];
        //table[hsh]->next = n;
        s++;

    }
    return true;
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // TODO
    return false;
}

Output is:

MISSPELLED WORDS

Segmentation fault

0

Nope, the problem is not with speller.c Think about it, the speller.c code was written by CS50 staff and has been in use for years by thousands of students. While it isn't impossible that there are still bugs, it's highly unlikely. Most bugs are found before the code is released and the few that remain turn up really soon. ;-)

The problem lies in the check() code. Look at the following:

while(cursor->next != NULL)

What if cursor is null to start with? If cursor is null, then cursor->next doesn't exist. That will cause a seg fault. Maybe the code shouldn't be checking cursor->next, and should be checking cursor instead? Step through the code and figure out why.

Debugging note: It's critical to be able to identify what causes a seg fault. Seg faults are always triggered by a single line of code. Finding the root cause starts with identifying the line that triggers it. I suggest reading this:

Do YOU know how to find a seg fault?? Advice to new programmers

There are more issues, starting with a logic flaw in check(), but I'll let you find it first. ;-)

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

4
  • Thanks! How can the cursor be null if I initialize it to point at the hash table node? Even if the table node is empty wouldn't cursor still have a non-null value? Dec 19 '20 at 0:56
  • 1
    No. The pointer in cursor is set to whatever is in table[i]. If no word has the hash value for table[i], then table[i] would be null, assuming it was correctly initialized. BTW, where are all the values of table[ ] initialized in your code? If not initialized (preferably to null), they will contain whatever garbage data is left in the physical memory. That would likely be an invalid address, also resulting in a seg fault. Or worse, it could contain random data that happens to be a valid address and the program would continue to run, corrupting your data. ALWAYS initialize pointers!!!!!
    – Cliff B
    Dec 19 '20 at 1:00
  • its the commented out code in load. I deleted the "->next" and uncommented it Dec 19 '20 at 1:18
  • I'm totally lost on what the other issues are, can I have a hint? Dec 19 '20 at 19:44

You must log in to answer this question.

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