Notes

AIM: Write a program the implementation of various operations on a linear queue and circular queue represented using linear array.
SOURCE CODE:
#include<iostream>
usingnamespace std;
int main()
{
int i,n,first=-1,last=-1,ch;
int num[100];
int item;
char ans='y';
cout<<"Menu is:n1. Insertion in queue..n";
cout<<"2. Deletion in queue..n3. Display..";
do {
cout<<"nEnter Choice.. ";
cin>>ch;
switch(ch)
{
case1: cout<<"Enter item to be inserted: ";
cin>>item;
if((first==0&&last== n-1)||(first==last+1))
{
cout<<"Overflow!!";
break;
}
elseif(first == -1)
{
first = 0;
last = 0;
num[first] = item;
}
elseif(last == n-1)
{
last=0;
num[last] = item;
}
else
{
last = last+1;
num[last] = item;
}
break;
case2:
if(first== -1)
{
cout<<"Underflow!!";
break;
}
item = num[first];
if(first == last)
{
first = -1;
last=-1;
}
elseif(first == n-1)
first = 0;
else
first = first + 1;
cout<<"Element deleted is: "<<item<<endl;
break;
case3:
cout<<"Elements are:n";
for(i=first;i<=last;i++)
{
cout<<"A["<<i<<"] = "<<num[i]<<endl;
}
break;
default: cout<<"Wrong Choice!!";}
cout<<"Want to run again(y/n)?";
cin>>ans;
}while(ans=='y'||ans=='Y');
return0;
}
\ circular queue
#include<iostream>
usingnamespace std;
int cqueue[5];
int front = -1, rear = -1, n=5;
void insertCQ(int val)
{
if ((front == 0&& rear == n-1) || (front == rear+1))
{
cout<<"Queue Overflow n";
return;
}
if (front == -1)
{
front = 0;
rear = 0;
} else
{
if (rear == n - 1)
rear = 0;
else
rear = rear + 1;
}
cqueue[rear] = val ;
}
void deleteCQ()
{
if (front == -1)
{
cout<<"Queue Underflown";
return ;
}
cout<<"Element deleted from queue is : "<<cqueue[front]<<endl;
if (front == rear)
{
front = -1;
rear = -1;
} else
{
if (front == n - 1)
front = 0;
else
front = front + 1;
}
}
void displayCQ()
{
int f = front, r = rear;
if (front == -1)
{
cout<<"Queue is empty"<<endl;
return;
}
cout<<"Queue elements are :n";
if (f <= r)
{
while (f <= r)
{
cout<<cqueue[f]<<"";
f++;
}
}
else
{
while (f <= n - 1)
{
cout<<cqueue[f]<<"";
f++;
}
f = 0;
while (f <= r)
{
cout<<cqueue[f]<<"";
f++;
}
}
cout<<endl;
}
int main()
{
int ch, val;
cout<<"1)Insertn";
cout<<"2)Deleten";
cout<<"3)Displayn";
cout<<"4)Exitn";
do
{
cout<<"Enter choice : "<<endl;
cin>>ch;
switch(ch)
{
case1:
cout<<"Input for insertion: "<<endl;
cin>>val;
insertCQ(val);
break;
case2:
deleteCQ();
break;
case3:
displayCQ();
break;
case4:
cout<<"Exitn";
break;
default: cout<<"Incorrect!n";
}
}
while(ch != 4);
return0;
}
OUTPUT:






PROGRAM: 7
Date: 8th October,2019
AIM: Write a program to demonstrate the implementation of various operations on a queue using linear linked list(linked queue).
SOURCE CODE:
#include<iostream>
usingnamespace std;
struct node
{
int data;
struct node *next;
}*front=NULL,*rear,*temp;
void ins()
{
temp=new node;
cout<<"Enter data:";
cin>>temp->data;
temp->next=NULL;
if(front==NULL)
front=rear=temp;
else
{
rear->next=temp;
rear=temp;
}
}
void del()
{
if(front==NULL)
cout<<"Queue is emptyn";
else
{
temp=front;
front=front->next;
cout<<"Deleted node is "<<temp->data<<"n";
delete(temp);
}
}
void dis()
{
if(front==NULL)
cout<<"Queue is emptyn";
else
{
temp=front;
while(temp!=NULL)
{
cout<<temp->data<<""<<endl;
temp=temp->next;
}
}
}
int main()
{
int ch;
while(1)
{
cout<<"*** Menu ***"<<endl<<"1.Insert 2.Delete 3.Display 4.Exit"<<endl;
cout<<"Enter your choice(1-4):";
cin>>ch;
switch(ch)
{
case1: ins();
break;
case2: del();
break;
case3: dis();
break;
default: cout<<"Wrong Choice!!!";
}
}
}
OUTPUT:














