TASK 1A

/*
DS LAB TASK 1A
1a. Write a C program to implement STACK operations using array
Write a C program to implement the folowing operations on STACKS using arrays.
[Link] [Link] [Link] [Link] [Link]/STOP

NOTE: ASSUME MAX SIZE OF STACK AS 4

Also check for "Invalid Option"
INPUT FORMAT:OPERATIONS AS INTEGERS GIVEN IN NOTE AND TERMINATED
ALWAYS BY EXIT OPERATION.
OUTPUT FORMAT: AS PER THE TEST CASE

TEST CASES:
case=t6
input=
1 10
1 20
2
3
4
5
output=
"STACK OPERATIONS USING ARARYS
10 is Pushed into stack[0]
20 is Pushed into stack[1]
20 is Popped from stack[1]
The elements of Stack are :10
Top Most element of the Stack is 10"

case = t1
input=
2
3
4
5
output=
"STACK OPERATIONS USING ARARYS
Cannot POP - STACK UNDERFLOW
Nothing to display - Stack Empty
No PEAK - Stack Empty"

NOTE:
CHECK OUTPUTS FOR ALL THE GIVEN OPERATIONS
NOTE : JUST REMEMEBER EVERY TEST CASE MUST END WITH EXIT OPERATION SO
THAT IT WILL STOP FINITELY.
*/
//Start writing program from here
#include <stdio.h>
#include <stdlib.h>
#define Max 4
int stack[Max],choice,n,top,x,i;
void push(void);
void pop(void);
void peak(void);
void display(void);
int main(){
top=-1;
printf("STACK OPERATIONS USING ARRAYS");
do{
scanf("%d",&choice);
switch(choice){
case 1:{
push();
break;
}
case 2:{
pop();
break;
}
case 3:{
display();
break;
}
case 4:{
peak();
break;
}
case 5:
exit(0);

default :
{
printf("\nInvalid Choice");

}
}

}
while(choice!=5);
return 0;
}
void push(){
scanf("%d",&x);
if (top>=Max-1){
printf("\nCannot PUSH - STACK OVERFLOW");
}else{

top++;
stack[top]=x;
printf("\n%d is Pushed into stack[%d]",x,top);
}
}
void pop(){
if (top<=-1){
printf("\nCannot POP - STACK UNDERFLOW");
}else{

printf("\n%d is Popped from stack[%d]",stack[top],top);

top--;
}
}
void display(){
if (top>=0){
printf("\nThe elements of Stack are :");
for (i=top;i>=0;i--){
printf("%d ",stack[i]);
}

}else{
printf("\nNothing to display - Stack Empty");
}
}
void peak(){
if (top<0){
printf("\nNo PEAK - Stack Empty");
}else{
printf("\nTop Most element of the Stack is %d",stack[top]);
}
}

TASK 1B

/*
DS LAB TASK 1B
1b. Write a C program to implement QUEUE operations using array
Write a C program to implement the folowing operations on QUEUE using arrays.
NOTE : [Link] [Link] [Link] [Link]/STOP
NOTE: ASSUME MAX SIZE OF QUEUE AS 4
Also check for "Invalid Option"
INPUT FORMAT:OPERATIONS AS INTEGERS GIVEN IN NOTE AND TERMINATED
ALWAYS BY EXIT OPERATION.
OUTPUT FORMAT: AS PER THE TEST CASE

TEST CASES:
case = t2
input =
3
2
4
output =
"QUEUE OPERATIONS USING ARRAY
Nothing to Display - QUEUE EMPTY
Cannot Dequeue - QUEUE UNDERFLOW"

case = t3
input =
1 10
1 20
3
2
2
2
3
4
output =
"QUEUE OPERATIONS USING ARRAY
20 is added into Q[1]
The elements of QUEUE are : 10 20
10 is dequeued from Q[0]
20 is dequeued from Q[1]
Cannot Dequeue - QUEUE UNDERFLOW
Nothing to Display - QUEUE EMPTY"

CHECK OUTPUT OF ALL THE GIVEN OPERATIONS

NOTE:JUST REMEMBER EVERY TEST CASE MUST END WITH EXIT OPERATION SO
THAT IT WILL STOP FINITELY.
*/
//Start writing program from here
#include<stdio.h>
#define MAX 4
int Q[MAX];
int front=-1,rear=-1;
void enqueue(int x){
if (rear==MAX-1){
printf("Cannot Enqueue - QUEUE OVERFLOW\n");
 }else{
if (front==-1){
front=0;
}
rear++;
Q[rear]=x;
printf("%d is added into Q[%d]\n",x,rear);

}
}
void dequeue(){
if (front==-1 || front>rear){
printf("Cannot Dequeue - QUEUE UNDERFLOW\n");
}else{
printf("%d is dequeued from Q[%d]\n",Q[front],front);
front++;
if (front>rear){
front=rear=-1;
}
}
}
void display(){
int i;
if (front==-1){
printf("Nothing to Display - QUEUE EMPTY\n");
}else{
printf("The elements of QUEUE are : ");
for (i=front;i<=rear;i++){
printf("%d ",Q[i]);
}
printf("\n");
}
}
int main(){
int choice,value;
printf("QUEUE OPERATIONS USING ARRAY\n");
while(1){
scanf(" %d",&choice);
switch(choice){
case 1:
scanf("%d",&value);
enqueue(value);
break;
case 2:
dequeue();
break;
case 3:
display();
 break;
case 4:
return 0;
default:
printf("Invalid Choice\n");
}
}
return 0;
}

TASK 1C

