Assignment 1: Searching Algorithms
Set A
a) Create a random array of n integers. Accept a value x from user and use linear search algorithm to check whether the number is present in the array or not and output the position if the number is present.
Program:-
#include<stdio.h>
int linear_search(int a[],int n,int sr)
{ int i;
for(i=0;i<n;i++)
{
if(a[i]==sr)
return i;
}
return -1;
}
void generate(int a[],int n)
{ int i;
for(i=0;i<n;i++)
a[i]=rand()%20;
}
void display(int a[],int n)
{ int i;
for(i=0;i<n;i++)
printf("%d\t",a[i]);
}
main()
{
int a[20],i,j,n,x,ans;
printf("\n Enter how many elemants:");
scanf("%d",&n);
generate(a,n);
printf("\n Elements are:\n");
display(a,n);
printf("\n Enter searching element : ");
scanf("%d",&x);
ans=linear_search(a,n,x);
if(ans==-1)
printf("\n %d is NOT found.",x);
else
printf("\n %d is found at %d position\n",x,ans+1);
}
b) Accept n values in array from user. Accept a value x from user and use sentinel linear search algorithm to check whether the number is present in the array or not and output the position if the number is present.
#include<stdio.h>
#define max 10
int main()
{
int a[max],k,i,n,flag=0,index;
printf("Enter Size of array:");
scanf("%d",&n);
generate(a,n);
printf("Random elements are\n");
for(i=0;i<n;i++)
printf("%d\n",a[i]);
printf("Enter number to search: ");
scanf("%d",&k);
Sentinelsearch(a,n,k);
}
void generate(int a[],int n)
{
int i;
for(i=0;i<n;i++)
a[i]=rand()%100;
}
void Sentinelsearch(int a[],int n,int k)
{
int i,flag=0,index ;
i=0;
a[n]=k;
while(a[i]!=k)
i++;
if(i<n)
printf("Searched found at index %d",i+1);
else
printf("Not Found");
}
c) Accept n sorted values in array from user. Accept a value x from user and use binary search algorithm to check whether the number is present in sorted array or not and output the position if the number is present..
#include<stdio.h>
void main()
{
int arra[100],i,n,x,f,l,m,flag=0;
printf("Input no. of elements in an array\n");
scanf("%d",&n);
printf("Input %d value in ascending order\n",n);
for(i=0;i<n;i++)
scanf("%d",&arra[i]);
printf("Input the value to be search : ");
scanf("%d",&x);
/* Binary Search logic */
f=0;l=n-1;
while(f<=l)
{
m=(f+l)/2;
if(x==arra[m])
{
flag=1;
break;
}
else if(x<arra[m])
l=m-1;
else
f=m+1;
}
if(flag==0)
printf("%d value not found\n",x);
else
printf("%d value found at %d position\n",x,m);
}
Set B
a) Read the data from file 'cities.txt' containing names of cities and their STD codes. Accept a name of the city from user and use linear search algorithm to check whether the name is present in the file and output the STD code, otherwise output “city not in the list”.
//Reading from file
#include<stdio.h>
typedef struct city
{
char name[20];
int code;
} city;
//Fileread
int fileread(city a[20])
{
FILE *fp;
int i=0;
fp=fopen("cities.txt","r");
if(fp==NULL)
printf("File Not Exist");
else
{
while(!feof(fp))
{
fscanf(fp,"%s%d", a[i].name, &a[i].code);
i++;
}
fclose(fp);
}
return i-1;
}
//Main
int main()
{
int i, n;
char key[20];
city a[20];
n = fileread(a);
for(int i=0; i<n; i++)
printf("%s %d\n", a[i].name, a[i].code);
/* displaying records*
linearsearch(n);
}
//Linear Search
linearsearch(int n)
{
city a[20];
n=fileread(a);
char str[20];
int index,flag=0;
printf("Enter city:");
scanf("%s",str);
for(int i=0;i<n;i++)
{
if(strcmp(str,a[i].name)==0)
{
flag=1;
index=i;
}
}
if(flag==1)
printf("City Code: %d",a[index].code);
else
printf("City Not in list");
}
b) Read the data from file 'cities.txt' containing names of cities and their STD codes. Accept a name of the city from user and use sentinel linear search algorithm to check whether the name is present in the file and output the STD code, otherwise output “city not in the list”.
#include<stdio.h>
#include<string.h>
typedef struct city
{
char name[20];
int code;
}record;
record city[100];
int read_file(record *a)
{
int i=0;
FILE *fp;
if((fp=fopen("cities.txt","r"))!=NULL)
{
while(!feof(fp))
{
fscanf(fp,"%s%d",a[i].name,&a[i].code);
i++;
}}
return (i-1);
}
void l_search(record *a,int n,char x[20])
{
int i;
for(i=0;i<n;i++)
{
if(strcmp(a[i].name,x)==0)
{
printf("\n%s=%d\n",a[i].name,a[i].code);
break;
}
}
if(i==n)
printf("\ncity not found\n");
}
main()
{
char x[20];
int n;
n=read_file(city);
printf("\nenter city name\n");
gets(x);
l_search(city,n,x);
}
c) Read the data from file ‘sortedcities.txt’ containing sorted names of cities and their STD codes. Accept a name of the city from user and use binary search algorithm to check whether the name is present in the file and output the STD code, otherwise output “city not in the list”.
No comments:
Post a Comment