TABLE OF CONTENTS

[Link] Date Title Page Mark Sign

No

1. SEARCHING:

1A. LINEAR SEARCHING

1B. BINARY SEARCHING

SORTING:
2.
2A. BUBBLE SORT
2B. SELECTION SORT
2C. INSERTION SORT
2D. SHELL SORT
2E. HEAP SORT

3. CONVERSION OF INFIX TO POSTFIX

4. STACK USING ARRAY

5. QUEUE USING ARRAY

6. LINKED LIST

7. STACK USING LINKED LIST

8. QUEUE USING LINKED LIST

9. DOUBLE ENDED QUEUE

10. BINARY SEARCH TREE

11. GRAPH TRAVERSALS:

(A) DEPTH FIRST SEARCH
(B) BREADTH FIRST SEARCH
 Page |1

Ex. No.1A LINEAR SEARCH

DATE:

AIM:
To Write a C Program to search a particular element from the given set of elements
using Linear Search (Recursion and Non-Recursion).

ALGORITHM:

Variables used:
K Array to hold elements
N  Total no of elements
X  Element to be searched

Function LINEAR_SEARCH (K, N, X)

1. [Initialize search]
I 1
K [N+1}  X
2. [Search the vector]
Repeat while K [I]  X
I  I +1
3. [Successful search?]
If I = N+1
Then Write (‘UNCSUCCESSFUL SEARCH’)
Return (0)
Else Write (‘SUCCESSFUL SEARCH”)
Return (1)
 Page |2

PROGRAM:

#include<stdio.h>
int RecursiveLS(int arr[], int value, int index, int n)
{
int pos = 0;

if(index >= n)
{
return 0;
}

else if (arr[index] == value)

{
pos = index + 1;
return pos;
}

else
{
return RecursiveLS(arr, value, index+1, n);
}
return pos;
}

int main()
{
int a[100],n,x,i,s=0;
printf("\n\n LINEAR SEARCH \n");
printf("\n Enter the Number of terms in the Array: ");
 Page |3

scanf("%d",&n);
printf("\n");
for(i=0;i<n;i++)
{
printf(" Enter the value of A[%d] : ",i+1);
scanf("%d",&a[i]);
}
printf("\n Enter the term that you want to search: ");
scanf("%d",&x);
printf("Searching without recursion ");
for(i=0;i<n;i++)
if(a[i]==x)
{
s=i+1;
printf("\n The given Number %d is found in the %d position.",x,s);
}
if(s==0)
printf("\n The given Number %d is not found in the Array. ",x);
s = RecursiveLS(a, x, 0, n);
printf("\nSearching with recursion ");
if (s != 0)
{
printf("\n The given Number %d is found in the %d position.",x,s);
}
else
{
printf("\n The given Number %d is not found in the Array. ",x);
}
return 0;
}
 Page |4

OUTPUT:

LINEAR SEARCH

Enter the Number of terms in the Array: 5

Enter the value of A[1] : 12

Enter the value of A[2] : 45
Enter the value of A[3] : 86
Enter the value of A[4] : 98
Enter the value of A[5] : 75

Enter the term that you want to search: 86

Searching without recursion
The given Number 86 is found in the 3 position.
Searching with recursion
The given Number 86 is found in the 3 position.
 Page |5

Ex. No.1B BINARY SEARCH

DATE:

AIM:
To Write a C Program to search a particular element from the given set of elements
using Binary Search (Recursion and Non-Recursion).

ALGORITHM:

Variables Used:

KVector to hold the elements

XTarget element to be searched.

LOW<-points to the lower bound of the vector.

HIGH<-points to the upper bound of the vector.

MIDDLE<-Points to the middle element in the vector.

1.{Initialise]

Low1

High N

2[Perform Search]

Repeat thru step 4 while LOW<= HIGH

3.[obtain Index of the midpoint interval]

MIDDLE(LOW + HIGH)/2

4.[Compare]

If X<K[MIDDLE]

Then HIGHMIDDLE-1

Else if X>K[MIDDLE]
 Page |6

Then LOWMIDDLE+1

Else Write (‘SUCCESSFUL SEARCH’)

Return (MIDDLE)

5. [UNSUCESSFUL SEARCH]

Write(‘UNSUCCESSFUL SEARCH’)

Return(0)

PROGRAM:
#include<stdio.h>

int m[100],x;
int iterativeBinarySearch(int array[], int start_index, int end_index, int element){
while (start_index <= end_index){
int middle = start_index + (end_index- start_index )/2;
if (array[middle] == element)
return middle+1;
if (array[middle] < element)
start_index = middle + 1;
else
end_index = middle - 1;
}
return -1;
}

int equal(int a,int b,int c)

{
if(a>b)
return 0;
if(m[c]==x)
return c+1;
else if(m[c]>x)
{

b=c-1;
c=(a+b)/2;
equal(a,b,c);
}
else if(m[c]<x)
{
a=c+1;
 Page |7

c=(a+b)/2;
equal(a,b,c);
}
else
return 0;
}

int main()
{
int i,l,h,mid,n,p;
printf("\n\n BINARY SEARCH");
printf("\n Enter the Number of terms in the Array: ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf(" Enter the value of A[%d]: ",i+1);
scanf("%d",&m[i]);
}
printf("\n Enter the number that you want to search: ");
scanf("%d",&x);
l=0;
h=n-1;
mid=(l+h)/2;
p=equal(l,h,mid);
printf("Using recursive method");
if(p==0)
printf("\n The given Number %d is not found in the Array.",x);
else
printf("\n The given Number %d is found in the %d position. ",x,p);
printf("\nUsing Non-recursive\n");
p = iterativeBinarySearch(m, 0, n-1, x);
if(p==-1)
printf("\n The given Number %d is not found in the Array.",x);
else
printf("\n The given Number %d is found in the %d position. ",x,p);
return 0;
}
 Page |8

SAMPLE INPUT OUTPUT:

BINARY SEARCH
Enter the Number of terms in the Array: 5
Enter the value of A[1]: 1
Enter the value of A[2]: 2
Enter the value of A[3]: 3
Enter the value of A[4]: 4
Enter the value of A[5]: 5
Enter the number that you want to search: 4
Using recursion
The given Number 4 is found in the 4 position.
Using Non recursion
The given Number 4 is found in the 4 position.

Criteria Maximum Marks

Marks Obtained
Aim and Algorithm 05
Program and Output 15
Viva 05
Total 25

RESULT:

Thus the C Program for searching was verified and executed successfully.
 Page |9

Ex. No.2A BUBBLE SORT

DATE:

AIM:
To Write a C Program to sort the given set of elements using Bubble Sort.

ALGORITHM:

Variables used:
K  Array to hold elements
N  Total no of elements
PASS  pass counter
LAST  position of the last unsorted element
EXCH  variable to count the no of exchanges made on any pass
I  index variable

Procedure BUBBLE_SORT(K,N)

1. [Initialize]
LAST  N
2. [Loop on pass index]
Repeat thru step 5 for PASS = 1,2,….,N-1
3. [Initialize exchanges counter for this pass]
EXCH 0
4. [Perform pair wise comparisons on unsorted elements]
Repeat for I=1,2,……LAST-1
If K[I] > K[I+1]
Then K[I] K[I+1]
EXCH  EXCH+1
5. [Were any exchanges made on this pass?]
If EXCH=0
 P a g e | 10

Then Return (mission accomplished; return early)

Else LAST LAST-1 (reduce size of unsorted list)
6. [Finished]
Return (maximum number of passes required)
PROGRAM:

#include<stdio.h>
#include<conio.h>
int main()
{
int i,j,temp,n,a[200];
clrscr();
printf("\n\n Bubble Sort");
printf("\n How many values have you got? ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf(" Enter the %d value: ",i+1);
scanf("%d",&a[i]);
}
printf("\n Sorted List");
for(i=0;i<n;i++)
{
for(j=0;j<n-1;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
 P a g e | 11

}
for(i=0;i<n;i++)
printf("\n %d",a[i]);
getch();
return 0;
}
INPUT & OUTPUT:

Bubble Sort
How many values have you got? 8
Enter the 1 value: 25
Enter the 2 value: 95
Enter the 3 value: 75
Enter the 4 value: 15
Enter the 5 value: 35
Enter the 6 value: 42
Enter the 7 value: 62
Enter the 8 value: 75
Sorted List
15
25
35
42
62
75
75
95
 P a g e | 12

Ex. No.2B SELECTION SORT

DATE:

AIM:
To Write a C Program to sort the given set of elements using Selection Sort.

ALGORITHM:

Variables used:
K  Array to hold elements
N  Total no of elements
PASS  Denotes the pass index
MIN_INDEX  Denotes the position of the smallest element
I  Index variable

Procedure SELECTION_SORT(K,N)

1. [Loop on pass index]

Repeat thru step 4 for PASS = 1,2,…,N-1
2. [Initialize minimum index]
MIN_INDEX  PASS
3. [Make a pass and obtain element with smallest value]
Repeat for I = PASS+1,PASS+2,…,N
If K[I] < K[MIN_INDEX]
Then MIN_INDEX  I
4. [Exchange elements]
If MIN_INDEX  PASS
Then K[PASS]  K[MIN_INDEX]

5. [Finised]
Return

PROGRAM:

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

int main()
{
int i,j,k,min,n,a[200];
clrscr();
printf("\n\n Selection Sort \n ");
printf("\n How many values do you have? ");
scanf("%d",&n);
for(i=0;i<n;i++)
 P a g e | 13

{
printf("\n Enter the %d value: ",i+1);
scanf("%d",&a[i]);
}
printf("\n Sorted List");
for(i=0;i<n;i++)
{
k=i;
min=a[i];
for(j=i+1;j<n;j++)
{
if(a[j]<min)
{
min=a[j];
k=j;
}
}
a[k]=a[i];
a[i]=min;
printf("\n %d",a[i]);
}
getch();
return 0;
}

INPUT & OUTPUT:

Selection Sort
How many values do you have? 5
Enter the 1 value: 78
Enter the 2 value: 25
Enter the 3 value: 75
Enter the 4 value: 91
Enter the 5 value: 100
Sorted List
25
75
78
91
100
 P a g e | 14

Ex. No. 2C INSERTION SORT

DATE:

AIM:
To Write a C Program to sort the given set of elements using Insertion Sort.

ALGORITHM:

Alg isort_c(unsigned *a, int n) {

int k;
for (k = 1; k < n; ++k) {
int key = a[k];
int i = k - 1;
while ((i >= 0) && (key < a[i])) {
a[i + 1] = a[i];
--i;
}
a[i + 1] = key;
}
}

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

int main()
{
int i,j,item,a[200],n;
clrscr();
printf("\n\n Insertion Sort");
printf("\n\n Enter the number of values you have got: ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf(" Enter the %d value: ",i+1);
scanf("%d",&a[i]);
}
printf("\n\n Sorted List");
for(j=1;j<n;j++)
 P a g e | 15

{
item=a[j];
i=j-1;
while((i>=0)&&(item<a[i]))
{
a[i+1]=a[i];
i=i-1;
}
a[i+1]=item;
}
for(i=0;i<n;i++)
{
printf("\n %d",a[i]);
}
getch();
return 0;
}

INPUT & OUTPUT:

Insertion Sort
Enter the number of values you have got: 5
Enter the 1 value: 25
Enter the 2 value: 36
Enter the 3 value: 15
Enter the 4 value: 75
Enter the 5 value: 92

Sorted List
15
25
36
75
92
 P a g e | 16

Ex. No.2D SHELL SORT

DATE:

AIM:
To Write a C Program to sort the given set of elements using Shell Sort.

ALGORITHM:

1. ShellSort(a, n) // 'a' is the given array, 'n' is the size of array

2. for (interval = n/2; interval > 0; interval /= 2)
3. for ( i = interval; i < n; i += 1)
4. temp = a[i];
5. for (j = i; j >= interval && a[j - interval] > temp; j -= interval)
6. a[j] = a[j - interval];
7. a[j] = temp;
8. End ShellSort

PROGRAM:

#include<stdio.h>
#define MAX 20
void main()
{
int arr[MAX],i,j,k,n,incr;
clrscr();
printf("\n\n SHELL SORT");
printf("\n Enter the Number of elements: ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf(" Enter the element [%d]: ",i+1);
scanf("%d",&arr[i]);
}
printf("\n Unsorted list is: \n");
for(i=0;i<n;i++)
printf(" %d",arr[i]);
printf("\n Enter the maximum increment (odd value) : ");
scanf(" %d",&incr);
// Shell Sort
while(incr>=1)
{
for(j=incr;j<n;j++)
{
k=arr[j];
for(i=j-incr;(i>=0)&&(k<arr[i]);i=i-incr)
arr[i+incr]=arr[i];
 P a g e | 17

arr[i+incr]=k;
}
printf("Increment = %d\n",incr);
for(i=0;i<n;i++)
printf(" %d",arr[i]);
printf("\n");
incr=incr-1;
} // End of while
printf(" Sorted list is: \n");
for(i=0;i<n;i++)
printf(" %d",arr[i]);
printf("\n");
getch();
}

INPUT & OUTPUT:

SHELL SORT
Enter the Number of elements: 5
Enter the element [1]: 98
Enter the element [2]: 23
Enter the element [3]: 10
Enter the element [4]: 75
Enter the element [5]: 89
Unsorted list is:
98 23 10 75 89
Enter the maximum increment (odd value) : 3
Increment = 3
75 23 10 98 89
Increment = 2
10 23 75 98 89
Increment = 1
10 23 75 89 98
Sorted list is:
10 23 75 89 98
 P a g e | 18

Ex. No.2E HEAP SORT

DATE:

AIM:
To Write a C Program to sort the given set of elements using Heap Sort.

ALGORITHM:

MaxHeapify(A, i)
l = left(i)
r = right(i)
if l <= heap-size[A] and A[l] > A[i]
then largest = l
else largest = i
if r <= heap-size[A] and A[r] > A[largest]
then largest = r
if largest != i
then swap A[i] with A[largest]
MaxHeapify(A, largest)
end func
BuildMaxHeap(A)
heap-size[A] = length[A]
for i = |length[A]/2| downto 1
do MaxHeapify(A, i)
end func
HeapSort(A)
BuildMaxHeap(A)
for i = length[A] downto 2
do swap A[1] with A[i]
heap-size[A] = heap-size[A] – 1
MaxHeapify(A, 1)
end func

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

void heapsort(int a[],int n);

void heapify(int a[],int n);
void adjust(int a[],int n,int i);

int a[10],n,i,j;

void main()
{
clrscr();
 P a g e | 19

printf("\n HEAP SORT ");

printf("\n Enter the no of elements:");
scanf("%d",&n);
printf("\n Enter the elements:");
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
heapsort(a,n);
printf("\n The sorted list is:");
for(i=1;i<=n;i++)
printf("\n %d",a[i]);
getch();
}

void heapsort(int a[],int n)

{
int t;
heapify(a,n);
for(i=n;i>=2;i--)
{
t=a[i];
a[i]=a[1];
a[1]=t;
adjust(a,1,i-1);
}
}

void heapify(int a[],int n)

{
for(i=(n/2);i>=1;i--)

adjust(a,i,n);
}

void adjust(int a[],int i,int n)

{
int item;
j=2*i;
item=a[i];
while(j<=n)
{
if((j<n)&&(a[j]<a[j+1]))
j=j+1;
if(item>=a[j])
break;
a[j/2]=a[j];
j=2*j;
}
a[j/2]=item;
}
 P a g e | 20

INPUT & OUTPUT:

HEAP SORT
Enter the no of elements:7
Enter the elements: 1 8 7 6 3 5 4
The sorted list is:
1
2
3
4
5
6
7
8

Criteria Maximum Marks

Marks Obtained
Aim and Algorithm 05
Program and Output 15
Viva 05
Total 25

RESULT:
Thus the sorting on the given vector elements has been performed and the program has
been executed and verified.
 P a g e | 21

Ex. No.03 CONVERSION OF INFIX TO POSTFIX

Date:

AIM:
To develop a program to implement stack application such as conversion of infix to
postfix expression.

ALGORITHM:
1. A string INFIX containing the infix expression
2. A stack opstk, which may contain:
- All arithmetic operators
- Parenthesis " (“ and “) "
- Null character " \O "
3. A string POSTFIXES containing the final postfix expression.

4. Push ' \o ' out OPSTACK as its first entry

5. Read the next character CH from the INFIX string
[Link] CH and:
- If CH is an operand, append it to the POSTFIX string
- If CH is a left parenthesis, then push CH onto the stack
- If CH is a right parenthesis. then pop entries from stack and append them to
POSTFIX until a left parenthesis is popped. Discard both left and right parentheses.
- If CH is ' \o ', pop all entries that remain on the stack and append them to the
POSTFIX string
- Otherwise, pop from the stack and append to the POSTFIX string , whose
STACK - PRIORITY is greater than or equal to the INFIX - PRIORITY of CH.
Then stack CH.
7. Repeat step (4) and (5) until CH becomes ' \o ‘.
 P a g e | 22

PROGRAM:
// Conversion of an arithmetic expression from infix to postfix

#include<stdio.h>
#include<conio.h>
#define STACKSIZE 100

struct stack // declaration of Stack Structure

{
char items[STACKSIZE];
int top;
}opstk;

void main()
{
int i=0,j=0;
char c,infix[100],postfix[100];
clrscr();
printf("\n\n\t\tCONVERSION OF INFIX TO POSTFIX\t\t\n\n");
printf("\n\nEnter the infix expression:");
gets(infix);
printf("********************************\n");
[Link] = 0;
[Link][[Link]] = '\0';
i=0;j=0;
while(infix[i] != '\0')
{
if((infix[i] == 'A') && (infix[i] <= 'Z'))/*Gets operands*/
postfix[j++] = infix[i++]; /*increments the positions*/
else if(infix[i] == ')')/*Stack priority is checked*/
{
c = pop(&opstk); /*operand stack is called*/
while(c != '(')
{
postfix[j++] = c; /*Pushed into the stack*/
c = pop(&opstk); /*Operand popped from the stack*/
}
i++;
}
else
{
c = pop(&opstk);

while(stp(c) >= imp(infix[i]))

{
postfix[j++] = c; /*assigned to c stack*/
c = pop(&opstk);
}
push(&opstk,c);/*Placed after evaluation*/
 P a g e | 23

push(&opstk,infix[i]);
i++;
}
}
while([Link] > 0)
{
c = pop(&opstk);
postfix[j++] = c;
}
postfix[j] = '\0';
printf("\n\n\n***********************************\n");
printf("The postfix expression is %s\n",postfix);
printf("************************************\n");
getch();
}

/*Pushing into the Stack*/

push(struct stack *ps,int y)

{
ps->items[++(ps->top)] = y;
return(y);
}

int pop(struct stack *ps) /*Popping from the stack*/

{
return(ps->items[ps->top--]);
}

int imp(char ch)

{
switch(ch) /*Differnt operators*/
{
case '*': /*same Priority levels*/
case '/':
return(2);

case '+':
case '-':
return(1);
case '\0':
return(0);
}
}

int stp(char ch) /*stack Priority*/

{
 P a g e | 24

switch(ch)
{
case '*': /*Values assigned different from operand stack*/
case '/':
return(2);
case '+':
case '-':
return(1);
case '\0':
return(0);
}
}

SAMPLE INPUT/OUTPUT:

CONVERSION OF INFIX TO POSTFIX

Enter the infix expression: a+b/c*d
********************************
***********************************
The postfix expression is abc/d*+
************************************

Criteria Maximum Marks

Marks Obtained
Aim and Algorithm 05
Program and Output 15
Viva 05
Total 25

RESULT:
Thus the application of stacks, Infix to postfix conversion has been implemented
 P a g e | 25

Ex. No.04 STACKS USING ARRAY

Date:

AIM:
To develop a program to perform stack operations and implement them.

ALGORITHM:

Variables used:
S  Array to hold elements
N  Total no of elements
TOP  Denotes the top element in the stack
X  The element to be inserted at the top of a stack
Procedure PUSH(S, TOP, X)
1. [Check for stack overflow]
If TOP>N
then Write ('STACK OVERFLOW')
Return
2. [Increment TOP]
TOP TOP+1
3. [Insert element]
S[TOP]  X
4. [Finished] Return
Variables used:
S  Array to hold elements
TOP denotes the top element in the stack
Procedure POP(S, TOP)
1. [Check for underflow on stack]
If TOP = 0
Then Write(‘STACK UNDERFLOW ON POP’)
Take action in response to underflow
Exit
2. [Decrement pointer]
TOP  TOP – 1
3. [Return former top element of stack]
Return(S [TOP + 1])
 P a g e | 26

PROGRAM:

#include<stdio.h>
#include<conio.h>
#define MAX 5

int front=-1,stack_arr[MAX];

push()
{
int pushed_item;
if(front==(MAX-1))
printf(" Stack Overflow.");
else
{
printf(" Enter the Item to be pushed : ");
scanf("%d",&pushed_item);
front++;
stack_arr[front]=pushed_item;
}
}

pop()
{
if(front==-1)
printf(" Stack Underflow.");
else
{
printf(" Item %d is deleted from the stack.",stack_arr[front]);
front--;
}
}

display()
{
int i;
if(front==-1)
printf(" Stack Empty.");
else
{
printf(" Stack elements are....");
for(i=front;i>=0;i--)

printf("\n %d ",stack_arr[i]);
}
}

void main()
 P a g e | 27

{
int ch;
clrscr();
while(1)
{
printf("\n Select your Operation: \n");
printf(" 1. Push \n ");
printf(" 2. Pop \n ");
printf(" 3. Display \n ");
printf(" 4. Exit \n ");
printf("\n Enter your choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("\n Wrong Choice.");
}
}
}

SAMPLE INPUT/OUTPUT:
Select your Operation:
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 1
Enter the Item to be pushed : 2
Select your Operation:
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 1
 P a g e | 28

Enter the Item to be pushed : 7

Select your Operation:
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 1
Enter the Item to be pushed : 5
Select your Operation:
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 3
Stack elements are....
5
7
2
Select your Operation:
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 2
Item 5 is deleted from the stack.
Select your Operation:
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 2
Item 7 is deleted from the stack.
Select your Operation:
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 3
Stack elements are....
2
Select your Operation:
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 4
 P a g e | 29

Criteria Maximum Marks

Marks Obtained
Aim and Algorithm 05
Program and Output 15
Viva 05
Total 25

RESULT:
Thus the various stack operations such as push pop display ahs been implemented and
the program is verified.
 P a g e | 30

Ex. No.05 QUEUES USING ARRAY

DATE:

AIM:

To develop a program to perform Queue operations and implement them.

ALGORITHM:
Procedure QINSERT(Q, F, R, N, Y)
Variables used:
F  Front end pointer
R  Rear end pointer
Q  Queue
N Total no of elements
Y  The element to be inserted

1. [Overflow?]
If R ≥ N
Then Write(‘OVERFLOW’)
Return
2. [Increment rear pointer]
R R+1
3. [Insert element]
Q[R]  Y
4. [Is front pointer properly set?]
If F = 0
Then F  1
Return

Procedure QDELETE (Q, F, R)

Variables used
Q  Queue
F  Front end pointer
R  Rear end pointer
Y  Temporary variable

1. [Underflow?]
If F = 0
Then Write(‘UNDERFLOW’)
Return(0) (0 denotes an empty queue)
2. [Delete element]
Y  Q[F]
3. [Queue empty?]
If F = R
Then F  R 0
Else F F + 1 (Increment front pointer)
3. [Return element]
Return(Y)
 P a g e | 31

PROGRAM:
#include<stdio.h>
#include<conio.h>
#define MAX 5

int front=-1,rear=-1,queue_arr[MAX];

push()
{
int pushed_item;
if(rear==(MAX-1))
printf("\n Queue Overflow.");
else
{
if(front==-1)
front++;
printf("\n Enter the item to be pushed: ");
scanf("%d",&pushed_item);
rear++;
queue_arr[rear]=pushed_item;
}
}

pop()
{
if(front>rear)
printf("\n Queue Underflow.");
else
{
printf("\n The element %d is removed from stack.",queue_arr[front]);
front++;
}
}

display()
{
int i;
if(front>rear)
printf("\n Queue Underflow.");
else
{

printf("\n Queue elements are.....");

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

void main()
 P a g e | 32

{
int choice;
clrscr();
while(1)
{
printf("\n Select a queue operation.....\n" );
printf(" 1. Push \n ");
printf(" 2. Pop \n ");
printf(" 3. Display \n ");
printf(" 4. Exit \n ");
printf(" Enter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("\n Wrong choice.");
}
}
}

SAMPLE INPUT/OUTPUT:
Select a queue operation.....
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 1
Enter the item to be pushed: 4
Select a queue operation.....
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 1
Enter the item to be pushed: 7
Select a queue operation.....
 P a g e | 33

1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 1
Enter the item to be pushed: 1
Select a queue operation.....
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 3
Queue elements are..... 4 7 1
Select a queue operation.....
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 2
The element 4 is removed from stack.
Select a queue operation.....
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 2
The element 7 is removed from stack.
Select a queue operation.....
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 3
Queue elements are..... 1
Select a queue operation.....
1. Push
2. Pop
3. Display
4. Exit
Enter your choice: 4
 P a g e | 34

Criteria Maximum Marks

Marks Obtained
Aim and Algorithm 05
Program and Output 15
Viva 05
Total 25

RESULT:
Thus the Queue operations are implemented and the program has been executed
and verified.
 P a g e | 35

Ex. No.06 LINKED LIST

DATE:
AIM:

To develop a program to perform singly linked list operations.

ALGORITHM:

Function INSERT(X, FIRST)

Variables used:

X  New element to be inserted

FIRST  Pointer to the first element whose node contains

INFO and LINK fields.

AVAIL Pointer to the top element of the availability stack

NEW  Temporary pointer variable.

1. [Underflow?]
If AVAIL = NULL

Then Write(‘AVAILABILITY STACK UNDERFLOW’)

Return(FIRST)

2. [Obtain address of next free node]

NEW  AVAIL

3. [Remove free node from availability stack]

AVAIL  LINK(AVAIL)

4. [Initialize fields of new node and its link to the list]

INFO(NEW)  X

LINK(NEW)  FIRST

5. [Return address of new node]

Return (NEW)
 P a g e | 36

Function INSORD(X, FIRST)

Variables used:

X new element

FIRST Pointer to the first element whose node contains

INFO and LINK fields.

AVAIL pointer to the top element of the availability stack

NEW,SAVE Temporary pointer variables

1. [Underflow?]

If AVAIL = NULL

Then Write(‘AVAILABILITY STACK UNDERFLOW’)

Return(FIRST)

2. [Obtain address of next free node]

NEW  AVAIL

3. [Remove free node from availability stack]

AVAIL  LINK(AVAIL)

4. [Copy information contents into new node]

INFO(NEW)  X

5. [Is the list empty?]

If FIRST = NULL

Then LINK(NEW)  NULL

6. [Does the new node precede all others in the list?]

If INFO(NEW) ≤ INFO(FIRST)

Then LINK(NEW)  FIRST

Return(NEW)

7. [Initialize temporary pointer]

SAVE  FIRST
 P a g e | 37

8. [Search for predecessor of new node]

Repeat while LINK(SAVE) ≠ NULL and INFO(LINK(SAVE))≤ INFO(NEW)

SAVE  LINK(SAVE)

9. [Set link fields of new node and its predecessor]

LINK(NEW)  LINK(SAVE)

LINK(SAVE) NEW

10. [Return first node pointer]

Return(FIRST)

Function INSEND(X,FIRST)

Variables used:

X new element

FIRST Pointer to the first element whose node contains

INFO and LINK fields.

AVAIL pointer to the top element of the availability stack

NEW, SAVE Temporary pointer variables

1. [Underflow?]
If AVAIL = NULL

Then Write(‘AVAILABILITY STACK UNDERFLOW’)

Return(FIRST)

2. [Obtain address of next free node]

NEW  AVAIL

3. [Remove free node from availability stack]

AVAIL  LINK(AVAIL)

4. [Initialize fields of new node]

INFO(NEW)  X
 P a g e | 38

LINK(NEW)  NULL

5. [Is the list empty?]

If FIRST = NULL

Then Return(NEW)

6. [Initiate search for the last node]

SAVE  FIRST

7. [Search for end of list]

Repeat while LINK(SAVE) ≠ NULL

SAVE  LINK (SAVE)

8. [Set LINK field of last node to NEW]

LINK (SAVE)  NEW

9. [Return first node pointer]

Return (FIRST)

Procedure DELETE(X, FIRST)

Variables used:

X  New element to be inserted

FIRST  Pointer to the first element whose node contains

INFO and LINK fields.

TEMP To find the desired node

PRED keeps track of the predecessor of TEMP

1. [Empty list?]
If FIRST = NULL

Then Write(‘UNDERFLOW”)

Return

2. [Initialize search for X]

 P a g e | 39

TEMP  FIRST

3. [Find X]
Repeat thru step 5 while TEMP ≠ X and LINK(TEMP) ≠ NULL

4. [Update predecessor marker]

PRED  TEMP

5. [Move to next node]

TEMP  LINK(TEMP)

6. [End of the list]

If TEMP ≠ X

Then Write (‘NODE NOT FOUND”)

Return

7. [Delete X]
If X = FIRST (Is X the first node?)

Then FIRST  LINK(FIRST)

Else LINK (PRED)  LINK(X)

8. [Return node to availability area]

LINK(X)  AVAIL

AVAIL  X

Return

PROGRAM:

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

struct node
{
int info;
 P a g e | 40

struct node*link;
} *start;

main()
{
int choice,n,m,position,i;
start=NULL;
clrscr();
while(1)
{
printf("\n 1. Create List");
printf("\n 2. Add at beginning");
printf("\n 3. Add after");
printf("\n 4. Delete");
printf("\n 5. Display");
printf("\n 6. Count");
printf("\n 7. Reverse");
printf("\n 8. Search");
printf("\n 9. Quit");
printf("\n Enter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf(" How many nodes you want: ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf(" Enter the element: ");
scanf("%d",&m);
 P a g e | 41

create_list(m);
}
break;
case 2:

printf("\n Enter the element: ");

scanf("%d",&m);
addatbeg(m);
break;
case 3:
printf("\n Enter the element: ");
scanf("%d",&m);
printf("\n Enter the position after which this element is inserted: ");
scanf("%d",&position);
addafter(m,position);
break;
case 4:
if(start==NULL)
{
printf("\n List is empty.");
continue;
}
printf("\n Enter the element for deletion: ");
scanf("%d",&m);
del(m);
break;
case 5:
display();
break;
 P a g e | 42

case 6:
count();
break;
case 7:
rev();
break;
case 8:
printf("\n Enter the element to be searched : ");
scanf("%d",&m);
search(m);
break;
case 9:
exit();
default:
printf("\n Wrong Choice.");
} // End of Switch
} // End of while
} // End of main

create_list(int data)
{
struct node *q,*tmp;
tmp=malloc(sizeof(struct node));
tmp->info=data;
tmp->link=NULL;
if(start==NULL) // If the List is empty
start=tmp;
else
{ // Elements inserted at end
q=start;
 P a g e | 43

while(q->link!=NULL)
q=q->link;
q->link=tmp;
}
} // End of create list

addatbeg(int data)
{
struct node *tmp;
tmp=malloc(sizeof(struct node));
tmp->info=data;
tmp->link=start;
start=tmp;
} // End of addatbeg()

addafter(int data,int pos)

{
struct node *tmp, *q;
int i;
q=start;
for(i=0;i<(pos-1);i++)
{
q=q->link;
if(q==NULL)
{
printf("\n There are less than %d elements.",pos);
return;
}
} // End of for
tmp=malloc(sizeof(struct node));
 P a g e | 44

tmp->link=q->link;
tmp->info=data;
q->link=tmp;
} // End of addafter()
del(int data)
{
struct node *tmp,*q;
if(start->info==data)
{
tmp=start;
start=start->link; // first element deleted
free(tmp);
return;
}
q=start;
while(q->link->link!=NULL)
{
if(q->link->info==data) // Element deleted in between
{
tmp=q->link;
q->link=tmp->link;
free(tmp);
return;
}
q=q->link;
} // end of while
if(q->link->info==data) // Last element deleted
{
tmp=q->link;
free(tmp);
 P a g e | 45

q->link=NULL;
return;
}
printf("\n Element %d not found.",data);
} // end of del()
display()
{
struct node *q;
if(start==NULL)
{
printf("\n List is empty.");
return;
}
q=start;
printf("\n List is: ");
while(q!=NULL)
{
printf(" %d ",q->info);
q=q->link;
}
printf("\n");
} // End of display

count()
{
struct node *q=start;
int cnt=0;
while(q!=NULL)
{
q=q->link;
 P a g e | 46

cnt++;
}
printf("\n Number of elements are %d.",cnt);
} // End of count

\
search(int data)
{
struct node *ptr=start;
int pos=1;
while(ptr!=NULL)
{
if(ptr->info==data)
{
printf("\n item %d found at position %d.\n",data,pos);
return;
}
ptr=ptr->link;
pos++;
}
if(ptr==NULL)
printf("\n Item %d not found in list.",data);
} // End of search

SAMPLE INPUT/OUTPUT:

1. Create List
2. Add at beginning
3. Add after
4. Delete
5. Display
6. Count
7. Search
8. Quit
 P a g e | 47

Enter your choice: 1

How many nodes you want: 4
Enter the element: 1
Enter the element: 2
Enter the element: 3
Enter the element: 9
1. Create List
2. Add at beginning
3. Add after
4. Delete
5. Display
6. Count
7. Search
8. Quit
Enter your choice: 2
Enter the element: 7
1. Create List
2. Add at beginning
3. Add after
4. Delete
5. Display
6. Count
7. Search
8. Quit

Enter your choice: 5

List is: 71239
1. Create List
2. Add at beginning
3. Add after
4. Delete
5. Display
6. Count
7. Search
8. Quit
Enter your choice: 3
Enter the element: 8
Enter the position after which this element is inserted: 3
1. Create List
2. Add at beginning
3. Add after
4. Delete
5. Display
6. Count
7. Search
8. Quit
Enter your choice: 5
List is: 7 1 2 8 3 9
1. Create List
2. Add at beginning
 P a g e | 48

3. Add after
4. Delete
5. Display
6. Count
7. Search
8. Quit
Enter your choice: 4
Enter the element for deletion: 7
1. Create List
2. Add at beginning
3. Add after
4. Delete
5. Display
6. Count
7. Search
8. Quit
Enter your choice: 4
Enter the element for deletion: 9
1. Create List
2. Add at beginning
3. Add after
4. Delete
5. Display
6. Count
7. Search
8. Quit
Enter your choice: 5
List is: 1 2 83
1. Create List
2. Add at beginning
3. Add after
4. Delete
5. Display
6. Count
7. Search
8. Quit
Enter your choice: 6
Number of elements are 4.
1. Create List
1. Create List
2. Add at beginning
3. Add after
4. Delete
5. Display
6. Count
7. Search
8. Quit
Enter your choice: 7
1. Create List
2. Add at beginning
 P a g e | 49

3. Add after
4. Delete
5. Display
6. Count
7. Search
8. Quit
Enter your choice: 5
List is: 3 8 2 1
1. Create List
2. Add at beginning
3. Add after
4. Delete
5. Display
6. Count
7. Search
8. Quit
Enter your choice: 6
Number of elements are 4.
1. Create List
2. Add at beginning
3. Add after
4. Delete
5. Display
6. Count
7. Search
8. Quit
Enter your choice: 8
Enter the element to be searched : 3
item 3 found at position 1.
1. Create List
2. Add at beginning
3. Add after
4. Delete
5. Display
6. Count
7. Search
8. Quit
Enter your choice: 9
 P a g e | 50

Criteria Maximum Marks

Marks Obtained
Aim and Algorithm 05
Program and Output 15
Viva 05
Total 25

RESULT:
Thus the singly linked list operations are implemented and the program'm has been
executed and verified.
 P a g e | 51

Ex. No.07 STACK USING LINKED LIST

DATE:

AIM:
To develop a program to implement the Stack using singly linked list.
ALGORITHM:
To implement a stack using a linked list, we need to set the following things before
implementing actual operations.

• Step 1 - Include all the header files which are used in the program. And declare all
the user defined functions.
• Step 2 - Define a 'Node' structure with two members data and next.
• Step 3 - Define a Node pointer 'top' and set it to NULL.
• Step 4 - Implement the main method by displaying Menu with list of operations and
make suitable function calls in the main method.

push(value) - Inserting an element into the Stack

We can use the following steps to insert a new node into the stack...

• Step 1 - Create a newNode with given value.

• Step 2 - Check whether stack is Empty (top == NULL)
• Step 3 - If it is Empty, then set newNode → next = NULL.
• Step 4 - If it is Not Empty, then set newNode → next = top.
• Step 5 - Finally, set top = newNode.

pop() - Deleting an Element from a Stack

We can use the following steps to delete a node from the stack...

• Step 1 - Check whether stack is Empty (top == NULL).

• Step 2 - If it is Empty, then display "Stack is Empty!!! Deletion is not
possible!!!" and terminate the function
• Step 3 - If it is Not Empty, then define a Node pointer 'temp' and set it to 'top'.
• Step 4 - Then set 'top = top → next'.
• Step 5 - Finally, delete 'temp'. (free(temp)).

display() - Displaying stack of elements

We can use the following steps to display the elements (nodes) of a stack...

• Step 1 - Check whether stack is Empty (top == NULL).

• Step 2 - If it is Empty, then display 'Stack is Empty!!!' and terminate the function.
• Step 3 - If it is Not Empty, then define a Node pointer 'temp' and initialize with top.
• Step 4 - Display 'temp → data --->' and move it to the next node. Repeat the same
until temp reaches to the first node in the stack. (temp → next != NULL).
• Step 5 - Finally! Display 'temp → data ---> NULL'
 P a g e | 52

PROGRAM:

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

struct node
{
int data;
struct node *next;
}*top=NULL;

void push(int);
void pop();
void display();
int main()
{
int choice;
int value;
while (1)
{
printf("\nMenu \n");
printf("1-push \n 2-pop \n 3-display \n 4-exit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
printf("Enter the value : ");
scanf("%d",&value);
push(value);
 P a g e | 53

break;
}
case 2:
pop();
break;
case 3:
display();
break;
case 4:
exit (0);
default:
printf("Invalid Choice");
}
}

}
void push(int val)
{
struct node *temp;
temp =(struct node*)malloc(sizeof(struct node));
if(temp == NULL)
{
printf("Stack Overflow");
}
else
{
if(top == NULL)
{
temp->data=val;
temp->next=NULL;
 P a g e | 54

top=temp;
}
else
{
temp->data = val;
temp->next = top;
top=temp;
}
}
}
void pop()
{
struct node *temp;
if(top==NULL)
{
printf("Stack Underflow");
}
else
{
temp=top;
top=top->next;
free(temp);
}
}
void display()
{
struct node *temp;
temp=top;
if(temp==NULL)
{
 P a g e | 55

printf("Stack is empty");
}
else
{
while(temp!=NULL)
{
printf("%d->",temp->data);
temp=temp->next;
}
printf("NULL");
}
}

SAMPLE INPUT/OUTPUT:
Menu
1-push
2-pop
3-display
4-exit
Enter your choice : 1
Enter the value : 12

Menu
1-push
2-pop
3-display
4-exit
Enter your choice : 1
Enter the value : 16
 P a g e | 56

Menu
1-push
2-pop
3-display
4-exit
Enter your choice : 1
Enter the value : 15

Menu
1-push
2-pop
3-display
4-exit
Enter your choice : 2

Menu
1-push
2-pop
3-display
4-exit
Enter your choice : 3
16->12->NULL
Menu
1-push
2-pop
3-display
4-exit
Enter your choice : 4
 P a g e | 57

Criteria Maximum Marks

Marks Obtained
Aim and Algorithm 05
Program and Output 15
Viva 05
Total 25

RESULT:
Thus the program has been executed and the stack using singly linked list are
implemented and verified.
 P a g e | 58

Ex. No.08 QUEUE USING LINKED LIST

DATE:

AIM:
To develop a program to implement the Queue using singly linked list.
ALGORITHM:

Step 1: Allocate the space for the new node PTR

Step 2: SET PTR -> DATA = VAL
Step 3: IF FRONT = NULL
SET FRONT = REAR = PTR
SET FRONT -> NEXT = REAR -> NEXT = NULL
ELSE
SET REAR -> NEXT = PTR
SET REAR = PTR
SET REAR -> NEXT = NULL
[END OF IF]
Step 4: END

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

struct node
{
int data;
struct node *next;
}*head=NULL;

void enqueue(int);
void dequeue();
 P a g e | 59

void display();
int main()
{
int choice;
int value;
while (1)
{
printf("\nMenu \n");
printf("1-Enqueue \n 2-Dequeue \n 3-display \n 4-exit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
printf("Enter the value : ");
scanf("%d",&value);
enqueue(value);
break;
}
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
exit (0);
default:
printf("Invalid Choice");
 P a g e | 60

}
}

}
void enqueue(int item)
{
struct node *p,*temp;
p = (struct node *) malloc(sizeof(struct node));
if(p == NULL)
{
printf("\nOVERFLOW");
}
else
{
p->data=item;
if(head == NULL)
{
p->next = NULL;
head = p;
}
else
{
temp = head;
while(temp->next!=NULL)
{
temp = temp->next;
}
temp->next = p;
p->next = NULL;
}
 P a g e | 61

}
printf("\ninserted\n");
}

void dequeue()
{
struct node *p;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\n deleted\n");
}
else
{
p = head;
head = head -> next;
free(p);
printf("\ndeleted\n");
}

}
void display()
{
struct node *p;
printf("\nPrinting values...\n");
 P a g e | 62

p = head;
if(head==NULL)
{
printf("Empty");
}
else
{
while(p != NULL)
{
printf("%d\n",p->data);
p=p->next;
}
}
}

SAMPLE INPUT/OUTPUT:
Menu
1-Enqueue
2-Dequeue
3-display
4-exit
Enter your choice : 1
Enter the value : 12

inserted

Menu
1-Enqueue
2-Dequeue
 P a g e | 63

3-display
4-exit
Enter your choice : 1
Enter the value : 15

inserted

Menu
1-Enqueue
2-Dequeue
3-display
4-exit
Enter your choice : 1
Enter the value : 14

inserted

Menu
1-Enqueue
2-Dequeue
3-display
4-exit
Enter your choice : 2

deleted

Menu
1-Enqueue
2-Dequeue
3-display
 P a g e | 64

4-exit
Enter your choice : 3

Printing values...
15
14

Menu
1-Enqueue
2-Dequeue
3-display
4-exit
Enter your choice : 4

Criteria Maximum Marks

Marks Obtained
Aim and Algorithm 05
Program and Output 15
Viva 05
Total 25

RESULT:
Thus the program has been executed and the queue using singly linked list are
implemented and verified.
 P a g e | 65

Ex. No.09 DOUBLE ENDED QUEUE

DATE:

AIM:
To develop a program to implement the Double ended queue using double linked list.
PROGRAM:
#include<stdio.h>
#include <stdlib.h>
/declaring a structure to create a node/

struct node

{
int data;
struct node *prev, *next;

};

struct node *head = NULL, *tail = NULL;

struct node * createNode(int data)

/allocating implicit memory to the node/

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

newnode->data = data;
newnode->next = newnode->prev = NULL;
return (newnode);
 P a g e | 66

}
/* create sentinel(dummy head & tail) that helps us to do insertion and deletion operation at
front and rear so easily. And these dummy head and tail wont get deleted till the end of
execution of this program */

void createSentinels() /creating a head and tail/ {

head = createNode(0);
tail = createNode(0);
head->next = tail;
tail->prev = head;
}

/* insertion at the front of the queue */

void enqueueAtFront(int data)

{
struct node *newnode, *temp;
newnode = createNode(data);
temp = head->next;
head->next = newnode;
newnode->prev = head;

newnode->next = temp;
temp->prev = newnode;
}

/*insertion at the rear of the queue */

void enqueueAtRear(int data)
 P a g e | 67

{
struct node *newnode, *temp;
newnode = createNode(data);

temp = tail->prev;
tail->prev = newnode;
newnode->next = tail;
newnode->prev = temp;
temp->next = newnode;

/* deletion at the front of the queue */

void dequeueAtFront()
{

struct node *temp;

if (head->next == tail)

{
printf("Queue is empty\n");
}

else
{
temp = head->next;
head->next = temp->next;
temp->next->prev = head;

free(temp);
 P a g e | 68

}
return;
}
/* deletion at the rear of the queue */

void dequeueAtRear()
{
struct node *temp;
if (tail->prev == head)
{
printf("Queue is empty\n");
}
else
{
temp = tail->prev;
tail->prev = temp->prev;
temp->prev->next = tail;
free(temp);
}
return;
}
/* display elements present in the queue */

void display()
{
struct node *temp;

if (head->next == tail)
{
printf("Queue is empty\n");
 P a g e | 69

return;
}
temp = head->next;
while (temp != tail)
{

printf("%-3d", temp->data);
temp = temp->next;
}
printf("\n");
}
/main program/
int main()
{
int data, ch;

createSentinels();
while (1)

{
printf("1. Enqueue at front\n2. Enqueue at rear\n");
printf("3. Dequeue at front\n4. Dequeue at rear\n");

printf("5. Display\n6. Exit\n");

printf("Enter your choice:");
scanf("%d", &ch);
switch (ch) /switch case/
{
case 1:
printf("Enter the data to insert:");
 P a g e | 70

scanf("%d", &data);
enqueueAtFront(data);
break;

case 2:

printf("Enter ur data to insert:");

scanf("%d", &data);
enqueueAtRear(data);
break;

case 3:
dequeueAtFront();
break;

case 4:

dequeueAtRear();
break
case 5:
display();
break;

case 6:
exit(0);

default:
printf(" enter correct option\n");
break;
} /end of switch case/
 P a g e | 71

}
return 0;
}
SAMPLE INPUT/OUTPUT:
1. Enqueue at front
2. Enqueue at rear
3. Dequeue at front
4. Dequeue at rear
5. Display
6. Exit
Enter your choice:1
Enter the data to insert:13
1. Enqueue at front
2. Enqueue at rear
3. Dequeue at front
4. Dequeue at rear
5. Display
6. Exit
Enter your choice:2
Enter ur data to insert:15
1. Enqueue at front
2. Enqueue at rear
3. Dequeue at front
4. Dequeue at rear
5. Display
6. Exit
Enter your choice:3
1. Enqueue at front
2. Enqueue at rear
3. Dequeue at front
 P a g e | 72

4. Dequeue at rear
5. Display
6. Exit
Enter your choice:4
1. Enqueue at front
2. Enqueue at rear
3. Dequeue at front
4. Dequeue at rear
5. Display
6. Exit
Enter your choice:5
Queue is empty
1. Enqueue at front
2. Enqueue at rear
3. Dequeue at front
4. Dequeue at rear
5. Display
6. Exit
Enter your choice:6
 P a g e | 73

Criteria Maximum Marks

Marks Obtained
Aim and Algorithm 05
Program and Output 15
Viva 05
Total 25

RESULT:

Thus the program has been executed and the double ended queue using double linked
list are implemented and verified.
 P a g e | 74

Ex. No.10 BINARY TREE TRAVERSAL

DATE:

AIM:
To develop a program to implement the Binary Search Tree and its operations.

ALGORITHM:
Insertion and deletion operations on a binary tree
Procedure Insert(element type,x,y)
[Link] (element type,x,y)
[Link](T==NULL)
t=malloc(sizeof(struct tree node))
[Link]
element(t)X
left(T)right(T)NULL
[Link] X<Element(T)
then left(T) Insert(x,Left(T))
[Link]
if X>element(T)
right(T)insert(x,right(T)0
[Link].

Procedure delete(Head,x)
[Link]
if LPTR(HEAD)!=HEAD
then
cur LPTR(HEAD)
PARENTHEAD
D ‘L’
Else
Write(‘Node not found’)
[Link] for the node marked for deletion
FOUND FALSE
 P a g e | 75

[Link] and repeat while node marked for deletion

if DATA(CUR)==X
then FOUNDTRUE
else if X>DATA(CUR)
PARENTCUR
CURLPTR(CUR)
D’R’
[Link] FOUND =FALSE
then write(‘Node not found’)
return.
[Link] the tree
if LPTR(CUR)==NULL
then empty left sub tree
QLPTR(CUR)
Else
Search for the right child
SocRPTR(CUR)
If LPTR(SOC)= = NULL
Then LPTR(SOC)LPTR(CUR)
QSOC
Else
PREVRPTR(CUR)
SUCLPTR(PRED)
Repeat while LPTR(SOC)!=NULL
PREVSOC
SOCLPTR(PRED)

LPTR(PRED)RPTR(SOC)
LPTR(SOC)RPTR(CUR)
QSOC
[Link].
 P a g e | 76

/*TREE TRAVERSAL*/

Procedure Inorder
1. check for the condition
if(Ptr!=NULL)
2. Call inorder (LPTR)
Inorder(left(Ptr))
[Link] the value
4. call inorder(right)
inorder(right(Ptr))
5. Repeat steps 2,3,4 until step 1 holds TRUE.
[Link].
Procedure Postorder

[Link]!=NULL
2. callpost order(Left(ptr))
[Link] post order(right(ptr))
4. Print the value.
5. repeat steps 2,3,4 until step 1 holds TRUE
[Link].
Procedure Preorder
[Link] ptr1=NULL
[Link] the value.
[Link] preorder(left(Ptr))
[Link] preorder(right(ptr))
[Link] thru steps 2,3,4 until step 1 holds True.
[Link].
 P a g e | 77

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

struct node
{
int data;
struct node *right,*left;
}*root,*p,*q;

struct node *make(int y)

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

void left(struct node *r,int x)

{
if(r->left!=NULL)
printf("\n Invalid!");
else
r->left=make(x);
}

void right(struct node *r,int x)

{
if(r->right!=NULL)
printf("\n Invalid!");
else
r->right=make(x);
}

void inorder(struct node *r)

{
if(r!=NULL)
{
inorder(r->left);
printf("\t %d",r->data);
inorder(r->right);

}
}

void preorder(struct node *r)

{
if(r!=NULL)
 P a g e | 78

{
printf("\t %d",r->data);
preorder(r->left);
preorder(r->right);
}
}

void postorder(struct node *r)

{
if(r!=NULL)
{
postorder(r->left);
postorder(r->right);
printf("\t %d",r->data);
}
}

void main()
{
int no;
int choice;
clrscr();
printf("\n Enter the root:");
scanf("%d",&no);
root=make(no);
p=root;
while(1)
{
printf("\n Do you want to enter another node? ");
printf("\n 1. Yes");
printf("\n 2. No");
printf("\n Enter your choice: ");
scanf("%d",&choice);
if(choice==1)
{
printf("\n Enter another no:");
scanf("%d",&no);
while(1)

{
p=root;
q=root;
while((no!=p->data)&&(q!=NULL))
{
p=q;
if(no<p->data)
q=p->left;
else
q=p->right;
 P a g e | 79

}
if(no<p->data)
{
printf("\n Left branch of %d is %d",p->data,no);
left(p,no);
break;
}
else
{
right(p,no);
printf("\n Right branch of %d is %d",p->data,no);
break;
}
}
}
else if(choice==2)
break;
else
{
printf("\n Wrong Choice!");
continue;
}
}
while(1)
{
printf("\n 1. Inorder traversal\n 2. Preorder traversal\n 3. Postorder traversal\n 4. Exit");
printf("\n Enter your choice:");
scanf("\%d",&choice);
switch(choice)
{
case 1:
inorder(root);
break;

case 2:
preorder(root);
break;
case 3:
postorder(root);
break;
case 4:
exit(1);
default:
printf("\n Invalid choice!");
break;
}
getch();
}
}
 P a g e | 80

SAMPLE INPUT/OUTPUT:

BINARY TREE TRAVERSALS

Enter the root:5
Do you want to enter another node?
1. Yes
2. No
Enter your choice: 1
Enter another number:3
Left branch of 5 is 3
Do you want to enter another node?
1. Yes
2. No
Enter your choice: 1
Enter another number:7
Right branch of 5 is 7
Do you want to enter another node?
1. Yes
2. No
Enter your choice: 1
Enter another number:2
Left branch of 3 is 2
Do you want to enter another node?
1. Yes
2. No
Enter your choice: 1
Enter another number:4
Right branch of 3 is 4
Do you want to enter another node?
1. Yes
2. No
Enter your choice: 1
Enter another number:6
Left branch of 7 is 6
Do you want to enter another node?
1. Yes
2. No

Enter your choice: 1

Enter another number:9
Right branch of 7 is 9
Do you want to enter another node?
1. Yes
2. No
Enter your choice: 2
1. Inorder traversal
2. Preorder traversal
3. Postorder traversal
4. Exit
 P a g e | 81

Enter your choice:1

2 3 4 5 6 7 9
1. Inorder traversal
2. Preorder traversal
3. Postorder traversal
4. Exit
Enter your choice:2
5 3 2 4 7 6 9
1. Inorder traversal
2. Preorder traversal
3. Postorder traversal
4. Exit
Enter your choice:3
2 4 3 6 9 7 5
1. Inorder traversal
2. Preorder traversal
3. Postorder traversal
4. Exit
Enter your choice:4

Criteria Maximum Marks

Marks Obtained
Aim and Algorithm 05
Program and Output 15
Viva 05
Total 25

RESULT:
Thus the program has been executed and the binary search tree operations are
implemented and verified.
 P a g e | 82

Ex. No.11(A) DEPTH FIRST SEARCH

DATE:

AIM:
To write a c program to perform Depth first search

ALGORITHM:

procedure DFS(G, v) is
label v as discovered
for all directed edges from v to w that are in [Link](v) do
if vertex w is not labeled as discovered then
recursively call DFS(G, w)

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

int adj[10][10],vis[10],n;

void dfs(int v);

void main()
{
int i,j,v=1;
clrscr();
printf("\n DEPTH FIRST SEARCH");
printf("\n Enter the no of nodes:");
scanf("%d",&n);
printf("\n Enter the adajacency matrix:");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
scanf("%d",&adj[i][j]);
}
printf("\n The visited order is:");
dfs(v);
getch();
}
 P a g e | 83

void dfs(int v)
{
int w;
vis[v]=1;
printf(" -> %d",v);
for(w=1;w<=n;w++)
{
if(vis[w]==0)
{
if(adj[v][w]==1)
{
dfs(w);
}
}
}
}

SAMPLE INPUT /OUTPUT:

INPUT & OUTPUT SCREEN:

DEPTH FIRST SEARCH
Enter the no of nodes:8
Enter the adajacency matrix:
0 1 1 0 0 0 0 0

1 0 0 1 1 0 0 0
1 0 0 0 0 1 1 0

0 1 0 0 0 0 0 1
0 1 0 0 0 0 0 1

0 0 1 0 0 0 0 1

0 0 1 0 0 0 0 1
0 0 0 1 1 1 1 0
The visited order is:

-> 1 -> 2 -> 4 -> 8 -> 5 -> 6 -> 3 -> 7

 P a g e | 84

Ex. No.11(B) BREADTH FIRST SEARCH

DATE:

AIM:
To write a c program to perform breadth first search.
ALGORITHM:
1 procedure BFS(G, root) is

2 let Q be a queue
3 label root as explored
4 [Link](root)
5 while Q is not empty do
6 v := [Link]()
7 if v is the goal then
8 return v
9 for all edges from v to w in [Link](v) do
10 if w is not labeled as explored then
11 label w as explored
12 [Link](w)

PROGRAM:
#include<stdio.h>
#include<conio.h>
void bfs(int v);
int adj[10][10],n;
void main()
{
int i,j,v=1;
clrscr();
printf(" BREADTH FIRST SEARCH\n\n");
printf("\nenter the number of nodes");
scanf("%d",&n);
printf("enter the adjacency matrix");
for(i=1;i<=n;i++)
{
 P a g e | 85

for(j=1;j<=n;j++)
{
printf(“\nadj[%d][%d]”,i,j);
scanf("%d",&adj[i][j]);
}
}
printf("\nthe visited nodes are:");
printf("%d-->",v);
bfs(v);
getch();
}
void bfs(int v)
{
int u,w ,q[10],i,vis[10],front=0,rear=0;
for(i=1;i<=n;i++)
{
vis[i]=0;
}
vis[v]=1;
u=v;
while(v<=n)
{
front=0;
rear=0;
for(i=1;i<=n;i++)
{
q[i]=0;
}
for(w=1;w<=n;w++)
{
if(adj[v][w]==1)
{
if(vis[w]==0)
{
 P a g e | 86

front=front+1;
q[front]=w;
vis[w]=1;
}
}
}
if(rear==0&&front==0)
{
return;
}
else
{
while(rear<front)
{
rear=rear+1;
u=q[rear];
printf("-->%d",u);
}
}
v++;
}
}

SAMPLE INPUT/OUTPUT:

BREADTH FIRST SEARCH

Enter the number of nodes: 8

Enter the adjacency matrix:
Enter 9999 for infinity:

0 1 1 9999 9999 9999 9999 9999

1 0 9999 1 1 9999 9999 9999
1 9999 0 9999 9999 1 1 9999
9999 1 9999 0 9999 9999 9999 1
9999 1 9999 9999 0 9999 9999 1
9999 9999 1 9999 9999 0 9999 1
9999 9999 1 9999 9999 9999 0 1.
9999 9999 9999 1 1 1 1 0
 P a g e | 87

The visited nodes are:

1
2
3
4
5
6
7
8

Criteria Maximum Marks

Marks Obtained
Aim and Algorithm 05
Program and Output 15
Viva 05
Total 25

RESULT:
Thus the C Program for depth first search and breadth first search was verified and
executed esuccessfully.