UNITED INSTITUTE OF TECHNOLOGY

DATA STRUCTURE LAB (BCS351)

Q.1) Write a program to perform following operations on 2D array:

a.) Add two matrices of size MxN and PxQ.

#include <stdio.h>
int main()
{
int i, j, m, n, p, q;
printf("Enter row and column for 1st matrix: ");
scanf("%d%d", &m, &n);
printf("Enter the array:");
int arr1[m][n];
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
scanf("%d", &arr1[i][j]);
}
}
printf("Enter row and column for 2nd matrix: ");
scanf("%d%d", &p, &q);
printf("Enter the array:");
int arr2[p][q];
for (i = 0; i < p; i++)
{
for (j = 0; j < q; j++)
{
scanf("%d", &arr2[i][j]);
}
}
if (m != p && n != q)
{
printf("Addition can not perform...");
return 0;
}
printf("Addition of two matrix:\n");

for (i = 0; i < m; i++)

{
for (j = 0; j < n; j++)
{
printf("%d ", arr1[i][j] + arr2[i][j]);
}
printf("\n");
}

return 0;
}
Output:-

Enter row and column for 1st matrix: 3 3

Enter the array:1 2 3 4 5 6 7 8 9
Enter row and column for 2nd matrix: 3 3
Enter the array:1 2 3 4 5 6 7 8 9
Addition of two matrix:
246
8 10 12
14 16 18

b. Subtract two matrices of size MxN and PxQ.

#include <stdio.h>

int main()
{
int i, j, m, n, p, q;
printf("Enter row and column for 1st matrix: ");
scanf("%d%d", &m, &n);
printf("Enter the array:");
int arr1[m][n];
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
scanf("%d", &arr1[i][j]);
}
}
printf("Enter row and column for 2nd matrix: ");
scanf("%d%d", &p, &q);
printf("Enter the array:");
int arr2[p][q];
for (i = 0; i < p; i++)
{
for (j = 0; j < q; j++)
{
scanf("%d", &arr2[i][j]);
}
}
if (m != p && n != q)
{
printf("Subtraction can not perform...");
return 0;
}
printf("Subtraction of two matrix:\n");

for (i = 0; i < m; i++)

{
 for (j = 0; j < n; j++)
{
printf("%d ", arr1[i][j]- arr2[i][j]);
}
printf("\n");
}

return 0;
}

Output:-

Enter row and column for 1st matrix: 3 3

Enter the array:11 22 33 44 55 66 77 88 99
Enter row and column for 2nd matrix: 3 3
Enter the array:10 20 30 40 50 60 70 80 90
Subtraction of two matrix:
123
456
789

c. Multiply two matrices of size MxN and PxQ.

#include <stdio.h>

int main()
{
int i, j,k, m, n, p, q;
printf("Enter row and column for 1st matrix: ");
scanf("%d%d", &m, &n);
printf("Enter the array:");
int arr1[m][n];
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
scanf("%d", &arr1[i][j]);
}
}
printf("Enter row and column for 2nd matrix: ");
scanf("%d%d", &p, &q);
printf("Enter the array:");
int arr2[p][q];
for (i = 0; i < p; i++)
{
for (j = 0; j < q; j++)
{
 scanf("%d", &arr2[i][j]);
}
}
printf("1st matrix:\n");
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
printf("%d ",arr1[i][j]);
}
printf("\n");
}
printf("\n2nd matrix:\n");
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
printf("%d ",arr2[i][j]);
}
printf("\n");
}
if (m != p && n != q)
{
printf("Multiplication can not perform...");
return 0;
}
int res[m][n];
printf("Multiplication of two matrix:\n");
for(i=0; i<m; i++)
{
for(j=0; j<n; j++)
{
res[i][j]=0;
for(k=0; k<m; k++)
{
res[i][j]=res[i][j]+arr1[i][k]*arr2[k][j];
}
}
}
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
printf("%d ",res[i][j]);
}
printf("\n");
}

return 0;
}
Output:-

Enter row and column for 1st matrix: 3 3

Enter the array:1 2 3 4 5 6 7 8 9
Enter row and column for 2nd matrix: 3 3
Enter the array:1 2 3 4 5 6 7 8 9
1st matrix:
123
456
789

2nd matrix:
123
456
789
Multiplication of two matrix:
30 36 42
66 81 96
102 126 150

d. Find Transpose of MxN Matrix.

#include <stdio.h>

int main()
{
int i, j, m, n;
printf("Enter row and column for matrix: ");
scanf("%d%d", &m, &n);
printf("Enter the array:");
int arr1[m][n];
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
scanf("%d", &arr1[i][j]);
}
}
int trans[n][m];
printf("Matrix:\n");
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
printf("%d ",arr1[i][j]);
}
printf("\n");
}
 for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
trans[j][i]=arr1[i][j];
}
}
printf("Transpose of matrix:\n");
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
printf("%d ",trans[i][j]);
}
printf("\n");
}

return 0;
}

Output:-

Enter row and column for matrix: 3 3

Enter the array:1 2 3 4 5 6 7 8 9
Matrix:
123
456
789
Transpose of matrix:
147
258
369

e. Check whether a Matrix is Sparse matrix or not.

#include <stdio.h>

int main()
{
int i, j, m, n;
int flag=0;
printf("Enter row and column for matrix: ");
scanf("%d%d", &m, &n);
printf("Enter the array:");
int arr1[m][n];
for (int i = 0; i < m; i++)
{
 for (int j = 0; j < n; j++)
{
scanf("%d", &arr1[i][j]);
}
}
printf("Matrix:\n");
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{ if(arr1[i][j]==0)
flag++;
printf("%d ",arr1[i][j]);
}
printf("\n");
}
int size=m*n;
if(flag>size/2)
{
printf("The given matrix is sparse matrix..");
}
else
{
printf("The given matrix is not sparse matrix..");
}
return 0;
}

Output:-

Enter row and column for matrix: 3 3

Enter the array:0 0 1 0 0 4 0 0 0
Matrix:
001
004
000
The given matrix is sparse matrix..
f. Generate Triplet of Sparse Matrix using array.

#include <stdio.h>

int main()
{
int i, j, m, n;

printf("Enter row and column for matrix: ");

scanf("%d%d", &m, &n);
printf("Enter the array:");
int arr1[m][n];
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
scanf("%d", &arr1[i][j]);
}
}
printf("Matrix:\n");
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
printf("%d ",arr1[i][j]);
}
printf("\n");
}
int triplet[m*n][n];
int k=0;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if(arr1[i][j]!=0)
{
triplet[k][0]=i;
triplet[k][1]=j;
triplet[k][2]=arr1[i][j];
k++;
}
}
}
printf("Triplet representation:\n");
printf("Row\tCol\tValue\n");
for (int i = 0; i < k; i++)
{
for (int j = 0; j < 3; j++)
{
printf("%d\t",triplet[i][j]);
}
 printf("\n");
}

return 0;
}

Output:-

Enter row and column for matrix: 3 3

Enter the array:0 1 0 0 5 0 0 7 0
Matrix:
010
050
070
Triplet representation:
Row Col Value
0 1 1
1 1 5
2 1 7

g. Generate Triplet of Sparse Matrix using linked list.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {

int row, col, value;
struct Node* next;
} Node;

Node* createNode(int row, int col, int value) {

Node* newNode = (Node*)malloc(sizeof(Node));
newNode->row = row;
newNode->col = col;
newNode->value = value;
newNode->next = NULL;
return newNode;
}

Node* insert(Node* head, int row, int col, int value) {

Node* newNode = createNode(row, col, value);
if (head == NULL) {
return newNode;
}
Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
 temp->next = newNode;
return head;
}

void display(Node* head) {

printf("Row\tCol\tValue\n");
while (head != NULL) {
printf("%d\t%d\t%d\n", head->row, head->col, head->value);
head = head->next;
}
}

int main() {
int m, n, value;
printf("Enter row and column for matrix: ");
scanf("%d%d", &m, &n);

int arr1[m][n];
printf("Enter the array:");
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &arr1[i][j]);
}
}

printf("Matrix:\n");
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", arr1[i][j]);
}
printf("\n");
}

Node* head = NULL;

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (arr1[i][j] != 0) {
head = insert(head, i, j, arr1[i][j]);
}
}
}

printf("Triplet representation:\n");
display(head);

return 0;
}
Output:-
Enter row and column for matrix: 3 3
Enter the array:1 0 0 3 0 0 0 7 0
Matrix:
100
300
070
Triplet representation:
Row Col Value
0 0 1
1 0 3
2 1 7

2) Write a program to add two polynomials of single variable using linked list

#include<stdio.h>
#include<stdlib.h>
struct node
{
int coef,exp;
struct node *link;
} *newnode,*temp;
void insert(struct node **p,int c,int e)
{
newnode=(struct node*)malloc (sizeof(struct node));
newnode->exp=e;
newnode->coef=c;
newnode->link =NULL;
if(*p==NULL)
*p=newnode;
else
{
temp=*p;
while (temp->link!=NULL)
{
temp=temp->link;
}
temp->link=newnode;
}
}
void traverse(struct node*p)
{
printf("\n");
temp=p;
while (temp!=NULL)
{
if (temp->link==NULL)
 printf ("%dx^%d",temp->coef,temp->exp);
else {
printf ("%dx^%d+",temp->coef,temp->exp);
}
temp=temp->link;

}
}
struct node* add(struct node *p1,struct node *p2)
{

struct node *p3 = NULL;

while(p1!=NULL&&p2!=NULL)
{
if (p1->exp>p2->exp)
{
insert(&p3,p1->coef,p1->exp);
p1=p1->link;
}
else if (p2->exp>p1->exp)
{
insert(&p3,p2->coef,p2->exp);
p2=p2->link;
}
else if (p1->exp==p2->exp)
{
insert (&p3,p1->coef+p2->coef,p1->exp);
p1=p1->link;
p2=p2->link;
}
}
while(p1!=NULL)
{
insert (&p3,p1->coef,p1->exp);
p1=p1->link;
}
while(p2!=NULL)
{
insert (&p3,p2->coef,p2->exp);
p2=p2->link;
}
return p3;
}
int main()
{
struct node *p1=NULL,*p2=NULL,*result=NULL;
//2x^3+5x^2+3x+4
insert (&p1,2,3);
insert (&p1,5,2);
insert (&p1,3,1);
insert (&p1,4,0);
traverse(p1);
 //3x^2+2x+3
insert (&p2,3,2);
insert (&p2,2,1);
insert (&p2,3,0);
traverse(p2);
printf("\nAddition of two given polynomials : ");
result=add(p1,p2);
traverse(result);
return 0;
}

Output:-

2x^3+5x^2+3x^1+4x^0
3x^2+2x^1+3x^0
Addition of two given polynomials :
2x^3+8x^2+5x^1+7x^0

3) Write a program to subtract two polynomials of single variable using linked

list

#include<stdio.h>
#include<stdlib.h>
struct node
{
int coef,exp;
struct node *link;
} *newnode,*temp;
void insert(struct node **p,int c,int e)
{
newnode=(struct node*)malloc (sizeof(struct node));
newnode->exp=e;
newnode->coef=c;
newnode->link =NULL;
if(*p==NULL)
*p=newnode;
else
{
temp=*p;
while (temp->link!=NULL)
{
temp=temp->link;
}
temp->link=newnode;
}
}
void traverse(struct node*p)
{
printf("\n");
temp=p;
while (temp!=NULL)
{
if (temp->link==NULL)
printf ("%dx^%d",temp->coef,temp->exp);
else {
printf ("%dx^%d+",temp->coef,temp->exp);
}
temp=temp->link;

}
}
struct node* add(struct node *p1,struct node *p2)
{

struct node *p3 = NULL;

while(p1!=NULL&&p2!=NULL)
{
if (p1->exp>p2->exp)
{
insert(&p3,p1->coef,p1->exp);
p1=p1->link;
}
else if (p2->exp>p1->exp)
{
insert(&p3,p2->coef,p2->exp);
p2=p2->link;
}
else if (p1->exp==p2->exp)
{
insert (&p3,p1->coef-p2->coef,p1->exp);
p1=p1->link;
p2=p2->link;
}
}
while(p1!=NULL)
{
insert (&p3,p1->coef,p1->exp);
p1=p1->link;
}
while(p2!=NULL)
{
insert (&p3,p2->coef,p2->exp);
p2=p2->link;
}
return p3;
}
int main()
{
struct node *p1=NULL,*p2=NULL,*result=NULL;
//7x^3+5x^2+3x+4
insert (&p1,7,3);
insert (&p1,5,2);
insert (&p1,3,1);
insert (&p1,4,0);
traverse(p1);
//3x^2+2x+3
insert (&p2,3,2);
insert (&p2,2,1);
insert (&p2,3,0);
traverse(p2);
printf("\n Subtraction of two given polynomials : ");
result=add(p1,p2);
traverse(result);
return 0;
}

Output:-

7x^3+5x^2+3x^1+4x^0
3x^2+2x^1+3x^0
Subtraction of two given polynomials :
7x^3+2x^2+1x^1+1x^0

4) Write a choice based program to perform following operations in Array.

A) Insert a new element at beginning
B) Insert a new element at last.
C) Insert a new element at any position k.
D) Delete an element from beginning
E) Delete an element from last.
F) Delete an element from any position k.
G) Print Array.

#include<stdio.h>
#define size 10
int arr[size];
int n;
void insertbeg(int num)
{ int i;
if(n==size)
{
 printf("\n Overflow\n");
return;
}
for(i=n;i>=0;i--)
{
arr[i]=arr[i-1];
}
arr[0]=num;
n++;
}
void insertlast(int num)
{
if(n==size)
{
printf("\n Overflow\n");
return;
}
int i;
arr[n]=num;
n++;
}
void inserAtposition(int num,int pos)
{ int i;
if(n==size)
{
printf("\n Overflow\n");
return;
}
for(i=n;i>=pos;i--)
{
arr[i]=arr[i-1];
}
arr[pos-1]=num;
n++;

}
void print()
{ int i;
for(i=0;i<n;i++)
{
printf("%d ",arr[i]);
}
printf("\n");
}
void deletebeg()
{ int i;
for(i=0;i<n;i++)
{
arr[i]=arr[i+1];
}
arr[n-1]=' ';
n--;
}
void deleteAtposition(int pos)
{ int i;
for(i=pos-1;i<n;i++)
{
arr[i]=arr[i+1];
}
arr[n-1]=' ';
n--;

}
void deletelast()
{
arr[n-1]=' ';
n--;
}
int main()
{ n=0;
int ch,num,p;
while(1)
{
printf("\n Enter 1 for insertAtbeg...");
printf("\n Enter 2 for insertAtlast...");
printf("\n Enter 3 for insertAtposition...");
printf("\n Enter 4 for deleteAtbeg...");
printf("\n Enter 5 for deleteAtlast...");
printf("\n Enter 6 for deletetAtposition...");
printf("\n Enter 7 for print...");
printf("\n Enter 8 for exit...\n");
scanf("%d",&ch);
switch (ch)
{
case 1:
printf("Enter number: ");
scanf("%d",&num);
insertbeg(num);
break;
case 2:
printf("Enter number: ");
scanf("%d",&num);
insertlast(num);
break;
case 3:
printf("Enter number and position: ");
scanf("%d%d",&num,&p);
inserAtposition(num,p);
break;
case 4:
deletebeg();
break;
case 5:
deletelast();
 break;
case 6:
printf("Enter position: ");
scanf("%d",&p);
deleteAtposition(p);
break;
case 7:
print();
break;
default:
printf("Unvalid Choice \n");
break;
}
}
}

Output:-

Enter 1 for insertAtbeg...

Enter 2 for insertAtlast...
Enter 3 for insertAtposition...
Enter 4 for deleteAtbeg...
Enter 5 for deleteAtlast...
Enter 6 for deletetAtposition...
Enter 7 for print...
Enter 8 for exit...
1
Enter number: 30

Enter 1 for insertAtbeg...

Enter 2 for insertAtlast...
Enter 3 for insertAtposition...
Enter 4 for deleteAtbeg...
Enter 5 for deleteAtlast...
Enter 6 for deletetAtposition...
Enter 7 for print...
Enter 8 for exit...
1
Enter number: 20

Enter 1 for insertAtbeg...

Enter 2 for insertAtlast...
Enter 3 for insertAtposition...
Enter 4 for deleteAtbeg...
Enter 5 for deleteAtlast...
Enter 6 for deletetAtposition...
Enter 7 for print...
Enter 8 for exit...
1
Enter number: 10

Enter 1 for insertAtbeg...