Date: 15th October,2019
PROGRAM: 8
AIM: Program to illustrate the implementation of different operations on binary search tree.
SOURCE CODE:
# include<iostream>
usingnamespace std;
struct node
{
int info;
struct node *left;
struct node *right;
}*root;
class BST
{
public:
void find(int, node **, node **);
void insert(node *, node *);
void del(int);
void case_a(node *,node *);
void case_b(node *,node *);
void case_c(node *,node *);
void preorder(node *);
void inorder(node *);
void postorder(node *);
void display(node *, int);
BST()
{
root = NULL;
}
};
int main()
{
int choice, num;
BST bst;
node *temp;
while (1)
{
cout<<"-----------------"<<endl;
cout<<"Operations on BST"<<endl;
cout<<"-----------------"<<endl;
cout<<"1.Insert Element "<<endl;
cout<<"2.Delete Element "<<endl;
cout<<"3.Inorder Traversal"<<endl;
cout<<"4.Preorder Traversal"<<endl;
cout<<"5.Postorder Traversal"<<endl;
cout<<"6.Display"<<endl;
cout<<"7.Quit"<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case1:
temp = new node;
cout<<"Enter the number to be inserted : ";
cin>>temp->info;
bst.insert(root, temp);
break;
case2:
if (root == NULL)
{
cout<<"Tree is empty, nothing to delete"<<endl;
continue;
}
cout<<"Enter the number to be deleted : ";
cin>>num;
bst.del(num);
break;
case3:
cout<<"Inorder Traversal of BST:"<<endl;
bst.inorder(root);
cout<<endl;
break;
case4:
cout<<"Preorder Traversal of BST:"<<endl;
bst.preorder(root);
cout<<endl;
break;
case5:
cout<<"Postorder Traversal of BST:"<<endl;
bst.postorder(root);
cout<<endl;
break;
case6:
cout<<"Display BST:"<<endl;
bst.display(root,1);
cout<<endl;
break;
default:
cout<<"Wrong choice"<<endl;
}
}
}
void BST::find(int item, node **par, node **loc)
{
node *ptr, *ptrsave;
if (root == NULL)
{
*loc = NULL;
*par = NULL;
return;
}
if (item == root->info)
{
*loc = root;
*par = NULL;
return;
}
if (item < root->info)
ptr = root->left;
else
ptr = root->right;
ptrsave = root;
while (ptr != NULL)
{
if (item == ptr->info)
{
*loc = ptr;
*par = ptrsave;
return;
}
ptrsave = ptr;
if (item < ptr->info)
ptr = ptr->left;
else
ptr = ptr->right;
}
*loc = NULL;
*par = ptrsave;
}
void BST::insert(node *tree, node *newnode)
{
if (root == NULL)
{
root = new node;
root->info = newnode->info;
root->left = NULL;
root->right = NULL;
cout<<"Root Node is Added"<<endl;
return;
}
if (tree->info == newnode->info)
{
cout<<"Element already in the tree"<<endl;
return;
}
if (tree->info > newnode->info)
{
if (tree->left != NULL)
{
insert(tree->left, newnode);
}
else
{
tree->left = newnode;
(tree->left)->left = NULL;
(tree->left)->right = NULL;
cout<<"Node Added To Left"<<endl;
return;
}
}
else
{
if (tree->right != NULL)
{
insert(tree->right, newnode);
}
else
{
tree->right = newnode;
(tree->right)->left = NULL;
(tree->right)->right = NULL;
cout<<"Node Added To Right"<<endl;
return;
}
}
}
void BST::del(int item)
{
node *parent, *location;
if (root == NULL)
{
cout<<"Tree empty"<<endl;
return;
}
find(item, &parent, &location);
if (location == NULL)
{
cout<<"Item not present in tree"<<endl;
return;
}
if (location->left == NULL && location->right == NULL)
case_a(parent, location);
if (location->left != NULL && location->right == NULL)
case_b(parent, location);
if (location->left == NULL && location->right != NULL)
case_b(parent, location);
if (location->left != NULL && location->right != NULL)
case_c(parent, location);
}
void BST::case_a(node *par, node *loc )
{
if (par == NULL)
{
root = NULL;
}
else
{
if (loc == par->left)
par->left = NULL;
else
par->right = NULL;
}
}
void BST::case_b(node *par, node *loc)
{
node *child;
if (loc->left != NULL)
child = loc->left;
else
child = loc->right;
if (par == NULL)
{
root = child;
}
else
{
if (loc == par->left)
par->left = child;
else
par->right = child;
}
}
void BST::case_c(node *par, node *loc)
{
node *ptr, *ptrsave, *suc, *parsuc;
ptrsave = loc;
ptr = loc->right;
while (ptr->left != NULL)
{
ptrsave = ptr;
ptr = ptr->left;
}
suc = ptr;
parsuc = ptrsave;
if (suc->left == NULL && suc->right == NULL)
case_a(parsuc, suc);
else
case_b(parsuc, suc);
if (par == NULL)
{
root = suc;
}
else
{
if (loc == par->left)
par->left = suc;
else
par->right = suc;
}
suc->left = loc->left;
suc->right = loc->right;
}
void BST::preorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
cout<<ptr->info<<"";
preorder(ptr->left);
preorder(ptr->right);
}
}
void BST::inorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
inorder(ptr->left);
cout<<ptr->info<<"";
inorder(ptr->right);
}
}
void BST::postorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
postorder(ptr->left);
postorder(ptr->right);
cout<<ptr->info<<"";
}
}

void BST::display(node *ptr, int level)
{
int i;
if (ptr != NULL)
{
display(ptr->right, level+1);
cout<<endl;
if (ptr == root)
cout<<"Root->: ";
else
{
for (i = 0;i < level;i++)
cout<<"";
}
cout<<ptr->info;
display(ptr->left, level+1);
}
}
OUTPUT:













Date: 22th October,2019
PROGRAM: 9
AIM: Program to sort an array of integers in ascending order using:
a) Quick Sort
b) Heap Sort
SOURCE CODE:
Heap sort:
#include<iostream>
usingnamespace std;
void heap(int arr[],int n,int k)
{
int lar=k;
int l=2*k+1;
int r=2*k+2;
if(l<n && arr[l]>arr[lar])
lar=l;
if(r<n && arr[r]>arr[lar])
lar=r;
if(lar != k) {
swap(arr[k],arr[lar]);
heap(arr,n,lar);
}
}
void heapSort(int arr[],int n)
{
for(int k=n/2-1;k>=0;k--)
heap(arr,n,k);
for(int k=n-1;k>=0;k--)
{
swap(arr[0],arr[k]);
heap(arr,k,0);
}
}
void display(int arr[],int n)
{
for(int k=0;k<n;++k)
cout<<arr[k]<<endl;
}
int main()
{
int a,b;
cout<<"Enter the number of elements : "<<endl;
cin>>a;
int arr[a];
cout<<"Enter the Elements : "<<endl;
for(b=0;b<a;b++)
{
cin>>arr[b];
}
cout<<"The Elements are : "<<endl;
for(b=0;b<a;b++)
{
cout<<arr[b]<<endl;
}
int n=sizeof(arr)/sizeof(arr[0]);
heapSort(arr,n);
cout<<"Sorted array is : "<<endl;
display(arr,n);
}
OUTPUT:

Quick sort:
#include<iostream>
usingnamespace std;
int a[10],l,u,i,j;
void quick(int *,int,int);
int main()
{
cout <<"enter 10 elements: ";
for(i=0;i<10;i++)
cin >> a[i];
l=0;
u=9;
quick(a,l,u);
cout <<"sorted elements: ";
for(i=0;i<10;i++)
cout << a[i] <<"";
}

void quick(int a[],int l,int u)
{
int p,temp;
if(l<u)
{
p=a[l];
i=l;
j=u;
while(i<j)
{
while(a[i] <= p && i<j )
i++;
while(a[j]>p && i<=j )
j--;
if(i<=j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;}
}
temp=a[j];
a[j]=a[l];
a[l]=temp;
cout <<"n";
for(i=0;i<10;i++)
cout <<a[i]<<"";
cout<<endl;
quick(a,l,j-1);
quick(a,j+1,u);
}
}
OUTPUT:


Date: 25th October,2019
PROGRAM: 10
AIM: Program to illustrate the traversal of graph using:
a) Breadth-First Search
b) Depth-First Search
SOURCE CODE:
Breadth-First Search
#include<iostream>
usingnamespace std;
int cost[10][10],i,j,k,n,qu[10],front,rare,v,visit[10],visited[10];
int main()
{
int m;
cout <<"enter no of vertices: ";
cin >> n;
cout <<"ente no of edges: ";
cin >> m;
cout <<"nEDGES: n";
for(k=1;k<=m;k++)
{
cin >>i>>j;
cost[i][j]=1;
}

cout <<"enter initial vertex: ";
cin >>v;
cout <<"Visitied vertices: n";
cout << v;
visited[v]=1;
k=1;
while(k<n)
{
for(j=1;j<=n;j++)
if(cost[v][j]!=0&& visited[j]!=1&& visit[j]!=1)
{
visit[j]=1;
qu[rare++]=j;
}
v=qu[front++];
cout<<""<<v <<"";
k++;
visit[v]=0; visited[v]=1;
}
}
OUTPUT:

Depth-First Search
#include<iostream>
usingnamespace std;
usingnamespace std;
int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10];
int main()
{
int m;
cout <<"enter no of vertices: ";
cin >> n;
cout <<"ente no of edges: ";
cin >> m;
cout <<"nEDGES: n";
for(k=1;k<=m;k++)
{
cin >>i>>j;
cost[i][j]=1;
}

cout <<"enter initial vertex: ";
cin >>v;
cout <<"ORDER OF VISITED VERTICES: ";
cout << v <<"";
visited[v]=1;
k=1;
while(k<n)
{
for(j=n;j>=1;j--)
if(cost[v][j]!=0&& visited[j]!=1&& visit[j]!=1)
{
visit[j]=1;
stk[top]=j;
top++;
}
v=stk[--top];
cout<<v <<"";
k++;
visit[v]=0; visited[v]=1;
}
}
OUTPUT: