Quadratic Probing

 avatar
unknown
plain_text
4 years ago
2.3 kB
16
Indexable
#include<stdio.h>
#include<stdlib.h>

int isEmpty(int *harr,int size)
{
    for(int i=0;i<size;i++)
    {
        if(harr[i] == -1)
        {
            return 0;
        }
    }
    return 1;
}



void insert(int *harr,int size)
{
    int i,key,hkey,index;
    printf("\nEnter a value to insert into hash table : ");
    scanf("%d",&key);
    hkey=key%size;

    if (harr[hkey] == -1)
    {
        harr[hkey] = key;
    } else
    {
        i = 0;
        while (isEmpty(harr,size)==0 && harr[hkey] != -1)
        {
            hkey = (hkey+i*i)%size;
            if (harr[hkey] == -1)
            {
                harr[hkey] = key;
                break;
            }
            i++;
        }
    }

    if(isEmpty(harr,size)==1)
    {
        printf("\nElement cannot be inserted as array is full\n");
    }
}

void display(int *harr,int size)
{
    int i;
    printf("\n Elements in the hash table are \n");
    for(i=0; i< size; i++)
    {
        if(harr[i]==-1)
        {
            printf("\n At index %d \t value = -1",i);
            continue;
        }
        printf("\n At index %d \t value =  %d",i,harr[i]);
    }
}

void search(int* harr, int size)
{
    int i,key,hkey,index;
    printf("\nEnter element to search : ");
    scanf("%d",&key);
    hkey=key%size;
    for(i=0; i<10; i++)
    {
        index=(hkey+i*i)%size;
        if(harr[index]==key)
        {
            printf("Value found at index %d\n",index);
            break;
        }
    }
    if(i == 10)
    {
        printf("\nValue not found\n");
    }
}

int main(void)
{
    int ch,size;
    printf("Enter Size of Array : ");
    scanf("%d",&size);
    int harr[size];
    for(int i=0 ; i<size ; i++)
    {
        harr[i] = -1;
    }

    do
    {
        printf("\nEnter one of the following options: \n");
        printf("1-Insert | 2-Search | 3-Display | 4-Quit\n");
        scanf("%d",&ch);
        switch(ch)
        {
        case 1:
        {
            insert(harr,size);
            break;
        }
        case 2:
        {
            search(harr,size);
            break;
        }
        case 3:
        {
            display(harr,size);
            break;
        }
        case 4:
            break;
        default:
            printf("Invalid choice");
        }
    }
    while(ch!=4);
}
Editor is loading...