Data Structure and Algorithm:
A data structure is a particular way of organizing data in a computer so that it can be used effectively.
For example, we can store a list of items having the same data-type using the array data structure.
In the data structure there two type of searching :
1. sequential search (linear search)
2. binary search
program of sequntial search:
#include<stdio.h>
#include<conio.h>
int linear_search(int a[],int n,int key) {
for(int i=0; i<n; i++)
if(a[i]==key)
return i;
return -1;
}
int main() {
int a[10],n,key,ans;
printf("enter how many numbers:");
scanf("%d",&n);
for(int i=0; i<n; i++) {
printf("enter the number:");
scanf("%d",&a[i]);
}
printf("\n enter the key:");
scanf("%d",&key);
ans=linear_search(a,n,key);
if(ans==-1)
printf("\n sorry yar ur element not found!!!");
else
printf("\n element found at index %d",ans);
return 0;
}
program for binary search:
/* It is very important in binary search 1st ly all element are making in sorted and then applid binary search
*/
#include<stdio.h>
#include<conio.h>
int BinarySearch(int a[],int n, int key);
int main() {
int a[10],n,key,i,ans;
printf("how many no u enter :");
scanf("%d",&n);
for( i=0; i<n; i++) {
printf("\n enter no:");
scanf("%d",&a[i]);
}
printf("\n enter the key:");
scanf("%d",&key);
ans=BinarySearch(a,n,key);
if(ans==-1)
printf("\nohh sorry %d not found in array!!!",key);
else
printf("\n key found at position %d",ans+1);
return 0;
}
int BinarySearch(int a[],int n, int key) {
int lower=0,upper=n-1,mid;
while(lower<=upper) {
mid=(lower+upper)/2;
if(key==a[mid])
return mid;
if(key<mid)
upper=mid-1;
else
lower=mid+1;
}
return -1;
}
In the sequntial search there are three type searchs:
1.sential search
2.probability search
3.ordered list search
program for sential search:
#include<stdio.h>
#include<conio.h>
int main() {
int a[10],n,key,i,ans;
printf(" how many elements u r enter :");
scanf("%d",&n);
printf("\nenter the elements:");
for(i=0; i<n; i++)
scanf("%d",&a[i]);
printf("\n enter the key u want to be search:");
scanf("%d",&key);
ans=sentialsearch(a,n,key);
if(ans==-1)
printf("\n ohhh sorry ur key is not found!!!");
else
printf("\n key is found at position :%d ",ans+1);
return 0;
}
int sentialsearch(int a[],int n,int key) {
int i=0,posn,compcount;
a[n]=key;
while(a[i]!=key) {
compcount++;
i++;
}
compcount++;
if(i==n)
return -1;
else
return i;
}
sorting :-
there are two types of sorting-
1) comparison-based
2) Non-comparison-based
1) Comparison based-
i) bubble
ii) insertion
iii) selection
iv) quick
v) merge
2) Non comparison based-
i) radix
ii) counting
iii)bucket
1] comparison-based sorting-
i) bubblesort-
#include<stdio.h>
#include<conio.h>
int accept(int a[],int n) {
int i;
for(i=0; i<n; i++) {
printf("\n enter the elements:");
scanf("%d",&a[i]);
}
}
int BubbleSort(int a[],int n) {
int i,j,temp;
for(i=0; i<n; i++) {
for(j=i+1; j<n; j++) {
if(a[j]<a[i]) {
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
}
int display(int a[],int n) {
int i;
for(i=0; i<n; i++) {
printf("\n %d\n",a[i]);
}
}
int main() {
int a[30],n;
printf("how many number you enter :");
scanf("%d",&n);
printf("\n before sorting array elements are:");
accept(a,n);
BubbleSort(a,n);
printf("\n after sorting array elements are:");
display(a,n);
return 0;
}
ii) insertion sort-
#include<stdio.h>
#include<conio.h>
int insertionsort(int a[],int n);
int display(int a[], int n);
int main()
{
int a[10],n,i;
printf(" how many elements u r enter :");
scanf("%d",&n);
printf("\nbefore sorting array elements are:");
printf("\nenter the elements:");
for(i=0; i<n; i++)
scanf("%d",&a[i]);
insertionsort(a,n);
printf("\n afetr sorting array elements are:");
display(a,n);
return 0;
}
int insertionsort(int a[],int n) {
int key,i,j;
for(i=1; i<n; i++) {
key=a[i];
j=i-1;
while(j>=0 && a[j]>key) {
a[j+1]=a[j];
j--;
}
a[j+1]=key;
}
}
int display(int a[], int n) {
int i;
for(i=0; i<n; i++)
printf("%d\n",a[i]);
}
iii) selection sort
#include<stdio.h>
int selectionsort(int a[],int n)
{
int i,j,min;
for(i=0;i<n-1;i++)
{
min=i;
for(j=i+1;j<n;j++)
{
if(a[j]<a[min])
{
min=j;
}
}
if(min!=i)
{
int temp=a[i];
a[i]=a[min];
a[min]=temp;
}
}
}
int display(int a[], int n)
{
int i;
for(i=0; i<n; i++)
printf("%d\n",a[i]);
}
int main()
{
int a[10],n,i;
printf(" how many elements u r enter :");
scanf("%d",&n);
printf("\nbefore sorting array elements are:");
printf("\nenter the elements:");
for(i=0; i<n; i++)
scanf("%d",&a[i]);
selectionsort(a,n);
printf("\n afetr sorting array elements are:");
display(a,n);
return 0;
}
iv)Quick sort
#include<stdio.h>
int partition (int a[],int lb,int ub)
{
int start=lb;
int end=ub;
int pivot=a[lb];
while(start<end)
{
while(a[start]<=pivot)
{
start++;
}
while(a[end]>pivot)
{
end--;
}
if(start<end)
{
int temp;
temp=a[start];
a[start]=a[end];
a[end]=temp;
}
}
int temp;
temp=a[lb];
a[lb]=a[end];
a[end]=temp;
return end;
}
int quicksort(int a[],int lb,int ub)
{
if(lb<ub)
{
int loc;
loc=partition(a,lb,ub);
quicksort(a,lb,loc-1);
quicksort (a,loc+1,ub);
}
}
int main()
{
int a[20], n, i;
printf("how many no u enter:");
scanf("%d", &n);
printf("\n before sorting:");
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
quicksort(a, 0, n - 1);
printf("\n after sorting:");
for (i = 0; i < n; i++)
printf("%d\n", a[i]);
}
V) merge sort-
#include <stdio.h>
void printArray(int *A, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", A[i]);
}
printf("\n");
}
void merge(int A[], int mid, int low, int high)
{
int i, j, k, B[100];
i = low;
j = mid + 1;
k = low;
while (i <= mid && j <= high)
{
if (A[i] < A[j])
{
B[k] = A[i];
i++;
k++;
}
else
{
B[k] = A[j];
j++;
k++;
}
}
while (i <= mid)
{
B[k] = A[i];
k++;
i++;
}
while (j <= high)
{
B[k] = A[j];
k++;
j++;
}
for (int i = low; i <= high; i++)
{
A[i] = B[i];
}
}
void mergeSort(int A[], int low, int high)
{
int mid;
if (low < high)
{
mid = (low + high) / 2;
mergeSort(A, low, mid);
mergeSort(A, mid + 1, high);
merge(A, mid, low, high);
}
}
int main()
{
int A[20], n, i;
printf("how many no u enter:");
scanf("%d", &n);
printf("\n before sorting:");
for (i = 0; i < n; i++)
scanf("%d", &A[i]);
printf("\n see merge sort working:\n");
printArray(A, n);
mergeSort(A, 0, n - 1);
printArray(A, n);
printf("\n after sorting:");
for (i = 0; i < n; i++)
printf("%d\n", A[i]);
}
File handling on searching -
1) File handling on binary search
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct city
{
char name[20];
} CITY;
void bisearch(CITY c[20], int lb, int ub, char x[20])
{
int mid;
if (lb < ub)
{
mid = (lb + ub) / 2;
if (strcmp(x, c[mid].name) == 0)
{
printf("Element is found ");
return;
}
else
{
if (strcmp(x, c[mid].name) < 0)
{
bisearch(c, lb, mid, x);
}
else
{
bisearch(c, mid, ub, x);
}
}
}
else
printf("Element not found");
} /* end of binary Search function.....*/
void main()
{
int i, j;
char n[20];
CITY c[20];
FILE *fp;
fp = fopen("fcity.txt", "r");
if (fp == NULL)
{
printf("file does not exist");
exit(0);
}
else
{
printf("file exits");
i = 0;
while (!feof(fp))
{
fscanf(fp, "%s", c[i].name);
i++;
}
//for (j = 0; j <i-1; j++)
// {
// printf("\n %s", c[i].name);
// }
}
printf("\nEnter the name of city to search:");
scanf("%s", n);
bisearch(c, 0, i - 1, n);
}
File on city:-
File name:- fcity.txt
los Angeles
pune
itali
america
Awesome programs❤️
ReplyDelete