Skip to main content
deleted 6748 characters in body
Source Link

Code is below, but can also be found here: https://repl.it/repls/BubblyUnripeTreesedited code out to not spoil it for everybody

// Implements a dictionary's functionality

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

#include "dictionary.h"

// Represents number of buckets in a hash table
#define N 26

// Represents a node in a hash table (+1 is for null char in case word with max length)
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// GLOBAL VARS
// 1. A counter to count amount of words in dictionary
int dictionarycounter = 0;
// 2. Represents a hash table - array called hashtable of N pointers to datatype node - a struct defined in line 15 - 1 bucket per letter
node *hashtable[N];

// Hashes word to a number between 0 and 25, inclusive, based on its first letter - 0 for word that starts with a/A, 1 for word that starts with b/B, ..., 25 for word that starts with z/Z.
unsigned int hash(const char *word)
{
    // returns an unsigned int by performing calculation with ascii values
    return tolower(word[0]) - 'a';
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Initialize hash table ("code that initializes all of the pointers in hashtable to NULL") - hashtable is an array of N pointers to nodes - here we dereference each pointer to NULL
    for (int i = 0; i < N; i++)
    {
        hashtable[i] = NULL;
    }

    // Open dictionary ("which is the file name of a dictionary to load") | FILE *fp = fopen("file.txt" or filepointer without quotation marks, mode)
    FILE *file = fopen(dictionary, "r");
    // check for file not being a nullpointer
    if (file == NULL)
    {
        unload();
        return false;
    }

    // Buffer for a word (array of chars) of size length + 1 (+ 1 to make room for the null char in case a word is max length)
    char word[LENGTH + 1];

    // Insert words into hash table
    while (fscanf(file, "%s", word) != EOF)
    {

        // hash the word
        int index = hash(word);

        // create a new node
        node *new_node = malloc(sizeof(node));

        // check for the new node being a null pointer
        if (new_node == NULL)
        {
            printf("Error, out of memory.\n");
            unload();
            return false;
        }

        // point new_node to NULL
        new_node->next = NULL;

        // assign the current word in the loop to the new node's word value
        strcpy(new_node->word, word);

        //check for collision (check if there already is a linked list with another node at the given index) - if hashtable[index] = NULL means there are no nodes yet linked to that index
        if (hashtable[index] == NULL)
        {
            // insert new node at the start of the bucket
            hashtable[index] = new_node;
        }
        else
        {
            // simplifying the code below as hashtable[index] is already a node
            new_node->next = hashtable[index];
            hashtable[index] = new_node;

            /** create pointer to first node in a given hashtable (i.e. define head node)
            node *head_node = hashtable[index];
            // make new_node point to the first node
            new_node->next = head_node;
            // point head to new_node (make new_node the new head node)
            head_node = new_node;*/
        }

        // count words in dictionary
        dictionarycounter ++;
    }

    // Close dictionary
    fclose(file);

    // Indicate success
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    // we defined this as a global variable and also counted words in the load section
    return dictionarycounter;
    return 0;
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // convert each word to full lowercase
    int x = strlen(word);
    char same[x + 1];


    for (int i = 0; i < x; i++)
    {
        same[i] = tolower(word[i]);
    }
    same[x] = '\0'; //adding null char at the end

    // getting the hash of the word being checked
    int index = hash(same);

    // create a pointer to the head node (point to the first word in a hashtable given a certain hash depending on word hashed)
    node *head = hashtable[index];

    // looking for the word in the hashtable
    while (head != NULL) // while not reaching end of list (last node points to NULL)
    {
        // if word is found return true
        if(strcmp(head->word, same) == 0)
        {
            return true;
        }
        // if not found, move to next node
        head = head->next;
    }

    // when end of list is reached and thus the word isn't found
    return false;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // loop through buckets
    for (int i = 0; i < N; i++)
    {

        while (hashtable[i] != NULL)
        {
            node *tmp = hashtable[i];
            hashtable[i] = hashtable[i]->next;
            free(tmp);
        }

        /** code above does the same as code below
        //point to first node in the linked list at current bucket
        node *bucket = hashtable[i];
        // check for not receiving a NULL pointer
        if (bucket == NULL)
        {
            return false;
        }
        //as long as the next field of the node isn't NULL, we haven't reached the last node and thus we need to keep freeing every node we loop
        while (bucket != NULL)
        {
            // create temporary node to keep track of the first node in the list ! (so we don't orphan the list)
            node *tmp = bucket;
            bucket = bucket->next;

            // free current node
            free(tmp);
        }*/
    }
    return true;
}

Code is below, but can also be found here: https://repl.it/repls/BubblyUnripeTrees

// Implements a dictionary's functionality

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

