Exercise 1 (Use list that is implemented using dynamic array)

Write a member function of the unsorted list class int Occurrence(ItemType item) that returns the number of occurrences of the item in the list.

Write a driver program to create an unsorted list for all the words in a given file by name input.txt and use this list to print the number of occurrences of each distinct word in the list.

\\ --------unsorted.cpp ---------------------------------------------------------

// Implementation file for Unsorted.h

#include "uslist.h"

UnsortedType::UnsortedType(int maxItems) { length = 0; MAX_ITEMS = maxItems; info = new ItemType[MAX_ITEMS]; currentPos = -1; } bool UnsortedType::IsFull() const { return (length == MAX_ITEMS); } int UnsortedType::GetLength() const { return length; }

ItemType UnsortedType::RetrieveItem(ItemType item, bool& found) // Pre: Key member(s) of item is initialized. // Post: If found, item's key matches an element's key in the // list and a copy of that element has been returned; // otherwise, item is returned. { bool moreToSearch; int location = 0; found = false;

moreToSearch = (location < length);

while (moreToSearch && !found) { switch (item.ComparedTo(info[location])) { case LESS : case GREATER : location++; moreToSearch = (location < length); break; case EQUAL : found = true; item = info[location]; break; } } return item; } void UnsortedType::MakeEmpty() // Post: list is empty. { length = 0; } Error_code UnsortedType::InsertItem(ItemType item) // Post: item is in the list. { info[length] = item; length++; return Success; } Error_code UnsortedType:: DeleteItem(ItemType item) // Pre: item's key has been initialized. // An element in the list has a key that matches item's. // Post: No element in the list has a key that matches item's. { int location = 0;

while (item.ComparedTo(info[location]) != EQUAL) location++; if(location == length) return Fail; info[location] = info[length - 1]; length--; return Success; } void UnsortedType::ResetList() // Post: currentPos has been initialized. { currentPos = -1; }

ItemType UnsortedType::GetNextItem() // Pre: ResetList was called to initialized iteration. // No transformer has been executed since last call. // currentPos is defined. // Post: item is current item. // Current position has been updated. { currentPos++; return info[currentPos]; }

\\ ----------- unsorted.h--------------------------------------

#ifndef uslist_h

#define uslist_h

#include

#include "Word.h"

using namespace std;

typedef Word ItemType;

// File Word.h must be provided by the user of this class.

// ItemType.h must contain the following definitions:

// MAX_ITEMS: the maximum number of items on the list

// ItemType: the definition of the objects on the list

// RelationType: {LESS, GREATER, EQUAL}

// Member function ComparedTo(ItemType item) which returns

// LESS, if self "comes before" item

// GREATER, if self "comes after" item

// EQUAL, if self and item are the same

enum Error_code {Success,Fail};

class UnsortedType

{

public:

UnsortedType(int maxItems=10);

// Constructor

void MakeEmpty();

// Function: Returns the list to the empty state.

// Post: List is empty.

bool IsFull() const;

// Function: Determines whether list is full.

// Pre: List has been initialized.

// Post: Function value = (list is full)

int GetLength() const;

// Function: Determines the number of elements in list.

// Pre: List has been initialized.

// Post: Function value = number of elements in list

ItemType RetrieveItem(ItemType, bool&);

// Function: Retrieves list element whose key matches item's key (if

// present).

// Pre: List has been initialized.

// Key member of item is initialized.

// Post: If there is an element someItem whose key matches

// item's key, then found = true and someItem is returned.

// otherwise found = false and item is returned.

// List is unchanged.

Error_code InsertItem(ItemType item);

// Function: Adds item to list.

// Pre: List has been initialized.

// List is not full.

// item is not in list.

// Post: item is in list.

Error_code DeleteItem(ItemType item);

// Function: Deletes the element whose key matches item's key.

// Pre: List has been initialized.

// Key member of item is initialized.

// One and only one element in list has a key matching item's key.

// Post: No element in list has a key matching item's key.

void ResetList();

// Function: Initializes current position for an iteration through the list.

// Pre: List has been initialized.

// Post: Current position is prior to list.

ItemType GetNextItem();

// Function: Gets the next element in list.

// Pre: List has been initialized and has not been changed since last call.

// Current position is defined.

// Element at current position is not last in list.

//

// Post: Current position is updated to next position.

// item is a copy of element at current position.

private:

int length, MAX_ITEMS;

ItemType * info;

int currentPos;

};

#endif

\\ --------------------- word.cpp -----------------------------

#include "word.h"

Word::Word(string wd )

{

word =wd;

}

string Word::getWord()

{

return word;

}

void Word::setWord(string wd)

{

word=wd;

}

void Word::printWord()

{

cout << word << endl;

}

RelationType Word::ComparedTo(Word otherItem) const

{

if (word < otherItem.word)

return LESS;

else if (word > otherItem.word)

return GREATER;

else return EQUAL;

}

\\ ----------------- word.h -------------------------

#ifndef s_h

#define s_h

#include

#include

using namespace std;

enum RelationType {LESS, GREATER, EQUAL};

class Word

{

public:

Word(string fname=" ");

string getWord();

void setWord(string wd);

void printWord();

RelationType ComparedTo(Word ) const;

private:

string word;

};

#endif