MCA SEM II DATA STRUCTURE
Practical No. 1
Aim: Write a program to Implementation of Circular Queue
Program-
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
class node
{
public:
int data;
node *next;
};
class cirqueue
{
public:
node *rear;
};
void addq(cirqueue *q, int n)
{
node *ptr, *p, *prev;
ptr=new node;
ptr->data=n;
if(q->rear==NULL)
{
q->rear=ptr;
ptr->next=ptr;
}
else
{
ptr->next=q->rear->next;
q->rear->next=ptr;
q->rear=ptr;
}
}
int deleteq(cirqueue *q)
{
node *ptr;
int n;
if(q->rear==NULL)
{
cout<<"\nQueue Empty";
1
MCA SEM II DATA STRUCTURE
return -1;
}
else
{
ptr=q->rear->next;
n=ptr->data;
if(ptr==q->rear)
q->rear=NULL;
else
q->rear->next=ptr->next;
delete ptr;
return n;
}
}
void display(cirqueue q)
{
node *p, *r;
r=p=q.rear->next;
if(p==NULL)
cout<<"\n Circular queue is empty";
else
{
do
{
cout<<"\n"<<p->data;
p=p->next;
}while(p!=r);
}
}
void main()
{
cirqueue q1;
int n,c;
q1.rear=NULL;
do
{
clrscr();
cout<<"\n 1. Add an element";
cout<<"\n 2. Delete an element";
cout<<"\n 3. Display";
cout<<"\n 4. Exit";
cout<<"\n Enter your choice: ";
cin>>c;
switch(c)
{
case 1:
2
MCA SEM II DATA STRUCTURE
cout<<"\nEnter the element to be inserted: ";
cin>>n;
addq(&q1, n);
cout<<"\n Circular queue after addition";
display(q1);
getch();
break;
case 2:
n=deleteq(&q1);
if(n>=0)
cout<<"\nElement deleted: "<<n;
getch();
break;
case 3:
cout<<"\nQueue is";
display(q1);
getch();
break;
default:
exit(1);
}
}while(c!=4);
}
Output:
3
MCA SEM II DATA STRUCTURE
Practical No. 2
Aim: Write a program to implement the Singly Linked List
Program-
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
}*head=NULL;
void insert();
void delete();
void traverse();
void main()
{
int ch;
do{
printf("Enter 1.insert 2.delete 3.traverse\n");
scanf("%d",&ch);
switch(ch)
{
case 1:insert();
break;
case 2:delete();
break;
case 3:traverse();
break;
}
}while(ch<=3);
}
void insert()
{
int value,key,choice;
struct node *n,*temp;
printf("Enter the value \n");
scanf("%d",&value);
n=(struct node *)malloc(sizeof(struct node));
n->data=value;
n->next=NULL;
if(head==NULL)
{
head=n;
}
else
{
printf("Enter 1.beginning 2.end 3.after key");
scanf("%d",&choice);
4
MCA SEM II DATA STRUCTURE
switch(choice)
{
case 1:n->next=head;
head=n;
break;
case 2:temp=head;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=n;
break;
case 3:printf("Enter the key\n");
scanf("%d",&key);
temp=head;
while(temp!=NULL)
{
if(temp->data==key)
{
n->next=temp->next;
temp->next=n;
break;
}
else{
temp=temp->next;
}
}
}
}
}
void traverse()
{
struct node *temp;
temp=head;
while(temp!=NULL)
{
printf("%d\n",temp->data);
temp=temp->next;
}
}
void delete()
{
int ch,key;
struct node *temp,*before;
if(head->next==NULL)
{
head=NULL;
}
else
{
printf("1.beginning 2.end 3.key");
5
MCA SEM II DATA STRUCTURE
scanf("%d",&ch);
switch(ch)
{
case 1:temp=head;
head=temp->next;
temp->next=NULL;
printf("data deleted from list %d\n",temp->data);
break;
case 2:temp=head;
before=NULL;
while(temp->next!=NULL)
{
before=temp;
temp=temp->next;
}
before->next=NULL;
printf("data deleted from list\n");
break;
case 3:temp=head;
before=NULL;
printf("Enter a key\n");
scanf("%d",&key);
while(temp!=NULL)
{
if(head->data==key)
{
head=temp->next;
}
else if(temp->data==key)
{
before->next=temp->next;
temp->next=NULL;
printf("data deleted from list\n");
break;
}
else
{
before=temp;
temp=temp->next;
}
}
}
}
}
OUTPUT:
6
MCA SEM II DATA STRUCTURE
Practical No. 3
Aim: Write a program to implement the Doubly Linked List
Program-
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
}*head=NULL;
void insert();
void delete();
void traverse();
void main()
{
int ch;
do
{
printf("Enter 1.Insert 2.Delete 3.Traverse\n");
scanf("%d",&ch);
switch(ch)
{
case 1: insert();
break;
case 2:delete();
break;
case 3:traverse();
break;
default:printf("Invalid choice");
}
}while(ch<=3);
}
void insert()
{
int value,key,choice;
struct node *new,*temp;
printf("Enter the value to be inserted\n");
scanf("%d",&value);
new=(struct node *)malloc(sizeof(struct node));
new->data=value;
new->next=NULL;
if(head==NULL)
7
MCA SEM II DATA STRUCTURE
{
head=new;
}
else
{
printf("Enter 1.beginning 2.end 3.after key");
scanf("%d",&choice);
switch(choice)
{
case 1:new->next=head;
head=new;
break;
case 2:temp=head;
while(temp->next!=NULL);//to reach 1st node
{
temp=temp->next;
}
temp->next=new;
break;
case 3:printf("Enter the key");
scanf("%d",&key);
temp=head;
while(temp!=NULL)
{
if(temp->data==key)
{
new->next=temp->next;
temp->next=new;
break;
}
else
{
temp=temp->next;
}
}//end of while
}//end of switch
}//end of else
}//end of function
void traverse()
{
struct node *temp;
temp=head;
while(temp!=NULL)
{
printf("%d\n",temp->data);
temp=temp->next;
8
MCA SEM II DATA STRUCTURE
void delete()
{
int ch,key;
struct node *temp,*before;
if(head->next==NULL) //only one node
{
head=NULL;
}
else
{
printf("1.beginning 2.end 3.key");
scanf("%d",&ch);
switch(ch)
{
case 1:temp=head;
head=temp->next;
temp->next=NULL;
printf("%d deleted from list",temp->data);
break;
case 2:temp=head;
before=NULL;
while(temp->next!=NULL)
{
before=temp;
temp=temp->next;
}
before->next=NULL;
printf("%d deleted",temp->data);
break;
case 3:temp=head;
before=NULL;
printf("Enter key ");
scanf("%d",&key);
while(temp!=NULL)
{
if(temp->data==key)
{
before->next=temp->next;
temp->next=NULL;
printf("%d deleted ",temp->data);
break;
}
else{
before=temp;
temp=temp->next;
}
}
}
9
MCA SEM II DATA STRUCTURE
}
}
OUTPUT:
10
MCA SEM II DATA STRUCTURE
Practical No. 4
Aim: Write a program to implement the Insertion Sort
Program:
#include <stdio.h>
int main()
int n, array[1000], c, d, t;
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
for (c = 1 ; c <= n - 1; c++) {
d = c;
while ( d > 0 && array[d-1] > array[d]) {
t = array[d]; array[d] = array[d-1];
array[d-1] = t;
d--;
printf("Sorted list in ascending order:\n");
11
MCA SEM II DATA STRUCTURE
for (c = 0; c <= n - 1; c++) {
printf("%d\n", array[c]);
return 0;
Output of program:
12
MCA SEM II DATA STRUCTURE
Practical No. 5
Aim: Write a program to implement the Selection Sort
Program:
#include <stdio.h>
int main()
int array[100], n, c, d, position, swap;
printf("Enter number of elements\n");
scanf("%d", &n);
printf("Enter %d integers\n", n);
for (c = 0; c < n; c++)
scanf("%d", &array[c]);
for (c = 0; c < (n - 1); c++)
position = c;
for (d = c + 1; d < n; d++)
if (array[position] > array[d])
position = d;
if (position != c)
swap = array[c];
array[c] = array[position];
array[position] = swap;
13
MCA SEM II DATA STRUCTURE
printf("Sorted list in ascending order:\n");
for (c = 0; c < n; c++)
printf("%d\n", array[c]);
return 0;
Output of program:
14
MCA SEM II DATA STRUCTURE
Practical No. 6
Aim: Write a program to implement the Quick Sort.
Program:
#include<iostream.h>
using namespace std;
void quicksort(int ,int ,int);
int partition(int ,int,int);
int partition(int *a,int s,int e)
{
int piviot=a[e];
int pind=s;
int i,t;
for(i=s;i<e;i++)
{
if(a[i]<=piviot)
{
t=a[i];
a[i]=a[pind];
a[pind]=t;
pind++;
}
}
t=a[e];
a[e]=a[pind];
a[pind]=t;
return pind;
}
void quicksort(int *a,int s,int e)
{
if(s<e)
{
int pind=partition(a,s,e);
quicksort(a,s,pind-1);
quicksort(a,pind+1,e);
}
}
int main()
{
int n;
cout<<"Enter number of elements"<<endl;
cin>>n;
int a[n];
cout<<"Enter the array :- ";
for(int i=0;i<n;i++)
{
cin>>a[i];
}
15
MCA SEM II DATA STRUCTURE
quicksort(a,0,n-1);
cout<<"Sorted array is :- ";
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
return 0;
}
Output
Enter number of elements
5
Enter the array :- 11 1 2 3 50
Sorted array is :- 1 2 3 11 50
16
MCA SEM II DATA STRUCTURE
Practical No. 7
Aim: Write a program to implement the Binary Search Tree
Program:
#include<stdlib.h>
#include<stdio.h>
struct node
{
int data;
struct node *right,*left;
}*root=NULL;
struct node *insert(struct node *r,int val)
{
struct node *n,*temp,*parent;
n=(struct node *)malloc(sizeof(struct node));
n->data=val;
n->right=NULL;
n->left=NULL;
if(r==NULL)
{
r=n;
r->left=NULL;
r->right=NULL;
}
else
{
parent=NULL;
temp=r;
while(temp!=NULL)
{
parent=temp;
if(val<temp->data)
temp=temp->left;
else
temp=temp->right;
}
if(val<parent->data)
parent->left=n;
else
parent->right=n;
}
return r;
}
void preorder(struct node *r)
{
if(r!=NULL)
{
17
MCA SEM II DATA STRUCTURE
printf("%d \t",r->data);
preorder(r->left);
preorder(r->right);
}
}
void inorder(struct node *r)
{
if(r!=NULL)
{
inorder(r->left);
printf("%d \t",r->data);
inorder(r->right);
}
}
void postorder(struct node *r)
{
if(r!=NULL)
{
postorder(r->left);
postorder(r->right);
printf("%d \t",r->data);
}
}
void main()
{
int val,opt;
struct node *ptr;
do
{
printf("Enter 1.insert 2.Preorder 3.Postorder 4.Inorder");
scanf("%d",&opt);
switch(opt)
{
case 1:
printf("Enter value");
scanf("%d",&val);
root=insert(root,val);
break;
case 2:
preorder(root);
break;
case 3:
postorder(root);
break;
case 4:
inorder(root);
break;
18
MCA SEM II DATA STRUCTURE
}
}
while(opt<5);
}
OUTPUT-
Enter 1.insert 2.Preorder 3.Postorder 4.Inorder1
Enter value 150
Enter 1.insert 2.Preorder 3.Postorder 4.Inorder1
Enter value120
Enter 1.insert 2.Preorder 3.Postorder 4.Inorder1
Enter value135
Enter 1.insert 2.Preorder 3.Postorder 4.Inorder1
Enter value170
Enter 1.insert 2.Preorder 3.Postorder 4.Inorder1
Enter value160
Enter 1.insert 2.Preorder 3.Postorder 4.Inorder4
120 135 150 160 170 Enter 1.insert 2.Preorder 3.Postorder 4.Inorder5
19
MCA SEM II DATA STRUCTURE
Practical No. 8
Aim: Write a program to implement the stack using array
Program:
#include <stdlib.h>
int stack[100];
void push();
int pop();
void traverse();
int is_empty();
int top_element();
int top = 0;
int main()
int element, choice;
for (;;)
printf("Stack Operations.\n");
printf("1. Insert into stack (Push operation).\n");
printf("2. Delete from stack (Pop operation).\n");
printf("3. Print top element of stack.\n");
printf("4. Check if stack is empty.\n");
printf("5. Traverse stack.\n");
printf("6. Exit.\n");
printf("Enter your choice.\n");
scanf("%d",&choice);
20
MCA SEM II DATA STRUCTURE
switch (choice)
case 1:
if (top == 5)
printf("Error: Overflow\n\n");
else {
printf("Enter a value to insert.\n");
scanf("%d", &element);
push(element);
break;
case 2:
if (top == 0)
printf("Error: Underflow.\n\n");
else {
element = pop();
printf("Element removed from the stack is %d.\n", element);
break;
case 3:
if (!is_empty()) {
element = top_element();
printf("Element at the top of the stack is %d\n\n", element);
else
printf("The stack is empty.\n\n");
21
MCA SEM II DATA STRUCTURE
break;
case 4:
if (is_empty())
printf("The stack is empty.\n\n");
else
printf("The stack isn't empty.\n\n");
break;
case 5:
traverse();
break;
case 6:
exit(0);
void push(int value) {
stack[top] = value;
top++;
int pop() {
top--;
return stack[top];
void traverse() {
22
MCA SEM II DATA STRUCTURE
int d;
if (top == 0) {
printf("The stack is empty.\n\n");
return;
printf("There are %d elements in the stack.\n", top);
for (d = top - 1; d >= 0; d--)
printf("%d\n", stack[d]);
printf("\n");
int is_empty() {
if (top == 0)
return 1;
else
return 0;
int top_element() {
return stack[top-1];
OUTPUT:
23
MCA SEM II DATA STRUCTURE
Practical No. 9
Aim: Write a program to implement the Linear Searching, to find an element in array.
Program:
#include <stdio.h>
#define MAX 5
int linearSearch(int *a,int n)
{
int i,pos=-1;
for(i=0;i< MAX; i++)
{
if(a[i]==n)
{
pos=i;
break;
}
}
return pos;
}
int main()
{
int i,n,arr[MAX];
int num; /* element to search*/
int position;
printf("\nEnter array elements:\n");
for(i=0;i< MAX;i++)
scanf("%d",&arr[i]);
printf("\nNow enter element to search :");
scanf("%d",&num);
position=linearSearch(arr,num);
if(num==-1)
printf("Element not found.\n");
else
printf("Element found @ %d position.\n",position);
return 0;
}
24
MCA SEM II DATA STRUCTURE
Output
Enter array elements:
10
20
15
30
40
Now enter element to search :15
Element found @ 2 position.
25
MCA SEM II DATA STRUCTURE
Practical No. 10
Aim: Write a program to implement the Bubble Sort
Program:
#include <stdio.h>
#define MAX 100
int main()
{
int arr[MAX],limit;
int i,j,temp;
printf("Enter total number of elements: ");
scanf("%d",&limit);
/*Read array*/
printf("Enter array elements: \n");
for(i=0; i<limit; i++)
{
printf("Enter element %3d: ",i+1);
scanf("%d",&arr[i]);
}
/*sort elements in Ascending Order*/
for(i=0; i<(limit-1); i++)
{
for(j=0; j<(limit-i-1); j++)
{
if(arr[j]>arr[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
printf("Array elements in Ascending Order:\n");
for(i=0; i<limit; i++)
printf("%d ",arr[i]);
printf("\n");
/*sort elements in Descending Order*/
for(i=0; i<(limit-1); i++)
{
for(j=0; j<(limit-i-1); j++)
{
if(arr[j]<arr[j+1])
{
26
MCA SEM II DATA STRUCTURE
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
printf("Array elements in Descending Order:\n");
for(i=0; i<limit; i++)
printf("%d ",arr[i]);
printf("\n");
return 0;
}
Output
Enter total number of elements: 10
Enter array elements:
Enter element 1: 12
Enter element 2: 34
Enter element 3: 43
Enter element 4: 32
Enter element 5: 21
Enter element 6: 1
Enter element 7: 11
Enter element 8: 2
Enter element 9: 3
Enter element10: 100
Array elements in Ascending Order:
1 2 3 11 12 21 32 34 43 100
Array elements in Descending Order:
100 43 34 32 21 12 11 3 2 1
27
