Question

IN C++

Create a student hash table that contains information, studentID (int), name (string), marks_oop345 (float). The size of hash table is equal to the number of students in the class. Use linear probing in case of collisions. Perform insertion, deletion, display and search operations.

Answer 1

Sample Output:

Code to be Copied:

//include required header files
#include<iostream>
#include<string>
using namespace std;
//Declare student record
struct student_record
{
   // structure for storing records
   int studentID;
   string name;
   float marks_oop345;
   //Display the record
   void displayrecord()
   {
       cout << "\nDisplaying search result: " << endl;
       cout << "Student Id = " << this->studentID << endl;
       cout << "Name = " << this->name << endl;
       cout << "Marks =" << this->marks_oop345 << endl;
   }
  
};

//Declare class to hash_node
class hash_node
{
//declare private mebers
public:
   //declare the id as key
   int student_id;
   student_record* value;
   //constructor
   hash_node(int key, student_record * r)
   {
       this->student_id = key;
       value = r;
   }
};

//Declare hash_class
class hashclass
{
   //declare data members
   //for table size and current_size
   int table_size;
   int curr_size;
   //declare pointer nodes
   hash_node ** h;
   hash_node *temp_node;

//member functions
public:
   hashclass(int n)
   {
       //set size to n
       table_size = n;
       curr_size = 0;
       //create hash_node
       h = new hash_node*[table_size];
       //set values to null
       for (int i = 0; i < table_size; i++)
       {
           h[i] = NULL;
       }
       //create a dummy node
       temp_node = new hash_node(-1, NULL);
   }

   //get the hash value
   int gethashcode(int k)
   {
       //apply hash function
       return k % table_size;
   }

   //Implement function to insert the record at
   //hash function code
   void insertion_record(int k, student_record* r)
   {
       //Create hash node
       hash_node* value = new hash_node(k, r);
       //get the index
       int hash_index = gethashcode(k);
       //use hile loop to check whether element is existed
       //at that index or not
       while (h[hash_index] != NULL &&
           h[hash_index]->student_id != k &&
           h[hash_index]->student_id != -1)
       {
           //increment hash size
           ++hash_index;
           // if empty deleted or non key then skip
           hash_index %= table_size;
       }
       //if the index is filled
       if (h[hash_index] == NULL ||
           h[hash_index]->student_id == -1)
       {
           //then increment the index
           //by using linear probing technique
           ++curr_size;
           //set the value
           h[hash_index] = value;
       }
   }
   //Implement the function
   //to delete the student record
   student_record * deleterecord(int delete_id)
   {
       //get the index of the student_id
       int pos = gethashcode(delete_id);
       //finding the hash_node with given key
       while (h[pos] != NULL)
       {
           //if hash_node is found
           if (h[pos]->student_id == delete_id)
           {
               hash_node* t = h[pos];
               //set the temp node
               h[pos] = temp_node;
               //increment current_size
               curr_size--;
               //return deleted value
               return t->value;
           }
           //increment index
           pos++;
           //again get hash code
           pos %= table_size;
       }
       //If not found return null
       return NULL;
   }

   //Implement method search_record
   student_record* search_record(int key)
   {
       // Apply hash function to find index for given key
       int hindex = gethashcode(key);
       int counter = 0;
       //finding the hash_node with given key
       while (h[hindex] != NULL)
       {
           int size = 0;
           //to avoid infinite loop
           if (size++ > table_size)
           {
               return NULL;
           }
           //if hash_node found return its value
           if (h[hindex]->student_id == key)
           {
               return h[hindex]->value;
           }
           //increment index
           hindex++;
           hindex %= table_size;
       }
       return NULL;
   }

   //Implement method to display values
   void display()
   {
       //print message
       cout << "\nDisplaying Hash Table\n";
       //use for-loop to iterate the table
       for (int i = 0; i < table_size; i++)
       {
           if (h[i] != NULL && h[i]->student_id != -1 && h[i]->student_id!=0)
           {
               cout << "Index= " << i
                   << " Student id= " << h[i]->value->studentID;
               cout << " Name= " << h[i]->value->name
                   << " Marks= "
                   << h[i]->value->marks_oop345 << endl;
           }
       }
   }
};

//Implement the method to read the record
student_record *getrecord(int id, string nam, float mar)
{
   //create object for record
   student_record * r = new student_record;
   //if record is null
   //then it is empty
   if (r == NULL)
   {
       cout << "Invalid data";
   }
   r->studentID = id;
   r->name = nam;
   r->marks_oop345 = mar;
   //return record
   return r;
}

//main method
int main()
{
   //declare local variables
   int option,studentID=0;
   float marks_oop345=0.0;
   string name="";
   //create table of size 50
   hashclass obj(50);
   do
   {
       //print menu
       cout << "\nHash Table Operations\n";
       cout << "1. Insertion\n2. Deletion\n3. Search\n4. Exit";
       //prompt and read the option
       cout << "\nEnter the option: ";
       cin >> option;
       //crete student record
       student_record *r = getrecord(studentID, name, marks_oop345);
       if (option == 1)
       {
           obj.insertion_record(r->studentID, r);
           cin.ignore();
           cout << "\nEnter the student name: ";
           getline(cin, name);
           cout << "\nEnter the student Id: ";
           cin >> studentID;
           cout << "\nEnter marks: ";
           cin >> marks_oop345;
           r = getrecord(studentID, name, marks_oop345);
       }
       //Implement else if condition for
       //delete the record
       else if (option == 2)
       {
           //prompt and read the student id
           cout << "Enter the student id to delete: ";
           cin >> studentID;
           //delete the record
           r = obj.deleterecord(studentID);
           //if return parameter is null
           if (r != NULL)
           {
               //display message
               cout << "Record is deleted\n" << endl;
           }
           else
           {
               //record not found
               cout << "Record not found" << endl;
           }
           cout << "After deleting the record: "<<endl;
           obj.display();
       }

       //Implement option for searching the record
       else if (option == 3)
       {
           obj.insertion_record(r->studentID, r);
           //Display records first
           obj.display();
           //prompt and read the id of the student
           cout << "Enter the student id to search: ";
           cin >> studentID;
          
           //search the record
           r = obj.search_record(studentID);
           if (r != NULL)
           {
               cout << "\nRecord found at index: " << obj.gethashcode(r->studentID);
               r->displayrecord();
           }
           else
           {
               cout << "Record not found" << endl;
           }          
       }
   }while(option != 4);
   //exit from the program
   if (option == 4)
   {
       cout << "End of the program....!" << endl;
   }
   return 0;
}