Data Structures and Algorithms I - Lab 3- A List ADT

Name _____________________________ Section ______________ Score ____________________

Objectives

To practice implementing and using a simple ADT.

Background

Abstract Data Types are often implemented in C++ using classes. This allows the use of private and public member access specifiers to be used to control access to the members of the class. It also promotes information hiding through the use of a public interface. Classes allow operations to be grouped; encapsulation is achieved by placing the implementation in a separate file from the class definition.

Experimental Procedure/Analysis

Task 1

Create a new Win32 Console Application project called Lab03 in an appropriate folder on your local hard disk. Add a new header file to the project named List.h. Place the standard #ifndef statement (and the associated #define and #endif) in the file. Add documentation at the top about the programmer, date, and project. This will form the definition of a List class that implements a simple List With Current Item ADT suggested by Shaffer. This list has positions numbered 1, 2, 3, ..., n+1 where n is the number of items currently in the list. The last position listed, n+1, represents the end of list position. It is used to append items to the end of the list. The List operations are as follows: At this time, we do not know what data type will be stored in the list. We will try to make our development as generic as possible so later we can support lists of integers, lists of strings, lists of fractions, or lists of lists! We will choose an array of ITEM_TYPE (this is the unknown data type) as the underlying data structure to hold the list contents. A typedef statement will be used to make this a meaningful type. In addition, we will assume that no lists may grow beyond 100 items (we will make this a constant in the header file). When we cover dynamic memory allocation, we will see how to relax this limitation.

Task 1a

Add the following constant and class definition to the header file.
//Specify the type of list components in this typedef
typedef int ITEM_TYPE
const int MAX_ITEMS = 100; //List length limit
class List{
public:
        List();
        ~List();
        bool insert(const ITEM_TYPE &);
        bool remove(void);
        void setPos(int n=1);
        void next(void);
        void prev(void);
        ITEM_TYPE currValue(void) const;
        int length(void) const;
private:
        ITEM_TYPE items[MAX_ITEMS];
        int currentPos, numItems;
};
Add a new source file to the project named List.cpp. This will contain the implementation of our List class. Enter these lines to implement the constructor and destructor.
List::List(){
        std::cout << "List constructor called - creating empty list\n";
        numItems = 0;
        //current starts at 'first' position
        // (which is also the 'end of the list' position for an empty list)
        currentPos=1; 
}
List::~List(){
        std::cout << "List destructor called\n";
}
Add another source file (Driver.cpp) to the project. Write a main function that displays a message that main has started (first line of main is std::cout << ...) and another that main has exited (last line, just before the return 0;). Declare a global variable of type List named globalList. Immediately after the first std::cout in main, declare a local variable of type List named localList. Add a block to main after the declaration of localList that includes a cout stating the block was entered, followed by a declaration of another List object named innerList, followed by another cout that states the block is ending. Build and test the project.

What files must be included in Driver.cpp to compile Driver.cpp? (look at the code to determine your answer)

_____________________________________  (list all required files)

What files must be included in List.cpp to compile List.cpp? (look at the code to determine your answer)

_________________________________________  (list all required files)

Record the messages displayed by the program in the order they appear when it runs:


 

 

 

When is the constructor for globalList called?

 

When is the constructor for localList called?

 

When is the constructor for innerList called?

 

When is the destructor for globalList called?

 

When is the destructor for localList called?

 

When is the destructor for innerList called?

 

Task 1b

In this task we will implement and test the insert function (in List.cpp). This function is given a const reference to an ITEM_TYPE value and must copy it into the list at the current location. The insert function never overwrites existing list data - it (almost) always causes the list to grow in length. When an item is inserted, current remains unchanged, so the new item will be current. Remember that the list's "current position" is an ordinal position: 1, 2, 3, etc. Physically, list items will be stored in an array, beginning at subscript 0. The first item in the list (at position 1) is therefore stored in the array at subscript 0. Keep this translation in mind as you implement the List methods.

Consult the List header file, and then answer this question. What statement would test for a full list?

if (_____________________________) // the list is full

What is the relational expression between the data members currentPos and numItems that indicates the current position is the 'end of list' position?

if (_______________________________________________) //List is at the 'end of list' position

There are several pitfalls to watch out for as you complete the body of the insert function:

  1. Is the list full? If so, do nothing and return false as a fail signal. Otherwise return true to indicate success.
  2. When inserting at position i, items at positions i and above must be moved over (in the array) to make room for the new item.
  3. Remember to update the number of items in the list.
When you get a clean compile on the insert function, modify main (in Driver.cpp) to add the integers 1 through n (create the variable n and initialize it to 10 for the upper limit) to the list localList (use a loop and the insert method). The loop should terminate with an error message if the insert method ever fails. Test that the program runs without error. You cannot see the results yet; this will come in a later task.

Change the value of n to insert more integers (1, 2, 3, ...) in the list; you want to test the failure of the insert method. 

When insert fails, what integer was being inserted into the list?  ___________ 

Change the upper limit back to 10.

Task 1c

To finish our testing, we need a simple way to output the list. Add a public method to the List class called print(). This function should simply print the elements of the list, first to last, separated by commas. Start the list with "[" and end it with "]\n" so there is no confusion about the list contents. Call this method from main after the items have been added to the list. Test your program and record the output here:
 
 

What is the list's current position when the list is created? _________ (1, 2, ...?)

Does the insert method change the list's current position? _________ (yes/no) - hint: recheck the specs for this method

At what position is the largest integer (n) inserted?  ________ (1, 2, ...?)

Examine the public List methods and design a modification (using some of these methods) to your loop in main so that item x (1, 2, 3, ...) would be inserted at position x of the list. Write the entire loop that implements your idea here (but do not add it to the code)

 

 

 

Be sure your name appears in each file of the project and then print all of the files. Hand in this lab stapled with your three files. Remember to clean up the local hard disk storage and save your project so you can access it again. We will need it for the next lab.