Third Hash table 10 points In this part you will implement a

Third: Hash table (10 points) In this part, you will implement a hash table containing integers. The hash table has 10,000 buckets. An important part of a hash table is collision resolution. In this assignment, we want you to use chaining with a linked list to handle a collision. This means that if there is a collision at a particular bucket then you will maintain a linked list of all values stored at that bucket. For more information about chaining, s http://research.cs.vt.edu/AVresearch/hashing/openhash.php For this problem, you have to use following hash function: key modulo the number of buckets. Input format: This program takes a file name as argument from the command line. The file is either blank or contains successive lines of input. Each line contains a character, either i\' or \'s\', followed by a tab and then an integer, the same format as in the Second Part. For each of the lines that starts with \'i\', your program should insert that number in the hash table if it is not present If the line starts with a \'s\', your program should search the hash table for that value Output format: For each line in the input file, your program should print the status/result of that operation. For an insert, the program should print \"inserted\" if the value is inserted or duplicate\" if the value is already present. For a search, the program should print \"present\" or \"absent\" based on the outcome of the search. Your program should print \"error\" (and nothing else) if the file does not exist. The program should also print \"error\" for input lines with improper structure Example Execution: Lets assume we have 2 text files with the following contents: \"filel txt\" is empty file2.txt:

Solution

#include #include #include #include #define SIZE 20 struct DataItem { int data; int key; }; struct DataItem* hashArray[SIZE]; struct DataItem* dummyItem; struct DataItem* item; int hashCode(int key) { return key % SIZE; } struct DataItem *search(int key) { //get the hash int hashIndex = hashCode(key); //move in array until an empty while(hashArray[hashIndex] != NULL) { if(hashArray[hashIndex]->key == key) return hashArray[hashIndex]; //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } return NULL; } void insert(int key,int data) { struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem)); item->data = data; item->key = key; //get the hash int hashIndex = hashCode(key); //move in array until an empty or deleted cell while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) { //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } hashArray[hashIndex] = item; } struct DataItem* delete(struct DataItem* item) { int key = item->key; //get the hash int hashIndex = hashCode(key); //move in array until an empty while(hashArray[hashIndex] != NULL) { if(hashArray[hashIndex]->key == key) { struct DataItem* temp = hashArray[hashIndex]; //assign a dummy item at deleted position hashArray[hashIndex] = dummyItem; return temp; } //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } return NULL; } void display() { int i = 0; for(i = 0; ikey,hashArray[i]->data); else printf(\" ~~ \"); } printf(\"\ \"); } int main() { dummyItem = (struct DataItem*) malloc(sizeof(struct DataItem)); dummyItem->data = -1; dummyItem->key = -1; insert(1, 20); insert(2, 70); insert(42, 80); insert(4, 25); insert(12, 44); insert(14, 32); insert(17, 11); insert(13, 78); insert(37, 97); display(); item = search(37); if(item != NULL) { printf(\"Element found: %d\ \", item->data); } else { printf(\"Element not found\ \"); } delete(item); item = search(37); if(item != NULL) { printf(\"Element found: %d\ \", item->data); } else { printf(\"Element not found\ \"); } }