BCA 3RD SEM DATA STRUCTURES RECORD PROGRAMS

1. Write a C program to implement Matrix multiplication

#include<stdio.h>
#include<conio.h>
void main()
{
int a[2][2],b[2][2],c[2][2],i,j,k;
clrscr();
printf("enter the elements in matrix a\n");
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
printf("enter a element\n");
scanf("%d",&a[i][j]);
}
}
printf("enter the elements in matrix b\n");
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
printf("enter a element\n");
scanf("%d",&b[i][j]);
}
}
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
c[i][j]=0;
for(k=0;k<2;k++)
{
c[i][j]=c[i][j]+a[i][k]+b[k][j];
}
}
}
printf("the elements in matrix a are\n");
for(i=0;i<2;i++)
{
NATIONAL DEGREE COLLEGE, NANDYAL Page 1
 for(j=0;j<2;j++)
{
printf("%d\t",a[i][j]);
}
printf("\n");
}
printf("the elements in matrix b are\n");
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
printf("%d\t",b[i][j]);
}
printf("\n");
}
printf("the multiplication of matrix a and b are\n");
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
printf("%d\t",c[i][j]);
}
printf("\n");
}
getch();
}
Output:

2. Write a c program to implement stack using arrays.

#include <stdio.h>
#include<conio.h>
#define max 5
int stack[max],top=-1;

NATIONAL DEGREE COLLEGE, NANDYAL Page 2

 void push();
void pop();
void show();
void main()
{
int n,choice=0;
clrscr();
printf("Enter the number of elements in the stack ");
scanf("%d",&n);
printf("*********Stack operations using array*********");
printf("\n----------------------------------------------\n");
while(choice != 4)
{
printf("Chose one from the below options...\n");
printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");
printf("\n Enter your choice \n");
scanf("%d",&choice);
switch(choice)
{
case 1:push();
break;
case 2:pop();
break;
case 3:show();
break;
case 4:exit(0);
default:printf("Invalid choice ");
}
}
getch();
}
void push()
{
int val;
if(top==max-1)
{
printf("\n stack is full or Overflow\n");
}
else
{

NATIONAL DEGREE COLLEGE, NANDYAL Page 3

 printf("Enter the value\n");
scanf("%d",&val);
top = top +1;
stack[top] = val;
}
}
void pop ()
{
int val;
if(top == -1)
{
printf("stack is empty or Underflow\n");
}
else
{
val=stack[top];
top = top -1;
printf("the element deleted successfully: %d\n",val);
}
}
void show()
{
int i;
for (i=top;i>=0;i--)
{
printf("%d\n",stack[i]);
}
if(top == -1)
{
printf("Stack is empty");
}
}
Output:

NATIONAL DEGREE COLLEGE, NANDYAL Page 4

 3. Write a c program to implement queue using arrays