Enter 2 for insertAtlast...
Enter 3 for insertAtposition...
Enter 4 for deleteAtbeg...
Enter 5 for deleteAtlast...
Enter 6 for deletetAtposition...
Enter 7 for print...
Enter 8 for exit...
7
10 20 30

Enter 1 for insertAtbeg...

Enter 2 for insertAtlast...
Enter 3 for insertAtposition...
Enter 4 for deleteAtbeg...
Enter 5 for deleteAtlast...
Enter 6 for deletetAtposition...
Enter 7 for print...
Enter 8 for exit...
2
Enter number: 40

Enter 1 for insertAtbeg...

Enter 2 for insertAtlast...
Enter 3 for insertAtposition...
Enter 4 for deleteAtbeg...
Enter 5 for deleteAtlast...
Enter 6 for deletetAtposition...
Enter 7 for print...
Enter 8 for exit...
2
Enter number: 50

Enter 1 for insertAtbeg...

Enter 2 for insertAtlast...
Enter 3 for insertAtposition...
Enter 4 for deleteAtbeg...
Enter 5 for deleteAtlast...
Enter 6 for deletetAtposition...
Enter 7 for print...
Enter 8 for exit...
7
10 20 30 40 50

Enter 1 for insertAtbeg...

Enter 2 for insertAtlast...
Enter 3 for insertAtposition...
Enter 4 for deleteAtbeg...
Enter 5 for deleteAtlast...
 Enter 6 for deletetAtposition...
Enter 7 for print...
Enter 8 for exit...
4

Enter 1 for insertAtbeg...

Enter 2 for insertAtlast...
Enter 3 for insertAtposition...
Enter 4 for deleteAtbeg...
Enter 5 for deleteAtlast...
Enter 6 for deletetAtposition...
Enter 7 for print...
Enter 8 for exit...
5

Enter 1 for insertAtbeg...

Enter 2 for insertAtlast...
Enter 3 for insertAtposition...
Enter 4 for deleteAtbeg...
Enter 5 for deleteAtlast...
Enter 6 for deletetAtposition...
Enter 7 for print...
Enter 8 for exit...
7
20 30 40

Enter 1 for insertAtbeg...

Enter 2 for insertAtlast...
Enter 3 for insertAtposition...
Enter 4 for deleteAtbeg...
Enter 5 for deleteAtlast...
Enter 6 for deletetAtposition...
Enter 7 for print...
Enter 8 for exit...
5

Enter 1 for insertAtbeg...

Enter 2 for insertAtlast...
Enter 3 for insertAtposition...
Enter 4 for deleteAtbeg...
Enter 5 for deleteAtlast...
Enter 6 for deletetAtposition...
Enter 7 for print...
Enter 8 for exit...
3
Enter number and position: 44 2

Enter 1 for insertAtbeg...

Enter 2 for insertAtlast...
Enter 3 for insertAtposition...
Enter 4 for deleteAtbeg...
Enter 5 for deleteAtlast...
 Enter 6 for deletetAtposition...
Enter 7 for print...
Enter 8 for exit...
7
20 44 30

Enter 1 for insertAtbeg...

Enter 2 for insertAtlast...
Enter 3 for insertAtposition...
Enter 4 for deleteAtbeg...
Enter 5 for deleteAtlast...
Enter 6 for deletetAtposition...
Enter 7 for print...
Enter 8 for exit...
6
Enter position: 2

Enter 1 for insertAtbeg...

Enter 2 for insertAtlast...
Enter 3 for insertAtposition...
Enter 4 for deleteAtbeg...
Enter 5 for deleteAtlast...
Enter 6 for deletetAtposition...
Enter 7 for print...
Enter 8 for exit...
7
20 30

Enter 1 for insertAtbeg...

Enter 2 for insertAtlast...
Enter 3 for insertAtposition...
Enter 4 for deleteAtbeg...
Enter 5 for deleteAtlast...
Enter 6 for deletetAtposition...
Enter 7 for print...
Enter 8 for exit...
8
exit..................................................
5) Write a choice based program to perform following operations in Single
Linked List.

A) Insert a new node at beginning

B) Insert a new node at last.
C) Insert a new node at any position k.
D) Delete a node from
E) Delete a node from last.
F) Delete a node from any position k.
G) Print Linked List.

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *link;
}*head=NULL,*newnode,*temp;
void insertbeg(int num)
{
newnode=(struct node*)malloc(sizeof(struct node));
newnode->data=num;
newnode->link=NULL;
if(head==NULL)
head=newnode;
else
{
newnode->link=head;
head=newnode;
}
}
void insertlast(int num)
{
newnode=(struct node*)malloc(sizeof(struct node));
newnode->data=num;
newnode->link=NULL;
if(head==NULL)
head=newnode;
else
{ temp=head;
while(temp->link!=NULL)
{
temp=temp->link;
}
temp->link=newnode;
}
}

void deletespecific(int source)

{
int found=0;
if(head==NULL)
{
printf("\n List is empty");
return;
}
if(head->data==source)
{
temp=head;
head=temp->link;
free(temp);
return;
}
else
{
temp=head;
while(temp->link!=NULL)
{ if(temp->link->data==source)
{
found=1;
break;
}

temp=temp->link;
}
if(found==0)
{
printf("\n Source is not found");
}
else
{
if(temp->link->link==NULL)
{
struct node *r=temp->link;
temp->link=NULL;
free(r);
}
else
{
struct node *r=temp->link;
temp->link=temp->link->link;
free(r);
}
}
}
}
void deleteatlast()
{
if(head==NULL)
{
printf("\n List is empty");
return;
}
if(head->link==NULL)
{
temp=head;
head=head->link;
printf("\n Data to be deleted = %d",temp->data);
free(temp);
}
else
{
temp=head;
while(temp->link->link!=NULL)
{
temp=temp->link;
}
struct node *r=temp->link;
temp->link=NULL;
printf("\n Data to be deleted = %d",r->data);
free(r);
}
}

void deleteatbig()
{
if(head==NULL)
{
printf("\n List is empty");
}
else
{
temp=head;
head=head->link;
printf("\n Data to be deleted = %d",temp->data);
free(temp);
}
}
void insertAtKthPosition(int value, int k) {

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

newnode->data = value;
newnode->link = NULL;
if (k == 1) {
newnode->link = head;
head = newnode;
printf("New node inserted at position %d\n", k);
return;
}
 temp = head;
int position = 1;

while (temp != NULL && position < k-1) {

temp = temp->link;
position++;
}
if (temp != NULL) {
newnode->link = temp->link;
temp->link = newnode;
printf("New node inserted at position %d\n", k);
} else {
printf("Position %d is out of bounds\n", k);
free(newnode);
}
}

void print()
{
temp=head;
while(temp!=NULL)
{
printf("%d -> ",temp->data);
temp=temp->link;
}
printf("NULL");
}
int main(){
int ch,num,c,source,value,k;
while(1)
{
printf("\nEnter 1 for insert beg");
printf("\nEnter 2 for insert last");
printf("\nEnter 3 for insert at k position");
printf("\nEnter 4 for delete at beg");
printf("\nEnter 5 for delete at last");
printf("\nEnter 6 for delete specific");
printf("\nEnter 7 for print\n");
scanf("%d",&ch);
switch (ch)
{
case 1:
printf("Enter the number:");
scanf("%d",&num);
insertbeg(num);
break;
case 2:
printf("Enter the number:");
scanf("%d",&num);
insertlast(num);
 break;
case 3:
printf("Enter the number and position:");
scanf("%d%d",&num,&k);
insertAtKthPosition(num,k);
break;
case 4:
deleteatbig();
break;
case 5:
deleteatlast();
break;
case 6:
printf("Enter source number:");
scanf("%d",&source);
deletespecific(source);
break;
case 7:
print();
break;

default:
exit(0);
break;
}

return 0;
}

Output:-

Enter 1 for insert beg

Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
1
Enter the number:30

Enter 1 for insert beg

Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
1
Enter the number:20

Enter 1 for insert beg

Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
1
Enter the number:10

Enter 1 for insert beg

Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
7
10 -> 20 -> 30 -> NULL
Enter 1 for insert beg
Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
2
Enter the number:40

Enter 1 for insert beg

Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
2
Enter the number:50

Enter 1 for insert beg

Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
7
10 -> 20 -> 30 -> 40 -> 50 -> NULL
Enter 1 for insert beg
Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
3
Enter the number and position:35 4
New node inserted at position 4

Enter 1 for insert beg

Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
7
10 -> 20 -> 30 -> 35 -> 40 -> 50 -> NULL
Enter 1 for insert beg
Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
4

Data to be deleted = 10
Enter 1 for insert beg
Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
5

Data to be deleted = 50
Enter 1 for insert beg
Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print

7
20 -> 30 -> 35 -> 40 -> NULL
Enter 1 for insert beg
Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
6
Enter source number:35

Enter 1 for insert beg

Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
7
20 -> 30 -> 40 -> NULL

6) Write a choice based program to perform following operations in Double

