Sorted List Example

This is a discussion on Sorted List Example within the C++ Programming forums, part of the General Programming Boards category; What am I doing wrong? I cannot get this student example to compile. I am using DEVC++ to compile the ...

  1. #1
    Pupil
    Join Date
    Oct 2005
    Location
    Toledo
    Posts
    27

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

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >I cannot get this student example to compile.
    That suggests you're getting compiler errors. What are they?
    My best code is written with the delete key.

  3. #3
    Pupil
    Join Date
    Oct 2005
    Location
    Toledo
    Posts
    27

    errors

    when compiling // Test driver

    Line 11: type specifier omitted for parameter
    Line 11: parse error before `)'
    Line 24: ItemType' undeclared (first use this function)

  4. #4
    Registered User
    Join Date
    Apr 2003
    Posts
    2,662
    Whatever their names are, you need to include the first file and the third file at the top of the file containing main(), e.g.:

    Code:
    #include "firstFile.h"
    #include "thirdFile.h"
    
    ...
    ...
    int main()
    {
    Last edited by 7stud; 11-20-2005 at 02:32 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 11:10 AM
  2. Pleas take a look & give a critique
    By sh3rpa in forum C++ Programming
    Replies: 14
    Last Post: 10-19-2007, 11:01 PM
  3. Inserting new nodes in a sorted double linked list
    By carrja99 in forum C++ Programming
    Replies: 2
    Last Post: 03-07-2003, 08:34 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 06:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21