0

As part of the edX course, CS50, I'm trying to load all the dictionary information into an array of char pointers. This would give random access and therefore a pretty fast load and unload time. The file compiles fine, but when I execute it, it stops at "MISSPELLED WORDS" and does not proceed.

I think it might be because I am implementing the "check" function wrong. Gdb tells me that all the words were loaded correctly, but it does not progress in searching for the first word.

The executable file "speller" uses two source files: dictionary.c and speller.c. The assignment is to only edit dictionary.c and dictionary.h in order to implement the executable file.

Thanks beforehand.

dictionary.c

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


#include "dictionary.h"

// storage and file pointer globalization
//open the dictionary file to read from
FILE* supply;

//allocate memory for the array of char pointers.
char** storage;

//initialization of variable for size function
int dictionarysize = 0;

//length of each word and indices
char supplyword[46];
int wordindex = 0;
int storageindex = 0;

//implement a binary search
bool search(int lower, int upper, const char* value)
{
    int middle = (upper + lower)/2;

    while (lower <= upper)
    {
        if (storage[middle] == value)
        {
            return true;
        }

        else if (storage[middle] < value)
        {
            lower = middle + 1;
            search(lower, upper, value);
        }

        else if (storage[middle] > value)
        {
            upper = middle - 1;
            search(lower, upper, value);
        }
     }
    return false;
}

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    return search(0, (LISTLENGTH - 1), word);
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    //supply is to read the dictionary file. word is to store individual words from file. index is the nth letter being stored
    supply = fopen(dictionary, "r");

    //allocate memory for the array of char pointers.
    storage = malloc(LISTLENGTH * sizeof(char*));
    for (int i = 0; i < LISTLENGTH; i++)
    {
        storage[i] = malloc((LENGTH + 1) * sizeof(char));
    }

    if (supply == NULL)
    {
        printf("Wasn't able to open dictionary file.\n");
        return false;
    }
    else if (storage == NULL)
    {
        printf("Wasn't able to open storage.\n");
        return false;   
    }

    for (int i = fgetc(supply); i != EOF; i = fgetc(supply))
    {
        // allow only alphabetical characters and apostrophes
        if (isalpha(i) || (i == '\''))
        {
            supplyword[wordindex] = i;
            wordindex++;
        }
        else if (isdigit(i))
        {
            while((i = fgetc(supply)) != EOF && isalpha(i));

            wordindex = 0;

        }
        else
        {
            supplyword[wordindex] = '\0';
            dictionarysize++;
            strncpy(storage[storageindex], supplyword, sizeof(supplyword) + 1);
            storageindex++;
            wordindex = 0;
        }
    }

    return true;
    // if success return true

}

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

    return dictionarysize;
}

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void)
{
    if (storage == NULL)
    {
        return false;
    }
    free(storage);
    fclose(supply);
    return true;
}

For further reference, I am attaching the two files:

dictionary.h

#ifndef DICTIONARY_H
#define DICTIONARY_H

#include <stdbool.h>

// maximum length for a word
// (e.g., pneumonoultramicroscopicsilicovolcanoconiosis)
#define LENGTH 45
#define LISTLENGTH 143091

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word);

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary);          

/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void);

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void);

bool search(int lower, int upper, const char* value);

#endif // DICTIONARY_H

speller.c

#include <ctype.h>
#include <stdio.h>
#include <sys/resource.h>
#include <sys/time.h>

#include "dictionary.h"
#undef calculate
#undef getrusage

// default dictionary
#define DICTIONARY "/home/cs50/pset5/dictionaries/large"

// prototype
double calculate(const struct rusage* b, const struct rusage* a);

