Data Structure and Algorithm

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

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

int main()
{
int size,key,n,address,*arr,temp;
cout << "Collision Resolution Technique : Linear Probing,";
cout << "\nThe Hash Function is Key%TableSize.";
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++)
  {
   cin >> key;
   address = key%size;
   cout << "\nH(" << key << '%' << size << ") = " << address;
   if(arr[address] == -1)
    arr[address] = key;
   else
    {
     while(arr[address] != -1)
     {
      cout << "\t(Collision occurs, Rehash required)\n";
      temp = address;
      address = address + 1;
      if(address == size)
        address = 0;
      cout << "  H' = " << temp << "+1 = " << address;
     }
     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 : Linear Probing,
The Hash Function is Key%TableSize.

Enter Table Size : 13

How Many Items? 11

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

H(25%13) = 12
H(46%13) = 7
H(75%13) = 10
H(29%13) = 3
H(36%13) = 10    (Collision occurs, Rehash required)
  H' = 10+1 = 11
H(53%13) = 1
H(68%13) = 3    (Collision occurs, Rehash required)
  H' = 3+1 = 4
H(89%13) = 11    (Collision occurs, Rehash required)
  H' = 11+1 = 12    (Collision occurs, Rehash required)
  H' = 12+1 = 0

H(117%13) = 0    (Collision occurs, Rehash required)
  H' = 0+1 = 1  (Collision occurs, Rehash required)
  H' = 1+1 = 2
H(120%13) = 3    (Collision occurs, Rehash required)
  H' = 3+1 = 4  (Collision occurs, Rehash required)
  H' = 4+1 = 5
H(140%13) = 10    (Collision occurs, Rehash required)
  H' = 10+1 = 11    (Collision occurs, Rehash required)
  H' = 11+1 = 12    (Collision occurs, Rehash required)
  H' = 12+1 = 0     (Collision occurs, Rehash required)

    H' = 0+1 = 1    (Collision occurs, Rehash required)
  H' = 1+1 = 2    (Collision occurs, Rehash required)
  H' = 2+1 = 3    (Collision occurs, Rehash required)
  H' = 3+1 = 4    (Collision occurs, Rehash required)
  H' = 4+1 = 5    (Collision occurs, Rehash required)
  H' = 5+1 = 6

Hash Table 

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

Download Original File

Linear Probing.cpp