#include "dictionary.h"

// Represents number of buckets in a hash table
#define N 26

// Represents a node in a hash table (+1 is for null char in case word with max length)
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// GLOBAL VARS
// 1. A counter to count amount of words in dictionary
int dictionarycounter = 0;
// 2. Represents a hash table - array called hashtable of N pointers to datatype node - a struct defined in line 15 - 1 bucket per letter
node *hashtable[N];

// Hashes word to a number between 0 and 25, inclusive, based on its first letter - 0 for word that starts with a/A, 1 for word that starts with b/B, ..., 25 for word that starts with z/Z.
unsigned int hash(const char *word)
{
    // returns an unsigned int by performing calculation with ascii values
    return tolower(word[0]) - 'a';
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Initialize hash table ("code that initializes all of the pointers in hashtable to NULL") - hashtable is an array of N pointers to nodes - here we dereference each pointer to NULL
    for (int i = 0; i < N; i++)
    {
        hashtable[i] = NULL;
    }

    // Open dictionary ("which is the file name of a dictionary to load") | FILE *fp = fopen("file.txt" or filepointer without quotation marks, mode)
    FILE *file = fopen(dictionary, "r");
    // check for file not being a nullpointer
    if (file == NULL)
    {
        unload();
        return false;
    }

    // Buffer for a word (array of chars) of size length + 1 (+ 1 to make room for the null char in case a word is max length)
    char word[LENGTH + 1];

    // Insert words into hash table
    while (fscanf(file, "%s", word) != EOF)
    {

        // hash the word
        int index = hash(word);

        // create a new node
        node *new_node = malloc(sizeof(node));

        // check for the new node being a null pointer
        if (new_node == NULL)
        {
            printf("Error, out of memory.\n");
            unload();
            return false;
        }

        // point new_node to NULL
        new_node->next = NULL;

        // assign the current word in the loop to the new node's word value
        strcpy(new_node->word, word);

        //check for collision (check if there already is a linked list with another node at the given index) - if hashtable[index] = NULL means there are no nodes yet linked to that index
        if (hashtable[index] == NULL)
        {
            // insert new node at the start of the bucket
            hashtable[index] = new_node;
        }
        else
        {
            // simplifying the code below as hashtable[index] is already a node
            new_node->next = hashtable[index];
            hashtable[index] = new_node;

            /** create pointer to first node in a given hashtable (i.e. define head node)
            node *head_node = hashtable[index];
            // make new_node point to the first node
            new_node->next = head_node;
            // point head to new_node (make new_node the new head node)
            head_node = new_node;*/
        }

        // count words in dictionary
        dictionarycounter ++;
    }

    // Close dictionary
    fclose(file);

    // Indicate success
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    // we defined this as a global variable and also counted words in the load section
    return dictionarycounter;
    return 0;
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // convert each word to full lowercase
    int x = strlen(word);
    char same[x + 1];


    for (int i = 0; i < x; i++)
    {
        same[i] = tolower(word[i]);
    }
    same[x] = '\0'; //adding null char at the end

    // getting the hash of the word being checked
    int index = hash(same);

    // create a pointer to the head node (point to the first word in a hashtable given a certain hash depending on word hashed)
    node *head = hashtable[index];

    // looking for the word in the hashtable
    while (head != NULL) // while not reaching end of list (last node points to NULL)
    {
        // if word is found return true
        if(strcmp(head->word, same) == 0)
        {
            return true;
        }
        // if not found, move to next node
        head = head->next;
    }

    // when end of list is reached and thus the word isn't found
    return false;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // loop through buckets
    for (int i = 0; i < N; i++)
    {

        while (hashtable[i] != NULL)
        {
            node *tmp = hashtable[i];
            hashtable[i] = hashtable[i]->next;
            free(tmp);
        }

        /** code above does the same as code below
        //point to first node in the linked list at current bucket
        node *bucket = hashtable[i];
        // check for not receiving a NULL pointer
        if (bucket == NULL)
        {
            return false;
        }
        //as long as the next field of the node isn't NULL, we haven't reached the last node and thus we need to keep freeing every node we loop
        while (bucket != NULL)
        {
            // create temporary node to keep track of the first node in the list ! (so we don't orphan the list)
            node *tmp = bucket;
            bucket = bucket->next;

            // free current node
            free(tmp);
        }*/
    }
    return true;
}

edited code out to not spoil it for everybody

Source Link

PSet 4 - getting more misspellt words then staff's solution & a lot of memory leaks

I would very much appreciate it of somebody could tell me what I did wrong or could help me get on the right track to the correct solution. My program overall works fine, except the end result isn't as expected.

