For this assignment, you will create a dictionary class that reads in a list of

ID: 3724598 • Letter: F

Question

For this assignment, you will create a dictionary class that reads in a list of unsorted words into a <list> STL (which is an implementation of a doubly linked list.) from a file called dictionary.txt You will use a list of dictionary entries (DictEntry). Next, you must sort the list. The list STL has a member function .sort which works as long as you have overloaded the < operator for the data type you are sorting). Now, you will read a list of words from a file called findwords.txt For each word in findwords.txt, you will search that list from the beginning of the list and if found, print (to the screen) how many searches/comparisons you had to make to find the word. Then you will search from the back of the list and print how many searches you had to make.

This will help you visualize that a Doubly Linked List might on average cut your search time in half by sorting the data, then choosing which end to start the search.

When complete print out each word with spaces in between in a file called revsorted.txt. Start at the back of the list so you end up with a reverse sorted list (words starting with z's first).

You will have a separate Dictionary class that uses a dictionary entry as defined with the Dicentry.h We do this to separate the dictionary methods from the type of data. If you were implementing your own doubly linked list, you would create a separate Node class. Remember, Nodes have data (which would be a dictionary entry), and forward and back pointers. Currently we are only using the word in DictEntry, but could easily use the definition, pronunciation, word history etc.

Extra Credit (up to 10 points!): In addition to the above implement the same functionality with a double linked list that you create with dynamically allocated pointers (replacing the STL list). So you would have a doubleLinkedList of dictEntry. You must note this in your readme.txt for credit.

------------------------------

Dictionary.txt is as follow:

Dog

cat

hippo

zebra

aardvark

---------------------------

findwords.txt is as follow

cat

dog

lion

zebra

----------------------------------

Dicentry.h is as follow

#ifndef DICTENTRY_

#define DICTENTRY_

#include <string>

typedef std::string wordType;

class DictEntry

{

private:

wordType word;

wordType definition;

public:

wordType getWord(){return word;}

void setWord(wordType _word){word = _word;}

wordType getDef(){return definition;}

void setDef(wordType _def){definition = _def;}

bool operator < (const DictEntry &entry) const {

return (word < entry.word);}

};

#endif

USE LANGUAGE C++ only!!

Explanation / Answer

dictionary.h

#ifndef dictionary_h
#define dictionary_h
#include <string>
#include <list>
#include <iostream>

using namespace std;
typedef string wordType;

class dictionary {
   public:
   // typedef string wordType;
   dictionary();
   wordType getWord();
   void setWord(wordType _word);
   friend bool operator <(const dictionary& first, const dictionary& second);
   private:
   wordType word;
};

/*******************************/
int searchForward(list<dictionary> &wordList, wordType &findString);

int searchBackward(list<dictionary> &wordList, wordType &findString);

void revPrintList(ostream& output, list<dictionary> &wordList);

bool comp(dictionary& first, dictionary& second);

#endif /* dictionary_h */

dictionary.cpp

#include "dictionary.h"
using namespace std;

dictionary::dictionary() {}

wordType dictionary::getWord() {
return word;
}

void dictionary::setWord(wordType newWord) {
word = newWord;
}

int searchForward(list<dictionary> &wordList, wordType &findString) {

// forward iterator
list<dictionary>::iterator f_it;

   bool isStringFound = false;
   int stepCount = 0;
   for(f_it = wordList.begin(); f_it != wordList.end(); ++f_it) {
       // increment the count for the current step taken
       stepCount += 1;

       // if we found the word break out of the loop
       if (f_it -> getWord() == findString) {
           isStringFound = true;
           break;
       }
   }

if (isStringFound) return stepCount;
else return -1;
}

int searchBackward(list<dictionary> &wordList, wordType &findString) {

// reverse iterator
list<dictionary>::reverse_iterator r_it;

   bool isStringFound = false;
   int stepCount = 0;
   for (r_it = wordList.rbegin(); r_it != wordList.rend(); ++r_it) {
       // increment the count for the current step taken
       stepCount += 1;

       // if we found the word break out of the loop
       if (r_it -> getWord() == findString) {
           isStringFound = true;
           break;
       }
   }

if (isStringFound) return stepCount;
else return -1;
}

void revPrintList(ostream& output, list<dictionary> &wordList) {

// reverse iterator
list<dictionary>::reverse_iterator r_it;

   // print each word
   for (r_it = wordList.rbegin(); r_it != wordList.rend(); ++r_it) {
       output << r_it -> getWord() << endl;
   }
}

bool comp(dictionary& first, dictionary& second) {
return first.getWord() < second.getWord();
}

bool operator <(const dictionary& first, const dictionary& second) {
return first.word < second.word;
}

main.cpp

#include <bits/stdc++.h>
#include "dictionary.h"
using namespace std;

int main() {

FILE *fp = freopen("dictionary.txt", "r", stdin);

   // fill the word list from file
   list<dictionary> wordList;
   wordType word;
   while (cin >> word) {
       // create new dictionary object
       dictionary* newDictionaryObj = new dictionary();
       newDictionaryObj -> setWord(word);

       // add it to list
       wordList.push_back(*newDictionaryObj);
   }
   fclose(fp);

// sort the list
wordList.sort();

   // search word from find words file
   ifstream infile;
   infile.open("findwords.txt", ifstream::in);
   while (infile >> word) {
       int forwardStepCount = searchForward(wordList, word);
       int backwardStepCount = searchBackward(wordList, word);

       // if not found in search add it to end of the list and sort
       // list again
       if (forwardStepCount == -1 || backwardStepCount == -1) {
           cout << "Info: Word not found adding to list" << endl;

           // create new dictionary object
           dictionary* newDictionaryObj = new dictionary();
           newDictionaryObj -> setWord(word);

           wordList.push_back(*newDictionaryObj);
           wordList.sort();
       } else {
           cout << "Word : " << word << endl;
           cout << "Forward Step Count : " << forwardStepCount << endl;
           cout << "Backward Step Count : " << backwardStepCount << endl;
           cout << endl;
       }
   }
   infile.close();

   fp = freopen("revsorted.txt", "w", stdout);
   revPrintList(cout, wordList);
   fclose(fp);
   return 0;
}

Navigate

For this assignment, you will create a class, Gameboard, that will contain metho

For this assignment, you will create a dictionary class that reads in a list of

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

For this assignment, you will create a dictionary class that reads in a list of

Question

Explanation / Answer

Related Questions

Navigate