Question generated for student with ID 0452422
(Make sure you are doing the right question! :) )
This assignment is about hashing. For all the questions, make sure you are creating linked lists to
resolve collisions. Each student has their own hashing function and their own test data.
There are 5 questions in this assignment, and they are as follows:
1. Write a function that determines how full your hash table is. Express the result as a percentage; i.e. what
percent of the buckets have something in them (other than a 0)? Print the result to the screen.
2. Write a function that finds the longest chain in your hash table. Print this length to the screen.
3. Write a function that calculates the average chain length in your table (don't forget to include chains
of length 0 in your calculation!). Print this length to the screen.
4. Write a function that prints the last element in each chain of your hash table to the screen. This means
you will need to traverse each chain until you reach the end of it, then print the value stored there.
If you encounter an empty bucket, print 0 (see notes below on initializing your hash table).
5. Write a function that prints the positions in your hash table containing exactly three entries. Note that you
are printing the positions, NOT the values stored in the table. (ex. if position 4 in the table has three
entries, your function should output "4").
Your hashing function is: h(x) = x mod 17
Your first data set is:
56 45 52 34 34 85 46 87 32 21 31 51 53 29 17 63 92 84 88 98 39 93 7 68
Your second data set is:
67 45 5 74 41 21 49 52 48 22 37 40 5 92 6 61 14 55 98 56
Your third data set is:
92 55 47 45 93 74 37 76 51 85 46 25 31 48 26 54 14 1 70 31 18 1 77 48 77 82 48 13 49 65 32 12
Additional instructions:
You will need to write a main program which calls your 5 functions as necessary. In this main program, you
will also need to create a hash table with 17 positions, where all buckets initially contain 0's.
Your table should consist of an array of structures of the following form:
struct element {
int value;
element *next;
};
After creating and initializing the hash table, you should hash your first data set into the table, then
call all 5 of your functions. Repeat this process for the other two data sets. Good luck and have fun!