DATA STRUCTURES LAB
Exercise-1
- a) Write C program that use both recursive and non recursive functions to perform Linear search for a Key value in a given list.
//non recursive functions to perform Linear search
#include<stdio.h>
void main()
{
int n,a[100],se,i;
void linear(int ,int [],int);
printf("Enter searching element:");
scanf("%d",&se);
printf("Enter no of elements:");
scanf("%d",&n);
printf("Enter elements into the array:");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
linear(n,a,se);
}
void linear(int n,int a[100],int se)
{
int i,flag=0;
for(i=0;i<n;i++)
{
if(a[i]==se)
{
flag=1;
printf("Element %d found at %d",se,i);
}
}
if(flag==0)
{
printf("%d was not found",se);
}
}
- b) Write C program that use both recursive and non recursive functions to perform Binary search for a Key value in a given list.
//Binary search without recursion
#include<stdio.h>
void main()
{
int n,a[100],se,i;
void binarysearch(int ,int [],int);
printf("Enter the no of elements:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("Enter %d elements:",i+1);
scanf("%d",&a[i]);
}
printf("Enter searching elements");
scanf("%d",&se);
binarysearch(n,a,se);
}
void binarysearch(int n,int a[100],int se)
{
int low,high,mid,flag=0;
low=0;
high=(n-1);
mid=(low+high)/2;
while(low<high)
{
if(se==a[mid])
{
flag=1;
printf("The element %d is found at %d",se,mid);
break;
}
else if(se<a[mid])
{
low=0;
high=mid-1;
}
else if(se<a[mid])
{
low=mid+1;
high=high;
}
}
if(flag==0)
{
printf("Element %d is not found",se);
}
}
Exercise-2(Sorting-I)
- a) Write C program that implement Bubble sort, to sort a given list of integers in ascending order.
//Bubble sort
#include<stdio.h>
void main()
{
int i,n,a[100],j,temp;
printf("Enter size:");
scanf("%d",&n);
printf("Enter elements into the array:");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
printf("Elements after sorting are:");
for(i=0;i<n;i++)
{
printf("%d,",a[i]);
}
}
- c) Write C program that implement Insertion sort, to sort a given list of integers in ascending order
//Insertion sort
#include<stdio.h>
void main()
{
int n,a[100],i,j,temp;
printf("Enter size:");
scanf("%d",&n);
printf("Enter elements into the array:");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=1;i<n;i++)
{
temp=a[i];
j=i-1;
while((j>=0)&&(temp<a[j]))
{
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
}
printf("Elements after sorting:");
for(i=0;i<n;i++)
{
printf("%d,",a[i]);
}
}
Exercise - 3
- b) Write C program that implement merge sort, to sort a given list of integers in ascending order.
//Merge sort
#include<stdio.h>
void mergesort(int a[],int lb,int ub);
void merge(int a[],int lb,int mid,int ub);
void main()
{
int a[100],i,n;
printf("Enter array size:");
scanf("%d",&n);
printf("Enter elements into the array:\n");
for(i=0;i<n;i++)
{
printf("Enter %d element:",i+1);
scanf("%d",&a[i]);
}
mergesort(a,0,n-1);
printf("The array elements after sorting are:");
for(i=0;i<n;i++)
{
printf("%d,",a[i]);
}
}
void mergesort(int a[],int lb,int ub)
{
int mid;
if(lb<ub)
{
mid=(lb+ub)/2;
mergesort(a,lb,mid);
mergesort(a,mid+1,ub);
merge(a,lb,mid,ub);
}
}
void merge(int a[],int lb,int mid,int ub)
{
int i,j,k;
int b[100];
i=lb;
j=mid+1;
k=lb;
while (i<=mid&&j<=ub)
{
if(a[i]<a[j])
{
b[k]=a[i];
i++;
k++;
}
else
{
b[k]=a[j];
j++;
k++;
}
}
if(i>mid)
{
while(j<=ub)
{
b[k]=a[i];
i++;
k++;
}
}
else
{
while(i<=mid)
{
b[k]=a[i];
i++;
k++;
}
}
for(i=lb;i<=ub;i++)
{
a[i]=b[i];
}
}
Exercise - 4(Singly Linked List)
- a) Write a C program that uses functions to create a singly linked list
- b) Write a C program that uses functions to perform insertion operation on a singly linked list
- c) Write a C program that uses functions to perform deletion operation on a singly linked list
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head=NULL;
void insert_begin();
void insert_end();
void insert_loc();
void delete_begin();
void delete_end();
void delete_loc();
void search();
void display();
void main()
{
int ch;
while(1)
{
printf("1.Insert at beginning");
printf("\n2.Insert at end");
printf("\n3.Insert at location");
printf("\n4.delete at beginning");
printf("\n5.delete at end");
printf("\n6.delete at location");
printf("\n7.search");
printf("\n8.display");
printf("\n9.exit");
printf("\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
insert_begin();
break;
case 2:
insert_end();
break;
case 3:
insert_loc();
break;
case 4:
delete_begin();
break;
case 5:
delete_end();
break;
case 6:
delete_loc();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
printf("No choice found");
break;
}
}
}
void insert_begin()
{
int data;
struct node *newnode=(struct node*)malloc(sizeof(struct node*));
printf("Enter a value to insert:");
scanf("%d",&data);
if(newnode==NULL)
printf("Memmory is full");
else if(head==NULL)
{
newnode->data=data;
newnode->next=NULL;
head=newnode;
}
else
{
newnode->data=data;
newnode->next=head;
head=newnode;
}
}
void insert_end()
{
int data;
struct node *newnode=(struct node*)malloc(sizeof(struct node*));
printf("Enter value to insert:");
scanf("%d",&data);
if(newnode==NULL)
printf("Memory is full");
else if(head==NULL)
{
newnode->data=data;
newnode->next=NULL;
head=newnode;
}
else
{
newnode->data=data;
newnode->next=NULL;
struct node *temp;
temp=head;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newnode;
}
}
void insert_loc()
{
int data,loc;
struct node *newnode=(struct node*)malloc(sizeof(struct node*));
printf("Enter a value to enter:");
scanf("%d",&data);
if(newnode==NULL)
printf("Memory is full");
else if(head==NULL)
{
newnode->data=data;
newnode->next=NULL;
head=newnode;
}
else
{
printf("Enter a location:");
scanf("%d",&loc);
struct node *temp;
temp=head;
while(temp->next!=loc)
{
temp=temp->next;
}
newnode->data=data;
newnode->next=temp->next;
temp->next=newnode;
}
}
void delete_begin()
{
if(head=NULL)
printf("Linked List is empty");
else
{
struct node*temp;
temp=head;
head=head->next;
temp->next=NULL;
free(temp);
}
}
void delete_end()
{
if(head==NULL)
printf("Linked List is empty");
else
{
struct node *temp;
struct node *prev;
prev=head;
temp=head->next;
while(temp->next!=NULL)
{
temp=temp->next;
prev=prev->next;
}
prev->next=NULL;
free(temp);
}
}
void delete_loc()
{
int loc;
if(head=NULL)
printf("Linked List is empty");
else
{
struct node *temp;
struct node *prev;
prev=head;
temp=head->next;
printf("Enter a location:");
scanf("%d",&loc);
while(temp->next!=loc)
{
temp=temp->next;
prev=prev->next;
}
prev->next=temp->next;
temp->next=NULL;
free(temp);
}
}
void search()
{
int se,count=0;
if(head==NULL)
printf("Linked List is empty");
else
{
printf("Enter a searching element");
scanf("%d",&se);
struct node *temp;
temp=head;
while(temp->next!=NULL)
{
if(se==temp->data)
count++;
}
temp=temp->next;
if(count==0)
printf("Element is not found");
else
printf("Element is found %d times",count);
}
}
void display()
{
if(head==NULL)
printf("Linked List is empty");
else
{
struct node *temp;
temp=head;
while(temp->next!=NULL)
{
printf("%d->",temp->data);
temp=temp->next;
}
printf("%d\n",temp->data);
}
}
Subscribe to:
Post Comments
(
Atom
)
No comments