Sorted List Example
What am I doing wrong? I cannot get this student example to compile.
I am using DEVC++ to compile the source code. This source is a student example of a Sorted list provided by the author of “C++ plus Data Structures” (Nell Dale)
You can find it here http://computerscience.jbpub.com/cpp...es/student.zip
It’s in the Chapter3/Sorted folder.
I’ll also post the code.
Code:// The following declarations and definitions go into file // ItemType.h. #include <fstream> const int MAX_ITEMS = 5; enum RelationType {LESS, GREATER, EQUAL}; class ItemType { public: ItemType(); RelationType ComparedTo(ItemType) const; void Print(std::ostream&) const; void Initialize(int number); private: int value; };Code:// The following definitions go into file ItemType.cpp. #include <fstream> #include <iostream> #include "ItemType.h" ItemType::ItemType() { value = 0; } RelationType ItemType::ComparedTo(ItemType otherItem) const { if (value < otherItem.value) return LESS; else if (value > otherItem.value) return GREATER; else return EQUAL; } void ItemType::Initialize(int number) { value = number; } void ItemType::Print(std::ostream& out) const // pre: out has been opened. // post: value has been sent to the stream out. { out << value; }
Code:#include "ItemType.h" // File ItemType.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 class SortedType { public: SortedType(); bool IsFull() const; // Function: Determines whether list is full. // Pre: List has been initialized. // Post: Function value = (list is full) int LengthIs() const; // Function: Determines the number of elements in list. // Pre: List has been initialized. // Post: Function value = number of elements in list void RetrieveItem(ItemType& item, bool& found); // 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 item is a copy of // someItem; otherwise found = false and item is unchanged. // List is unchanged. void InsertItem(ItemType item); // Function: Adds item to list. // Pre: List has been initialized. // List is not full. // item is not in list. // List is sorted. // Post: item is in list. // List is sorted void 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. // List is sorted. void ResetList(); // Function: Initializes current position for an iteration through the list. // Pre: List has been initialized. // Post: Current position is prior to list. void GetNextItem(ItemType& item); // 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; ItemType info[MAX_ITEMS]; int currentPos; };
Code:// Implementation file for sorted.h #include "sorted.h" SortedType::SortedType() { length = 0; } bool SortedType::IsFull() const { return (length == MAX_ITEMS); } int SortedType::LengthIs() const { return length; } void SortedType::RetrieveItem(ItemType& item, bool& found) { int midPoint; int first = 0; int last = length - 1; bool moreToSearch = first <= last; found = false; while (moreToSearch && !found) { midPoint = ( first + last) / 2; switch (item.ComparedTo(info[midPoint])) { case LESS : last = midPoint - 1; moreToSearch = first <= last; break; case GREATER : first = midPoint + 1; moreToSearch = first <= last; break; case EQUAL : found = true; item = info[midPoint]; break; } } } void SortedType::DeleteItem(ItemType item) { int location = 0; while (item.ComparedTo(info[location]) != EQUAL) location++; for (int index = location + 1; index < length; index++) info[index - 1] = info[index]; length--; } void SortedType::InsertItem(ItemType item) { bool moreToSearch; int location = 0; moreToSearch = (location < length); while (moreToSearch) { switch (item.ComparedTo(info[location])) { case LESS : moreToSearch = false; break; case GREATER : location++; moreToSearch = (location < length); break; } } for (int index = length; index > location; index--) info[index] = info[index - 1]; info[location] = item; length++; } void SortedType::ResetList() // Post: currentPos has been initialized. { currentPos = -1; } void SortedType::GetNextItem(ItemType& item) // Post: item is current item. // Current position has been updated. { currentPos++; item = info[currentPos]; }
Code:// Test driver #include <iostream> #include <fstream> #include <string> #include <cctype> #include <cstring> #include "sorted.h" using namespace std; void PrintList(ofstream& outFile, SortedType list); int main() { ifstream inFile; // file containing operations ofstream outFile; // file containing output string inFileName; // input file external name string outFileName; // output file external name string outputLabel; string command; // operation to be executed int number; ItemType item; SortedType list; bool found; int numCommands; // Prompt for file names, read file names, and prepare files cout << "Enter name of input command file; press return." << endl; cin >> inFileName; inFile.open(inFileName.c_str()); cout << "Enter name of output file; press return." << endl; cin >> outFileName; outFile.open(outFileName.c_str()); cout << "Enter name of test run; press return." << endl; cin >> outputLabel; outFile << outputLabel << endl; inFile >> command; numCommands = 0; while (command != "Quit") { if (command == "InsertItem") { inFile >> number; item.Initialize(number); list.InsertItem(item); item.Print(outFile); outFile << " is inserted" << endl; } else if (command == "DeleteItem") { inFile >> number; item.Initialize(number); list.DeleteItem(item); item.Print(outFile); outFile << " is deleted" << endl; } else if (command == "RetrieveItem") { inFile >> number; item.Initialize(number); list.RetrieveItem(item, found); if (found) outFile << number << " found in list." << endl; else outFile << number << " not in list." << endl; } else if (command == "LengthIs") outFile << "Length is " << list.LengthIs() << endl; else if (command == "IsFull") if (list.IsFull()) outFile << "List is full." << endl; else outFile << "List is not full." << endl; else PrintList(outFile, list); numCommands++; cout << " Command number " << numCommands << " completed." << endl; inFile >> command; }; cout << "Testing completed." << endl; inFile.close(); outFile.close(); return 0; } void PrintList(ofstream& dataFile, SortedType list) // Pre: list has been initialized. // dataFile is open for writing. // Post: Each component in list has been written to dataFile. // dataFile is still open. { int length; ItemType item; list.ResetList(); length = list.LengthIs(); for (int counter = 1; counter <= length; counter++) { list.GetNextItem(item); item.Print(dataFile); } dataFile << endl; }
