Data Structure and Algorithm

/***********************************************
APPLICATION : Collision Resolution Technique : Quadratic Probing
CODED BY    : Ankit Pokhrel
COMPILED ON : Borland C++ Ver 5.02
DATE         : 2010 - October - 22
************************************************/

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

int main()
{
int size,key,n,address,*arr,temp;
cout << "Collision Resolution Technique : Quadratic Probing,";
cout << "\nThe Hash Function is Key%TableSize,";
cout << "\nThe Table Size must be atleast two times the Total Numbers.";
cout << "\n\nEnter Table Size : ";
cin >> size;
arr = new int[size];
for(int i = 0;i < size;i++)
  arr[i] = -1;

cout << endl << "How Many Items? ";
cin >> n;
cout << endl << "Enter " << n << " Keys\n";

for(int i = 0;i < n;i++)
  {
   int j = 1;
   cin >> key;
   address = key%size;
   cout << "\nH(" << key << '%' << size << ") = " << address;
   temp = address;
   if(arr[address] == -1)
    arr[address] = key;
   else
    {
     while(arr[temp] != -1)
     {
      cout << "\t(Collision occurs, Rehash required)\n";
      temp = address + (j*j);
      if(temp >= size)
       temp = temp - size;
      cout << "  H' = " << address << '+' << (j*j) << " = " << temp;
      j++;
     }
     address = temp;
     arr[address] = key;
    }
  }

cout << "\n\nHash Table\n";
cout << "----------";
cout << endl << endl;
for(int i = 0;i < size;i++)
  {
   if(arr[i] != -1)
    cout << i << '\t' << arr[i] << endl;
   else
    cout << i << '\t' << endl;
  }

getch();
return 0;
}

OUTPUT

Collision Resolution Technique : Quadratic Probing,
The Hash Function is Key%TableSize,
The Table Size must be atleast two times the Total Numbers.

Enter Table Size : 18

How Many Items? 11

Enter 11 Keys
25 46 75 29 36 53 68 89 117 120 140

H(25%18) = 7
H(46%18) = 10
H(75%18) = 3   
H(29%18) = 11
H(36%18) = 0   
H(53%18) = 17
H(68%18) = 14   
H(89%18) = 17    (Collision occurs, Rehash required)
  H' = 17+1 = 0    (Collision occurs, Rehash required)
  H' = 17+4 = 3    (Collision occurs, Rehash required)
  H' = 17+9 = 8
H(117%18) = 9 
H(120%18) = 12
H(140%18) = 14    (Collision occurs, Rehash required)
  H' = 14+1 = 15       

Hash Table

0    36
1   
2   
3    75
4   
5   
6   
7    25
8    89
9    117
10    46
11    29
12    120
13   
14    68
15    140
16
17    53

Download Original File