#include<stdio.h>
#include<stdlib.h>
#define HASH_SIZE 5

#define MALLOC(p,n,type)\
p=(type*)malloc(n*sizeof(type));\
if(p==NULL)\
{\
printf("insufficient memeory\n");\
exit(0);\
}

struct node                           
{
    int info;
    struct node *link;
};
typedef struct node* NODE;  

NODE search_sll(int,NODE);
NODE insertion_rear(int,NODE);
int search_hash_table(int,NODE []);
int H(int);
void insert_hash_table(int item,NODE a[])
{
    int h_value;
    h_value=H(item);
    a[h_value]=insertion_rear(item,a[h_value]);  
}
int H(int k)                                     
{
    return k%HASH_SIZE;
}
NODE insertion_rear(int item,NODE first)
{
    NODE temp,cur;
    MALLOC(temp,1,struct node);
    temp->info=item;
    temp->link=NULL;
    if(first==NULL)
    {
        return temp;
    }
    cur=first;
    while(cur->link!=NULL)
    {
        cur=cur->link;
    }
    cur->link=temp;
    return first;
}

NODE search_sll(int key,NODE first)
{
    NODE cur;
    if(first==NULL)
    {
        printf("SLL is empty\n");
        return NULL;
    }
   
    cur=first;
    while(cur!=NULL)
    {
        if(key==cur->info)break;
        cur=cur->link;
    }
    return cur;
}
int search_hash_table(int key,NODE a[])
{
    int h_value;
    NODE cur;
    h_value=H(key);
    cur=search_sll(key,a[h_value]);   
    if(cur==NULL)
    return 0;
    else
    return 1;
}

void display_hash_table(NODE a[])
{
    int i;
    NODE temp;
    for(i=0;i<HASH_SIZE;i++)
    {
        printf("a[%d]=",i);
        temp=a[i];
        if(temp==NULL)
        printf("NULL\n");
        else
        {
            temp=a[i];
            while(temp->link!=NULL)
            {
                printf("%d-->",temp->info);
                temp=temp->link;
            }
            printf("%d\n",temp->info);
        }
    }    
}
void main()
{
    NODE a[10];
    int item,key,choice,flag,i;
    for(i=0;i<HASH_SIZE;i++)                   
    {
        a[i]=NULL;
    }
    for(;;)
    {
        scanf("%d",&choice);
        switch(choice)
        {
            case 1:scanf("%d",&item);
                   insert_hash_table(item,a);
                   break;
            case 2:scanf("%d",&key);
                   flag=search_hash_table(key,a);
                   if(flag==0)
                   {
                       printf("key is not found\n");
                   }
                   else
                   {
                       printf("key is found\n");
                   }
                   break;
            case 3:printf("content of hash table\n");
                   display_hash_table(a);
                   printf("\n");
                   break;
            case 4:exit(0);
            default:printf("please enter valid choice\n");
		}        
    }    
}