Lab Sheet 10
The first credit will go for an implementation of the class described in Problem 10.1. You will need to update the hash table class that you designed and wrote during the last laboratory. Employ, also, some of what you learnt during the tutorial session on hash tables.
Problem 10.1 A hash table of length 100 is required to store a list of friends' telephone numbers. Each element of the array will contain a string (or character array) to hold the first name, a string (or character array) to hold the number, and a variable to indicate whether the element is empty, used, or deleted. The name will be the key for the hash table; your hash function should simply convert the first character of the name into its corresponding ASCII integer, and use this integer as the index.
Methods you should implement are
Add(), add a name and number to the table
RemoveElement(), delete a single name from the table
GetNumber(), return the number corresponding to a particular name (if present)
CountEmpty(), count the number of empty elements in the table
Print(), print the contents of all non-empty elements to the screen
Show a demonstrator a running version of your program to get a credit. Your second credit goes for Problem 10.2.
Problem 10.2 What is the distribution of used elements in the hash table when 30 (name, number) pairs have been added to the table and 5 have been deleted? To determine this you will need to print out the status of each element to the screen. To get a credit, copy this information into a text file and hand it to a demonstrator. To help you, here is a method called PrintStatus(). (Use your own HASH_TABLE_CLASS, and HASH_ARRAY, and values for SIZE_OF_HASH_TABLE, EMPTY, and USED.)
void HASH_TABLE_CLASS::PrintStatus(){
// print the status of each element (whether it is empty, used, or deleted)
int count;
cout << endl << "Here is the table:" << endl;
count = 0;
while (count < SIZE_OF_HASH_TABLE) {
if (HASH_ARRAY[count].status == EMPTY) {
cout << '.';
} else if (HASH_ARRAY[count].status == USED) {
cout << 'O';
} else {
// must be a deleted element
cout << 'X';
}
count++;
}
}
So, run your program, adding any 30 names to the hash table. Then delete any five of those. Next run PrintStatus() and copy the output to a text file.
Your handup should contain a list of 30 first names, a copied printout of the hash table status, and your name, your lab, and today's date. Demonstrators will show you how to copy text from a DOS terminal window into a text document if you do not know how. You will be given a credit as soon as you hand it up.
For advanced students: What do you notice about this distribution? If you increased the size of the hash table to 300, how would your distribution change? Can you suggest improvements to your hash function?
End of Lab Sheet
