C++ program to implement searching & Sorting on Item record using STL.

Code :
#include<iostream.h>
#include<conio.h>
#include<algorithm>
#include<vector>
using namespace std;
class Item
{
public: char name[10];
int quantity;
int cost;
int code;
bool operator==(const Item &i1)
{
if(code==i1.code)
return 1;
return 0;
}

bool operator<(Item &i1)
{
if(code<i1.code)
return 1;
return 0;
}
};
vector<Item> o1;
void print(Item &i1);
void display();
void insert();
void search();
void dlt();
void main()
{
int ch;
do
{
cout<<”\n***** Menu *****”;
cout<<”\n1.Insert”;
cout<<”\n2.Display”;
cout<<”\n3.Search”;
cout<<”\n4.Sort”;
cout<<”\n5.Delete”;
cout<<”\n6.Exit”;
cout<<”\nEnter your choice:”;
cin>>ch;
switch(ch)
{
case 1: insert();
break;
case 2: display();
break;
case 3: search();
break;
case 4: sort(o1.begin(),o1.end());
break;
case 5: dlt();
break;
case 6: exit(0);
}
}while(ch!=7);
}
void insert()
{
Item i1;
cout<<”\nEnter Item Name:”;
cin>>i1.name;
cout<<”\nEnter Item Quantity:”;
cin>>i1.quantity;
cout<<”\nEnter Item Cost:”;
cin>>i1.cost;
cout<<”\nEnter Item Code:”;
cin>>i1.code;
o1.push_back(i1);
}
void display()
{
for_each(o1.begin(),o1.end(),print);
}
void print(Item &i1)
{
cout<<”\n”;
cout<<”\nItem Name:”<<i1.name;
cout<<”\nItem Quantity:”<<i1.quantity;
cout<<”\nItem Cost:”<<i1.cost;
cout<<”\nItem Code:”<<i1.code;
}
void search()
{
vector<Item>::iterator p;
Item i1;
cout<<”\nEnter Item Code to search:”;
cin>>i1.code;
p=find(o1.begin(),o1.end(),i1);
if(p==o1.end())
cout<<”\nNot found.”;
else
{
cout<<”\nFound.”;
}
}
void dlt()
{
vector<Item>::iterator p;
Item i1;
cout<<”\nEnter Item Code to delete:”;
cin>>i1.code;
p=find(o1.begin(),o1.end(),i1);
if(p==o1.end())
cout<<”\nNot found.”;
else
{
o1.erase(p);
cout<<”\nDeleted.”;
} }

Program to implement dequeue using C++

Description :
Deque stands for Double-ended queue.These are sequence containers with dynamic sizes that can be expanded or contracted on both ends.
Code:
#include<deque>     //include deque library
#include<stdio.h>
#include<iostream.h>
using namespace std;
void main()
{
deque <int>dq;
deque <int>::iterator p;
char cc;
int val,ch;
do
{
cout<<”\n\nMENU:”;
cout<<”\n1. Enter element at front\n2. Enter element at Rear\n3. Delet element at front\n4. Delet element at Rear\n5. Disp front element\n6. Disp back element\n7. Display the element of Deque\n\n”;
cout<<”\nEnter choice:”;
cin>>ch;
switch(ch)
{
case 1:
cout<<”\n\nEnter the element to be inserted:”;
cin>>val;
dq.push_front(val);
cout<<”\nElement inserted at front:”<<dq.front();
break;
case 2:
cout<<”\n\nEnter the element to be inserted:”;
cin>>val;
dq.push_back(val);
cout<<”\nElement inserted at rear end:”<<dq.back();
break;
case 3:
cout<<”\nElementto be deleted at front:”<<dq.front();
dq.pop_front();
break;
case 4:
cout<<”\nElement to be deleted at rear:”<<dq.back();
dq.pop_back();
break;
case 5:
cout<<”\nElement at front:”<<dq.front();
break;
case 6:
cout<<”\nElement at rear:”<<dq.back();
break;

case 7:
if(dq.empty()==1)
cout<<”\n\nDEQUE is EMPTY..”;
else
{
cout<<”\n\nDisplaying the elements of DEQUE…\n”;
for(p=dq.begin();p<dq.end();p++)
cout<<” “<<*p<<”\t”;
}
break;
}
cout<<”\n\nCONTINUE MENU:”;
cin>>cc;
}while(cc==’y'); }

C++ code to add binary numbers using STL stack

Description:
Using STL ,the stack header file needs to be included to use this class. The class member functions that are provided are listed below.

• push, pushes an item onto the stack.
• pop, pops an item from the stack but does not give this item to the programmer to use.
• top, gives the programmer a reference to the top of stack item; no change is made to the stack.
• empty, the usual boolean function.
• size, reports the number of items on the stack.

Code:
#include<iostream.h>
#include<vector>
#include<stack>
using namespace std;
stack <int> read();
void display(stack<int> &s);
stack <int>add(stack<int> &s1,stack<int> &s2);
void main()
{
stack<int> s1,s2,s3;
int ch;
do
{
cout<<”\n1.Addition of two binary numbers\n2.Quit”;
cout<<”\nEnter your choice:”;
cin>>ch;
switch(ch)
{
case 1: s1=read();
s2=read();
s3=add(s1,s2);
display(s3);
break;
}
}while(ch!=2);
}
stack<int> read()
{
char a[40];
stack<int> s;
cout<<”\n Enter a binary number: “;
cin>>a;
for(int i=0;a[i]!=’\0′;i++)
{
if(a[i]==’1′)
s.push(1);
else
if(a[i]==’0′)
s.push(0);
}
return s;
}
stack<int> add(stack<int> &s1,stack<int> &s2)
{
stack<int> s;
int sum,carry=0,bit1,bit2;
while(!s1.empty() || !s2.empty())
{
bit1=bit2=0;
if(!s1.empty())
{
bit1=s1.top();
s1.pop();
}
if(!s2.empty())
{
bit2=s2.top();
s2.pop();
}
sum=(bit1+bit2+carry)%2;
carry=(bit1+bit2+carry)/2;
s.push(sum);
}
if(carry==1)
s.push(1);
return s;
}
void display(stack<int> &s)
{
cout<<”\n Sum= “;
while(!s.empty())
{
cout<<s.top();
s.pop();
} }

Program to Implement queue using SLL

Code:
#include<iostream.h>
#include<conio.h>
#include<deque>
using namespace std;

void main()
{
int ch,val;
deque<int> dq;
deque<int>::iterator p;
cout<<”\n1.Inserting at front position\n2.Inserting at rear position”;
cout<<”\n3.Deleting front element\n4.Deleting rear element”;
cout<<”\n5.Display front element\n6.Display rear element\n7.Display whole deque”;
do
{
cout<<”\nEnter your choice:”;
cin>>ch;
switch(ch)
{
case 1:cout<<”\nEnter data:”;
cin>>val;
dq.push_front(val);
break;
case 2:cout<<”\nEnter data:”;
cin>>val;
dq.push_back(val);
break;
case 3:dq.pop_front();
break;
case 4:dq.pop_back();
break;
case 5:cout<<”\nFront:”;
cout<<dq.front();
break;
case 6:cout<<”\nRear:”;
cout<<dq.back();
break;
case 7: if(dq.empty())
cout<<”\nQueue is empty!”;
else
{
for(p=dq.begin();p<dq.end();p++)
cout<<” “<<*p;
}
break;
}
}while(ch!=8);
}

C++ code to Implement direct access file using different collision resolution techniques.

Code :
/* To implement Direct Access File ,Collision handling throgh linear probing with chaining and without replacement.
*/
#include <iomanip.h>
#include <iostream.h>
#include <fstream.h>
#include <conio.h>
#include <string.h>
#define SIZE 10
#define h(x) x%SIZE
struct student
{
int rollno;
char name[20];
float marks;
int status;
int link;
};
class lin_probe
{
char table[30];
fstream tab;
student rec;
public:
lin_probe(char *a);

void displayall();
void insert(student rec1);
void Delete(int rollno);
int search(int rollno);
void display(int recno)
{
int i=recno;
tab.open(table,ios::binary | ios::in | ios::nocreate);
tab.seekg(recno*sizeof(student),ios::beg);
tab.read((char*)&rec,sizeof(student));
if(rec.status==0)
{
cout<<”\n”<<i<<”) “<<rec.rollno<<” “<<rec.name<<” “<<setprecision(2)<<rec.marks;
cout<<” “<<rec.link;
}
else
cout<<”\n”<<i<<”) ***** Empty ********”;
tab.close();
}
void read(int recno)
{
tab.open(table,ios::binary | ios::in );
tab.seekg(recno*sizeof(student),ios::beg);
tab.read((char*) &rec,sizeof(student));
tab.close();
}
void write(int recno)
{
tab.open(table,ios::binary | ios::nocreate | ios::out | ios::in);
tab.seekp(recno*sizeof(student),ios::beg);
tab.write((char*)&rec,sizeof(student));
tab.close();
}
};
void lin_probe::lin_probe(char *a)
{
int i;
strcpy(table,a);
rec.status=1;rec.link=-1;
tab.open(table,ios::binary | ios::out);
tab.close();
for(i=0;i<SIZE;i++)
write(i);
}
void lin_probe::displayall()
{
int i=1,n;
cout<<”\n*********Data File*********\n”;
for(i=0;i<SIZE;i++)
display(i);
}
void lin_probe::insert(student rec1)
{
int n,i,j,start,k;
rec1.status=0;
rec1.link=-1;
start=h(rec1.rollno);
for(i=0;i<SIZE;i++)
{
j=(start+i)%SIZE;
read(j);
if(rec.status==0 && h(rec.rollno)==start)
break;
}
if(i<10)
{
while(rec.link!=-1)
{
j=rec.link;
read(j);
}
for(i=0;i<SIZE;i++)
{
k=(start+i)%SIZE;
read(k);
if(rec.status==1)
{
rec=rec1;
write(k);
read(j);
rec.link=k;
write(j);
return;
}
}
cout<<”\nTable is full “;
}
else
{
for(i=0;i<SIZE;i++)
{
k=(start+i)%SIZE;
read(k);
if(rec.status==1)
{
rec=rec1;
write(k);
return;
}
}
cout<<”\nTable is full “;
}
}
void lin_probe::Delete(int rollno)
{
student rec1;
int recno;
int i,j,start,k;
start=h(rollno);
for(i=0;i<SIZE;i++)
{
j=(start+i)%SIZE;
read(j);
if(rec.status==0 && h(rec.rollno)==start)//synonim found
break;
}
if(i<10)
{
if(rec.rollno==rollno )
{
rec.status=1;
write(j);
}
else
{
while(rec.rollno !=rollno && rec.link!=-1)
{
k=j;
j=rec.link;
read(j);
}
if(rec.rollno==rollno)
{ rec.status=1;
write(j);
int nextlink=rec.link;
read(k);
rec.link=nextlink;
write(k);
}
else
cout<<”\nElement not found”;
}
}
else
cout<<”\nRecord Not Found “;
}
int lin_probe::search(int rollno)
{
int start,i,j;
start=h(rollno);
for(i=0;i<SIZE;i++)
{
j=(start+i)%SIZE;
read(j);
if(rec.status==0 && h(rec.rollno)==start)//synonim found
break;
}
if(i<10)
{
while(rec.rollno !=rollno && rec.link!=-1)
{
j=rec.link;
read(j);
}
if(rec.rollno==rollno)
return(j);
else
return -1;
}
else
return -1;
}
void main()
{
lin_probe object(“table.txt”);
int rollno,op,recno;
student rec1;
clrscr();
do
{
cout<<”\n\n1)Print\n2)Insert\n3)Delete”;
cout<<”\n4)Search\n5)Quit”;
cout<<”\nEnter Your Choice:”;
cin>>op;
switch(op)
{
case 1: object.displayall();
break;
case 2:
cout<<”\nEnter a record to be inserted(roll no,name,marks) : “;
cin>>rec1.rollno>>rec1.name>>rec1.marks;
object.insert(rec1);
break;
case 3:
cout<<”\nEnter the roll no.:”;
cin>>rollno;
object.Delete(rollno);
break;
case 4:
cout<<”\nEnter a roll no. : “;
cin>>rollno;
recno=object.search(rollno);
if(recno>=0)
{
cout<<”\n Record No.: “<<recno;
object.display(recno);
}
else
cout<<”\nRecord Not Found “;
break;
}
}while(op!=5); }

Program for Implementation of AVL tree in C++

Description :
AVL is named so by   its two inventors,.Adelson-Velskii  and Landis.
In AVL tree,the height of the two child subtrees of any node differ by at most one. If at any time they differ by more than one, rebalancing is done to restore this property.

Code  :
#include<iostream.h>
#include<conio.h>
#include<alloc.h>
# include<stdlib.h>
class node
{
public:
int data;
struct node *left,*right;
int ht;
};

class AVL
{
node *root;
int height(node *);
node *rotate_right(node *);
node *rotate_left(node *);
node *RR(node *);
node *LL(node *);
node *LR(node *);
node *RL(node *);
int BF(node *);
public:
AVL()
{
root=NULL;
}
node *insert(node *,int);
node *delet(node *,int);
void preorder (node *);
void inorder(node *);
};
void main()
{
AVL A;
int x,n,i,choice;
node *root=NULL;
clrscr();
cout<<”\n\n\t\t\t\t\t\t\t\t\t\t\t\t…. CREATION OF AVL TREE ….”;
do
{
cout<<”\n\n MENU: “;
cout<<”\n\n\t1.Create\n\n\t2.Insert\n\n\t3.Delete\n\n\t4.Display\n\n\t5.Exit “;
cout<<”\n\nEnter the choice: “;
cin>>choice;
switch(choice)
{
case 1:
cout<<”\n\nEnter the number of elements: “;
cin>>n;
cout<<”\n\nEnter tree data: “;
for(i=0;i<n;i++)
{
cin>>x;
root=A.insert(root,x);
}
break;
case 2:
cout<<”\n\nEnter the data to be insert: “;
cin>>x;
A.insert(root,x);
break;
case 3:
cout<<”\n\nEnter a data which u have to delete: “;
cin>>x;
A.delet(root,x);
break;
case 4:
cout<<”\n\nPreorder Display:\n\n”;
A.preorder(root);
cout<<”\n\nInorder Display:\n\n”;
A.inorder(root);
break;
}
}while(choice!=5);
getch();
}
node *AVL::insert(node *T,int x)
{
if(T==NULL)
{
T=new node;
T->data=x;
T->left=NULL;
T->right=NULL;
}
else
{
if(x>T->data)
{
T->right=insert(T->right,x);
if(BF(T)==-2)
{
if(x>T->right->data)
T=RR(T);
else
T=RL(T);
}
}
else if(x<T->data)
{
T->left=insert(T->left,x);
if(BF(T)==2)
{
if(x<T->left->data)
T=LL(T);
else
T=LR(T);
}
}
}
T->ht=height(T);
return(T);
}
node *AVL::delet(node *T,int x)
{
node *p;
if(T==NULL)
return(0);
else
if(x>T->data)
{
T->right=delet(T->right,x);
if(BF(T)==2)
if(BF(T->left)>=0)
T=LL(T);
else
T=LR(T);
}
else if(x<T->data)
{
T->left=delet(T->left,x);
if(BF(T)==-2)
if(BF(T->right)<=0)
T=RR(T);
else
T=RL(T);
}
else
{
if(T->right!=NULL)
{
p=T->right;
while(p->left!=NULL)
p=p->left;
T->data=p->data;
T->right=delet(T->right,p->data);
if(BF(T)==2)
if(BF(T->left)>=0)
T=LL(T);
else
T=LR(T);
}
else
return(T->left);
}
T->ht=height(T);
return(T);
}
int AVL::height(node *T)
{
int LH,RH;
if(T==NULL)
return(0);
if(T->left==NULL)
LH=0;
else
LH=1+T->left->ht;
if(T->right==NULL)
RH=0;
else
RH=1+T->right->ht;
if(LH>RH)
return (LH);
else
return (RH);
}
int AVL::BF(node *T)
{
int LH,RH;
if(T==NULL)
return(0);
if(T->left==NULL)
LH=0;
else
LH=1+T->left->ht;
if(T->right==NULL)
RH=0;
else
RH=1+T->right->ht;
return(LH-RH);
}
node *AVL::rotate_left(node *x)
{
node *y;
y=x->right;
x->right=y->left;
y->left=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}
node *AVL::rotate_right(node *x)
{
node *y;
y=x->left;
x->left=y->right;
y->right=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}
node *AVL::LL(node *T)
{
T=rotate_right(T);
return(T);
}
node *AVL::RR(node *T)
{
T=rotate_left(T);
return(T);
}
node *AVL::LR(node *T)
{
T->left=rotate_left(T->left);
T=rotate_right(T);
return(T);
}
node *AVL::RL(node *T)
{
T->right=rotate_right(T->right);
T=rotate_left(T);
return(T);
}
void AVL::preorder(node *root)
{
node *T=root;
if(T!=NULL)
{
cout<<” \n”<<T->data<<” [BF= "<<BF(T)<<"]“;
preorder(T->left);
preorder(T->right);
}
}
void AVL::inorder(node *root)
{
node *T=root;
if(T!=NULL)
{
inorder(T->left);
cout<<” \n”<<T->data<<” [BF= "<<BF(T)<<"]“;
inorder(T->right);
} }

Program to implement B tree in c++

Code :
#include<iostream.h>
#include<conio.h>
#define MAX 5
class node;
typedef struct pair
{
int key;
node *next;
}pair;
class node
{
public:
node *father;
int noofkeys;
pair data[MAX];
node *first;
node();
void insert_in_node(pair x);
pair splitnode(pair x);
int leaf_node();
node *nextindex(int x);
void display();
};
void node::display()
{
int i;
cout<<”(“;
for(i=0;i<noofkeys;i++)
cout<<data[i].key<<” “;
cout<<”)”;
}
node* node::nextindex(int x)
{
if(x<data[0].key)
return first;
for(int i=0;i<noofkeys;i++)
{
if(x<=data[i].key)
return (data[i-1].next);
}
return (data[i-1].next);
}
int node::leaf_node()
{
if(data[0].next==NULL)
return 1;
return 0;
}
void node::insert_in_node(pair mypair)
{
int i;
for(i=noofkeys-1;i>=0 && data[i].key>mypair.key;i–)
data[i+1]=data[i];
data[i+1]=mypair;
noofkeys++;
}
pair node::splitnode(pair x)
{
node *T;
pair mypair;
int i,j,centre;
centre=(noofkeys-1)/2;
T=new node;
if(x.key>data[centre].key) //Divide the node in two parts(original and T)
{
for(i=centre+1,j=0;i<=noofkeys;i++,j++)
T->data[j]=data[i];
T->noofkeys=noofkeys-centre-1;
noofkeys=noofkeys-T->noofkeys;
T->insert_in_node(x);
T->first=T->data[0].next;
T->father=father;
mypair.key=T->data[0].key;
mypair.next=T;
//Delete the first key from node T
for(i=1;i<T->noofkeys;i++)
T->data[i-1]=T->data[i];
T->noofkeys–;
}
else
{
for(i=centre,j=0;i<noofkeys;i++,j++)
T->data[j]=data[i];
T->noofkeys=noofkeys-centre;
noofkeys=noofkeys-T->noofkeys;
insert_in_node(x);
T->father=father;
mypair.key=T->data[0].key;
mypair.next=T;
//Delete the first key from node T
for(i=1;i<T->noofkeys;i++)
T->data[i-1]=T->data[i];
T->noofkeys–;
}
return(mypair);
}
node::node()
{
for(int i=0;i<=MAX;i++)
data[i].next=NULL;
noofkeys=0;
father=NULL;
first=NULL;
}
class btree
{
int mkeys;
node *root;
public:
btree(int n)
{
mkeys=n;
root=NULL;
}
void insert(int x);
void displaytree();
};

void btree::insert(int x)
{
int index;
pair mypair;
node *p,*q;
mypair.key=x;
mypair.next=NULL;
if(root==NULL)
{
root = new node;
root->insert_in_node(mypair);
}
else
{
p=root;
while(!(p->leaf_node()))
p=p->nextindex(x);
if(p->noofkeys < mkeys-1)
p->insert_in_node(mypair);
else
{
mypair=p->splitnode(mypair);
while(1)
{
if(p==root)
{
q=new node;
q->data[0]=mypair;
q->first=root;
q->father=NULL;
q->noofkeys=1;
root=q;
q->first->father=q;
q->data[0].next->father=q;
return;
}
else
{
p=p->father;
if(p->noofkeys < mkeys)
{
p->insert_in_node(mypair);
return;
}
else
mypair=p->splitnode(mypair);
}
}
}
}
}
class Q
{
node *data[60];
int R,F;
public:
Q()
{
R=F=0;
}
int empty()
{
if(R==F)
return 1;
else
return 0;
}
node *deque()
{
return data[F++];
}
void enque(node *x)
{
data[R++]=x;
}
void makeempty()
{
R=F=0;
}
};
void btree::displaytree()
{
Q q1,q2;
node *p;
q1.enque(root);
while(!q1.empty())
{
q2.makeempty();
cout<<”\n”;
while(!q1.empty())
{
p=q1.deque();
p->display();cout<<” “;
if(!p->leaf_node())
{
q2.enque(p->first);
for(int i=0;i<p->noofkeys;i++)
q2.enque(p->data[i].next);
}
}
q1=q2;
}
}
void main()
{
int n,i,x,op;
node *p;
clrscr();
cout<<”\nmaximum number of keys in a node ? :”;
cin>>n;
btree b(n);
do
{
cout<<”\n\n1)Insert\n2)Print\n3)Quit”;
cout<<”\nEnter your choice : “;
cin>>op;
switch(op)
{
case 1: cout<<”\nEnter a data : “;
cin >> x;
b.insert(x);
break;
case 2:
b.displaytree();
break;
}
}while(op!=3); }