07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

Children’s Education Society (Regd.)

THE OXFORD COLLEGE OF ENGINEERING
Hosur Road, Bommanahalli, Bangalore

Department of
Master of Computer Applications

A Laboratory Manual

For

DATA STRUCTURES USING ‘C ‘

-07MCA27

2nd Semester, MCA

Dept. of MCA, TOCE, Bangalore 1

 07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA
Sl.No. Date Experiments Index Page Initial of
Faculty
1 Write a C Program to construct a stack of integers and
to perform the following
operations on it:
a. Push
b. Pop
c. Display
The program should print appropriate messages for
stack overflow, stack underflow, and
Stack empty.

2 Write a C Program to convert and print a given valid

parenthesized infix arithmetic
Expression to postfix expression. The expression
consists of single character operands
And the binary operators + (plus), - (minus), *
(multiply) and / (divide).

3 Write a C Program to evaluate a valid suffix/postfix

expression using stack. Assume that the
suffix/postfix expression is read as a single line
consisting of non-negative single digit operands and
binary arithmetic operators. The arithmetic operators
are + (add), -
(Subtract), * (multiply) and / (divide).

4 Write a C program using recursive function for the

following:
a. To calculate GCD and LCM of 2 integer
numbers.
b. To solve Towers of Hanoi problem.

5 Write a C program using recursive function for the

following:
a. To solve Towers of Hanoi problem.
b. To search an element in a list using binary
search

6 . Write a C Program to simulate the working of a

queue of integers using an array.
Provide the following operations:
a. Insert
b. Delete
c. Display

Dept. of MCA, TOCE, Bangalore 2

 07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

7 Write a C Program to simulate the working of a

circular queue of integers using an array.
Provide the following operations:
a. Insert
b. Delete
c. Display

8 . Write a program to design a priority queue which is

maintained as a set of queues
(Assume a maximum of 3 queues). The elements are
inserted based upon the given
Priority. The deletion of an element is to be done
starting from the 1st queue, if it is not
Empty. If it is empty, the elements from the 2nd
queue will be deleted and so on.

9 Write a C Program using dynamic variables and

pointers, to construct a singly linked list consisting
integers in each node
The operations to be supported are:
a. The insertion operation
i. At the front of a list
ii. At the back of the list
iii. At any position in the list
b. Displaying all the nodes in the list.

10 Write a C Program using dynamic variables and

pointers, to construct a singly linked list consisting
integers in each node
The operations to be supported are:
a. The insertion operation. At the front of a list
b. Deleting a node based on searching item If the
specified node is not present in the list an error
message should be displayed. Both the options should
be demonstrated.
c. Displaying all the nodes in the list.

11 Write a C Program using dynamic variables and

pointers, to construct a singly linked list consisting
integers in each node
The operations to be supported are:
a. The insertion operation at the front/back of a list
b. Searching a node based on integer and updates the

Dept. of MCA, TOCE, Bangalore 3

 07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

information content. If the

Specified node is not present in the list an error
message should be displayed. Both
Situations should be displayed.
c. Displaying all the nodes in the list.

12 Write a C Program using dynamic variables and

pointers, to construct an ordered
(ascending) singly linked list based on the rank of the
student, where each node consists
of the following information : student id (integer),
student name (character string) and
Rank (integer) and display the list.

13 Write a C Program using dynamic variables and

pointers to construct a stack of integers using singly
linked list and to perform the following operations:
a. Push
b. Pop
c. Display
The program should print appropriate messages for
stack overflow and stack empty.

14 Write a C Program to support the following

operations on a doubly linked list where each node
consists of integers:
a. Create a doubly linked list by adding each node at
the front.
b. Insert a new node to the left of the node whose key
value is read as an input.
c. Display the contents of the list.

15 Write a C Program to support the following

operations on a doubly linked list where each
node consists of integers:
a. Create a doubly linked list by adding each node at
the front.
b. Delete the node of a given data, if it is found,
otherwise display appropriate message.
c. Display the contents of the list.

16 Write a C Program
a. To construct a binary search tree of integers.
b. To traverse the tree using all the methods i.e.,

Dept. of MCA, TOCE, Bangalore 4

 07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

inorder, preorder and postorder.

c. To display the elements in the tree
17 Write a C Programs for searching an element on a
given list of integers using the
a. Binary Search.
b. Linear search

18 . Write a C program to sort a list of N integers using

the quick sort algorithm
19 Write a C program to sort a list of N integers using
the heap sort algorithm
20 Write a C program to traverse the nodes in a graph
using Breadth First Search

Dept. of MCA, TOCE, Bangalore 5

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

1. Write a C Program to construct a stack of integers and to perform the following

Operations on it:
a. Push
b. Pop
c. Display
The program should print appropriate messages for stack overflow, stack
Underflow and stack empty.

Keywords Descriptions:
Stack: A Stack is defined as a linear data structure in which all insertion and deletion
are made at one end called Top of Stack. A stack is based on LIFO (Last in First Out)
principle. Stack is a restricted data structure because it is not possible to insert or
delete an element at the middle of stack.
Push: Push operation is to insert an item to the top of the stack
Pop: The Pop operation deletes or removes top most item from the stack.

Program:

/* Program to Implement Stack using Array*/

#include <stdio.h>
#include <conio.h>
#define asize 5
int st[asize],top=-1;
void push();
void pop();
void display();
void main()
{
int ch;
clrscr();
while(1)
{
printf(“\nStack Operation\n”);
printf("\n1-PUSH\n2-POP\n3-DISPLAY\n4-EXIT\n");
printf(“\nEnter your choice:”);
scanf("%d",&ch);
switch(ch)
{
case 1: push();
break;
case 2: pop();
break;
case 3: display();
break;

Dept. of MCA, TOCE, Bangalore 6

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

case 4: exit(0);
}
}
}

void push()
{
int item;
if(top==asize-1)
printf("\nStack is overflow\n");
else
{
printf("\nEnter item to be pushed:");
scanf("%d",&item);
top=top+1;
st[top]=item;
}
}
void pop()
{
if(top==-1)
printf("Stack Underflow");
else
printf("\nPopped item is %d",st[top--]);
return;

}
void display()
{
int i;
printf("Stack Element\n");
for(i=top;i>=0;i--)
printf("%d\n",st[i]);
}

Input-Output:
Stack Operation
1-Push
2-POP
3-Display
4-Exit
Enter your choice:1
Enter the item to be pushed: 31
Stack Operation
1-Push
2-POP

Dept. of MCA, TOCE, Bangalore 7

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

3-Display
4-Exit
Enter your choice:1
Enter the item to be pushed: 55
Stack Operation
1-Push
2-POP
3-Display
4-Exit
Enter your choice:1
Enter the item to be pushed: 45
Stack Operation
1-Push
2-POP
3-Display
4-Exit
Enter your choice:1
Enter the item to be pushed: 41
Stack Operation
1-Push
2-POP
3-Display
4-Exit
Enter your choice:1
Enter the item to be pushed: 56
Stack Operation
1-Push
2-POP
3-Display
4-Exit
Enter your choice:1
Stack is Overflow
Stack Operation
1-Push
2-POP
3-Display
4-Exit
Enter your choice:3
Stack Elements
56
41
45
55
31
Stack Operation
1-Push

Dept. of MCA, TOCE, Bangalore 8

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

2-POP
3-Display
4-Exit
Enter your choice:2
Popped item is 56
Stack Operation
1-Push
2-POP
3-Display
4-Exit
Enter your choice:2
Popped item is 41
Enter your choice: 4.

Dept. of MCA, TOCE, Bangalore 9

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

2. Write a C Program to convert and print a given valid parenthesized infix

Arithmetic expression to postfix expression. The expression consists of
Single character operands and the binary operators + (plus), - (minus), *
(Multiply) and / (divide).

Keywords Descriptions:

Infix: The expression having an operator in between two operand is known as

infix expression. Infix expr may be unparenthetic, parenthetic or fully
parenthetic
Ex: a+b*c

Postfix: The expression having an operand followed by operator is known as

postfix expression
Ex:ab+

Program:
#include <stdio.h>
#include <string.h>
#include <conio.h>
void infix_postfix(char infix[],char postfix[])
{
int top,i,j;
char s[20],symbol;
top=-1;
s[++top]="#";
j=0;
for(i=0;i<strlen(infix);i++)
{
symbol=infix[i];
while(F(s[top])>G(symbol))
{
postfix[j]=s[top--];
j++;
}
if(F(s[top])!=G(symbol))
s[++top]=symbol;
else
top--;
}
while(s[top]!='#')
{
postfix[j++]=s[top--];
}
postfix[j]='\0';

Dept. of MCA, TOCE, Bangalore 10

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

}
int F(char symbol)
{
switch(symbol)
{
case '+':
case '-': return 2;
case '*':
case '/': return 4;
case '^':
case '$': return 5;
case '(': return 0;
case '#': return -1;
default: return 8;
}
}
int G(char symbol)
{
switch(symbol)
{
case '+':
case '-': return 1;
case '*':
case '/': return 3;
case '^':
case '$': return 6;
case '(': return 9;
case ')': return 0;
default: return 7;
}
}
void main()
{
char infix[20],postfix[20];
clrscr();
printf("\nEnter a valid infix expression\n");
scanf("%s",infix);
infix_postfix(infix,postfix);
printf("\nThe postfix expression is\n");
printf("%s\n",postfix);
getch();
}

Dept. of MCA, TOCE, Bangalore 11

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

INPUT-OUTPUT
Enter a valid infix expression
((a+b)*c-(d-e))^(f+g)
The postfix expression is
Ab+c*de—fg+^

Dept. of MCA, TOCE, Bangalore 12

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

3. Write a C Program to evaluate a valid suffix/postfix expression using stack.

Assume that the suffix/postfix expression is read as a single line consisting of
non-negative single digit operands and binary arithmetic operators. The
arithmetic operators are + (add), -(subtract), * (multiply) and / (divide).

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

double op(char symbol,double op1,double op2)

{
switch(symbol)
{
case '+':return op1+op2;
case '-':return op1-op2;
case '*':return op1*op2;
case '/':return op1/op2;
case '^':return pow(op1,op2);
}
return 0;
}
void push(int item,double s[],int *top)
{
*top=*top+1;
s[*top]=item;
}
int pop(double s[],int *top)
{
double item;
item=s[*top];
*top=*top-1;
return(item);

}
isdigit(char symbol)
{
return(symbol>='0' && symbol <='9');
}
void main()
{
double op1,op2,res,s[10];
char symbol;
char postfix[10];

Dept. of MCA, TOCE, Bangalore 13

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

int i;
int top=-1;
clrscr();
printf("Enter the postfix expression\n");
scanf("%s",&postfix);
for(i=0;i<strlen(postfix);i++)
{
symbol=postfix [i];
if(isdigit(symbol))
push(symbol- '0',s,&top);
else
{
op2=pop(s,&top);
op1=pop(s,&top);
res=op(symbol,op1,op2);
push(res,s,&top);
}
}
res=pop(s,&top);
printf("The evaluated expression is %f\n",res);

INPUT-OUTPUT
Enter the postfix expression
23/
The evaluated expression is 0.666667

Dept. of MCA, TOCE, Bangalore 14

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

4. Write a C program using recursive function for the following:

a. To calculate GCD and LCM of 2 integer numbers.
b. To solve Towers of Hanoi problem.

Keywords Descriptions:
Recursion: A function, which calls itself, is known as recursion its one of the major
application of stack.
Two conditions must be satisfied by a recursive function:
1. A recursive function must always call a simple case of itself.
2. There should be terminating condition; otherwise it will go into infinite loop.

Towers of Hanoi: TOI is a complex problem which states that:

Given N disks of decreasing size stacked on one needle and two empty needles, it is
required to stack all the disks onto a second needle in decreasing order of size.
The third needle may be used for auxiliary storage this must be done using the
following rules:
- Only one disk may be moved at a time.
- A disk may be removed from any needle to any other needle.
- A larger disk may never rest upon a smaller disk.

Program:
/* Program to find GCD and LCM of two 2 integer numbers*/
#include<stdio.h>
#include<conio.h>
int gcd(int,int);
void main()
{
int n,m,lcm,x;
clrscr();
printf("Enter two numbers::");
scanf("%d %d",&n,&m);
x=gcd(n,m);
lcm=(n+m)/x;
printf("GCD=%d",x);
printf("LCM=%d",lcm);
getch();
}

int gcd(int u,int v)

{
if(u==v)
return(u);

Dept. of MCA, TOCE, Bangalore 15

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

else if(v==0)
return(u);
else
return(gcd(v,u%v));
}
INPUT-OUTPUT
Enter two numbers:: 10 20
GCD=10
LCM=20

/* Program to implement Towers of Honai*/

#include<stdio.h>
#include<conio.h>
int toi(int,char,char,char);
void main()
{
int n;
clrscr();
printf("Enter no of disk::");
scanf("%d",&n);
toi(n,'A','B','C');
getch();
}
int toi(int n,char source,char intr,char dest)
{

if(n!=0)
{
toi(n-1,source,dest,intr);
printf("\n Move %c to %c",source,dest);
toi(n-1,intr,source,dest);
return(0);
}
}
INPUT-OUTPUT
Enter no of disk::3
Move A to C
Move A to B
Move C to B
Move A to C
Move B to A
Move B to C
Move A to C

Dept. of MCA, TOCE, Bangalore 16

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

5. Write a C program using recursive function for the following:

a. To solve Towers of Hanoi problem.
b. To search an element in a list using binary search

Program:
/* Program to implement Towers of Honai*/

#include<stdio.h>
#include<conio.h>
int toi(int,char,char,char);
void main()
{
int n;
clrscr();
printf("Enter no of disk::");
scanf("%d",&n);
toi(n,'A','B','C');
getch();
}
int toi(int n,char source,char intr,char dest)
{

if(n!=0)
{
toi(n-1,source,dest,intr);
printf("\n Move %c to %c",source,dest);
toi(n-1,intr,source,dest);
return(0);
}
}
INPUT-OUTPUT
Enter no of disk::3
Move A to C
Move A to B
Move C to B
Move A to C
Move B to A
Move B to C
Move A to C

Dept. of MCA, TOCE, Bangalore 17

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

/* Program to implement Binary Search using Recursion*/

#include<stdio.h>
#include<conio.h>
int bs(int [],int,int,int);
void main()
{
int a[10],n,i,item,lb,ub,l;
clrscr();
printf("\nENTER SIZE:");
scanf("%d",&n);
printf("\nENTER ARRAY ELEMENT:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\nENTER SEARCH ELEMENT:");
scanf("%d",&item);
lb=0;
ub=n-1;
l=bs(a,item,lb,ub);
if(l!=-1)
printf("\n%d IS FOUND AT LOCATION AT %d",item,l);
else
printf("\nUNSUCCESSFUL SEARCH: %d",l);
getch();
}
int bs(int a[ ],int item,int lb,int ub)
{
int mid=0;
mid=(int)((lb+ub)/2);
if(lb>ub)
return(-1);
if(item==a[mid])
return(mid);
else if(item<a[mid])
return(bs(a,item,lb,mid-1));
else if(item>a[mid])
return(bs(a,item,mid+1,ub));
}

Dept. of MCA, TOCE, Bangalore 18

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

INPUT-OUTPUT
ENTER SIZE:4
ENTER ARRAY ELEMENT:
41
61
8
01
ENTER SEARCH ELEMENT: 16
UNSUCCESSFUL SEARCH
ENTER SEARCH ELEMENT: 61
61 IS FOUND AT LOCATION AT 2.

Dept. of MCA, TOCE, Bangalore 19

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

6. Write a C Program to simulate the working of a queue of integers using an

Array. Provide the following operations:
a. Insert
b. Delete
c. Display

Keywords Descriptions:
Queues: A Queue is an ordered collection of items in which items may be inserted at
one end known as Front end and item may be deleted from other end known as Rear
end. Queue is also known as FIFO structure because the elements which is inserted
first will be the first element to be deleted.
Two basic operations are performed on queues
Insertion adds a new item at rear end .
Deletion- deletes at the front end.

Program:
/* Program to implement Queues using Arrays*/
#include <stdio.h>
#include <conio.h>
void qinsert();
void qdelete();
void qdisplay();
#define size 10
int q[size],front=-1,rear=-1;
void main()
{
int ch;
clrscr();
while(1)
{
printf(“\nQUEUE OPERATION\n”);
printf("\n1.QINSERT\n2.QDELETE\n3.QDISPLAY\n4.QEND\n");
printf("\nEnter your choice");
scanf("%d",&ch);
switch(ch)
{
case 1: qinsert();
break;
case 2: qdelete();
break;
case 3: qdisplay();
break;
case 4: exit(0);

Dept. of MCA, TOCE, Bangalore 20

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

}
}
void qinsert()
{
int item;
if(rear==size-1)
printf("\nQueue is full");
else
{
printf("\nEnter item to be inserted");
scanf("%d",&item);
if(front==-1)
front=rear=0;
else
rear=rear+1;
q[rear]=item;
}
}
void qdelete()
{
if(front==-1)
printf("\nQueue is empty\n");
else
{
printf("\nDeleted item is %d\n",q[front]);
if(front==rear)
rear=front=-1;
else
front=front+1;
}
}
void qdisplay()
{
int i;
if(front==-1)
printf("\nQueue is empty");
else
{
printf("\nQueue elements are \n");
for(i=front;i<=rear;i++)
printf("%d\t",q[i]);

}
}

Dept. of MCA, TOCE, Bangalore 21

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

INPUT-OUTPUT
QUEUE OPERATION
1. QINSERT
2. QDELETE
3. QDISPLAY
4. QEND
Enter your choice: 2
Queue is empty
QUEUE OPERATION
1. QINSERT
2. QDELETE
3. QDISPLAY
4. QEND
Enter your choice: 1
Enter item to be inserted: 23
QUEUE OPERATION
1. QINSERT
2. QDELETE
3. QDISPLAY
4. QEND
Enter your choice: 1
Enter item to be inserted: 33
QUEUE OPERATION
1. QINSERT
2. QDELETE
3. QDISPLAY
4. QEND
Enter your choice: 1
Enter item to be inserted: 43
QUEUE OPERATION
1. QINSERT
2. QDELETE
3. QDISPLAY
4. QEND
Enter your choice: 3
Queue elements are:
43 33 23
QUEUE OPERATION
1. QINSERT
2. QDELETE
3. QDISPLAY
4. QEND
Enter your choice: 4

Dept. of MCA, TOCE, Bangalore 22

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

7. Write a C Program to simulate the working of a circular queue of integers using

an array.
Provide the following operations:
a. Insert
b. Delete
c. Display

Keywords Descriptions:
Circular Queue: Circular Queue is a linear data structure implemented using two
pointer front and rear. Here two pointers will chase each other in order to utilize the
memory effectively.

Program:
/* Program to implement Circular Queue using Array*/
#include<stdio.h>
#include<conio.h>
#define size 10
int q[size];
int front=-1,rear=-1;
void cinsert();
void cdelete();
void cdisplay();
void main()
{
int ch;
clrscr();
while(1)
{
printf("\nCircular Queue using Arrays\n");
printf("\n1.Insert\n2.Delete\n3.Display\n4.Exit\n");
printf("\nEnter your choice\n");
scanf("%d",&ch);
switch(ch)
{
case 1: cinsert();
break;
case 2: cdelete();
break;
case 3: cdisplay();
break;
case 4: exit(0);
}

Dept. of MCA, TOCE, Bangalore 23

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

}
}
void cinsert()
{
int item;
printf("Enter the item to be inserted\n");
scanf("%d",&item);
if((front==0)&&(rear==size-1))
printf("Circular queue is empty\n");
else
{
if(front==-1)
front=rear=0;
else
if((rear==size-1)&&(front!=0))
rear=0;
else
rear=rear+1;
q[rear]=item;
}
}
void cdelete()
{
if(rear==-1||front==-1)
printf("Circular queue is empty\n");
else
{
printf("Deleted element is %d\n",q[front]);
if((front==size-1)&&(rear!=0))
front=0;
else
if(rear==front)
front=rear=-1;
else
front=front+1;
}
}
void cdisplay()
{
int i;
if(front==-1)
printf("\nQueue is empty");
else
{
printf("\nCircular Queue elements are \n");
for(i=front;i<=rear;i++)

Dept. of MCA, TOCE, Bangalore 24

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

printf("%d\t",q[i]);

}
}

INPUT-OUTPUT
Circular Queue using Arrays
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice: 2
Queue is empty
Circular Queue using Arrays
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice: 1
Enter item to be inserted: 23
Circular Queue using Arrays
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice: 1
Enter item to be inserted: 33
Circular Queue using Arrays
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice: 1
Enter item to be inserted: 43
Circular Queue using Arrays
1.Insert
2.Delete
3.Display
4.Exit
Enter your choice: 3
Circular Queue elements are:
43 33 23
Circular Queue using Arrays
1.Insert
2.Delete

Dept. of MCA, TOCE, Bangalore 25

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

3.Display
4.Exit
Enter your choice: 4

Dept. of MCA, TOCE, Bangalore 26

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

8. Write a program to design a priority queue which is maintained as a set of

queues(assume a maximum of 3 queues). The elements are inserted based upon
the given priority. The deletion of an element is to be done starting from the 1st
queue, if it is not empty. If it is empty, the elements from the 2nd queue will be
deleted and so on.

Keywords Descriptions:
Priority Queue: A Priority queue is defined as a linear data structure in which each
element is given some priority at the time of insertion but the deletion operation
depends upon priority. Priority queue does not follow the basic rule of linear queue i.e,
the element s can be inserted or removed from any position depending on some
priority.

Program:
/* Program to implement Priority Queue */
#include <stdio.h>
#include <conio.h>
#define max 5
void pqinsert(int qno,int q[],int *front,int *rear,int item)
{
if(*rear==max-1)
{
printf("\nQueue is full:",qno);
return;
}
else if(*front==-1)
*front=*rear=0;
else
*rear=*rear+1;
q[*rear]=item;
}
int pqdelete(int q[],int *front,int *rear)
{
int item;
if(*front==-1)
return 0;
else
printf("\nDeleted item is %d\n",q[*front]);
if(*front==*rear)
*front=*rear=-1;
else
*front=*front+1;
return 1;
}

Dept. of MCA, TOCE, Bangalore 27

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

void pqdisplay(int qno,int q[],int *front,int *rear)

{ int i;
if(*front==-1)
printf("\n%d queue is empty\n",qno);
else
{
printf("\nElements of %d queue are\n",qno);
for(i=*front;i<=*rear;i++)
printf("%d\t",q[i]);
}
}
void main()
{
int q1[max], q2[max], q3[max];
int f1=-1,r1=-1,f2=-1,r2=-1,f3=-1,r3=-1;
int item,priority,flag,ch;
clrscr();
while(1)
{
printf(“\nPriority Queue Operation\n”);
printf("\n1.Insert\n2.Delete\n3.Display\n4.End\n");
printf("\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\nEnter the item and priority no\n");
scanf("%d%d",&item,&priority);
if(priority==1)
pqinsert(1,q1,&f1,&r1,item);
if(priority==2)
pqinsert(2,q2,&f2,&r2,item);
if(priority==3)
pqinsert(3,q3,&f3,&r3,item);
break;
case 2: flag=pqdelete(q1,&f1,&r1);
if(flag==1)
{
printf("\nDelete from the 1st priority\n");
break;
}
else
printf("\nFirst Priority Queue is Empty\n");
flag=pqdelete(q2,&f2,&r2);
if(flag==1)
{

Dept. of MCA, TOCE, Bangalore 28

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

printf("\nDelete from the 2nd

priority\n");
break;
}
else
printf("\nSecond Priority Queue is Empty\n");
flag=pqdelete(q3,&f3,&r3);
if(flag==1)
{
printf("\nDelete from the 3rd priority\n");
break;
}
else
printf("\nThird Priority Queue is Empty\n");
break;
case 3: printf("\nQueue Elements are\n");
pqdisplay(1,q1,&f1,&r1);
pqdisplay(2,q2,&f2,&r2);
pqdisplay(3,q3,&f3,&r3);
break;
case 4: exit(0);
}
}
}

INPUT-OUTPUT
Priority Queue Operation
1.Insert
2.Delete
3.Display
4.End
Enter your choice:1
Enter the item and priority no:
20
1
Priority Queue Operation
1.Insert
2.Delete
3.Display
4.End
Enter your choice:1
Enter the item and priority no:
30
2
Priority Queue Operation
1.Insert

Dept. of MCA, TOCE, Bangalore 29

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

2.Delete
3.Display
4.End
Enter your choice:3
Queue Elements are
Elements of 1 queue are 20
Elements of 2 queue are 30
Priority Queue Operation
1.Insert
2.Delete
3.Display
4.End
Enter your choice:2
Delete from the 1st priority
Deleted item is 20
Priority Queue Operation
1.Insert
2.Delete
3.Display
4.End
Enter your choice:2
First Priority Queue is Empty
Priority Queue Operation
1.Insert
2.Delete
3.Display
4.End
Enter your choice:4

Dept. of MCA, TOCE, Bangalore 30

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

9. Write a C Program using dynamic variables and pointers, to construct a singly

linked list consisting integers in each node The operations to be supported are:

a. The insertion operation

i. At the front of a list
ii. At the back of the list
iii. At any position in the list
b. Displaying all the nodes in the list.

Key Descriptions:
Linked list is a linear data structure which can store and manipulate variable number
of elements.
Singly linked list is a linear collection of nodes maintained by using only one pointer.
Each and every node in a singly linked list is divided into two parts
Data/info- it can store one or more than one data.
Link/pointer-which contains address of next node.
Each and every linked list starts with a pointer known as head or start. The last node
link part contains NULL indicates the end of the linked list.

Program:

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
void insert_front();
void display();
void insert_end();
void insert_middle();
struct list
{
int data;
struct list *next;
};
typedef struct list node;

node *head=NULL;
int count=0;
node *getnode();
void main()
{
int ch;
clrscr();
while(1)
{

Dept. of MCA, TOCE, Bangalore 31

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

printf(“\nInsertion operation on Singly Linked\n”);

printf("\n 1.Insert_front \n
2.Insert_end\n3.Insert_mid\n4:display \n 5. End\n");
printf("\nEnter your choice:");
scanf("%d",&ch);
switch(ch)
{
case 1: insert_front();
break;
case 2: insert_end();
break;
case 3: insert_middle();
break;
case 4: display();
break;
case 5: exit(0);
}
}
}
/*Inserts the item at the beginning of the list*/
void insert_front()
{
node *new1;
new1=getnode();
if(head==NULL)
{
head=new1;
}
else
{
new1->next=head;
head=new1;
}
}
/* Insert the item at the end of the list*/
void insert_end()
{
node *new1,*temp;
new1->next=NULL;
new1=getnode();
if(head==NULL)
{
head=new1;
}
else
{

Dept. of MCA, TOCE, Bangalore 32

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

temp=head;
while(temp->next!=NULL)

temp=temp->next;
temp->next=new1;

}
}
node *getnode()
{
node *x;
count++;
x=(node *)malloc(sizeof(node));
x->next=NULL;
printf("\nEnter the data:");
scanf("%d",&x->data);
return(x);
}
void display()
{
node *ptr;
ptr=head;
while(ptr!=NULL)
{
printf("\n%d\t",ptr->data);
ptr=ptr->next;
}
}
/*Inserts the element at any position of the list based on node position*/
void insert_middle()
{
node *new1,*loc;
int n,i;
printf("\nenter the new node pos:");
scanf("%d",&n);
if(n>count)
printf("Illegal node position\n");
else
{

new1=getnode();
loc=head;
for(i=2;i<=n;i++)
loc=loc->next;
if(head==NULL)
{

Dept. of MCA, TOCE, Bangalore 33

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

head=new1;
new1->next=NULL;
}
else if((head==loc) && (loc->next!=NULL))
{
new1->next=head;
head=new1;
}
if((loc!=head)&&(loc->next==NULL))
{
loc->next=new1;
new1->next=NULL;
}
else
{
new1->next=loc->next;
loc->next=new1;
}
}
}
INPUT-OUTPUT
Insertion operation on Singly Linked
1.Insert_front
2.Insert_end
3.Insert_mid
4: Display
5. End
Enter your choice:1
Enter the data:23
Insertion operation on Singly Linked
1.Insert_front
2.Insert_end
3.Insert_mid
4: Display
5. End
Enter your choice:1
Enter the data:45
Insertion operation on Singly Linked
1.Insert_front
2.Insert_end
3.Insert_mid
4: Display
5. End
Enter your choice:2
Enter the data:56
Insertion operation on Singly Linked

Dept. of MCA, TOCE, Bangalore 34

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

1.Insert_front
2.Insert_end
3.Insert_mid
4: Display
5. End
Enter your choice:3
Enter the new node pos:2
Enter data:66
Insertion operation on Singly Linked
1.Insert_front
2.Insert_end
3.Insert_mid
4: Display
5. End
Enter your choice:4
23 45 66 56
Insertion operation on Singly Linked
1.Insert_front
2.Insert_end
3.Insert_mid
4: Display
5. End
Enter your choice:5

Dept. of MCA, TOCE, Bangalore 35

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

10. Write a C Program using dynamic variables and pointers, to construct a singly
linked list consisting integers in each node The operations to be supported are:
a. The insertion operation. At the front of a list
b. Deleting a node based on searching item If the specified node is not present
in the list an error message should be displayed. Both the options should be
demonstrated.
c. Displaying all the nodes in the list.

Program:
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
void insert_front();
void delete_any();
void display();
struct llist
{
int data;
struct llist *next;
};
typedef struct llist node;
node *getnode();
node *head=NULL;
void main()
{
int ch;
clrscr();
while(1)
{
printf(“\nDeletion Operation on Singly linked list\n”);
printf("\n1.Insert front \n 2.Delete end \n 3.Display \n 4.End\n");
printf("\nEnter ur choice::");
scanf("%d",&ch);
switch(ch)
{
case 1:insert_front();
break;
case 2:delete_any();
break;
case 3:display();
break;
case 4:exit(0);

Dept. of MCA, TOCE, Bangalore 36

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

}
}
}
void insert_front()
{
node *new1;
new1=getnode();
if(head==NULL)
head=new1;
else
{
new1->next=head;
head=new1;
}
}
node *getnode()
{
node *x;
x=(node *)malloc(sizeof(node));
x->next=NULL;
printf("\nEnter data\n");
scanf("%d",&x->data);
return x;
}
void delete_any()
{
node *loc,*locp;
int i,j,n;
loc=head;
locp=NULL;
if((loc==NULL)&&(locp==NULL))
printf("List is empty\n");
else
{
printf("enter the node number to be deleted\n");
scanf("%d",&n);

for(i=2;i<=n;i++)
{
locp=loc;
loc=loc->next;
}
if((loc==head)&&(loc->next==NULL))
{
head=NULL;
free(loc);

Dept. of MCA, TOCE, Bangalore 37

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

}
else
{
if((loc==head)&&(loc->next))
{
head=head->next;
free(loc);
}
else
if((loc!=NULL)&&(loc->next==NULL))
{
locp->next=NULL;
free(loc);

}
else
{
locp->next=loc->next;
free(loc);
}
}

if (loc == NULL)
printf("\n item not present in List.");
}

}
void display()
{
node *ptr;
ptr=head;
printf("\nList of elements \n");
while(ptr != NULL)
{
printf("%d\n",ptr->data);
ptr=ptr->next;
}
}

Dept. of MCA, TOCE, Bangalore 38

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

INPUT-OUPUT
Deletion Operation on Singly linked list
1.Insert front
2.Delete end
3.Display
4.End
Enter your choice:2
List is empty
Deletion Operation on Singly linked list
1.Insert front
2.Delete end
3.Display
4.End
Enter your choice:1
Enter Data:12
Deletion Operation on Singly linked list
1.Insert front
2.Delete end
3.Display
4.End
Enter your choice:1
Enter Data:23
Deletion Operation on Singly linked list
1.Insert front
2.Delete end
3.Display
4.End
Enter your choice:2
enter the node number to be deleted: 6
item not present in List
Deletion Operation on Singly linked list
1.Insert front
2.Delete end
3.Display
4.End
Enter your choice:4

Dept. of MCA, TOCE, Bangalore 39

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

11. Write a C Program using dynamic variables and pointers, to construct a singly
Linked list consisting integers in each node
The operations to be supported are:
a. The insertion operation at the front/back of a list
b. Searching a node based on integer and updates the information content. If
The specified node is not present in the list an error message should be
Displayed. Both situations should be displayed.
c. Displaying all the nodes in the list.

Program:
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
void insert_front();
void display();
void search();
struct llist
{
int sid;
char sname[10];
int sem;
struct llist *next;
};
typedef struct llist node;
node *getnode();
node *head=NULL;
int count=0;
node *new1;
void main()
{
int ch;
clrscr();
while(1)
{
printf("\n1.Insert Front\n2.Display\n3.Search\n4.End\n");
printf("\nEnter ur choice::");
scanf("%d",&ch);
switch(ch)
{
case 1:insert_front();
break;
case 2:display();
break;

Dept. of MCA, TOCE, Bangalore 40

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

case 3:search();
break;
case 4:exit(0);
}
}
}
void insert_front()
{
node *new1;
new1=getnode();
if(head==NULL)
head=new1;
else
{
new1->next=head;
head=new1;
}
}
node *getnode()
{
node *x;
count++;
x=(node *)malloc(sizeof(node));
x->next=NULL;
printf("\nEnter student id::");
scanf("%d",&x->sid);
printf("\nEnter student name::");
scanf("%s",x->sname);
printf("\nEnter semester::");
scanf("%d",&x->sem);
return(x);
}

void search()
{
int item,y;
node *locp=NULL,*loc;
printf("Enter student ID to be seached::");
scanf("%d",&item);
if(head==NULL)
printf("\n ID not present");
else
{
loc=head;
while(loc->sid!=item && loc!=NULL)
{

Dept. of MCA, TOCE, Bangalore 41

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

locp=loc;
loc=loc->next;
}
if(loc==NULL)
printf("\nElement not found");
else
{
printf("\nSTUDENT DETAILD \n");
printf("\nSID\tNAME\tSEM\n");
printf("\n%d\t%s\t%d\n",loc->sid,loc->sname,loc->sem);
printf("\nIf U want updationenter 1 otherwise 0:") ;
scanf("%d",&y);
if(y ==1)
{
printf("\n enter new name:");
scanf("%s",loc->sname);
printf("\n enter new sem:");
scanf("%d",&loc->sem);

}
}

}
void display()
{
node *ptr;
ptr=head;
if(head==NULL)
printf("\nList is empty");
else
{
printf("\nSTUDENT DETAILS \n");
printf("\nSID\tNAME\tSEM\n");
while(ptr!= NULL)
{
printf("\n%d\t%s\t%d\n",ptr->sid,ptr->sname,ptr->sem);
ptr=ptr->next;
}
}
}
INPUT-OUPUT
1.Insert Front
2.Display

Dept. of MCA, TOCE, Bangalore 42

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

3.Search
4.End
Enter ur choice::1
Enter student id:1
Enter student name:: Ashwini.J
Enter semester::4
1.Insert Front
2.Display
3.Search
4.End
Enter ur choice::2
STUDENT DETAILS
SID NAME SEM
1 Ashwini.J 4
1.Insert Front
2.Display
3.Search
4.End
Enter ur choice::3
Enter the student-id to be searched:2
ID not present
1.Insert Front
2.Display
3.Search
4.End
Enter ur choice::3
Enter the student-id to be searched:1
If U want update enter 1 otherwise 0
1
Enter new student name:Ashwini.J
Enter new semester:2
1.Insert Front
2.Display
3.Search
4.End
Enter ur choice::2
STUDENT DETAILS
SID NAME SEM
1 Ashwini.J 4
1.Insert Front
2.Display
3.Search
4.End
Enter ur choice::4

Dept. of MCA, TOCE, Bangalore 43

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

12. Write a C Program using dynamic variables and pointers, to construct an

ordered (ascending) singly linked list based on the rank of the student, where
each node consists of the following information : student id (integer), student
name (character string) and rank (integer) and display the list.

Program:
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#include <string.h>
struct LinkedList
{
int stu_id;
char *stu_name;
int stu_rank;
struct LinkedList *next;
};
typedef struct LinkedList node;

node * insert_order(node *,int,char *,int);

void display(node *);

void main()
{
int choice,s_id,rank;
char *name;
node *head=NULL;
clrscr();
while(1)
{
printf("\n1.Insert Order\n2.Display\n3.Exit\n");
printf("\nEnter ur choice::");
scanf("%d",&choice);
switch(choice)
{
case 1: printf("\nEnter Stu_Id, Name & Rank : ");
scanf("%d%s%d",&s_id,name,&rank);
head=insert_order(head,s_id,name,rank);
break;
case 2: display(head);
break;
default:exit(0);
}
}

Dept. of MCA, TOCE, Bangalore 44

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

}
node * insert_order(node * head,int s_id,char *name,int rank)
{
node *new1,*loc;
new1=(node *)malloc(sizeof(node));
new1->stu_id=s_id;
strcpy(new1->stu_name, name);
new1->stu_rank=rank;
new1->next=NULL;
if(head == NULL)
return(new1);
else if(new1->stu_rank < head->stu_rank)
{
new1->next=head;
head=new1;
return(head);
}
else
{
loc=head;
while((loc->next != NULL) &&
(loc->next->stu_rank <= new1->stu_rank))
loc=loc->next;
new1->next=loc->next;
loc->next=new1;
return(head);
}
}
void display(node *head)
{
node *loc=head;
printf("\nSTUDENT DETAILD:- \n");
printf("\nS_ID\tS_NAME\tS_RANK\n");
if(head == NULL)
printf("\n List is empty.");
while(loc != NULL)
{
printf("\n%d\t%s\t%d\n",loc->stu_id,loc->stu_name,loc->stu_rank);
loc=loc->next;
}
}

Dept. of MCA, TOCE, Bangalore 45

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

INPUT-OUTPUT
1.Insert order
2.Display
3.Exit
Enter ur choice::2
List is empty
1.Insert order
2.Display
3.Exit
Enter ur choice::1
Enter Stu_Id, Name & Rank :
1
Ash
4
1.Insert order
2.Display
3.Exit
Enter ur choice::1
Enter Stu_Id, Name & Rank :
3
Lee
1
1.Insert order
2.Display
3.Exit
Enter ur choice::2
STUDENT DETAILS
SID SNAME SRANK
3 Lee 1
1 Ash 4
1.Insert order
2.Display
3.Exit
Enter ur choice::3

Dept. of MCA, TOCE, Bangalore 46

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

13. Write a C Program using dynamic variables and pointers to construct a stack of
Integers using singly linked list and to perform the following operations:
a. Push
b. Pop
c. Display
The program should print appropriate messages for stack overflow and stack empty.

Keywords Descriptions:
Linked list implementation of stack: Linked list can be used to perform stack
operations i.e., adding a new node at the front of the linked list indicates push
operation, deleting the node at the front indicates pop operation.
The main advantage of implementation of stack using linked list is can store variable
no. of elements of stack.

Program:
/* Program to implement Stack using Linked List*/
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
void push();
void pop();
void display();
struct list
{
int data;
struct list *next;
};
typedef struct list node;
node *top=NULL;
void main()
{
int ch;
clrscr();
while(1)
{
printf("Stack operation using singly linked list\n");
printf("\n1.Push \n2.Pop \n3.Display \n4.Exit\n");
printf("enter your choice\n");
scanf("%d",&ch);
switch(ch)
{
case 1: push();
break;

Dept. of MCA, TOCE, Bangalore 47

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

case 2: pop();
break;
case 3: display();
break;
case 4: exit(0);
}
}
}
void push()
{
node *new1;
new1=(node *)malloc(sizeof(node));
printf("enter the element:\n");
scanf("%d",&new1->data);
new1->next=NULL;
if(top==NULL)
top=new1;
else
{
new1->next=top;
top=new1;
}
}
void pop()
{
node *ptr;
if(top==NULL)
printf("STACK IS EMPTY\n");
else
{
ptr=top;
top=top->next;
free(ptr);
}
}
void display()
{
node *ptr;
ptr=top;
printf("Stack Elements Are:\n");
if(ptr==NULL)
printf("STACK IS EMPTY\n");
else
{
while(ptr!=NULL)
{

Dept. of MCA, TOCE, Bangalore 48

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

printf("%d\n",ptr->data);
ptr=ptr->next;
}
}
}

INPUT-OUPUT
Stack operation using singly linked list
1.Push
2.Pop
3.Display
4.Exit
enter your choice:1
enter the element:23
Stack operation using singly linked list
1.Push
2.Pop
3.Display
4.Exit
enter your choice:1
enter the element:34
Stack operation using singly linked list
1.Push
2.Pop
3.Display
4.Exit
enter your choice:3
Stack Elements Are:
34
23
Stack operation using singly linked list
1.Push
2.Pop
3.Display
4.Exit
enter your choice:2
Stack operation using singly linked list
1.Push
2.Pop
3.Display
4.Exit
enter your choice:2
Stack operation using singly linked list
1.Push

Dept. of MCA, TOCE, Bangalore 49

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

2.Pop
3.Display
4.Exit
enter your choice:2
STACK IS EMPTY

Dept. of MCA, TOCE, Bangalore 50

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

14. Write a C Program to support the following operations on a doubly linked list
where each node consists of integers:
a. Create a doubly linked list by adding each node at the front.
b. Insert a new node to the left of the node whose key value is read as an
input.
c. Display the contents of the list.

Keyword Descriptions:
Doubly linked list:Doubly linked list is a linear collection of one or more nodes
maintained with two pointers. Each and every node of doubly linked list is divided
into three parts
Info- information or data part of node
Left/llink-it contains the address of the previous node
Right/rlink-it contains the address of the next node

The advantage of doubly linked list is traversal can be done in both direction of the list
i.e., from the beginning to end or end to beginning.

Program:
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include <string.h>

typedef struct Node

{
int data;
struct Node *pLeft;
struct Node *pRight;
}NODE;

NODE * insert_front(NODE * head,int n)

{
NODE *new1;
new1=(NODE *)malloc(sizeof(NODE));
new1->data = n;
new1->pLeft = NULL;
new1->pRight = NULL;
if(head == NULL)
head = new1;
else
{

Dept. of MCA, TOCE, Bangalore 51

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

head->pLeft = new1;
new1->pRight = head;
head = new1;
}
return(head);
}
NODE* search(NODE *head,int n)
{
NODE *ptr = head;
while(ptr)
{
if(ptr->data == n)
return ptr;
ptr = ptr->pRight;
}
return NULL;
}

NODE * insert_middle(NODE *head,int leftOf, int n)

{
NODE *loc = search(head,leftOf);
NODE *prev,*new1;
if(!loc)
{
printf("\nItem Can't be Inserted...\n");
return head;
}
prev = head;
if(prev == loc)
{
head = insert_front(head,n);
return head;
}
prev = loc->pLeft;
new1=(NODE *)malloc(sizeof(NODE));
new1->data = n;
new1->pLeft = prev;
new1->pRight = prev->pRight;
prev->pRight = new1;
return(head);
}
void Display(NODE *head)
{
NODE *ptr = head;
while(ptr)
{

Dept. of MCA, TOCE, Bangalore 52

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

printf("%d\t",ptr->data);
ptr = ptr->pRight;
}
}
int main()
{
NODE *head = NULL;
int choice,n,key;
clrscr();
while(1)
{
printf("\n1.Insert Front\n2.Insert Before\n3.Display\n4.Exit\n");
printf("\nEnter ur choice::");
scanf("%d",&choice);

switch(choice)
{
case 1:
printf("\nEnter Data to be inserted : ");
scanf("%d",&n);
head=insert_front(head,n);
break;
case 2:
printf("\nEnter Key node and Data : ");
scanf("%d%d",&key,&n);
head=insert_middle(head,key,n);
break;

case 3:
Display(head);
break;
default:
return 0;;
}
}
}

Dept. of MCA, TOCE, Bangalore 53

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

INPUT-OUTPUT
1.Insert Front
2.Insert Before
3.Display
4.Exit
Enter ur choice::1
Enter Data to be inserted:23
1.Insert Front
2.Insert Before
3.Display
4.Exit
Enter ur choice::1
Enter Data to be inserted:45
1.Insert Front
2.Insert Before
3.Display
4.Exit
Enter ur choice::3
45 23
1.Insert Front
2.Insert Before
3.Display
4.Exit
Enter ur choice::2
Enter Key node and Data
23
30
1.Insert Front
2.Insert Before
3.Display
4.Exit
Enter ur choice::3
45 30 23

Dept. of MCA, TOCE, Bangalore 54

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

15. Write a C Program to support the following operations on a doubly linked list
where each node consists of integers:
a. Create a doubly linked list by adding each node at the front.
b. Delete the node of a given data, if it is found, otherwise display appropriate
message.
c. Display the contents of the list.

Program:
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include <string.h>

typedef struct Node

{
int data;
struct Node *pLeft;
struct Node *pRight;
}NODE;

NODE * insert_front(NODE * head,int n)

{
NODE *new1;
new1=(NODE *)malloc(sizeof(NODE));
new1->data = n;
new1->pLeft = NULL;
new1->pRight = NULL;
if(head == NULL)
head = new1;
else
{
head->pLeft = new1;
new1->pRight = head;
head = new1;
}
return(head);
}
NODE* search(NODE *head,int n)
{
NODE *ptr = head;
while(ptr)
{

Dept. of MCA, TOCE, Bangalore 55

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

if(ptr->data == n)
return ptr;
ptr = ptr->pRight;
}
return NULL;
}
NODE * del(NODE *head, int n)
{
NODE *loc = search(head,n);
NODE *prev,*nxt,*temp;
if(!loc)
{
printf("Item to be deleted is not found..");
return head;
}
if(loc == head)
{
temp = loc->pRight;
temp->pLeft = NULL;
return temp;
}
prev = loc->pLeft;
nxt = loc->pRight;
prev->pRight = loc->pRight;
nxt->pLeft = prev;
return head;
}

void Display(NODE *head)

{
NODE *ptr = head;
while(ptr)
{
printf("%d\t",ptr->data);
ptr = ptr->pRight;
}
}
int main()
{
NODE *head = NULL;
int choice,n,key;
clrscr();
while(1)
{
printf("\n1.Insert Front\n2.Delete\n3.Display\n4.Exit\n");
printf("\nEnter ur choice::");

Dept. of MCA, TOCE, Bangalore 56

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

scanf("%d",&choice);

switch(choice)
{
case 1:
printf("\nEnter Data to be inserted : ");
scanf("%d",&n);
head=insert_front(head,n);
break;
case 2: printf("\nEnter Node to be Deleted : ");
scanf("%d", &key);
head=del(head,key);
break;
case 3:
Display(head);
break;
default:
return 0;;
}
}
}

INPUT-OUTPUT
1.Insert Front
2.Delete
3.Display
4.Exit
Enter ur choice::1
Enter Data to be inserted:23
1.Insert Front
2. Delete
3.Display
4.Exit
Enter ur choice::1
Enter Data to be inserted:45
1.Insert Front
2. Delete
3.Display
4.Exit
Enter ur choice::3
45 23
1.Insert Front
2. Delete
3.Display
4.Exit
Enter ur choice::2

Dept. of MCA, TOCE, Bangalore 57

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

Enter Node to be Deleted:3

Item to be deleted is not found..
1.Insert Front
2. Delete
3.Display
4.Exit
Enter ur choice::2
Enter Node to be Deleted:23
1.Insert Front
2. Delete
3.Display
4.Exit
Enter ur choice::3
45
1.Insert Front
2. Delete
3.Display
4.Exit
Enter ur choice::4

Dept. of MCA, TOCE, Bangalore 58

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

16. Write a C Program

a. To construct a binary search tree of integers.
b. To traverse the tree using all the methods i.e., in order, preorder and
Post order.
c. To display the elements in the tree.

Keyword Descriptions:
Binary Search Tree: Binary search tree method is used to store binary tree in the
memory. It consists of anode called root together with two binary trees left sub tree
and right tree of the root.
Left sub tree should be less than or equal to the root.
Right sub tree should be greater than or equal to the root.
There are three main ways of order of traversing a binary search tree.
1. Preorder Traversal:
a. Process the root
b. Traverse the right sub tree.
c. Traverse the left sub tree.
2. Inorder Traversal:
a. Traverse the right sub tree.
b. Process the root
c. Traverse the left sub tree.
3. Postorder Traversal:
a. Traverse the right sub tree.
b. Traverse the left sub tree.
c. Process the root

#include <stdio.h>
#include <conio.h>
int sum=0,count=0;

struct llist
{
int info;
struct llist *left,*right;
};
typedef struct llist node;
node *root=NULL;
void create(int item)
{
node *temp,*currptr,*ptr;
temp=(node *)malloc(sizeof(node));
temp->info=item;
temp->left=temp->right=NULL;

Dept. of MCA, TOCE, Bangalore 59

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

if(root==NULL)
root=temp;
else
{
currptr=root;
while(currptr!=NULL)
{
ptr=currptr;
if(item>=currptr->info)
currptr=currptr->right;
else
currptr=currptr->left;
}
if(ptr->info<=item)
ptr->right=temp;
else
ptr->left=temp;
}
}
void preorder(node *ptr)
{
if(ptr!=NULL)
{
printf("%d\t",ptr->info);
sum=sum+ptr->info;
preorder(ptr->left);
preorder(ptr->right);
}
}
void inorder(node *ptr)
{
if(ptr!=NULL)
{
inorder(ptr->left);
printf("%d\t",ptr->info);
inorder(ptr->right);
}
}
void postorder(node *ptr)
{
if(ptr!=NULL)
{
count++;
postorder(ptr->left);
postorder(ptr->right);
printf("%d\t",ptr->info);

Dept. of MCA, TOCE, Bangalore 60

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

}
}
void main()
{
int ele,i,n;
clrscr();
printf("\nEnter no. of node::");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\nEnter data for the node\n");
scanf("%d",&ele);
create(ele);
}
printf("\nInorder o/p\n");
inorder(root);
printf("\nPreorder o/p\n");
preorder(root);
printf("\nPostorder o/p\n");
postorder(root);
printf("\nSum=%d",sum);
printf("\nCount=%d",count);getch();}

INPUT-OUTPUT

Enter no. of node:3

Enter data for the node:
20
10
30
Inorder o/p
10 20 30
Preorder o/p
10 30 20
Postorder o/p
20 10 30

Dept. of MCA, TOCE, Bangalore 61

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

17. Write a C Programs for searching an element on a given list of integers

using
a. Binary Search.
b. Linear search

Keyword Descriptions.

Linear Search:
This is the simplest search technique. In this method , the array is searches first
required element from the first element onwards either the list exhausted or the
required element is found.
Binary Search:
Binary search is the fastest searching algorithm.
To implement binary search method, the elements must be in sorted order.
This method is implemented as given below:
- The key is compared with item in the middle position of the array.
- If the key matches with item, return it and stop.
- If the key is less than mid position item, then the item to be found must be in first
half of the array otherwise it must be in the second half of the array.
- Repeat the procedure for lower or upper half of array until the element is found.

Program:
/* Linear Search */
#include <stdio.h>
#include <conio.h>
void main()
{
int a[10],i,n,item;
clrscr();
printf("\nEnter the size of the array\n");
scanf("%d",&n);
printf("\nEnter arrary elements one by one\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\nEnter searching element\n");
scanf("%d",&item);
for(i=0;i<n;i++)
if(item==a[i])
{
printf("\nElement %d is found at %d loc",item,i+1);
goto end;
}
printf("\nUnscuccessful Search\n");
end:

Dept. of MCA, TOCE, Bangalore 62

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

getch();
}
Program
/* Binary Search */
#include <stdio.h>
#include <conio.h>
void main()
{
int a[5],i,n,item,ub,lb,mid;
clrscr();
printf("\nEnter the size\n");
scanf("%d",&n);
printf("\nEnter arrary elements\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\nEnter the item to be searched ");
scanf("%d",&item);
lb=0;
ub=n-1;
while(lb<=ub)
{
mid=(lb+ub)/2;
if(item==a[mid])
{
found=1;
loc=mid;
break;
}
if(item<a[mid])
ub=mid-1;
else
lb=mid+1;
}
if(found)
printf("%d found at %d loc\n",item,i+1);
else
printf("\nUnsuccessful search");
getch();
}

Dept. of MCA, TOCE, Bangalore 63

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

INPUT-OUTPUT
Enter the size
4
Enter array elements
23
1
33
12

Enter the item to be searched

33
33 found at 3 loc
Enter the item to be searched
19
Unsuccessful search

Dept. of MCA, TOCE, Bangalore 64

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

18. Write a C program to sort a list of N integers using the quick sort algorithm.
Key Descriptions.

QUICK SORT:
The most powerful sorting algorithm is quick sort. It uses the policy of divide and
conquer rule. It is also known as Partition Exchange Sort.

Program
/*Declaration of preprocessor directives */
#include<stdio.h>
#include<conio.h>
/* Global declaration */
int k[100];

/*Function for the quick sort */

int partion(int low,int high)
{
int i,j,p,temp,flag;
p=k[low];
i=low+1;
j=high;
flag=1;
while(flag)
{
while(p>k[i])
{
i++;
}
while(p<k[j])
{
j--;
}
if(i<j)
{
temp=k[i];
k[i]=k[j];
k[j]=temp;
}
else
{
flag=0;
}
}

Dept. of MCA, TOCE, Bangalore 65

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

temp=k[low];
k[low]=k[j];
k[j]=temp;
return j;
}

/* Function for the quicksort */

void qsort(int low, int high)
{
int pos;
if(low<high)
{
pos=partion(low,high);
qsort(low,pos-1);
qsort(pos+1,high);
}
}

/* Main function */
void main()
{
int n,i;
clrscr();
printf("\n------------------------------------------------------\n");
printf("\nPROGRAM FOR SORTING THE LIST USING QUICK SORT \n");
printf("\n-------------------------------------------------------\n");
printf("Enter the limit \n");
scanf("%d",&n);
printf("\nEnter the elements\n");
for(i=0;i<n;i++)
{
scanf("%d",&k[i]);
}
qsort(0,n-1);
printf("\nThe sorted list is :\n");
for(i=0;i<n;i++)
{
printf("%d\n",k[i]);
}
getch();
}

Dept. of MCA, TOCE, Bangalore 66

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

INPUT-OUTPUT
-----------------------------------------------------------------------------
PROGRAM FOR SORTING THE LIST USING QUICK SORT
-----------------------------------------------------------------------------
Enter the limit
5
Enter the elements
12
4
-9
18
23
The sorted list is:
-9
4
12
18
23

Dept. of MCA, TOCE, Bangalore 67

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

19. Write a C program to sort a list of N integers using the heap sort algorithm.
Key Descriptions.

HEAP SORT:
To implement heap sort sequential representation is used.
The Heap sort is implemented in two phases:
Phase 1(Growing Phase):
In this phase entries are arranged in the list so that they satisfy the requirements of
heap.
Phase 2(Shrinking Phase):
Repeatedly, the top of the heap is removed and is adjusted so that the other entries
made to take its place.

#include<stdio.h>
#include<conio.h>
void adjust(int [],int);
void heap(int [],int);
void heapsort(int [],int);
void main()
{
int a[20],n,t,i;
clrscr();
printf("\nEnter size of array::");
scanf("%d",&n);
printf("\nEnter array element\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
heapsort(a,n);
printf("\nSorted Array\n");
for(i=0;i<n;i++)
printf("%d\n",a[i]);
getch();
}
void heap(int a[],int n)
{
int i,j,k,item;
for(k=1;k<n;k++)
{
item=a[k];
i=k;
j=(i-1)/2;
while(i>0 && item>a[j])
{
a[i]=a[j];

Dept. of MCA, TOCE, Bangalore 68

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

i=j;
j=(i-1)/2;
}
a[i]=item;
}
}
void adjust(int a[],int n)
{
int i,j,item;
j=0;
item=a[j];
i=2*j+1;
while(i<=n-1)
{
if(i+1 <= n-1)
if(a[i]<a[i+1])
i++;
if(item<a[i])
{
a[j]=a[i];
j=i;
i=2*j+1;
}
else
break;
}
a[j]=item;
}
void heapsort(int a[],int n)
{
int i,t;
heap(a,n);
for(i=n-1;i>0;i--)
{
t=a[0];
a[0]=a[i];
a[i]=t;
adjust(a,i);
}
}

Dept. of MCA, TOCE, Bangalore 69

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

INPUT-OUTPUT

Enter the size of array:

5
Enter the array elements
10
4
91
81
23
The sorted list is:
4
10
23
81
91

Dept. of MCA, TOCE, Bangalore 70

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

20. Write a C program to traverse the nodes in a graph using Breadth First Search.
Key Descriptions

BREADTH FIRST SEARCH:

In this we start with given vertex V and visit all the nodes adjacent to V from left to
right. Data structures queue is used to keep track of all the adjacent nodes. The first
node visited is the first node whose successors are visited.
#include <stdio.h>
#include <conio.h>
char q[10];
int front=0,rear=-1;
char delet();
void insert(char x);
void main()
{
int a[10][10],m,n;
int i,j,state[10];
char g[10],x;
clrscr();
printf("\nEnter the no. of nodes of graph:");
scanf("%d",&n);
printf("\nEnter the nodes of the graph-");
for(i=1;i<=n;i++)
{
printf("\n enter name for %d node",i);
fflush(stdin);
scanf("%c",&g[i]);
}
printf("\nEnter the adjacency matrix of the graph:");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
printf("\n enter a[%d][%d]: ",i,j);
scanf("%d",&a[i][j]);
}

for(i=1;i<=n;i++)
state[i]=1;
state[1]=2;
insert(g[1]);
while(front<=rear)
{
x=delet();
for(i=1;i<=n;i++)
if(g[i]==x)

Dept. of MCA, TOCE, Bangalore 71

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

break;
state[i]=3;
printf("%c ",g[i]);
for(j=1;j<=n;j++)
{
if((a[i][j]==1)&&(state[j]==1))

{
state[j]=2;
insert(g[j]);
}
}
}
getch();
}
void insert(char x)
{
rear++;
q[rear]=x;
}
char delet()
{
char x;
x=q[front];
front++;
return(x);
}

INPUT-OUTPUT

Dept. of MCA, TOCE, Bangalore 72

07MCA27 Data Structure Using ‘C’ 2nd Semester, MCA

Enter the no. of nodes of graph: 3

Enter the nodes of the graph
Enter name for 1 node: a
Enter name for 2 node: b
Enter name for 3 node: c
Enter the adjacency matrix of the graph
Enter a [1][1]:0
Enter a [1] [2]:1
Enter a [1] [3]:1
Enter a [2] [1]:1
Enter a [2] [2]:0
Enter a [2] [3]:1
Enter a [3] [1]:1
Enter a [3] [2]:1
Enter a [3] [3]:0
ab c

Dept. of MCA, TOCE, Bangalore 73