Exercise 1 ( Use list that is implemented using dynamic array ) Write a member f
ID: 3722973 • Letter: E
Question
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 <iostream>
#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 <iostream>
#include <string>
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
Explanation / Answer
main.cpp
//main.cpp
#include<iostream>
#include <fstream>
#include<string>
#include <fstream>
#include "Word.h"
#include"uslist.h"
using namespace std;
int Occurrence(const UnsortedType & list, ItemType item) {
int count = 0;
UnsortedType tmplst = list;
tmplst.ResetList();
ItemType tmp;
for (int i = 0; i < list.GetLength(); i++) {
tmp = tmplst.GetNextItem();
if (tmp.ComparedTo(item) == EQUAL)
count++;
}
tmplst.ResetList();
return count;
}
int main() {
ifstream in;
in.open("input.txt");
UnsortedType l(50);
Word item, nextitem;
string s;
while (!in.eof()) {
in >> s;
//for some reason in>>s reads the last word twice
item.setWord(s);
if (l.InsertItem(item) == Fail) {
cout << "List full";
return 0;
}
}
UnsortedType temp = l;
int num = 0;
while (temp.GetLength() != 0) {
item = temp.GetNextItem();
item.printWord();
num = Occurrence(temp, item);
cout << " " << num << endl;
for (int i = 0; i < num; i++) {
temp.ResetList();
temp.DeleteItem(item);
}
}
}
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;
}
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 <iostream>
#include <string>
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
uslist.cpp
// Implementation file for Unsorted.h
#include "uslist.h"
UnsortedType::UnsortedType(int maxItems) {
currentPos = -1;
length = 0;
MAX_ITEMS = maxItems;
info = new ItemType[MAX_ITEMS];
}
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.
{
if (IsFull())
return Fail;
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];
}
Error_code UnsortedType::Resize(int increaseSize) {
if (increaseSize < length + 1 || increaseSize > MAX_ITEMS) {
return Fail;
}
ItemType temp[length];
for (int i = 0; i <= length; i++) {
temp[i] = this->info[i];
}
delete[] info;
info = new ItemType[increaseSize];
for (int i = 0; i <= length; i++) {
this->info[i] = temp[i];
}
return Success;
}
UnsortedType UnsortedType::operator=(const UnsortedType rhs) {
if (this->length != rhs.length) {
delete[] info;
info = new ItemType[rhs.length];
}
this->MAX_ITEMS = rhs.MAX_ITEMS;
this->currentPos = rhs.currentPos;
this->length = rhs.length;
for (int i = 0; i <= length; i++) {
this->info[i] = rhs.info[i];
}
return *this;
}
uslist.h
#ifndef uslist_h
#define uslist_h
#include <iostream>
#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.
Error_code Resize(int increaseSize);
UnsortedType operator= (const UnsortedType rhs);
private:
int length, MAX_ITEMS;
ItemType * info;
int currentPos;
};
#endif
input.txt
Apple Car Orange
Car Apple
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.