ITM UNIVERSITY GWALIOR

DEPARTMENT OF COMPUTER SCIENCE & APPLICATIONS

LAB MANUAL

Subject Name: Data Structures

PREPARED BY

Mr. Suraj Sharma

Assistant Professor
 Table of Contents
S. No. Program details Page No.
1 Write a program in C to implement array and traverse all the elements of
the array.
2 Write a program in C to insert an element at Kth location of the array.
3 Write a program in C to delete an element from the array with given
item of information.
4 Write a program in C to implement the bubble sort algorithm.
5 Write a program in C to implement the linear search algorithm.
6 Write a program in C to implement the binary search algorithm.
7 Write a program in C to create and traverse the elements of the two-
dimensional array.
8 Write a program in C to create and traverse the elements of the
multidimensional array.
9 Write a program in C to multiply two matrices.
10 Write a program in C to implement triangular sparse matrix.
11 Write a program in C to implement strlen( ) function.
12 Write a program in C to implement strcmp( ) function.
13 Write a program in C to implement strcat( ) function.
14 Write a program in C to implement strcpy( ) function.
15 create and display the element of the linked list
16 search an item with given information
17 search an item in sorted list
18 insert at the begining of the linked list
19 insert a node after the given node
Delete the first node from linked list.

20 delete a node from circular header linked list with a given item of
information
21 traversing the circular header linked list
22 search an item in the circular header linked list
23 delete an item from two-way circular linked list
24 implements the polynomials
25 Convert the given infix expression into postfix expression.
26 factorial function by using recursion
27 Generate the Fibonacci series.
28 implementation of simple queue
29 implementation of circular queue
30 implementation of double ended queue
31 implementation of double ended circular queue input by rear & deletion
from (front & rear)
32 implementation of double ended circular queue deletion by front &
insertion by (front & rear)
33 priority queue by using multiple arrays
34 priority queue by using linked list
35 Implementation of Binary Search Tree.
36 program to implement the insertion sort
37 program to implement the selection sort
 38 Implementation of merge sort

Objective(s): This course aims to teach students:

 familiar with major data structures;

 determine which data structure to use in different scenarios;

 demonstrate understanding of the abstract properties of various data structures such as

stacks, queues, lists, trees and graphs;

 demonstrate understanding of various sorting techniques, including bubble sort, heap

sort and quick sort;

 demonstrate understand understanding of various graph and tree traversal approaches;

 demonstrate understanding of various searching techniques;

 program multiple file programs in a manner that allows for reusability of code;

 compare different implementations of data structures and to recognize the advantages

and disadvantages of the different implementations;

 trace and code recursive functions;

 implement various data structures in more than one manner;

 write complex applications using structured programming methods.

LIST OF PROJECTS

Project Name: Implementation of Recursion and Tracing its Stack.

Description: This project will implement and trace recursive functions.

Basic Idea: When we write and execute any recursive function its implementation is hidden
from us we can’t tell what is happening in background.
In this project, students are required to show the recursion steps that they have studied
practically.

Project Name: Binary Tree Class

Description: This project requires the implementation of all tree related concepts and write an
application that will implement all basic tree related concepts and operations.

Basic Idea: We have studied many basic tree related concepts in our data structure course. In
this project, students are required to implement these concepts practically using C.

Project Name: Sorting Technique

Description: This project requires the implementation of all the sorting algorithms and writes
an application that will implement all basic sorting concepts and operations.

Basic Idea: We have studied many number of sorting techniques in data structure course. In
this project, students are required to implement these concepts and show all the intermediate
steps of each technique using C.

Project Name: Path Matrix for Graph

Description: This project requires generating the path matrix of different order for the graph
details submitted by the user.

Basic Idea: students are required to implement the concepts of adjacency matrix and also
generate the path matrices using C.
About arrays:
A linear array is a list of a finite number of n of homogeneous data elements. Such that
a. The elements of the arrays are referenced respectively by an index set consisting of n
consecutive numbers.
b. The elements of the array are stored respectively in successive memory locations.

The number of elements is called the length or the size of the array. We assume the index set
consisting of the integers 0 to (n-1) { in C language). In other programming language the
index set can be start with any integer.

Experiment No.1

Object: Write a program in C to implement array and traverse all the elements of the array.

Algorithm:
(Traversing a linear array)
1. [Initialize a counter] set K:=LB
2. Repeat step 3 and 4 while K<=UB
3. [Visit elements] apply process to LA[K]
4. [Increase counter] set K:=K+1.
5. Exit

Program:
//implements an array & traverse all the elements of the array
#include<stdio.h>
#include<conio.h>
void main()
{
int a[10];
int i;
clrscr();
for(i=0;i<10;i++)
{
printf("enter the elements of array");
scanf("%d",&a[i]);
}
printf("array is\n");
for(i=0;i<10;i++)
{
printf(" %d",a[i]);
}
getch();
}
 Experiment No.2

Object: Write a program in C to insert an element at Kth location of the array.

Algorithm:

INSERT ( LA,N,K,ITEM)
1. [Initialize counter] set J:=N
2. Repeat step 3 and 4 while J>=K
3. [Move jth element downward] set LA[J+1]:=LA[J]
4. [Decrease counter] set J:=J-1
End of step 2 loop
5. [insert element] set LA[K]:=ITEM
6. [Reset N] set N:=N+1
7. Exit

Program:

//program to implement an array & insert an element at Kth location

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

void main()
{
int a[10];
int i,n,k,item;
printf("enter the no. of elements in the list(less than 10)");
scanf("%d",&n);
//enter the array element
for(i=0;i<n;i++)
{
printf("enter the element No.%d",i+1);
scanf("%d",&a[i]);
}
printf("enter the location to insert new element");
scanf("%d",&k);
printf("enter the element ");
scanf("%d",&item);
//insert element at Kth location
i=n-1;
while(i>=(k-1))
{
a[i+1]=a[i];
i--;
}
a[k-1]=item;
n=n+1;
//traverse the array & display
for(i=0;i<n;i++)
{
printf(" %d",a[i]);
}
getch();
}
 Experiment No.3

Object: Write a program in C to delete an element from the array with given item of
information.

Algorithm:

DELETE( LA,N,K, ITEM)

1. Set ITEM:=LA[K]
2. Repeat for J=K to N-1:
[Move j+1 element upward] set LA[J]:=LA[J+1]
[End of loop]
3. [Reset the number N of the element in LA] set N:=N-1
4. Exit

Program No. 1:
//delete an element by index value
#include<stdio.h>
#include<conio.h>

void main()
{
int a[10];
int i,n,k,item;
clrscr();
printf("enter the no. of elements in the list(not more than 10)");
scanf("%d",&n);
//enter the array element
for(i=0;i<n;i++)
{
printf("enter the element No.%d",i+1);
scanf("%d",&a[i]);
}
printf("enter the location to delete an element from the list");
scanf("%d",&k);

//delete element from Kth location

i=k-1;
while(i<n-1)
{
a[i]=a[i+1];
i++;
}
n=n-1;
//traverse the array & display
for(i=0;i<n;i++)
 {
printf(" %d",a[i]);
}
getch();
}

Program No. 2:

//delete an element by item information

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

