CS 102 LAB 6 Virtual Functions and Data Structures

Introduction:

This lab will give you the opportunity to write work with both virtual functions and data structures.

The important concepts in this lab.

• A second opportunity to design your own class interactions and generating your own UML for that design.
• Use virtual functions
• Work with simple data structures like linked lists and queues.
  

Preparation:

Lab Tasks:

First read the specifications for the project given below. Then think about a good solution. The specification still spell out (some of ) the classes required, so you don't have complete freedom, but you once again have more design freedom than in previous labs

Once you have a design in mind, visualize that design and the relationships between the classes using UML. The UML, along with a brief description of what each function listed in the uml will do, is due by Tuesday Dec 7th in class. Print out your uml and bring it to class.. If you are way off, you will hear back by the end of the day.

Specification for the project:

At a high level:

In this project you will write a program that reads in input from a user adds it to two different data structures, one a queue and one an ordered linked list. When the user is finished entering as much data as desired, your progrm should remove all of the data from each data structure, printing it out as it goes

for example:

please enter your data, enter a blank line when done:

<data entry>

The queue contains:

<FIFO display here>

the ordered linked list contains:

<output ordered by data value here>

Your solution needs to conform to some additional requirements:

1. Your ordered linked list class and your queue class must both derive from a linked list class that you write.
2. You must only use variables of type pointer to linked list (pointer to your base class) to refer to your data structures, you may not have any variables that are of your ordered linked list or queue classes.
3. You must also have the following virtual functions in each of your three classes.
   1. void add(<type> newItem)
   2. <type> remove()
4. In the above <type> is whatever data type you decide to use in your solution.
5. You can add any other methods, virtual or otherwise that help you with your solution so long as those methods do nothing that would defeat the definition of the data structure (a function that allowed looking at any data other than the first item in a queue for example would not be acceptable.)

Specifics for the required functions:

The two virtual functions should of course do different things for different classes.

In the base class, add and remove can add and remove in whatever way is appropriate for a linked list - simply remember to add this into the readme file.

in the Queue class, add should add the new item to the end of the queue. Remove should remove and return the item at the beginning of the queue.

In the ordered linked list class add must insert the new object into the appropriate place in the list (so that all items are still ordered), remove should remove and return the first element in the list.

When you have your design sketched out, produce the UML for the design.

Beginning your Coding:

Because you are designing this solution largely yourself, you are encouraged to find your own best beginning point for writing your code. However, your UML is an excellent place to start. Choose one of the classes in the UML, and write the header file for that class from the UML.

when you are done, write the readme.

Submitting:

What to submit:

• Your name
• the name of each header/cpp file combo that you are turning in and the class it implements.
• how to run your program.
• What implementation decisions you made
• If there is anything missing, incomplete or any bugs in your program

When you are ready to submit, zip up your lab6 directory. Go to your home directory and do the following.

zip -r Lab6Solution.zip lab6
and submit it.

(best way is probably email, in which case you can ftp your zip file to your webhost (w:) drive and submit it as an attachement.

Due Date:

UML and function descriptions due at the beginning of class Dec 7th.

The rest of the lab is

Due By Midnight Tuesday Dec 14th.