Data Structures Lab BCSL305
PROGRAM 12.
12. Given a File of N employee records with a set K of Keys (4-digit) which uniquely
determine the records in file F. Assume that file F is maintained in memory by a Hash
Table (HT) of m memory locations with L as the set of memory addresses (2-digit) of
locations in HT. Let the keys in K and addresses in L are Integers. Develop a Program
in C that uses Hash function H:
K →L as H(K)=K mod m (remainder method), and implement hashing technique to
map a given key K to the address space L. Resolve the collision (if any) using linear
probing.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct record
{
int empno,flag;// employee number is the key- K with 4
digits char name[10];
}emp[100];
int hash(int m)
{
int r;
r=m%100;
return r;
}
void main()
{
int m,k,eno,loc,i,n,j;
char name[10];
FILE *in;
printf("\nEnter no of records to read from file:
"); scanf("%d",&n);
in = fopen("[Link]", "r");
if(n<=10)
{
for(k=0;k<100;k++)
Department of CSE, KSIT Page 75
Data Structures Lab BCSL305
emp[k].flag=0;
for(i=0;i<n;i++)
{
fscanf(in,"%d%s",&eno,name);
loc=hash(eno);
if(emp[loc].flag==0)
{
printf("\nRecord:%d is mapped to
address:%d\n",i,loc); emp[loc].empno=eno;
emp[loc].flag=1;
strcpy(emp[loc].name,name);
}/* end of inner if*/
else
{
printf("\n\nCollision occured for record %d resolved using
linearprobing\n\n",i);
for(j=loc+1;j<100;j++)
{
if(emp[j].flag==0)
{
printf("\nRecord:%d is at address:%d\n",i,j);
strcpy(emp[j].name,name);
emp[j].empno=eno;
emp[j].flag=1;
break;
}/* end of inner if*/
}/* end of for*/
if(j>=100)
{
printf("HASH TABLE IS FULL\n");
printf("\n ------------------------ \n");
}/* end of if*/
}/* end of inner else*/
}/* end of for*/
fclose(in);
printf("\n\nThe Hash Table Content is: ");
for(i=0;i<100;i++
Department of CSE, KSIT Page 76
Data Structures Lab BCSL305
)
{
if(emp[i].flag==1)
printf("\n%d\t%d\t%s",i,emp[i].empno,emp[i].name);
else
printf("\n####");
}/* end of for*/
}/* end of if*/
else
printf("\nFile is containing only 10 records\n\n");
}/* end of main*/
NOTE: Create a notepat file with name [Link], and
store employee no and name. Save the file in the same
folder as your program folder.
OUTPUT:
Enter no of records to read from file: 10
Record:0 is mapped to address:1 Record:1
is mapped to address:10
Collision occured for record 2 resolved using linearprobing
Record:2 is ataddress:11
Collision occured for record 3 resolved using linearprobing
Record:3 is ataddress:12
Record:4 is mapped to address:36
9999Collision occured for record 5 resolved using linear probing
Record:5 is at address:37
Record:6 is mapped to address:56
Collision occured for record 7 resolved using linear probing
Record:7 is at address:57
Record:8 is mapped to address:66
Record:9 is mapped to address:89
The Hash Table Content is:
Address Empno Name
Department of CSE, KSIT Page 77