DATA STRUCTURE: ASSIGNMENT-4:SEARCHING TECHNIQUES
PRACTICE PROGRAMS:
1) Write a C program to linearly search an element in a given array. (Use Recursion).
ANS:
#include <stdio.h>
#include <conio.h>
void display(int a[], int n)
{
for (int i = 0; i < n; i++)
{
printf("\t%d", a[i]);
}
}
void linear_search(int a[], int n, int key)
{
int flag = 0;
for (int i = 0; i < n; i++)
{
if (a[i] == key)
{
printf("\n The %d element are founded at %d position!", key, i);
flag = 1;
}
}
if (flag == 0)
{
printf("\n the element are not exist!");
}
}
int main()
{
int a[10], i, n, key, search;
printf("\n Enter the size of array:");
scanf("%d", &n);
printf("\n Enter array elements:");
for (i = 0; i < n; i++)
{
printf("\n Enter %d index element:", i);
scanf("%d", &a[i]);
}
printf("\n The array is:");
display(a, n);
printf("\n Enter element what you want to search:");
scanf("%d", &key);
linear_search(a, n, key);
getch();
return 0;
}
-------------------------------------------------------------------------------------------------
2) Read the data from file ‘employee.txt’ containing names of n employees, their qualification
and salary. Accept a name of the employee from the user and by using linear search
algorithm check whether the name of employee is present in the file or not if present
display salary of that employee, otherwise display “Employee not found”.
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
struct employee
{
char name[20];
char qua[20];
float salary;
};
void linear_search(struct employee emp[], int n, char key[])
{
int flag = 0, index;
for (int i = 0; i < n; i++)
{
if (strcmp(emp[i].name, key) == 0)
{
flag = 1;
printf("\n The employee %s is found at index of %d.", key, i);
printf("\n employee name:%s", emp[i].name);
printf("\n employee qualification:%s", emp[i].qua);
printf("\nemployee salary:%f", emp[i].salary);
break;
}
}
if (flag == 0)
{
printf("\n The employee are not exist!");
}
}
int main()
{
struct employee emp[10];
FILE *ptr;
int i = 0, n = 0;
char key[20];
ptr = fopen("employee.txt", "r");
if (ptr == NULL)
{
printf("\n The file does not exist!");
exit(0);
}
while (!feof(ptr))
{
fscanf(ptr, "%s%s%f", &emp[i].name, &emp[i].qua, &emp[i].salary);
i++;
n++;
}
printf("\n Enter search value:");
gets(key);
linear_search(emp, n, key);
fclose(ptr);
getch();
return 0;
}
TEXT FILE:
rakesh mca 20000
ram mcm 30000
krishna mba 20000
-----------------------------------------------------------------------------------------------
3) Read the data from file ‘player.txt’ containing names of n Player, their game_played and
age. Accept a name of the player from the user and by using binary search algorithm check
whether the name of player is present in the file or not if present display game_played and
age of that player, otherwise display “player not found”.
ANS:
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
typedef struct play
{
char name[20];
char game[20];
int age;
} player;
void display(player p[], int i, int n)
{
for (i = 0; i < n; i++)
{
printf("\n%s %s %d", p[i].name, p[i].game, p[i].age);
}
}
void bubble_sort(player a[], int n)
{
player temp;
int i, pass;
for (pass = 1; pass < n; pass++)
{
for (i = 0; i < n - pass; i++)
{
if (strcmp(a[i].name, a[i + 1].name) > 0)
{
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
}
}
}
void binary_search(player a[], int first, int last, char key[])
{
int mid, flag = 0;
while (first < last)
{
mid = (first + last) / 2;
if (strcmp(a[mid].name, key) == 0)
{
flag = 1;
printf("\nThe %s player founded at %d position.", key, mid);
printf("\n Player name:%s", a[mid].name);
printf("\n Player game:%s", a[mid].game);
printf("\n Player age:%d", a[mid].age);
break;
}
if (strcmp(a[mid].name, key) > 0)
{
last = mid - 1;
}
else
{
first = mid + 1;
}
}
if (flag == 0)
{
printf("\n The %s player are not exist in file!", key);
}
}
int main()
{
player p[10];
FILE *ptr;
int i, n = 0;
char key[20];
ptr = fopen("player.txt", "r");
if (ptr == NULL)
{
printf("\n The file does not exist!");
exit(0);
}
i = 0;
while (!feof(ptr))
{
fscanf(ptr, "%s%s%d", &p[i].name, &p[i].game, &p[i].age);
i++;
n++;
}
printf("\n Before sorting details:\n");
display(p, 0, n);
printf("\n Enter search player name:");
scanf("%s", &key);
printf("\n After sorting details:\n");
bubble_sort(p, n);
display(p, 0, n);
binary_search(p, 0, n, key);
fclose(ptr);
}
TEXT FILE:
virat cricket 45
sachin cricket 55
rohit cricket 43
dyanchand hockey 50
-------------------------------------------------------------------------------------
SET A:
1) Write a C program to accept n elements from user store it in an array. Accept a value from
the user and use linear/Sequential search method to check whether the value is present in
array or not. Display proper message.
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
int main()
{
int a[20], i, n, key,flag=0;
printf("\n Enter size of an array:");
scanf("%d", &n);
printf("\n Enter array elements:");
for (i = 0; i < n; i++)
{
printf("\n Enter [%d] index element:",i);
scanf("%d", &a[i]);
}
printf("\n Enter search value:");
scanf("%d", &key);
for (i = 0; i < n; i++)
{
if (a[i]==key)
{
flag=1;
printf("\n The element %d are founded at %d position of array.",key,i);
break;
}
}
if (flag==0)
{
printf("\n The element are not exist in array.");
}
}
-----------------------------------------------------------------------------------------------------
2) Write a C program to accept n elements from user store it in an array. Accept a value from
the user and use binary search method to check whether the value is present in array or not.
Display proper message. (Students should accept sorted array and use Recursive function).
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
void display(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
{
printf("\t%d", a[i]);
}
}
void insertion_sort(int a[], int n)
{
int i, j, temp;
for (i = 0; i < n; i++)
{
temp = a[i];
for (j = i - 1; j >= 0 && a[j] > temp; j--)
{
a[j + 1] = a[j];
}
a[j + 1] = temp;
}
}
void binary_search(int a[], int first, int last, int key)
{
int mid, flag = 0;
while (first <= last)
{
mid = (first + last) / 2;
if (a[mid] == key)
{
flag = 1;
printf("\n The %d element are founded at %d position.", key, mid);
break;
}
if (a[mid] > key)
{
last = mid - 1;
}
else
{
first = mid + 1;
}
}
if (flag == 0)
{
printf("\n The element are not exist in array!");
}
}
int main()
{
int a[20], i, n, key;
printf("\n Enter size of an array:");
scanf("%d", &n);
printf("\n Enter array elements:");
for (i = 0; i < n; i++)
{
printf("\n Enter [%d] index element:", i);
scanf("%d", &a[i]);
}
printf("\n Enter search value:");
scanf("%d", &key);
printf("\n The before sorting array is:");
display(a, n);
insertion_sort(a, n);
printf("\n The after sorting array is:");
display(a, n);
binary_search(a, 0, n - 1, key);
}
-----------------------------------------------------------------------------
3) Write a ‘C’ program to create a random array of n integers. Accept a value of n from user
and use Binary search algorithm to check whether the number is present in array or not.
(Students should accept sorted array and use Non-Recursive function also use random
function).
ANS:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
void display(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
{
printf("\t%d", a[i]);
}
}
void binary_search(int a[],int first,int last,int key){
int mid,flag=0;
while (first<=last)
{
mid=(first+last)/2;
if (a[mid]==key)
{
flag=1;
printf("\n The %d element are founded at %d position.",key,mid);
break;
}
if (a[mid]>key)
{
last=mid-1;
}else
{
first=mid+1;
}
}
if (flag==0)
{
printf("\n The element are not exist in array!");
}
}
int partition(int a[],int first,int last){
int pivot,i,j,temp;
pivot=a[first];
i=first+1;
j=last;
do
{
while (i<=last&&a[i]<pivot)
{
i++;
}
while (j>first&&a[j]>pivot)
{
j--;
}
if (i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
} while (i<j);
a[first]=a[j];
a[j]=pivot;
return j;
}
void quick_sort(int a[], int first ,int last ){
int j;
if (first<=last)
{
j=partition(a,first,last);
quick_sort(a,first,j-1);
quick_sort(a,j+1,last);
}
}
int main()
{
int a[20], i, n, key;
printf("\n Enter size of an array:");
scanf("%d", &n);
printf("\n Enter array elements:");
for (i = 0; i < n; i++)
{
printf("\n Enter [%d] index element:", i);
scanf("%d", &a[i]);
}
printf("\n Enter search value:");
scanf("%d", &key);
printf("\n The before sorting array is:");
display(a, n);
quick_sort(a,0,n-1);
printf("\n The after sorting array is:");
display(a,n);
binary_search(a,0,n-1,key);
}
---------------------------------------------------------------------------
SET B:
1) Write a ‘C’ program to accept the names of cities and store them in array. Accept the city
name from user and use linear search algorithm to check whether the city is present in array
or not.
ANS:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
int main(){
char city[10][20],key[10];
int n,i,flag=0;
printf("\n Enter how many cities want to store in array:");
scanf("%d",&n);
printf("\n Enter city name:");
for ( i = 0; i < n; i++)
{
printf("\n Enter [%d] index city:",i);
scanf("%s",&city[i]);
}
printf("\n Enter city name for searching:");
scanf("%s",&key);
for ( i = 0; i < n; i++)
{
if (strcmp(city[i],key)==0)
{
flag=1;
printf("\n The %s city are founded at %d index of an array.",key,i);
break;
}
}
if (flag==0)
{
printf("\n The city %s are not exist in array!");
}
}
-----------------------------------------------------------------------------------------------
2) Write a C program to accept n elements from user store it in an array. Accept a value from
the user and use recursive binary search method to check whether the value is present in
array or not. Display proper message. (use any sorting method to sort the array).
ANS:
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
void display(int a[], int n)
{
int i;
for (i = 0; i < n; i++)
{
printf("\t%d", a[i]);
}
}
void binary_search(int a[],int first,int last,int key){
int mid,flag=0;
while (first<last)
{
mid=(first+last)/2;
if (a[mid]==key)
{
flag=1;
printf("\n The %d element are founded at %d position of array !",key,mid);
break;
}
if (a[mid]>key)
{
last=mid-1;
}else{
first=mid+1;
}
}
if (flag==0)
{
printf("\n The element are not exist in array!");
}
}
void merge(int a[], int first, int mid, int last)
{
int i, j, b[20], k;
i = first;
j = mid + 1;
k = 0;
while (i <= mid && j <= last)
{
if (a[i] > a[j])
{
b[k++] = a[j++];
}
else
{
b[k++] = a[i++];
}
}
while (i<=mid)
{
b[k++]=a[i++];
}
while (j<=last)
{
b[k++]=a[j++];
}
for ( j = first,k=0; j <= last; j++,k++)
{
a[j]=b[k];
}
}
void merge_sort(int a[], int first, int last)
{
int mid;
if (first < last)
{
mid = (first + last) / 2;
merge_sort(a, first, mid);
merge_sort(a, mid + 1, last);
merge(a, first, mid, last);
}
}
int main()
{
int a[20], n, i, key;
printf("\n Enter size of array:");
scanf("%d", &n);
printf("\n Enter array elements:");
for (i = 0; i < n; i++)
{
printf("\n Enter [%d] index element:", i);
scanf("%d", &a[i]);
}
printf("\n Enter searching element:");
scanf("%d", &key);
printf("\n before sorting array is:");
display(a, n);
merge_sort(a, 0, n - 1);
printf("\n after sorting array is:");
display(a, n);
binary_search(a,0,n-1,key);
}
---------------------------------------------------------------------------------
3) Read the data from file ‘sortedcities.txt’ containing sorted names of n 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”.
ANS:
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
typedef struct cities
{
char name[20];
int code;
}city;
int main(){
city c[10];
int n,i,flag=0;
char key[10];
FILE *ptr;
ptr=fopen("sorted_cities.txt","r");
if (ptr==NULL)
{
printf("\n The file are empty!");
exit(0);
}
n=1;
i=0;
while (!feof(ptr))
{
fscanf(ptr,"%s%d",&c[i].name,&c[i].code);
i++;
n++;
}
printf("\n Enter searching city name:");
scanf("%s",&key);
for ( i = 0; i < n; i++)
{
if (strcmp(c[i].name,key)==0)
{
flag=1;
printf("\n The city name %s are founded at %d position in file.",key,i);
printf("\n City name:%s",c[i].name);
printf("\n City STD code:%d",c[i].code);
break;
}
}
if (flag==0)
{
printf("\n The city are not exist in array!");
}
}
TEXT FILE:
nagar 297466
nashik 730098
pune 764766
shrirampur 413709
-------------------------------------------------------------------------------------------------
SET C:
1) Write a C program to read the data from file 'cities.txt' containing names of 10 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”.
ANS:
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
typedef struct cities
{
char name[20];
int code;
} city;
void bubble_sort(city c[], int n)
{
city temp;
int pass, i;
for (pass = 1; pass < n; pass++)
{
for (i = 0; i < n - pass; i++)
{
if (strcmp(c[i].name, c[i + 1].name) > 0)
{
temp = c[i];
c[i] = c[i + 1];
c[i + 1] = temp;
}
}
}
}
void binary_search(city c[], int first, int last, char key[])
{
int mid;
int flag = 0;
while (first <= last)
{
mid = (first + last) / 2;
if (strcmp(c[mid].name, key) == 0)
{
flag = 1;
printf("\n The %s city are founded at %d location.", key, mid);
printf("\n City name:%s", c[mid].name);
printf("\n City code:%d", c[mid].code);
break;
}
if (strcmp(c[mid].name, key) > 0)
{
last = mid - 1;
}
else
{
first = mid + 1;
}
}
if (flag == 0)
{
printf("\n city not in the list!");
}
}
int main()
{
city c[10];
int i, n = 0;
char key[20];
FILE *ptr;
ptr = fopen("cities.txt", "r");
if (ptr == NULL)
{
printf("\n The file are not exist!");
exit(0);
}
i = 0;
while (!feof(ptr))
{
fscanf(ptr, "%s%d", &c[i].name, &c[i].code);
i++;
n++;
}
bubble_sort(c, n);
printf("\n Enter search value:");
scanf("%s", &key);
binary_search(c, 0, n, key);
ptr = fopen("cities.txt", "a");
fprintf(ptr, "\n The sorted file is:");
for (i = 0; i < n; i++)
{
fprintf(ptr, "\n%s %d", c[i].name, c[i].code);
}
fclose(ptr);
}
TEXT FILE:
nashik 65346
nagar 54653
pune 64766
mumbai 67466
aurangabad 67347
rahata 67367
shirdi 64776
rahuri 35556
sangmaner 67643
shrirampur 64766
-------------------------------------------------------------------------------------
2) Write a C program to read the data from file 'student.txt' containing names of 10 students
and their roll no. Accept a name of the student from user and use Binary search algorithm
to check whether the name is present in the file and output the roll no, otherwise output
“Student name not in the list”.
ANS:
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
typedef struct student
{
char name[20];
int roll_no;
} student;
void bubble_sort(student a[], int n)
{
student temp;
int i, pass;
for (pass = 1; pass < n; pass++)
{
for (i = 0; i < n - pass; i++)
{
if (strcmp(a[i].name, a[i + 1].name) > 0)
{
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
}
}
}
void binary_search(student a[], int first, int last, char key[])
{
int mid, flag = 0;
while (first <= last)
{
mid = (first + last) / 2;
if (strcmp(a[mid].name, key) == 0)
{
flag = 1;
printf("\n The student %s are founded at %d position.", key, mid);
printf("\n Roll no.:%d", a[mid].roll_no);
printf("\n Student name:%s", a[mid].name);
break;
}
if (strcmp(a[mid].name, key) > 0)
{
last = mid - 1;
}
else
{
first = mid + 1;
}
}
if (flag == 0)
{
printf("\n The student name not in the list! ");
}
}
int main()
{
student s1[10];
int n = 0, i;
char key[20];
FILE *ptr;
ptr = fopen("student.txt", "r");
if (ptr == NULL)
{
printf("\n The file does not exist!");
exit(0);
}
i = 0;
while (!feof(ptr))
{
fscanf(ptr, "%s%d", &s1[i].name, &s1[i].roll_no);
i++;
n++;
}
bubble_sort(s1, n);
printf("\n Enter student name for search:");
scanf("%s", &key);
binary_search(s1, 0, n - 1, key);
fclose(ptr);
}
TEXT FILE:
sahil 7754
nikhil 6456
siddharth 6656
gopal 6546
nayan 7757
ramesh 7767
suresh 7757
aman 75665
rushikesh 7776
sanjay 5777
--------------------------------------------------------------------------------
Comments
Post a Comment
Enter comment here!