#include<stdio.h>
#include<stdlib.h>
#define maxsize 5
void insert();
void delete();
void display();
int queue[maxsize];
int front = -1, rear = -1;
void main()
{
int choice;
clrscr();
while(choice!=4)
{
printf("\n******************MainMenu***********************\n");
printf("\n==================================================\n");
printf("\n1.insert an element\n2.Delete an element\n3.Display the
queue\n4.Exit\n");
printf("\nEnter your choice ?");
scanf("%d",&choice);
switch(choice)
{
case 1:insert();
break;
case 2:delete();
break;
case 3:display();
break;
case 4:exit(0);
break;
default:printf("\n Invalid choice??\n");
}
}
getch();
}
void insert()
{
int item;
NATIONAL DEGREE COLLEGE, NANDYAL Page 5
 if(rear == maxsize-1)
{
printf("\n Queue is full or OVERFLOW\n");
}
else
{
if(front==-1)
front=0;
printf("\nEnter the element\n");
scanf("\n%d",&item);
rear = rear+1;
queue[rear] = item;
printf("\nValue inserted ");
}
}
void delete()
{
int item;
if(front == -1 || front>rear)
{
printf("\n Queue is empty or UNDERFLOW\n");
}
else
{
item = queue[front];
front = front + 1;
printf("\n element deleted %d \n",item);
}
}
void display()
{
int i;
if(front == -1 || front>rear)
{
printf("\nQueue is Empty\n");
}
else
{
printf("\nprinting values .....\n");
for(i=front;i<=rear;i++)

NATIONAL DEGREE COLLEGE, NANDYAL Page 6

 {
printf("\n%d\n",queue[i]);
}
}
}
Output:

4. Write a c program to implement single linked list using the methods

insert(),delete() and display()
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next;
};
struct Node* head = NULL;
void insert()
{
int item;
struct Node *new_node,*temp;
new_node = (struct Node*) malloc(sizeof(struct Node));
printf("enter a element\n");
scanf("%d",&item);
new_node->data = item;
new_node->next = NULL;
if(head==NULL)
{
head = new_node;
}
else
{
temp=head;

NATIONAL DEGREE COLLEGE, NANDYAL Page 7

 while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=new_node;
}
}
void del()
{
struct Node *temp;
if(head==NULL)
{
printf("list is empty\n");
}
else
{
temp=head;
head=head->next;
free(temp);
}
}
void display()
{
struct Node* ptr;
ptr = head;
while (ptr != NULL)
{
printf("%d\t",ptr->data);
ptr = ptr->next;
}
}
void main()
{
int choice=0;
clrscr();
while(choice != 4)
{
printf("\n\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");

NATIONAL DEGREE COLLEGE, NANDYAL Page 8

 printf("\n1.Insert \n2.Delete \n3.Show\n4.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:insert();
break;
case 2:del();
break;
case 3:display();
break;
case 4:exit(0);
break;
default:printf("Please enter valid choice..");
}
}
getch();
}
Output:

5. Write a c program to implement stack using linked list

#include <stdio.h>
#include <stdlib.h>
void push();
void pop();
void display();
struct node
{
int val;
struct node *next;
};
struct node *head;

void main()
{
int choice=0;
clrscr();
printf("\n*********Stack operations using linked list*********\n");
printf("\n----------------------------------------------\n");
while(choice != 4)
{
printf("\n\nChose one from the below options...\n");

NATIONAL DEGREE COLLEGE, NANDYAL Page 9

 printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");
printf("\n Enter your choice \n");
scanf("%d",&choice);
switch(choice)
{
case 1:push();
break;
case 2:pop();
break;
case 3:display();
break;
case 4:exit(0);
break;
default:printf("Invalid choice\n");
}
}
getch();
}
void push()
{
int val;
struct node *ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("not able to push the element");
}
else
{
printf("Enter the value");
scanf("%d",&val);
if(head==NULL)
{
ptr->val = val;
ptr -> next = NULL;
head=ptr;
}
else
{
ptr->val = val;
ptr->next = head;
head=ptr;

}
printf("Item pushed");

}
}

void pop()
{
int item;
struct node *ptr;
if (head == NULL)
{
printf("Underflow");
}
else

NATIONAL DEGREE COLLEGE, NANDYAL Page 10

 {
item = head->val;
ptr = head;
head = head->next;
free(ptr);
printf("Item popped :%d\n",item);

}
}
void display()
{
int i;
struct node *ptr;
ptr=head;
if(ptr == NULL)
{
printf("Stack is empty\n");
}
else
{
printf("Printing Stack elements \n");
while(ptr!=NULL)
{
printf("%d\n",ptr->val);
ptr = ptr->next;
}
}
}
Output:

6. Write a c program to implement queue using linked list

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *front;
struct node *rear;
void insert();
void delete();
void display();
void main()
{

NATIONAL DEGREE COLLEGE, NANDYAL Page 11

 int choice;
clrscr();
while(choice != 4)
{
printf("\n*************************Main Menu*****************************\n");
printf("\n===============================================
==================\n");
printf("\n1.insert an element\n2.Delete an element\n3.Display the
queue\n4.Exit\n");
printf("\nEnter your choice ?");
scanf("%d",&choice);
switch(choice)
{
case 1:insert();
break;
case 2:delete();
break;
case 3:display();
break;
case 4:exit(0);
break;
default:printf("\nEnter valid choice??\n");
}
}
getch();
}
void insert()
{
struct node *ptr;
int item;

ptr = (struct node *) malloc (sizeof(struct node));

if(ptr == NULL)
{
printf("\nOVERFLOW\n");
}
else
{
printf("\nEnter value?\n");
scanf("%d",&item);
ptr -> data = item;
if(front == NULL)
{
front = ptr;

NATIONAL DEGREE COLLEGE, NANDYAL Page 12

 rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}
else
{
rear -> next = ptr;
rear = ptr;
rear->next = NULL;
}
}
}
void delete ()
{
struct node *ptr;
if(front == NULL)
{
printf("\nUNDERFLOW\n");

}
else
{
ptr = front;
front = front -> next;
free(ptr);
}
}
void display()
{
struct node *ptr;
ptr = front;
if(front == NULL)
{
printf("\nEmpty queue\n");
}
else
{ printf("\nprinting values .....\n");
while(ptr != NULL)
{
printf("\n%d\n",ptr -> data);
ptr = ptr -> next;
}
}
}

NATIONAL DEGREE COLLEGE, NANDYAL Page 13

 7. Give a solution to towers of Hanoi using C program

#include <stdio.h>
#include<conio.h>
void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod)
{
if (n == 1)
{
printf("\n Move disk 1 from rod %c to rod %c", from_rod, to_rod);
return;
}
towerOfHanoi(n-1, from_rod, aux_rod, to_rod);
printf("\n Move disk %d from rod %c to rod %c", n, from_rod, to_rod);
towerOfHanoi(n-1, aux_rod, to_rod, from_rod);
}
void main()
{
int n = 4;
clrscr();
towerOfHanoi(n, 'A', 'C', 'B');
getch();
}
Output:

8. Write a c program to implement bubble sort

#include<stdio.h>
#include<conio.h>
void main()
{
int a[50],n,i,j,temp;
clrscr();
printf("enter how many elemnts\n");
scanf("%d",&n);

NATIONAL DEGREE COLLEGE, NANDYAL Page 14

 printf("enter %d elements in an array\n",n);
for(i=0;i<n;i++)
{
printf("enter a element\n");
scanf("%d",&a[i]);
}
printf("before sorting the elemnts in an array are\n");
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
printf("\nafter sorting the elemnts in an array are\n");
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
getch();
}
Output:

9. Write a c program to implement insertion sort

#include <math.h>
#include <stdio.h>
#include<conio.h>

NATIONAL DEGREE COLLEGE, NANDYAL Page 15

 void insertionSort(int arr[], int N)
{
int i,key,j;
for (i = 1; i < N; i++)
{
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}

void main()
{
int arr[100],i,n;
clrscr();
printf("enter how many elemnts\n");
scanf("%d",&n);
printf("enter %d elements in an array\n",n);
for(i=0;i<n;i++)
{
printf("enter a element\n");
scanf("%d",&arr[i]);
}
printf("\nbefore sorting the elemnts in an array are\n");
for(i=0;i<n;i++)
{
printf("%d\t",arr[i]);
}
insertionSort(arr, n);

printf("after sorting an array: ");

for (i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}

NATIONAL DEGREE COLLEGE, NANDYAL Page 16

 printf("\n");

getch();
}
Output:

10.Write a c program to implement quick sort

#include<stdio.h>
#include<conio.h>
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
int partition(int arr[], int low, int high)
{
int i,j,pivot;
pivot = arr[high];
i = (low - 1);

for (j = low; j <= high - 1; j++)

{
if (arr[j] < pivot)
{
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high)

NATIONAL DEGREE COLLEGE, NANDYAL Page 17

 {
if (low < high)
{
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}

void printArray(int arr[], int size)

{
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}

void main()
{
int arr[100],n,i;
clrscr();
printf("enter how many elemnts\n");
scanf("%d",&n);
printf("enter %d elements in an array\n",n);
for(i=0;i<n;i++)
{
printf("enter a element\n");
scanf("%d",&arr[i]);
}
printf("before sorting the elemnts in an array are\n");
for(i=0;i<n;i++)
{
printf("%d\t",arr[i]);
}
quickSort(arr, 0, n - 1);
printf("after sorting an array: \n");
printArray(arr, n);
getch();
}
Output:

NATIONAL DEGREE COLLEGE, NANDYAL Page 18