CS50 Speller questions about how to move forward

Question

I have a few questions about speller, both about how the program operates and how I should begin the start debugging and testing a program of this complexity. My first question involves why you only need to allocate memory for certain nodes. It seems that the transfer node (you will see in my code below) requires allocating memory because you copy data into and later out of this node, yet other nodes (which I have concluded from looking at other people's code) does for some reason not require allocating memory. Is that because they are just pointers or something? I'm not sure. My second question revolves around what you need pointers for when inserting. It seems the walkthrough on CS50 recommends inserting at the beginning of a node, which would require more various pointers, because you don't want to "lose" the beginning of the node. My code inserts at the end of node, which does not require so many pointers. Now that my two conceptual questions are out of the way, I wonder how I'm supposed to debug a program this complex. For recover you could start with something like listing how many files are in the raw card to make sure you are reading correctly, but I'm not sure how I would start with something more elementary for this. Anyway, thanks for reading and below is my code.

// Implements a dictionary's functionality

#include <stdbool.h>

#include "dictionary.h"

#include <stdio.h>
#include <string.h>
#include <strings.h>
#include <stdlib.h>
#include <stdint.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 = 26;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // TODO
    int i;

    i = hash(word);

    node *current = table[i];

    while (current != NULL)
    {
        if (strcasecmp(word, current -> word) == 0)
        {
            return true;
        }
        current = current -> next;
    }

    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    // TODO
    int a = (word[0] -65);
    return a;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // TODO
    FILE *load = fopen(dictionary, "r");

    if (load == NULL)
    {
        printf("There has been an error loading dictionary \n");
        return false;
    }

    char word[LENGTH + 1];

    while (fscanf(load,"%s",word) != EOF)
    {
        node *transfer = malloc(sizeof(node));
        strcpy (transfer -> word, word);
        transfer -> next = NULL;

        int wordhash = hash(word);

        while (transfer != NULL)
        {
            table[wordhash] = transfer;
            table[wordhash] -> next = NULL;
            table[wordhash] = table[wordhash] -> next;
        }
    }
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    // TODO
    int total = 0;

    for (int i = 0; i < N; i++)
    {
        while (table[i] != NULL)
        {
            total ++;
        }
    }
    return total;
}

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

Answer 1

On your second question you can do whatever you want insert at the end middle or the front of the list it's your choice. The reason it is recommended to insert the word in the front of the list is basically for efficiency yes you might think it involves more pointer but once you grasp how it's done it's actually very simple. Remember a linked list there is no random access or index in arrays. What that basically means is that to access a value in a list you need to go through the head of the list to your value, so what does all this mean it means you shouldn't really care where your words end up in the list be it at the front middle or end it doesn't really matter because you don't have random access. And also the reason we use lists is for us to not think ahead of how much memory we need usually in arrays where you have to specify its length at declaration. Why is it more efficient to add to front of the list, well because what if your linked list has 1000 values to add to the end of your list you're going to have to go through those 1000 values then add your value to the list, which is pretty dumb because if you care where your values go then most probably don't use a linked list as you don't have random access just use array it's much simpler. How do we add to the front of the list? I don't know why you're using new pointers but all you have to do is have the pointer of your new value to point at the first value of the list, after that you can just point the head of the list to your new value simple as that.

head-->value->NULL         it may look like this you first set a pointer to the firstvalue
   l       ^1st            of the list then set the pointer of the head of the list to
2ndl       +---new_value       your new value
   +--------------^

I'm sorry but I don't really understand your first question...

For your other questions how do you start debugging this kind of program where do you start? A big tip is to take a step back this is a hard problem for new programmers. If you're really new search up about hash tables data structures and pointers for you to understand those concepts better. Next would be to not overthink things the reason they gave us this problem is because it's solvable in many different ways. Also I noticed you have a pretty sketchy hash function I think you should get a better one. Also your buckets are only 26 look at the dictionary it's more than 100,000 lines, so you're expecting 100,000+ words to be fit in 26 buckets you're linked lists would be as far as 5,000 values per bucket, which in just numbers itself would be very inefficient. I feel like you are having a hard time with pointers so just research about things that are confusing to you first before you start and tackle this problem. Debug this via valgrind then reread your code for logic errors.

Answer 2

other nodes [do not] require allocating memory. Is that because they are just pointers or something?

Yes.

My code inserts at the end of node, which does not require so many pointers.

It doesn't seem to. To insert at the end of the list, program would need to read the linked list to the terminal node, then "point" the terminal node (ie next) to the new node. This program doesn't, in fact, build a linked list at all because the head of the list always points to NULL.

table[wordhash] -> next = NULL;
table[wordhash] = table[wordhash] -> next

As for debugging: start small (eg dictionaries/small). You can create your own text files to use as dictionary and/or text file. Build on them until "you get the hang of it". It's a good idea, as you say, for a program this complex.