PRACTICAL NO-8

BHUSHAN BHOYE

//Perform insert and delete operations on Linear queue using array

#include<stdio.h>
#include<conio.h>
#define SIZE 10
void enQueue(int);
void deQueue();
void display();
int queue[SIZE], front = -1, rear = -1;
void main()
{
int value, choice;
clrscr();
while(1){
printf("\n\n***** MENU *****\n");
printf("1. Insertion\n2. Deletion\n3. Display\n4. Exit");
printf("\nEnter your choice: ");
scanf("%d",&choice);
switch(choice){
case 1: printf("Enter the value to be insert: ");
scanf("%d",&value);
enQueue(value);
break;
case 2: deQueue();
break;
case 3: display();
break;
case 4: exit(0);
default: printf("\nWrong selection!!! Try again!!!");
}
}
}
void enQueue(int value){
if(rear == SIZE-1)
printf("\nQueue is Full!!! Insertion is not possible!!!");
else{
if(front == -1)
 front = 0;
rear++;
queue[rear] = value;
printf("\nInsertion success!!!");
}
}
void deQueue(){
if(front == rear)
printf("\nQueue is Empty!!! Deletion is not possible!!!");
else{
printf("\nDeleted : %d", queue[front]);
front++;
if(front == rear)
front = rear = -1;
}
}
void display(){
if(rear == -1)
printf("\nQueue is Empty!!!");
else{
int i;
printf("\nQueue elements are:\n");
for(i=front; i<=rear; i++)
printf("%d\t",queue[i]);
}
}
**************** OUTpUT ****************
 PRACTICAL NO-8
BHUSHAN BHOYE

// Perform insert delete operations on Circular queue using array

#include<stdio.h>
# define MAX 5
int cqueue_arr[MAX];
int front = -1;
int rear = -1;
void insert(int item)
{
if((front == 0 && rear == MAX-1) || (front == rear+1))
{
printf("Queue Overflow n");
return;
}
if(front == -1)
{
front = 0;
rear = 0;
}
else
{
if(rear == MAX-1)
rear = 0;
else
rear = rear+1;
}
cqueue_arr[rear] = item ;
}
void deletion()
{
if(front == -1)
{
printf("Queue Underflown");
return ;
}
printf("Element deleted from queue is : %dn",cqueue_arr[front]);
if(front == rear)
{
front = -1;
rear=-1;
}
else
{
 if(front == MAX-1)
front = 0;
else
front = front+1;
}
}
void display()
{
int front_pos = front,rear_pos = rear;
if(front == -1)
{
printf("Queue is emptyn");
return;
}
printf("Queue elements :n");
if( front_pos <= rear_pos )
while(front_pos <= rear_pos)
{
printf("%d ",cqueue_arr[front_pos]);
front_pos++;
}
else
{
while(front_pos <= MAX-1)
{
printf("%d ",cqueue_arr[front_pos]);
front_pos++;
}
front_pos = 0;
while(front_pos <= rear_pos)
{
printf("%d ",cqueue_arr[front_pos]);
front_pos++;
}
}
printf("n");
}
int main()
{
int choice,item;
do
{
printf("1.Insertn");
printf("2.Deleten");
printf("3.Displayn");
printf("4.Quitn");
 printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1 :
printf("Input the element for insertion in queue : ");
scanf("%d", &item);
insert(item);
break;
case 2 :
deletion();
break;
case 3:
display();
break;
case 4:
break;
default:
printf("Wrong choicen");
}
} while(choice!=4);
return 0;
}

**************** OUTpUT ****************

 PRACTICAL NO-10
BHUSHAN BHOYE
// Perform operation on singly Linked list
#include <stdlib.h>
#include <iostream>
using namespace std;
// Create a node
struct Node
{
int data;
struct Node* next;
};
void insertAtBeginning(struct Node** head_ref, int new_data) {
// Allocate memory to a node
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
// insert the data
new_node->data = new_data;
new_node->next = (*head_ref);
// Move head to new node
(*head_ref) = new_node;
}
// Insert a node after a node
void insertAfter(struct Node* prev_node, int new_data) {
if (prev_node == NULL) {
cout << "the given previous node cannot be NULL";
return;
}
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
}
// Insert at the end
void insertAtEnd(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref; /* used in step 5*/
new_node->data = new_data;
new_node->next = NULL;
if (*head_ref == NULL)
{
*head_ref = new_node;
return;
}

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

last->next = new_node;
return;
}
// Delete a node
 void deleteNode(struct Node** head_ref, int key)
{
struct Node *temp = *head_ref, *prev;
if (temp != NULL && temp->data == key)
{
*head_ref = temp->next;
free(temp);
return;
}
// Find the key to be deleted
while (temp != NULL && temp->data != key)
{
prev = temp;
temp = temp->next;
}
// If the key is not present
if (temp == NULL) return;
// Remove the node
prev->next = temp->next;
free(temp);
}
// Search a node
bool searchNode(struct Node** head_ref, int key)
{
struct Node* current = *head_ref;
while (current != NULL)
{
if (current->data == key) return true;
current = current->next;
}
return false;
}
// Sort the linked list
void sortLinkedList(struct Node** head_ref)
{
struct Node *current = *head_ref, *index = NULL;
int temp;
if (head_ref == NULL)
{
return;
} else
{
while (current != NULL)
{
// index points to the node next to current
index = current->next;
while (index != NULL) {
if (current->data > index->data) {
temp = current->data;
current->data = index->data;
index->data = temp;
 }
index = index->next;
}
current = current->next;
}
}
}
// Print the linked list
void printList(struct Node* node) {
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
// Driver program
int main() {
struct Node* head = NULL;
insertAtEnd(&head, 1);
insertAtBeginning(&head, 2);
insertAtBeginning(&head, 3);
insertAtEnd(&head, 4);
insertAfter(head->next, 5);
cout << "Linked list: ";
printList(head);
cout << "\nAfter deleting an element: ";
deleteNode(&head, 3);
printList(head);
int item_to_find = 3;
if (searchNode(&head, item_to_find)) {
cout << endl << item_to_find << " is found";
} else
{
cout << endl << item_to_find << " is not found";
}
sortLinkedList(&head);
cout << "\nSorted List: ";
printList(head);
}
**************** OUTpUT ****************
 PRACTICAL NO-11
BHUSHAN BHOYE

// Perform operation on Circular singly Linked List

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;

void beginsert ();

void lastinsert ();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 7)
{
printf("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert in begining\n2.Insert at last\n3.Delete from Beginning\n4.Delete from
last\n5.Search for an element\n6.Show\n7.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
beginsert();
break;
case 2:
lastinsert();
break;
case 3:
begin_delete();
break;
case 4:
 last_delete();
break;
case 5:
search();
break;
case 6:
display();
break;
case 7:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void beginsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter the node data?");
scanf("%d",&item);
ptr -> data = item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
}
else
{
temp = head;
while(temp->next != head)
temp = temp->next;
ptr->next = head;
temp -> next = ptr;
head = ptr;
}
printf("\nnode inserted\n");
}
}
void lastinsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW\n");
}
else
{
printf("\nEnter Data?");
scanf("%d",&item);
ptr->data = item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
}
else
{
temp = head;
while(temp -> next != head)
{
temp = temp -> next;
}
temp -> next = ptr;
ptr -> next = head;
}

printf("\nnode inserted\n");
}

void begin_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nUNDERFLOW");
}
else if(head->next == head)
{
 head = NULL;
free(head);
printf("\nnode deleted\n");
}

else
{ ptr = head;
while(ptr -> next != head)
ptr = ptr -> next;
ptr->next = head->next;
free(head);
head = ptr->next;
printf("\nnode deleted\n");

}
}
void last_delete()
{
struct node *ptr, *preptr;
if(head==NULL)
{
printf("\nUNDERFLOW");
}
else if (head ->next == head)
{
head = NULL;
free(head);
printf("\nnode deleted\n");

}
else
{
ptr = head;
while(ptr ->next != head)
{
preptr=ptr;
ptr = ptr->next;
}
preptr->next = ptr -> next;
free(ptr);
printf("\nnode deleted\n");

}
}

void search()
{
struct node *ptr;
int item,i=0,flag=1;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
if(head ->data == item)
{
printf("item found at location %d",i+1);
flag=0;
}
else
{
while (ptr->next != head)
{
if(ptr->data == item)
{
printf("item found at location %d ",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
}
if(flag != 0)
{
printf("Item not found\n");
}
}

void display()
{
struct node *ptr;
 ptr=head;
if(head == NULL)
{
printf("\nnothing to print");
}
else
{
printf("\n printing values ... \n");

while(ptr -> next != head)

{

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

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

}
**************** OUTpUT ****************
 PRACTICAL NO-12
BHUSHAN BHOYE

// Perform traversing on binary search tree

#include <bits/stdc++.h>
using namespace std;

/* A binary tree node has data, pointer to left child

and a pointer to right child */
struct Node {
int data;
struct Node *left, *right;
};

// Utility function to create a new tree node

Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}

/* Given a binary tree, print its nodes in inorder*/

void printInorder(struct Node* node)
{
if (node == NULL)
return;

/* first recur on left child */

printInorder(node->left);

/* then print the data of node */

cout << node->data << " ";

/* now recur on right child */

printInorder(node->right);
}

/* Driver code*/
int main()
{
struct Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
 root->left->right = newNode(5);

// Function call
cout << "\nInorder traversal of binary tree is \n";
printInorder(root);

return 0;
}
**************** OUTpUT ****************