Project#3: Searching and Sorting

In this project you are to first create a class called which contains an array of strings of size DICT_SIZE which encapsulate several variables and methods.  Its purpose is to hold a dictionary of distinct words in the English language. Here is the definition of this class. Define  a constant DICT_SIZE to be 500.

class Dict
 string _word[DICT_SIZE];
 int _size;
 // This method adds a new word to the dictionary. Returns false if overflow // The following function adds a new word to the end of the dictionary
 bool AddToDict(string);//implement this first and load the example data
 //return true if in dictionary and false otherwise //Sorts the Dictionary
 void iSort();// Performs an insertion sort on the _word array O(n2)
bool BSearch(string);// Does a binary search on the array O(log2n)

The program reads in a dictionary of words from the file wordlist.txt.   This file begins with an integer N which is followed by N strings  which continue on this and subsequent lines separated by blanks. First read in the integer N, and then read in the next N words loading each into the dictionary via AddToDict().   The AddToDict() adds a new word to the dictionary _word[] at the end of the array.  It does not need to check if the word is already in the dictionary, we will assume it is not since AddToDict is basically used to load another collection of words already known to be a unique dictionary of English words. After reading in this dictionary of lowercase words into an array you are to sort the array of strings by calling the method iSort(). The next phase of the program is to read in another file document.txt and check each word to see if it is in the dictionary.  Document.txt is just a letter or poem that we will do a spellcheck on.  If the word is not in the dictionary, we will assume that is is spelled incorrectly and print the offending misspelled word and go on to the next word.  Note that many of the strings need to be lowercased and even may have some additional punctuation characters such as hello,  or can’t and these need to be removed prior to checking. You need to remove these by writing the function  string Clean(string wd). This takes a word wd and returns the cleaned up word without punctuation and with every character converted to lowercase. Here is the function that you can use.

string Clean(string w) {
 string cw;
 for (int i = 0; i < w.length(); i++) {
    if (isalpha(w[i]))// if it is an alphabetic char
       cw.push_back(tolower((char)w[i]));// adds new char on end of string.
 return cw;

After loading and sorting the wordlist.txt output Dictionary is loaded and sorted. In addition to AddToDict() you  need to write a sort method called iSort() that performs an insertion sort on the array of strings within the dictionary class.  When the program has completed its processing print out either Document is clean of misspelled words  or the misspelled words and number as indicated in the output given below.

Example wordlist.txt file: wordlist, example document.txt file:document.  Use these to test and develop your program.  Remind me to discuss Clean() in class.  Here is the output for the above data

Dictionary loaded and sorted
enugh lage rmember :are not in the dictionary
Document has 3 misspelled words

Comments are closed.