Index Sequential and Interpolation Search

By -
Write a Program to implement Searching methods Index Sequential and Interpolation Search using menu driven programming.

#include<stdio.h>
#include<conio.h>
int interpolation_search(int a[],int i,int j,int key);
int index_sequential(int a[],int n,int key);

void main()
{
 int a[30],key,mid,p,q,k,n,i,result,op;
 clrscr();
 do
 {
  printf("\n1) Interpolation Search\n2) Index Sequential Search\n3) Quit\n");
  printf("Enter your choice: ");
  scanf("%d",&op);
  switch(op)
  {
   case 1:printf("\n Enter No. of Element: ");
             scanf("%d",&n);
             printf("\n Enter a sorted list of %d elements : ",n);
            for(i=0;i<n;i++)
            scanf("%d",&a[i]);
            printf("\n Enter the element to searched : ");
            scanf("%d",&key);
            result=interpolation_search(a,0,n-1,key);
            if(result==-1)
            printf("\n Not found :");
            else
            printf("\n Found at location=%d",result);
            break;
   case 2:printf("\n Enter No. of element:");
            scanf("%d",&n);
            printf("\n Enter a list of %d elements:",n);
            for(i=0;i<n;i++)
            scanf("%d",&key);
            result=index_sequential(a,n,key);
            if(result==-1)
            printf("\n Not found");
            else
            printf("\n Found at location =%d",result);
            break;
  }
}while(op!=3);
 getch();
 }
int interpolation_search(int a[],int i,int j,int key)
{
 int c,mid;
 if(i>j)
 return (-1);
 if(j>i)
 c=(key-i)/(j-i);
 else
 c=0;
 mid=i;
 if(c>0)
 mid=i+(j-i)/c;
 if(key==a[mid])
 return(mid);
 if(key>a[mid])
 return(interpolation_search(a,mid+1,j,key));
 return(interpolation_search(a,i,mid-1,key));
}
 int index_sequential(int a[],int n,int key)
{
 int keys[6],index[6],i,j,temp,n1,start;
 for(i=0;i<n;i++)
 for(j=0;j<n;j++)
 if(a[j]>a[j+1])
 {
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
 }
 n1=0;
 for(i=0;i<n;i=i+4)
 {
keys[n1]=a[i];
index[n1]=i;
n1++;
 }
 if(key<keys[0])
  return(-1);
 for(i=0;i<n;i++)
  if(key<keys[i])
   break;
   start=index[i-1];
 for(i=start;i<start+4&&i<n;i++)
 if(a[i]==key)
 return (i);
 return(-1);
}


 OUTPUT:




Comments

Post a Comment

Popular posts from this blog

Sequential File Allocation

By -
Image
Write a C Program to implement Sequential File Allocation method #include < stdio.h> #include<conio.h> void main() { int f[50], i, st, len, j, c, k, count = 0; clrscr(); for(i=0;i<50;i++) f[i]=0; printf("Files Allocated are : \n"); x: count=0; printf(“Enter starting block and length of files: ”); scanf("%d%d", &st,&len); for(k=st;k<(st+len);k++)  if(f[k]==0)  count++; if(len==count) {  for(j=st;j<(st+len);j++)  if(f[j]==0)  {  f[j]=1;  printf("%d\t%d\n",j,f[j]);  }  if(j!=(st+len-1))  printf(” The file is allocated to disk\n"); } else printf(” The file is not allocated \n"); printf("Do you want to enter more file(Yes - 1/No - 0)"); scanf("%d", &c); if(c==1)  goto x; else  exit(); getch(); } Output:
Read more

Indexed File Allocation method

By -
Image
Write a C Program to implement Indexed File Allocation method #include<stdio.h> #include<conio.h> #include<stdlib.h> void main() { int f[50], index[50],i, n, st, len, j, c, k, ind,count=0; clrscr(); for(i=0;i<50;i++) f[i]=0; x:printf("Enter the index block: "); scanf("%d",&ind); if(f[ind]!=1) {  printf("Enter no of blocks needed and no of files for the index %d on the disk : \n", ind);  scanf("%d",&n); } else {  printf("%d index is already allocated \n",ind);  goto x; } y: count=0; for(i=0;i<n;i++) {  scanf("%d", &index[i]);  if(f[index[i]]==0)  count++; } if(count==n) {  for(j=0;j<n;j++)  f[index[j]]=1;  printf("Allocated\n");  printf("File Indexed\n");  for(k=0;k<n;k++)  printf("%d-------->%d : %d\n",ind,index[k],f[index[k]]); } else { printf("File in the index is already allocated \n"); printf(&quo
Read more

Linked File Allocation

By -
Image
Write a C Program to implement Linked File Allocation method. #include<stdio.h> #include<conio.h> #include<stdlib.h> void main() { int f[50], p,i, st, len, j, c, k, a; clrscr(); for(i=0;i<50;i++) f[i]=0; printf("Enter how many blocks already allocated: "); scanf("%d",&p); printf("Enter blocks already allocated: "); for(i=0;i<p;i++) {  scanf("%d",&a);  f[a]=1; } x: printf("Enter index starting block and length: "); scanf("%d%d", &st,&len); k=len; if(f[st]==0) {  for(j=st;j<(st+k);j++)  {  if(f[j]==0)  {  f[j]=1;  printf("%d-------->%d\n",j,f[j]);  }  else  {  printf("%d Block is already allocated \n",j);  k++;  }  } } else printf("%d starting block is already allocated \n",st); printf("Do you want to enter more file(Yes - 1/No - 0)"); scanf("%d", &c); if(c==1)  goto x; else  exit(0);
Read more