Description

This exercise is to be completed during your week 8 laboratory class. When you complete the exercise show your work to your lab tutor to have your work marked. The marking is based mainly on correct implementation and code readability. You should implement your code in one file (e.g. ex5.cpp, ex5.c, ex5.java). Make sure your program has a header comment block accontaining the name of the exercise, your name and your student login (e.g. jfk01). You may implement your solution in C, C++, Java or Python.

For this exercise, you are to implement a simple hash table. Your program should prompt for the name of an input file and the read and process the data contained in the file.

The file contains a sequence of integer values. Read them and construct a hash table using chaining. For this exercise, you should use linked lists implemented with dynamic data, as shown below

Your program should read each integer in turn and calculate its hash value using mod 100 as the hashing function. Thus, if the key is k, the hash value h(k) = k mod 100.

When you have finished calculate and print:

1. The number of empty entries in the hash table.
2. The length of the longest chain.

As usual, do not use STL or equivalent. Page 2 has pseudo code of some algorithms you might use.

When you are finished, test your program using the provided text file named “ex5.txt” and show your code and the output to your lab tutor to receive your mark. Also, submit your file via unix (banshee) using the submit command below.

$ submit -u login -c CSCI203 –a ex5 filename

where ‘login‘ is your UNIX login ID and ‘filename’ is the name of your file.

If you are unable to attend your lab class and demonstrate your work on time due to circumstances beyond your control (e.g. sickness), contact your lecturer  to request an extension.

1

Pseudo Code

insert( int key, int value )

   create newNode, assign value to it,     set newNode.next to null    if hashTable[key] is NULL then         hashTable[key] = newNode    else         Node^ currentNode = hashTable[key]         while currentNode.next != NULL             currentNode = currentNode.next         end while         currentNode.next = newNode    end if  end insert()

int hashFunction( int value )

      calculate hashKey from value     return hashKey

end hashFunction()

main()     try to open input file,   print error & exit if file not found

      initise hash table

      while file has more data…

            get hash key from hash function         insert value into hashTable at key

      end while       print nubmer of empty entries and collisions

end main()

2