Data Structure and Algorithm

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