Find Indices of Pair of Elements Whose Sum Is Equal To Target

DEPARTMENT OF EC 23CSR205 DATA STRUCTURES AND ALGORITHMS LABORATORY
Ex no: 1.1(a)
Find Indices of Pair of Elements whose Sum is equal to Target
Date:
AIM:
To write a C-program for find the target and return the index value, otherwise return -1.
PSEUDOCODE:
BEGIN
for(i=0;i<=n-2;i++)
for(j=i+1;j<=n-1;j++)
if(arr[i]+arr[j]==target)
return i,j
f=0
END
SOURCE CODE:
#include<stdio.h>
int main()
{
int n,target=13;
int i,j;
int f=1;
printf("Enter the size of array :");
scanf("%d",&n);
int arr[n];
printf("Enter the array elements:");
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
for(i=0;i<=n-2;i++)
{
for(j=i+1;j<=n-1;j++)
{
if(arr[i]+arr[j]==target)
{
printf("%d %d",i,j);
f=0;
}
}}
if(f)
printf("-1");
return 0;
Register No:717823L149
OUTPUT:
RESULT:
Thus the program for finding the target in the array is executed successfully and the output is
verified.
2 Register No:717823L160
Ex no: 1.1(b)
Remove Duplicates in an Array
Date:
AIM:
To write a C-program for remove the duplicates and return the -1 at end.
PSEUDOCODE:
BEGIN
//n=k;
for i=1 to k-1
if(arr[i]==arr[i-1])
for j=i+1 to j<k
arr[j-1]=arr[j];
arr[j-1]=-1;
k--;
i--;
END
SOURCE CODE:
#include<stdio.h>
int main()
{
int n,i,j;
printf("Enter array size: ");
scanf("%d",&n);
int k=n,arr[n];
printf("Enter array elements:
"); for(i=0;i<=n-1;i++)
{
scanf("%d",&arr[i]);
}
for(i=0;i<k;i++)
{
if(arr[i]==arr[i-1])
{
for(j=i+1;j<k;j++)
{
arr[j-1]=arr[j];
}
arr[j-1]=-1;
k--;
i--;
}
}
3
Register No:717823L160
for(i=0;i<=n-1;i++)
{
printf("%d",arr[i]);
}
printf("\n k:%d",k);
return 0;
}
OUTPUT:
RESULT:
Thus the program for remove the duplicate in array is executed successfully and the output is
verified.
Ex no: 1.1(c)
Date:
Find the Maximum Streak Count of Players
AIM:
To write a C-program for find who is winner, Addy or Om
PSEUDOCODE:
BEGIN
//input
omtemp=0,addytemp=0,ommax=0,addymax=0;
while(t--)
for(i=0;i<n;i++)
if(om[i]>0)
omtemp++;
if(omtemp>ommax)
ommax=omtemp;
END
SOURCE CODE:
#include<stdio.h>
int main()
{
int t;
printf("Enter the number of test case: ");
scanf("%d",&t);
while(t--)
{
int n,i;
printf("Enter the number of days:");
scanf("%d",&n);
int om[n],addy[n],omtemp=0,ommax=0,adtemp=0,admax=0;
printf("Enter om's scores:");
for(i=0;i<n;i++)
{
scanf("%d",&om[i]);
if(om[i]>0)
{
omtemp++;
if(omtemp>ommax)
ommax=omtemp;
}
els
e
omtemp=0;
}
printf("Enter addys's scores: ");
for(i=0;i<n;i++)
{
scanf("%d",&addy[i]);
if(addy[i]>0)
{
adtemp++;
if(adtemp>admax)
admax=adtemp;
}
else
adtemp=0;
}
if(ommax>admax)
printf("Om has the maximum streak count\n");
else if(admax>ommax)
printf("Addy has te maximum streak count\n");
else
printf("Draw\n");
}
return 0;
}
OUTPUT:
RESULT:
Thus the program is executed successfully and the output is verified.
PREPARATION 30
LAB PERFORMANCE 30
REPORT 40
TOTAL 100
INITIAL OF FACULTY
Ex no: 1.2(a)
Date:
Reverse the Singly Linked List
AIM:
To write a C-program for reverse the single linked list.
PSEUDOCODE:
BEGIN
struct node *prev = NULL
struct node *curr = head
while(curr != NULL)
struct node *forward = curr-
>next curr->next = prev
prev = curr
curr=forward
head = prev
END
SOURCE CODE:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head = NULL, *tail = NULL, *newnode = NULL, *temp = NULL;
void InsertAtEnd(int Element)

{
newnode = (struct node*)malloc(sizeof(struct
node)); newnode->data = Element;
newnode->next = NULL;
if(head == NULL)
{
head = newnode;
tail = newnode;
}
else
{
tail->next = newnode;
tail = newnode;
}
}
void Display()
{
if(head == NULL)
printf("List is Empty\n");
else
{
printf("Linked List of elements : \n");
temp = head;
while(temp != NULL)
{
printf("%d\n", temp->data);
temp = temp->next;
}
}
}
void ReverseLL()
{
struct node *prev = NULL;
struct node *curr = head;
while(curr != NULL)
{
struct node *forward = curr-
>next; curr->next = prev;
prev = curr;
curr =
forward;
}
head = prev;
}
int main()
{
int choice, ele, flg=1;
while(flg)
{
printf("1. Insert 2. Reverse 3. Display \n");
printf("Enter the choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter the element : ");
scanf("%d", &ele);
InsertAtEnd(ele);
break;
case 2:
ReverseLL();
break;
case 3:
Display();
break;
default:
printf("Invalid choice");
flg=0;
break;
}
}
}
OUTPUT:
RESULT:
Thus the program for reversing the single linked list is executed successfully and the output is verified.
Ex no: 1.2(b)
Date:
Detect Cycle in a Singly Linked List
AIM:
To write a C-program to determine whether the given linked list has cycle or not.
PSEUDOCODE:
BEGIN
struct node *fast = head;
struct node *slow = head;
while(fast != NULL && fast ->next != NULL)
fast = fast->next->next
slow = slow->next
if(fast == slow)
return 1
END
SOURCE CODE:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head = NULL,
*tail = NULL, *newnode =
NULL, *temp = NULL;
void InsertAtEnd(int
Element)
{
newnode = (struct
node*)malloc(sizeof(struct
node));
newnode->data = Element;
newnode->next = NULL;
if(head == NULL)
{
head = newnode;
tail = newnode;
}
else
{
tail = newnode;
}
}
void FormCycleLL()
{
temp=head->next;
tail->next = temp;
}
int DetectCycleLL()
{
struct node *fast = head;
struct node *slow = head;
while(fast != NULL
&& fast ->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
return 1;
}
return 0;
}
int main()
{
result; int choice, ele, flg=1,
while(flg)
{
printf("1. Insert 2.
FormCycle 3. DetectCycle
\n");
printf("Enter the choice : ");
switch(choice)
{
case 1:
scanf("%d", &ele);
InsertAtEnd(ele);
break;
case 2:
FormCycleLL();
break;
case 3:
result=DetectCycleLL();
if(result == 1) printf("true\
n");
else printf("false\
n"); break;
default:
printf("Invalid choice");
flg=0;
break;
}
}
}
OUTPUT:
RESULT:
Thus the program for to determine whether the given linked list has cycle or not is executed successfully
and the output is verified.
Ex no: 1.2(C)
Date:
Implementation of Circular Doubly Linked List
AIM:
To Write a C program to implement the following operations on a Circular Doubly Linked List.
(1) InsertionAtBegin() (2) InsertionAtEnd() (3) InsertionAtPosition() (4) DeletionAtBegin()
(5) DeletionAtEnd() (6) DeletionAtPosition() (7) Display
PSEUDOCODE:
BEGIN
InsertAtBegin
BEGIN
newnode=(struct node*)malloc(sizeof(struct
node)) newnode->data=Element
newnode->next=NULL
newnode->prev=NULL
if(head == NULL)
BEGIN
head = newnode
tail = newnode
head->prev=tail
tail->next=head
END
else
BEGIN
newnode->next=head;
head->prev=newnode;
head=newnode;
head->prev=tail;
tail->next=head;
END
END
InsertAtEnd
BEGIN
newnode=(struct node*)malloc(sizeof(struct node));

newnode->data=Element;
newnode->next=NULL;
newnode->prev=NULL;
if(head == NULL)
BEGIN
head =
newnode; tail =
newnode; head-
>prev=tail; tail-
>next=head;
END
else
BEGIN
newnode->prev=tail;
tail=newnode;
tail->next=head;
head->prev=tail;
END
END
InsertAtPosition
BEGIN
int pos,i;
newnode->data=Element;
newnode->next=NULL;
newnode->prev=NULL;
if(head==NULL)
BEGIN
head=newnode;
tail=newnode;
head->prev=tail;
tail->next=head;
END
else
BEGIN
temp = head;
printf("Position :");
scanf("%d",&pos);
for(i=1;i<pos-1;i++)
BEGIN
temp=temp->next;
END
E p;
N temp->next=newnode;
D newnode->next->prev=newnode;
n END
e
w
n
o
d
e
-
>
n
e
x
t
=
t
e
m
p
-
>
n
e
x
t
;
n
e
w
n
o
d
e
-
>
p
r
e
v
=
t
e
m
void DeletionAtBegin()
BEGIN
if(head==NULL)
BEGIN
printf("List is empty");
END
else
BEGIN
printf("Deleted Node:%d",head->data);
delnode=head;
head=head->next;
head->prev=tail;
tail->next=head;
delnode->prev=delnode->next=NULL;
free(delnode);
END
END
void DeletionAtEnd()
BEGIN
if(head==NULL)
BEGIN
printf("The list is empty ");
END
else
BEGIN
printf("Deleted Node:%d",tail->data); \
delnode = tail;
\tail=tail->prev;
tail->next=head;
head->prev=tail;
delnode->prev=NULL;
delnode->next=NULL;
free(delnode);
END
END
DeletionAtPosition
BEGIN
int pos,i;
if(head == NULL)
BEGIN
printf("Cannot delete");
END
else
BEGIN
temp=head;
printf("Enter the position :");
scanf("%d",&pos);
BEGIN
temp=temp->next;
END
delnode=temp->next;
printf("Deleted Node:%d",delnode->data);
temp->next = delnode->next;
delnode->next->prev=temp;
delnode->next=NULL;
delnode->prev=NULL;
free(delnode);
END
END
void Display()
BEGIN
if(head==NULL)
BEGIN
END
else
BEGIN
printf("\nLinked List:");
do
BEGIN
printf("%d\n",temp->data);
temp=temp->next;
ENDwhile(temp!=head);
END
SOURCE CODE:
#include<stdio.h>
#include<stdlib.>
struct node
{ struct node
*prev; int data;
struct node *next;
};
struct node *head=NULL,*tail=NULL,*temp=NULL,*delnode=NULL,*newnode=NULL;
void InsertAtBegin(int Element)
{
node)); newnode->data=Element;
newnode->next=NULL;
newnode->prev=NULL;
if(head == NULL)
{
head = newnode;
tail = newnode;
head->prev=tail;
tail->next=head;
}
else
{
newnode->next=head;
head->prev=newnode;
head=newnode;
head->prev=tail;
tail->next=head;
}
}
void InsertAtEnd(int Element)
{
newnode->data=Element; newnode->next=NULL;
newnode->prev=NULL;
if(head == NULL)
{
head = newnode;
tail = newnode;
head->prev=tail;
tail->next=head;
}
else
{
newnode->prev=tail;
tail=newnode;
tail->next=head;
head->prev=tail;
}
}
void InsertAtPosition(int Element)

{
int pos,i;
node)); newnode->data=Element;
newnode->next=NULL;
newnode->prev=NULL;
if(head==NULL)
{
head=newnode;
tail=newnode;
head->prev=tail;
tail->next=head;
}
else
{
temp = head;
printf("Position :");
scanf("%d",&pos);
{
temp=temp->next;
}
newnode->next=temp->next;
newnode->prev=temp;
temp->next=newnode;
newnode->next->prev=newnode;
}
}
void DeletionAtBegin()
{
if(head==NULL)
{
}
else
{
printf("Deleted Node:%d",head->data);
delnode=head;
head=head->next;
head->prev=tail;
tail->next=head;
delnode->prev=NULL;
delnode->next=NULL;
free(delnode);
}
}
void DeletionAtEnd()
{
if(head==NULL)
{
printf("The list is empty ");
}
else
{
printf("Deleted Node:%d",tail->data);
delnode = tail;
tail=tail->prev;
tail->next=head;
head->prev=tail;
delnode->prev=NULL;
delnode->next=NULL;
free(delnode);
}
}
void DeletionAtPosition()
{
int pos,i;
if(head ==NULL)
{
printf("Cannot delete");
}
else
{
temp=head;
printf("Enter the position :");
scanf("%d",&pos);
{
temp=temp->next;
}
delnode=temp->next;
printf("Deleted Node:%d",delnode->data);
temp->next = delnode->next;
delnode->next->prev=temp;
delnode->next=NULL;
delnode->prev=NULL;
free(delnode);
}
}
voidDisplay()
{
if(head==NULL)
{
}
else
{
printf("\nLinked List:");
do{
printf("%d\n",temp->data);
temp=temp->next;
}
while(temp!=head);
}
printf(" %d",tail->data);
printf(" %d",head->data);
}
Intmain()
{
int choice,ele,flag=1;
while(flag)
{
printf("\n1.Insert at begin\n2.Insert at position\n3.Insert at end\n4.delete at
begin\n5.delete at position\n6.delete at end\n7.display\n");
switch(choice)
{
case 1:
printf("Enter the elements to be inserted at the begin :");
scanf("%d",&ele);
InsertAtBegin(ele);
break;
case 2:
printf("Enter the elements to be inserted at the position :");
scanf("%d",&ele);
InsertAtPosition(ele);
break;
case 3:
printf("Enter the elements to be inserted at the end:");

scanf("%d",&ele);
InsertAtEnd(ele);
break;
case 4:
DeletionAtBegin();
break;
case 5:
DeletionAtPosition();
break;
case 6:
DeletionAtEnd();
break;
case 7:
Display();
break;
default:
printf("Invalid Input ");
flag=0;
break;
}
}
}
OUTPUT:
RESULT:
Thus the program for (1) InsertionAtBegin() (2) InsertionAtEnd() (3) InsertionAtPosition()
(4)DeletionAtBegin() (5) DeletionAtEnd() (6) DeletionAtPosition() (7) Display in Circular Doubly
Linked List is executed successfully and the output is verified
DEPARTMENT OF EC 23CSR205-DATA STRUCTURES AND ALGORITHM LABORATORY
Exp. No : 2.1 (a)

BALANCING SYMBOLS
Date :
AIM:
To write a C-program for the balancing symbols.
PSEUDOCODE:
BEGIN
void push(char
element) if(top==size-
1)
printf("Stack is full.Overflow\n");
else
stack[++top]=element;
char pop()
char value;
if(top==-1)
printf("Stack is empty.Underflow\n");
else
value=stack[top];
top=top-1;
return value;
int BalancingSymbols(char input[])
int len=strlen(input),i;
char value,temp;
for(i=0;i<=len-1;i++)
if(input[i]=='{'||input[i]=='['||input[i]=='(')
push(input[i]);
else
if(top==-1)
return 0;
value=pop();
switch(input[i])
case'}':
temp='{';
break;
case']':
temp='[';
break;
case')':
temp='(';
break;
if(value!=temp)
return 0;
if(top==-1)
return 1;
else
return 0;
717823L328
void main()
char
input[size]; int
result;
printf("Enter the expression of symbols:");
scanf("%s\n",input);
result=BalancingSymbols(input);
if(result==1)
printf("Expression %s is valid\n",input);
else
printf("Expression %s is not valid\n",input);
END
SOURCE CODE:
#include <stdio.h>
#include<string.h>
#define size 20
int top=-1;
char stack[size];
void push(char element)
{
if(top==size-1)
printf("Stack is full");
else
{
stack[top]=element;
top=top++;
}
}
char pop()
{
char value;
if(top==-1)
printf("stack is empty");
else
{
value=stack[top];
top=top-1;
return value;
}
}
int balancing_symbols(char input[])
{
int
len=strlen(input),i;
char value,temp;
{
if(input[i]=='{'||input[i]=='['||input[i]=='(')
push(input[i]);
else
{
if(top==-1)
return 0;
717823L328
value=pop();
switch(input[i])
717823L328
{
case'}':
temp='{';
break;
case']':
temp='[';
break;
case')':
temp='(';
break;
}
if(value!=temp)
return 0;
}
}
if(top==-1)
return 1;
else
return 0;
}
int main()
{
char input[size];
int result;
int t;
printf("Enter testcase:");
scanf("%d",&t);
while(t--)
{
printf("Enter the symbols: ");
scanf("%s", input);
result=balancing_symbols(input);
if(result-1)
printf("it is a valid expression\n");
else
{
printf("it is a invalid expression\n");
}
}
}
717823L328
OUTPUT:
RESULT:
Thus the program for the balancing symbol is executed successfully and the output
is verified.
717823L328
Exp. No : 2.1 (b) CONVERSION OF INFIX TO POSTFIX EXPRESSION
Date :
AIM:
To write a C-program for the conversion of infix to postfix expression.
PSEUDOCODE:
BEGIN
void push(char
1)
else
char pop()
char value;
if(top==-1)
else
value=stack[top];
top=top-1;
return value;
int Isoperator(char op)
switch(op)
case '+':
case '-':
case '*':
case '/':
case '^':
case '(':
case ')':
return 1;
default:
return 0;
int Preceedence(char op)
switch(op)
case'+':
case'-':
return 1;
case'*':
case'/':
return 2;
case'^':
return 3;
default:
return 0
int InfixtoPostfixconversion(char input[])
char postfix[size],symbol;
717823L328
int len=strlen(input),i,j=0;
717823L328
symbol=input[i];
if(Isoperator(symbol))
if(symbol=='(')
Push(symbol);
else
if(symbol==')')
while(stack[top]!='(')
postfix[j++]=Pop();
Pop();
else
while(top!=-1&&Preceedence(symbol)<=Preceedence(stack[top])) postfix[j+
+]=Pop();
Push(symbol);
else
postfix[j++]=symbol
while(top!=-1) postfix[j+
+]=Pop(); postfix[j]='\0';
printf("Converted Infix (%s) to Postfix expression is %s\n",input,postfix);
void main()
char infixexp[size];
printf("Enter the infix expression:");
scanf("%s",infixexp);
InfixtoPostfixconversion(infixexp);
END
SOURCE CODE:
#include<stdio.h>
#include<string.h>
#define size 20
char stack[size];
int top=-1;
{
if(top==size-1)
printf("stack is full,overflow");
else {
}
}
int pop()
{
int value;
if(top==-1)
printf("stack is empty,underflow");
else{
value=stack[top--];
return value;
}
}
int is_operator(char op)
717823L328
{
switch(op)
{
case '+':
case '-':
case '/':
case '*':
case '^':
case '(':
case ')':
return 1;
default:
return 0;
}
}
int precedence(char op)
{
switch(op)
{
case '+':
case '-':
return 1;
break;
case '/':
case '*':
return 2;
break;
case '^':
return 3;
break;
default:
return 0;
break;
}
}
void infix_to_postfix(char input[])
{
char postfix[size],symbol;
int
i,j=0,length=strlen(input);
for(i=0;i<length;i++)
{
symbol=input[i];
if(is_operator(symbol))
{
if(symbol=='(')
push(symbol);
else{ if(symbol
==')')
{
while(stack[top]!='(')
postfix[j++]=pop();
pop();
}
717823L328
else{
717823L328
while(top!=-1&&precedence(symbol)<=precedence(stack[top])) postfix[j+
+]=pop();
push(symbol);
}
}
}
else
postfix[j++]=symbol;
}
while(top!=-1)
postfix[j++]=pop();
postfix[j]='\0'; printf("converted infix to postfix expression is %s\n",postfix);
}
int main()
{
char infixexp[size]; int t;
printf("enter no of testcase:");
scanf("%d",&t);
while(t--)
{ printf("enter infix expression:");
scanf("%s",infixexp);
infix_to_postfix(infixexp);
}
}
OUTPUT:
RESULT:
Thus the program for the conversion of infix to postfix expression is executed
successfully and the output is verified.
717823L328
Exp. No : 2.1(c) EVALUATION OF POSTFIX EXPRESSION
Date :
AIM:
To write a C-program for the evaluation of postfix expression
PSEUDOCODE:
void Push(char
1)
else
char Pop()
char value;
if(top==-1)
else
value=stack[top];
top=top-1;
return value;
int Postfixexpeval(char postfixexp[])
int
len=strlen(postfixexp),i,operand1,operand2,value;
if(postfixexp[i]=='+'||postfixexp[i]=='-'||postfixexp[i]=='*'||postfixexp[i]=='/')
operand2=Pop();
operand1=Pop();
switch(postfixexp[i])
case'+':
value=operand1+operand2;
break;
case'-':
value=operand1-operand2;
break;
case'*':
value=operand1*operand2;
break;
case'/':
value=operand1/operand2;
break;
Push(value);
else
Push(postfixexp[i]-48);
return Pop();
void main()
717823L328
char postfixexp[size];
int result;
printf("Enter the postfix expression:");
717823L328
scanf("%s",postfixexp);
result=Postfixexpeval(postfixexp);
printf("Result of postfix expression:%d\n",result);
SOURCE CODE:
#include<stdio.h>
#include<string.h>
#define size 20
char stack[size];
int top=-1;
{
if(top==size-1)
printf("stack is full,overflow");
else {
}
}
int pop()
{
int value;
if(top==-1)
printf("stack is empty,underflow");
else
{
value=stack[top--];
return value;
}
}
int postfix_exp_eval(char postfixexp[])
{
int length=strlen(postfixexp),value,operand1,operand2,i; for(i=0;i<length;i+
+)
{
if(postfixexp[i]=='+'||postfixexp[i]=='-'||postfixexp[i]=='*'||postfixexp[i]=='/')
{
operand1=pop();
operand2=pop();
switch(postfixexp[i])
{
case '+':
value=operand1+operand2;
break;
case '-':
value=operand1-operand2;
break;
case '*':
break;
case '/':
break;
717823L328
}
push(value);
}
else {
push(postfixexp[i]-48);
}
}
return pop();
}
int main()
{
char postfixexp[size];
int t,n,value;
printf("enter no.testcase: ");
scanf("%d",&t);
while(t--)
{
printf("\nenter n:");
scanf("%d",&n);
printf("\nenter postfix expression:");
scanf("%s",postfixexp);
value=postfix_exp_eval(postfixexp);
printf("after evaluation: %d",value);
}
}
OUTPUT:
717823L328
RESULT:
Thus the program for the evaluation of postfix expression is executed
717823L328
717823L328
Electronics and communication engineering 23CSR205 Data Structures
and Algorithms Laboratory
Exp. No : 2.2(a)
IMPLEMENTATION OF LINEAR QUEUE
Date :
AIM:
To wite a C program for the implementation of linear queue using using
Enqueue() , Dequeue() and Display() functions.
PSEUDOCODE:
void enqueue(int element)
{
if(rear==size-1)
printf("queue is full overflow\n");
else
{
if(front==-1&&rear==-1)
front=rear=0;
else
rear=rear+1;
queue[rear]=element;
}
}
int dequeue()
{
int value;
if(front==-1)
printf("queue is empty,underflow\n");
else
{
value=queue[front];
if(front==rear)
{
front=rear=-1;
}
else
front=front+1;
return value;
}
}
void display()
717823L160
{
int i;
if(front==-1)
printf("queue is empty\n");
else
{
printf("element in queue:\n");
for(i=front;i<=rear;i++)
printf("%d\n",queue[i]);
}
}
SOURCE CODE:
#include<stdio.h>
#define size 5
int queue[size],front=-1,rear=-1;
void enqueue(int element)
{
if(rear==size-1)
printf("queue is full overflow\n");
else
{
front=rear=0;
else
rear=rear+1;
}
}
int dequeue()
{
int value;
if(front==-1)
printf("queue is empty,underflow\n");
else
{
value=queue[front];
if(front==rear)
{
front=rear=-1;
}
else
front=front+1;
717823L160
return value;
}
}
void display()
{
int i;
if(front==-1)
else
{
printf("element in queue:\n");
printf("%d\n",queue[i]);
}
}
int main()
{
int i,element,flage=1;
while(flage)
{
printf("1.enqueue(),2.dequeue(),3.display()\n");
printf("enter the choice:");
scanf("%d",&i);
switch(i)
{
case 1:
printf("enter the element:");
scanf("%d",&element);
enqueue(element);
break;
case 2:
printf("the deleted element is: %d\
n",dequeue()); break;
case 3:
display();
break;
default :
printf("invalid choice");
flage=0;
break;
}
717823L160
}
return 0;
}
OUTPUT:
RESULT:
Thus the C program for the implementation of Linear queue is
successfully executed and the output is verified.
717823L160
Exp. No : 2.2(b)
IMPLEMENTATION OF CIRCULAR QUEUE
Date :
AIM:
To wite a C program for the implementation of Circular queue using using Enqueue() ,
Dequeue() , Isfull() , Isempty() and Display() functions.
PSEUDOCODE:
void EnqueueR(int element)
{
if(rear==size-1)
printf("queue is full.overflow\n");
else
{
{
front=0;
rear=0;
}
else
{
rear=rear+1;
}
}
}
int DequeueF()
{
int value;
if(front==-1)
printf("queue is empty.underflow\n");
else
{
value=queue[front];
if(front==rear)
{
front=-1;
717823L160
rear=-1;
}
else
{
front=front+1;
}
return value;
}
}
void EnqueueF(int element)
{
if(front<=0)
printf("insertion not possible at front\n");
else
{
front=front-1;
queue[front]=element;
}
}

{
if(front<=0)
else
{
front=front-1;
}
}
int DequeueR()
{
int value;
if(rear==-1)
else
{
value=queue[rear];
if(front==rear)
{
717823L160
front=-1;
rear=-1;
}
else
{
rear=rear-1;
}
return value;
}
}
SOURCE CODE:
#include<stdio.h>
#define size 6
int queue[size],front=-1,rear=-1;
void EnqueueR(int element)
{
if(rear==size-1)
printf("queue is full.overflow\n");
else
{
{
front=0;
rear=0;
}
else
{
rear=rear+1;
}
}
}
int DequeueF()
{
int value;
if(front==-1)
else
{
value=queue[front];
717823L160
if(front==rear)
{
front=-1;
rear=-1;
}
else
{
front=front+1;
}
return value;
}
}
{
if(front<=0)
else
{
front=front-1;
}
}
int DequeueR()
{
int value;
if(rear==-1)
else
{
value=queue[rear];
if(front==rear)
{
front=-1;
rear=-1;
}
else
{
rear=rear-1;
}
return value;
717823L160
}
}
void display()
{
int i;
if(front==-1)
else
{
printf("elements is queue:\n");
for(i=front;i<=rear;i++) printf("%d\
n",queue[i]);
}
}
int main()
{
int choice,element,value,flag=1;
while(flag)
{
printf("1.enqueue at rear 2.dequeue at front 3.enqueue at front 4.dequeue at rear 5.display \n
enter the choice:");
switch (choice)
{
case 1:
printf("enter the element to be inserted:");
EnqueueR(element);
break;
case 2:
value=DequeueF();
printf("dequeue element:%d\n",value);
break;
case 3:
printf("enter the element to be inserted:");
EnqueueF(element);
break;
case 4:
value=DequeueR();
printf("dequeue element:%d\n",value);
717823L160
break;
case 5:
display();
break;
default:
printf("invalid input\n");
flag=0;
break;
}
}
return 0;
}
OUTPUT:
RESULT:
Thus the C program for the implementation of Circular queue is
successfully executed and the output is verified.
717823L160
ELECTRONICS AND COMMUNICATION ENGINEERING 23CSR205 DATA STRUCTURES AND ALGORITHM LABORATORY
Exp. No : 2.2(c) PRINT STRINGS IN RANDOM USING DOUBLE

ENDED QUEUE
Date :
AIM:
To write a C-program to print strings in random using double ended queue.
PSEUDOCODE:
BEGIN
Void Enqueue F(int element)
if(front<=0)
printf(“Insertion at front impossible.”);
else
front=front-1;
Queue[front]=element;
Void Enqueue R(int element)
if(front==size-1)
printf(“Queue is fu l.Overflow”);
else
front=rear=0;
else
rear=rear+1;
Queue[rear]=element;
int Dequeue F()
int value;
if(front==-
1)
printf(“Queue is empty.Unerflow”);
else
value=Queue[front];
if(front==rear)
front=rear=-
1; else
front=front+1;
return value;
int Dequeue R()
int value;
if(rear==-1)
printf(“Queue is empty.Underflow”);
717823L160
else
717823L160
value=Queue[rear];
if(front==rear)
front=rear=-1;
else
rear=rear-1;
return value;
void Display
int i;
if(front==-1)
printf(“Queue is Empty.Underflow”);
else
printf(“Elements in Queue are”);
printf(“%d”,Queue[i]);
END
SOURCE CODE:
#include<stdio.h>
#include<string.h
> #define size
100
int queue[size],rear=-1,front=-1;
void Enqueue(char ele[])
{
int i,l=strlen(ele);
for(i=0;i<l;i++)
{
if(rear==size-1)
printf("Q ueue is full,overflow");
else
{
if(front==-1&rear==-1){
front=0;
rear=0;
}
else
rear=rear+1;
queue[rear]=ele[i];
}
}
}
void Display(char ele[])
{
int i,r=strlen(ele);
if(front==-1)
printf("Q ueue is empty");
else
{
printf("output string:");
for(i=front;i<r;i++)
717823L160
{
if(i==r-1)
printf("%c",ele[i]);
else
{
printf("%c",ele[i]);
printf("%c",ele[r-1]);
}
r=r-1;
}
printf("\n");
}
}
int main()
{
int flg;
char input[size];
printf("Enter number of times: ");
scanf("%d",&flg);
while(flg--)
{
printf("Enter the string: ");
scanf("%s",input);
Enqueue(input);
Display(input);
}
return 0;
}
OUTPUT:
717823L160
]RESULT:
Thus the program for the implementation of linear queue is executed successfully
and the output is verified.
717823L160
ELECTRONICS AND COMMUNICATION ENGINEERING-B 23CSR205 DATA STRUCTURES AND ALGORITHMS LABORATORY
Exp. No : 3.1 (a) IMPLEMENTATION OF BINARY TREE

Date :
AIM:
To write a C-program for the implementation of binary tree
PSEUDOCODE:
BT* Create()
int
element;
BT *tree;
printf("Enter Data (-1 for no data) : ");
scanf("%d", &element); if(element
== -1) return NULL;
tree = (BT*)malloc(sizeof(BT)); tree->data =

element; printf("Enter the Left Child of %d \n",
element); tree->left = Create(); printf("Enter the Right
Child of %d \n", element); tree->right = Create(); return
tree; void InOrder(BT *tree)
if(tree != NULL)
InOrder(tree->left);
printf("%d\n", tree->data);
InOrder(tree->right);
void PreOrder(BT *tree)
if(tree != NULL) printf("%d\

n", tree->data);
PreOrder(tree->left);
PreOrder(tree->right);
void PostOrder(BT *tree)
if(tree != NULL)
PostOrder(tree-
>left); PostOrder(tree-
>right); printf("%d\n", tree-
>data); void main()
root = Create();
printf("Inorder:\
717823L160
n")
717823L160
;
InOrder(root); root
= Create();
printf("Preorder:\
n"); PreOrder(root);
root = Create();
printf("Postorder:\n");
PostOrder(root);
SOURCE CODE:
#include<stdio.h>
#include<stdlib.h>
struct node
{
struct node *left;
int data;
struct node *right;
}*root = NULL;
typedef struct node BT;
BT* Create()
{
int
element;
BT *tree;
printf("Enter Data (-1 for no data) :
"); scanf("%d", &element);
if(element == -1)
return NULL;
tree = (BT*)malloc(sizeof(BT));
tree->data = element;
printf("Enter the Left Child of %d \n",
element); tree->left = Create();
printf("Enter the Right Child of %d \n",
element); tree->right = Create();
return tree;
}
void InOrder(BT *tree)
{
if(tree != NULL)
{
InOrder(tree->left); printf("%d\n", tree->data); InOrder(tree->right);
}
}
void PreOrder(BT *tree)
{
if(tree != NULL)
{
printf("%d\n", tree->data); PreOrder(tree->left);
PreOrder(tree->right);
}
717823L160
}
void PostOrder(BT *tree)
717823L160
{
if(tree != NULL)
{
PostOrder(tree->left);
PostOrder(tree->right);
printf("%d\n", tree->data);
}
}
void main()
{
root = Create();
printf("Inorder:\
n"); InOrder(root);
root = Create();
printf("Preorder:\
n"); PreOrder(root);
root = Create();
printf("Postorder:\n");
PostOrder(root);
}
OUTPUT
717823L160
RESULT:
Thus the program for the implementation of binary tree is executed successfully and the output
is verified.
717823L160
ELCTRONICS AND COMMUNICATION ENGINEERING 23CSR205 DATA STRUCTURES AND ALGORITHMS LABORATORY
Exp.No:3.1(b) IMPLEMENTATION OF BINARY SEARCH TREE

Date :
AIM:
To write a C-program for the implementation of binary search tree
PSEUDOCODE:
void Inorder(struct node *tree)
if(tree != NULL)
Inorder(tree->LChild);
printf("%d ", tree->data);
Inorder(tree->RChild);
void Preorder(struct node * tree)
if(tree != NULL) printf("%d

", tree->data);
Preorder(tree->LChild);
Preorder(tree->RChild);
void Postorder(struct node * tree)
if(tree!= NULL)
Postorder(tree->LChild);
Postorder(tree->RChild);
int HeightofNode(struct node *tree)
int lh, rh; if(tree

== NULL)
return -1;
else lh = HeightofNode(tree->LChild); rh
= HeightofNode(tree->RChild);
if(lh > rh) return lh+1;
else return rh+1;
struct node* Insert(struct node *tree, int element)

if(tree == NULL) tree = (struct
node*)malloc(sizeof(struct node)); tree->data =
element; tree->LChild = NULL;
tree->RChild = NULL;
else if(element < tree->data) tree->LChild =
717823L160
Insert(tree->LChild, element);
else if(element > tree->data) tree->RChild =
Insert(tree->RChild, element);
else printf("Element %d already exists\n", element);
return tree; struct node*
FindMin(struct node *tree)
if(tree == NULL)
return 0;
else if(tree->LChild != NULL) return
FindMin(tree->LChild);
else return tree;
struct node* FindMax(struct node *tree)
if(tree == NULL)
return 0;
else if(tree->RChild != NULL) return
FindMax(tree->RChild);
else return tree;
int Search(struct node *tree, int key)
if(tree == NULL)
return 0;
else if(key < tree->data) return
Search(tree->LChild, key);
else if(key > tree->data) return
Search(tree->RChild, key);
else return 1;
int DepthofNode(struct node *tree, int key)
if(tree == NULL)
return -1;
else if(key < tree->data) return 1+
DepthofNode(tree->LChild,
key); else if(key > tree->data)
return 1+
DepthofNode(tree->RChild, key);
else return
0; void main()
int choice, element, flag=1, res;

struct node *root = NULL, *temp =
NULL;
while(flag) printf("1. Insertion 2. FindMin 3. FindMax 4. Search 5. DepthofNode 6.
HeightofNode 7. Inorder Traversal 8. Preorder Traversal 9. Postorder Traversal \n Enter the
717823L160
choice
: "); scanf("%d", &choice);
switch(choice)
case 1:
printf("Enter the element to be
inserted : "); scanf("%d", &element); root
= Insert(root, element); break;
case 2:
temp = FindMin(root); printf("Minimum Element
in BST is %d\n", temp->data); break;
case 3:
temp = FindMax(root); printf("Maximum
Element in BST is %d\n", temp->data); break;
case 4:
printf("Enter the element to be searched : ");
scanf("%d", &element);
res = Search(root, element);
if(res)
printf("Element %d Found in BST\n",
element); else printf("Element %d Not Found in
BST\n", element); break;
case 5:
scanf("%d", &element); res =
DepthofNode(root, element); printf("Depth
of %d is %d\n", element, res); break;
case 6:
res = HeightofNode(root);
printf("Height of %d is %d\n", root->data,
res); break;
case 7:
printf("Inorder Traversal:\n");
Inorder(ro
ot); printf("\n");
break;
case 8:
printf("Preorder Traversal:\n");
Preorder(r
oot); printf("\n");
break;
case 9:
printf("Postorder Traversal:\n");
Postord er(root);
printf("\n");
break; default:
printf("Invalid Input\n"); flag=0; break;
SOURCE CODE:
717823L160
#include <stdio.h>
#include
<stdlib.h> struct
node
{
struct node
*LChild; int data;
struct node *RChild;
};
void Inorder(struct node *tree)

{
if(tree != NULL)
{
Inorder(tree->LChild);
printf("%d ", tree-
>data); Inorder(tree-
>RChild);
}
}
void Preorder(struct node * tree)

{
if(tree != NULL)
{
Preorder(tree->LChild);
Preorder(tree->RChild);
}
}
void Postorder(struct node * tree)

{
if(tree!= NULL)
{
Postorder(tree->LChild);
Postorder(tree->RChild);
printf("%d ", tree-
>data);
}
}
int HeightofNode(struct node *tree)

{
int lh, rh;
if(tree == NULL)
return -1;
else
{
lh = HeightofNode(tree->LChild);
rh = HeightofNode(tree-
>RChild); if(lh > rh)
return lh+1;
else
717823L160
return rh+1;
717823L160
}
}
struct node* Insert(struct node *tree, int element)

{
if(tree == NULL)
{
tree = (struct
node*)malloc(sizeof(struct node));
tree->data = element;
tree->LChild =
NULL; tree->RChild
= NULL;
}
else
{
if(element < tree->data)
tree->LChild =
Insert(tree->LChild, element);
else if(element > tree-
>data) tree->RChild
=
Insert(tree->RChild, element);
else
printf("Element %d already
exists\n", element);
}
return tree;
}
struct node* FindMin(struct node *tree)

{
if(tree == NULL)
return 0;
else
{
if(tree->LChild != NULL)
return FindMin(tree->LChild);
else
return tree;
}
}
struct node* FindMax(struct node *tree)

{
if(tree == NULL)
return 0;
else
{
if(tree->RChild != NULL)
return FindMax(tree->RChild);
else }
717823L160
return tree;
717823L160
int Find(struct node *tree, int key)

{
if(tree == NULL)
return 0;
else
{
if(key < tree->data)
return Find(tree->LChild, key);
else if(key > tree->data)
return Find(tree->RChild, key);
else
return 1;
}
}
int DepthofNode(struct node *tree, int key)

{
if(tree == NULL)
return -1;
else
{
if(key < tree->data)
return 1+
DepthofNode(tree->LChild, key);
else if(key > tree->data)
return 1+
DepthofNode(tree->RChild, key);
else
return 0;
}
}
void main()
{
int choice, element, flag=1, res;
struct node *root = NULL, *temp = NULL;
while(flag)
{
printf("1. Insertion 2. FindMin 3.
FindMax 4. Search 5. DepthofNode 6. HeightofNode
7. Inorder Traversal 8. Preorder Traversal 9. Postorder
Traversal \n Enter the choice : ");
scanf("%d", &choice);
switch(choice)
{
case 1:
: ");
inserted scanf("%d", &element);
717823L160
root = Insert(root, element);

break;
case 2:
temp = FindMin(root);
printf("Minimum Element in BST is
%d\n", temp->data);
break;
case 3:
temp = FindMax(root);
printf("Maximum Element in BST is
%d\n", temp->data);
break;
case
4: searched :
"); res = Find(root, element);
if(res)
printf("Element %d Found in BST\n",
else
element); printf("Element %d Not Found in
BST\n", element);
break;
case
5: printf("Enter the element : ");
res = DepthofNode(root, element);
printf("Depth of %d is %d\n", element,
res);
break;
case 6:
res = HeightofNode(root);
printf("Height of %d is %d\n",
root->data, res);
break;
case 7:
printf("Inorder Traversal:\n");
Inorder(root)
; printf("\n");
break;
case 8:
printf("Preorder Traversal:\n");
Preorder(root);
printf("\n");
break;
case 9:
printf("Postorder Traversal:\n");
Postorder(root);
printf("\n");
break;
default:
717823L160
Input\n"); printf("Invalid
flag=0;
} break;
}
}
OUTPUT:
Pu
RESULT:
Thus the program for the implementation of binary search tree is executed
30
PREPARATION
LAB PERFORMANCE 30
REPORT 40
TOTAL 10
0
INITIAL OF FACULTY
717823L160
23CSR205 Data Structures and Algorithms Laboratory
Exp. No :3.2(a)
Date : Count the numbers of nodes in the given range
AIM:
Given a Binary Search Tree (BST) and a range, write a C program to count number of
nodes that lie in the given range.
PSEUDOCODE:
BEGIN
int countInRange(struct Node* root, int low, int high) {

if (root == NULL)
return 0;
if (root->data >= low && root->data <= high)

return 1 + countInRange(root->left, low, high) + countInRange(root->right, low, high);
else if (root->data < low)
return countInRange(root->right, low, high);
else
return countInRange(root->left, low, high);
}
END
SOURCE CODE:
#include <stdio.h>
#include <stdlib.h>
struct Node
{ int data;
struct Node* left;
struct Node* right;
};
struct Node* newNode(int data) {

struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
struct Node* insert(struct Node* root, int data) {

if (root == NULL)
return newNode(data);
if (data < root->data)

root->left = insert(root->left, data);
else if (data > root->data)
root->right = insert(root->right, data);
return root;
}
717823L1
717823L1
int countInRange(struct Node* root, int low, int high) {

if (root == NULL)
return 0;
if (root->data >= low && root->data <= high)

return 1 + countInRange(root->left, low, high) + countInRange(root->right, low,
high); else if (root->data < low)
return countInRange(root->right, low, high);
else
return countInRange(root->left, low, high);
}
int main() {
struct Node* root =
NULL; int choice, value,
low, high;
do {
printf("1. Insert a value\t");
printf("2. Count nodes in range\t");
printf("3. Exit\n");
printf("Enter your choice: ");
switch (choice) {
case 1:
printf("Enter a value to insert:
"); scanf("%d", &value);
root = insert(root, value);
break;
case 2:
printf("Enter the range [low high]: ");
scanf("%d %d", &low, &high);
printf("N umber of nodes in range: %d\n", countInRange(root, low, high));
break;
case 3:
printf("Exiting the program. Goodbye!\n");
break;
default:
printf("Invalid choice. Please try again.\n");
}
} while (choice != 3);
return 0;
}
717823L1
OUTPUT:
RESULT:
Thus the program was successfully executed and the output is verified.
717823L1
Exp. No :3.2 (b)
Date : Sum of leaf nodes
AIM:
Given a binary search tree, write a program to find the sum of all the leaf nodes.
PSEUDOCODE:
BEGIN
int leafSum(struct Node* root) {
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)

return root->data;
return leafSum(root->left) + leafSum(root->right);

}
END
SOURCE CODE:
#include <stdio.h>
#include <stdlib.h>
struct Node
{ int data;
struct Node* left;
struct Node* right;
};
struct Node* newNode(int data) {

struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
struct Node* insert(struct Node* root, int data) {

if (root == NULL)
return newNode(data);
if (data < root->data)

root->left = insert(root->left,
data); else if (data > root->data)
root->right = insert(root->right, data);
return root;
}
717823L1
717823L1
int leafSum(struct Node* root)

{ if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)

return root->data;
return leafSum(root->left) + leafSum(root->right);

}
int main() {
struct Node* root =
NULL; int choice, value;
do {
printf("1. Insert a value\t");
printf("2. Display sum of leaf nodes\t");
printf("3. Exit\n");
printf("Enter your choice: ");
switch (choice) {
case 1:
printf("Enter a value to insert: ");
scanf("%d", &value);
root = insert(root, value);
break;
case 2:
printf("Sum of leaf nodes: %d\n", leafSum(root));
break;
case 3:
printf("Exiting the program. Goodbye!\n");
break;
default:
printf("Invalid choice. Please try again.\n");
}
} while (choice != 3);
return 0;
}
717823L1
OUTPUT:
RESULT:
717823L1
Exp. No :3.2(c)
Date : Heap sort
AIM:
The task is to complete heapify() and buildHeap() functions which are used to implement Heap Sort.
PSEUDOCODE:
BEGIN
void Heapify(int arr[], int n, int s)

{ int i = s, j, t;
while ((2 * i) <= n)
{ j = 2 * i;
if (j < n) {
if (arr[j] < arr[j +
1]) j = j + 1;
}
if (arr[i] < arr[j])
{ t = arr[i];
arr[i] = arr[j];
arr[j] = t;
i = j;
} else
break;
}
}
void Extract_Max(int arr[], int n) {
int i;
for (i = n; i >= 1; i--)
{ int t = arr[1];
arr[1] =
arr[i]; arr[i]
= t;
Heapify(arr, i - 1, 1);
}
}
END
SOURCE CODE:
#include <stdio.h>
void Display(int arr[], int n) {

int i;
for (i = 1; i <= n; i++)
printf("%d ", arr[i]);
}
void Heapify(int arr[], int n, int s)

{ int i = s, j, t;
while ((2 * i) <= n)
{ j = 2 * i;
717823L1
717823L1
if (j < n) {
if (arr[j] < arr[j + 1])
j = j + 1;
}
if (arr[i] < arr[j]) {

t = arr[i];
arr[i] = arr[j];
arr[j] = t;
i = j;
} else
break;
}
}
void Extract_Max(int arr[], int n) {
int i;
for (i = n; i >= 1; i--)
{ int t = arr[1];
arr[1] =
arr[i]; arr[i]
= t;
Heapify(arr, i - 1, 1);
}
}
int main() {
int n, i;
printf("Enter the size of the array: ");
scanf("%d", &n);
int arr[n];
printf("Enter %d elements:\n", n);
for (i = 1; i <= n; i++)
scanf("%d", &arr[i]);
for (i = n / 2; i >= 1; i--)
Heapify(arr, n, i);
Extract_Max(arr, n);
printf("\nThe Final Sorted Array using Binary Heap Sort is:\n");
Display(arr, n);
printf("\n");
return 0;
}
OUTPUT:
717823L1
RESULT:
PREPARATION 30
LAB PERFORMANCE 30
REPORT 40
TOTAL 100
INITIAL OF FACULTY
717823L1
Exp. No : 4.1(a)
Date : Implementation of Breadth First Traversal
AIM:
To Implement the Breadth First Traversal in C Programming.
PSEUDOCODE:
BEGIN
void create_graph(){
int ch, v1, v2;
printf("Enter the no. of vertices:");
scanf("%d", &n);
do{
printf("\nEnter the edges(v1 to v2):");
scanf("%d %d", &v1, &v2);
adj[v1][v2] = 1;
adj[v2][v1] = 1;
printf("enter 1 to add more edges:");
scanf("%d", &ch);
}while(ch == 1);
}
void display(){
int i, j;
printf("\nAdjacacency Matrix");
printf("\nVERTEX");
for(i = 1; i <= n; i++)
printf("\tV%d", i);
for(i = 1;i <= n; i++){
printf("\nV%d", i);
for(j = 1; j <= n; j++){
printf("\t%d", adj[i][j]);
}
}
}
void bfs(int v){

int k, w; printf("V
%d-", v);
visited[v] = 1;
enqueue(v);
while(front != -1)
{
k = dequeue();
for(w = 1; w <= n; w++){ if(adj[k]
[w] == 1){
if(visited[w] == 0){
printf("V%d-", w);
visited[w] = 1;
enqueue(w);
}
}
}}}
717823L333
717823L333
void enqueue(int s){

if(front == -1)
front++; rear+
+; que[rear] =
s;
}
int dequeue(){
int s;
s = que[front];
if(front == rear){
front = -1;
rear = -1;
}
else front+
+; return s;
}
END
SOURCE CODE:
#include<stdio.h>
#define MAX 15
int n, adj[MAX][MAX],
visited[MAX]; int que[MAX], front = -
1, rear = -1; void create_graph();
void display();
void bfs(int v);
void enqueue(int s);
int dequeue();
void create_graph()
{ int ch, v1, v2;
scanf("%d", &n);
do{
scanf("%d %d", &v1, &v2);
adj[v1][v2] = 1;
adj[v2][v1] = 1;
scanf("%d", &ch);
}while(ch == 1);
}
void display()
{ int i, j;
printf("\nVERTEX");
for(i = 1; i <= n; i++)
printf("\tV%d", i);
for(i = 1;i <= n; i++){
printf("\nV%d", i);
for(j = 1; j <= n; j++){
717823L333
}
}
}
void bfs(int v){

int k, w; printf("V
%d-", v);
visited[v] = 1;
enqueue(v);
while(front != -1)
{
k = dequeue();
for(w = 1; w <= n; w++)
{ if(adj[k][w] == 1){
if(visited[w] == 0)
{ printf("V%d-",
w); visited[w] = 1;
enqueue(w);
}
}
}}}
if(front == -1)
front++; rear+
+; que[rear] =
s;
}
int dequeue(){
int s;
s = que[front];
if(front == rear){
front = -1;
rear = -1;
}
else
front++;
return s;
}
void main()
{
int i;
create_graph();
printf("\nGRAPH SUCCESSFULLY CREATED..\n");
display();
printf("\nBFS TRAVERSAL..\n");
for(i = 1; i <= n; i++){
if(visited[i] == 0)
bfs(i);
}
}
717823L333
OUTPUT:
RESULT:
717823L333
Exp. No : 4.1(b)
Date : Implementation of Depth First Traversal
AIM:
To Implement the Depth First Traversal in C Programming.
PSEUDOCODE:
BEGIN
int ch, v1, v2;
scanf("%d", &n);
do
{
scanf("%d %d", &v1, &v2);
adj[v1][v2] = 1;
adj[v2][v1] = 1;
scanf("%d", &ch);
}while(ch == 1);
}
void dfs(int v){

int w;
printf("V%d-", v);
visited[v] = 1;
for(w = 1; w <= n; w++)
{ if(adj[v][w] == 1){
if(visited[w] == 0)
dfs(w);
}
}
}
void display(){
int i, j;
printf("\nVERTEX");
for(i = 1; i <= n; i++)
printf("\tV%d", i);
for(i = 1;i <= n; i++){
printf("\nV%d", i);
for(j = 1; j <= n; j++){
}
}
}
END
717823L333
717823L333
SOURCE CODE:
#include<stdio.h>
#define MAX 15
int n, adj[MAX][MAX],
visited[MAX]; void create_graph();
void display();
void dfs(int v);
void create_graph()
{ int ch, v1, v2;
scanf("%d", &n);
do
{
scanf("%d %d", &v1, &v2);
adj[v1][v2] = 1;
adj[v2][v1] = 1;
scanf("%d", &ch);
}while(ch == 1);
}
void dfs(int v)
{ int w;
printf("V%d-", v);
visited[v] = 1;
for(w = 1; w <= n; w++){ if(adj[v]
[w] == 1){
if(visited[w] == 0)
dfs(w);
}
}
}
void display(){
int i, j;
printf("\nVERTEX");
for(i = 1; i <= n; i++)
printf("\tV%d", i);
for(i = 1;i <= n; i++){
printf("\nV%d", i);
for(j = 1; j <= n; j++){
}
}
}
void main()
{
int i;
create_graph();
printf("\nGRAPH SUCCESSFULLY CREATED..\n");
717823L333
display();
printf("\nDFS TRAVERSAL..\n");
for(i = 1; i <= n; i++)
{
if(visited[i] == 0)
dfs(i);
}
}
OUTPUT:
717823L333
PREPARATION 30
LAB PERFORMANCE 30
REPORT 40
TOTAL 100
INITIAL OF FACULTY
RESULT:
717823L333
Exp. No : 4.2(a)
Date : Implementation of Topological Sort
AIM:
To Implement the Topological Sort in C Programming
PSEUDOCODE:
BEGIN
int ch, v1, v2;
scanf("%d", &n);
do{
scanf("%d %d", &v1, &v2);
adj[v1][v2] = 1;
scanf("%d", &ch);
}while(ch == 1);
}
void display(){
int i, j;
printf("\nAdjacency Matrix");
printf("\nVERTEX");
for(i = 1; i <= n; i+
+) printf("\tV%d", i);
for(i = 1;i <= n; i++)
{ printf("\nV%d", i);
for(j = 1; j <= n; j++){ printf("\t
%d", adj[i][j]);
}
}
}

if(front == -1)
front++; rear+
+; que[rear] =
s;
}
int dequeue(){
int s;
s = que[front];
if(front == rear)
{ front = -1;
rear = -1;
}
else
front++;
return s;}
int indegree(int v){
717823L333
717823L333
int i, count = 0;
for(i = 1; i <= n; i++)
if(adj[i][v] == 1)
count++;
return count;
}
void topologicalsort(){
int i, j = 1, k, t, topsort[n], indeg[n];
for(i = 1; i <= n; i++){
indeg[i] = indegree(i);
if(indeg[i] == 0)
enqueue(i);
}
while(front != -1)
{
k = dequeue();
topsort[j++] = k; // or printf("%d ", k);
for(i = 1; i <= n; i++){
if(adj[k][i] == 1){
adj[k][i] = 0;
indeg[i] = indeg[i] - 1;
if(indeg[i] == 0)
enqueue(i);
}
}
}
printf("\nTopological Ordering of vertices:\n");
for(i = 1; i <= n; i++)
printf("V%d-", topsort[i]);
printf("\n");
}
END
SOURCE CODE:
#include<stdio.h>
#define MAX 15
int n, adj[MAX][MAX];
int que[MAX], front = -1, rear = -1;
void create_graph();
void display();
void
topologicalsort();
void enqueue(int s);
int dequeue();
int indegree(int v);
int ch, v1, v2;
scanf("%d", &n);
do{
717823L333

scanf("%d %d", &v1, &v2);
adj[v1][v2] = 1;
scanf("%d", &ch);
}while(ch == 1);
}
void display(){
int i, j;
printf("\nAdjacency Matrix");
printf("\nVERTEX");
for(i = 1; i <= n; i+
+) printf("\tV%d", i);
for(i = 1;i <= n; i++)
{ printf("\nV%d", i);
for(j = 1; j <= n; j++)
{ printf("\t%d", adj[i]
[j]);
}
}
}

if(front == -1)
front++; rear+
+; que[rear] =
s;
}
int dequeue(){
int s;
s = que[front];
if(front == rear)
{ front = -1;
rear = -1;
}
else
front++;
return s;}
int indegree(int v){
int i, count = 0;
for(i = 1; i <= n; i++)
if(adj[i][v] == 1)
count++;
return count;
}
void topologicalsort(){
int i, j = 1, k, t, topsort[n], indeg[n];
for(i = 1; i <= n; i++){
indeg[i] = indegree(i);
if(indeg[i] == 0)
enqueue(i);
}
while(front != -1)
717823L333
{
k = dequeue();
topsort[j++] = k; // or printf("%d ", k);
for(i = 1; i <= n; i++){
if(adj[k][i] == 1){
adj[k][i] = 0;
indeg[i] = indeg[i] - 1;
if(indeg[i] == 0)
enqueue(i);
}
}
}
printf("\nTopological Ordering of vertices:\n");
for(i = 1; i <= n; i++)
printf("V%d-", topsort[i]);
printf("\n");
}
void main()
{
create_graph();
display();
topologicalsort();
}
OUTPUT:
717823L333
RESULT:
717823L333
Exp. No : 4.2(b)
Date : Implementation of Kruskal’s Minimum Spanning Tree
AIM:
To Implement the Kruskal’s Minimum Spanning Tree in C Programming
PSEUDOCODE:
BEGIN
int find(int i){

while(parent[i])
i = parent[i];
return i;
}
int uni(int i, int j)

{ if(i != j){
parent[j] = i;
return 1;
}
return 0;
}
END
SOURCE CODE:
#include<stdio.h>
#define MAX 15
int parent[MAX];
int find(int i){

while(parent[i])
i = parent[i];
return i;
}
int uni(int i, int j)

{ if(i != j){
parent[j] = i;
return 1;
}
return 0;
}
void main()
{
int n, cost[MAX][MAX], a, b, u, v, i, j, ne = 1, min, mincost = 0;
printf("Enter the number of nodes:");
scanf("%d",&n);
printf("Enter the adjacency matrix:\n");
717823L333
717823L333
for(i = 1; i <= n; i++){

for(j = 1; j <= n; j++){
scanf("%d", &cost[i][j]);
if(cost[i][j] == 0)
cost[i][j] = 999;
}
}
while(ne < n)
{ min = 999;
for(i = 1 ; i <= n; i++)
{ for(j = 1; j <= n; j++)
{
if(cost[i][j] < min){
min = cost[i][j];
a = i;
b = j;
}
}
}
u = find(a);
v = find(b);
if(uni(u, v)){
printf("Edge %d:(%d %d) cost:%d\n", ne++, a, b,
min); mincost += min;
}
cost[a][b] = cost[b][a] = 999;
}
printf("Minimum cost = %d\n", mincost);
}
OUTPUT:
717823L333
PREPARATION 30
LAB PERFORMANCE 30
REPORT 40
TOTAL 100
INITIAL OF FACULTY
RESULT:
717823L333
Exp. No : 5.1(a)
Date : Implementation of Bubble Sort
AIM:
To Implement the Bubble Sort in C Programming
PSEUDOCODE:
BEGIN
void BubbleSort(int n, int arr[])

{ int i, j, temp;
for(i=0; i<n-1; i++){
for(j=0; j<n-i-1; j++){
if(arr[j] > arr[j+1])
{ temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
END
SOURCE CODE:
#include<stdio.h>
void BubbleSort(int n, int arr[])
{ int i, j, temp;
for(i=0; i<n-1; i++){
for(j=0; j<n-i-1; j++){
if(arr[j] > arr[j+1])
{ temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
void main(){
int n;
printf("Enter the value of n : ");
scanf("%d", &n);
int arr[n], i;
printf("Enter the array elements : \n");
for(i=0; i<n; i++)
printf("Array before Sorting : \n");
717823L333
717823L333
for(i=0; i<n; i++)

printf("%d\t", arr[i]);
BubbleSort(n, arr);
printf("\nArray after Sorting in Ascending Order : \n");
for(i=0; i<n; i++)
}
OUTPUT:
RESULT:
717823L333
Exp. No : 5.1(b)
Date : Implementation of Insertion Sort
AIM:
To Implement the Insertion Sort in C Programming
PSEUDOCODE:
BEGIN
void InsertionSort(int n, int arr[]){

int i, j, key;
for(i=1; i<n; i++)
{ key = arr[i];
for(j=i-1; j>=0 && arr[j] > key; j--)
{ arr[j+1] = arr[j];
}
arr[j+1] = key;
}
}
END
SOURCE CODE:
#include<stdio.h>
void InsertionSort(int n, int arr[]){
int i, j, key;
for(i=1; i<n; i++)
{ key = arr[i];
for(j=i-1; j>=0 && arr[j] > key; j--)
{ arr[j+1] = arr[j];
}
arr[j+1] = key;
}
}
void main(){
int n;
scanf("%d", &n);
int arr[n], i;
for(i=0; i<n; i++)
for(i=0; i<n; i++)
InsertionSort(n, arr);
717823L333
717823L333

for(i=0; i<n; i++)
}
OUTPUT:
RESULT:
717823L333
Exp. No : 5.1(c)
Date : Implementation of Selection Sort
AIM:
To Implement the Selection Sort in C Programming.
PSEUDOCODE:
BEGIN
void SelectionSort(int n, int arr[])

{ int i, j, min, temp;
for(i=0; i<n-1; i++)
{ min = i;
for(j=i+1; j<n; j++)
{ if(arr[j] <
arr[min])
min = j;
}
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
END
SOURCE CODE:
#include<stdio.h>
void SelectionSort(int n, int arr[])
{ int i, j, min, temp;
for(i=0; i<n-1; i++)
{ min = i;
for(j=i+1; j<n; j++)
{ if(arr[j] <
arr[min])
min = j;
}
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
void main(){
int n;
scanf("%d", &n);
int arr[n], i;
717823L333
717823L333
for(i=0; i<n; i++)

scanf("%d",
&arr[i]);
for(i=0; i<n; i++)
SelectionSort(n, arr);
for(i=0; i<n; i++)
}
OUTPUT:
RESULT:
717823L333
Exp. No : 5.1(d)
Date : Implementation of Merge Sort
AIM:
To Implement the Merge Sort in C Programming.
PSEUDOCODE:
BEGIN
void Merge(int arr[], int low, int mid, int high){

int i=low, j=mid+1, temp[25], k=low;
while(i<=mid && j<=high){
if(arr[i] <= arr[j])
temp[k++] = arr[i++];
else
temp[k++] = arr[j++];
}
while(i<=mid) temp[k+
+] = arr[i++];
while(j<=high)
for(i=low; i<=high; i++)
arr[i] = temp[i];
}
void MergeSort(int arr[], int low, int high)

{ int mid;
if(low < high){
mid = (low+high)/2;
MergeSort(arr, low, mid);
MergeSort(arr, mid+1, high);
Merge(arr, low, mid, high);
}
}
END
SOURCE CODE:
#include<stdio.h>
int i=low, j=mid+1, temp[25], k=low;
while(i<=mid && j<=high){
if(arr[i] <= arr[j])
temp[k++] = arr[i++];
else
}
while(i<=mid) temp[k+
+] = arr[i++];
while(j<=high)
for(i=low; i<=high; i++)
717823L333
717823L333
arr[i] = temp[i];
}
void MergeSort(int arr[], int low, int high){

int mid;
if(low < high){
mid = (low+high)/2;
MergeSort(arr, low, mid);
MergeSort(arr, mid+1, high);
Merge(arr, low, mid, high);
}
}
void main()
{ int n;
scanf("%d", &n);
int arr[n], i;
for(i=0; i<n; i++)
for(i=0; i<n; i++)
MergeSort(arr, 0, n-1);
for(i=0; i<n; i++)
}
OUTPUT:
717823L333
PREPARATION 30
LAB PERFORMANCE 30
REPORT 40
TOTAL 100
INITIAL OF FACULTY
RESULT:
717823L333
Exp. No : 5.2(a)
Date : Implementation of Quick Sort
AIM:
To Implement the Quick Sort in C Programming.
PSEUDOCODE:
BEGIN
int Partition(int arr[], int low, int high)

{ int pivot=low, i=low+1, j=high,
temp; while(1){
while(arr[i] <= arr[pivot] && i<=high)
i++;
while(arr[j] > arr[pivot] &&
j>=low) j--;
if(i < j){
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
else{
temp = arr[j];
arr[j] = arr[pivot];
arr[pivot] = temp;
return j;
}
}
}
void QuickSort(int arr[], int low, int high)

{ int pi;
if(low < high){
pi = Partition(arr, low, high);
QuickSort(arr, low, pi-1);
QuickSort(arr, pi+1, high);
}
}
END
SOURCE CODE:
#include<stdio.h>
int Partition(int arr[], int low, int high){
int pivot=low, i=low+1, j=high, temp;
while(1){
while(arr[i] <= arr[pivot] && i<=high)
i++;
while(arr[j] > arr[pivot] &&
j>=low) j--;
717823L333
717823L333
if(i < j){

temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
else{
temp = arr[j];
arr[j] = arr[pivot];
arr[pivot] = temp;
return j;
}
}
}
void QuickSort(int arr[], int low, int high)

{ int pi;
if(low < high){
pi = Partition(arr, low, high);
QuickSort(arr, low, pi-1);
QuickSort(arr, pi+1, high);
}
}
void main()
{ int n;
scanf("%d", &n);
int arr[n], i;
for(i=0; i<n; i++)
for(i=0; i<n; i++)
QuickSort(arr, 0, n-1);
for(i=0; i<n; i++)
}
717823L333
OUTPUT:
RESULT:
717823L333
Exp. No : 5.2(b)
Date : Search Element Using Binary Search
AIM:
To search of element in binary search tree using C Programming.
PSEUDOCODE:
BEGIN
int BinarySearch_Iter(int low, int high, int arr[], int key){

int mid;
while(low <= high)
{ mid =
(low+high)/2;
if(key == arr[mid])
return mid;
else if(key < arr[mid])
high = mid-1;
else
low = mid+1;
}
return -1;
}
END
SOURCE CODE:
#include<stdio.h>
int BinarySearch_Iter(int low, int high, int arr[], int key){
int mid;
while(low <= high)
{ mid =
(low+high)/2;
if(key == arr[mid])
return mid;
else if(key < arr[mid])
high = mid-1;
else
low = mid+1;
}
return -1;
}
void main()
{
int n, result;
scanf("%d", &n);
int arr[n], i, key;
printf("Enter the array elements(Sorted Array): \n");
for(i=0; i<n; i++)
printf("Enter the element to be searched : ");
717823L333
Exp. No : 5.2(c)
717823L333
scanf("%d", &key);
result = BinarySearch_Iter(0, n-1, arr, key);
if(result == -1)
printf("Element %d does not exist in the given array\n", key);
else
printf("Element %d exists at the index %d \n", key, result);
}
OUTPUT:
RESULT:
717823L333
Date : Implementation of Linear Probing
AIM:
To Implementation of Linear Probing using C Programming.
PSEUDOCODE:
BEGIN
void LinearProbing(int tablesize, int HashTable[])

{ int n, j, element, hashkey, i;
scanf("%d", &n);
for(j=0; j<n; j++){
printf("Enter the element %d : ", j+1);
i=0;
while(1){
hashkey = ((element % tablesize) + i) % tablesize;
if(HashTable[hashkey] == -1){
HashTable[hashkey] = element;
break;
}
else
i++;
}
}
}
END
SOURCE CODE:
#include<stdio.h>
void LinearProbing(int tablesize, int HashTable[])

scanf("%d", &n);
for(j=0; j<n; j++){
i=0;
while(1){
hashkey = ((element % tablesize) + i) % tablesize;
break;
}
else
i++;
}
}
717823L333
void main(){
int tablesize, i;
printf("Enter the TableSize : ");
scanf("%d", &tablesize);
int HashTable[tablesize];
for(i=0; i<tablesize; i++)
HashTable[i] = -1;
LinearProbing(tablesize,
HashTable);
printf("HashTable Contents after Linear Probing: \
n"); printf("Index Value \n");
printf("%d %d\n", i, HashTable[i]);
}
OUTPUT:
RESULT:
717823L333
Exp. No : 5.2(d)
Date : Implementation of Quadratic Probing
AIM:
To Implementation of Quadratic Probing using C Programming.
PSEUDOCODE:
BEGIN
void QuadraticProbing(int tablesize, int HashTable[])

scanf("%d", &n);
for(j=0; j<n; j++){
i=0;
while(1){
hashkey = ((element % tablesize) + (i*i)) % tablesize;
break;
}
else
i++;
}
}
}
END
SOURCE CODE:
#include<stdio.h>
void QuadraticProbing(int tablesize, int HashTable[])

scanf("%d", &n);
for(j=0; j<n; j++){
i=0;
while(1){
hashkey = ((element % tablesize) + (i*i)) % tablesize;
break;
}
else
i++;
717823L333
717823L333
}
}
}
void main(){
int tablesize, i;
HashTable[i] = -1;
QuadraticProbing(tablesize,
HashTable);
printf("HashTable Contents after Quadratic Probing: \
}
OUTPUT:
RESULT:
717823L333
Exp. No : 5.2(e)
Date : Implementation of Double Probing
AIM:
To Implementation of Double Probing using C Programming.
PSEUDOCODE:
BEGIN
void DoubleHashing(int tablesize, int HashTable[])

{ int n, j, element, hashkey, i, R, t, flag;
scanf("%d", &n);
for(R=tablesize-1; R>1; R--)
{
flag=1;
for(t=2; t<R; t++){ if((R
%t)==0){
flag=0;
break;
}
}
if(flag)
break;
}
printf("Largest Prime Smaller than Tablesize : %d\n", R);
for(j=0; j<n; j++){
i=0;
while(1){
hashkey = ((element % tablesize) + (i*(R-(element%R)))) % tablesize;
break;
}
else
i++;
}
}
}
END
SOURCE CODE:
#include<stdio.h>
void DoubleHashing(int tablesize, int HashTable[])

{ int n, j, element, hashkey, i, R, t, flag;
717823L333
717823L333
scanf("%d", &n);
for(R=tablesize-1; R>1; R--)
{
flag=1;
for(t=2; t<R; t++){ if((R
%t)==0){
flag=0;
break;
}
}
if(flag)
break;
}
printf("Largest Prime Smaller than Tablesize : %d\n", R);
for(j=0; j<n; j++){
i=0;
while(1){
hashkey = ((element % tablesize) + (i*(R-(element%R)))) % tablesize;
break;
}
else
i++;
}
}
}
void main()
{
int tablesize, i;
HashTable[i] = -1;
DoubleHashing(tablesize, HashTable);
printf("HashTable Contents after Double Hashing: \
}
717823L333
OUTPUT:
PREPARATION 30
LAB PERFORMANCE 30
REPORT 40
TOTAL 100
INITIAL OF FACULTY
RESULT:
717823L333

Find Indices of Pair of Elements Whose Sum Is Equal To Target

Uploaded by

Copyright:

Available Formats

Find Indices of Pair of Elements Whose Sum Is Equal To Target

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Find Indices of Pair of Elements Whose Sum Is Equal To Target

Uploaded by

Copyright:

Available Formats

DEPARTMENT OF EC 23CSR205 DATA STRUCTURES AND ALGORITHMS LABORATORY

void InsertAtEnd(int Element)

result; int choice, ele, flg=1,

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

void InsertAtPosition(int Element)

printf("Enter the elements to be inserted at the end:");

Exp. No : 2.1 (a)

Exp. No : 2.1 (b) CONVERSION OF INFIX TO POSTFIX EXPRESSION

Exp. No : 2.1(c) EVALUATION OF POSTFIX EXPRESSION

void EnqueueF(int element)

Exp. No : 2.2(c) PRINT STRINGS IN RANDOM USING DOUBLE

int Dequeue F()

int Dequeue R()

Exp. No : 3.1 (a) IMPLEMENTATION OF BINARY TREE

tree = (BT*)malloc(sizeof(BT)); tree->data =

void PreOrder(BT *tree)

if(tree != NULL) printf("%d\

void PostOrder(BT *tree)

Exp.No:3.1(b) IMPLEMENTATION OF BINARY SEARCH TREE

void Preorder(struct node * tree)

if(tree != NULL) printf("%d

void Postorder(struct node * tree)

int HeightofNode(struct node *tree)

int lh, rh; if(tree

struct node* Insert(struct node *tree, int element)

else if(element < tree->data) tree->LChild =

FindMin(struct node *tree)

struct node* FindMax(struct node *tree)

int Search(struct node *tree, int key)

int DepthofNode(struct node *tree, int key)

int choice, element, flag=1, res;

void Inorder(struct node *tree)

void Preorder(struct node * tree)

void Postorder(struct node * tree)

int HeightofNode(struct node *tree)

struct node* Insert(struct node *tree, int element)

struct node* FindMin(struct node *tree)

struct node* FindMax(struct node *tree)

int Find(struct node *tree, int key)

int DepthofNode(struct node *tree, int key)

root = Insert(root, element);

int countInRange(struct Node* root, int low, int high) {

if (root->data >= low && root->data <= high)

struct Node* newNode(int data) {

struct Node* insert(struct Node* root, int data) {

if (data < root->data)

int countInRange(struct Node* root, int low, int high) {

if (root->data >= low && root->data <= high)

if (root->left == NULL && root->right == NULL)

return leafSum(root->left) + leafSum(root->right);

struct Node* newNode(int data) {

struct Node* insert(struct Node* root, int data) {

if (data < root->data)

int leafSum(struct Node* root)

if (root->left == NULL && root->right == NULL)

return leafSum(root->left) + leafSum(root->right);

void Heapify(int arr[], int n, int s)

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

void Heapify(int arr[], int n, int s)