Linked List.
A) Insert a new node at beginning
B) Insert a new node at last.
C) Insert a new node at any position k.
D) Delete a node from beginning
E) Delete a node from last.
F) Delete a node from any position k.
G) Print Linked List.

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *prev;
struct node *next;
}*head=NULL,*newnode,*temp;

void insertbeg(int num)

{
newnode = (struct node*)malloc(sizeof(struct node));
newnode->data = num;
newnode->prev = NULL;
newnode->next = head;
 if (head != NULL)
head->prev = newnode;
head = newnode;
}

void insertlast(int num)

{
newnode = (struct node*)malloc(sizeof(struct node));
newnode->data = num;
newnode->next = NULL;
if (head == NULL)
{
newnode->prev = NULL;
head = newnode;
return;
}
temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newnode;
newnode->prev = temp;
}

void deletespecific(int source)

{
if (head == NULL)
{
printf("\nList is empty");
return;
}
temp = head;
while (temp != NULL && temp->data != source)
temp = temp->next;
if (temp == NULL)
{
printf("\nSource not found");
return;
}
if (temp->prev != NULL)
temp->prev->next = temp->next;
else
head = temp->next;
if (temp->next != NULL)
temp->next->prev = temp->prev;
free(temp);
}

void deleteatlast()
{
if (head == NULL)
{
printf("\nList is empty");
 return;
}
temp = head;
while (temp->next != NULL)
temp = temp->next;
if (temp->prev != NULL)
temp->prev->next = NULL;
else
head = NULL;
printf("\nData to be deleted = %d", temp->data);
free(temp);
}

void deleteatbig()
{
if (head == NULL)
{
printf("\nList is empty");
return;
}
temp = head;
head = head->next;
if (head != NULL)
head->prev = NULL;
printf("\nData to be deleted = %d", temp->data);
free(temp);
}

void insertAtKthPosition(int value, int k)

{
newnode = (struct node*)malloc(sizeof(struct node));
newnode->data = value;
newnode->prev = NULL;
newnode->next = NULL;
if (k == 1)
{
newnode->next = head;
if (head != NULL)
head->prev = newnode;
head = newnode;
printf("New node inserted at position %d\n", k);
return;
}
temp = head;
int position = 1;
while (temp != NULL && position < k - 1)
{
temp = temp->next;
position++;
}
if (temp != NULL)
{
 newnode->next = temp->next;
newnode->prev = temp;
if (temp->next != NULL)
temp->next->prev = newnode;
temp->next = newnode;
printf("New node inserted at position %d\n", k);
}
else
{
printf("Position %d is out of bounds\n", k);
free(newnode);
}
}

void print()
{
temp = head;
while (temp != NULL)
{
printf("%d <-> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

int main()
{
int ch, num, source, value, k;
while (1)
{
printf("\nEnter 1 for insert beg");
printf("\nEnter 2 for insert last");
printf("\nEnter 3 for insert at k position");
printf("\nEnter 4 for delete at beg");
printf("\nEnter 5 for delete at last");
printf("\nEnter 6 for delete specific");
printf("\nEnter 7 for print\n");
scanf("%d", &ch);
switch (ch)
{
case 1:
printf("Enter the number: ");
scanf("%d", &num);
insertbeg(num);
break;
case 2:
printf("Enter the number: ");
scanf("%d", &num);
insertlast(num);
break;
case 3:
printf("Enter the number and position: ");
 scanf("%d%d", &num, &k);
insertAtKthPosition(num, k);
break;
case 4:
deleteatbig();
break;
case 5:
deleteatlast();
break;
case 6:
printf("Enter source number: ");
scanf("%d", &source);
deletespecific(source);
break;
case 7:
print();
break;
default:
exit(0);
}
}
return 0;
}

Output:-

Enter 1 for insert beg

Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
1
Enter the number: 30

Enter 1 for insert beg

Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
1
Enter the number: 20

Enter 1 for insert beg

Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
1
Enter the number: 10

Enter 1 for insert beg

Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
7
10 <-> 20 <-> 30 <-> NULL

Enter 1 for insert beg

Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
2
Enter the number: 40

Enter 1 for insert beg

Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
2
Enter the number: 50

Enter 1 for insert beg

Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
7
10 <-> 20 <-> 30 <-> 40 <-> 50 <-> NULL

Enter 1 for insert beg

Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
3
Enter the number and position: 35 4
New node inserted at position 4

Enter 1 for insert beg

Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
7
10 <-> 20 <-> 30 <-> 35 <-> 40 <-> 50 <-> NULL

Enter 1 for insert beg

Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
4

Data to be deleted = 10
Enter 1 for insert beg
Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
5

Data to be deleted = 50
Enter 1 for insert beg
Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
7
20 <-> 30 <-> 35 <-> 40 <-> NULL

Enter 1 for insert beg

Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
6
Enter source number: 35

Enter 1 for insert beg

Enter 2 for insert last
Enter 3 for insert at k position
Enter 4 for delete at beg
Enter 5 for delete at last
Enter 6 for delete specific
Enter 7 for print
7
20 <-> 30 <-> 40 <-> NULL

7) Write a choice based program to perform following operations in Circular

Linked List

A) Insert a new node at beginning

B) Insert a new node at last.
C) Insert a new node at any position k.
D) Delete a node from beginning
E) Delete a node from last.
F) Delete a node from any position k.
G) Print Linked List.

#include<stdio.h>
#include<stdlib.h>

struct node {
int data;
struct node *link;
} *last = NULL, *newnode, *temp;

void insertbeg(int num) {

newnode = (struct node*)malloc(sizeof(struct node));
newnode->data = num;
if(last == NULL) {
newnode->link = newnode;
last = newnode;
} else {
newnode->link = last->link;
last->link = newnode;
}
}

void insertatlast(int num) {

 newnode = (struct node*)malloc(sizeof(struct node));
newnode->data = num;
if(last == NULL) {
newnode->link = newnode;
last = newnode;
} else {
newnode->link = last->link;
last->link = newnode;
last = newnode;
}
}

void insertatkthposition(int num, int k) {

if(k <= 0) {
printf("Invalid position.\n");
return;
}

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

newnode->data = num;
if(k == 1) {
insertbeg(num);
return;
}

temp = last->link;
int count = 1;
while(count < k-1 && temp != last) {
temp = temp->link;
count++;
}

if(count == k-1) {
newnode->link = temp->link;
temp->link = newnode;
if(temp == last) {
last = newnode;
}
printf("Node inserted at position %d\n", k);
} else {
printf("Position %d out of bounds.\n", k);
free(newnode);
}
}

void deleteatbeg() {
if(last == NULL) {
printf("\nList is empty.\n");
return;
}
if(last->link == last) {
temp = last->link;
 last = NULL;
printf("\nData to be deleted = %d\n", temp->data);
free(temp);
} else {
temp = last->link;
last->link = temp->link;
printf("\nData to be deleted = %d\n", temp->data);
free(temp);
}
}

void deleteatlast() {
if(last == NULL) {
printf("\nList is empty.\n");
return;
}
if(last->link == last) {
temp = last->link;
last = NULL;
printf("\nData to be deleted = %d\n", temp->data);
free(temp);
} else {
struct node *r;
temp = last->link;
while(temp != last) {
if(temp->link == last) {
break;
}
temp = temp->link;
}
printf("\nData to be deleted = %d\n", temp->link->data);
r = last;
temp->link = last->link;
last = temp;
free(r);
}
}

void deleteSpecific(int num) {

if(last == NULL) {
printf("\nList is empty.\n");
return;
}
temp = last->link;
struct node *prev = NULL;

do {
if(temp->data == num) {
if(prev == NULL) {
deleteatbeg();
} else {
prev->link = temp->link;
 if(temp == last) {
last = prev;
}
printf("\nData to be deleted = %d\n", temp->data);
free(temp);
}
return;
}
prev = temp;
temp = temp->link;
} while(temp != last->link);

printf("Element %d not found in the list.\n", num);

}

