Computer Science II - Lab 4: Unordered Lists

Objectives:

  • To Introduce the use of array's of objects
  • To Introduce the the Unsorted List ADT
  • To implement the operator< and operator!=

Instructions:

  • Create a word processing document as an answer sheet
  • Put all answers, and code, on the answersheet, numbering it as numbered below.
  • Turn the answer sheet into Moodle.

The list ADT

In the text the unsorted LIST ADT was developed. Below is a version that uses integers:

List.h

// Specification file array-based list (“list.h”)
const  int  MAX_LENGTH  =  50;
typedef int   ItemType;

class  List           // Declares a class data type
{ 
public:            // Public member functions

    List();           // constructor
    bool IsEmpty () const;
    bool IsFull ()  const;              
    int  Length ()  const; // Returns length of list 
    void Insert (ItemType  item);  
    void Delete (ItemType  item);  
    bool IsPresent(ItemType  item)  const;
    void SelSort ();
    void Reset ();
    ItemType GetNextItem ();  

private:       // Private data members
    int length;   // Number of values currently stored
    ItemType data[MAX_LENGTH]; 
    int  currentPos;  // Used in iteration       
};

List.cpp

// Implementation file array-based list (“list.cpp”)

#include  "list.h"
#include  <iostream>

using namespace std;

int  List::Length ()  const
// Post: Return value is length
{    
   return  length;
}
bool  List::IsFull ()  const
// Post: Return value is true if length is equal
//  to MAX_LENGTH and false otherwise
{
   return (length == MAX_LENGTH);
}
List::List ()
// Constructor
// Post: length == 0
{
   length = 0;
}

void  List::Insert (/* in */  ItemType  item)
// Pre: length < MAX_LENGTH && item is assigned
// Post: data[length@entry] == item && 
//       length == length@entry + 1
{
   data[length] = item;
   length++;
}
bool  List::IsEmpty ()  const
// Post: Return value is true if length is equal
//  to zero and false otherwise
{
   return (length == 0);
}
bool List::IsPresent( /* in */ ItemType item) const   
// Searches the list for item, reporting whether found
// Post: Function value is true, if item is in 
//   data[0 . . length-1] and is false otherwise
{    
    int index  =  0;
    while (index < length && item != data[index])
         index++;
    return  (index < length);
}


void  List::Delete ( /* in */  ItemType  item) 
// Pre: length > 0  &&  item is assigned
// Post: IF item is in data array at entry
// First occurrence of item is no longer in array
//    && length == length@entry - 1
// ELSE
//       length and data array are unchanged
{    
    int  index  =  0;
    
    while (index < length  &&  item != data[index])
    index++;
    // IF item found, move last element into 
    //  item’s place
    if (index < length)
    {
      data[index] = data[length - 1];
        length--;
    }
}
void List::Reset()
// Post: currentPos has been initialized.
{
    currentPos = 0;
}
ItemType List::GetNextItem ()
// Pre: No transformer has been executed since last call
// Post:Return value is currentPos@entry
//   Current position has been updated
//   If last item returned, next call returns first item
{
    ItemType item;
    item = data[currentPos];
    if (currentPos == length - 1)
        currentPos = 0;
    else
        currentPos++;
    return item;    
}

void  List::SelSort () 
// Sorts list into ascending order 

{   
   ItemType temp;
   int passCount;
   int sIndx;
   int minIndx;  // Index of minimum so far    
 
 for (passCount = 0; passCount < length - 1;
         passCount++)
   {
   minIndx = passCount;
   // Find index of smallest value left
   for (sIndx = passCount + 1; sIndx <  length; sIndx++)
     if (data[sIndx] < data[minIndx])
         minIndx = sIndx;
   temp = data[minIndx]; // Swap 
   data[minIndx] = data[passCount];
   data[passCount] = temp;
   }
}

Exercise 1

Create a project in Visual studio, and add the files above. Then write a simple test program which gives the following menu:

  1. Enter a new number
  2. Check for a certain number
  3. Delete a certain number
  4. Display the List
  5. Sort the List
Check the operation by doing the following:
  • Add 4, 6, 34, -23, 2, 6, 6, 45, 100
  • Check for 6, -23, 5,
  • Delete 6, -23, 100
  • Display the list
  • Check for 4, 6, 100
  • Sort the list
  • Check for 4, 6, 100
  • Display the list

Integrate with Date Class

Retrive your Date class. Create a new project called "Dates". Add both the List and Date classes. Comment out the list SelSort operation for right now.

Note that the List class requires the type it operates on to support the != comparison operator. You will thus need to add it to your Date class:

bool Date::operator!=(Date date1) const
{
   if (year != date1.year) return true;
   if (month != date1.month) return true;   
   return ( day != date1.day );

}

Modify the List class to operate on the data type "Date" by changing the typedef in List.h. Your will also need to #include "Date.h" in List.h.

Also bring in your test program from above, and make the required changes operate on a list of dates. Again, comment out the SelSort option for now.

Exercise 2

Get the above code to work.

Check the operation by doing the following (it should reject the bad dates with a mesage):

  • Add 3/12/2004 4/19/2011 6/34/2010 4/4/1993 4/19/2011 5/20/2012
  • Check for 4/19/2011 6/22/1955 5/20/2012
  • Delete 4/19/2011 6/22/1955 3/12/2004
  • Display the list
  • Check for 4/19/2011 3/12/2004 5/20/2012

Exercise 3

The reason we commented out the SelSort operation was because your Date function does not currently implement the < function. We need to add this. Review Lab3 (with the factions), and add operator<.

bool Date::operator<(Date date1) const
{
   if (year < date1.year) return true;
   if (year ==  date1.year && month < date1.month) return true;   
   return ( year ==  date1.year && month == date1.month && day < date1.day );

}

Uncomment the SelSort code, and try to get it working.

Check the operation by doing the following (it should reject the bad dates with a mesage):

  • Add 3/12/2004 4/19/2011 6/34/2010 4/4/1993 4/19/2011 5/20/2012
  • Check for 4/19/2011 6/22/1955 5/20/2012
  • Delete 4/19/2011 6/22/1955 3/12/2004
  • Display the list
  • Check for 4/19/2011 3/12/2004 5/20/2012
  • Sort the list
  • Check for 4/19/2011 3/12/2004 5/20/2012
  • Display the list
Turn in every thing in a word document on Moodle

-- JimSkon - 2011-03-10

Topic revision: r7 - 2011-03-18 - JimSkon
 
This site is powered by the TWiki collaboration platformCopyright &© by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback