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 Stype page (see link on the main assignments page). 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/
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:
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). -----------------------------------------------------------------------*/
Pseudocode: If newCapacity < current size Set newCapacity to current size If newCapacity is the same as the current capacity Do nothing (return) 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
Then 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.
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 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
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 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; }
Copyright: © 2012 by the Austin Community College
Department of Computer Studies. All rights reserved.
Comments to: Bob Comer
Last updated: November 1, 2012