COSC 2415 - Data Structures and
ITSE 2445 Data Structures
Bob Comer, Professor of Computer Studies
Program 2 - List Class with a Dynamic Array
Be sure to read through Section 6.3 in your textbook before starting this assignment. Implement a List class that uses a dynamic array to store the items in a list. Your list class will include the ability to "grow" when it becomes full, as described below. For background information, refer to Section 6.3 of your text book, An Array-Based Implementation of Lists with Dynamic Allocation, and the first solution to Deficiency #1 on page 85.
Start with the List class from Figure 6.2 on pages 270 - 274 of your book. You can download the code here:
http://cs.calvin.edu/activities/books/c++/ds/2e/SourcePrograms/
Add a public function member called resize( ) as follows:
/***** resize operation *****/ void resize( int newCapacity); /*---------------------------------------------------------------------- Change the capacity of a 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). -----------------------------------------------------------------------*/
void List::resize( int newCapacity ) { ElementType *largerArray; if (newCapacity < mySize) newCapacity = mySize; // Don’t allocate less than currently used if (newCapacity == myCapacity) return; // Allocated memory is already the correct size largerArray = new ElementType[newCapacity]; for ( int i=0; i<mySize; i++ ) largerArray[i] = myArray[i]; delete [ ] myArray; myArray = largerArray; myCapacity = newCapacity; }
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 resize( ) and then perform the insertion.
Be sure to update your class documentation as required.
Test your class using a list of integers. I want you to use a menu-driven program for testing where the user can specify which command to test and the data to store in the list. 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 #include "DList.h" using namespace std; // 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 '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 << " C Change the capacity of the list using resize( )" << 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; } char get_user_command( ) // Library facilities used: iostream { char command; cout << "Enter choice: "; cin >> command; // Input of characters skips blanks and newline character return command; } 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; }