Advertisement
Arnab_Manna

HASHING Quardratic Probing

Dec 8th, 2022
718
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.26 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<String.h>
  4.  
  5. int m;
  6. int c1,c2;
  7.  
  8. int poW(int n,int m)
  9. {
  10.     int i;
  11.     for(i=1;i<=m;i++)
  12.     {
  13.         n*=n;
  14.     }
  15.     return n;
  16. }
  17. int HashFn(int k,int i)
  18. {
  19.     return ((k+(c1*i)+(c2*i*i))%m);
  20. }
  21.  
  22. int isfull(int *a)
  23. {
  24.     int i,f=0;
  25.     for(i=0;i<m;i++)
  26.     {
  27.         if(a[i]!=-1)
  28.         {
  29.             f++;
  30.         }
  31.     }
  32.     if(f==0)
  33.     return 1;
  34.     else
  35.     return 0;
  36. }
  37.  
  38. int isempty(int *a)
  39. {
  40.     int i,f=0;
  41.     for(i=0;i<m;i++)
  42.     {
  43.         if(a[i]==-1)
  44.         {
  45.             f++;
  46.         }
  47.     }
  48.     if(f==12)
  49.     return 1;
  50.     else
  51.     return 0;
  52. }
  53. void printHash(int *a)
  54. {
  55.     int i;
  56.     puts("index\t\tdata\n");
  57.     for(i=0;i<m;i++)
  58.     {
  59.        
  60.         if(a[i]==-1)
  61.         printf("%d\t\t\n",i);
  62.         else
  63.         printf("%d\t\t%d\n",i,a[i]);
  64.     }
  65. }
  66.  
  67. void insert(int *a,int k)
  68. {
  69.     int i=0;
  70.     int h=HashFn(k,i);
  71.     while (a[h]!=-1)
  72.     {
  73.         if(isfull(a)==1)
  74.         {
  75.             printf("no space found ");
  76.             break;
  77.         }
  78.         i++;
  79.         h=HashFn(k,i);
  80.     }
  81.     a[h]=k;
  82.     puts("data added successfully");
  83.    
  84. }
  85.  
  86. void search(int *a,int n1)
  87. {
  88.     int i=0;
  89.     int h=HashFn(n1,i);
  90.     while (a[h]!=n1)
  91.     {
  92.         i++;
  93.         h=HashFn(n1,i);
  94.     }
  95.     if(a[h]==n1)
  96.     {
  97.         printf("the data is present at position%d\n",h);
  98.     }
  99.     else
  100.     {
  101.         printf("not found !\n");
  102.     }
  103. }
  104.  
  105. void Delete(int *a,int n1)
  106. {
  107.     int i=0;
  108.     int h=HashFn(n1,i);
  109.     while (a[h]!=n1)
  110.     {
  111.         if(isempty(a)==1)
  112.         {
  113.             printf("no space found ");
  114.             break;
  115.         }
  116.         i++;
  117.         h=HashFn(n1,i);
  118.     }
  119.     if(a[h]==n1)
  120.     {
  121.         a[h]=-1;
  122.         printf("deleted\n");
  123.     }
  124.     else
  125.     {
  126.         printf("not found!\n");
  127.     }
  128. }
  129.  
  130. int main()
  131. {
  132.     int *a,i,n,ch;
  133.     puts("enter m :");
  134.     scanf("%d",&m);
  135.     a=(int*) calloc(m,sizeof(int));
  136.     puts("enter c1 :");
  137.     scanf("%d",&c1);
  138.     puts("enter c2 :");
  139.     scanf("%d",&c2);
  140.    
  141.     for(i=0;i<m;i++)
  142.     {
  143.         a[i]=-1;
  144.     }
  145.     while(1)
  146.     {
  147.         puts("1>insert a key\n2> search key\n3> delete a key\n4>display the hash table\n5>exit\nenter your choice :");
  148.         scanf("%d",&ch);
  149.         switch(ch)
  150.         {
  151.             case 1:
  152.                 printf("enter the data :");
  153.                 scanf("%d",&n);
  154.                 insert(a,n);
  155.             break;
  156.             case 2:
  157.                 printf("the data you want ? :");
  158.                 scanf("%d",&n);
  159.                 search(a,n);
  160.             break;
  161.             case 3:
  162.                 printf("the data you want to delete ? :");
  163.                 scanf("%d",&n);
  164.                 Delete(a,n);
  165.             break;
  166.             case 4:
  167.                 printHash(a);
  168.             break;
  169.             case 5:
  170.                 exit(0);
  171.             default:
  172.                 puts("invalid choice");
  173.         }
  174.     }
  175.     return 0;
  176. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement