1.

PROGRAM TO IMPLEMENT THE LIST ADT

USING ARRAYS AND LINKED LISTS

#include<iostream>
#include<stdlib.h>
using namespace std;
class node
{
public:
class node *next;
int data;
};

class queue:public node

{
node *head;
int front,rare;

public:
queue()
{
front=-1;
rare=-1;
}

void push(int x)
{
if(rare<0)
{
head=new node;
head->next=NULL;
head->data=x;
rare++;
}
else
{
node *temp, *temp1;
temp=head;

if(rare>=4)
{
cout<<"Queue over flow";
return;
}
rare++;
 while(temp->next!=NULL)
temp=temp->next;

temp1=new node;
temp->next=temp1;
temp1->next=NULL;
temp1->data=x;
}
}

void display()
{
node *temp;
temp=head;

if(rare<0)
{
cout<<"Queue underflow";
return;
}

while(temp!=NULL)
{
cout<<temp->data<<" ";
temp=temp->next;
}
}

void pop()
{
node *temp;
temp=head;

if(rare<0)
{
cout<<"Queue underflow";
return;
}

if(front==rare)
{
front=rare=-1;
head=NULL;
return;
}
 front++;
head=head->next;
}
};

int main()
{
queue s1;
int ch;

while(1)
{
cout<<"\[Link]\[Link]\[Link]\[Link]\nEnter your choice:";
cin>>ch;

switch(ch)
{
case 1:
cout<<"\nEnter a element:";
cin>>ch;
[Link](ch);
break;

case 2:
[Link]();
break;

case 3:
[Link]();
break;

case 4:
exit(0);
}
}

return 0;
}
 2. PROGRAMS TO IMPLEMENT THE FOLLOWING USING A SINGLY LINKED
LIST
I) STACK
#include<iostream>
#include<stdlib.h>
using namespace std;
class node
{
public:
class node *next;
int data;
};
class stack:public node
{
node *head;
int tos;
public:
stack(){
tos=-1;}
void push(int x){
if(tos<0) {
head=new node;
head->next=NULL;
head->data=x;
tos++; }
else{
node *temp,*temp1;
temp=head;
if(tos>=4) {
cout<<"Stack overflow";
return; }
tos++;
while(temp->next!=NULL)
temp=temp->next;
temp1=new node;
temp->next=temp1;
temp1->next=NULL;
temp1->data=x; }}
void display() {
node *temp;
temp=head;
if(tos<0) {
cout<<"Stack underflow";
return; }
while(temp!=NULL) {
cout<<temp->data<<" ";
 temp=temp->next;
}
}
void pop()
{
node *temp;
temp=head;
if(tos<0)
{
cout<<"Stack underflow";
return;
}
tos--;
while(temp->next->next!=NULL)
temp=temp->next;
temp->next=NULL;
}
};
int main()
{
stack s1;
int ch;
while(1)
{
cout<<"\[Link]\[Link]\[Link]\[Link]\nEnter your choice:";
cin>>ch;
switch(ch)
{
case 1:
cout<<"\nEnter a element:";
cin>>ch;
[Link](ch);
break;

case 2:
[Link]();
break;

case 3:
[Link]();
break;

case 4:
exit(0);} }
return 0;
}
 II) QUEUE

#include<iostream>
#include<stdlib.h>

using namespace std;

class node
{
public:
class node *next;
int data;
};

class queue:public node

{
node *head;
int front,rare;

public:
queue()
{
front=-1;
rare=-1;
}

void push(int x)
{
if(rare<0)
{
head=new node;
head->next=NULL;
head->data=x;
rare++;
}
else
{
node *temp, *temp1;
temp=head;

if(rare>=4)
{
cout<<"Queue underflow";
return;
}

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

temp1=new node;
temp->next=temp1;
temp1->next=NULL;
temp1->data=x;
}
}

void display()
{
node *temp;
temp=head;

if(rare<0)
{
cout<<"Queue underflow";
return;
}

while(temp!=NULL)
{
cout<<temp->data<<" ";
temp=temp->next;
}
}

void pop()
{
node *temp;
temp=head;

if(rare<0)
{
cout<<"Queue underflow";
return;
}

if(front==rare)
{
front=rare=-1;
head=NULL;
return;
}

front++;
 head=head->next;
}
};

int main()
{
queue s1;
int ch;

while(1)
{
cout<<"\nQUEUE ADT";
cout<<"\[Link]\[Link]\[Link]\[Link]\nEnter your choice:";
cin>>ch;

switch(ch)
{
case 1:
cout<<"\nEnter a element:";
cin>>ch;
[Link](ch);
break;

case 2:
[Link]();
break;

case 3:
[Link]();
break;

case 4:
exit(0);
}
}

return 0;
}
 3. PROGRAM THAT READS AN INFIX EXPRESSION, CONVERTS THE
EXPRESSION TO POSTFIX FORM

#include<bits/stdc++.h>
using namespace std;
int prec(char c)
{
if(c=='^')
return 3;
else if(c=='/'||c=='*')
return 2;
else if(c=='+'||c=='-')
return 1;
else
return -1;
}
char associativity(char c)
{
if(c=='^')
return 'R';
return 'L';
}
void infixTopostfix(string s)
{
stack<char>st;
string result;
for(int i=0;i<[Link]();i++)
{
char c=s[i];
if((c>='a'&&c<='z')||(c>'A'&&c<='Z')||(c>='0'&&c<='9'))
result+=c;
else if(c=='(')
[Link]('(');
else if(c==')')
{
while([Link]()!='(')
{
result+=[Link]();
[Link]();
}
[Link]();
}
else
{
 while(![Link]() && (prec(c)<prec([Link]()) ||

(prec(c)==prec([Link]()) && associativity(c)=='L')))

{
result+=[Link]();
[Link]();
}
[Link](c);
}
}
while(![Link]())
{
result+=[Link]();
[Link]();
}
cout<<result<<endl;
}
int main()
{
string exp="a+b*(c^d-e)^(f+g*h)-i";
infixTopostfix(exp);
return 0;
}
 4. PROGRAM TO IMPLEMENT PRIORITY QUEUE ADT

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>

using namespace std;

struct n
{
int p;
int info;
struct n*l;
};

class priority_Queue
{
private:
n*f;

public:
priority_Queue()
{
f=NULL;
}

void insert(int i,int p)

{
n*t,*q;
t=new n;
t->info=i;
t->p=p;

if(f==NULL||p<f->p)
{
t->l=f;
f=t;
}
else
{
q=f;
while(q->l!=NULL&&q->l->p<=p)
q=q->l;
 t->l=q->l;
q->l=t;
}
}

void del()
{
n*t;
if(f==NULL)
cout<<"Queue underflow\n";
else
{
t=f;
cout<<"Deleted item is:"<<t->info<<endl;
f=f->l;
free(t);
}
}

void show()
{
n*ptr;
ptr=f;

if(f==NULL)
cout<<"Queue is empty\n";
else
{
cout<<"Queue is:\n";
cout<<"Priority item\n";

while(ptr!=NULL)
{
cout<<ptr->p<<" "<<ptr->info<<endl;
ptr=ptr->l;
}
}
}
};

int main()
{
int c,i,p;
priority_Queue pq;

do
{
 cout<<"[Link]\n";
cout<<"[Link]\n";
cout<<"[Link]\n";
cout<<"[Link]\n";
cout<<"Enter your choice:";
cin>>c;

switch(c)
{
case 1:
cout<<"Input the item value to be added in the queue:";
cin>>i;
cout<<"Enter its priority:";
cin>>p;
[Link](i,p);
break;

case 2:
[Link]();
break;

case 3:
[Link]();
break;

case 4:
break;

default:
cout<<"Wrong choice\n";
}
}
while(c!=4);

return 0;
}
 5) WRITE A PROGRAM TO PERFORM THE FOLLOWING OPERATIONS:
*INSERT AN ELEMENT INTO A BINARY SEARCH TREE.
*DELETE AN ELEMENT FROM A BINARY SEARCH TREE.
*SEARCH FOR A KEY ELEMENT IN A BINARY SEARCH TREE.

#include<iostream>
#include<stdlib.h>

using namespace std;

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

node* insert(node* root, int key)

{
if(root == NULL)
{
node* temp = new node;
temp->data = key;
temp->left = NULL;
temp->right = NULL;
return temp;
}

if(key < root->data)

root->left = insert(root->left, key);
else if(key > root->data)
root->right = insert(root->right, key);

return root;
}

node* minValueNode(node* root)

{
node* current = root;
while(current && current->left != NULL)
current = current->left;
return current;
}

node* deleteNode(node* root, int key)

{
 if(root == NULL)
return root;
if(key < root->data)
root->left = deleteNode(root->left, key);
else if(key > root->data)
root->right = deleteNode(root->right, key);
else
{
if(root->left == NULL)
{
node* temp = root->right;
free(root);
return temp;
}
else if(root->right == NULL)
{
node* temp = root->left;
free(root);
return temp;
}
node* temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
bool search(node* root, int key)
{
if(root == NULL)
return false;
if(root->data == key)
return true;
if(key < root->data)
return search(root->left, key);
return search(root->right, key);
}
void inorder(node* root)
{
if(root != NULL)
{
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
int main()
{
 node* root = NULL;
int ch, key;
while(1)
{
cout << "\nBINARY SEARCH TREE OPERATIONS";
cout << "\n1. INSERT";
cout << "\n2. DELETE";
cout << "\n3. SEARCH";
cout << "\n4. DISPLAY (INORDER)";
cout << "\n5. EXIT";
cout << "\nEnter your choice: ";
cin >> ch;
switch(ch)
{
case 1:
cout << "Enter element to insert: ";
cin >> key;
root = insert(root, key);
break;

case 2:
cout << "Enter element to delete: ";
cin >> key;
root = deleteNode(root, key);
break;

case 3:
cout << "Enter element to search: ";
cin >> key;
if(search(root, key))
cout << "Element found";
else
cout << "Element not found";
break;

case 4:
cout << "Inorder Traversal: ";
inorder(root);
break;

case 5:
exit(0);
}
}
return 0;
}
 6. WRITE A PROGRAM TO PERFORM THE FOLLOWING OPERATIONS
INSERT AN ELEMENT INTO AN AVL TREE
DELETE AN ELEMENT FROM AN AVL TREE

#include<iostream>
#include<stdlib.h>
using namespace std;
#define TRUE 1
#define FALSE 0
#define NULL0
class AVL;
class AVLNODE
{
friend class AVL;
private:
int data;
AVLNODE *left,*right;
int bf;
};

class AVL
{
private:
AVLNODE *root;
public:
AVLNODE *loc,*par;
AVL()
{
root=NULL;
}

int insert(int);
void displayitem();
void display(AVLNODE*);
void removeitem(int);
void remove1(AVLNODE*,AVLNODE*,int);
void remove2(AVLNODE*,AVLNODE*,int);
void search(int x);
void search1(AVLNODE*,int);
};
int AVL::insert(int x)
{
AVLNODE *a,*b,*c,*f,*p,*q,*y;
int found,unbalanced;
int d;
if(!root)
{
y=new AVLNODE;
y->data=x;
root=y;
root->bf=0;
root->left=root->right=NULL;
return TRUE;
}
f=NULL;
a=p=root;
q=NULL;
found=FALSE;
while(p&&!found)
{
if(p->bf)
{
a=p;
f=q;
}
if(x<p->data)
{
q=p;
p=p->left;
}
else if(x>p->data)
{
q=p;
p=p->right;
}
else
{
y=p;
found=TRUE;
}
}

if(!found)
{
y=new AVLNODE;
y->data=x;
y->left=y->right=NULL;
y->bf=0;

if(x<q->data)
q->left=y;
else
q->right=y;

if(x>a->data)
{
p=a->right;
b=p;
d=-1;
}
else
{
p=a->left;
b=p;
d=1;
}

while(p!=y)
if(x>p->data)
{
p->bf=-1;
p=p->right;
}
else
{
p->bf=1;
p=p->left;
}

unbalanced=TRUE;

if(!(a->bf)||!(a->bf+d))
{
a- >bf+=d;
unbalanced=FALSE;
}

if(unbalanced)
{
if(d==1)
{
if(b->bf==1)
{
a- >left=b->right;
b->right=a;
a- >bf=0;
b->bf=0;
}
else
{
c=b->right;
b- >right=c->left;
a->left=c->right;
c->left=b;
c- >right=a;

switch(c->bf)
{
case 1:a->bf=-1;b->bf=0;break;
case -1:b->bf=1;a->bf=0;break;
case 0:a->bf=0;b->bf=0;break;
}
c->bf=0;
b=c;
}
}
else
{
if(b->bf==-1)
{
a- >right=b->left;
b->left=a;
a- >bf=0;
b->bf=0;
}
else
{
c=b->right;
b- >right=c->left;
a->right=c->left;
c->right=b;
c- >left=a;

switch(c->bf)
{
case 1:a->bf=-1;b->bf=0;break;
case -1:b->bf=1;a->bf=0;break;
case 0:a->bf=0;b->bf=0;break;
}
c->bf=0;
b=c;
}
}

if(!f)
 root=b;
else if(a==f->left)
f->left=b;
else
f->right=b;
}
return TRUE;
}
return FALSE;
}

void AVL::displayitem()
{
display(root);
}

void AVL::display(AVLNODE* temp)

{
if(temp==NULL)
return;

cout<<temp->data<<" ";
display(temp->left);
display(temp->right);
}

void AVL::removeitem(int x)
{
search(x);
if(loc==NULL)
{
cout<<"Item not found";
return;
}

if(loc->left!=NULL && loc->right!=NULL)

remove1(loc,par,x);
else
remove2(loc,par,x);
}

void AVL::remove1(AVLNODE*l,AVLNODE*p,int x)
{
AVLNODE *ptr,*save;
ptr=l->right;
save=l;
 while(ptr->left!=NULL)
{
save=ptr;
ptr=ptr->left;
}

remove2(ptr,save,x);
}

void AVL::remove2(AVLNODE* s,AVLNODE* p,int x)

{
AVLNODE* child;

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

child=NULL;
else if(s->left!=NULL)
child=s->left;
else
child=s->right;

if(p!=NULL)
{
if(s==p->left)
p->left=child;
else
p->right=child;
}
else
root=child;
}

void AVL::search(int x)
{
search1(root,x);
}

void AVL::search1(AVLNODE*temp,int x)
{
AVLNODE* ptr=temp;
AVLNODE* save=NULL;

while(ptr!=NULL)
{
if(ptr->data==x)
{
cout<<"Element found";
loc=ptr;
 par=save;
return;
}
save=ptr;
if(x<ptr->data)
ptr=ptr->left;
else
ptr=ptr->right;
}

cout<<"Element not found";

loc=NULL;
par=NULL;
}

int main()
{
AVL a;
int x,c;
char ch;

do
{
cout<<"\[Link]";
cout<<"\[Link]";
cout<<"\[Link]";
cout<<"\[Link]";
cout<<"\[Link]";
cout<<"\nEnter your choice:";
cin>>c;

switch(c)
{
case 1:
cout<<"Enter element:";
cin>>x;
[Link](x);
break;

case 2:
[Link]();
break;

case 3:
cout<<"Enter element to delete:";
cin>>x;
[Link](x);
 break;

case 4:
cout<<"Enter element to search:";
cin>>x;
[Link](x);
break;

case 5:
exit(0);
}

cout<<"\nContinue (y/n):";
cin>>ch;

}while(ch=='y'||ch=='Y');

return 0;
}
 7. PROGRAM FOR THE IMPLEMENTATION OF BFS AND DFS
FOR A GIVEN GRAPH

#include<iostream>
#include<vector>
#include<queue>
#include<stack>

using namespace std;

void edge(vector<int>adj[],int u,int v)

{
adj[u].push_back(v);
}

void bfs(int s,vector<int>adj[],bool visit[])

{
queue<int>q;
[Link](s);
visit[s]=true;

while(![Link]())
{
int u=[Link]();
cout<<u<<" ";
[Link]();

for(int i=0;i<adj[u].size();i++)
{
if(!visit[adj[u][i]])
{
[Link](adj[u][i]);
visit[adj[u][i]]=true;
}
}
}
}

void dfs(int s,vector<int>adj[],bool visit[])

{
stack<int>stk;
[Link](s);
visit[s]=true;

while(![Link]())
 {
int u=[Link]();
cout<<u<<" ";
[Link]();

for(int i=0;i<adj[u].size();i++)
{
if(!visit[adj[u][i]])
{
[Link](adj[u][i]);
visit[adj[u][i]]=true;
}
}
}
}

int main()
{
vector<int>adj[5];
bool visit[5];

for(int i=0;i<5;i++)
{
visit[i]=false;
}

edge(adj,0,2);
edge(adj,0,1);
edge(adj,1,3);
edge(adj,2,0);
edge(adj,2,3);
edge(adj,2,4);

cout<<"BFS traversal is:"<<" ";

bfs(0,adj,visit);
cout<<endl;

for(int i=0;i<5;i++)
{
visit[i]=false;
}

cout<<"DFS traversal is:"<<" ";

dfs(0,adj,visit);
return 0;

}
 8) WRITE A PROGRAMS FOR IMPLEMENTING THE FOLLOWING SEARCHING
METHODS

A) LINEAR SEARCH

#include<iostream>
using namespace std;

int main()
{
int arr[10],i,num,index;

cout<<"Enter 10 number:";
for(i=0;i<10;i++)
cin>>arr[i];

cout<<"\nEnter a number to search:";

cin>>num;

for(i=0;i<10;i++)
{
if(arr[i]==num)
{
index=i;
break;
}
}

cout<<"\nFound at index no:"<<index;

cout<<endl;

return 0;
}
 8) WRITE A PROGRAMS FOR IMPLEMENTING THE FOLLOWING SEARCHING
METHODS
B) BINARY SEARCH

#include<iostream>
using namespace std;

int main()
{
int i,arr[10],num,first,last,middle;

cout<<"Enter 10 elements(in ascending order):";

for(i=0;i<10;i++)
cin>>arr[i];

cout<<"\nEnter a element to be search:";

cin>>num;

first=0;
last=9;
middle=(first+last)/2;

while(first<=last)
{
if(arr[middle]<num)
first=middle+1;
else if(arr[middle]==num)
{
cout<<"\nThe number,"<<num<<" found at position "<<middle+1;
break;
}
else
last=middle-1;

middle=(first+last)/2;
}

if(first>last)
cout<<"\nThe number,"<<num<<" is not found in given array";

cout<<endl;
return 0;
}