C++

For this assignment, you will implement dictionary.h to create a dictionary that reads in a list of unsorted words into a STL (which is an implementation of a doubly linked list.) from a file called dictionary.txt. Next, you must sort the list. The list STL has a member function .sort which works as long as you have overloaded the 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).

The reason you have a separate DictEntry.h is 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 easilly use the definition, pronunciation, word history etc.

Some Important tips (please read): http://www.cplusplus.com/reference/list/list/ (Links to an external site.)Links to an external site.

- Remember like a vector, you have a list of a particular type (dictionary in this case)

- A list::iterator is a pointer to a list containing dictionary items. Not every operator is defined, but ++ and -- are defined, so you can increment or decrement the pointer.

- There are member functions for a list .begin() which is pointing to the first item on the list and .end() which is the last pointer NULL. So, you generally want to loop from .begin() to != .end()

To start at the back (tail pointer) and work you way to the front you want to reverse the process. so instead of an iterator (which points to the head of the list), you want to use reverse_iterator. And instead of .begin() to != .end(), you want to go from .rbegin() to != .rend()

In order to use the .sort() function for lists, you must overload the operator

Remember if you are looking at the VALUE of what the pointer points to, you must dereference the pointer. An iterator or reverse_iterator is a pointer. If you are pointing to a class with a public member function called findValue, you would write that as xPtr->getWords(), NOT xPtr.findValue.

code for dictionary.h:

#ifndef DICTIONARY_H

#define DICTIONARY_H

#include

#include

#include

#include "DictEntry.h"

using namespace std

class dictionary

{

public:

//typedef string wordType;

dictionary();

/*Searches the list starting at the front of the list and moving to the back

Returns the number of searches it took to find the findString, or a -1 if not found*/

int searchForward(list &wordList,wordType &findString);

/*Searches the list starting at the back of the list and moving to the front

Returns the number of searches it took to find the findString, or a -1 if not found*/

int searchBackward(list &wordList,wordType &findString);

/*Prints the list of words in reverse alphabetic order to a file*/

void revPrintList(ostream& output, list &wordList);

};

/*******************************/

#endif

code for DictEntry.h:

#ifndef DICTENTRY_

#define DICTENTRY_

#include

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

return (word

};

#endif

Dictionary.txt

dog cat hippo zebra aardvark

FindWords.txt

cat dog lion zebra