instructions

 

Sequences: The Sequel!

Step 1 – Take your sequence class from Assignment 1 and update it to use a template parameter to determine what type of data to hold. Keep in mind that this will likely require you to implement some of your class member functions (and maybe some nonmember functions) as template functions, which will require them to be implemented in the header file. To solve this problem, create a file called sequence.template and define the necessary functions there. (All other functions should continue to be implemented in sequence.cpp.)

Step 2 – Referencing the dynamic array example code from Lecture 5 if necessary, rewrite your templated sequence class from Step 1 to use a dynamic array for data storage. Save the resulting files as “sequence_dynamic[.h, .cpp, .template]”.

Step 3 – Extending your previous work on the node class in Lab 3, rewrite your node class to use a template parameter to determine what type of data it will store. (Figure 6.4 in Main and Savitch might be helpful here.) Save the resulting files as “node[.h, .cpp, .template]”.

Step 4 – Lightly modify your class from Step 3 to implement a templated _doubly_ linked list. Save the resulting files as “node_doubly_linked[.h, .cpp, .template]”.

Step 5 – Create a templated sequence class using a linked list for data storage. (This means using the templated node class.) Save the required files as “sequence_linked_list[.h, .cpp, .template]”.

Step 6 – Finally, modify your work from step 5 to implement the templated sequence class using a doubly-linked list. Save the resulting files as “sequence_doubly_linked[.h, .cpp, .template]”.

Step 7: Now that you’ve written all of your code, I’d like you to go back and indicate the Big-O complexity class of each function in each implementation. A short one-line comment (for example, “// O(n)”) before each function is sufficient.

Step 8:  You will need to test the core functionaliy of each class. (don’t worry, tests should largelt be reusable between implementations of a given class.) Whether you submit a single test file for all classes, or one for each class, is up to you.

*To be clear you will ultimately implement, analyze, and test 6 classes here:

— 4 different sequence classes

— 2 different node classes

* Note that you may now always have a resulting *.cpp implementation file for some templated classes. Your entire implementation might rightfully end up in the *.template file.

Once you are ready to submit everything, zip all *.h, *.template, and *.cpp files (including test files) into a single zip file and upload that file through Canvas.