program to store students information using linear hashing with linked list in c++

[monalisa mohanty]

please help me to complete the below written c++ program code. i have witten the code to insert student's information(case:1) and display it using linked list(case:5). Help me to write the code for case:2 -to count the no. of collisions in the hash table, case:3 -to show the values of hash table, case:4 -to search a value using the hash table. use roll no of the student to be stored in hash table using double linked list.

#include <iostream.h>
#include<conio.h>

struct node
{ char name[20]; // Name of up to 20 letters
int roll;
char branch[20];
node *nxt;// Pointer to next node
};

node *start_ptr = NULL;
node *current; // Used to move along the list
int option = 0;

void insert()
{ node *temp, *temp2; // Temporary pointers

// Reserve space for new node and fill it with data
temp = new node;
cout << "Please enter the name : ";
cin >> temp->name;
cout << "Please enter the roll : ";
cin >> temp->roll;
cout << "Please enter the branch : ";
cin >> temp->branch;
temp->nxt = NULL;

// Set up link to this node
if (start_ptr == NULL)
{ start_ptr = temp;
current = start_ptr;
}
else
{ temp2 = start_ptr;
// We know this is not NULL - list not empty!
while (temp2->nxt != NULL)
{ temp2 = temp2->nxt;
// Move to next link in chain
}
temp2->nxt = temp;
}
}

void display()
{ node *temp;
temp = start_ptr;
cout << endl;
if (temp == NULL)
cout << "The list is empty!" << endl;
else
{ while (temp != NULL)
{ // Display details for what temp points to
cout<<"\nROLL\tNAME\tBRANCH\n";
cout <<temp->name <<"\t" << temp->roll <<"\t"<< temp->branch<<"\n";
temp = temp->nxt;

}
}
}
int main()
{
int c=0;
clrscr();
do
{
cout<<"\n****************PROJECT****************** ";
cout<<"\n0 : exit";
cout<<"\n1 : Insert into the table";
cout<<"\n2 : count no. of collisions";
cout<<"\n3 : show values";
cout<<"\n4 : search a value";
cout<<"\n5 : show all records";
cout<<"\nenter your choice";
cin>>c;


switch(c)
{
case 0:
cout<<"\n0";
break;

case 1:
cout<<"\nenter students info"<<endl;
insert();
break;

case 2:
cout<<"\n2";
break;

case 3:
cout<<"\n3";
break;

case 4:
cout<<"\n4";
break;

case 5:
cout<<"\nstudent's info:";
display();
break;

default:
cout<<"\nWRONG CHOICE";
}
} while(c!=0);


return 0;

}

[weaknessforcats]

It looks like you are after a thing called a chain-link table. Here you hash a a key to get a value.

Then you create a node for a linked list and out the key in the node. Then put the address of the node in the array.
Let's say you allow 100 values. The address of a node whose key has a hash value of 34 would go in array[34].

You start by initializing the array elements to 0. You can assign a node address to an array element if the element is currently 0. Otherwise, you have a collision.

On collisions you can a) report the collision an do nothing or b) add the address of the new node as the "next" node in a linked list. So if you hash 34 again, you go to array[34] to get the first node and add the new node and the "next" node for the linked list starting a array[34].

There is a good explanation for this in Algorithms in C++ by Robert Sedgewick.

You logic should look like:

1) hash the key.
2) create a node with the key
3) if the hash array element for the has value is 0 then assing the address of the node to the4 array element corresponding to the hash value. Otherwise, add the new node as the "next" node for that array element.