void print() {
if(last == NULL) {
printf("\nList is empty.\n");
return;
}
temp = last->link;
do {
printf("%d\t", temp->data);
temp = temp->link;
} while(temp != last->link);
printf("\n");
}

int main() {
int choice, num, k;
while(1) {
printf("\nMenu: \n");
printf("1. Insert at beginning\n");
printf("2. Insert at last\n");
printf("3. Insert at Kth position\n");
printf("4. Delete at beginning\n");
printf("5. Delete at last\n");
printf("6. Delete specific element\n");
printf("7. print the list\n");
printf("8. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch(choice) {
case 1:
printf("Enter the number: ");
scanf("%d", &num);
insertbeg(num);
break;
case 2:
printf("Enter the number: ");
scanf("%d", &num);
 insertatlast(num);
break;
case 3:
printf("Enter the number and position: ");
scanf("%d%d", &num, &k);
insertatkthposition(num, k);
break;
case 4:
deleteatbeg();
break;
case 5:
deleteatlast();
break;
case 6:
printf("Enter the number to delete: ");
scanf("%d", &num);
deleteSpecific(num);
break;
case 7:
print();
break;
case 8:
exit(0);
default:
printf("Invalid choice, please try again.\n");
}
}
return 0;
}

Output:-

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. print the list
8. Exit
Enter your choice: 1
Enter the number: 30

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. print the list
8. Exit
Enter your choice: 1
Enter the number: 20

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. print the list
8. Exit
Enter your choice: 1
Enter the number: 10

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. print the list
8. Exit
Enter your choice: 7
10 20 30

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. print the list
8. Exit
Enter your choice: 2
Enter the number: 40

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. print the list
8. Exit
Enter your choice: 7
10 20 30 40

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. print the list
8. Exit
Enter your choice: 3
Enter the number and position: 35 4
Node inserted at position 4

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. print the list
8. Exit
Enter your choice: 7
10 20 30 35 40

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. print the list
8. Exit
Enter your choice: 4

Data to be deleted = 10

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. print the list
8. Exit
Enter your choice: 5
Data to be deleted = 40

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. print the list
8. Exit
Enter your choice: 7
20 30 35

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. print the list
8. Exit
Enter your choice: 6
Enter the number to delete: 30

Data to be deleted = 30

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. print the list
8. Exit
Enter your choice: 7
20 35

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. print the list
8. Exit
Enter your choice: 8
exit.........................................
8) Write a choice based program to perform following operations in Doubly
Circular Linked List

A) Insert a new node at beginning

B) Insert a new node at last.
C) Insert a new node at any position k.
D) Delete a node from beginning
E) Delete a node from last.
F) Delete a node from any position k.
G) Print Linked List.

#include<stdio.h>
#include<stdlib.h>

struct node {
int data;
struct node *next;
struct node *prev;
} *last = NULL, *newnode, *temp;

void insertbeg(int num) {

newnode = (struct node*)malloc(sizeof(struct node));
newnode->data = num;
if(last == NULL) {
newnode->next = newnode;
newnode->prev = newnode;
last = newnode;
} else {
newnode->next = last->next;
newnode->prev = last;
last->next->prev = newnode;
last->next = newnode;
}
}

void insertatlast(int num) {

newnode = (struct node*)malloc(sizeof(struct node));
newnode->data = num;
if(last == NULL) {
newnode->next = newnode;
newnode->prev = newnode;
last = newnode;
} else {
newnode->next = last->next;
newnode->prev = last;
last->next->prev = newnode;
last->next = newnode;
 last = newnode;
}
}

void insertatkthposition(int num, int k) {

if(k <= 0) {
printf("Invalid position.\n");
return;
}

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

newnode->data = num;
if(k == 1) {
insertbeg(num);
return;
}

temp = last->next;
int count = 1;
while(count < k-1 && temp != last) {
temp = temp->next;
count++;
}

if(count == k-1) {
newnode->next = temp->next;
newnode->prev = temp;
temp->next->prev = newnode;
temp->next = newnode;
if(temp == last) {
last = newnode;
}
printf("Node inserted at position %d\n", k);
} else {
printf("Position %d out of bounds.\n", k);
free(newnode);
}
}

void deleteatbeg() {
if(last == NULL) {
printf("\nList is empty.\n");
return;
}
if(last->next == last) {
temp = last;
last = NULL;
printf("\nData to be deleted = %d\n", temp->data);
free(temp);
} else {
temp = last->next;
last->next = temp->next;
 temp->next->prev = last;
printf("\nData to be deleted = %d\n", temp->data);
free(temp);
}
}

void deleteatlast() {
if(last == NULL) {
printf("\nList is empty.\n");
return;
}
if(last->next == last) {
temp = last;
last = NULL;
printf("\nData to be deleted = %d\n", temp->data);
free(temp);
} else {
temp = last;
last = last->prev;
last->next = temp->next;
temp->next->prev = last;
printf("\nData to be deleted = %d\n", temp->data);
free(temp);
}
}

void deleteSpecific(int num) {

if(last == NULL) {
printf("\nList is empty.\n");
return;
}
temp = last->next;
struct node *prev = NULL;

do {
if(temp->data == num) {
if(prev == NULL) {
deleteatbeg();
} else {
prev->next = temp->next;
temp->next->prev = prev;
if(temp == last) {
last = prev;
}
printf("\nData to be deleted = %d\n", temp->data);
free(temp);
}
return;
}
prev = temp;
temp = temp->next;
} while(temp != last->next);
 printf("Element %d not found in the list.\n", num);
}

void print() {
if(last == NULL) {
printf("\nList is empty.\n");
return;
}
temp = last->next;
do {
printf("%d\t", temp->data);
temp = temp->next;
} while(temp != last->next);
printf("\n");
}

int main() {
int choice, num, k;
while(1) {
printf("\nMenu: \n");
printf("1. Insert at beginning\n");
printf("2. Insert at last\n");
printf("3. Insert at Kth position\n");
printf("4. Delete at beginning\n");
printf("5. Delete at last\n");
printf("6. Delete specific element\n");
printf("7. Print the list\n");
printf("8. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch(choice) {
case 1:
printf("Enter the number: ");
scanf("%d", &num);
insertbeg(num);
break;
case 2:
printf("Enter the number: ");
scanf("%d", &num);
insertatlast(num);
break;
case 3:
printf("Enter the number and position: ");
scanf("%d%d", &num, &k);
insertatkthposition(num, k);
break;
case 4:
deleteatbeg();
break;
case 5:
 deleteatlast();
break;
case 6:
printf("Enter the number to delete: ");
scanf("%d", &num);
deleteSpecific(num);
break;
case 7:
print();
break;
case 8:
exit(0);
default:
printf("Invalid choice, please try again.\n");
}
}
return 0;
}

Output:-

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. Print the list
8. Exit
Enter your choice: 1
Enter the number: 30

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. Print the list
8. Exit
Enter your choice: 1
Enter the number: 20

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. Print the list
8. Exit
Enter your choice: 1
Enter the number: 10

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. Print the list
8. Exit
Enter your choice: 7
10 20 30

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. Print the list
8. Exit
Enter your choice: 2
Enter the number: 40

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. Print the list
8. Exit
Enter your choice: 7
10 20 30 40

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. Print the list
8. Exit
Enter your choice: 3
Enter the number and position: 35 4
Node inserted at position 4

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. Print the list
8. Exit
Enter your choice: 7
10 20 30 35 40

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. Print the list
8. Exit
Enter your choice: 4

Data to be deleted = 10

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. Print the list
8. Exit
Enter your choice: 5

Data to be deleted = 40

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. Print the list
8. Exit
Enter your choice: 7
20 30 35

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. Print the list
8. Exit
Enter your choice: 6
Enter the number to delete: 35

Data to be deleted = 35

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. Print the list
8. Exit
Enter your choice: 7
20 30

Menu:
1. Insert at beginning
2. Insert at last
3. Insert at Kth position
4. Delete at beginning
5. Delete at last
6. Delete specific element
7. Print the list
8. Exit
Enter your choice: 8
exit......................................
9) Write a choice based program to perform following operations on STACK

a) PUSH b) POP c)PEEK d) Display

#include<stdio.h>
#include<stdlib.h>
#define size 5
int stack[size];
int top=-1;
void push(int num)
{
if(top==size-1)
{
printf("\nOverflow ");
}
else
{
top=top+1;
stack[top]=num;
}

}
int pop()
{
if(top==-1)
{
printf("\nUnderflow");
return -1;
}
else
{
int num=stack[top];
top=top-1;
return num;
}
}
int peek()
{

if(top==-1)
{
printf("\nUnderflow");
}
if(top==size-1)
{
printf("\nOverflow ");
}
return stack[top];
}
void display()
{
int i;
for(i=0;i<=top;i++)
{
printf("%d ",stack[i]);
}
printf("\n");
}
int main()
{
int ch,num;
while(1)
{
printf("\nEnter 1 for Push operation...");
printf("\nEnter 2 for pop operation...");
printf("\nEnter 3 for Peek operation...");
printf("\nEnter 4 for display operation...");
printf("\nEnter 5 for exit operation...\n");
scanf("%d",&ch);
switch (ch)
{
case 1:
printf("Enter the number: ");
scanf("%d",&num);
push(num);
break;
case 2:
printf("\npoped element = %d\n",pop());
break;
case 3:
printf("\nTop element = %d\n",peek());
break;
case 4:
display();
break;
case 5:
exit(0);
break;
default:
printf("\nUnvalid choice");
break;
}

}
return 0;
}
Output:-

Enter 1 for Push operation...

Enter 2 for pop operation...
Enter 3 for Peek operation...
Enter 4 for display operation...
Enter 5 for exit operation...
1
Enter the number: 10

Enter 1 for Push operation...

Enter 2 for pop operation...
Enter 3 for Peek operation...
Enter 4 for display operation...
Enter 5 for exit operation...
1
Enter the number: 20

Enter 1 for Push operation...

Enter 2 for pop operation...
Enter 3 for Peek operation...
Enter 4 for display operation...
Enter 5 for exit operation...
1
Enter the number: 30

Enter 1 for Push operation...

Enter 2 for pop operation...
Enter 3 for Peek operation...
Enter 4 for display operation...
Enter 5 for exit operation...
4
10 20 30

Enter 1 for Push operation...

Enter 2 for pop operation...
Enter 3 for Peek operation...
Enter 4 for display operation...
Enter 5 for exit operation...
3

Top element = 30

Enter 1 for Push operation...

Enter 2 for pop operation...
Enter 3 for Peek operation...
Enter 4 for display operation...
Enter 5 for exit operation...
2

poped element = 30
Enter 1 for Push operation...
Enter 2 for pop operation...
Enter 3 for Peek operation...
Enter 4 for display operation...
Enter 5 for exit operation...
2

poped element = 20

Enter 1 for Push operation...

Enter 2 for pop operation...
Enter 3 for Peek operation...
Enter 4 for display operation...
Enter 5 for exit operation...
1
Enter the number: 45

Enter 1 for Push operation...

Enter 2 for pop operation...
Enter 3 for Peek operation...
Enter 4 for display operation...
Enter 5 for exit operation...
4
10 45

Enter 1 for Push operation...

Enter 2 for pop operation...
Enter 3 for Peek operation...
Enter 4 for display operation...
Enter 5 for exit operation...
1
Enter the number: 50

Enter 1 for Push operation...

Enter 2 for pop operation...
Enter 3 for Peek operation...
Enter 4 for display operation...
Enter 5 for exit operation...
4
10 45 50

Enter 1 for Push operation...

Enter 2 for pop operation...
Enter 3 for Peek operation...
Enter 4 for display operation...
Enter 5 for exit operation...
5
exit.....................................
10) Write a choice based program to perform following operations on QUEUE

a) Enqueue b) Dequeue

#include<stdio.h>
#define size 5
int queue[size];
int front=-1,rear=-1;
void insertopr(int n)
{
if(rear==size-1)
{
printf("Overflow\n");
return;
}
if(front==-1)
{
front=0;
}
rear=rear+1;
queue[rear]=n;

}
void deleteopr()
{
if(front==-1||front==rear+1)
{
printf("Underflow\n");
}
printf("Deleted data = %d\n",queue[front]);
front=front+1;
}
void traverse()
{
for(int i=front;i<=rear;i++)
{
printf("%d ",queue[i]);
}
printf("\n");
}

int main()
{
int c,num;
while(1)
{
printf("Enter 1 for Insert operation...\n");
printf("Enter 2 for Delete operation...\n");
printf("Enter 3 for Traverse operation...\n");
scanf("%d",&c);
switch (c)
{
case 1:
printf("Enter number : ");
scanf("%d",&num);
insertopr(num);
break;
case 2:
deleteopr();
break;
case 3:
traverse();
break;

default:
printf("Unvalid Choice\n");
break;
}
}
return 0;
}

Output:-

Enter 1 for Insert operation...

Enter 2 for Delete operation...
Enter 3 for Traverse operation...
1
Enter number : 10
Enter 1 for Insert operation...
Enter 2 for Delete operation...
Enter 3 for Traverse operation...
1
Enter number : 20
Enter 1 for Insert operation...
Enter 2 for Delete operation...
Enter 3 for Traverse operation...
1
Enter number : 30
Enter 1 for Insert operation...
Enter 2 for Delete operation...
Enter 3 for Traverse operation...
3
10 20 30
Enter 1 for Insert operation...
Enter 2 for Delete operation...
Enter 3 for Traverse operation...
2
Deleted data = 10
Enter 1 for Insert operation...
Enter 2 for Delete operation...
Enter 3 for Traverse operation...
3
20 30

11) Write a choice based program to perform following operations on

CIRCULAR QUEUE

a) Enqueue b) Dequeue

#include<stdio.h>
#include<stdlib.h>
#define size 5
int cqueue[size];
int front=-1,rear=-1;
void insertopr(int num)
{
if((front==0 && rear==size-1)||(front==rear+1))
{
printf("\n Overflow");
return;
}
if(front==-1)
{
front=rear=0;
}
else
{
if(rear==size-1)
rear=0;
else
rear=rear+1;

}
cqueue[rear]=num;
}
void deleteopr()
{
if(front==-1)
{
printf("\n Underflow");
return;

}
int del=cqueue[front];
cqueue[front]=' ';
if(front==rear)
{
front=rear=-1;

}
else
{
if(front==size-1)

front=0;
else
front=front+1;
}
printf("\n Deleted data = %d\n",del);
}
void traverse()
{
if(front==-1)
{
printf("\n Underflow");
return;
}
if(rear>=front)
{
for(int i=front;i<=rear;i++)
{
printf("%d ",cqueue[i]);
}
}
if(rear<front)
{
for(int i=front;i<=size-1;i++)
{
printf("%d ",cqueue[i]);
}
for(int i=0;i<=rear;i++)
{
printf("%d ",cqueue[i]);
}
}
}
int main()
{
int c,num;
while(1)
{
printf("\nEnter 1 for Insert operation...\n");
printf("Enter 2 for Delete operation...\n");
printf("Enter 3 for Traverse operation...\n");
printf("Enter 4 for exit...\n");
scanf("%d",&c);
switch (c)
{
case 1:
printf("Enter number : ");
scanf("%d",&num);
insertopr(num);
break;
case 2:
deleteopr();
break;
case 3:
traverse();
break;

case 4:
exit(0);
break;

default:
printf("Unvalid Choice\n");
break;
}
}

return 0;
}

Output:-

Enter 1 for Insert operation...

Enter 2 for Delete operation...
Enter 3 for Traverse operation...
Enter 4 for exit...
1
Enter number : 10

Enter 1 for Insert operation...

Enter 2 for Delete operation...
Enter 3 for Traverse operation...
Enter 4 for exit...
1
Enter number : 20

Enter 1 for Insert operation...

Enter 2 for Delete operation...
Enter 3 for Traverse operation...
Enter 4 for exit...
1
Enter number : 30

Enter 1 for Insert operation...

Enter 2 for Delete operation...
Enter 3 for Traverse operation...
Enter 4 for exit...
3
10 20 30
Enter 1 for Insert operation...
Enter 2 for Delete operation...
Enter 3 for Traverse operation...
Enter 4 for exit...
2

Deleted data = 10

Enter 1 for Insert operation...

Enter 2 for Delete operation...
Enter 3 for Traverse operation...
Enter 4 for exit...
3
20 30
Enter 1 for Insert operation...
Enter 2 for Delete operation...
Enter 3 for Traverse operation...
Enter 4 for exit...
4
exit...........................

12) Write a program to implement linear search.

#include<stdio.h>
int main()
{ int a[100],i,n,search,flag=0;
printf("Enter the size of the set\n");
scanf("%d",&n);
printf("Enter the set of numbers\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("Enter the number to be searched\n");
scanf("%d",&search);
for(i=0;i<n;i++)
{
if(search==a[i])
{
printf("%d is found at location %d",search,i+1);
 flag++;
break;
}

}
if(flag!=1)
printf("%d is not found in given set",search);

return 0;
}

Output:-

Enter the size of the set

5
Enter the set of numbers
25791
Enter the number to be searched
7
7 is found at location

13) Write a program to implement binary search.

#include<stdio.h>
int
main ()
{
int i, a[50], search, first, last, mid, n;
printf ("Enter the number of elements:\n");
scanf ("%d", &n);
printf ("Enter the elements:");
for (i = 0; i < n; i++)
scanf ("%d", &a[i]);
printf ("\n Enter element to be search:");
scanf ("%d", &search);
first = 0;
last = n - 1;
mid = (first + last) / 2;
while (first <= last)
{
if (a[mid] < search)
{
first = mid + 1;
mid = (first + last) / 2;
}
 else if (a[mid] == search)
{
printf ("\n The number ,%d foundat position %d", search, mid + 1);
break;
}
else
{
last = mid - 1;
mid = (first + last) / 2;
}
}
if (first > last)
printf ("\n The search is unsuccessful");

return 0;
}

Output:-

Enter the number of elements:

10
Enter the elements:2 4 5 7 9 1 44 66 88 22

Enter element to be search:44

The number ,44 foundat position 7

14) Write a program to implement Index Sequential Searching

#include<stdio.h>
#define size 12
int indexseqential(int arr[],int n,int num)
{
if(num<arr[0]||num>arr[n-1])
return -1;

int i,j,indx=0;
int valarr[n];
int indexarr[n];
for(i=0;i<n;i=i+3)
{
valarr[indx]=arr[i];
indexarr[indx]=i;
 indx++;
}
int s,e;
int maybe=0;
for(i=1;i<n;i++)
{
if(num<=valarr[i])
{
s=indexarr[i-1];
e=indexarr[i];
maybe=1;
break;
}
}
if(maybe==0)
{
s=indexarr[i-1];
e=n-1;
}
for(i=s;i<=e;i++)
{
if(num==arr[i])
return i;

}
return -1;
}
int main ()
{
int arr[size]={10,20,30,40,50,60,70,80,90,100,110,120};
int num =100;
int index=indexseqential(arr,size,num);
if (index!=-1)
printf ("\n Number found at %d position ",index+1);
else
printf ("\n Number not found");
return 0;

Output:-

Number found at 10 position

15) Write a program to implement bubble sort.

#include<stdio.h>
void bubble(int arr[], int n)
{
int i,j,temp;
for (i=0;i<n;i++)
{
for (j=0;j<n-i-1;j++)
{
if (arr[j]>arr[j+1])
{
temp= arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp; }
}
}
}
void print(int arr[],int n)
{
int i;
for (i=0;i<n;i++)
{
printf ("%d ",arr[i]);
}

}
int main()
{
int size,i,flag=0;
printf("\n Enter the size of array :");
scanf("%d",&size);
int arr[size];
printf("\n Enter the number :");
for(i=0;i<size;i++)
{
scanf("%d",&arr[i]);
}
printf("\nBefore sorting : ");
print(arr,size);
printf("\nAfter sorting : ");
bubble(arr,size);
print(arr,size);

return 0;
}
Output:-

Enter the size of array :6

Enter the number :33 44 12 11 3 78

Before sorting : 33 44 12 11 3 78
After sorting : 3 11 12 33 44 78

16) Write a program to implement selection sort.

#include<stdio.h>
void print(int arr[],int n)
{ int i;
for(i=0;i<n;i++)
{
printf("%d ",arr[i]);
}

}
void selection(int arr[],int n)
{
int i,j,temp;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(arr[i]>arr[j])
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
}
int main()
{
int size,i;
printf("\n Enter the size of array :");
scanf("%d",&size);
int arr[size];
printf("\n Enter the number :");
for(i=0;i<size;i++)
{
 scanf("%d",&arr[i]);
}
printf("\nBefore sorting : ");
print(arr,size);
printf("\nAfter sorting : ");
selection(arr,size);
print(arr,size);

return 0;
}

Output:-

Enter the size of array :6

Enter the number :2 55 12 67 22 44

Before sorting : 2 55 12 67 22 44
After sorting : 2 12 22 44 55 67

17) Write a program to implement counting sort.

#include<stdio.h>
int getmax(int ip[],int m)
{
int mx=ip[0];
int i;
for(i=0;i<m;i++)
{
if(mx<ip[i])
mx=ip[i];
}
return mx;
}
void countsort(int ip[],int op[],int size)
{
int i;
int max=getmax(ip,size);
int count[max+1];
for(i=0;i<=max;i++)
{
count[i]=0;
}
for(i=0;i<size;i++)
{
 count[ip[i]]++;
}
for(i=1;i<=max;i++)
{
count[i]=count[i]+count[i-1];
}
for(i=size-1;i>=0;i--)
{
int n=ip[i];
count[n]=count[n]-1;
op[count[n]]=n;
}
}
int main()
{
int n;
printf("Enter the size of array: ");
scanf("%d",&n);
int ip[n],op[n];
printf("Enter the element of array: ");
for(int i=0;i<n;i++)
{
scanf("%d",&ip[i]);
}
printf("\n Before sorting: ");
for(int i=0;i<n;i++)
{
printf("%d ",ip[i]);
}
countsort(ip,op,n);
printf("\n After sorting: ");
for(int i=0;i<n;i++)
{
printf("%d ",op[i]);
}
return 0;
}

Output:-

Enter the size of array: 6

Enter the element of array: 2 3 1 4 2 5

Before sorting: 2 3 1 4 2 5
After sorting: 1 2 2 3 4 5
18) Write a program to implement radix sort.

#include<stdio.h>
int getmax(int ip[],int m)
{
int mx=ip[0];
int i;
for(i=0;i<m;i++)
{
if(mx<ip[i])
mx=ip[i];
}
return mx;
}
void countsort(int ip[],int op[],int size,int exp)
{
int i,md=ip[0]/exp%10;
for(i=0;i<size;i++)
{
if(md<ip[i]/exp%10)
md=ip[i]/exp%10;
}
int count[md+1];
for(i=0;i<=md;i++)
{
count[i]=0;
}
for(i=0;i<size;i++)
{
count[ip[i]/exp%10]++;
}
for(i=1;i<=md;i++)
{
count[i]=count[i]+count[i-1];
}
for(i=size-1;i>=0;i--)
{
int n=ip[i]/exp%10;
count[n]=count[n]-1;
op[count[n]]=ip[i];
}
for(i=0;i<size;i++)
{
ip[i]=op[i];
}
}
void radixsort(int ip[],int op[],int s)
{
int m=getmax(ip,s);
int exp=1;
while(exp<=m)
 {
countsort(ip,op,s,exp);
exp=exp*10;
}
}
int main()
{
int n;
printf("Enter the size of array: ");
scanf("%d",&n);
int ip[n],op[n];
printf("Enter the element of array: ");
for(int i=0;i<n;i++)
{
scanf("%d",&ip[i]);
}
printf("\n Before sorting: ");
for(int i=0;i<n;i++)
{
printf("%d ",ip[i]);
}
radixsort(ip,op,n);
printf("\n After sorting: ");
for(int i=0;i<n;i++)
{
printf("%d ",ip[i]);
}
return 0;
}

Output:-

Enter the size of array: 5

Enter the element of array: 22 4 12 23 66

Before sorting: 22 4 12 23 66
After sorting: 4 12 22 23 66
19) Write a program to implement heap sort.

#include <stdio.h>

void heapify(int arr[], int n, int i) {

int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;

if (left < n && arr[left] > arr[largest])

largest = left;

if (right < n && arr[right] > arr[largest])

largest = right;

if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;

heapify(arr, n, largest);
}
}

void heapSort(int arr[], int n) {

for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

for (int i = n - 1; i > 0; i--) {

int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;

heapify(arr, i, 0);
}
}

int main() {
int n;
printf("Enter the number of elements: ");
scanf("%d", &n);

int arr[n];
printf("Enter the elements: ");
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);

heapSort(arr, n);

printf("Sorted array: ");

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

return 0;
}

Output:-

Enter the number of elements: 6