void main()
{
int a[10];
int i,n,k,item;
clrscr();
printf("enter the no. of elements in the list(not more than 10)");
scanf("%d",&n);
//enter the array element
for(i=0;i<n;i++)
{
printf("enter the element No.%d",i+1);
scanf("%d",&a[i]);
}
printf("enter the element to delete from the list");
scanf("%d",&item);
//find the location of given item
i=0;
while((a[i]!=item)&&(i<n))
{
i++;
}
if(i==n)
{
printf("item not in the list");
goto level;
}
k=i;
//delete element from Kth location
i=k;
while(i<n-1)
{
a[i]=a[i+1];
i++;
}
n=n-1;
//traverse the array & display
level:
for(i=0;i<n;i++)
 {
printf(" \n %d",a[i]);
}
getch();
}
 Experiment No.4

Object: Write a program in C to implement the bubble sort algorithm.

Algorithm:
BUBBLE( DATA, N)
1. Repeat step 2 and 3 for K=1 to N-1
2. Set PTR:=1
3. Repeat while PTR<=N-K
a. If DATA [PTR]> DATA[PTR+1] then:
Interchange DATA [PTR] and DATA[PTR=1]
[End of is structure]
b. Set PTR:=PTR+1
[End of inner loop]
[End of step 1 outer loop]
4. Exit

Program:
// Implementation of bubble sort algorithm

#include<stdio.h>
#include<conio.h>
#define n 8

void main()
{
int a[n];
int i,k,ptr,b;
clrscr();
//insert elements in to array
for(i=0;i<n;i++)
{
printf("enter the element a[%d] ",i+1);
scanf("%d",&a[i]);
}

// sort the elements of the array

for(k=0;k<n-1;k++)
{
ptr=0;
while(ptr<((n-1)-k))
{
if(a[ptr]>a[ptr+1])
{
b=a[ptr];
a[ptr]=a[ptr+1];
a[ptr+1]=b;
 }
ptr++;
}
}

//traversing of array
printf("Sorted array is");
printf("\n");
for(i=0;i<n;i++)
{
printf(" %d",a[i]);
}
getch();
}
 Experiment No.5

Object: Write a program in C to implement the linear search algorithm.

Algorithm:

LINEAR ( DATA,N,ITEM,LOC)
1. [insert item at the end of DATA] set DATA[N+1]:=ITEM
2. [Initialize counter] set LOC :=1
3. [Search for item]
Repeat while DATA[LOC]!=ITEM
Set LOC:=LOC+1
[end of loop]
4. [Successful] if LOC=N+1 then set LOC:=0
5. Exit

Program:

// implementation of linear search

#include<stdio.h>
#include<conio.h>
#define n 10

void main()
{
int a[n];
int i,item,loc;
clrscr();
for(i=0;i<n;i++)
{
printf("enter the element a[%d] ",i+1);
scanf("%d",&a[i]);
}
printf("Array is");
printf("\n");

for(i=0;i<n;i++)
{
printf(" %d",a[i]);
}
printf("\n");
printf("enter the element to search");
scanf("%d",&item);
i=0;
loc=0;
while((a[i]!=item)&&(i<n))
 {
i++;
}
printf("\n");
if(i<n)
{
loc=i;
printf("%d found at location %d",item,loc+1);
}
else
printf("%d not in the list",item);

getch();
}
 Experiment No.6

Object: Write a program in C to implement the binary search algorithm.

Algorithm:
BINARY ( DATA,LB,UB,ITEM,LOC)
1. Set BG:=LB, END:=UB and MID=INT( ( BEG+END)/2).
2. Repeat step 3 and 4 while BEG<=END AND DATA [MID]!=ITEM
3. If ITEM < DATA[MID] then:
Set END := MID-1
Else
Set BEG:=MID+1
[end of if structure]
4. Set MID:=INT((BEG+END)/2)
[end of step 2 loop]
5. If DATA[MID]=ITEM then
Set LOC:=MID
Else
Set LOC:=NULL
[end of if structure]
6. Exit

Program:

// implementation of binary search

#include<stdio.h>
#include<conio.h>
#define n 10

void main()
{
int a[n];
int i,item,loc;
int beg,end,mid;
clrscr();
//insert elements in the array
for(i=0;i<n;i++)
{
printf("enter the element a[%d] ",i+1);
scanf("%d",&a[i]);
}
printf("Array is");
printf("\n");

//traversing of array
for(i=0;i<n;i++)
 {
printf(" %d",a[i]);
}
printf("\n");
printf("enter the element to search");
scanf("%d",&item);

// implementation of binary search algo

beg=0;
end=n-1;
mid=(beg+end)/2;
while(beg<=end&&a[mid]!=item)
{
if(item<a[mid])
{
end=mid-1;
}
if(item>a[mid])
{
beg=mid+1;
}
mid=(beg+end)/2;
}

if(a[mid]==item)
{
loc=mid;
printf("%d found at %d", item,loc+1);
}
else
printf("%d not found in the list", item);

getch();
}
 Experiment No.7

Object: Write a program in C to create and traverse the elements of the two-dimensional
array.

Program:
// create and display the contents of two-dimensional array
#include<stdio.h>
#include<conio.h>
void main()
{
int a[10][10];
int i,j,m,n;
clrscr();
printf("enter the no. of rows in array");
scanf(" %d",&m);
printf("\nenter the no. of columns in array");
scanf(" %d",&n);
//insert the element into the array
//column wise insertion
for(j=0;j<m;j++)
{
for(i=0;i<n;i++)
{
printf("enter the element a[%d][%d] of array",i,j);
scanf(" %d",&a[i][j]);
}
}

// traverse and display the element of array

for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
printf(" %d",a[i][j]);
}
printf("\n\n");
}
getch();
}
 Experiment No.8

Object: Write a program in C to create and traverse the elements of the multidimensional
array.

Program:

// create and display the contents of multi-dimentional array

#include<stdio.h>
#include<conio.h>
void main()
{
int a[2][2][2];
int i,j,k;
clrscr();
//insert the element into the array
for(k=0;k<2;k++)
{
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
printf("enter the element a[%d][%d][%d] of array",i,j,k);
scanf(" %d",&a[i][j][k]);
}
}
}

// traverse and display the element of array

for(k=0;k<2;k++)
{
printf("\n page %d",k);
printf("\n\n");
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
printf(" %u",a[i][j][k]);
}
printf("\n\n");
}
printf("\n\n\n");
}

getch();
}
 Experiment No.9

Object: Write a program in C to multiply two matrices.

Algorithm:
MATMUL (A,B,C,M,P,N)
1. Repeat step 2 to 4 for I=1 to M
2. Repeat step 3 and 4 for J=1 to N
3. Set C[I,J]:0
4. Repeat step K=1 to P
C[I,J]:=C[I,J]+A[I,K]*B[K,J]
[end of inner loop]
[End of step 2 middle loop]
[End of step 1 outer loop]
5. Exit

Program:

// matrix multiplication
#include<stdio.h>
#include<conio.h>

void main()
{
int a[2][2],b[2][3],c[2][3];
int i,j,k;
clrscr();
// insert elements into matrix a[][]
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
printf("enter the element at a[%d][%d]",i,j );
scanf("%d",&a[i][j]);
}
}
// insert elements into matrix b[][]
for(i=0;i<2;i++)
{
for(j=0;j<3;j++)
{
printf("enter the element at b[%d][%d]",i,j );
scanf("%d",&b[i][j]);
}
printf("\n\n");
 }
