Program 3 - List Class with a Dynamic Array

COSC 2415 - Data Structures and
ITSE 2445 Data Structures
Bob Comer, Professor of Computer Studies

Program 3 - List Class with a Dynamic Array

Be sure to read through Section 6.3 in your textbook before starting this assignment. Be sure that your program meets the requirements listed on the Professional Programming Style page (see link on the main assignments page).

In this assignment, you will start with the List class from Figure 6.2 of your textbook. This class uses a dynamic array to store the items in the list. Your list class will add the ability to increase or decrease the capacity of the list (size of the dynamic array). For background information, refer to Section 6.3 An Array-Based Implementation of Lists with Dynamic Allocation from your text book and the first solution to Deficiency #1 on page 85.

You can download the code the List class from Figure 6.2 here:

http://cs.calvin.edu/activities/books/c++/ds/2e/SourcePrograms/

The code in the textbook tends to display messages in class functions, so I am providing an edited copy of the class implementation file here:

DList.cpp

Important: Remember that every list has a size (the number of items in the list) and a capacity (the maximum number of items that the list can hold).

Add a public function member called setCapacity( ) as follows:

   void setCapacity( int newCapacity);
   /*----------------------------------------------------------------------
     Change the capacity of the list

     Precondition:  None.
     Postcondition: The list's current capacity is changed to newCapacity
         (but not less than the number of items already in the list).
   -----------------------------------------------------------------------*/

Pseudocode:

If newCapacity < current size
   Set newCapacity to current size
End If
If newCapacity is the same as the current capacity
   Do nothing (return)
End If
Dynamically allocate a new array with size newCapacity
Copy the data from the current array to the new array
Free the memory allocated to the current (old) array
Make the list point to the new array
Update the capacity of the list

Add public function members that allow the client programmer to retrieve the current size and capacity of the list as follows:

   int getSize( ) const;
   /*----------------------------------------------------------------------
     Return the size of the list

     Precondition:  None.
     Postcondition: The return value is the number of elements in the list
         (the list size).
   -----------------------------------------------------------------------*/

   int getCapacity( ) const;
   /*----------------------------------------------------------------------
     Return the capacity of the list

     Precondition:  None.
     Postcondition: The return value is the maximum number of elements that the list can hold
         (the list capacity).
   -----------------------------------------------------------------------*/

Modify the insert( ) function as follows. Remove the precondition that there is room in the array for the item to be inserted. If the array is full, double its capacity using setCapacity( ) and then perform the insertion.

Be sure to update your class documentation as required. Note: I will only grade the documentation for the class functions that you added or modified.

Test your class using a list of integers. Use a menu-driven program for testing where the user can specify which command to test and the data to store in the list.

To facilitate testing, in some cases it would be nice to quickly add a number of items to the list. Add a menu option that has the user input a positive integer and then adds that number of items to the List. The items to be added should be random integers in the range 0 - 999. Each item should be added to the end of the List. Note: C++ includes a rand() function that returns a number between 0 and RAND_MAX, where RAND_MAX is generally at least 32,767. If you need a number between 0 and n, you can use the % operator as follows:

rand() % n+1

Also, note that you can use the getSize() member function to determine the position of the end of the list (where to insert each item).

Here is some sample code to help you get started on your test program.

#include <cctype>       // Provides toupper
#include <iostream>     // Provides cout and cin
#include <cstdlib>      // Provides EXIT_SUCCESS
using namespace std;
#include "DList.h"  

// PROTOTYPES:
void print_menu( );
// Postcondition: A menu of choices has been printed.

int get_number( );
// Postcondition: The user has been prompted to enter an integer number. The
// number has been read, echoed to the screen, and returned by the function.


int main( )
{
    List test;     // A List to perform tests on
    char choice;   // Command entered by the user
    
    cout << "I have initialized an empty list of integers." << endl;

    do
    {
        print_menu( );
        cout << "Enter choice: ";
        cin >> command; 
        choice = toupper(choice);
        
        switch (choice)
        {
            case 'A': // add code to add n integers to end of list
                      break;
            case 'C': // add code to change the capacity of the list
                      break;
            case 'E': // add code to print result of empty( )
                      break;
            case 'P': // add code to print the list
                      break;
            case 'I': // add code to input an item and position, and insert item into the list
                      break;
            case 'R': // add code to input a position, and erase the item at that position
                      break;     
            case 'Q': cout << "Test program ended." << endl;
                      break;
            default:  cout << choice << " is invalid." << endl;
        }
    }
    while ((choice != 'Q'));

    return EXIT_SUCCESS;
}

void print_menu( )
{
    cout << endl; 
    cout << "The following choices are available: " << endl;
    cout << " A   Add a number of random integers to end of list" << endl;
    cout << " C   Change the capacity of the list using the setCapacity function" << endl;
    cout << " E   Print the result from the empty( ) function" << endl;
    cout << " P   Print a copy of the entire list" << endl;
    cout << " I   Insert a new number with the insert(...) function" << endl;
    cout << " R   Remove a number with the erase( ) function" << endl;
    cout << " Q   Quit this test program" << endl;
}


int get_number( )
// Library facilities used: iostream
{
    int result;
    
    cout << "Please enter an integer number for the list: ";
    cin  >> result;
    cout << result << " has been read." << endl;
    return result;
}

Return to C++ Home Page