I believe the issue lies in the check section and has something to do with the conversion to lowercase letters,thought I'm not entirely sure where.

As for the memory leaks I really don't understand what went wrong here.

Thank you for helping out!

When I run: ./speller texts/lalaland.txt

enter image description here enter image description here

Code is below, but can also be found here: https://repl.it/repls/BubblyUnripeTrees

// Implements a dictionary's functionality

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

#include "dictionary.h"

// Represents number of buckets in a hash table
#define N 26

// Represents a node in a hash table (+1 is for null char in case word with max length)
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// GLOBAL VARS
// 1. A counter to count amount of words in dictionary
int dictionarycounter = 0;
// 2. Represents a hash table - array called hashtable of N pointers to datatype node - a struct defined in line 15 - 1 bucket per letter
node *hashtable[N];

// Hashes word to a number between 0 and 25, inclusive, based on its first letter - 0 for word that starts with a/A, 1 for word that starts with b/B, ..., 25 for word that starts with z/Z.
unsigned int hash(const char *word)
{
    // returns an unsigned int by performing calculation with ascii values
    return tolower(word[0]) - 'a';
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Initialize hash table ("code that initializes all of the pointers in hashtable to NULL") - hashtable is an array of N pointers to nodes - here we dereference each pointer to NULL
    for (int i = 0; i < N; i++)
    {
        hashtable[i] = NULL;
    }

    // Open dictionary ("which is the file name of a dictionary to load") | FILE *fp = fopen("file.txt" or filepointer without quotation marks, mode)
    FILE *file = fopen(dictionary, "r");
    // check for file not being a nullpointer
    if (file == NULL)
    {
        unload();
        return false;
    }

    // Buffer for a word (array of chars) of size length + 1 (+ 1 to make room for the null char in case a word is max length)
    char word[LENGTH + 1];

    // Insert words into hash table
    while (fscanf(file, "%s", word) != EOF)
    {

        // hash the word
        int index = hash(word);

        // create a new node
        node *new_node = malloc(sizeof(node));

        // check for the new node being a null pointer
        if (new_node == NULL)
        {
            printf("Error, out of memory.\n");
            unload();
            return false;
        }

        // point new_node to NULL
        new_node->next = NULL;

        // assign the current word in the loop to the new node's word value
        strcpy(new_node->word, word);

        //check for collision (check if there already is a linked list with another node at the given index) - if hashtable[index] = NULL means there are no nodes yet linked to that index
        if (hashtable[index] == NULL)
        {
            // insert new node at the start of the bucket
            hashtable[index] = new_node;
        }
        else
        {
            // simplifying the code below as hashtable[index] is already a node
            new_node->next = hashtable[index];
            hashtable[index] = new_node;

            /** create pointer to first node in a given hashtable (i.e. define head node)
            node *head_node = hashtable[index];
            // make new_node point to the first node
            new_node->next = head_node;
            // point head to new_node (make new_node the new head node)
            head_node = new_node;*/
        }

        // count words in dictionary
        dictionarycounter ++;
    }

    // Close dictionary
    fclose(file);

    // Indicate success
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    // we defined this as a global variable and also counted words in the load section
    return dictionarycounter;
    return 0;
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // convert each word to full lowercase
    int x = strlen(word);
    char same[x + 1];


    for (int i = 0; i < x; i++)
    {
        same[i] = tolower(word[i]);
    }
    same[x] = '\0'; //adding null char at the end

    // getting the hash of the word being checked
    int index = hash(same);

    // create a pointer to the head node (point to the first word in a hashtable given a certain hash depending on word hashed)
    node *head = hashtable[index];

    // looking for the word in the hashtable
    while (head != NULL) // while not reaching end of list (last node points to NULL)
    {
        // if word is found return true
        if(strcmp(head->word, same) == 0)
        {
            return true;
        }
        // if not found, move to next node
        head = head->next;
    }

    // when end of list is reached and thus the word isn't found
    return false;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // loop through buckets
    for (int i = 0; i < N; i++)
    {

        while (hashtable[i] != NULL)
        {
            node *tmp = hashtable[i];
            hashtable[i] = hashtable[i]->next;
            free(tmp);
        }

        /** code above does the same as code below
        //point to first node in the linked list at current bucket
        node *bucket = hashtable[i];
        // check for not receiving a NULL pointer
        if (bucket == NULL)
        {
            return false;
        }
        //as long as the next field of the node isn't NULL, we haven't reached the last node and thus we need to keep freeing every node we loop
        while (bucket != NULL)
        {
            // create temporary node to keep track of the first node in the list ! (so we don't orphan the list)
            node *tmp = bucket;
            bucket = bucket->next;

            // free current node
            free(tmp);
        }*/
    }
    return true;
}