/*
DS LAB TASK 1C
1c. Write a C programto implement Circular Queue operations using arrays
Write a C program to implement the folowing operations on CIRCULAR QUEUE
NOTE : [Link] [Link] [Link] [Link]/STOP

NOTE: ASSUME MAX SIZE OF QUEUE AS 4

Also check for "Invalid Option"
INPUT FORMAT:OPERATIONS AS INTEGERS GIVEN IN NOTE AND TERMINATED
ALWAYS BY EXIT OPERATION.
OUTPUT FORMAT: AS PER THE TEST CASE

TESTCASES:

case = t1
input = 1
10
1
20
1
30
1
40
1
50
4
output = " QUEUE IS FULL "

case = t4
input = 1
10
20
4
output =
" INVALID CHOICE "

CHECK OUTPUT OF ALL THE GIVEN OPERATIONS

NOTE:JUST REMEMBER EVERY TEST CASE MUST END WITH EXIT OPERATION SO
THAT IT WILL STOP FINITELY.
*/
//Start writing program from here
/*
DS LAB TASK 1C
1c. Write a C programto implement Circular Queue operations using arrays
Write a C program to implement the folowing operations on CIRCULAR QUEUE
NOTE : [Link] [Link] [Link] [Link]/STOP

NOTE: ASSUME MAX SIZE OF QUEUE AS 4

Also check for "Invalid Option"
INPUT FORMAT:OPERATIONS AS INTEGERS GIVEN IN NOTE AND TERMINATED
ALWAYS BY EXIT OPERATION.
OUTPUT FORMAT: AS PER THE TEST CASE

TESTCASES:

case = t1
input = 1
10
1
20
1
30
1
40
1
50
4
output = " QUEUE IS FULL "

case = t4
input = 1
10
20
4
output =
" INVALID CHOICE "

CHECK OUTPUT OF ALL THE GIVEN OPERATIONS

NOTE:JUST REMEMBER EVERY TEST CASE MUST END WITH EXIT OPERATION SO
THAT IT WILL STOP FINITELY.
*/
//Start writing program from here
#include <stdio.h>
#define size 4
void enqueue(int);
void dequeue();
void display();
int cQueue[size],front=-1,rear=-1;
int main(){
int choice,value;
while(1){
scanf("%d",&choice);
switch(choice){
case 1:
scanf("%d",&value);
enqueue(value);
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
return 0;
default:
printf(" INVALID CHOICE ");
}
}
}
void enqueue(int value){
if ((front==0 && rear==size-1) || (rear+1==front)){
printf(" QUEUE IS FULL ");
return;
}
if (front==-1){
front=rear=0;
}else if (rear==size-1){
rear=0;
}else{
rear++;
}
cQueue[rear]=value;
}
void dequeue(){
if (front==-1){
printf("QUEUE IS UNDERFLOW \n");
return;
 }
printf("DELETED ELEMENT IN QUEUE = %d\n",cQueue[front]);
if (front==rear){
front=rear=-1;
}else if (front==size-1){
front=0;
}else{
front++;
}
}
void display(){
if (front==-1){
printf(" QUEUE IS EMPTY \n");
return;
}
int i=front;
if (front<=rear){
while (i<=rear){
printf("%d ",cQueue[i]);
i++;
}
}else{
while (i<=size-1){
printf("%d ",cQueue[i]);
i++;
} i=0;
while(i<=rear){
printf("%d ",cQueue[i]);
i++;

}
}
printf("\n");
}

TASK 2A

/*2a. Write a C program to implement INFIX TO POSTFIX conversion.

INPUT FORMAT: READ THE POSTFIX EXPRESSION AS A STRING
OUTPUT FORMAT: DISPLAY THE RESULTANT POSTFIX EXPRESSION AS PER TEST
CASE.
NOTE: CHECK ALL INVALID CASES
[Link] Infix Expression - Missing close braces
[Link] underflow - Open Brace Missing
[Link] Infix Expression - Invalid Symbols
SAMPLE TEST CASES:
case=t8
input=a+b-c)
output=
"Given Infix expression is : a+b-c)
Stack underflow - Open Brace Missing"

case=t9
input=a+b*c-(d+e)
output=
"Given Infix expression is : a+b*c-(d+e)
Postfix expression is : abc*+de+-"
*/
//Start writing program from heee
#include<stdio.h>
#include<ctype.h>
#include<string.h>

#define MAX 100

char stack[MAX];
int top=-1;

void push(char x)
{
stack[++top]=x;
}

char pop()
{
if(top==-1)
return '\0';
else
return stack[top--];
}

int priority(char x)
{
if(x=='+'||x=='-')
return 1;
if(x=='*'||x=='/')
return 2;
return 0;
}

int main()
{
char infix[MAX],postfix[MAX];
int i,j=0;
int open=0,close=0;

scanf("%s",infix);

printf("Given Infix expression is : %s\n",infix);

for(i=0;i<strlen(infix);i++)
{
char ch=infix[i];

if(isalnum(ch))
{
postfix[j++]=ch;
}

else if(ch=='(')
{
push(ch);
open++;
}

else if(ch==')')
{
close++;

while(top!=-1 && stack[top]!='(')

{
postfix[j++]=pop();
}

if(top==-1)
{
printf("Stack underflow - Open Brace Missing");
return 0;
}

pop();
}

else if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
{
while(top!=-1 && stack[top]!='(' && priority(stack[top])>=priority(ch))
{
postfix[j++]=pop();
}
 push(ch);
}

else
{
printf("Incorrect Infix Expression - Invalid Symbols");
return 0;
}
}

if(open>close)
{
printf("Invalid Infix Expression - Missing close braces");
return 0;
}

while(top!=-1)
{
if(stack[top]=='(')
{
printf("Invalid Infix Expression - Missing close braces");
return 0;
}

postfix[j++]=pop();
}

postfix[j]='\0';

printf("Postfix expression is : %s",postfix);

return 0;
}

TASK 2B

/*DS LAB
TASK 2B Write a C program to evalulate a postfix expression.
INPUT FORMAT:
Enter a mathematical expression in postfix notation.
Ensure that operands(numbers)and operators(+, -, *, /) are not separated by spaces.
OUTPUT FORMAT:
Result after evaluation of the Postfix Expression.
or
Error codes for invalid expressions as per test cases.
Test Cases:

Case=t8
Input=ab*c-d+
25
7
14
6
Output=
"Result of Postfix expression ab*c-d+ = 167"

Case=t2
Input=ab*c-d+
25
7
14
6
Output=
"Result of Postfix expression ab*c-d+ = 167"

case=t4
input=
ab$
2
0
output=
"Invalid symbols in the Postfix Expression"

*/
//Start writing program from here
#include<stdio.h>
#include<ctype.h>
#include<string.h>

#define MAX 100

int stack[MAX];
int top=-1;

void push(int x)
{
stack[++top]=x;
}

int pop()
{
if(top==-1)
 return -9999;
return stack[top--];
}

int main()
{
char postfix[MAX];
int value[26];
int i,a,b,res;

for(i=0;i<26;i++)
value[i]=-1;

scanf("%s",postfix);

for(i=0;i<strlen(postfix);i++)
{
if(isalpha(postfix[i]))
{
int idx = tolower(postfix[i])-'a';
if(value[idx]==-1)
scanf("%d",&value[idx]);
}
}

for(i=0;i<strlen(postfix);i++)
{
char ch=postfix[i];

if(isdigit(ch))
{
push(ch-'0');
}
else if(isalpha(ch))
{
int idx = tolower(ch)-'a';
push(value[idx]);
}
else if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
{
b=pop();
a=pop();

if(a==-9999 || b==-9999)
{
printf("Stack underflow - Missing Operands");
return 0;
 }

switch(ch)
{
case '+': res=a+b; break;
case '-': res=a-b; break;
case '*': res=a*b; break;
case '/': res=a/b; break;
}

push(res);
}
else
{
printf("Invalid symbols in the Postfix Expression");
return 0;
}
}

if(top!=0)
{
printf("Invalid or Incomplete Postfix expression");
return 0;
}

printf("Result of Postfix expression %s = %d",postfix,pop());

return 0;
}

TASK 3

/*3. Write a C program to implement Singly Linked List operations.

Write a C program to implement the folowing operations on SINGLE LINKED LIST
OPERATIONS:
[Link] [Link] [Link] [Link] [Link] [Link] Display [Link]
Also check for "Invalid Choice"
INPUT FORMAT :
FOR INSERT - ENTER POSITION AND VALUE
FOR DELETE - ENTER POSITION
FOR SEARCH - ENTER KEY TO FIND.

SAMPLE TEST CASES:

case=t1
input=
1
1 700
1
2 900
1
1 1100
3
4 700
4 100
22
5
6
2 20
1
10 100
7
output=
SLL ELEMENTS ARE
1100 ->700 ->900 ->
700 is found in SLL
100 is not found in SLL
Deleted element from SLL is 700
No of nodes in SLL = 2
SLL ELEMENTS IN REVERSE ORDER
900 1100
Position does not exist - Cannot delete from SLL
Position does not exist - Cannot insert into SLL

CHECK OUTPUT FOR ALL THE GIVEN OPERATIONS

NOTE : JUST REMEMEBER EVERY TEST CASE MUST END WITH EXIT OPERATION SO
THAT IT WILL STOP FINITELY.
*/
//Start writing program from here

//sll implementation
#include<stdio.h>
#include<stdlib.h>

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

void SLLdisplay();
void SLLsearch(int x);
void SLLdeletePos(int pos);
void SLLinsertPos(int pos ,int val);
int SLLCountNodes();
void SLLreverse(struct node *temp);

int main()
{
int ch,val,pos,x;

while(1)
{
scanf("%d",&ch);

switch(ch)
{
case 1:
scanf("%d %d",&pos,&val);
SLLinsertPos(pos,val);
break;

case 2:
scanf("%d",&pos);
SLLdeletePos(pos);
break;

case 3:
SLLdisplay();
break;

case 4:
scanf("%d",&x);
SLLsearch(x);
break;

case 5:
printf("\nNo of nodes in SLL = %d",SLLCountNodes());
break;

case 6:
if(start==NULL)
printf("\nEmpty SLL - Cannot Reverse Display");
else
{
printf("\nSLL ELEMENTS IN REVERSE ORDER\n");
SLLreverse(start);
}
break;

case 7:
 exit(0);

default:
printf("\nInvalid Choice");
}
}
}

void SLLinsertPos(int pos,int val)

{
struct node *newnode,*temp;
int i;

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

newnode->data=val;
newnode->next=NULL;

if(pos==1)
{
newnode->next=start;
start=newnode;
return;
}

temp=start;

for(i=1;i<pos-1 && temp!=NULL;i++)

temp=temp->next;

if(temp==NULL)
{
printf("\nPosition does not exist - Cannot insert into SLL");
free(newnode);
return;
}

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

void SLLdeletePos(int pos)

{
struct node *temp,*prev;
int i;

if(start==NULL)
{
printf("\nPosition does not exist - Cannot delete from SLL");
 return;
}

if(pos==1)
{
temp=start;
start=start->next;
printf("\nDeleted element from SLL is %d",temp->data);
free(temp);
return;
}

temp=start;

for(i=1;i<pos && temp!=NULL;i++)

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

if(temp==NULL)
{
printf("\nPosition does not exist - Cannot delete from SLL");
return;
}

prev->next=temp->next;
printf("\nDeleted element from SLL is %d",temp->data);
free(temp);
}

void SLLdisplay()
{
struct node *temp=start;

if(start==NULL)
{
printf("\nEmpty SLL - Cannot display");
return;
}

printf("\nSLL ELEMENTS ARE\n");

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

void SLLsearch(int x)
{
struct node *temp=start;

if(start==NULL)
{
printf("\nSLL Empty - Cannot Search");
return;
}

while(temp!=NULL)
{
if(temp->data==x)
{
printf("\n%d is found in SLL",x);
return;
}
temp=temp->next;
}

printf("\n%d is not found in SLL",x);

}

int SLLCountNodes()
{
struct node *temp=start;
int count=0;

while(temp!=NULL)
{
count++;
temp=temp->next;
}

return count;
}

void SLLreverse(struct node *temp)

{
if(temp==NULL)
return;

SLLreverse(temp->next);
printf("%d ",temp->data);
}
TASK 4

/* TASK 7:
[Link] a C program to implement the folowing operations on CIRCULAR LINKED LIST
OPERATIONS:
[Link] [Link] [Link] [Link] [Link] [Link] Display [Link]
Also check for "Invalid Choice"
INPUT FORMAT :
FOR INSERT - READ VALUE AND POSITION
FOR DELETE - READ POSITION
FOR SEARCH - READ KEY
OUTPUT FORMAT:
DISPLAY AS PER TEST CASES.

TEST CASE :
CASE=T10
INPUT=
1
100 1
1
200 1
1
300 1
5
6
3
4
2500
4
200
2
2
2
10
1
1000 10
7

OUTPUT=
CLL OPERATIONS
100 is inserted into CLL at position 1
200 is inserted into CLL at position 1
300 is inserted into CLL at position 1
No of nodes in CLL = 3
CLL Reverse Display :100 ->200 -> 300 ->
CLL elements are :300 ->200 ->100 ->
2500 is not found in CLL
200 is found in CLL
Deleted Node form CLL is 200 from position 2
Cannot Delete from CLL - Invalid Position or CLL Empty
Cannot Insert in CLL - Invalid Position

CHECK OUTPUT FOR ALL THE GIVEN OPERATIONS

NOTE : JUST REMEMEBER EVERY TEST CASE MUST END WITH EXIT OPERATION SO
THAT IT WILL STOP FINITELY.
*/
//Start writing program from here

//IMPLEMENTING CIRCULAR LINKED LIST

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

struct node
{
int data;
struct node *next;
};

struct node *head = NULL;

int countNodes()
{
int count = 0;

if(head == NULL)
return 0;

struct node *temp = head;

do
{
count++;
temp = temp->next;
} while(temp != head);

return count;
}

void insertNode(int value, int pos)

{
int count = countNodes();

if(pos < 1 || pos > count + 1)

{
 printf("\nCannot Insert in CLL - Invalid Position");
return;
}

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

newnode->data = value;

if(head == NULL)
{
newnode->next = newnode;
head = newnode;
printf("\n%d is inserted into CLL at position %d", value, pos);
return;
}

if(pos == 1)
{
struct node *last = head;

while(last->next != head)
last = last->next;

newnode->next = head;
last->next = newnode;
head = newnode;

printf("\n%d is inserted into CLL at position %d", value, pos);

return;
}

struct node *temp = head;

int i;

for(i = 1; i < pos - 1; i++)

temp = temp->next;

newnode->next = temp->next;
temp->next = newnode;

printf("\n%d is inserted into CLL at position %d", value, pos);

}

void deleteNode(int pos)

{
int count = countNodes();

if(head == NULL || pos < 1 || pos > count)

{
 printf("\nCannot Delete from CLL - Invalid Position or CLL Empty");
return;
}

struct node *temp = head;

int deletedValue;

if(pos == 1)
{
deletedValue = head->data;

if(head->next == head)
{
free(head);
head = NULL;
}
else
{
struct node *last = head;

while(last->next != head)
last = last->next;

head = head->next;
last->next = head;
free(temp);
}

printf("\nDeleted Node form CLL is %d from position %d", deletedValue, pos);

return;
}

struct node *prev = NULL;

int i;

for(i = 1; i < pos; i++)

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

deletedValue = temp->data;
prev->next = temp->next;
free(temp);

printf("\nDeleted Node form CLL is %d from position %d", deletedValue, pos);

}
void display()
{
if(head == NULL)
{
printf("\nCLL Empty-Nothing to Display");
return;
}

struct node *temp = head;

printf("\nCLL elements are :");

do
{
printf("%d ->", temp->data);
temp = temp->next;
} while(temp != head);
}

void searchNode(int key)

{
if(head == NULL)
{
printf("\nCLL Empty - Cannot search");
return;
}

struct node *temp = head;

do
{
if(temp->data == key)
{
printf("\n%d is found in CLL", key);
return;
}

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

printf("\n%d is not found in CLL", key);

}

void reverseDisplay()
{
int count = countNodes();

if(count == 0)
 {
printf("\nEmpty CLL- Nothing TO REV Display");
return;
}

printf("\nCLL Reverse Display :");

int i, j;
struct node *temp;

for(i = count; i >= 1; i--)

{
temp = head;

for(j = 1; j < i; j++)

temp = temp->next;

printf("%d ->", temp->data);

}
}

int main()
{
int choice, value, pos, key;

printf("CLL OPERATIONS");
while(1)
{
scanf("%d", &choice);

switch(choice)
{
case 1:
scanf("%d%d", &value, &pos);
insertNode(value, pos);
break;

case 2:
scanf("%d", &pos);
deleteNode(pos);
break;

case 3:
display();
break;

case 4:
scanf("%d", &key);
 searchNode(key);
break;

case 5:
printf("\nNo of nodes in CLL = %d", countNodes());
break;

case 6:
reverseDisplay();
break;

case 7:
return 0;

default:
printf("\nInvalid Choice");
}
}

return 0;
}

TASK 5

/*
DS LAB TASK 5
5. Write a C program to implement Double Linked List operations – create, insert, delete and
display.

PERFORM THE BELOW DLL OPERATIONS:

[Link] [Link] [Link] [Link] [Link] Display [Link]
Also check for "Invalid Choice"
NOTE : FOR INSRET FIRST READ POSITION THEN LATER READ THE VALUE IF THE
POSITION IS IN VALID RANGE.

INPUT FORMAT: AS PER TEST CASES.

OUTPUT FORMAT AS PER TEST CASES.

SAMPLE TEST CASES:

case = t8
input =
1
10
2
1
34
3
4
200
5
6
output =
IMPLEMENTING OPERATIONS ON DOUBLE LINKED LIST.
Position does not exist - Cannot insert into DLL
Position does not exist - Cannot delete from DLL
Invalid Choice
Empty DLL - Cannot Display.
DLL Empty - Cannot Search
Empty DLL - Cannot Perform Reverse Display.

CASE=T9
INPUT=
1
1
100
1
2
200
1
3
300
4
300
3
4
250
6
OUTPUT=
IMPLEMENTING OPERATIONS ON DOUBLE LINKED LIST.
300 is found in DLL
THE DLL ELEMENTS :
100 ->200 ->300 ->
250 is not found in DLL

CHECK OUTPUT FOR ALL THE GIVEN OPERATIONS INCLUDING INVALID CASES
NOTE : JUST REMEMEBER EVERY TEST CASE MUST END WITH EXIT OPERATION SO
THAT IT WILL STOP FINITELY.
PREFER A "\n" BEFORE EVERY PRINTF STATEMENT.
*/
//Start writing program from here
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node *prev;
struct node *next;
};

struct node *head = NULL;

int countNodes()
{
int count = 0;
struct node *temp = head;

while(temp != NULL)
{
count++;
temp = temp->next;
}

return count;
}

void insertNode(int pos, int value)

{
int count = countNodes();

if(pos < 1 || pos > count + 1)

{
printf("\nPosition does not exist - Cannot insert into DLL");
return;
}

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

newnode->data = value;
newnode->prev = NULL;
newnode->next = NULL;

if(pos == 1)
{
newnode->next = head;

if(head != NULL)
head->prev = newnode;

head = newnode;
return;
}
 struct node *temp = head;
int i;

for(i = 1; i < pos - 1; i++)

temp = temp->next;

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

if(temp->next != NULL)
temp->next->prev = newnode;

temp->next = newnode;
}

void deleteNode(int pos)

{
int count = countNodes();

if(pos < 1 || pos > count)

{
printf("\nPosition does not exist - Cannot delete from DLL");
return;
}

struct node *temp = head;

int deletedValue;
int i;

if(pos == 1)
{
deletedValue = head->data;
head = head->next;

if(head != NULL)
head->prev = NULL;

free(temp);

printf("\nDeleted element from DLL is %d", deletedValue);

return;
}

for(i = 1; i < pos; i++)

temp = temp->next;

deletedValue = temp->data;
 temp->prev->next = temp->next;

if(temp->next != NULL)
temp->next->prev = temp->prev;

free(temp);

printf("\nDeleted element from DLL is %d", deletedValue);

}

void display()
{
if(head == NULL)
{
printf("\nEmpty DLL - Cannot Display.");
return;
}

struct node *temp = head;

printf("\nTHE DLL ELEMENTS :\n");

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

void searchNode(int key)

{
struct node *temp = head;

while(temp != NULL)
{
if(temp->data == key)
{
printf("\n%d is found in DLL", key);
return;
}

temp = temp->next;
}

printf("\n%d is not found in DLL", key);

}
void reverseDisplay()
{
if(head == NULL)
{
printf("\nEmpty DLL - Cannot Perform Reverse Display.");
return;
}

struct node *temp = head;

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

printf("\nDLL REVERSE DISPLAY\n");

while(temp != NULL)
{
printf("%d ->", temp->data);
temp = temp->prev;
}
}

int main()
{
int choice, pos, value;

printf("IMPLEMENTING OPERATIONS ON DOUBLE LINKED LIST.");

while(1)
{
scanf("%d", &choice);

switch(choice)
{
case 1:
scanf("%d", &pos);

if(pos >= 1 && pos <= countNodes() + 1)

{
scanf("%d", &value);
insertNode(pos, value);
}
else
{
printf("\nPosition does not exist - Cannot insert into DLL");
}
break;
 case 2:
scanf("%d", &pos);
deleteNode(pos);
break;

case 3:
display();
break;

case 4:
scanf("%d", &value);
searchNode(value);
break;

case 5:
reverseDisplay();
break;

case 6:
return 0;

default:
printf("\nInvalid Choice");
}
}

return 0;
}

TASK 6

/*
TASK - 6a - Develop a C code for preorder, inorder and postorder traversals of
a Binary Search Tree using recursion.
i. insert ii. preorder iii. inorder iv. postorder v. exit.

case = t2
input= 1
45
1
23
1
67
1
12
2
3
4
5
output=
"
PREORDER TRAVERSAL OF BINARY SEARCH TREE
45 23 12 67
INORDER TRAVERSAL OF BINARY SEARCH TREE
12 23 45 67
POSTORDER TRAVERSAL OF BINARY SEARCH TREE
12 23 67 45 "

case = t5
input= 1
0
1
-3
1
5
1
-10
1
2
1
8
2
3
4
5
output=
"
PREORDER TRAVERSAL OF BINARY SEARCH TREE
0 -3 -10 5 2 8
INORDER TRAVERSAL OF BINARY SEARCH TREE
-10 -3 0 2 5 8
POSTORDER TRAVERSAL OF BINARY SEARCH TREE
-10 -3 2 8 5 0 "

NOTE:
CHECK OUTPUTS FOR ALL THE GIVEN OPERATIONS
NOTE : JUST REMEMBER EVERY TEST CASE MUST END WITH EXIT OPERATION SO
THAT IT WILL STOP FINITELY.
*/
#include <stdio.h>
#include <stdlib.h>

struct node
{
int data;
struct node *left;
struct node *right;
};

struct node *root = NULL;

struct node* createNode(int value)

{
struct node *newnode;

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

newnode->data = value;
newnode->left = NULL;
newnode->right = NULL;

return newnode;
}

struct node* insert(struct node *root, int value)

{
if(root == NULL)
{
return createNode(value);
}

if(value < root->data)

{
root->left = insert(root->left, value);
}
else
{
root->right = insert(root->right, value);
}

return root;
}

void preorder(struct node *root)

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

void inorder(struct node *root)

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

void postorder(struct node *root)

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

int main()
{
int choice, value;

while(1)
{
scanf("%d", &choice);

switch(choice)
{
case 1:
scanf("%d", &value);
root = insert(root, value);
break;

case 2:
if(root == NULL)
{
printf("\nBST Empty\n");
}
else
{
 printf("\nPREORDER TRAVERSAL OF BINARY SEARCH TREE\n");
preorder(root);
printf("\n");
}
break;

case 3:
if(root == NULL)
{
printf("BST Empty\n");
}
else
{
printf("INORDER TRAVERSAL OF BINARY SEARCH TREE\n");
inorder(root);
printf("\n");
}
break;

case 4:
if(root == NULL)
{
printf("BST Empty\n");
}
else
{
printf("POSTORDER TRAVERSAL OF BINARY SEARCH TREE\n");
postorder(root);
printf("\n");
}
break;

case 5:
exit(0);

default:
printf("Invalid Choice\n");
}
}

return 0;
}

TASK 6B
/*
TASK 6b. Design a C program for level order traversal of a Binary Search Tree.
case = t1
input =
2
3
output =
Level Order Traversal of BST :
Binary Search Tree is Empty

case = t2
input =
1
10
1
20
1
30
1
5
2
3
output =
Level Order Traversal of BST :
10 5 20 30
*/
//start writing program from here
#include <stdio.h>
#include <stdlib.h>

struct node
{
int data;
struct node *left;
struct node *right;
};

struct node *root = NULL;

struct node *queue[100];

int front = -1, rear = -1;

struct node* createNode(int value)

{
 struct node *newnode;

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

newnode->data = value;
newnode->left = NULL;
newnode->right = NULL;

return newnode;
}

struct node* insert(struct node *root, int value)

{
if(root == NULL)
{
return createNode(value);
}

if(value < root->data)

{
root->left = insert(root->left, value);
}
else
{
root->right = insert(root->right, value);
}

return root;
}

void enqueue(struct node *temp)

{
if(front == -1)
{
front = 0;
}

rear++;
queue[rear] = temp;
}

struct node* dequeue()

{
struct node *temp;
 temp = queue[front];
front++;

return temp;
}

int isempty()
{
if(front > rear || front == -1)
{
return 1;
}

return 0;
}

void levelorder(struct node *root)

{
struct node *temp;

if(root == NULL)
{
printf("Binary Search Tree is Empty\n");
return;
}

enqueue(root);

while(!isempty())
{
temp = dequeue();

printf("%d ", temp->data);

if(temp->left != NULL)
{
enqueue(temp->left);
}

if(temp->right != NULL)
{
enqueue(temp->right);
}
}

printf("\n");
}
int main()
{
int choice, value;

while(1)
{
scanf("%d", &choice);

switch(choice)
{
case 1:
scanf("%d", &value);
root = insert(root, value);
break;

case 2:
printf("Level Order Traversal of BST :");
levelorder(root);
break;

case 3:
exit(0);

default:
printf("Invalid Choice\n");
}
}

return 0;
}

TASK 7A

/*
DS LAB TASK 7A
7A. Implement the following operations on Binary Search Tree i. Create ii. Insert iii. Search
NOTE OPTIONS: (i)CREATE-INSERT (ii) SEARCH (iii)EXIT
Also check for "Invalid Option"
INPUT FORMAT: AS PER TEST CASE
OUTPUT FORMAT: AS PER THE TEST CASE
SAMPLE TEST CASES :
case = t5
input=
1
100
1
200
2
300
2
100
3
output=
"Binary Search Tree Operations
100 is inserted into BST.
200 is inserted into BST.
300 is not found in BST.
100 is found in BST."
*/
//Start writing program from here
// BST CREATE INSERT SEARCH
#include <stdio.h>
#include <stdlib.h>

struct node
{
int data;
struct node *left;
struct node *right;
};

struct node *root = NULL;

// Create Node
struct node* createNode(int value)
{
struct node *newnode;

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

newnode->data = value;
newnode->left = NULL;
newnode->right = NULL;

return newnode;
}
// Insert into BST
struct node* insert(struct node *root, int value)
{
if(root == NULL)
{
return createNode(value);
}

if(value < root->data)

{
root->left = insert(root->left, value);
}
else if(value > root->data)
{
root->right = insert(root->right, value);
}

return root;
}

// Search Function
int search(struct node *root, int key)
{
if(root == NULL)
{
return 0;
}

if(root->data == key)
{
return 1;
}

if(key < root->data)

{
return search(root->left, key);
}
else
{
return search(root->right, key);
}
}

int main()
{
int choice, value;

printf("Binary Search Tree Operations\n");

while(1)
{
scanf("%d", &choice);

switch(choice)
{
case 1:

scanf("%d", &value);

root = insert(root, value);

printf("%d is inserted into BST.\n", value);

break;

case 2:

scanf("%d", &value);

if(root == NULL)
{
printf("EMPTY BST - CANNOT SEARCH.\n");
}
else
{
if(search(root, value))
{
printf("%d is found in BST.\n", value);
}
else
{
printf("%d is not found in BST.\n", value);
}
}

break;

case 3:
exit(0);

default:
printf("Invalid Choice.\n");
}
}

return 0;
}

TASK 7B

/*
DS LAB TASK 7B
7b.​ Implement the following operations on Binary Search Tree
i.​ Delete​ ii. Display (INORDER)
NOTE THE OPTIONS: [Link] [Link] [Link]-INORDER [Link]
Also check for "Invalid Option"
NOTE : USE THE PREXISTING INSERT FUNCTION GIVEN IN THE CODE AS CASE 1 IN
LOGIC IMPLEMENTATION.
INPUT FORMAT: AS PER TEST CASE
OUTPUT FORMAT: AS PER THE TEST CASE

SAMPLE TEST CASES :

case = t8
input=
1
50
1
67
1
34
3
2
50
3
2
67
4
output=
"
The elements of BST - INORDER :34->50->67->
50 is found and deleted from BST
The elements of BST - INORDER :34->67->
67 is found and deleted from BST"
*/
//Start writing program from here
#include <stdio.h>
#include <stdlib.h>

struct Node {
 int data;
struct Node* left;
struct Node* right;
};
struct Node*root = NULL;

struct Node* createNode(int data) {

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

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

if (root == NULL) return createNode(data);
if (data < root->data)
root->left = insert(root->left, data);
else if (data > root->data)
root->right = insert(root->right, data);
return root;
}

struct Node* findMin(struct Node* root) {

while (root->left != NULL)
root = root->left;
return root;
}

struct Node* deleteNode(struct Node* root, int data, int* found) {

if (root == NULL) {
*found = 0;
return NULL;
}
if (data < root->data) {
root->left = deleteNode(root->left, data, found);
} else if (data > root->data) {
root->right = deleteNode(root->right, data, found);
} else {
*found = 1;

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

free(root);
return NULL;
}

else if (root->left == NULL) {

struct Node* temp = root->right;
 free(root);
return temp;
} else if (root->right == NULL) {
struct Node* temp = root->left;
free(root);
return temp;
}

else {
struct Node* successor = findMin(root->right);
root->data = successor->data;
int dummyFound = 0;
root->right = deleteNode(root->right, successor->data, &dummyFound);
}
}
return root;
}

void inorder(struct Node* root) {

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

int main() {
struct Node* root = NULL;
int choice, data, found;

while (1) {
scanf("%d", &choice);
switch (choice) {
case 1:
scanf("%d", &data);
root = insert(root, data);
break;
case 2:
scanf("%d", &data);
if (root == NULL) {
printf("\nEmpty BST - Cannot delete");
} else {
found = 0;
root = deleteNode(root, data, &found);
if (found)
printf("\n%d is found and deleted from BST", data);
else
printf("\n%d is not found in BST - So cannot delete\n", data);
 }
break;
case 3:
if (root == NULL) {
printf("\nEmpty BST - Nothing to Display");
} else {
printf("\nThe elements of BST - INORDER :");
inorder(root);
//printf("\n");
}
break;
case 4:
exit(0);
default:
printf("Invalid Choice.\n");
}
}
return 0;
}

TASK 8A

/*
TASK 8A. Implement the following operations on BINARY SEARCH TREE using a C
program.
TASK 8-BST OPERATIONS - Countnodes Height Minimum node Maximum node
(i) CREATE/INSERT (ii) COUNT NODES (iii) HEIGHT (iV) MINIMUM (v) MAXIMUM (vi) Exit

INPUT FORMAT: AS PER TEST CASE

OUTPUT FORMAT: AS PER TEST CASE
LEAF NODES ARE AT HEIGHT 0.
SAMPLE TEST CASES
case = T7
input=
1
10
1
5
1
0
1
-5
1
-10
3
5
2
4
6
output=
"
Binary Search Tree Operations
HEIGHT OF BST = 4
MAXIMUM VALUE IN BST = 10
NODES IN BST = 5
MINIMUM VALUE IN BST = -10"

NOTE:
CHECK OUTPUTS FOR ALL THE GIVEN OPERATIONS
NOTE : JUST REMEMBER EVERY TEST CASE MUST END WITH EXIT OPERATION SO
THAT IT WILL STOP FINITELY.
*/
#include <stdio.h>
#include <stdlib.h>

struct node{
int data;
struct node*left,*right;
};
struct node*root = NULL;
struct node*create(int data){
struct node*newnode = (struct node*)malloc(sizeof(struct node));
newnode -> data = data;
newnode -> left = newnode -> right = NULL;
return newnode;
}
struct node*insert(struct node*root,int data){
if(root == NULL)
return create(data);
if(data < root -> data)
root -> left = insert(root -> left,data);
if(data > root -> data)
root -> right = insert(root -> right,data);
return root;

}
int countnodes(struct node*root){
if(root == NULL)
return 0;
return 1 + countnodes(root -> left) + countnodes(root -> right);
}
int height(struct node*root){
 int lh,rh;
if(root == NULL)
return -1;
lh = height(root -> left);
rh = height(root -> right);
if(lh > rh)
return lh + 1;
else
return rh + 1;
}
int minimum(struct node*root){
while(root -> left != NULL)
root = root -> left;
return root -> data;
}
int maximum(struct node*root){
while(root -> right != NULL)
root = root -> right;
return root -> data;
}
int main(){
int ch,val;
printf("\nBinary Search Tree Operations\n");
while(1){
scanf("%d",&ch);
switch(ch){
case 1:
scanf("%d",&val);
root = insert(root,val);
break;

case 2:
printf("NODES IN BST = %d\n",countnodes(root));
break;

case 3:
if(root == NULL)
printf("BST EMPTY - NO HEIGHT\n");
else
printf("HEIGHT OF BST = %d\n",height(root));
break;

case 4:
if(root == NULL)
printf("BST EMPTY - NO MINIMUM\n");
else
printf("MINIMUM VALUE IN BST = %d\n",minimum(root));
break;
 case 5:
if(root == NULL)
printf("BST EMPTY - NO MAXIMUM\n");
else
printf("MAXIMUM VALUE IN BST = %d\n",maximum(root));
break;

case 6:
exit(0);

default:
printf("INVALID CHOICE");
}

}
return 0;
}

TASK 9A

/*
LAB TASK 9A
QUESTION: 9a-Develop a C program for Quick sort.

INPUT FORMAT:
FIRST LINE CONTAINS "n" THE SIZE OF THE LIST.
SECOND LINE CONTAINS "n" integers seperated by a space.

OUTPUT FORMAT:
DISPLAY UNSORTED LIST,SORTING METHOD NAME AND SORTED LIST AS PER THE
TEST CASE
THE OUTPUT VALUES ARE SEPERATED BY A TRAILING SPACE.

Test Cases:
case = t1
input = 6
-1 6 -45 -8 0 4
output =
"Unsorted List
-1​ 6​ -45​ -8​ 0​ 4​
QUICK SORT
Sorted List
-45​ -8​ -1​ 0​ 4​ 6"
*/
//Start writing program from here
#include<stdio.h>
void swap(int*a,int *b){
int t=*a;
*a=*b;
*b=t;
}
int partition(int arr[],int low ,int high){
int pivot=arr[high];
int i=low-1;
for(int j=low;j<high;j++){
if(arr[j]<=pivot){
i++;
swap(&arr[i],&arr[j]);
}
}swap(&arr[i+1],&arr[high]);
return i+1;
}
void quicksort(int arr[],int low,int high){
if(low<high){
int pi=partition(arr,low,high);
quicksort(arr,low,pi-1);
quicksort(arr,pi+1,high);
}
}
int main(){
int n;
scanf("%d",&n);
int arr[n];
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}
printf("Unsorted List\n");
for(int i=0;i<n;i++){
printf("%d ",arr[i]);
}
quicksort(arr,0,n-1);
printf("\nQUICK SORT\nSorted List\n");
for(int i=0;i<n;i++){
printf("%d ",arr[i]);
}
}

TASK 9B
/*
LAB TASK 9B
QUESTION: 9B-Demonstrate Merge sort using a C program.

INPUT FORMAT:
FIRST LINE CONTAINS "n" THE SIZE OF THE LIST.
SECOND LINE CONTAINS "n" integers seperated by a space.

OUTPUT FORMAT:
DISPLAY UNSORTED LIST,SORTING METHOD NAME AND SORTED LIST AS PER THE
TEST CASE
THE OUTPUT VALUES ARE SEPERATED BY A TRAILING SPACE.

Test Cases:
case = t1
input = 6
-1 6 -45 -8 0 4
output =
"Unsorted List
-1​ 6​ -45​ -8​ 0​ 4​
MERGE SORT
Sorted List
-45​ -8​ -1​ 0​ 4​ 6"
*/
//Start writing program from here
#include<stdio.h>
void mergesort(int arr[],int left,int mid,int right){

int size1=mid-left+1;
int size2=right-mid;

int l[size1],r[size2];

int i,j,k;

for(i=0;i<size1;i++){
l[i]=arr[left+i];
}for(j=0;j<size2;j++){
r[j]=arr[mid+1+j];
}
i=0;
j=0;
k=left;

while(i<size1 && j<size2){

 if(l[i]<=r[j]){
arr[k++]=l[i++];
}else{
arr[k++]=r[j++];
}
}
while(i<size1){
arr[k++]=l[i++];
}
while(j<size2){
arr[k++]=r[j++];
}
}
void merge(int arr[],int left,int right){
if(left<right){
int mid=left+(right-left)/2;
merge(arr,left,mid);
merge(arr,mid+1,right);
mergesort(arr,left,mid,right);
}
}
int main(){
int size;
scanf("%d",&size);
int arr[size];
for(int i=0;i<size;i++){
scanf("%d",&arr[i]);
}
printf("Unsorted List\n");
for(int i=0;i<size;i++){
printf("%d ",arr[i]);
}merge(arr,0,size-1);
printf("\nMERGE SORT\nSorted List\n");
for(int i=0;i<size;i++){
printf("%d ",arr[i]);
}
}

TASK 9C

/*
LAB TASK 9C
QUESTION: 9C- Design a C program for Radix Sort.

INPUT FORMAT:
FIRST LINE CONTAINS "n" THE SIZE OF THE LIST
SECOND LINE CONTAINS "n" integers seperated by a space

OUTPUT FORMAT:
DISPLAY UNSORTED LIST,SORTING METHOD NAME AND SORTED LIST AS PER THE
TEST CASE.
THE VALUES ARE DISPLAYED BY A TRAILING SPACE.

Test Cases:
case = t1
input = 6
502 674 175 542 874 245
output =
"UNSORTED LIST
502​ 674​ 175​ 542​ 874​ 245​
RADIX SORT
SORTED LIST
175​ 245​ 502​ 542​ 674​ 874 "​
*/
//Start writing program from here
#include<stdio.h>
int getmax(int arr[],int n){
int max=arr[0];
for(int i=0;i<n;i++){
if(arr[i]>max){
max=arr[i];
}
}return max;
}
void countingsort(int arr[],int n,int place){
int output[n],count[10]={0};
for(int i=0;i<n;i++){
count[(arr[i]/place)%10]++;
}
for(int i=1;i<10;i++){
count[i]+=count[i-1];
}
for(int i=n-1;i>=0;i--){
output[count[(arr[i]/place)%10]-1]=arr[i];
count[(arr[i]/place)%10]--;
}
for(int i=0;i<n;i++){
arr[i]=output[i];
}
}
void radixsort(int arr[],int n){
int max=getmax(arr,n);
for(int place=1;max/place>0;place*=10){
 countingsort(arr,n,place);
}
}
int main(){
int n;
scanf("%d",&n);
int arr[n];
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}
printf("UNSORTED LIST\n");
for(int i=0;i<n;i++){
printf("%d ",arr[i]);
}
radixsort(arr,n);
printf("\nRADIX SORT\nSORTED LIST\n");
for(int i=0;i<n;i++){
printf("%d ",arr[i]);
}
}

TASK 10A

/*LAB TASK 10A

[Link] a C program for Tree sort.

INPUT FORMAT:
FIRST LINE CONTAINS "n" THE SIZE OF THE LIST.
SECOND LINE CONTAINS "n" integers seperated by a space.

OUTPUT FORMAT:
DISPLAY UNSORTED LIST,SORTING METHOD NAME AND SORTED LIST AS PER THE
TEST CASE
THE OUTPUT VALUES ARE SEPERATED BY A TRAILING SPACE.

Test Cases:
case = t6
input =
7
-98 -567 -345 1000 -1000 54 202
output=
"
TREE SORT - SORTED LIST
-1000 -567 -345 -98 54 202 1000 "
*/
//Start writing program from here
#include <stdio.h>
#include <stdlib.h>

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

struct Node* createNode(int value)

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

struct Node* insert(struct Node* root, int value)

{
if (root == NULL)
return createNode(value);

if (value < root->data)

root->left = insert(root->left, value);
else
root->right = insert(root->right, value);

return root;
}

void inorder(struct Node* root)

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

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

scanf("%d", &n);

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

{
 scanf("%d", &value);
root = insert(root, value);
}

printf("TREE SORT - SORTED LIST\n");

inorder(root);

return 0;
}

TASK 10B

/*LAB TASK 10B

TASK 10B- Demonstrate Heap sort using a C program
INPUT FORMAT:
FIRST LINE CONTAINS "n" THE SIZE OF THE LIST.
SECOND LINE CONTAINS "n" integers seperated by a space.

OUTPUT FORMAT:
DISPLAY UNSORTED LIST,SORTING METHOD NAME AND SORTED LIST AS PER THE
TEST CASE
THE OUTPUT VALUES ARE SEPERATED BY A TRAILING SPACE.

Test Cases:
case = t6
input=10
0987654321
output =
"
UNSORTED LIST
0987654321
HEAP SORT
SORTED LIST
0123456789"

*/
//Start writing program from here
#include<stdio.h>
void heapify(int arr[],int n,int i){
int largest=i;
int left=2*i+1;
int right=2*i+2;
if(left<n && arr[left]>arr[largest]){
largest=left;
}if(right<n && arr[right]>arr[largest]){
largest=right;
 }if(largest != i){
int temp=arr[i];
arr[i]=arr[largest];
arr[largest]=temp;
heapify(arr,n,largest);
}
}
void heapsort(int arr[],int n){
for(int i=n/2-1;i>=0;i--){
heapify(arr,n,i);
}for(int i=n-1;i>0;i--){
int temp=arr[0];
arr[0]=arr[i];
arr[i]=temp;
heapify(arr,i,0);
}
}
int main(){
int n;
scanf("%d",&n);
int arr[n];
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
}printf("\nUNSORTED LIST\n");
for(int i=0;i<n;i++){
printf("%d ",arr[i]);
}heapsort(arr,n);
printf("\nHEAP SORT\nSORTED LIST\n");
for(int i=0;i<n;i++){
printf("%d ",arr[i]);
}
}

TASK 11A

/*LAB TASK 11A

11A. C Program to Perform Depth-First Search (DFS) Traversal on a Graph

This program reads a graph represented as an adjacency matrix and

performs a DFS traversal starting from a given node.

Steps:
1. Read the number of vertices in the graph.
2. Read the adjacency matrix representing the graph.
3. Read the starting node for DFS traversal.
 4. Use a recursive function to traverse and print the nodes in DFS order.

Test Case Example:

Input=
5
01010
10000
10011
10100
00100
1

Output=
The DFS Traversal of Graph is :
1-2-4-3-5-
*/
//Start writing program from here
#include <stdio.h>

int graph[20][20], visited[20], n;

void DFS(int v)
{
int i;
visited[v] = 1;
printf("%d - ", v + 1);

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

{
if(graph[v][i] == 1 && !visited[i])
DFS(i);
}
}

int main()
{
int i, j, start;

scanf("%d", &n);

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

{
for(j = 0; j < n; j++)
{
scanf("%d", &graph[i][j]);
}
}
 scanf("%d", &start);

printf("The DFS Traversal of Graph is :\n");

DFS(start - 1);

return 0;
}

TASK 11B

/*
LAB TASK 11B
11 b. Implement a C program for BFS traversal on graph.
Note : Also visit the finally unvisited nodes.
Do test for invalid start vertex.
INPUT FORMAT: FIRST LINE NO OF VERTICES 'n',
IN NEXT 'n' LINES THE ADJACENCY MATRIX OF THE GRAPH.
LAST LINE IS THE START VERTEX OF THE BFS TRAVERSAL.
OUTPUT FORMAT: DISPLAY THE BFS TARVERSAL AS PER THE GIVEN TEST CASE
FORMAT.
ALSO HANDLE NOT POSSIBLE SITUATIONS ACCORDINGLY.

Sample Test Cases:

case=t8
input=
4
0101
1011
0101
0110
3
output=
"THE BREADTH FIRST SEARCH TRAVERSAL OF THE GIVEN GRAPH IS :
3 -> 2 -> 4 -> 1 ->"
*/
//Start writing program from here
#include <stdio.h>

#define MAX 100

int graph[MAX][MAX];
int visited[MAX];
int queue[MAX];
int n;
int front=0,rear=-1;
void bfs(int start)
{
queue[++rear] = start;
visited[start] = 1;

while (front <= rear)

{
int current = queue[front++];
printf(" %d ->", current + 1);

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

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

int main()
{
int start;

scanf("%d", &n);

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

{
for (int j = 0; j < n; j++)
{
scanf("%d", &graph[i][j]);
}
}

scanf("%d", &start);

if (start < 1 || start > n)

{
printf("Invalid Start Vertex - Cannot perform BFS.");
return 0;
}

printf("THE BREADTH FIRST SEARCH TRAVERSAL OF THE GIVEN GRAPH IS :\n");

bfs(start - 1);
 for (int i = 0; i < n; i++)
{
if (visited[i] == 0)
{
bfs(i);
}
}

return 0;
}

TASK 12A

/*
LAB TASK 12A
QUESTION:
Task 12A. Implement a C program for the following operations on Hashing:
i. insert ii. delete iii. search iv. Display
v Exit
Also Check for Invalid Case.
Note: Initilaize the Hash Table with -1.
Also Use MAX size as 5.
Test Cases:
case=t4
input=
1
16
1
67
1
56
1
20
1
78
4
3
20
3
55
2
16
3
67
5
output=
Operations on Hash Table
16 is inserted at H[1]
67 is inserted at H[2]
Collision at H[1] in Hash table - Cannot Insert 56
20 is inserted at H[0]
78 is inserted at H[3]
Hash Table
H[0] = 20
H[1] = 16
H[2] = 67
H[3] = 78
H[4] = -1
20 is found in Hash Table
55 is not found in Hash Table
16 is found in the Hash table at H[1] and deleted from it.
67 is found in Hash Tab
*/
//Start writing program from here
#include <stdio.h>

#define MAX 5

int hashTable[MAX];

void initialize()
{
int i;
for (i = 0; i < MAX; i++)
hashTable[i] = -1;
}

void insert(int key)

{
int index = key % MAX;

if (hashTable[index] == -1)
{
hashTable[index] = key;
printf("%d is inserted at H[%d]\n", key, index);
}
else
{
printf("Collision at H[%d] in Hash table - Cannot Insert %d\n", index, key);
}
}
void deleteKey(int key)
{
int index = key % MAX;

if (hashTable[index] == key)
{
hashTable[index] = -1;
printf("%d is found in the Hash table at H[%d] and deleted from it.\n", key, index);
}
else
{
printf("%d is not found in the Hash table - Cannot Delete\n", key);
}
}

void search(int key)

{
int index = key % MAX;

if (hashTable[index] == key)
{
printf("%d is found in Hash Table\n", key);
}
else
{
printf("%d is not found in Hash Table\n", key);
}
}

void display()
{
int i;
printf("Hash Table\n");
for (i = 0; i < MAX; i++)
{
printf("H[%d] = %d\n", i, hashTable[i]);
}
}

int main()
{
int choice, key;

initialize();

printf("Operations on Hash Table:\n");

 while (1)
{
if (scanf("%d", &choice) != 1)
break;

switch (choice)
{
case 1:
scanf("%d", &key);
insert(key);
break;

case 2:
scanf("%d", &key);
deleteKey(key);
break;

case 3:
scanf("%d", &key);
search(key);
break;

case 4:
display();
break;

case 5:
return 0;

default:
printf("Invalid Choice\n");
}
}

return 0;
}