// multiply the two matrix a[][] and b[][]
for(i=0;i<2;i++)
{
for(j=0;j<3;j++)
{
c[i][j]=0;
for(k=0;k<2;k++)
{
c[i][j]=c[i][j]+a[i][k]*b[k][j];
}
}
}

// display the elements of the product matrix

for(i=0;i<2;i++)
{
for(j=0;j<3;j++)
{
printf(" %d",c[i][j]);
}
}

getch();
}
 Experiment No.10

Object: Write a program in C to implement triangular sparse matrix.

11
12 13
14 15 16
Program:

//triangular sparse matrix

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

void main()
{
int a[3][3];
int i,j;
clrscr();
//insert the element into the sparse matrix
for(i=0;i<3;i++)
{
for(j=0;j<=i;j++)
{
printf("enter the element a[%d][%d]",i,j);
scanf("%d",&a[i][j]);
}
}
printf("\n\n trangular sparse matrix is");
printf("\n\n");
//display the elements of the array
for(i=0;i<3;i++)
{
for(j=0;j<=i;j++)
{
printf(" %d",a[i][j]);
}
printf("\n\n");
}
getch();
}
About string:

A finite sequence of S of zeros or more characters is called a string. The number of

characters in the string is called the length of the string. The string with zero characters is
called the empty string or the null string.

Experiment No.11

Object: Write a program in C to implement strlen( ) function.

Program:

// implementation of strlen() function

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

void main()
{
char str1[]="shyam";
int l;
clrscr();
l=xstrlen(str1);
printf(" length of %s is %d", str1,l);
getch();
}
xstrlen( char *t)
{
int length=0;
while(*t!='\0')
{
length++;
t++;
}
return(length);
}
 Experiment No.12

Object: Write a program in C to implement strcmp( ) function.

Program:
// implementation of strcmp() function
#include<stdio.h>
#include<conio.h>

void main()
{
char str1[]="ram";
char str2[]="shyam";
int k;
clrscr();
k=xstrcmp(str1,str2);

if(k==0)
{
printf("string str1 and str2 are identical");
}
else if(k<0)
{
printf("string str1 smaller than str2 ");
}
else
printf("string str1 greater than str2 ");

getch();
}
xstrcmp(char *t,char *s)
{
while(*t==*s)
{
if(*t=='\0'||*s=='\0')
{
goto l;
}
t++;
s++;
}
l:
return(*t-*s);
}
 Experiment No.13

Object: Write a program in C to implement strcat( ) function.

Program:
// implementation of strcat() function
#include<stdio.h>
#include<conio.h>

void main()
{
char str1[]="shyam";
char str2[]="ram";
//int l;
clrscr();
xstrcat(str1,str2);
printf("string str1 after concatenation is %s ",str1);
getch();
}
xstrcat( char *t,char *s)
{
while(*t!='\0')
{
t++;
}
while(*s!='\0')
{
*t=*s;
t++;
s++;
}
*t='\0';
return(*t);
}
 Experiment No.14

Object: Write a program in C to implement strcpy( ) function.

Program:
// implementation of strcpy() function
#include<stdio.h>
#include<conio.h>

void main()
{
char str1[]="shyam";
char str2[]="ram";
//int l;
clrscr();
xstrcpy(str1,str2);
printf("string str1 is %s ",str1);
getch();
}
xstrcpy( char *t,char *s)
{
while(*s!='\0')
{
*t=*s;
t++;
s++;
}
*t='\0';
return(*t);
}
 Experiment No.15

Object: create and display the element of the linked list

Program:
//create and display the element of the linked list
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define null 0

struct node
{
int num;
struct node *link;
};
void main()
{
struct node *start,*p,*q;
int n,i,item,loc;
clrscr();
printf("How many no. are in the list");
scanf("%d",&n);
start=(struct node *)malloc(sizeof(struct node));
p=start;
printf("enter 1 number ");
scanf("%d",&p->num);

for(i=1;i<n;i++)
{
p->link=(struct node *)malloc(sizeof(struct node));
p=p->link;
printf("enter %d number ",i+1);
scanf("%d",&p->num);
}
p->link=null;

// traversing the linked list

q=start;
while(q!=null)
{
printf(" %d",q->num);
q=q->link;
}
getch();
}

Experiment No.16

Object: search an item with given information

Program:
//search an item with given information
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define null 0

struct node
{
int num;
struct node *link;
};
void main()
{
struct node *start,*p,*q,*loc;
int n,i,item;
clrscr();
printf("How many no. are in the list");
scanf("%d",&n);
start=(struct node *)malloc(sizeof(struct node));
p=start;
printf("enter 1 number ");
scanf("%d",&p->num);

for(i=1;i<n;i++)
{
p->link=(struct node *)malloc(sizeof(struct node));
p=p->link;
printf("enter %d number ",i+1);
scanf("%d",&p->num);
}
p->link=null;

//search an item with given information

printf("enter the item to search");
scanf("%d",&item);
p=start;
loc=null;
while(p!=null)
{
if(item==p->num)
{
 loc=p;
break;
}
else
p=p->link;

if(loc==null)
{
printf("item not in the list");
}
else
printf("%d found at node %u",item,loc);

// traversing the linked list

q=start;
while(q!=null)
{
printf(" %d",q->num);
q=q->link;
}
getch();
}
 Experiment No.17

Object: search an item in sorted list

Program:
// search an item in sorted list
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define null 0

struct node
{
int num;
struct node *link;
};
void main()
{
struct node *start,*p,*q,*loc;
int n,i,item;
clrscr();
printf("How many no. are in the list");
scanf("%d",&n);
start=(struct node *)malloc(sizeof(struct node));
p=start;
printf("enter 1 number ");
scanf("%d",&p->num);

for(i=1;i<n;i++)
{
p->link=(struct node *)malloc(sizeof(struct node));
p=p->link;
printf("enter %d number ",i+1);
scanf("%d",&p->num);
}
p->link=null;

//search an item with given information

printf("enter the item to search");
scanf("%d",&item);
p=start;
loc=null;
while(p!=null)
{
if(item<(p->num))
{
p=p->link;
 }
else
{
printf("item not in the list");
break;
}
if(item==p->num)
{
loc=p;
break;
}
}

if(loc==null)
{
printf("item not in the list");
}
else
printf("%d found at node %u",item,loc);

// traversing the linked list

q=start;
while(q!=null)
{
printf(" %d",q->num);
q=q->link;
}
getch();
}
 Experiment No.18

Object: insert at the begining of the linked list

Program:
//insert at the beginning of the linked list

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define null 0

struct node
{
int num;
struct node *link;
};
void main()
{
struct node *start,*p,*q;
struct node *avail,*r,*s,*newnode;
int n,i;
clrscr();
printf("How many no. are in the list");
scanf("%d",&n);
start=(struct node *)malloc(sizeof(struct node));
p=start;
printf("enter i number ");
scanf("%d",&p->num);

for(i=1;i<n;i++)
{
p->link=(struct node *)malloc(sizeof(struct node));
p=p->link;
printf("enter %d number ",i+1);
scanf("%d",&p->num);
}
p->link=null;
//defining the avail list
avail=(struct node *)malloc(sizeof(struct node));
r=avail;
for(i=1;i<5;i++)
{
r->link=(struct node *)malloc(sizeof(struct node));
r=r->link;
}
r->link=null;
//inserting a node at the begining of the list
if(avail==null)
{
printf("OVERFLOW:FREE POOL IS EMPTY");
}
else
{
newnode=avail;
avail=avail->link;
newnode->num=10;

// insert node at the begining

newnode->link=start;
start=newnode;
}

//traversing the list

q=start;
while(q!=null)
{
printf(" %d",q->num);
q=q->link;
}
getch();
}

//insert at the end of the linked list

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define null 0

struct node
{
int num;
struct node *link;
};
void main()
{
struct node *start,*p,*q;
struct node *avail,*r,*s,*newnode;
int n,i;
clrscr();
printf("How many no. are in the list");
scanf("%d",&n);
start=(struct node *)malloc(sizeof(struct node));
p=start;
 printf("enter i number ");
scanf("%d",&p->num);

for(i=1;i<n;i++)
{
p->link=(struct node *)malloc(sizeof(struct node));
p=p->link;
printf("enter %d number ",i+1);
scanf("%d",&p->num);
}
p->link=null;
//defining the avail list
avail=(struct node *)malloc(sizeof(struct node));
r=avail;
for(i=1;i<5;i++)
{
r->link=(struct node *)malloc(sizeof(struct node));
r=r->link;
}
r->link=null;

//inserting a node at the end of the list

if(avail==null)
{
printf("OVERFLOW:FREE POOL IS EMPTY");
}
else
{
newnode=avail;
avail=avail->link;
newnode->num=10;

q=start;
while(q->link!=null)
{
q=q->link;
}

// insert node at the end

newnode->link=q->link;
q->link=newnode;
}

//traversing the list

q=start;
while(q!=null)
{
printf(" %d",q->num);
q=q->link;
}
getch();
}

Experiment No.19

Object: insert a node after the given node

Program:
//insert a node after the given node

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define null 0

struct node
{
int num;
struct node *link;
};
void main()
 {
struct node *start,*p,*q,*loc;
struct node *avail,*r,*s,*newnode;
int n,i,item;
clrscr();
printf("How many no. are in the list");
scanf("%d",&n);
start=(struct node *)malloc(sizeof(struct node));
p=start;
printf("enter i number ");
scanf("%d",&p->num);

for(i=1;i<n;i++)
{
p->link=(struct node *)malloc(sizeof(struct node));
p=p->link;
printf("enter %d number ",i+1);
scanf("%d",&p->num);
}
p->link=null;

//defining the avail list

avail=(struct node *)malloc(sizeof(struct node));
r=avail;
for(i=1;i<5;i++)
{
r->link=(struct node *)malloc(sizeof(struct node));
r=r->link;
}
r->link=null;

//inserting a node at the begining of the list

if(avail==null)
{
printf("OVERFLOW:FREE POOL IS EMPTY");
}
newnode=avail;
avail=avail->link;
newnode->num=10;
printf("enter the location after which you want to insert");
scanf("%d", &item);
// search the location
p=start;
loc=null;
while(p!=null)
{
if(p->num==item)
{
loc=p;
break;
 }
else
p=p->link;
}
if(loc==null)
{
newnode->link=start;
start=newnode;
}
else
{
newnode->link=loc->link;
loc->link=newnode;
}

//traversing the list

q=start;
while(q!=null)
{
printf(" %d",q->num);
q=q->link;
}
getch();
}

//delete the first node from linked list

#include <stdio.h>
#include <malloc.h>
#define null 0

struct node
{
int info;
struct node *link;
};

int main()
{
struct node *start,*avail,*ptr,*newnode;
int n,i,p;
printf("\n enter the no. of nodes in start linked list");
scanf("%d", &n);
//start list creation
if(n==0)
start=null;
else
{
start=malloc(sizeof(struct node));
ptr=start;
printf("\n enter the info of node: 1");
scanf("%d", &ptr->info);
for(i=1;i<n;i++)
{
ptr->link=malloc(sizeof(struct node));
ptr=ptr->link;
printf("\n enter the info of node: %d", i+1);
scanf("%d", &ptr->info);
}
ptr->link=null;
}
//avail list
printf("\n enter the no. of nodes in avail linked list");
scanf("%d", &n);
//avail list creation
if(n==0)
avail=null;
else
{
avail=malloc(sizeof(struct node));
ptr=avail;
for(i=1;i<n;i++)
{
ptr->link=malloc(sizeof(struct node));
ptr=ptr->link;

}
ptr->link=null;
}
//traverse the linked list
printf("\nstart list before the deletion\n");
ptr=start;
while(ptr!=null)
{
printf("%d ",ptr->info);
ptr=ptr->link;
}
//delete the first node
if(start==null)
{
printf("\nUNDERFLOW\n");
}
else
{
newnode=start;start=start->link;
newnode->link=avail;avail=newnode;
}
//traverse the linked list
printf("\nstart list after the deletion\n");
if(start==null)
 {
printf("\nstart list is empty\n");
}
else
{
ptr=start;
while(ptr!=null)
{
printf("%d ",ptr->info);
ptr=ptr->link;
}
}

printf("\nno. of nodes in avail list after the deletion\n");

p=0;
ptr=avail;
while(ptr!=null)
{
p++;
ptr=ptr->link;
}

printf("\nno. of nodes in avail list after the deletion: %d",p);

return 0;
}

// Insert a new node after a given node in grounded header linked list.
#include <stdio.h>
#include <malloc.h>
#define null 0

struct node
{
int info;
struct node *link;
};

int main()
{
struct node *start,*avail,*ptr,*newnode;
int n,i,item;
//create the start list
printf("\n No. of nodes in start list: ");
scanf("%d",&n);//5
if(n==0)
start=null;
else
{
 start=malloc(sizeof(struct node));
ptr=start;

for(i=0;i<n;i++)
{
ptr->link=malloc(sizeof(struct node));
ptr=ptr->link;
printf("\n info of node: %d",i+1);
scanf("%d",&ptr->info);
}
ptr->link=null;
}
//avail list
printf("\n No. of nodes in avail list: ");
scanf("%d",&n);//5
if(n==0)
avail=null;
else
{
avail=malloc(sizeof(struct node));
ptr=avail;
for(i=1;i<n;i++)
{
ptr->link=malloc(sizeof(struct node));
ptr=ptr->link;

}
ptr->link=null;
}

//traverse the list before the insertion

printf("\n Start list before the insertion...\n");
ptr=start->link;
while(ptr!=null)
{
printf("%d ",ptr->info);
ptr=ptr->link;
}

//insert a new node after a given node in header linked list

printf("\n info of node after which new node has to be inserted ");
scanf("%d",&item);
if(avail==null)
printf("\n OVERFLOW\n");
else
{
newnode=avail;avail=avail->link;newnode->info=20;
ptr=start->link;
while(ptr!=null&&ptr->info!=item)
{
 ptr=ptr->link;
}
if(ptr==null)
{
newnode->link=start->link;start->link=newnode;
}
else
{
newnode->link=ptr->link;ptr->link=newnode;
}
}

//traverse the list before the insertion

printf("\n Start list after the insertion...\n");
ptr=start->link;
while(ptr!=null)
{
printf("%d ",ptr->info);
ptr=ptr->link;
}

return 0;
}

// Delete a given new node from grounded header linked list with given item of information.
#include <stdio.h>
#include <malloc.h>
#define null 0

struct node
{
int info;
struct node *link;
};

int main()
{
struct node *start,*avail,*ptr,*newnode;
int n,i,item;
//create the start list
printf("\n No. of nodes in start list: ");
scanf("%d",&n);//5
if(n==0)
start=null;
else
{
start=malloc(sizeof(struct node));
ptr=start;

for(i=0;i<n;i++)
 {
ptr->link=malloc(sizeof(struct node));
ptr=ptr->link;
printf("\n info of node: %d",i+1);
scanf("%d",&ptr->info);
}
ptr->link=null;
}
//avail list
printf("\n No. of nodes in avail list: ");
scanf("%d",&n);//5
if(n==0)
avail=null;
else
{
avail=malloc(sizeof(struct node));
ptr=avail;
for(i=1;i<n;i++)
{
ptr->link=malloc(sizeof(struct node));
ptr=ptr->link;

}
ptr->link=null;
}

//traverse the list before the insertion

printf("\n Start list before the insertion...\n");
ptr=start->link;
while(ptr!=null)
{
printf("%d ",ptr->info);
ptr=ptr->link;
}

//insert a new node after a given node in header linked list

printf("\n info of node after which new node has to be inserted ");
scanf("%d",&item);
if(avail==null)
printf("\n OVERFLOW\n");
else
{
newnode=avail;avail=avail->link;newnode->info=20;
ptr=start->link;
while(ptr!=null&&ptr->info!=item)
{
ptr=ptr->link;
}
if(ptr==null)
{
 newnode->link=start->link;start->link=newnode;
}
else
{
newnode->link=ptr->link;ptr->link=newnode;
}
}

//traverse the list before the insertion

printf("\n Start list after the insertion...\n");
ptr=start->link;
while(ptr!=null)
{
printf("%d ",ptr->info);
ptr=ptr->link;
}

return 0;
}

Experiment No.20

Object: delete a node from circular header linked list with a given item of information
Program:
//delete a node from circular header linked list with a given item of information

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define null 0

struct node
{
int num;
struct node *link;
};
void main()
{
struct node *start,*p,*q,*loc,*locp;
struct node *avail,*r,*s,*newnode,*save,*ptr;
int n,i,item;
clrscr();
printf("How many no. are in the list");
scanf("%d",&n);
//header node
start=(struct node *)malloc(sizeof(struct node));
p=start;

for(i=0;i<n;i++)
{
 p->link=(struct node *)malloc(sizeof(struct node));
p=p->link;
printf("enter %d number ",i+1);
scanf("%d",&p->num);
}
p->link=start;

//defining the avail list

avail=(struct node *)malloc(sizeof(struct node));
r=avail;
for(i=1;i<5;i++)
{
r->link=(struct node *)malloc(sizeof(struct node));
r=r->link;
}
r->link=null;
//check the underflow condition
if( start==null)
{
loc=null;
locp=null;
printf("UNDERFLOW");
}
loc=null;
locp=null;

printf("enter the item information to delete");

scanf("%d", &item);
// search the location
if(start->num==item)
{
loc=start;
locp=null;
goto l;
}
save=start;
ptr=start->link;

while(ptr!=null)
{
if(ptr->num==item)
{
loc=ptr;
locp=save;
break;
}
save=ptr;
ptr=ptr->link;
}
l:
//delete the node
if(loc==null)
{
printf("item not in the list");
goto j;
}
else if(locp==null)
{
start=start->link;
}
else
{
locp->link=loc->link;
}
loc->link=avail;
avail=loc;

j:
//traversing the list
q=start;
while(q!=null)
{
printf(" %d",q->num);
q=q->link;
}
getch();
}
 Experiment No.21

Object: traversing the circular header linked list

Program:
//traversing the circular header linked list

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define null 0

struct node
{
int num;
struct node *link;
};
void main()
{
struct node *start,*p,*q;
//struct node *avail,*r,*s,*newnode,*save,*ptr;
int n,i,item,loc;
clrscr();
printf("How many no. are in the list");
scanf("%d",&n);
//header node
start=(struct node *)malloc(sizeof(struct node));
p=start;

for(i=0;i<n;i++)
{
 p->link=(struct node *)malloc(sizeof(struct node));
p=p->link;
printf("enter %d number ",i+1);
scanf("%d",&p->num);
}
p->link=start;

loc=0;
//traversing the circular header linked list
q=start->link;
while(q!=start)
{
loc++;
printf(" %d",q->num);
q=q->link;
}
start->num=loc;
printf("total number of nodes in the list are %d",start->num);
getch();
}
Experiment No.22

Object: search an item in the circular header linked list

Program:
//search an item in the circular header linked list

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define null 0

struct node
{
int num;
struct node *link;
};
void main()
{
struct node *start,*p,*q;
//struct node *avail,*r,*s,*newnode,*save,*ptr;
int n,i,item,loc;
clrscr();
printf("How many no. are in the list");
scanf("%d",&n);
//header node
start=(struct node *)malloc(sizeof(struct node));
p=start;

for(i=0;i<n;i++)
{
 p->link=(struct node *)malloc(sizeof(struct node));
p=p->link;
printf("enter %d number ",i+1);
scanf("%d",&p->num);
}
p->link=start;

printf(" enter the item to search");

scanf("%d",&item);
//search the item in the list
loc=0;
q=start->link;

while(q!=start)
{
loc++;
if(q->num==item)
{
break;
}
q=q->link;
}
if(q==start)
{
printf("item not in the list");
}
else
{
printf("item %d found at node %d",item,loc);
}

loc=0;
//traversing the circular header linked list
q=start->link;
while(q!=start)
{
loc++;
printf(" %d",q->num);
q=q->link;
}
start->num=loc;
printf("\n\ntotal number of nodes in the list are %d",start->num);
getch();
}
 Experiment No.23

Object: delete an item from two-way circular linked list

Program:
//delete an item from two-way circular linked list

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define null 0

struct node
{
int num;
struct node *back;
struct node *forw;
};
void main()
{
struct node *start,*p,*q,*last,*loc;
//struct node *avail,*r,*s,*newnode,*save,*ptr;
int n,i,item;
clrscr();
printf("How many no. are in the list");
scanf("%d",&n);
//header node
start=(struct node *)malloc(sizeof(struct node));
p=start;
p->back=null;
printf("enter 1 number ");
 scanf("%d",&p->num);

for(i=1;i<n;i++)
{
p->forw=(struct node *)malloc(sizeof(struct node));
p->forw->back=p;
p=p->forw;
printf("enter %d number ",i+1);
scanf("%d",&p->num);
}
p->forw=null;
last=p;

printf(" enter the item to delete");

scanf("%d",&item);
//search the item in the list

p=start;

while(p!=null)
{

if(p->num==item)
{
loc=p;
break;
}
p=p->forw;
}
if(p==null)
{
printf("item not in the list");
}
else
{
loc->back->forw=loc->forw;
loc->forw->back=loc->back;
}

//traversing the circular header linked list

printf("\ntraverse the list in forw direction");
p=start;
while(p!=null)
{
printf(" %d",p->num);
last=p;
p=p->forw;
}
printf("\n\ntraverse the list in back direction");
q=last;
while(q!=null)
{
printf(" %d",q->num);
q=q->back;
}

getch();
}

Experiment No.24

Object: implements the polynomials

Program:
//implements the polynomials

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define null 0
#include<math.h>

struct node
{
int coef;
int exp;
struct node *link;
};
void main()
{
struct node *poly,*p,*q;
int n,i,x,pp;
clrscr();
printf("How many no. are in the list");
scanf("%d",&n);

//header node
poly=(struct node *)malloc(sizeof(struct node));
p=poly;
 for(i=0;i<n;i++)
{
p->link=(struct node *)malloc(sizeof(struct node));
p=p->link;
printf("enter the coef in node %d:",i+1);
scanf("%d",&p->coef);
printf("enter the exp in node %d:",i+1);
scanf("%d",&p->exp);
}
p->link=poly;
printf("enter the value of x:");
scanf("%d",&x);
pp=0;
p=poly->link;
while(p!=poly)
{
pp=pp+(p->coef)*(pow(x,p->exp));
p=p->link;
}
printf("\nvalue of polynomial is %d",pp);

//traversing the list

q=poly->link;
while(q!=poly)
{
printf(" \n%d %d",q->coef,q->exp);
q=q->link;
}

getch();
}
 Experiment No.25

Object: convert the given infix expression into postfix expression.

Program:
//infix to postfix
#include<stdio.h>
#include<conio.h>

void postfix();
void push(int);
char pop();
char inf[40],post[40];
int top=-1;
int st[20];

void main()
{
/*
char inf[40],post[40];
int top=-1;
int st[20];
*/
clrscr();
printf("enter the infix expression");
scanf("%s",inf);
postfix();
getch();
}
//postfix conversion
void postfix()
 {
int i,j=0;
for(i=0;inf[i]!='\0';i++)
{
switch(inf[i])
{
case '+':
while(st[top]>=1)
post[j++]=pop();
push(1);
break;
case '-':
while(st[top]>=1)
post[j++]=pop();
push(2);
break;
case '*':
while(st[top]>=3)
post[j++]=pop();
push(3);
break;
case '/':
while(st[top]>=3)
post[j++]=pop();
push(4);
break;
case '^':
while(st[top]>=4)
post[j++]=pop();
push(5);
break;
case '(':
push(0);
break;
case ')':
while(st[top]!=0)
post[j++]=pop();
top--;
break;
default:
post[j++]=inf[i];
}
}
// printf the postfix expression
while(top>-1)
post[j++]=pop();
printf("\n postfix expression is %s:",post);
}
void push(int ele)
{
top++;
st[top]=ele;
}

char pop()
{
int el;
char e;
el=st[top];
top--;
switch(el)
{
case 1:
e='+';
break;
case 2:
e='-';
break;
case 3:
e='*';
break;
case 4:
e='/';
break;
case 5:
e='^';
break;
}
return(e);
}
 Experiment No.26

Object: factorial function by using recursion

Program:
//factorial function by using recursion
#include<stdio.h>
#include<conio.h>

void main()
{
int n;
clrscr();
printf("enter the No. of which you want to find the factorial");
scanf("%d",&n);
factorial(n);
printf("factorial of %d=%d",n,factorial(n));
getch();
}
int factorial( int n)
{
if(n==0)
return(1);
else
return(n*factorial(n-1));
}
 Experiment No.27

Object: Generate the Fibonacci series.

Program:
//fibonacci series
#include<stdio.h>
#include<conio.h>

void main()
{
int n;
int i=0;
clrscr();
printf("input the number for fibonacci series");
scanf("%d",&n);
printf("\n fibonacci series as follows");
while(i<n)
{
printf(" %d",fibo_number(i));
i++;
}
getch();
}

fibo_number( int n)
{
if((n==0)||(n==1))
return(n);
else
return(fibo_number(n-1)+fibo_number(n-2));
}

Experiment No.28

Object: implementation of simple queue

Program:

// implementation of simple queue

#include<stdio.h>
#include<conio.h>
#define n 10
#define null -1

void main()
{
int queue[n];
int q,i;
int front=null;
int rear=null;
printf("enter the no. of elements onto the queue");
scanf("%d",&q);

for(i=0;i<q;i++)
{
if((front==0&&rear==(n-1))||front==rear+1)
{
printf("OVERFLOW");
return;
}
if(front==null)
{
front=0;
 rear=0;
}
else
rear=rear+1;
printf("enter the %d element",i+1);
scanf("%d",&queue[i]);
}

//traversing the queue

for(i=front;i<=rear;i++)
{
printf(" %d",queue[i]);
}
getch();
}

Experiment No.29
Object: implementation of circular queue
Program:
//implementation of circular queue
#include<stdio.h>
#include<conio.h>
#define size 5
#define null -1
void main()
{
int q[size];
int front=null;
int rear=null;
int choice,num,i;
clrscr();
do
{
//clrscr();
printf("\n1. insert");
printf("\n2. delete");
printf("\n3. display");
printf("\n4. exit");
printf("\nenter your choice ");
scanf("%d",&choice);
switch(choice)
{
case 1:
if(front==(rear+1)%size)
{
printf("OVERFLOW: queue if full");
 break;
}
else
{
printf("\nenter the number to be inserted");
scanf("%d",&num);
if(front==-1)
{
front=rear=0;
}
else
rear=(rear+1)%size;
}
q[rear]=num;

break;
case 2:
if(front==-1)
{
printf("\nqueue is empty");
return;
}
else
{
num=q[front];
printf("deleted element is : %d",num);
if(front==rear)
{
front=rear=-1;
}
else
front=(front+1)%size;
}
printf("\n\n");

break;
case 3:
printf("\n\n");
//display the circular queue
printf("\ncircular queue after traversing");
//i=front;
if(front==-1)
{
printf("\nqueue is empty");
break;
}
else
{
i=front;
while(i!=rear)
 {
printf(" %d",q[i]);
i=(i+1)%size;
}
printf(" %d",q[i]);
}
break;
case 4:
return;
}
}
while(choice!=4);
getch();
}

Experiment No.30
Object: implementation of double ended queue
Program:
//implementation of double ended queue
#include<stdio.h>
#include<conio.h>
#define size 5
#define null -1

void main()
{
int q[size];
int front=null;
int rear=null;
int choice,num,i;
clrscr();
do
{
printf("\n1. insert by front ");
printf("\n2. insert by rear ");
printf("\n3. delete by front");
printf("\n4. delete by rear");
printf("\n5. display");
printf("\n6. exit");
printf("\nenter your choice ");
scanf("%d",&choice);
switch(choice)
{
case 1:
//insertion by front
 if(front==0)
{
printf("OVERFLOW: FRONT IS FULL");
break;
}
if(front==-1)
{
printf("\nillegal selection");
break;
}
if(front<size&&front>0)
{
front=front-1;
printf("\nenter the no. to be inserted");
scanf("%d",&num);
q[front]=num;
}
break;
case 2:
//insertion by rear
if(front==0&&rear==(size-1))
{
printf("\nOVERFLOW: REAR IS FULL");
break;
}
if(front==-1)
{
front=0;
}
if(rear<size)
{
rear++;
printf("\nenter the no. to be inserted");
scanf("%d",&num);
q[rear]=num;
}
break;
case 3:
//deletion by front
if(front==-1&&rear==-1)
{
printf("\nUNDERFLOW: QUEUE IS EMPTY");
break;
}
if(front>-1)
{
num=q[front];
printf("deleted item from front is: %d",num);
}
if(front==rear)
 {
front=rear=-1;
}
else
{
front=front+1;
//printf("deleted item from front is: %d",num);
}
break;
case 4:
//deletion by rear
if(front==-1&&rear==-1)
{
printf("\nUNDERFLOW: QUEUE IS EMPTY");
break;
}
if(rear>-1)
{
num=q[rear];
}
if(front==rear)
{
front=rear=-1;
}
else
{
rear=rear-1;
printf("deleted item from rear is: %d",num);
}
break;
case 5:
printf("\n\n");
//display the circular queue
printf("\ndouble ended queue after traversing");
//i=front;
if(front==-1&&rear==-1)
{
printf("\nqueue is empty");
break;
}
else
{
for(i=front;i<=rear;i++)
{
printf(" %d",q[i]);
}
}
break;
case 6:
return;
 }
printf("\n\n");
}
while(choice!=6);
getch();
}

Experiment No.31
Object: implementation of double ended circular queueinput by rear & deletion from (front
& rear)
Program:
/*implementation of double ended circular queue
input by rear & deletion from (front & rear)*/

#include<stdio.h>
#include<conio.h>
#define size 5
#define null -1

void main()
{
int q[size];
int front=null;
int rear=null;
int choice,num,i;
clrscr();
do
{
printf("\n1. insert by rear ");
printf("\n2. delete by front");
printf("\n3. delete by rear");
printf("\n4. display");
printf("\n5. exit");
printf("\nenter your choice ");
scanf("%d",&choice);
switch(choice)
{
case 1:
//insertion by rear
if(front==(rear+1)%size)
{
printf("\nOVERFLOW: QUEUE IS FULL");
break;
}
if(front==-1)
{
front=rear=0;
}
else
{
rear=(rear+1)%size;
}
printf("\n enter the no. to be inserted");
scanf("%d",&num);
q[rear]=num;
break;
case 2:
//deletion by front
if(front==-1&&rear==-1)
{
printf("\nUNDERFLOW: QUEUE IS EMPTY");
break;
}
if(front>-1)
{
num=q[front];
printf("deleted item from front is: %d",num);
}
if(front==rear)
{
front=rear=-1;
}
else
{
front=(front+1)%size;
//printf("deleted item from front is: %d",num);
}
break;
case 3:
//deletion by rear
if(front==-1&&rear==-1)
{
printf("\nUNDERFLOW: QUEUE IS EMPTY");
break;
}
if(rear>-1)
{
 num=q[rear];
printf("deleted item from rear is: %d",num);
}
if(front==rear)
{
front=rear=-1;
}
else if(front<rear)
{
rear=rear-1;
}
else if(front>rear)
{
if(rear==0)
{
rear=(size-1);
}
else
rear=rear-1;
}
break;
case 4:
printf("\n\n");
//display the circular queue
printf("\ndouble ended circular queue after traversing");
//i=front;
if(front==-1&&rear==-1)
{
printf("\nqueue is empty");
break;
}
else
{
i=front;
while(i!=rear)
{
printf(" %d",q[i]);
i=(i+1)%size;
}
printf(" %d",q[i]);
}
break;
case 5:
return;
}
printf("\n\n");
}
while(choice!=5);
getch();
}
 Experiment No.32
Object: implementation of double ended circular queue deletion by front & insertion by
(front & rear)
Program:
/*implementation of double ended circular queue
deletion by front & insertion by (front & rear)*/

#include<stdio.h>
#include<conio.h>
#define size 5
#define null -1

void main()
{
int q[size];
int front=null;
int rear=null;
int choice,num,i;
clrscr();
do
{
printf("\n1. insert by rear ");
printf("\n2. delete by front");
printf("\n3. insert by front");
printf("\n4. display");
printf("\n5. exit");
printf("\nenter your choice ");
scanf("%d",&choice);
switch(choice)
{
case 1:
//insertion by rear
if(front==(rear+1)%size)
{
printf("\nOVERFLOW: QUEUE IS FULL");
break;
}
if(front==-1)
{
front=rear=0;
}
else
{
rear=(rear+1)%size;
}
printf("\n enter the no. to be inserted");
scanf("%d",&num);
q[rear]=num;
break;
case 2:
//deletion by front
if(front==-1&&rear==-1)
{
printf("\nUNDERFLOW: QUEUE IS EMPTY");
break;
}
if(front>-1)
{
num=q[front];
printf("deleted item from front is: %d",num);
}
if(front==rear)
{
front=rear=-1;
}
else
{
front=(front+1)%size;
//printf("deleted item from front is: %d",num);
}
break;
case 3:
//insertion by front
if(front==0&&rear==(size-1)||rear==(front-1))
{
printf("\nOVERFLOW: QUEUE IS FULL");
break;
}
/*
if(front>0)
 {
front=front-1;
}
*/
if(rear>front||front>0)
{
if(front==0)
{
front=(size-1);
}
else
front=front-1;
}
printf("\n enter the no. to be inserted");
scanf("%d",&num);
q[front]=num;
break;
case 4:
printf("\n\n");
//display the circular queue
printf("\ndouble ended circular queue after traversing");
//i=front;
if(front==-1&&rear==-1)
{
printf("\nqueue is empty");
break;
}
else
{
i=front;
while(i!=rear)
{
printf(" %d",q[i]);
i=(i+1)%size;
}
printf(" %d",q[i]);
}
break;
case 5:
return;
}
printf("\n\n");
}
while(choice!=5);
getch();
}
 Experiment No.33
Object: priority queue by using multiple arrays
Program:
//priority queue by using multiple array
#include<stdio.h>
#include<conio.h>
#define m 3
#define n 5
#define null -1

void main()
{
int q[m][n];
int f1,r1,f2,r2,f3,r3,f4,r4,f5,r5;
int choice,num,i,j,p,i1,i2,i3;
f1=r1=f2=r2=f3=r3=null;
clrscr();
do
{
printf("\n1. insert into queue");
printf("\n2. delete from queue");
printf("\n3. display");
printf("\n4. exit");
printf("\nenter your choice ");
scanf("%d",&choice);
switch(choice)
{
case 1:
//insertion into queue
printf("enter the priority of item");
scanf("%d",&p);
printf("enter the information of item");
scanf("%d",&num);
switch(p)
{
case 1://first row
if(f1==(r1+1)%n)
{
printf("OVERFLOW:QUEUE OF PRIORITY: 1 IS FULL");
break;
}
if(f1==null)
{
f1=r1=0;
}
else
{
r1=(r1+1)%n;
}
j=r1;
q[0][j]=num;
break;
case 2://second row
if(f2==(r2+1)%n)
{
printf("OVERFLOW:QUEUE OF PRIORITY: 2 IS FULL");
break;
}
if(f2==null)
{
f2=r2=0;
}
else
{
r2=(r2+1)%n;
}
j=r2;
q[1][j]=num;
break;
case 3://third row
if(f3==(r3+1)%n)
{
printf("OVERFLOW:QUEUE OF PRIORITY: 3 IS FULL");
break;
}
if(f3==null)
{
f3=r3=0;
 }
else
{
r3=(r3+1)%n;
}
j=r3;
q[2][j]=num;
break;
default:
printf("please check the priority of the item");
break;

}
break;
case 2: //deletion from queue
if(f1==-1&&r1==-1)
{
printf("UNDERFLOW: QUEUE: 1. IS EMPTY");
break;
}
else
{
if(f1==r1)
{
f1=r1=-1;
}
else
f1=(f1+1)%n;
}
break;
case 3: //display the item of queue
for(i=0;i<m;i++)
{
if(i==0)
{
if(f1==-1&&r1==-1)
{
printf("QUEUE: 1. IS EMPTY\n");
//return;
}
else
{
i1=f1;
while(i1!=r1)
{
printf(" %d",q[i][i1]);
i1=(i1+1)%n;
}
printf(" %d",q[i][i1]);
printf("\n\n");
 }
}
//printf("\n");
if(i==1)
{
if(f2==-1&&r2==-1)
{
printf("QUEUE: 2. IS EMPTY\n");
//return;
}
else
{
i2=f2;
while(i2!=r2)
{
printf(" %d",q[i][i2]);
i2=(i2+1)%n;
}
printf(" %d",q[i][i2]);
printf("\n\n");
}
}
//printf("\n");
if(i==2)
{
if(f3==-1&&r3==-1)
{
printf("QUEUE: 3. IS EMPTY\n");
//return;
}
else
{
i3=f3;
while(i3!=r3)
{
printf(" %d",q[i][i3]);
i3=(i3+1)%n;
}
printf(" %d",q[i][i3]);
printf("\n\n");
}
}
//printf("\n");
}
break;
case 4:
return;
}
printf("\n\n");
}
 while(choice!=4);
getch();
}

Experiment No.34
Object: priority queue by using linked list
Program:
/*****priority queue by using linked list********************/
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define null 0
struct node
{
int pri;
int info;
struct node *link;
};
void main()
{
struct node *start,*ptr,*ins,*loc;
int choice,num,i;
clrscr();
start=(struct node*)malloc(sizeof(struct node));
loc=start;
loc->pri=null;
loc->info=null;
loc->link=null;

do
{
printf("\n1. insert into priority queue");
printf("\n2. delete from priority queue");
printf("\n3. display the queue");
 printf("\n4. exit");
printf("\nenter your choice ");
scanf("%d",&choice);
switch(choice)
{
case 1:
//insertion into queue
ins=(struct node*)malloc(sizeof(struct node));
ins->link=null;
printf("enter the priority of the node");
scanf("%d",&ins->pri);
printf("enter the information of the node");
scanf("%d",&ins->info);
if(loc->link==null)
{
ins->link=loc->link;
loc->link=ins;
}
else
{
loc=start;
ptr=start->link;
while(ptr->pri<ins->pri&&ptr->link!=null)
{
loc=ptr;
ptr=ptr->link;
}
if(ptr->pri>ins->pri)
{
ins->link=loc->link;
loc->link=ins;
}
if(ptr->pri<=ins->pri)
{
ins->link=ptr->link;
ptr->link=ins;
}

}
break;
case 2://delete from queue
ptr=start->link;
if(ptr==null)
{
printf("UNDERFLOW: QUEUE IS EMPTY");
break;
}
else
{
printf(" item deleted is: priority[%d] infor[%d]",ptr->pri,ptr->info);
 start->link=ptr->link;
}
break;

case 3: //display the queue

ptr=start->link;
if(ptr==null)
{
printf("QUEUE IS EMPTY");
break;
}
else
{
while(ptr!=null)
{
printf("\npriority[%d] information[%d]",ptr->pri,ptr->info);
ptr=ptr->link;
}
}
break;
case 4:
return;
}
printf("\n\n");
}
while(choice!=4);
getch();
}
 Experiment No.35
Object: Implementation of Binary Search Tree.
Program:
//binary search tree implementation
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define null 0

struct node
{
struct node *left;
int data;
struct node *right;
};
void main()
{
struct node *bt;
int n,i,num;
bt=null;
clrscr();
printf("enter the number of nodes in the tree");
scanf("%d",&n);

for(i=0;i<n;i++)
{
printf("enter the data in node %d",i+1);
scanf("%d",&num);
insert(&bt,num);
}
printf("\n inorder traversal");
inorder(bt);
getch();
}
insert (struct node **sr,int num)
{
if(*sr==null)
{
*sr=(struct node *)malloc(sizeof(struct node));
(*sr)->left=null;
(*sr)->data=num;
(*sr)->right=null;
return;
}
else
{
if(num<(*sr)->data)
insert(&((*sr)->left),num);
else
insert(&((*sr)->right),num);
}
return;
}

inorder(struct node *sr)

{
if(sr!=null)
{
inorder(sr->left);
printf(" %d",sr->data);
inorder(sr->right);
}
else
{
return;
}
return;
}
 Experiment No.36
Object: program to implement the insertion sort
Program:

//program to implement the insertion sort

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

void main()
{
int a[11],i,k,temp,ptr;
clrscr();
a[0]=-1;
//inserting elements into array
for(i=1;i<11;i++)
{
printf("enter the %d element",i);
scanf("%d",&a[i]);
}

printf("\nlist of elements before sorting is:");

for(i=1;i<11;i++)
{
printf("%d ",a[i]);
}

//code for insertion sort

for(k=2;k<11;k++)
{
temp=a[k];ptr=k-1;
 {
while(temp<a[ptr])
{
a[ptr+1]=a[ptr];
ptr--;
}
a[ptr+1]=temp;
}
}
//traversing the sorted array
printf("\nsorted list of elements is:");
for(i=1;i<11;i++)
{
printf("%d ",a[i]);
}

getch();
}

Experiment No.37
Object: program to implement the selection sort
Program:
//program to implement the selection sort
#include<stdio.h>
#include<conio.h>

void main()
{
int a[10],i,k,min,j,temp,loc;
clrscr();
//inserting elements into array
for(i=0;i<10;i++)
{
printf("enter the %d element",i);
scanf("%d",&a[i]);
}

printf("\nlist of elements before sorting is:");

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

//code for selection sort

for(k=0;k<9;k++)
{
min=a[k];loc=k;
for(j=(k+1);j<10;j++)
{
 if(min>a[j])
loc=j;
}
temp=a[k];a[k]=a[loc];a[loc]=temp;

}
//traversing the sorted array
printf("\nsorted list of elements is:");
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}

getch();
}

Experiment No.38
Object: Implementation of merge sort
Program:
//implementation of merge sort
#include<stdio.h>
#include<conio.h>

void main()
{
int a[5],b[5],c[10];
int na,nb,ptr,i;
na=nb=ptr=0;
//insert into a
for(i=0;i<5;i++)
{
printf("enter the %d element of A",i+1);
scanf("%d",&a[i]);
}
//insert into b
for(i=0;i<5;i++)
{
printf("enter the %d element of B",i+1);
scanf("%d",&b[i]);
}
//code for merge sort
while(na<5&&nb<5)
{
if(a[na]<b[nb])
{
c[ptr]=a[na];
 ptr++;na++;
}
else
{
c[ptr]=b[nb];
ptr++;nb++;
}
if(na==5)
{
for(i=0;i<=(4-nb);i++)
{
c[ptr+i]=b[nb+i];
}
}
else
{
for(i=0;i<=(4-na);i++)
{
c[ptr+i]=b[na+i];
}
}
}

//traversing the sorted array C

for(i=0;i<10;i++)
{
printf("%d ",c[i]);
}
getch();
}