C - Programming Guide

C - Program to Implement Hashing , handle collision  using linear probing with chaining and with replacement

 

#include <conio.h>
#define SIZE 10              /* size of the hash table*/
#define FALSE 0
#define TRUE 1
#define h(x) x%SIZE         /*hashing function */



void insert( int data[],int flag[],int chain[],int x);
int search(int data[],int flag[],int chain[],int x);
void print(int data[],int flag[],int chain[]);


void main()
 {
    int data[SIZE],flag[SIZE],chain[SIZE],i,j,x,op,loc;
    /* array data[]  - is a hash table
       array flag[]  - if flag[i] is 1 then the ith place of the hash
               table is filled */
    for(i=0;i<SIZE;i++) /* initialize */
       {
        flag[i]=FALSE;
        chain[i]=-1;
       }
   clrscr();
    do
      {
        flushall();
        printf("\n\n1)Insert\n2)Search\n3)Print\n4)Quit");
        printf("\nEnter Your Choice : ");
        scanf("%d",&op);
        switch(op)
           {
            case 1: printf("\n Enter a number to be inserted:");
                scanf("%d",&x);
                insert(data,flag,chain,x);
                break;
            case 2: printf("\n Enter a number to be searched :");
                scanf("%d",&x);
                if((loc=search(data,flag,chain,x))==-1)
                    printf("\n****Element not found****");
                else
                    printf("\n***Found at the location=%d",loc);
                break;
            case 3: print(data,flag,chain);
                break;
           }
    }while(op!=4);
  }

void insert( int data[],int flag[],int chain[],int x)
{
    int i=0,j,start;
    start=h(x); /*hashed location*/
    /*Situation I, hashed location is empty*/
    if(flag[start]==0)
      {
        data[start]=x;
        flag[start]=1;
        return;
      }
 /*Situation II, hashed location does not contain a synonym*/
    if(h(data[start])!=h(x))
      { /* locate an empty location */
        i=0;j=start;
        while(flag[j] && i<SIZE)
           {
            j=(j+1)%SIZE;
            i++;
           }
        if(i==SIZE)
           {
            printf("\nTable is full ...");
            return;
           }
    /*Delete the element by modifying the chain */
        i=data[start]%SIZE;/*beginning of the chain*/
        while(chain[i] != start)
            i=chain[i];
        chain[i]=chain[start]; /*modify */
    /*add the deleted element at the end of the chain */
        while(chain[i]!=-1)
            i=chain[i];
        chain[i]=j;
        data[j]=data[start];
        chain[start]=-1;
        flag[j]=1;
        chain[j]=-1;
    /*insert the current key */
        data[start]=x;
        chain[start]=-1;
        return;
      }
    /*Situation III ,hashed location contains a synonym */
    /* locate an empty location */
    i=0;j=start;
    while(flag[j] && i<SIZE)
       {
        j=(j+1)%SIZE;
        i++;
       }
    if(i==SIZE)
       {
        printf("\nTable is full ...");
        return;
       }
    data[j]=x;
    flag[j]=1;
    chain[j]=-1;
    /*go to the end of chain */
    i=start;/*beginning of the chain*/
    while(chain[i] != -1)
        i=chain[i];
    chain[i]=j;
}

int search(int data[],int flag[],int chain[],int x)
 {
    int i=0,j;
    j=h(x); /*hashed location*/
    /*locate beginning of the chain*/
    while(i<SIZE && flag[j] && data[j]%SIZE !=x%SIZE)
       {
        i++;
        j=(j+1)%SIZE;
       }
    if(!flag[j] || i==SIZE)
        return(-1);
    /*locate the element in the chain */
    while(j!=-1)
       {
        if(data[j]==x)
            return(j);
        j=chain[j];
       }
    return(-1);
}

void print(int data[],int flag[],int chain[])
 {
    int i;
    for(i=0;i<SIZE;i++)
        if(flag[i])
            printf("\n(%d) %d     %d",i,data[i],chain[i]);
        else
            printf("\n(%d) ---    %d",i,chain[i]);
 }

 Click Here to Download Source Code with Executable Program