Array Implementation of List ADTs

[Link] Date:

AIM:
To implement list concept using array and performing the following operations.

1. Create the list.

2. Insert elements into the list at different positions.
3. Display the list.
4. Delete an element and display the list again.
5. Search for an element and display its position if found.

ALGORITHM:

1. Algorithm for Defining list structure:

Steps:

1. Define MAX_SIZE as the maximum capacity of the list.

2. Define a structure List that contains:

An array to hold the elements.

An integer size to keep track of the number of elements in the list.

2. Algorithm for Create Operation:

Steps:

1. Initialize the size field of the list to 0.

2. The list is now ready to be used.

3. Algorithm for Insert Operation:

Steps:

1. Check if the list is full. If it is, print a message.

2. Check if the position is valid. If not, print a message.
3. Shift elements to the right to make space for the new element.
4. Insert the new element at the specified position.
5. Increment the size of the list.
4. Algorithm for Deletion Operation:

Steps:

1. Check if the list is empty. If it is, print a message.

2. Check if the position is valid. If not, print a message.
3. Shift elements to the left to fill the gap left by the deleted element.
4. Decrement the size of the list.

5. Algorithm for Display Operation/Traversing a list

Steps:

1. Check if the list is empty. If it is, print a message.

2. Otherwise, iterate through the array and print each element.

6. Algorithm for Search Operation:

Steps:

1. Iterate through the list.

2. If the element is found, return its position.
3. If the element is not found, return -1.
PRPGRAM:
#include<stdio.h>
#include<conio.h>
#define maxsize 10
int list[maxsize],n;
void Create();
void Insert();
void Delete();
void Display();
void Search();
void main()
{
int choice;
clrscr();
do
{
printf("\n Array Implementation of List\n");
printf("\[Link]\n");
printf("\[Link]\n");
printf("\[Link]\n");
printf("\[Link]\n");
printf("\[Link]\n");
printf("\[Link]\n");
printf("\n Enter your choice:\t");
scanf("%d",&choice);
switch(choice)
{
case 1: Create();
break;
case 2: Insert();
break;
case 3: Delete();
break;
case 4: Display();
break;
case 5: Search();
break;
case 6: exit(1);
default:
printf("\n Enter option between 1 - 6\n");
break;
}
}
while(choice<7);
}
void Create()
{
int i;
printf("\n Enter the number of elements to be added in the list:\t");
scanf("%d",&n);
printf("\n Enter the array elements:\t");
for(i=0;i<n;i++)
scanf("%d",&list[i]);
Display();
}
void Insert()
{
int i,data,pos;
printf("\n Enter the element to be inserted:\t");
scanf("%d",&data);
printf("\n Enter the index-position at which element to be inserted:\t");
scanf("%d",&pos);
for(i = n-1 ; i >= pos ; i--)
list[i+1] = list[i];
list[pos] = data;
n+=1;
Display();
}
void Delete( )
{
int i,pos;
printf("\n Enter the index-position of the data to be deleted:\t");
scanf("%d",&pos);
printf("\n The data deleted is:\t %d", list[pos-1]);
for(i=pos;i<n-1;i++)
list[i]=list[i+1];
n=n-1;
Display();
}
void Display()
{
int i;
printf("\n*Elements in the array*\n");
for(i=0;i<n;i++)
printf("%d\t",list[i]);
}
void Search()
{
int search,i,count = 0;
printf("\n Enter the element to be searched:\t");
scanf("%d",&search);
for(i=0;i<n;i++)
{
if(search == list[i])
{
count++;
}}
if(count==0)
printf("\n Element not present in the list");
else
printf("\n Element present in the list");
}

OUTPUT:

Array Implementation of List

[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
Enter your choice: 1

Enter the number of elements to be added in the list: 5

Enter the array elements: 10 20 30 40 50
**********Elements in the array**********
10 20 30 40 50
Array Implementation of List
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
Enter your choice: 2
Enter the data to be inserted: 25
Enter the index-position at which element to be inserted: 2

**********Elements in the array**********

10 20 25 30 40 50
Array Implementation of List
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]

Enter your choice: 3

Enter the position of the data to be deleted: 2
The data deleted is: 3
**********Elements in the array**********
10 20 30 40 50

Array Implementation of List

[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
Enter your choice: 5
Enter the element to be searched: 50
Element present in the list
 Array Implementation of List
[Link]
2. Insert
[Link]
[Link]
[Link]
6. Exit
Enter your choice:6

IENGINEERINGCOLLEGE

(Autonomous)

MAX. MARKS
DESCRIPTION
MARKS AWARDED

Preparation&
20
Conduction

Observation &Results 10

Record Completion 05

Viva Voce 05

TOTAL 40

RESULT:
Thus, the above program for List Implementation using array is executed
and all of its operations are implemented successfully.
 Linked List Implementation of Singly Linked List.
[Link] Date:

AIM:
To implement singly and Doubly linked list and performing insert, search, display and
delete
operations.

ALGORITHMS:

1. Algorithm for Creation:

Steps:

1. Allocate memory for a new node.

2. Set the data field of the new node.
3. Initialize the next pointer to NULL.
4. Return the new node.

2. Algorithm for Display:

Steps:

1. Start from the head of the list.

2. Traverse each node, printing its data.
3. Move to the next node using the next pointer.
4. Print "NULL" at the end to indicate the end of the list.

3. Algorithm for Insertion at the Beginning:

Steps:

1. Allocate memory and create a new node.

2. Point the new node's next to the current head.
3. Update the head pointer to the new node.

4. Algorithm for Insertion at the End:

Steps:

1. Allocate memory and create a new node.

2. If the list is empty, make the new node the head.
3. Otherwise, traverse to the last node.
4. Point the last node's next to the new node.
5. Algorithm for Insertion at a Specific Position:

Steps:

1. Allocate memory and create a new node.

2. If inserting at position 1, make the new node the head.
3. Traverse to the node just before the desired position.
4. If the position is out of bounds, print an error message.
5. Set the new node's next to the current node at that position.
6. Update the previous node's next to the new node.

6. Algorithm for Delete a Node at the Beginning:

Steps:

1. Check if the list is empty. If it is, return with a message.

2. Save the current head node in a temporary variable.
3. Update the head to the next node.
4. Free the memory of the old head node.

7. Algorithm for Delete a Node at the End:

Steps:

1. Check if the list is empty. If it is, return with a message.

2. If the list has only one node, free that node and set head to NULL.
3. Traverse the list to find the second last node.
4. Free the memory of the last node.
5. Set the next of the second last node to NULL.

8. Algorithm for Delete a Node at a Specific Position:

Steps:

1. Check if the list is empty. If it is, return with a message.

2. If the position is 1, delete the head node as in the beginning deletion process.
3. Traverse the list to find the node just before the position you want to delete.
4. If the position is out of bounds, return with an error message.
5. Adjust the next pointer of the previous node to skip the node to be deleted.
6. Free the memory of the node to be deleted.
PROGRAM:1
// Singly Lined List Creation, Display and Insertion//
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void create();
void display();
void insertatbegin();
void insertatend();
void insertatspecific();
struct node
{
int data;
struct node *next;
};
struct node *head;
struct node *tail;
struct node *new;
struct node *temp;
void main()
{
int n;
clrscr();
do
{
printf("* Singly Lined List *\n"); printf("_\n\
n");
printf("[Link] \n");
printf("[Link] \n");
printf("[Link] at the Beginning \n");
printf("[Link] at the Ending \n");
printf("[Link] at the specific Position:\n");
printf("[Link] \n");
printf("Enter your choice:\n");
scanf("%d",&n);
switch(n)
{
case 1:
create();
break;
case 2:
display();
break;
case 3:
insertatbegin();
break;
case 4:
insertatend();
break;
case 5:
insertatspecific();
break;
case 6:
exit(0);
break;
}
}while(1);
}

void create()
{
intval;
char ch;
do
{
new=(struct node *)malloc(sizeof(struct node));
printf("Enter the node value:");
scanf("%d",&val);
new->data=val;
new->next=NULL;
if(head==NULL)
{
head=new;
tail=new;
}
else
{
tail->next=new;
tail=new;
}

printf("Do you want to continue:");

fflush(stdin);// cleans the input buffer
scanf("%c",&ch);
}while(ch=='y');
}
void display()
{
//Node current will point to head
temp=head;
printf("Nodes of singly linked list: \n");
while(temp != NULL) {
//Prints each node by incrementing pointer
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}

void insertatbegin()
{
int value;
new=(struct node*)malloc(sizeof( struct node));
printf("Enter the node value to insert:\n");
scanf("%d",&value);
new->data=value;
new->next=head;
head=new;
}

void insertatend()
{
int value;
new=(struct node*)malloc(sizeof( struct node));
printf("Enter the node value to insert:\n");
scanf("%d",&value);
new->data=value;
new->next=NULL;
tail->next=new;
tail=new;
}
void insertatspecific()
{
intvalue,pos,I;
temp=head;
new=(struct node*)malloc(sizeof( struct node));
printf("Enter the node value to insert:\n");
scanf("%d",&value);
new->data=value;
printf("Enter the position to Insert:\n");
scanf("%d",&pos);
for(I=0;I<pos-1; I++)
{
temp=temp->next;
}
new->next=temp->next;
temp->next=new;
}
OUTPUT:
Singly Linked List Creation, Display, Insertion:
1. Create
2. Display
3. Insertion at the Beginning
4. Insertion at the Ending
5. Insertion at the Specific Position
6. Exit
1. Linked list Creation
Enter your Choice: 1
Enter the node value: 10
Do you want to continue: y
Enter the node value: 20
Do you want to continue: y
Enter the node value: 30
Do you want to continue: y
Enter the node value: 40
Do you want to continue: n
2. Display:
Enter your Choice: 2
Nodes of Singly linked list: 10 20 30 40
3. Insertion at the
Beginning: Enter
your Choice: 3
Enter the node value to insert: 5
Enter your Choice: 2
Nodes of Singly linked list: 5 10 20 30 40
4. Insertion at the
Ending: Enter your
Choice: 4
Enter the node value to insert: 50
Enter your Choice: 2
 Nodes of Singly linked list: 5 10 20 30 40 50
[Link] at the Specific Position:
Enter your Choice: 5
Enter the node value to insert: 25
Enter the position to insert: 3
Enter your Choice: 2
Nodes of Singly linked list: 5 10 20 25 30 40 50
6. Exit:
Enter your Choice: 6
PROGRAM: 2

// Singly Linked List Creation, Display and Deletion //

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void create();
void display();
void deleteatbegin();
void deleteatend();
void deleteatspecific();
struct node
{
int data;
struct node *next;
};
struct node *head;
struct node *tail;
struct node *new;
struct node *temp;
void main()
{
int n;
do
{
printf("* Singly Lined List *\n"); printf("_\n\
n");
printf("[Link] \n");
printf("[Link] \n");
printf("[Link] at the Beginning \n");
printf("[Link] at the Ending \n");
printf("[Link] at the specific Location:\n");
printf("[Link] \n");
printf("Enter your choice:\n");
scanf("%d",&n);
switch(n)
{
case 1:
create();
break;
case 2:
display();
break;
case 3:
deleteatbegin();
break;
case 4:
deleteatend();
break;
case 5:
deleteatspecific();
break;
case 6:
exit(0);
break;
}
}while(1);
}
void create()
{
intval;
char ch;
do
{
new=(struct node *)malloc(sizeof(struct node));
printf("Enter the node value:\n;");
scanf("%d",&val);
new->data=val;
new->next=NULL;
if(head==NULL)
{
head=new;
tail=new;
}
else
{
tail->next=new;
tail=new;
}

printf("Do you want to continue:");

fflush(stdin);
scanf("%c",&ch);
}while(ch=='y');
}

void display()
{
//Node current will point to head
 temp=head;
printf("Nodes of singly linked list: \n");
while(temp != NULL) {
//Prints each node by incrementing pointer
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}

void deleteatbegin()
{
temp=head;
head=head->next;
temp->next=NULL;
}

void deleteatend()
{
temp=head;
while(temp->next!=tail)
{
temp=temp->next;
}
temp->next=NULL;
tail=temp;
}
 void deleteatspecific()
{
intpos,I;
printf("Enter the position to Delete:\n");
scanf("%d",&pos);
temp=head;
for(I=0;I<pos-1; I++)
{
temp=temp->next;
}
temp->next=temp->next->next;
}

OUTPUT:

Singly Linked List Creation, Display, Deletion:

1. Create
2. Display
3. Deletion at the Beginning
4. Deletion at the Ending
5. Deletion at the Specific Position
6. Exit
1. Linked list Creation
Enter your Choice: 1
Enter the node value: 10
Do you want to continue: y
Enter the node value: 20
Do you want to continue: y
Enter the node value: 30
Do you want to continue: y
Enter the node value: 40
 Do you want to continue: n
2. Display:
Enter your Choice: 2
Nodes of Singly linked list: 10 20 30 40
3. Deletion at the
Beginning: Enter
your Choice: 3 Enter
your Choice: 2
Nodes of Singly linked list: 20 30 40
4. Deletion at the
Ending: Enter your
Choice: 4 Enter your
Choice: 2
Nodes of Singly linked list: 20 30

5. Deletion at the Specific

Position: Enter your
Choice: 5
Enter the position to delete: 1
Enter your Choice: 2
Nodes of Singly linked list: 20

6. Exit:
Enter your Choice: 6
 IENGINEERINGCOLLEGE

(Autonomous)

MAX. MARKS
DESCRIPTION
MARKS AWARDED

Preparation&
20
Conduction

Observation &Results 10

Record Completion 05

Viva Voce 05

TOTAL 40

RESULT:

Thus, the above Singly Linked List are created and all of its

operations are implemented successfully.

 Linked List Implementation of Doubly Linked List.
[Link] Date:

AIM:
To implement singly and Doubly linked list and performing insert, search, display and
delete
operations.

ALGORITHMS:

1. Algorithm for Creation:

Steps:

1. Allocate memory for a new node.

2. Set the data field of the new node.
3. Initialize the prev and next pointers to NULL.
4. Return the new node.

2. Algorithm for Display:

Steps:

1. Start from the head of the list.

2. Traverse each node, printing its data.
3. Move to the next node using the next pointer.
4. Print "NULL" at the end to indicate the end of the list.

3. Algorithm for Insertion at the Beginning:

Steps:

1. Allocate memory and create a new node.

2. If the list is empty, make the new node the head.
3. If the list is not empty, set the new node's next to the current head.
4. Update the current head's prev to point to the new node.
5. Update the head to the new node.

4. Algorithm for Insertion at the End:

Steps:

1. Allocate memory and create a new node.

2. If the list is empty, make the new node the head.
3. Otherwise, traverse to the last node.
4. Set the last node's next to the new node.
5. Set the new node's prev to the last node.
5. Algorithm for Insertion at a Specific Position:

Steps:

1. Allocate memory and create a new node.

2. If the position is 1, insert the new node at the beginning.
3. Otherwise, traverse to the node just before the desired position.
4. If the position is out of bounds, print an error message and free the new node.
5. Set the new node's next to the current node at that position.
6. Set the new node's prev to the previous node.
7. Adjust the pointers of the adjacent nodes to accommodate the new node.

6. Algorithm for Delete a Node at the Beginning:

Steps:

1. Check if the list is empty. If it is, return with a message.

2. Save the current head node in a temporary variable.
3. Update the head to the next node.
4. If the new head is not NULL, set its prev pointer to NULL.
5. Free the memory of the old head node.

7. Algorithm for Delete a Node at the End:

Steps:

1. Check if the list is empty. If it is, return with a message.

2. If the list has only one node, free that node and set head to NULL.
3. Traverse the list to find the last node.
4. Set the next pointer of the second last node to NULL.
5. Free the memory of the last node.

8. Algorithm for Delete a Node at a Specific Position:

Steps:

1. Check if the list is empty. If it is, return with a message.

2. If the position is 1, call the function to delete the node at the beginning.
3. Traverse the list to find the node at the desired position.
4. If the position is out of bounds, return with an error message.
5. Adjust the prev pointer of the node after the target node.
6. Adjust the next pointer of the node before the target node.
7. Free the memory of the target node.
PROGRAM: 1

//Doubly Lined List Creation, Display and Insertion//

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void create();
void display();
void insertatbegin();
void insertatend();
void insertatspecific();
struct node
{
int data;
struct node *next;
struct node *prev;
};
struct node *head;
struct node *tail;
struct node *new;
struct node *temp;
void main()
{
int n;
clrscr();
do
{
printf("* Doubly Linked List *\n");
printf(" \n\n");
printf("[Link] \n");
printf("[Link] \n");
printf("[Link] at the Beginning \
n"); printf("[Link] at the Ending \
n");
printf("[Link] at the specific Location:\n");
printf("[Link] \n");
printf("Enter your choice:\n");
scanf("%d",&n);
switch(n)
{
case 1:
create();
break;
case 2:
display();
break;
case 3:
insertatbegin();
break;
case 4:
insertatend();
break;
case 5:
insertatspecific();
break;
case 6:
exit(0);
break;
}
}while(1);
}
void create()
{
intval;
char ch;
do
{
new=(struct node *)malloc(sizeof(struct node));
printf("Enter the node value:");
scanf("%d",&val);
new->data=val;
new->next=NULL;
new->prev=NULL;
if(head==NULL)
{
head=new;
tail=new;
}
else
{
tail->next=new;
new->prev=tail;
tail=new;
}

printf("Do you want to continue:");

fflush(stdin);// cleans the input buffer
scanf("%c",&ch);
}while(ch=='y');
}
void display()
{
//Node current will point to head
temp=head;
printf("Nodes of Doubly linked list: \n");
while(temp != NULL) {
//Prints each node by incrementing pointer
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}

void insertatbegin()
{
int value;
new=(struct node*)malloc(sizeof( struct node));
printf("Enter the node value to insert:\n");
scanf("%d",&value);
new->data=value;
new->prev=NULL;
new->next=head;
head->prev=new;
head->prev=NULL;
head=new;
}

void insertatend()
{
int value;
new=(struct node*)malloc(sizeof( struct node));
printf("Enter the node value to insert:\n");
scanf("%d",&value);
new->data=value;
new->next=NULL;
new->prev=tail;
tail->next=new;
tail=new;
}

void insertatspecific()
{

intvalue,pos,I;
temp=head;
new=(struct node*)malloc(sizeof( struct node));
printf("Enter the node value to insert:\n");
scanf("%d",&value);
new->data=value;
printf("Enter the position to Inser:\n");
scanf("%d",&pos);
for(I=0;I<pos-1; I++)
{
temp=temp->next;
}

new->next=temp->next;
temp->next->prev=new;
temp->next=new;
new->prev=temp;
}
OUTPUT:
Doubly Linked List Creation, Display, Insertion:
1. Create
2. Display
3. Insertion at the Beginning
4. Insertion at the Ending
5. Insertion at the Specific Position
6. Exit
1. Linked list Creation
Enter your Choice: 1
Enter the node value: 10
Do you want to continue: y
Enter the node value: 20
Do you want to continue: y
Enter the node value: 30
Do you want to continue: y
Enter the node value: 40
Do you want to continue: n
2. Display:
Enter your Choice: 2
Nodes of Doubly linked list: 10 20 30 40
3. Insertion at the
Beginning: Enter
your Choice: 3
Enter the node value to insert: 5
Enter your Choice: 2
Nodes of Doubly linked list: 5 10 20 30 40
4. Insertion at the
Ending: Enter your
Choice: 4
Enter the node value to insert: 50
Enter your Choice: 2
Nodes of Doubly linked list: 5 10 20 30 40 50
[Link] at the Specific Position:
Enter your Choice: 5
Enter the node value to insert: 25
Enter the position to insert: 3
Enter your Choice: 2
Nodes of Doubly linked list: 5 10 20 25 30 40 50

6. Exit:
Enter your Choice: 6
PROGRAM: 2

//Doubly Lined List Creation, Display and Deletion//

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void create();
void display();
void deleteatbegin();
void deleteatend();
void deleteatspecific();
struct node
{
int data;
struct node *next;
struct node *prev;
};
struct node *head;
struct node *tail;
struct node *new;
struct node *temp;
void main()
{
int n;
clrscr();
do
{
printf("* Doubly Linked List *\n");
printf(" \n\n");
printf("[Link] \n");
printf("[Link] \n");
printf("[Link] at the Beginning \
n"); printf("[Link] at the Ending \
n");
printf("[Link] at the specific Location:\n");
printf("[Link] \n");
printf("Enter your choice:");
scanf("%d",&n);
switch(n)
{
case 1:
create();
break;
case 2:
display();
break;
case 3:
deleteatbegin();
break;
case 4:
deleteatend();
break;
case 5:
deleteatspecific();
break;
case 6:
exit(0);
break;
}
}while(1);
}
void create()
{
intval;
char ch;
do
{
new=(struct node *)malloc(sizeof(struct node));
printf("Enter the node value:");
scanf("%d",&val);
new->data=val;
new->next=NULL;
new->prev=NULL;
if(head==NULL)
{
head=new;
tail=new;
}
else
{
tail->next=new;
new->prev=tail;
tail=new;
}

printf("Do you want to continue:");

fflush(stdin);// cleans the input buffer
scanf("%c",&ch);
}while(ch=='y');
}
void display()
{
//Node current will point to head
temp=head;
printf("Nodes of Doubly linked list: \n");
while(temp != NULL) {
//Prints each node by incrementing pointer
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}

void deleteatbegin()
{
temp=head;
head=head->next;
temp->next=NULL;
head->prev=NULL;
}

void deleteatend()
{
temp=tail;
tail=tail->prev;
temp->prev=NULL;
tail->next=NULL;
}

void deleteatspecific()
{
intpos,I;
printf("Enter the position to delete:\n");
scanf("%d",&pos);
 temp=head;
for(I=0;I<pos-1; I++)
{
temp=temp->next;
}
temp->next=temp->next->next;
temp->next->prev=temp;
}

OUTPUT:
Doubly Linked List Creation, Display, Deletion:
1. Create
2. Display
3. Deletion at the Beginning
4. Deletion at the Ending
5. Deletion at the Specific Position
6. Exit
1. Linked list Creation
Enter your Choice: 1
Enter the node value: 10
Do you want to continue: y
Enter the node value: 20
Do you want to continue: y
Enter the node value: 30
Do you want to continue: y
Enter the node value: 40
Do you want to continue: n
2. Display:
Enter your Choice: 2
Nodes of Doubly linked list: 10 20 30 40
3. Deletion at the
Beginning: Enter
your Choice: 3 Enter
your Choice: 2
 Nodes of Doubly linked list: 20 30 40
4. Deletion at the
Ending: Enter your
Choice: 4 Enter your
Choice: 2
Nodes of Doubly linked list: 20 30

5. Deletion at the Specific

Position: Enter your
Choice: 5
Enter the position to delete: 1
Enter your Choice: 2
Nodes of Doubly linked list: 20

6. Exit:
Enter your Choice: 6
 IENGINEERINGCOLLEGE

(Autonomous)

MAX. MARKS
DESCRIPTION
MARKS AWARDED

Preparation&
20
Conduction

Observation &Results 10

Record Completion 05

Viva Voce 05

TOTAL 40

RESULT:

Thus the above Doubly Linked List are created and all of its

operations are implemented successfully.

 Array Implementation of Stack ADTs.

[Link] Date:

AIM:
To implement the program for Push, Pop and Display operations in Stack using
Array.

ALGORITHMS:

ALGORITHM FOR PUSH OPERATION:

Step 1: If Top=Max-1

Print “Overflow : Stack is full” and Exit

End If

Step 2: Top=Top+1

Step 3: Stack[TOP]=Element

Step 4: End

ALGORITHM FOR POP OPEARTION:

Step 1: If TOP=-1

Print “Underflow: Stack is empty” and Exit

End if

Step 2: Set Del_element=Stack[Top]

Step 3: Top=Top-1

Step 4: Del_Element

Step 5: End
PROGRAM:
#include<stdio.h>
int stack[100],choice,n,top,x,i;
void push(void);
void pop(void);
void display(void);
int main()
{
//clrscr();
top=-1;
printf("\n Enter the size of STACK[MAX=100]:");
scanf("%d",&n);
printf("\n\t STACK OPERATIONS USING ARRAY");
printf("\n\t ");
printf("\n\t [Link]\n\t [Link]\n\t [Link]\n\t [Link]");
do
{
printf("\n Enter the Choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
 case 3:
{
display();
break;
}
case 4:
{
printf("\n\t EXIT POINT ");
break;
}
default:
{
printf ("\n\t Please Enter a Valid Choice(1/2/3/4)");
}

}
}
while(choice!=4);
return 0;
}
void push()
{
if(top>=n-1)
{
printf("\n\tSTACK is over flow");

}
else
{
printf(" Enter a value to be pushed:");
scanf("%d",&x);
 top++;
stack[top]=x;
}
}
void pop()
{
if(top<=-1)
{
printf("\n\t Stack is under flow");
}
else
{
printf("\n\t The popped elements is %d",stack[top]);
top--;
}
}
void display()
{
if(top>=0)
{
printf("\n The elements in STACK \n");
for(i=top; i>=0; i--)
printf("\n%d",stack[i]);
printf("\n Press Next Choice");
}
else
{
printf("\n The STACK is empty");
}

}
OUTPUT:

Enter the size of STACK[MAX=100]:10

STACK OPERATIONS USING ARRAY

1. PUSH

2. POP

3. DISPLAY

4. EXIT

Enter the Choice:1

Enter a value to be pushed:12

Enter the Choice:1

Enter a value to be pushed:24

Enter the Choice:1

Enter a value to be pushed:98

Enter the Choice:3

The elements in STACK

98

24

12

Press Next Choice

Enter the Choice:2

The popped elements is 98

Enter the Choice:3

The elements in STACK

24

12

Press Next Choice

Enter the Choice:4

EXIT POINT
 IENGINEERINGCOLLEGE

(Autonomous)

MAX. MARKS
DESCRIPTION
MARKS AWARDED

Preparation&
20
Conduction

Observation &Results 10

Record Completion 05

Viva Voce 05

TOTAL 40

RESULT:
Thus, the program for Push, Pop and Display operations in Stack was implemented
and executed successfully.
 IMPLEMENTATION OF EVALUATING THE POSTFIX EXPRESSION

[Link] Date:

AIM:

To write the C Program in implementing the evaluation of postfix expression using

Stack ADT.

ALGORITHM:

1. Create an integer array stack[] of size 20.

Initialize top to -1, which represents an empty stack.
2. Increment the top by 1 and assign the given value x to stack[top].
3. Return the value at stack[top] and then decrement the top by 1.
4. Declare a character array exp[] of size 20 to store the input expression.
5. Declare integer variables n1, n2, n3, and num to store operands and result.
6. Read the postfix expression from the user.
7. Initialize a pointer e to point to the beginning of the postfix expression exp.
8. Loop through each character of the expression until the end (*e != '\0'):
9. If the current character is a digit:Convert the character to its numeric equivalent by subtracting '0'
(ASCII 48) from [Link] this numeric value onto the stack.
10. If the current character is an operator (+, -, *, /):Pop two values from the stack (operands n1 and
n2).
11. Apply the operator on these operands:
+ → Add n1 and n2.
- → Subtract n1 from n2.
* → Multiply n1 and n2.
/ → Divide n2 by n1.
12. Push the result (n3) back onto the stack.
13. After processing the entire expression, the final result will be the last value left in the stack.
14. Pop this value and print it as the result.
[Link] 0 to indicate successful completion.
PROGRAM:

#include<stdio.h>
#include<ctype.h>
int stack[20];
int top = -1;
void push(int x)
{
stack[++top] = x;
}
int pop()
{
return stack[top--];
}
int main()
{
char exp[20];
char *e;
int n1,n2,n3,num;
printf("Enter the expression :: ");
scanf("%s",exp);
e = exp;
while(*e != '\0')
{
if(isdigit(*e))
{
num = *e - 48;
push(num);
}
else
{
n1 = pop();
n2 = pop();
switch(*e)

{
case '+':
{
n3 = n1 + n2;
break;
}
case '-':
{
n3 = n2 - n1;
break;
}
case '*':
{
n3 = n1 * n2;
 break;
}
case '/':
{
n3 = n2 / n1;
break;
}
}
push(n3);
}
e++;
}
printf("\nThe result of expression %s = %d\n\n",exp,pop());
return 0;
}

OUTPUT:

Enter the expression :: 234+*

The result of expression 234+* = 14

 IENGINEERINGCOLLEGE

(Autonomous)

MAX. MARKS
DESCRIPTION
MARKS AWARDED

Preparation&
20
Conduction

Observation &Results 10

Record Completion 05

Viva Voce 05

TOTAL 40

RESULT:

Thus, the evaluation of postfix expression is successfully implemented using stack ADT.
 IMPLEMENTATION OF CONVERTING INFIX TO POSTFIX EXPRESSION

[Link] Date:

AIM:

To write the C Program in implementing the conversion of infix to postfix expression using
Stack ADT.

ALGORITHM:

1. Create a stack[] of size 100 to store operators and parentheses.

2. Initialize top to -1, representing an empty stack.
[Link] top by 1 and store the character x in stack[top].
[Link] the stack is empty (i.e., top == -1), return -1.
5. Otherwise, return the value at stack[top] and then decrement top.
6. Return the precedence level of an operator:
'(': Priority 0 (lowest priority)
'+' or '-': Priority 1
'*' or '/': Priority 2
Return 0 for any other character.
7. Declare a character array exp[] to store the input infix expression.
8. Declare a pointer e to traverse the input expression and a variable x to hold characters popped
from the stack.
9. Read the infix expression from the user.
10. Initialize pointer e to point to the first character of exp.
11. Loop through each character of the expression until the end (*e != '\0'):
[Link] the current character is an operand (digit or letter), print it directly.
[Link] the left parenthesis '(' onto the stack.
14. Pop and print operators from the stack until a left parenthesis '(' is encountered. Do not print '('.
15. Pop and print operators from the stack as long as the operator at the top of the stack has greater
or equal precedence compared to the current operator.
16. Push the current operator onto the stack.
17. After processing the entire expression, pop and print any remaining operators from the stack.
18. Return 0 to indicate successful completion.
PROGRAM:

#include<stdio.h>
#include<ctype.h>
char stack[100];
int top = -1;

void push(char x)
{
stack[++top] = x;
}
char pop()
{
if(top == -1)
return -1;
else
return stack[top--];
}
int priority(char x)
{
if(x == '(')
return 0;
if(x == '+' || x == '-')
return 1;
if(x == '*' || x == '/')
return 2;
return 0;
}
int main()
{
char exp[100];
char *e, x;
printf("Enter the expression : ");
scanf("%s",exp);
printf("\n");
e = exp;

while(*e != '\0')
{
if(isalnum(*e))
printf("%c ",*e);
else if(*e == '(')
push(*e);
else if(*e == ')')
{
while((x = pop()) != '(')
printf("%c ", x);
}
 else
{
while(priority(stack[top]) >= priority(*e))
printf("%c ",pop());
push(*e);
}
e++;
}
while(top != -1)
{
printf("%c ",pop());
}return 0;
}

OUTPUT:

Enter the expression : (a+b)*c+(d-a)

ab+c*da-+
 IENGINEERINGCOLLEGE

(Autonomous)

MAX. MARKS
DESCRIPTION
MARKS AWARDED

Preparation&
20
Conduction

Observation &Results 10

Record Completion 05

Viva Voce 05

TOTAL 40

RESULT:

Thus, the conversion of infix to postfix expression is successfully implemented using stack
ADT.
 IMPLEMENTATION OF QUEUE AND ITS OPERATIONS

[Link] Date:

AIM:
To write the C Program in implementing the queue and its operations using Array.

ALGORITHMS:

Algorithm: Enqueue Operation

Step 1: Check if the Queue is Full

 If rear == MAX_SIZE - 1, the queue is full and no more elements can be added.
Output: "Queue is full" and terminate the operation.
Step 2: Check if the Queue is Empty
 If the queue is empty, i.e., front == -1:
Set front = 0 because you are inserting the first element.
Step 3: Increment the Rear Pointer
 Increment the rear pointer by 1 to point to the next available position.
rear = rear + 1
Step 4: Insert the Element
 Insert the new element at the position indicated by rear in the array.
queue[rear] = element
Step 5: End of Operation
 Print a message or simply end the operation after successfully adding the element.

Algorithm: Dequeue Operation

1. Start
2. Check if the Queue is Empty:
If front == -1 or front > rear (i.e., no elements to remove) Then:
 Print "Queue is empty!"
 Return // Terminate the operation as there are no elements to remove.
3. Access the Element at the Front:
Set x = queue[front] // Store the element at the front index for removal.
4. Check if the Queue Has Only One Element:
If front == rear Then:
 Set front = -1 and rear = -1 // Reset the queue to the empty state after
removing the only element.
5. Move the Front Pointer:
Else:
 Set front = front + 1 // Move the front pointer to the next element.
6. Print: "Element x has been dequeued."
7. Return x (the dequeued element).
8. End
Algorithm: Display Operation
1. Start
2. Check if the Queue is Empty:
If front == -1 or front > rear Then:
 Print "Queue is empty!"
 Return // Terminate the display operation as there are no elements to show.
3. Traverse and Display Elements:
For i = front to rear, do:
 Print queue[i] // Print each element from front to rear.
4. End
PROGRAM:

#include<stdio.h>
#include<stdlib.h>
#define n 5
int main()
{
int queue[n],ch=1,front=0,rear=0,i,j=1,x=n;
printf("Queue using Array");
printf("\[Link] \[Link] \[Link] \[Link]");
while(ch)
{
printf("\nEnter the Choice:");
scanf("%d",&ch);
switch(ch)
{
case 1:
if(rear==x)
printf("\n Queue is Full");
else
{
printf("\n Enter no %d:",j++);
scanf("%d",&queue[rear++]);
}
break;
case 2:
if(front==rear)
{
printf("\n Queue is empty");
}
else
{
printf("\n Deleted Element is %d",queue[front++]);
x++;
}
break;
case 3:
printf("\nQueue Elements are:\n ");
if(front==rear)
printf("\n Queue is Empty");
else
{
for(i=front; i<rear; i++)
{
printf("%d",queue[i]);
printf("\n");
}
break;
 case 4:
exit(0);
default:
printf("Wrong Choice: please see the options");
}
}
}
return 0;
}

OUTPUT:
Queue using Array
[Link]
[Link]
[Link]
[Link]
Enter the Choice:1
Enter no 1:2
Enter the Choice:1
Enter no 2:3
Enter the Choice:1
Enter no 3:4
Enter the Choice:1
Enter no 4:5
Enter the Choice:2
Deleted Element is 2
Enter the Choice:3
Queue Elements are:
3
4
5
Enter the Choice:4
 IENGINEERINGCOLLEGE

(Autonomous)

MAX. MARKS
DESCRIPTION
MARKS AWARDED

Preparation&
20
Conduction

Observation &Results 10

Record Completion 05

Viva Voce 05

TOTAL 40

RESULT:
Thus, the queue and its operations is successfully implemented using Array.
 APPLICATIONS OF QUEUE ADTs.

[Link] Date:

Aim:
To write the C Program in implementing the Applications of Queue.

ALGORITHMS:

Enqueue Operation Algorithm (Adding an element to the queue):

Goal: Insert an element at the rear of the queue.

1. Start
2. Input: Element x to be enqueued.
3. Check if the Queue is Full:
If rear == MAX - 1 Then:
Print "Queue is full!"
Return // Terminate the operation.
4. Check if the Queue is Empty:
If front == -1 Then:
Set front = 0 // Initialize the queue for the first element.
5. Increment the Rear Pointer:
Set rear = rear + 1
6. Insert the Element:
queue[rear] = x
7. Print: "Element x enqueued."
8. End

2. Dequeue Operation Algorithm (Removing an element from the queue)

Goal: Remove an element from the front of the queue.

1. Start
2. Check if the Queue is Empty:
If front == -1 or front > rear Then:
Print "Queue is empty!"
Return // Terminate the operation.
3. Access the Element at the Front:
Set x = queue[front]
4. Check if the Queue Has Only One Element:
If front == rear Then:
Set front = -1 and rear = -1 // Reset the queue to the empty state.
5. Else Move the Front Pointer:
Set front = front + 1
6. Print: "Element x dequeued."
7. Return x
8. End
3. Display Operation Algorithm (Showing all elements in the queue)

Goal: Display all elements from front to rear of the queue.

1. Start
2. Check if the Queue is Empty:
If front == -1 or front > rear Then:
Print "Queue is empty!"
Return // Terminate the operation.
3. Traverse the Queue:
For i = front to rear:
Print queue[i]
4. End
PROGRAM:

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

#define MAX 5 // Maximum size of the queue

// Global variables for the queue

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

// Function to check if the queue is full

int isFull() {
return rear == MAX - 1;
}

// Function to check if the queue is empty

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

// Function to enqueue (add) an element to the queue

void enqueue(int element) {
if (isFull()) {
printf("Queue is full! Cannot enqueue.\n");
} else {
if (front == -1) front = 0; // If the queue is initially empty
rear++;
queue[rear] = element;
printf("Enqueued: %d\n", element);
}
}

// Function to dequeue (remove) an element from the queue

void dequeue() {
if (isEmpty()) {
printf("Queue is empty! Cannot dequeue.\n");
} else {
printf("Dequeued: %d\n", queue[front]);
front++; // Move the front pointer to the next element
if (front > rear) { // Reset the queue if it's empty
front = -1;
rear = -1;
}
}
}
// Function to display the current elements in the queue
void displayQueue() {
if (isEmpty()) {
printf("Queue is empty!\n");
} else {
printf("Queue elements: ");
for (int i = front; i <= rear; i++) {
printf("%d ", queue[i]);
}
printf("\n");
}
}

// Main function demonstrating queue operations

int main() {
int choice, element;

while (1) {
printf("\nQueue Operations Menu:\n");
printf("1. Enqueue\n");
printf("2. Dequeue\n");
printf("3. Display Queue\n");
printf("4. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice) {
case 1:
printf("Enter element to enqueue: ");
scanf("%d", &element);
enqueue(element);
break;
case 2:
dequeue();
break;
case 3:
displayQueue();
break;
case 4:
exit(0);
break;
default:
printf("Invalid choice! Please try again.\n");
}
}

return 0;
}
OUTPUT:
Queue Operations Menu:
1. Enqueue
2. Dequeue
3. Display Queue
4. Exit
Enter your choice: 1
Enter element to enqueue: 10
Enqueued: 10

Queue Operations Menu:

1. Enqueue
2. Dequeue
3. Display Queue
4. Exit
Enter your choice: 1
Enter element to enqueue: 20
Enqueued: 20

Queue Operations Menu:

1. Enqueue
2. Dequeue
3. Display Queue
4. Exit
Enter your choice: 3
Queue elements: 10 20

Queue Operations Menu:

1. Enqueue
2. Dequeue
3. Display Queue
4. Exit
Enter your choice: 2
Dequeued: 10

Queue Operations Menu:

1. Enqueue
2. Dequeue
3. Display Queue
4. Exit
Enter your choice: 3
Queue elements: 20
 IENGINEERINGCOLLEGE

(Autonomous)

MAX. MARKS
DESCRIPTION
MARKS AWARDED

Preparation&
20
Conduction

Observation &Results 10

Record Completion 05

Viva Voce 05

TOTAL 40

RESULT:

Thus, the applications of queue were executed successfully and the Output is verified.
 IMPLEMENTATION OF BINARY SEARCH TREE

[Link] Date:

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

ALGORITHM:
1. Read integers
2. Create binary tree with the functions insert, del, findmin, display.
FOR INSERTION
If(T==null)
Newnode -> data=X;
Newnode->left=Null;
Newnode -> right=Null;
FOR DELETION
If(T== null)
Print(“element not found”)
FINDMIN
If(T!=null)
If(t->left==null)
Return T;
DISPLAY
If(T!=null)
Display T->left;
Printf(“%d\t”,T->data);
Display(T->right);
4. Visit in the order left, root, right,
5. Display the visited nodes
PROGRAM:
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
typedef struct tree *node;
node insert(int,node T);
node findmin(node T);
node del(int,node T);
void display(node T);
struct tree
{
int data;
struct tree *right,*left;
}*root;
void main()
{
node T=NULL;
int data,n,i=0;
char c;
clrscr();
printf("\n\n Enter the number of elements in the tree:");
scanf("%d", &n);
printf("\n Enter the elements to insert:\n");
while(i<n)
{
scanf("%d", &data);
T=insert(data,T);
i++;
}
printf("\n Elements displayed in inorder format are:\n");
display(T);
printf("\n Enter the element to delete:\n");
scanf("%d",&data);
T=del(data,T);
printf("\nThe contents of tree after deletion:\n");
display(T);
getch();
}
node insert(int X, node T)
{
struct tree *newnode;
newnode=malloc(sizeof (struct tree));
if(newnode==NULL)
printf("\n Out of space\n");
else
{
if(T==NULL)
{
newnode->data=X;
newnode->left=NULL;
newnode->right=NULL;
T=newnode;
}
else
{
if(X<T->data)
T->left=insert(X,T->left);
else
T->right=insert(X,T->right);
}
}
return T;
}
node del(int X,node T)
{
node tmpcell;
if(T==NULL)
printf("\nElement not found");
else if(X<T->data)
T->left=del(X,T->left);
else if(X>T->data)
T->right=del(X,T->right);
else if(T->left&&T->right)
{
tmpcell=findmin(T->right);
T->data=tmpcell->data;
T->right=del(T->data,T->right);
}
else
{
tmpcell=T;
if(T->left==NULL)
T=T->right;
else if(T->right==NULL)
T=T->left;
free(tmpcell);
}
return T;
}
node findmin(node T)
{
if(T!=NULL)
{
if(T->left==NULL)
return T;
else
return findmin(T->left);
}
 return(0);
}
void display(node T)
{
if(T!=NULL)
{
display(T->left);
printf("%d\t",T->data);
display(T->right);
}
}

OUTPUT:

Enter the number of elements in the tree: 5

Enter the elements to insert:

35
23
10
45
30

Elements displayed in in-order format are:

10 23 30 35 45

Enter the element to delete:

23

The contents of tree after deletion:

10 30 35 45
 IENGINEERINGCOLLEGE

(Autonomous)

MAX. MARKS
DESCRIPTION
MARKS AWARDED

Preparation&
20
Conduction

Observation &Results 10

Record Completion 05

Viva Voce 05

TOTAL 40

RESULT:
Thus, the program for Binary Search Tree operations was implemented and
executed successfully.
 IMPLEMENTATION OF AVL TREE
[Link] Date:

AIM:
To write the program to implement AVL Tree and its operation.

ALGORITHMS:

[Link] for Insertion in an AVL Tree:

1. Start with the root node.

2. Insert the node following Binary Search Tree (BST) insertion rules:
o If the key is less than the root, recursively insert it into the left subtree.
o If the key is greater than the root, recursively insert it into the right subtree.
o If the key is equal, do nothing (no duplicates allowed).
3. After insertion, update the height of each node from the inserted node up to the root.
4. Check the balance factor of each node:
o Balance Factor (BF) = height of left subtree - height of right subtree.
o If the balance factor is not in the range [-1, 1], the tree is unbalanced.
5. Perform rotations to rebalance the tree:
o Left-Left Case (BF > 1 and new key < left child’s key): Right rotate the subtree.
o Right-Right Case (BF < -1 and new key > right child’s key): Left rotate the subtree.
o Left-Right Case (BF > 1 and new key > left child’s key): Left rotate the left child,
then right rotate the subtree.
o Right-Left Case (BF < -1 and new key < right child’s key): Right rotate the right
child, then left rotate the subtree.
2. Algorithm for Deletion from an AVL Tree
Algorithm:
1. Start with the root node.
2. Perform the standard BST deletion:
o If the key to be deleted is smaller than the node’s key, recursively delete it from the
left subtree.
o If the key to be deleted is larger than the node’s key, recursively delete it from the
right subtree.
 o If the key matches the node's key:
 If the node has one or no child, replace the node with its child (or NULL if
no child).
 If the node has two children, find its inorder successor (smallest node in the
right subtree), replace the node's key with the successor's key, and
recursively delete the successor.
3. After deletion, update the height of each node from the deleted node up to the root.
4. Check the balance factor of each node and perform rotations if necessary:
o Same 4 cases as in insertion.
3. Algorithm for Rotations in AVL Tree
Right Rotation (used for Left-Left unbalance):
1. Let the unbalanced node be y.
2. Set x = y->left.
3. Perform rotation:
o y->left = x->right.
o x->right = y.
4. Update the heights of y and x.

4. Algorithm for Left Rotation (used for Right-Right unbalance):

1. Let the unbalanced node be x.
2. Set y = x->right.
3. Perform rotation:
o x->right = y->left.
o y->left = x.
4. Update the heights of x and y.
5. Algorithm for Traversal (Preorder)
Algorithm:
1. Start from the root node.
2. Visit the node.
3. Recursively traverse the left subtree.
4. Recursively traverse the right subtree.
PROGRAM:

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

// Define the structure for an AVL Tree node

struct Node {
int key;
struct Node *left;
struct Node *right;
int height;
};

// A utility function to get the height of the tree

int height(struct Node *N) {
if (N == NULL)
return 0;
return N->height;
}

// A utility function to get the maximum of two integers

int max(int a, int b) {
return (a > b) ? a : b;
}

// Allocate a new node with the given key and NULL left and right pointers
struct Node* newNode(int key) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially added at leaf
return(node);
}

// Right rotate subtree rooted with y

struct Node* rightRotate(struct Node *y) {
struct Node *x = y->left;
struct Node *T2 = x->right;

// Perform rotation
x->right = y;
y->left = T2;

// Update heights
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;

// Return new root

return x;
}
 // Left rotate subtree rooted with x
struct Node* leftRotate(struct Node *x) {
struct Node *y = x->right;
struct Node *T2 = y->left;

// Perform rotation
y->left = x;
x->right = T2;

// Update heights
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;

// Return new root

return y;
}

// Get balance factor of node N

int getBalance(struct Node *N) {
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}

// Recursive function to insert a key in the subtree rooted with node and returns the new root
of the subtree
struct Node* insert(struct Node* node, int key) {
// Perform the normal BST insertion
if (node == NULL)
return(newNode(key));

if (key < node->key)

node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // Equal keys are not allowed in BST
return node;

// Update height of this ancestor node

node->height = 1 + max(height(node->left), height(node->right));

// Get the balance factor of this ancestor node to check whether this node became
unbalanced
int balance = getBalance(node);

// If this node becomes unbalanced, then there are 4 cases

// Left Left Case

if (balance > 1 && key < node->left->key)
return rightRotate(node);

// Right Right Case

if (balance < -1 && key > node->right->key)
return leftRotate(node);
 // Left Right Case
if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}

// Right Left Case

if (balance < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}

// Return the (unchanged) node pointer

return node;
}

// Function to find the node with the minimum value (used for deletion)
struct Node* minValueNode(struct Node* node) {
struct Node* current = node;

// Loop down to find the leftmost leaf

while (current->left != NULL)
current = current->left;

return current;
}

// Recursive function to delete a node with a given key from the subtree with the given root
struct Node* deleteNode(struct Node* root, int key) {
// Perform standard BST delete
if (root == NULL)
return root;

if (key < root->key)

root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else {
// Node with only one child or no child
if ((root->left == NULL) || (root->right == NULL)) {
struct Node *temp = root->left ? root->left : root->right;

// No child case
if (temp == NULL) {
temp = root;
root = NULL;
} else // One child case
*root = *temp; // Copy the contents of the non-empty child

free(temp);
}
else {
// Node with two children: Get the inorder successor (smallest in the right subtree)
struct Node* temp = minValueNode(root->right);

// Copy the inorder successor's data to this node

root->key = temp->key;

// Delete the inorder successor

root->right = deleteNode(root->right, temp->key);
}
}

// If the tree had only one node, then return

if (root == NULL)
return root;

// Update height of the current node

root->height = 1 + max(height(root->left), height(root->right));

// Get the balance factor

int balance = getBalance(root);

// If this node becomes unbalanced, then there are 4 cases

// Left Left Case

if (balance > 1 && getBalance(root->left) >= 0)
return rightRotate(root);

// Left Right Case

if (balance > 1 && getBalance(root->left) < 0) {
root->left = leftRotate(root->left);
return rightRotate(root);
}

// Right Right Case

if (balance < -1 && getBalance(root->right) <= 0)
return leftRotate(root);

// Right Left Case

if (balance < -1 && getBalance(root->right) > 0) {
root->right = rightRotate(root->right);
return leftRotate(root);
}

return root;
}
// A utility function to print the preorder traversal of the tree
void preOrder(struct Node *root) {
if (root != NULL) {
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}

int main() {
struct Node *root = NULL;

/* Constructing tree */
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);

/* The constructed AVL Tree would be

30
/ \
20 40
/ \ \
10 25 50
*/

printf("Preorder traversal of the constructed AVL tree is \n");

preOrder(root);

// Deleting node
root = deleteNode(root, 50);

printf("\nPreorder traversal after deletion of 50 \n");

preOrder(root);

return 0;
}

OUTPUT:

Preorder traversal of the constructed AVL tree is

30 20 10 25 40 50
Preorder traversal after deletion of 50
30 20 10 25 40
 IENGINEERINGCOLLEGE

(Autonomous)

MAX. MARKS
DESCRIPTION
MARKS AWARDED

Preparation&
20
Conduction

Observation &Results 10

Record Completion 05

Viva Voce 05

TOTAL 40

RESULT:

Thus, the concept of AVL Tree was implemented successfully.

 IMPLEMENTATION OF GRAPH TRAVERSAL

[Link] Date:

AIM:
To write the program to implement the Graph Traversal.

ALGORITHM:

BREADTH FIRST SEARCH:

Step 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue.

Step 2 − If no adjacent vertex is found, remove the first vertex from the queue.

Step 3 − Repeat Rule 1 and Rule 2 until the queue is empty.

DEPTH FIRST SEARCH:

Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a stack.

Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It will pop up all the
vertices from the stack, which do not have adjacent vertices.)

Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty.

PROGRAM:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 5
struct Vertex {
char label;
bool visited;
};
//stack variables
int stack[MAX];
int top = -1;
//graph variables
//array of vertices
struct Vertex* lstVertices[MAX];
//adjacency matrix
int adjMatrix[MAX][MAX];
//vertex count
int vertexCount = 0;
//stack functions
void push(int item) {
stack[++top] = item;
}
int pop() {
return stack[top--];
}
int peek() {
return stack[top];
}
bool isStackEmpty() {
return top == -1;
}
//graph functions
//add vertex to the vertex list
void addVertex(char label) {
struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));
vertex->label = label;
vertex->visited = false;
lstVertices[vertexCount++] = vertex;
}
//add edge to edge array
void addEdge(int start,int end) {
adjMatrix[start][end] = 1;
adjMatrix[end][start] = 1;
}
//display the vertex
void displayVertex(int vertexIndex) {
printf("%c ",lstVertices[vertexIndex]->label);
}
//get the adjacent unvisited vertex
int getAdjUnvisitedVertex(int vertexIndex) {
int i;
for(i = 0; i < vertexCount; i++) {
if(adjMatrix[vertexIndex][i] == 1 && lstVertices[i]->visited == false) {
return i;
}
}
return -1;
}
void depthFirstSearch() {
int i;
//mark first node as visited
lstVertices[0]->visited = true;

//display the vertex

displayVertex(0);
//push vertex index in stack
push(0);

while(!isStackEmpty())
{
//get the unvisited vertex of vertex which is at top of the stack
int unvisitedVertex = getAdjUnvisitedVertex(peek());

//no adjacent vertex found

if(unvisitedVertex == -1) {
pop();
} else {
lstVertices[unvisitedVertex]->visited = true;
displayVertex(unvisitedVertex);
push(unvisitedVertex);
}
}

//stack is empty, search is complete, reset the visited flag

for(i = 0;i < vertexCount;i++) {
lstVertices[i]->visited = false;
}
}
 int main() {
int i, j;
for(i = 0; i < MAX; i++) // set adjacency {
for(j = 0; j < MAX; j++) // matrix to 0
adjMatrix[i][j] = 0;
}

addVertex('S'); // 0
addVertex('A'); // 1
addVertex('B'); // 2
addVertex('C'); // 3
addVertex('D'); // 4
addEdge(0, 1); // S - A
addEdge(0, 2); // S - B
addEdge(0, 3); // S - C
addEdge(1, 4); // A - D
addEdge(2, 4); // B - D
addEdge(3, 4); // C - D
printf("Depth First Search: ")
depthFirstSearch();
return 0;
}

OUTPUT:

Depth First Search: S A D B C

 IENGINEERINGCOLLEGE

(Autonomous)

MAX. MARKS
DESCRIPTION
MARKS AWARDED

Preparation&
20
Conduction

Observation &Results 10

Record Completion 05

Viva Voce 05

TOTAL 40

RESULT:
Thus, the program Graph Traversal was implemented and executed successfully.
 IMPLEMENTATION OF LINER SEARCH
[Link] Date:

AIM:

To write a C program for implementing linear search and to perform the various operations.

ALGORITHM:

1. Start
2. Input: Array arr[] of size n, element x to search.
3. Set: i = 0
4. While i < n (iterate over the array):
o If arr[i] == x Then:
 Print "Element found at index i" // Element found
 Return i // Return the index of the found element.
o Else: Increment i (i = i + 1)
5. End While
6. If the loop completes and no element is found:
o Print "Element not found in the array"
7. End

PROGRAM:

#include <stdio.h>

// Function to perform linear search

int linearSearch(int arr[], int n, int x) {
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
return i; // Return the index where the element is found
}
}
return -1; // If element is not found
}

int main() {
int n, x, result;

// Input the size of the array

printf("Enter the number of elements in the array: ");
scanf("%d", &n);

int arr[n]; // Declare the array

 // Input the elements of the array
printf("Enter the elements of the array:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

// Input the element to search

printf("Enter the element to search: ");
scanf("%d", &x);

// Perform linear search

result = linearSearch(arr, n, x);

// Display the result

if (result != -1) {
printf("Element found at index %d\n", result);
} else {
printf("Element not found in the array\n");
}

return 0;
}

OUTPUT:

Enter the number of elements in the array: 5

Enter the elements of the array:
10 20 30 40 50
Enter the element to search: 30
Element found at index 2
 IENGINEERINGCOLLEGE

(Autonomous)

MAX. MARKS
DESCRIPTION
MARKS AWARDED

Preparation&
20
Conduction

Observation &Results 10

Record Completion 05

Viva Voce 05

TOTAL 40

RESULT:
Thus, the above liner search is implemented successfully.
 IMPLEMENTATION OF BINARY SEARCH
[Link] Date:

AIM:
To write a C program for implementing binary search and to perform the various operations.

ALGORITHM:
1. Start
2. Input: A sorted array arr[] of size n, element x to search.
3. Initialize: low = 0, high = n - 1
4. While low <= high:
o Set mid = (low + high) / 2 // Find the middle element
o If arr[mid] == x:
 Print "Element found at index mid"
 Return mid // Return the index where the element is found.
o Else If arr[mid] < x:
 Set low = mid + 1 // Search the right half.
o Else:
 Set high = mid - 1 // Search the left half.
5. End While
6. If element is not found:
o Print "Element not found in the array"
7. End

PROGRAM:

#include <stdio.h>

// Function to perform binary search

int binarySearch(int arr[], int n, int x) {
int low = 0, high = n - 1;

while (low <= high) {

int mid = (low + high) / 2; // Find the middle index

// Check if the middle element is the target

if (arr[mid] == x) {
return mid; // Return the index if the element is found
}
// If target is greater, ignore the left half
else if (arr[mid] < x) {
low = mid + 1;
}
// If target is smaller, ignore the right half
else {
high = mid - 1;
}
}
 return -1; // Element is not present in the array
}

int main() {
int n, x, result;

// Input the size of the array

printf("Enter the number of elements in the array: ");
scanf("%d", &n);

int arr[n]; // Declare the array

// Input the sorted array elements

printf("Enter the elements of the array (sorted order):\n");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

// Input the element to search

printf("Enter the element to search: ");
scanf("%d", &x);

// Perform binary search

result = binarySearch(arr, n, x);

// Display the result

if (result != -1) {
printf("Element found at index %d\n", result);
} else {
printf("Element not found in the array\n");
}

return 0;
}

OUTPUT:

Enter the number of elements in the array: 6

Enter the elements of the array (sorted order):
10 20 30 40 50 60
Enter the element to search: 30
Element found at index 2
 IENGINEERINGCOLLEGE

(Autonomous)

MAX. MARKS
DESCRIPTION
MARKS AWARDED

Preparation&
20
Conduction

Observation &Results 10

Record Completion 05

Viva Voce 05

TOTAL 40

RESULT:

Thus, the above liner search was implemented and the output are verified successfully.
 IMPLEMENTATION OF INSERTION SORT
[Link] Date:

AIM:
To write a C program for implementing insertion sort.

ALGORITHM:
1. Start
2. Input: Array arr[] of size n.
3. For i = 1 to n-1:
Set key = arr[i] (element to be inserted).
Set j = i - 1
While j >= 0 and arr[j] > key:
 Set arr[j + 1] = arr[j] (shift element to the right).
 Decrement j = j - 1
Set arr[j + 1] = key (insert the key element in its correct position).
4. End For
5. End
PROGRAM:

#include <stdio.h>
// Function to perform insertion sort
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i]; // Element to be inserted
int j = i - 1;

// Shift elements of arr[0..i-1], that are greater than key, to one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key; // Insert key in its correct position
}
}
// Function to print the array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int n;

// Input the size of the array

printf("Enter the number of elements: ");
scanf("%d", &n);

int arr[n]; // Declare the array

 // Input the elements of the array
printf("Enter the elements of the array:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

// Perform insertion sort

insertionSort(arr, n);

// Display the sorted array

printf("Sorted array: \n");
printArray(arr, n);

return 0;
}

OUTPUT:

Enter the number of elements: 6

Enter the elements of the array:

64 25 12 22 11 90

Sorted array:

11 12 22 25 64 90
 IENGINEERINGCOLLEGE

(Autonomous)

MAX. MARKS
DESCRIPTION
MARKS AWARDED

Preparation&
20
Conduction

Observation &Results 10

Record Completion 05

Viva Voce 05

TOTAL 40

RESULT:

Thus, the above insertion sort was implemented and the output are verified successfully.
 IMPLEMENTATION OF BUBBLE SORT

[Link] Date:

AIM:
To write a C program for implementation of bubble sort.

Algorithm: Bubble Sort

1. Start
2. Input: Array arr[] of size n.
3. For i = 0 to n-1:
o Set swapped = false (to track if a swap occurred).
o For j = 0 to n-i-2 (last i elements are already sorted):
If arr[j] > arr[j + 1]:
Swap arr[j] and arr[j + 1].
Set swapped = true.
o If swapped == false:
Break the loop (array is sorted).
4. End For
5. End

PROGRAM:

#include <stdio.h>

// Function to perform bubble sort

void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0; // Track if a swap occurred

for (int j = 0; j < n - i - 1; j++) {

// Compare adjacent elements
if (arr[j] > arr[j + 1]) {
// Swap if they are in the wrong order
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = 1; // A swap occurred
}
}

// If no elements were swapped, the array is sorted

if (swapped == 0) {
break;
}
}
}
// Function to print the array
void printArray(int arr[], int n) {
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int n;

// Input the size of the array

printf("Enter the number of elements: ");
scanf("%d", &n);

int arr[n]; // Declare the array

// Input the elements of the array

printf("Enter the elements of the array:\n");
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

// Perform bubble sort

bubbleSort(arr, n);

// Display the sorted array

printf("Sorted array: \n");
printArray(arr, n);

return 0;
}

OUTPUT:

Enter the number of elements: 5

Enter the elements of the array:
64 34 25 12 22
Sorted array:
12 22 25 34 64
 IENGINEERINGCOLLEGE

(Autonomous)

MAX. MARKS
DESCRIPTION
MARKS AWARDED

Preparation&
20
Conduction

Observation &Results 10

Record Completion 05

Viva Voce 05

TOTAL 40

RESULT:

Thus, the above bubble sort was implemented and the output are verified successfully.
 IMPLEMENTATION OF HASHING WITH SEPARATE CHAINING

[Link] Date:

AIM:
To write a C program for implementation of hashing with separate chaining.

ALGORITHM:

1. Initialization
 Create a hash table of size TABLE_SIZE where each index points to the head of a linked list.
 Initialize all entries in the hash table to NULL.
2. Hash Function
 Input: Key k
 Output: Index index
 Compute the hash value:
index = (sum of ASCII values of characters in k) % TABLE_SIZE
3. Insertion (Insert)
 Input: Key k, Value v
 Compute the index using the hash function:
index = hash(k)
 Create a new node with the key k and value v.
 If table[index] is NULL:
Set table[index] to point to the new node (insert as the head of the list).
 Else:
Traverse the linked list at table[index] to find the end of the list.
Append the new node to the end of the list.
4. Search (Search)
 Input: Key k
 Compute the index using the hash function:
index = hash(k)
 Traverse the linked list at table[index]:
While the current node is not NULL:
 If the key of the current node matches k, return the value.
 Move to the next node.
 If no match is found, return NULL or an indication that the key is not found.
5. Display (Display)
 For each index in the hash table:
Print the index and traverse the linked list at that index.
Print all key-value pairs in the list.

Example Implementation Steps:

1. Initialize the hash table.
2. Insert key-value pairs using the insertion algorithm.
3. Search for keys using the search algorithm.
4. Display the contents of the hash table.
PROGRAM:

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

#define TABLE_SIZE 10 // Size of the hash table

// Node structure for the linked list

typedef struct Node {
char key[50];
int value;
struct Node* next;
} Node;

// Hash table structure

typedef struct HashTable {
Node* table[TABLE_SIZE];
} HashTable;

// Hash function
int hash(char* key) {
int hashValue = 0;
for (int i = 0; key[i] != '\0'; i++) {
hashValue += key[i]; // Simple hash function
}
return hashValue % TABLE_SIZE; // Modulus to fit within table size
}

// Function to create a new node

Node* createNode(char* key, int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
strcpy(newNode->key, key);
newNode->value = value;
newNode->next = NULL;
return newNode;
}

// Function to insert a key-value pair into the hash table

void insert(HashTable* ht, char* key, int value) {
int index = hash(key);
Node* newNode = createNode(key, value);
if (ht->table[index] == NULL) {
ht->table[index] = newNode; // Insert at empty index
} else {
Node* temp = ht->table[index];
while (temp->next != NULL) {
temp = temp->next; // Traverse to the end of the linked list
}
temp->next = newNode; // Insert at the end of the list
}
}
// Function to search for a key in the hash table
int search(HashTable* ht, char* key) {
int index = hash(key);
Node* temp = ht->table[index];
while (temp != NULL) {
if (strcmp(temp->key, key) == 0) {
return temp->value; // Return the value if key is found
}
temp = temp->next; // Move to the next node
}
return -1; // Return -1 if key is not found
}

// Function to display the hash table

void display(HashTable* ht) {
for (int i = 0; i < TABLE_SIZE; i++) {
Node* temp = ht->table[i];
printf("Index %d: ", i);
while (temp != NULL) {
printf(" -> [%s: %d]", temp->key, temp->value);
temp = temp->next;
}
printf("\n");
}
}

// Main function to demonstrate hash table operations

int main() {
HashTable ht = {0}; // Initialize the hash table

// Insert key-value pairs

insert(&ht, "apple", 10);
insert(&ht, "banana", 20);
insert(&ht, "orange", 30);
insert(&ht, "mango", 40);
insert(&ht, "grape", 50);
insert(&ht, "banana", 60); // This will collide with the previous banana entry

// Display the hash table

display(&ht);

// Search for a key

char* searchKey = "banana";
int value = search(&ht, searchKey);
if (value != -1) {
printf("Value for key '%s': %d\n", searchKey, value);
} else {
printf("Key '%s' not found.\n", searchKey);
}

return 0;
}
OUTPUT:

Index 0:
Index 1:
Index 2:
Index 3:
Index 4: -> [banana: 60]
Index 5: -> [apple: 10]
Index 6:
Index 7:
Index 8: -> [orange: 30] -> [mango: 40]
Index 9: -> [grape: 50]
Value for key 'banana': 60
 IENGINEERINGCOLLEGE

(Autonomous)

MAX. MARKS
DESCRIPTION
MARKS AWARDED

Preparation&
20
Conduction

Observation &Results 10

Record Completion 05

RESULT: Viva Voce 05

TOTAL 40
Thus, the above program for
implementation of hashing with separate chaining was executed and the output are verified
successfully.