Lab 5: Template Classes and Hash Tables

CSE109
1
Systems Software
Lab 5: Template Classes and Hash Tables
Lab Objectives
In this activity, students should demonstrate the following abilities:
1. Implement and test linked list and binary search tree template classes
2. Implement and test Hash Table class
3. Compare the three data structure performance for the search operation
Lab Assignment
In this lab, you will implement the three data structures, Linked List, BST, and Hash Table, and
compare the performance of their search operation.
1. Create the class Student as seen in class with the data members id, name, and gpa.
The class has two constructors, getters and setters for every data member, and
overloading operator functions for the following operators: ==, >, <, >>, and <<.
2. Create the template class LinkedList as seen in class.
3. Create the template abstract class Tree and the template class BST that inherits Tree
as seen in class.
4. Create the class HashTable as seen in lecture 10 for the type Student.
5. Modify the search methods in the three classes to return the number of iterations
performed to find, or not, the student record.
6. Write a C++ program that creates two instances of the classes LinkedList and BST
for the type Student and a HashTable object with a capacity equal to 500. The
program reads in the text file students.txt and loads the students’ information in
the linked list, the BST, and the hash table using the insert methods from the three
classes.
7. Create an array of 10 student IDs and initialize it to the following IDs: {91242, 87351,
13385, 55555, 37867, 98296, 22222, 62985, 33333, 48851}
8. Search for each student id, from the list above, in the three data structures. Display the
number of iterations for each search operation as shown in the sample output below.
What are your observations on the performance of the search operation in the three
data structures? If you reduce the size of the hash table to 250, how does the
performance of the search operation compare to that of the linked list and the BST?
CSE109 Lehigh University Summer 2020
2
9. Create a makefile to build the executable of the program.
10. Submit all your files on courseSite as a zipped folder named lab5.
-------------------- Program Output --------------------------
ID HASH LL BST
91242 3 500 1
87351 2 489 6
13385 4 404 9
55555 1 500 12
37867 1 143 12
98296 1 83 10
22222 1 500 9
62985 1 42 13
33333 1 500 8
48851 1 1 14