Suppose you are implementing a dynamic set of student records as a hash table. E
ID: 3853513 • Letter: S
Question
Suppose you are implementing a dynamic set of student records as a hash table. Each record has an integer key. Key can have values from 0 through 65,536 and no two records can have the same key values. In addition to the key, each record has following information.
Name:
GPA:
Academic level:
Even though the key can take a value between 0 and 65536, this university can have max 10000 students at a given time.
Hash Table Implementation Details: Assume that the hash key is k mod m and using chaining in case of a collision. Also, the size (m) of the hash table is 1000. Also, you can assume that keys for student are generated using a random uniform distribution function.
Write a C or C++ program that Implements the hash table construction for the above scenario and then implement the following three functions
a) INSERT(T, x) // insert the student record x to the table
b) DELETE(T, x) // delete the student record x from the table
c) SEARCH(T, k) //search key k in the hash table
C Wil N Do wssystem 32cmd.exe ash Table Implementation 3EasEEaaaszs3ss3Es 1. Insert a Record (user enters the name, GPA, Academic level, Key (Key should be between e 65536 2. Search the table (user enter a key for search) Key should be between -65536 Delete a record (user enter a key of the decord to be deleted) enter your choice Press any key to continue .Explanation / Answer
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct hash *hashTable = NULL;
int eleCount = 0;
truct node {
int key, age;
char name[100];
struct node *next;
};
struct hash {
struct node *head;
int count;
};
struct node * createNode(int key, char *name, int age) {
struct node *newnode;
newnode = (struct node *) malloc(sizeof(struct node));
newnode->key = key;
newnode->age = age;
strcpy(newnode->name, name);
newnode->next = NULL;
return newnode;
void insertToHash(int key, char *name, int age) {
int hashIndex = key % eleCount;
struct node *newnode = createNode(key, name, age);
/* head of list for the bucket with index "hashIndex" */
if (!hashTable[hashIndex].head) {
hashTable[hashIndex].head = newnode;
hashTable[hashIndex].count = 1;
return;
}
/* adding new node to the list */
newnode->next = (hashTable[hashIndex].head);
/*
* update the head of the list and no of
* nodes in the current bucket
*/
hashTable[hashIndex].head = newnode;
hashTable[hashIndex].count++;
return;
}
void deleteFromHash(int key) {
/* find the bucket using hash index */
int hashIndex = key % eleCount, flag = 0;
struct node *temp, *myNode;
/* get the list head from current bucket */
myNode = hashTable[hashIndex].head;
if (!myNode) {
printf("Given data is not present in hash Table!! ");
return;
}
temp = myNode;
while (myNode != NULL) {
/* delete the node with given key */
if (myNode->key == key) {
flag = 1;
if (myNode == hashTable[hashIndex].head)
hashTable[hashIndex].head = myNode->next;
else
temp->next = myNode->next;
hashTable[hashIndex].count--;
free(myNode);
break;
}
temp = myNode;
myNode = myNode->next;
}
if (flag)
printf("Data deleted successfully from Hash Table ");
else
printf("Given data is not present in hash Table!!!! ");
return;
}
void searchInHash(int key) {
int hashIndex = key % eleCount, flag = 0;
struct node *myNode;
myNode = hashTable[hashIndex].head;
if (!myNode) {
printf("Search element unavailable in hash table ");
return;
}
while (myNode != NULL) {
if (myNode->key == key) {
printf("VoterID : %d ", myNode->key);
printf("Name : %s ", myNode->name);
printf("Age : %d ", myNode->age);
flag = 1;
break;
}
myNode = myNode->next;
}
if (!flag)
printf("Search element unavailable in hash table ");
return;
}
void display() {
struct node *myNode;
int i;
for (i = 0; i < eleCount; i++) {
if (hashTable[i].count == 0)
continue;
myNode = hashTable[i].head;
if (!myNode)
continue;
printf(" Data at index %d in Hash Table: ", i);
printf("VoterID Name Age ");
printf("-------------------------------- ");
while (myNode != NULL) {
printf("%-12d", myNode->key);
printf("%-15s", myNode->name);
printf("%d ", myNode->age);
myNode = myNode->next;
}
}
return;
}
int main() {
int n, ch, key, age;
char name[100];
printf("Enter the number of elements:");
scanf("%d", &n);
eleCount = n;
/* create hash table with "n" no of buckets */
hashTable = (struct hash *) calloc(n, sizeof(struct hash));
while (1) {
printf(" 1. Insertion 2. Deletion ");
printf("3. Searching 4. Display 5. Exit ");
printf("Enter your choice:");
scanf("%d", &ch);
switch (ch) {
case 1:
printf("Enter the key value:");
scanf("%d", &key);
getchar();
printf("Name:");
fgets(name, 100, stdin);
name[strlen(name) - 1] = '';
printf("Age:");
scanf("%d", &age);
/*inserting new node to hash table */
insertToHash(key, name, age);
break;
case 2:
printf("Enter the key to perform deletion:");
scanf("%d", &key);
/* delete node with "key" from hash table */
deleteFromHash(key);
break;
case 3:
printf("Enter the key to search:");
scanf("%d", &key);
searchInHash(key);
break;
case 4:
display();
break;
case 5:
exit(0);
default:
printf("U have entered wrong option!! ");
break;
}
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.