Algorithm to insert a value in quadratic probing
Hashtable is an array of size = TABLE_SIZE
Step 1: Read the value to be inserted, key
Step 2: let i = 0
Step 3: hkey=key%TABLE_SIZE
Step 4: compute the index at which the value has to be inserted in hash table
Step 4: compute the index at which the value has to be inserted in hash table
index = (hkey+ i * i) %
TABLE_SIZE
Step 5: if there is no element at that index then insert the value at index and STOP
Step 6: If there is already an element at that index
step
4.1: i = i+1
step 7: if i <
TABLE_SIZE then go to step 4
Algorithm to search a value in quadratic probing
Hashtable is an array of size = TABLE_SIZE
Step 1: Read the value to be searched, key
Step 2: let i = 0
Step 3: hkey=key%TABLE_SIZE
Step 4: compute the index at which the value can be found
Step 4: compute the index at which the value can be found
index = (hkey + i * i) %
TABLE_SIZE
Step 5: if the
element at that index is same as the search value then print element
found and STOP
Step 6: else
step
4.1: i = i+1
step 7: if i <
TABLE_SIZE then go to step 4
#include <stdio.h>
#include<stdlib.h>
#define TABLE_SIZE 10
int h[TABLE_SIZE]={NULL};
void insert()
{
int key,index,i,flag=0,hkey;
printf("\nenter a value to insert into hash table\n");
scanf("%d",&key);
hkey=key%TABLE_SIZE;
for(i=0;i<TABLE_SIZE;i++)
{
index=(hkey+i*i)%TABLE_SIZE;
if(h[index] == NULL)
{
h[index]=key;
break;
}
}
if(i == TABLE_SIZE)
printf("\nelement cannot be inserted\n");
}
void search()
{
int key,index,i,flag=0,hkey;
printf("\nenter search element\n");
scanf("%d",&key);
hkey=key%TABLE_SIZE;
for(i=0;i<TABLE_SIZE; i++)
{
index=(hkey+i*i)%TABLE_SIZE;
if(h[index]==key)
{
printf("value is found at index %d",index);
break;
}
}
if(i == TABLE_SIZE)
printf("\n value is not found\n");
}
void display()
{
int i;
printf("\nelements in the hash table are \n");
for(i=0;i< TABLE_SIZE; i++)
printf("\nat index %d \t value = %d",i,h[i]);
}
main()
{
int opt,i;
while(1)
{
printf("\nPress 1. Insert\t 2. Display \t3. Search \t4.Exit \n");
scanf("%d",&opt);
switch(opt)
{
case 1:
insert();
break;
case 2:
display();
break;
case 3:
search();
break;
case 4:exit(0);
}
}
}
Output:
Press 1. Insert 2. Display 3. Search 4.Exit
1
enter a value to insert into hash table
12
Press 1. Insert 2. Display 3. Search 4.Exit
1
enter a value to insert into hash table
22
Press 1. Insert 2. Display 3. Search 4.Exit
1
enter a value to insert into hash table
32
Press 1. Insert 2. Display 3. Search 4.Exit
2
elements in the hash table are
at index 0 value = 0
at index 1 value = 0
at index 2 value = 12
at index 3 value = 22
at index 4 value = 0
at index 5 value = 0
at index 6 value = 32
at index 7 value = 0
at index 8 value = 0
at index 9 value = 0
Press 1. Insert 2. Display 3. Search 4.Exit
3
enter search element
22
value is found at index 3
Press 1. Insert 2. Display 3. Search 4.Exit
3
enter search element
123
value is not found
Press 1. Insert 2. Display 3. Search 4.Exit
4