Enter the elements: 23 12 11 34 5 21
Sorted array: 5 11 12 21 23 34

20) Write a program to implement quick sort.

#include<stdio.h>
#define size 10
void print(int arr[],int n)
{
int i;
for (i=0;i<n;i++)
{
printf ("%d ",arr[i]);
}

}
void swap(int *a,int *b)
{
int c;
c=*a;
*a=*b;
*b=c;
}
int partition(int arr[],int low,int high,int pivot)
{
int i,j;
i=low;
j=low;
while (i<=high)
{
if(arr[i]>pivot)
{
i++;
}
 else
{
swap(&arr[i],&arr[j]);
i++;
j++;
}
}
return j-1;
}
void quicksort(int arr[],int low,int high)
{
if(low>=high)
return;
int pivot=partition(arr,low,high,arr[high]);
quicksort(arr,low,pivot-1);
quicksort(arr,pivot+1,high);
}
int main()
{
int i;
printf("\n The size of the array is :%d",size);
int arr[size];
printf("\n Enter the number :");
for(i=0;i<size;i++)
{
scanf("%d",&arr[i]);
}
printf("\nBefore sorting : ");
print(arr,size);
printf("\nAfter sorting : ");
quicksort(arr,0,size-1);
print(arr,size);

return 0;
}

Output:-

The size of the array is :10

Enter the number :12 44 5 66 77 12 23 45 98 15

Before sorting : 12 44 5 66 77 12 23 45 98 15
After sorting : 5 12 12 15 23 44 45 66 77 98
21) Write a program to implement insertion sort

#include<stdio.h>
//Code of Insertion Sort
void insertionSort(int arr[],int s){
int i,j,temp;
for(i=1;i<s;i++){
temp=arr[i];
j=i;
while (j>0 && temp<arr[j-1])
{
arr[j]=arr[j-1];
j=j-1;
}
arr[j]=temp;
}
}
void print(int arr[],int n)
{
int i;
for (i=0;i<n;i++)
{
printf ("%d ",arr[i]);
}

}
int main()
{
int size,i,flag=0;
printf("\n Enter the size of array :");
scanf("%d",&size);
int arr[size];
printf("\n Enter the number :");
for(i=0;i<size;i++)
{
scanf("%d",&arr[i]);
}
printf("\nBefore sorting : ");
print(arr,size);
printf("\nAfter sorting : ");
insertionSort(arr,size);
print(arr,size);

return 0;
}
Output:-

Enter the size of array :6

Enter the number :23 45 11 21 56 2

Before sorting : 23 45 11 21 56 2
After sorting : 2 11 21 23 45 56

22) Write a program to implement merge sort.

#include<stdio.h>
#define size 10
void print(int arr[],int n)
{
int i;
for (i=0;i<n;i++)
{
printf ("%d ",arr[i]);
}

}
void merge(int arr[],int low,int mid,int high)
{
int i,j,k=0;
i=low;
j=mid+1;
int temp[size];
while(i<=mid&&j<=high)
{
if(arr[i]<arr[j])
{
temp[k]=arr[i];
k++;
i++;
}
else
{
temp[k]=arr[j];
k++;
j++;
}
}
while(i<=mid)
{
 temp[k]=arr[i];
k++;
i++;
}
while(j<=high)
{
temp[k]=arr[j];
k++;
j++;
}
for(i=high;i>=low;i--)
{
arr[i]=temp[--k];
}
}
void mergesort(int arr[],int low,int high)
{
if(low==high)
return;

int mid=(low+high)/2;
mergesort(arr,0,mid);
mergesort(arr,mid+1,high);
merge(arr,low,mid,high);
}
int main()
{
int i;
printf("\n The size of the array is :%d",size);
int arr[size];
printf("\n Enter the number :");
for(i=0;i<size;i++)
{
scanf("%d",&arr[i]);
}
printf("\nBefore sorting : ");
print(arr,size);
printf("\nAfter sorting : ");
mergesort(arr,0,size-1);
print(arr,size);

return 0;
}

Output:-

The size of the array is :10

Enter the number :34 12 34 11 22 33 44 56 98 19

Before sorting : 34 12 34 11 22 33 44 56 98 19
After sorting : 11 12 19 22 33 34 34 44 56 98
23) Write a program to create a binary tree and then traverse using in order, pre
order post order traversing techniques.

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* left;
struct Node* right;
};
void inorderTraversal(struct Node* root) {

if (root == NULL)
return;
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);

}
void preorderTraversal(struct Node* root) {

if (root == NULL)
return;
printf("%d ", root->data);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
void postorderTraversal(struct Node* node) {

if (node == NULL)
return;
postorderTraversal(node->left);
postorderTraversal(node->right);
printf("%d ", node->data);
}

struct Node* newNode(int data) {

struct Node* node =
(struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}

int main() {
struct Node* root = newNode(1);
 root->left = newNode(2);
root->right = newNode(3);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
printf("Preorder traversal: ");
preorderTraversal(root);
printf("\n");
printf("Inorder traversal: ");
inorderTraversal(root);
printf("\n");
printf("Postorder traversal: ");
postorderTraversal(root);
return 0;
}

Output:-

Preorder traversal: 1 2 4 5 3 6 7
Inorder traversal: 4 2 5 1 6 3 7
Postorder traversal: 4 5 2 6 7 3 1

24) Write a program to create BST and print all elements using in order
traversing technique. Create user defined function for each operation and call
then in main function.

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node *left, *right;
};

struct Node* createNode(int data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
struct Node* insert(struct Node* root, int data) {
if (root == NULL)
return createNode(data);
if (data < root->data)
root->left = insert(root->left, data);
else if (data > root->data)
root->right = insert(root->right, data);
return root;
}

void inorderTraversal(struct Node* root) {

if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}

int main() {
struct Node* root = NULL;
int n, data, i;

printf("Enter the number of elements to insert: ");

scanf("%d", &n);

printf("Enter the elements: ");

for (i = 0; i < n; i++) {
scanf("%d", &data);
root = insert(root, data);
}

printf("In-order Traversal: ");

inorderTraversal(root);
printf("\n");

return 0;
}

Output:-

Enter the number of elements to insert: 6

Enter the elements: 2 4 7 8 1 4
In-order Traversal: 1 2 4 7 8
25) Write a program to create a graph and then traverse using BFS and DFS
traversing techniques.

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

int graph[MAX][MAX], visited[MAX], queue[MAX], front = -1, rear = -1;

void addEdge(int u, int v) {

graph[u][v] = 1;
graph[v][u] = 1;
}

void bfs(int start, int n) {

int i;
front = rear = -1;
queue[++rear] = start;
visited[start] = 1;

while (front != rear) {

start = queue[++front];
printf("%d ", start);

for (i = 0; i < n; i++) {

if (graph[start][i] && !visited[i]) {
queue[++rear] = i;
visited[i] = 1;
}
}
}
}

void dfs(int start, int n) {

int i;
printf("%d ", start);
visited[start] = 1;

for (i = 0; i < n; i++) {

if (graph[start][i] && !visited[i]) {
dfs(i, n);
}
}
}

int main() {
int n, edges, u, v, i, start;

printf("Enter the number of vertices: ");

 scanf("%d", &n);

for (i = 0; i < n; i++)

for (int j = 0; j < n; j++)
graph[i][j] = 0;

printf("Enter the number of edges: ");

scanf("%d", &edges);

for (i = 0; i < edges; i++) {

printf("Enter edge (u v): ");
scanf("%d %d", &u, &v);
addEdge(u, v);
}

printf("Enter the starting vertex for BFS: ");

scanf("%d", &start);
for (i = 0; i < n; i++)
visited[i] = 0;
printf("BFS Traversal: ");
bfs(start, n);
printf("\n");

printf("Enter the starting vertex for DFS: ");

scanf("%d", &start);
for (i = 0; i < n; i++)
visited[i] = 0;
printf("DFS Traversal: ");
dfs(start, n);
printf("\n");

return 0;
}

Output:-

Enter the number of vertices: 5

Enter the number of edges: 6
Enter edge (u v): 0 1
Enter edge (u v): 0 2
Enter edge (u v): 1 3
Enter edge (u v): 1 4
Enter edge (u v): 2 4
Enter edge (u v): 3 4
Enter the starting vertex for BFS: 0
Enter the starting vertex for DFS: 0

BFS Traversal: 0 1 2 3 4
DFS Traversal: 0 1 3 4 2