Friday, 10 November 2017

Write a program in C to implement hash function ( Division method) with two collision resolution techniques (Linear probing & Quadratic probing).

Program Code:
#include <stdio.h>
#include <conio.h>
int tsize;
int hasht(int key) // division method for hashing
{
 int i ;
 i = key%tsize ;
 return i;
}
int rehashl(int key) // Linear probing function
{
 int i ;
 i = (key+1)%tsize ;
 return i ;
}
int rehashq(int key, int j) // Quadratic probing function
{
 int i ;
 i = (key+(j*j))%tsize ;
 return i ;
}
void main()
{
int key,arr[20],hash[20],i,n,s,op,j,k ;
clrscr() ;
printf ("Enter the size of the hash table:  ");
scanf ("%d",&tsize);
printf ("nEnter the number of elements: ");
scanf ("%d",&n);
for (i=0;i<tsize;i++)
hash[i]=-1 ;
printf ("Enter Elements: ");
for (i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
do
{
printf("nn1.Linear Probingn2.Quadratic Probing n3.Exit nEnter your option: ");
scanf("%d",&op);
 switch(op)
 {
 case 1:
for (i=0;i<tsize;i++)
hash[i]=-1 ;
for(k=0;k<n;k++)
{
key=arr[k] ;
i = hasht(key);
while (hash[i]!=-1)
{
i = rehashl(i);
}
hash[i]=key ;
}
printf("nThe elements in the array are: ");
for (i=0;i<tsize;i++)
{
printf("n  Element at position %d: %d",i,hash[i]);
}
break ;

case 2:
for (i=0;i<tsize;i++)
hash[i]=-1 ;
for(k=0;k<n;k++)
{
j=1;
key=arr[k] ;
i = hasht(key);
while (hash[i]!=-1)
{
i = rehashq(i,j);
j++ ;
}
hash[i]=key ;
}
printf("nThe elements in the array are: ");
for (i=0;i<tsize;i++)
{
printf("n Element at position %d: %d",i,hash[i]);
}
break ;
}
}
while(op!=3);
getch() ;
}

Output:
Enter the size of the hash table:  10
Enter the number of elements: 8
Enter Elements: 63 24 27 72 81 101 36 92

1.Linear Probing
2.Quadratic Probing
3.Exit
Enter your option: 2

The elements in the array are: 
 Element at position 0: -1
 Element at position 1: 81
 Element at position 2: 72
 Element at position 3: 63
 Element at position 4: 24
 Element at position 5: 101
 Element at position 6: 36
 Element at position 7: 27
 Element at position 8: 92
 Element at position 9: -1

1.Linear Probing
2.Quadratic Probing
3.Exit
Enter your option: 3


Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput