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

Quadratic Probing.cpp

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

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

int main()
{
int tb_size,size,resize,key,n,address,*arr,temp;
cout << "Collision Resolution Technique : Double Hashing,";
cout << "\nThe Hash Function is Key%H1_Size and Key%H2_Size,";
cout << "\nThe Table Size must be atleast two times H1_Size and H2_size.";
cout << "\n\nEnter Table Size : ";
cin >> tb_size;
arr = new int[tb_size];
for(int i = 0;i < tb_size;i++)
  arr[i] = -1;
cout << "\nEnter Size for First Hash Function (H1_Size) : ";
cin >> size;
cout << "\nEnter Size for Second Hash Function(H2_Size) : ";
cin >> resize;

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;
   if(arr[address] == -1)
    arr[address] = key;
   else
    {
     int h = key%resize; //Calculate address using second Hash Function
     temp = address;
     while(arr[temp] != -1)
     {
      cout << "\t(Collision occurs, Rehash required)\n";
      temp = address + j*h; //find address
      cout << "  H' = " << address << '+' << (j*h) << " = " << temp;
      if(temp >= size)
       temp = temp - size;
      j++;
     }
     address = temp;
     arr[address] = key; //insert key
    }
  }

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

getch();
return 0;
}

OUTPUT

Collision Resolution Technique : Double Hashing,
The Hash Function is Key%H1_Size and Key%H2_Size,
The Table Size must be atleast two times H1_Size and H2_Size.

Enter Table Size : 25

Enter Size for First Hash Fucntion (H1_Size) : 13

Enter Size for Second Hash Fucntion (H2_Size) : 11

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+3 = 13
H(53%13) = 1
H(68%13) = 3    (Collision occurs, Rehash required)
  H' = 3+2 = 5
H(89%13) = 11
H(117%13) = 0 
H(120%13) = 3    (Collision occurs, Rehash required)
  H' = 3+10 = 13  (Collision occurs, Rehash required)
  H' = 3+20 = 23 
H(140%13) = 10    (Collision occurs, Rehash required)
  H' = 10+8 = 18   

Hash Table

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

Download Original File

Double Hashing.cpp

/*********************************************
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

/************************************************
APPLICATION : Program to Implement Hashing by Chaining Method
CODED BY    : Ankit Pokhrel
COMPILED ON : Borland C++ Ver 5.02
DATE         : 2010 - October - 20
*************************************************/

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

struct Node
{
int data,index;
struct Node *next;
struct Chain *ch,*top;
};

struct Chain
{
int data;
struct Chain *next;
};

typedef Node node;
typedef Chain chain;

node *New,*top;
void create() //function to create a node
{
New = new node;
New -> next = NULL;
New -> ch = NULL;
New -> top = NULL;
}

void insert(node *&n,int Item)
{
if(n == NULL) //if first node
  {
   n = new node; //create a node
   n -> data = Item; //copy item
   n -> index = 0; //set index
   n -> next = NULL; //initialize next
   top = n; //update top
   return;
  }

static int i = 0;
create(); //create a new node
New -> data = Item; //copy item
New -> index = ++i; //update index
top -> next = New; //insert new node
top = New; //update top
}

void Link(node *&n,int loc,int Item)
{
node *temp = n;
while(temp -> index != loc) //goto location
  temp = temp -> next;

chain *c;
c = new chain; //create a node
c -> data = Item; //copy item
c -> next = NULL;
if(temp -> ch == NULL)
  {
   temp -> ch = c;
   temp -> top = c;
  }

else
  {
   temp -> top -> next = c;
   temp -> top = c;
  }
}

void copy(node *&n,int loc,int Item)
{
node *temp = n;
while(temp -> index != loc) //goto location
  temp = temp -> next;

if(temp -> data == -1)
  temp -> data = Item; //copy data
else
  Link(n,loc,Item); //Link data
}

void display(node *n)
{
node *temp = n;
chain *c;
while(temp != NULL)
  {
   if(temp -> data != -1)
    cout << endl << temp -> index << '\t' << temp -> data;
   else
    cout << endl << temp -> index;
   if(temp -> ch != NULL)
   {
    c = temp -> ch;
    while(c != NULL)
    {
     cout << " -> " << c -> data;
     c = c -> next;
    }
   }
  temp = temp -> next;
  }
}

int main()
{
node *nd = NULL;
int size,key,n,address;
cout << "Program to Implement Hashing by Chaining Method,";
cout << "\nThe Hash Function is Key%TableSize.";
cout << "\n\nEnter Table Size : ";
cin >> size;

for(int i = 0;i < size;i++)  //Initialize Table with 0 as data
  insert(nd,-1);

cout << endl << "How Many Items? ";
cin >> n;
cout << endl << "Enter " << n << " Keys\n";
for(int i = 0;i < n;i++)
  {
   cin >> key;
   address = int (key%size); //Find Address using Hash Function key%size
   cout << "\nH(" << key << ") = " << key << '%' << size << " = " << address;
   copy(nd,address,key); //Copy key to Address
  }

cout << "\n\nHash Table\n";
cout << "----------\n";
display(nd); //Display Hash Table
getch();
return 0;
}

OUTPUT

Program to Implement Hashing by Chaining Method,
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) = 25%13 = 12
H(46) = 46%13 = 7
H(75) = 75%13 = 10
H(29) = 29%13 = 3
H(36) = 36%13 = 10
H(53) = 53%13 = 1
H(68) = 68%13 = 3
H(89) = 89%13 = 11
H(117) = 117%13 = 0
H(120) = 120%13 = 3
H(140) = 140%13 = 10

Hash Table

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

Download Original File

Chaining.cpp