int main(int argc, char* argv[])
{
    // check for correct number of args
    if (argc != 2 && argc != 3)
    {
        printf("Usage: speller [dictionary] text\n");
        return 1;
    }

    // structs for timing data
    struct rusage before, after;

    // benchmarks
    double time_load = 0.0, time_check = 0.0, time_size = 0.0, time_unload = 0.0;

    // determine dictionary to use
    char* dictionary = (argc == 3) ? argv[1] : DICTIONARY;

    // load dictionary
    getrusage(RUSAGE_SELF, &before);
    bool loaded = load(dictionary);
    getrusage(RUSAGE_SELF, &after);

    // abort if dictionary not loaded
    if (!loaded)
    {
        printf("Could not load %s.\n", dictionary);
        return 1;
    }

    // calculate time to load dictionary
    time_load = calculate(&before, &after);

    // try to open text
    char* text = (argc == 3) ? argv[2] : argv[1];
    FILE* fp = fopen(text, "r");
    if (fp == NULL)
    {
        printf("Could not open %s.\n", text);
        unload();
        return 1;
    }

    // prepare to report misspellings
    printf("\nMISSPELLED WORDS\n\n");

    // prepare to spell-check
    int index = 0, misspellings = 0, words = 0;
    char word[LENGTH+1];

    // spell-check each word in text
    for (int c = fgetc(fp); c != EOF; c = fgetc(fp))
    {
        // allow only alphabetical characters and apostrophes
        if (isalpha(c) || (c == '\'' && index > 0))
        {
            // append character to word
            word[index] = c;
            index++;

            // ignore alphabetical strings too long to be words
            if (index > LENGTH)
            {
                // consume remainder of alphabetical string
                while ((c = fgetc(fp)) != EOF && isalpha(c));

                // prepare for new word
                index = 0;
            }
        }

        // ignore words with numbers (like MS Word can)
        else if (isdigit(c))
        {
            // consume remainder of alphanumeric string
            while ((c = fgetc(fp)) != EOF && isalnum(c));

            // prepare for new word
            index = 0;
        }

        // we must have found a whole word
        else if (index > 0)
        {
            // terminate current word
            word[index] = '\0';

            // update counter
            words++;

            // check word's spelling
            getrusage(RUSAGE_SELF, &before);
            bool misspelled = !check(word);
            getrusage(RUSAGE_SELF, &after);

            // update benchmark
            time_check += calculate(&before, &after);

            // print word if misspelled
            if (misspelled)
            {
                printf("%s\n", word);
                misspellings++;
            }

            // prepare for next word
            index = 0;
        }
    }

    // check whether there was an error
    if (ferror(fp))
    {
        fclose(fp);
        printf("Error reading %s.\n", text);
        unload();
        return 1;
    }

    // close text
    fclose(fp);

    // determine dictionary's size
    getrusage(RUSAGE_SELF, &before);
    unsigned int n = size();
    getrusage(RUSAGE_SELF, &after);

    // calculate time to determine dictionary's size
    time_size = calculate(&before, &after);

    // unload dictionary
    getrusage(RUSAGE_SELF, &before);
    bool unloaded = unload();
    getrusage(RUSAGE_SELF, &after);

    // abort if dictionary not unloaded
    if (!unloaded)
    {
        printf("Could not unload %s.\n", dictionary);
        return 1;
    }

    // calculate time to unload dictionary
    time_unload = calculate(&before, &after);

    // report benchmarks
    printf("\nWORDS MISSPELLED:     %d\n", misspellings);
    printf("WORDS IN DICTIONARY:  %d\n", n);
    printf("WORDS IN TEXT:        %d\n", words);
    printf("TIME IN load:         %.2f\n", time_load);
    printf("TIME IN check:        %.2f\n", time_check);
    printf("TIME IN size:         %.2f\n", time_size);
    printf("TIME IN unload:       %.2f\n", time_unload);
    printf("TIME IN TOTAL:        %.2f\n\n", 
     time_load + time_check + time_size + time_unload);

    // that's all folks
    return 0;
}

/**
 * Returns number of seconds between b and a.
 */
double calculate(const struct rusage* b, const struct rusage* a)
{
    if (b == NULL || a == NULL)
    {
        return 0.0;
    }
    else
    {
        return ((((a->ru_utime.tv_sec * 1000000 + a->ru_utime.tv_usec) -
                 (b->ru_utime.tv_sec * 1000000 + b->ru_utime.tv_usec)) +
                ((a->ru_stime.tv_sec * 1000000 + a->ru_stime.tv_usec) -
                 (b->ru_stime.tv_sec * 1000000 + b->ru_stime.tv_usec)))
                / 1000000.0);
    }
}
2

Jessup: There's a few things here: 1) If you're calling a recursion on a function with a return value, like in this case, you should return each recursive call. This has nothing to do with the program hanging, but it will cause for it not to return the value expected. 2) You can't compare 2 strings with == or >/<. Look with gdb the result you get from your comparisons. What are you actually comparing when you use == with 2 strings? Even if it did work, you're not taking capitalization into account. You can see if with those two fixes the program runs correctly. Even if it does, i don't think it will pass check50: the idea of the program is that you should load a dictionary of a size you don't know beforehand. You're hardcoding the size of the dictionary here.

1
  • Thanks, Irene. This helped a lot. The program now works! – Jessup Jong Jul 19 '15 at 0:14

You must log in to answer this question.

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