Demo (Practice) Program Topics (and date due)

8/31 Array use, stream I/O (both cin and cout), and switch statement

9/9 C++ class with a ctor, public function, and private function

9/14 Class template and regular (non-class) function template 

9/21 Dynamic storage allocation, exception handling, and istringstream

9/28 Add, remove, and display numerical values in an STL Vector

10/5 Doubly-linked list

10/12 Recursive function

10/19 Dense (array-based) stack implementation

10/26 Linked queue implementation

11/2 Binary search or hash table (both for make-up credit)

11/9 Quicksort

11/16 Binary tree creation and traversal

11/23 Storage & retrieval tree

11/30 Weighted graph short path algorithm 

The practice programs are intended to make sure that the students use the material from class as soon as possible and to encourage experimentation with the topic. Practice programs do not have to be extremely useful or well-written, but they need to be done on time. They will receive full credit if they cover all the topics specified and are turned in on time, otherwise no credit will be counted; it is all or nothing for grading. For each practice program, just hand in the source code. You can miss 3 and still get the maximum points allowed.

Instructions concerning major programs:

The major programs will be graded on programming style as well as functionality and meeting the requirement specifications. For each program, hand in the C++ source code ( .h and .cpp files), sample output from test runs, and executable (.exe). The executable must be able to run on the lab computers! Use descriptive names for the files. Include your name and the date in the header comments for each source code file. Split source code into appropriate modular files (usually a .h file for each independent class, a .cpp file per class for the implementation code for the member functions, and a .cpp file for the main "driver" program). You may submit your programs online or on CD.

Use good style in your programs including: header block comments for each program, class, and function; additional comment lines to describe sections of functions and subtle design features; indenting to show structure of logic and data; descriptive identifiers; effective use of white space; efficient algorithms and implementation methods; defensive programming to prevent errors.

Major Program 1

Write a C++ program that implements an ADT class named Complex for manipulating complex numbers (with real and imaginary parts; each can have a decimal fraction). The operators provided on this type must include: sum (+), difference (-), product (*), division (/), output (<<), and input (>>) of values for Complex objects. Allow for positive and negative Real and Imaginary parts.  The input (>>) operation must allow values formatted like 16.3 +25.44i, -27.456 (no imaginary part), and 256.4i (no real part) to be entered.  Do not prompt the user for input in the ADT, that should only be done in the application code that uses the ADT class. Use the class in a program that gives the user the ability to enter data and perform each of the calculations. The operator overloading you provide must support expressions like:

  C3 =C1+ C2; //each variable is of type Complex

cout << "results:" << C4 << " & " << C5 << endl; {might print -- results: 27.60i & 36.43-2.78i}

Bonus credit will be given for properly "throwing" an "exception" if division by zero is attempted.

Major Program 2

Write a C++ class template (named GenLookup) to implement a generic look-up list class. The elements of the lists may be instantiated to any simple data type or to string type. The lists must be implemented by your own singly-linked list implementation for which you keep a pointer only to the start (Head) of the list. New items will always be added at the start of the list. The operations you must provide will be used as:

MyListl.Add(ElementVal); // add item to this list

MyList2.Remove( ElementVal); // get an item off this list

Element* Ptr = MyList2.Find( ElementVal); // get a pointer to the data field on this list (or null if not found)

Write a driver program that will create multiple lists (including numeric and string types) and allow the user to add, remove, and find data on each, with output to show the operations performed and values added, removed, or found. Throw an exception in Remove if the item is not on the list. Catch and handle this exception in the driver program.

Make sure your sample output shows that you have instantiated multiple lists with different kinds of elements (including string) and verified the behaviors for each list. 

Major Program 3
Write a C++ program that loads an unspecified number of multi-word strings from a file to a linked list, creates a dynamic (allocated using new) array of strings of the exact size needed (dynamically allocated using new), moves or copies the strings to the array from the list while emptying the list, sorts the array, displays the resulting sequence of strings, and then allows the user to repeatedly search for any particular string using a binary search (reporting its position or that it was not found).  The sorting and searching should be handled by independent programmer-defined functions that will work for any array of strings passed in as an argument (along with the size of the array; also the search value for the search function).

Since we have not covered sorting yet, you can look ahead in the book, look on the Internet for a sort function, or use this link to a Bubble Sort implementation. Cite your source if the sort function is not your own code.

Major Program 4

Write a C++ program using a linked implementation of a binary tree to help sort a list of integer numbers. Organize them onto the tree using the rule that we talked about in class for storage and retrieval (smaller left, larger or equal right), then output them using a recursive function implementing the LNR-recursive (in-order) scan and using a function pointer or functor (function object) argument to determine the processing (printing out, for this case). 

Make sure that it works correctly for any number of inputs (one or more). Include duplicate inputs in your testing: if three values of 47 are entered, the output should produce three of those.