Description
In this lab, we will implement hashing ADT. For resolving collisions, you may want to use open addressing with linear probing (i.e. F(i) = i).
-
Input
Your input file consists of three lines.
-
In the first line, your hash table size is given.
-
In the second line, you obtain all the data that should be inserted into the hash table. Obtain a list of numbers from the second line, and execute an insertion operation for each number in order. If a collision happens, print a meesage to notify. Duplicated insertion query will be rejected. Don’t notify when insertion succeeds.
-
In the third line, the numbers are given for checking whether each number is in the hash table or not. For each number, print the message about the availability.
Input.txt
|
30 3 5 35 2 7 18 19 22 5 100 26 8 4 16 5 27 45 67 2 |
2. Hashing ADT
(1) Data Specification for the hash table
typedef int ElementType;
struct HashTable{
int TableSize;
};
(2) functions
void Insert (ElementType Key, struct HashTable *H)
-
print an error message when a duplicated key is insert (request will be rejected)
-
print a message when a collision occurs
-
do NOT print any message when insertion succeeds
-
collision resolution methods are given at the top of the lecture note
int find(struct HashTable *H, ElementType value)
//will return non zero value when succeed to find. If not, return 0.
3. Program description
-
name : p11.c
-
input : a list of operations in a file (an input file name is given as a command line argument. See the example in “1. input” on the first page)
-
output : the corresponding result in the standard output
Submit to the course gitlab your source code. ( ~2020/6/4 23:59 )
