*********************************************************
Step 1.1 Examine and understand the DateLinkedList class for managing dates:
Please download and
unzip this DateLinkedList zipped project to get the Visual
Stidio.
·
DateType.h is the same as the DateType.h in your programming #2, which specifies the
logical interface of DateType
class.
·
DateType.cpp is the same as the DateType.cpp in your programming #2 that implements the member functions of the DateType
class.
·
DateLinkedList.h specifies the interface of the DateLinkedList class.
·
DateLinkedList.cpp implements the details of the member functions of the DateLinkedList class.
·
DateMain.cpp contains the main function in it to provide a user menu for
managing dates stored in a linked list. One of the options in the menu allows
the user to experience the amount of time needed to insert n random dates into and then delete n random dates from a linked list.
Compare it with the simple integer linked list zipped project in reading #8 regarding the implementation of a simple linked list class for managing integers. In particular, please carefully compare LinkedList.h and LinkedList.cpp in the simple List class with DateLinkedList.h and DateLinkedList.cpp to see how the original List class is revised to create the DateLinkedList class by incorporating DateType objects of the DateType class you developed for Programming#2 into the definition and implementation (i.e. definition) of the DateLinkedList class.
Step 1.2. Measure the performance of the DateLinkedList class for managing dates:
·
Run the DateLinkedList C++ project and use your watch to measure
the amount of time it takes to insert n random dates into and then delete n random dates from a unsorted linked list for
different values of n from small to
very large, say up to 100,000 or higher.
Report your findings in both the self-evaluation report of this programming
assignment and the weekly progress report.
·
Run the DateLinkedList C++ project and use your watch to measure
the amount of time it takes to insert n random dates into and then delete n random dates from a sorted linked list for
different values of n from small to
very large, say up to 100,000 or higher.
Report your findings in both the self-evaluation report of this programming
assignment and the weekly progress report.
*********************************************************
Step 2.1. Implement a Tree class for managing dates:
Your task here is to (i) implement a new DateTree class for storing date information by revising the Tree class in the following simple Tree C++ project regarding the implementation of a simple binary search tree class for storing integers, and (ii) create a DateTree project similar to DateLinkedList project in step 2.1 with the following structure:
·
DateType.h is the same as the DateType.h in your programming #2, which specifies the
logical interface of DateType
class.
·
DateType.cpp is the same as the DateType.cpp in your programming #2 that implements the member functions of the DateType
class.
· DateTree.h specifies the interface of the Tree class. You should modify the TreeNode class and the Tree class so that the Tree class can store date information as DateType objects, instead of integers. Also you should add a Clear method into the Tree class so that you can call the method to clear a Tree object into an empty tree, just like in the DateLinkedList class we can call the Clear method to empty the whole linked list.
·
DateTree.cpp implements the additional details of
the member functions of the Tree class so that the Tree
class can store date information as DateType objects in the trees, as specified in DateTree.h. In parcular, you should
implement the Clear method of the
Tree class by (i)
calling DeleteCompleteTree(Root)
to empty the tree by systematically deleting the nodes from the tree to free
the memory storage, and then (ii)
set Root to be a null pointer, i.e “Root=NULL;”.
·
DateMain.cpp should have the main function in it to provide a user menu for
managing dates stored in a binary search
tree, just similar to what you see in the main function in DateMain.cpp for the DateLinkedList
zipped project in Step 1. One of the
options in the menu allows the user to experience the amount of time needed to
insert n random dates into and then
delete n random dates from a binary
search tree (i.e. a DateTree object).
Step 2.2. Measure the performance of the DateTree class for managing dates:
·
Run the DateTree C++ project and measure the amount of time it
takes to insert n
random dates into and then delete n random
dates from a binary search tree for different values of n from small to very large, say up to 100,000 or higher. Report
your findings in both the self-evaluation report of this programming assignment
and the weekly progress report.
Submit
your work
Submit all
your source code files (.cpp and .h files) for Step 2
and the self-evaluation report (include
your observations of time in the performance experiments above into the
self-evaluation report also) to the TA.