This will help you visualize that a Doubly Linked List might on average cut your

Question

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 on a new line 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).

For this assignment, you should have setup a class called dictionary that holds a word as type string, with a single private value, a default constructor and appropriate get/set functions. This way you could (in the future) expand the definition

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

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

- A list<dictionary>::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 <, as a friend function of the class. The .sort() function uses this operator to sort.

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

Here is the code for dictionary.h

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;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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