Full Record

Data Structures Lab (PC351CS)
M.V.S.R ENGINEERING COLLEGE

(Affiliated to Osmania University & Recognized ay AICTE)
Nadergul, Hyderabad
CERTIFICATE
Department of COMPUTER SCIENCE & ENGINEERING
Certified that this is a bonafide work of lab experiments carried out by
Mr/Ms._________________________________ bearing Roll.No. _______________________ under the
course of Data Structures Lab prescribed by Osmania University for BE 2/4 Sem-1 of
COMPUTER SCIENCE & ENGINEERING during the academic year 2017–2018.
Internal Examiner External Examiner
CSE Department MVSR Engineering College

M.V.S.R ENGINEERING COLLEGE

(Affiliated to Osmania University & Recognized ay AICTE)
Nadergul, Hyderabad
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

Subject: Data Structures Lab Acad.Year: 2017-18 Sem-I
Class : BE 2/4 CSE Section :
Experiment Date of Page
S.No. Name of the Experiment
Date Submission No.
1 Implementation of Single Linked List.
2 Implementation of Double Linked List.

3 Implementation of Circular Linked List.
4 Stack Implementation using Arrays.

5 Stack Implementation using Linked Lists.
6 Queue Implementation using Arrays.
7 Queue Implementation using Linked Lists.
8 Infix to postfix Conversion using Stacks.
9 Evaluation of postfix Expression.

10 Polynomial Arithmetic using Linked Lst.
11 Hashing Implementation.
12 Binary Tree Traversals (Recursive).
13 Binary Tree Traversals (Iterative).
14 Operations on Binary Trees.
15 Binary Search Tree Implementation.
16 AVL Tree Implementation.

17 Implementation of Selection Sort Algorithm.
18 Implementation of Shell Sort Algorithm.
19 Implementation of Merge Sort Algorithm.
20 Implementation of Quick Sort Algorithm.
21 Implementation of Heap Sort Algorithm.
Implementations of BFS graph Traversal
22
Technique.
Implementation of DFS graph Traversal
23
Technique.
24 Implementation of Binary Search.
CSE Department MVSR Engineering College

1. Implementation of Single Linked List.

#include<iostream>
using namespace std;
template<class t>
class chain;
template<class t>
class node
{
t data;
node<t> *next;
public:node(t x)
{
data=x;
next=NULL;
}
friend chain<t>;
};
template<class t>
class chain
{
int listsize;
node<t> *first,*last;
public:chain()
{
first=NULL;
last=NULL;
listsize=0;
}
~chain();
void insertatbeg(t x);
void insertatend(t x);
void insert(t ele,int index);
bool isempty()const
{
if(first==NULL)
{
return true;
}
return false;
}
int sizeOf()const
{
return listsize;
}
void deleteatbeg();
void deleteatend();
void erase(int index);
int indexof(t ele)const;
t get(int index)const;
CSE Department 1 MVSR Engineering College

int counting()const;
void reverse();
void display()const;
};
template<class t>
void chain<t>::insertatbeg(t x)
{
node<t> *nn=new node<t>(x);
nn->next=first;
first=nn;
listsize++;
}
template<class t>
void chain<t>::insertatend(t x)
{
node<t> *curr=first;
while(curr->next)
{
curr=curr->next;
}
curr->next=nn;
listsize++;
}
template<class t>
void chain<t>:: insert(t x,int index)
{
if(index<0||index>listsize)
{
cout<<"illegal index"<<endl;
return;
}
for(int i=0;i<index-1;i++)
{
curr=curr->next;
}
nn->next=curr->next;
curr->next=nn;
listsize++;
}
template<class t>
void chain<t>::deleteatbeg()
{
if(first==NULL)
{
return;

}
else
{
first=first->next;
cout<<"deleted element is "<<curr->data<<endl;
delete curr;
}
listsize--;
}
template<class t>
void chain<t>::deleteatend()
{
if(first==NULL)
{
cout<<"no elements to delete\n";
return;
}
else
{
node<t> *prev;
while(curr->next)
{
prev=curr;
curr=curr->next;
}
cout<<"deleted element is\n "<<curr->data;
prev->next=NULL;
delete curr;
}listsize--;
}
template<class t>
void chain<t>::erase(int index)
{
if(index<0||index>=listsize)
{
cout<<"illegal index"<<endl;
return;
}
else
{
node<t> *prev;
for(int i=0;i<=index;i++)
{
prev=curr;
curr=curr->next;
}
cout<<"deleted element is \n"<<curr->data;

prev->next=NULL;
delete curr;
}listsize--;
}
template<class t>
int chain<t>:: indexof(t ele)const
{
int i;
node<t> *curr;
for(i=0,curr=first;curr;i++,curr=curr->next)
{
if(curr->data==ele)
{
return i;
}
}
return -1;
}
template<class t>
t chain<t>::get(int index)const
{
if(index<0||index>=listsize)
{
cout<<"illegal index\n";
return -1;
}
else
{
for(int i=0;i<index;i++)
{
curr=curr->next;
}
return curr->data;
}
}
template<class t>
chain<t>::~chain()
{
while(first)
{
first=first->next;
delete curr;
}
}
template<class t>
int chain<t>::counting()const

{
int count=0;
while(curr)
{
count++;
curr=curr->next;
}
cout<<"no of nodes are"<<count<<endl;
}
template<class t>
void chain<t>::reverse()
{
node<t> *prev=NULL;
while(curr)
{
node<t> *p=prev;
prev=curr;
curr=curr->next;
prev->next=p;
}
first=prev;
}
template<class t>
void chain<t>::display()const
{
if(first==NULL)
{
cout<<"no elements to display\n";
return;
}
else
{
while(curr)
{
cout<<curr->data<<"\t";
curr=curr->next;
}
cout<<endl;
}
}
main()
{
chain <int> s1;
int ch,s,e,i;
while(1)
{

cout<<"\n1.isempty\n2.sizeof\n3.insertatbeg\n4.insertatend\n5.insert\n6.deleteatbeg\n7.deleteatend\n
8.erase\n9.indexof\n10.get element \n11.reverse\n12.display\n13.exit\n";
cout<<"enter ur choice\n";
cin>>ch;
switch(ch)
{
case 1:if(s1.isempty())
cout<<"list is empty\n";
else
cout<<"list is not empty\n";
break;
case 2:s=s1.sizeOf();
cout<<"list size is\n"<<s;
break;
case 3:cout<<"enter the element to be inserted\n";
cin>>e;
s1.insertatbeg(e);
break;
case 4:cout<<"enter the element to be inserted\n";
cin>>e;
s1.insertatend(e);
break;
case 5:cout<<"insert element and the index\n";
cin>>e>>i;
s1.insert(e,i);
break;
case 6:s1.deleteatbeg();
break;
case 7:s1.deleteatend();
break;
case 8:cout<<"enter the index of element to be deleted\n";
cin>>i;
s1.erase(i);
break;
case 9:cout<<"enter the data to be searched\n";
cin>>e;
i=s1.indexof(e);
if(i==-1)
cout<<"element not found\n";
else
cout<<"index of "<<e<<" is : "<<i<<endl;
break;
case 10:cout<<"enter the index\n";
cin>>i;
e=s1.get(i);
if(e==-1)
cout<<"illegel index\n";
else

cout<<"data at index i is: "<<e<<endl;

break;
case 11:s1.reverse();
break;
case 12:s1.display();
break;
}
}
}
OUTPUT:

2. Implementation of Double Linked List.

#include<iostream>
#include<stdlib.h>
template<class T>
class dlinkedlist;
template<class T>
class node
{
public:T ele;
node<T> *prev,*next;
friend class dlinkedlist<T>;
node(T x)
{
ele=x;
prev=next=NULL;
}
};
template<class T>
class dlinkedlist
{
int ls;
node<T> *first,*last;
public:dlinkedlist()
{
first=last=NULL;
ls=0;
}
int isempty()
{
if(first==NULL&&last==NULL)
{
return 1;
}
else
{
return 0;
}
}
int size()
{
node<T> *p=first;
int c=0;
while(p)
{
p=p->next;
c++;
}
return c;

}
void insert(T ele,int pos)
{
if(pos<0||pos>ls)
{
cout<<"invalid position given"<<endl;
return;
}
node<T> *q=new node<T> (ele);
if(isempty())
{
first=last=q;
ls++;
}
else
{
if(pos<=(int)(ls)/2)
{
if(pos==0)
{
q->next=first;
first->prev=q;
first=q;
ls++;
return;
}
node<T> *p=first;
for(int i=0;i<pos-1;i++,p=p->next);
q->next=p->next;
q->prev=p;
q->next->prev=q;
p->next=q;
}
else
{
if(pos==ls)
{
last->next=q;
q->prev=last;
last=q;
ls++;
return;
}
node<T> *p=last;
for(int i=ls-1;i>=pos;i--,p=p->prev);
q->next=p->next;
q->prev=p;
q->next->prev=q;
p->next=q;

}
ls++;
}
}
int indexof(T ele)

{
if(isempty()==1)
cout<<"list is empty"<<endl;
node<T> *p=first;
int i=0;
while(p&&p->ele!=ele)
{
p=p->next;
i++;
}
if(!p)
{
return -1;
}
else
{
return i;
}
}
void show()
{
node<T> *p=first;
while(p)
{
cout<<p->ele<<" "<<endl;
p=p->next;
}
}
void del(int pos)
{
if(pos<0||pos>=ls)
{
cout<<"invalid position given"<<endl;
return;
}
else
{
node<T>*cur;
if(pos<=(int)(ls)/2)
{
if(pos==0)
{
cur=first;

first=first->next;
first->prev=NULL;
if(first==NULL)
last=NULL;
}
else
{
node<T>* p=NULL;
cur=first;
for(int i=0;i<pos;i++)
{
p=cur;
cur=cur->next;
}
p->next=cur->next;
cur->next->prev=p;
}
delete cur;
ls--;
return;
}
else
{
node<T>* cur,*p;
if(pos==ls-1)
{
cur=last;
last=last->prev;
last->next=NULL;
}
else
{
p=NULL;cur=last;
for(int i=ls-1;i>pos;i--)
{
p=cur;
cur=cur->prev;
}
p->prev=cur->prev;
cur->prev->next=p;
}
delete cur;
ls--;
return;
}
}
}
};

main()
{
int x,p,ch,k;
dlinkedlist <int>a;
while(1)
{
cout<<"1.isempty 2.size 3.insert 4.delete 5.index 6.show 6.exit"<<endl;
cin>>ch;
switch(ch)
{
case 1:x=a.isempty();
if(x==1)
cout<<"list is empty"<<endl;
else
cout<<"list is not empty"<<endl;
break;
case 2:x=a.size();
cout<<"list size is"<<endl;
cout<<x;
break;
case 3:cout<<"enter the element and position"<<endl;
cin>>x>>p;
a.insert(x,p);
break;
case 4:cout<<"enter the position"<<endl;
cin>>p;
a.del(p);
break;
case 5:cout<<"enter the element whose index is to be found"<<endl;
cin>>x;
k=a.indexof(x);
if(k!=-1)
cout<<x<<"element is fount at position"<<k<<endl;
else
cout<<"element is not found in list"<<endl;
break;
case 6:a.show();
break;
case 7:exit(1);
}
}
return 0;
}
OUTPUT:

3. Implementation of Circular Linked List.

#include<iostream>
#include<stdlib.h>
template<class T>
struct node
{
T data;
node<T>* next;
node(){}
node(T data)
{
this->data=data;
}
};
template<class T>
class cll
{
protected:
node<T>* header;
int ls;
public:
cll()
{
cout<<"Cll Constructor\n";
header=new node<T>();
header->next=header;
ls=0;
}
~chain();
bool empty() const
{
return ls==0;
}
int size() const
{
return ls;
}
int get(int index) const;
int indexOf(const T& x) const;
void erase(int index);
void insert(int, const T& x);
void output(ostream& out) const;
};
template<class T>
int cll<T>::get(int index) const
{
node<T>* t=header->next;

{
t=t->next;
}
if(t!=header)
return t->data;
else
return -1;
}
template<class T>
int cll<T>::indexOf(const T& x) const
{
int index=0;
header->data=x;
node<T>* ptr=header->next;
while(ptr->data!=x)
{
ptr=ptr->next;
index++;
}
if(ptr==header)
return -1;
else
return index;
}
template<class T>
void cll<T>::erase(int index)
{
node<T>* del;
if(index<0 || index>ls)
{
cout<<"Illegal index\n";
return;
}
node<T>* p;
p=header;
p=p->next;
del=p->next;
p->next=p->next->next;
ls--;
delete del;
}
template<class T>
void cll<T>::insert(int index,const T& x)
{
if(index<0 || index>ls)

{
cout<<"Illegal index\n";
return;
}
node<T>* p;
p=header;
p=p->next;
node<T>* nn=new node<T>(x);
nn->next=p->next;
p->next=nn;
ls++;
}
template<class t>
chain<t>::~chain()
{
while(header->next)
{
node<t> *curr=heard->next;
header->next=cur->next->next;
delete curr;
}
delete header;
}
template<class T>
void cll<T>::display() const
{
cout<<"List is:\n";
for(node<T>* current=header->next;current!=header;current=current->next)
cout<<current->data<<" ";
}
main()
{
cout<<"Main begins\n";
int ch,x,ele,in,index;
char op;
cll<int> c1;
do{
cout<<"MENU:\n1.Empty\n2.Size\n3.Get\n4.IndexOf\n5.Insert\n6.Erase\n7.Display\n";
cout<<"Enter your choice\n";
cin>>ch;
switch(ch)
{
case 1:if(c1.empty()==1)
cout<<"The linked list is empty\n";
else

cout<<"List contain elements\n";

break;
case 2:cout<<"Size of list is "<<c1.size();
cout<<endl;
break;
case 3:cout<<"Enter index to get element\n";
cin>>index;
cout<<"Your ele is "<<c1.get(index);
break;
case 4:cout<<"Enter element to get index\n";
cin>>x;
cout<<"Your index is "<<c1.indexOf(x);
break;
case 5:cout<<"Insert the index and the element\n";
cin>>in>>ele;
c1.insert(in,ele);
break;
case 6:cout<<"Enter the index of ele you want to delete\n";
cin>>x;
c1.erase(x);
break;
case 7: c1.display();
break;
default:exit(0);
}
cout<<"Do you want to continue?\n";
cin>>op;
}while(op=='y');
cout<<"Main ends\n";
}
OUTPUT:

4. Stack Implementation using Arrays.

#include<iostream>
#include<stdlib.h>
template<class t>
class stack
{
t *st;
int top,capacity;
public:
stack(int max)
{
capacity=max;
if(capacity<1)
{
cout<<"capacity must be >=1 \n";
exit(0);
}
st=new t[capacity];
top=-1;
}
int isempty()const;
void push(t &);
t pop();
t topmost()const;
void enhancecapacity();
};
template<class t>
int stack<t>::isempty()const
{
if(top== -1)
return 1;
else
return 0;
}
template<class t>
void stack<t>::push(t &x)
{
if(top==capacity-1)
{
enhancecapacity();
capacity*=2;
}
st[++top]=x;
}
template<class t>

void stack<t>::enhancecapacity()
{
t *tmp=new t[2*capacity];
for(int i=0;i<=top;i++)
tmp[i]=st[i];
delete[]st;
st=tmp;
cout<<"Stack size doubled\n";
}
template<class t>
t stack<t>::pop()
{
if(isempty())
return NULL;
else
{
t x=st[top--];
return x;
}
}
template<class t>
void stack<t>::display() const
{
if(isempty())
cout<"stack is empty\n";
else
for(int i=top;i>=0;i--)
cout<<st[i]<<endl;
}
template<class t>
t stack<t>::topmost()const
{
if(isempty())
return NULL;
else
return st[top];
}
int main()
{
stack<int> s(2);
int c,d;
while(1)
{
cout<<"MENU\n1.push\n2.pop\n3.display\n4.top element\n5.exit\n";
cout<<"SELECT YOUR OPTION\n";

cin>>c;
switch(c)
{
case 1:
cout<<"enter data\n";
cin>>d;
s.push(d);
break;
case 2:
d=s.pop();
if(d!=0)
cout<<"the popped data is "<<d<<endl;
else
cout<<"stack underflow\n";
break;
case 3:
cout<<"the contents of stack are\n";
s.display();
break;
case 4: d=s.topmost();
if(d)
cout<<"top element is : "<<d<<endl;
else
break;
case 5: exit(0);
}
}
}
OUTPUT:

5. Stack Implementation using Linked Lists.

#include<iostream>
#include<stdlib.h>
template <class t>
class stack;
template <class t>
class node
{
t data;
node<t>*link;
friend class stack<t>;
public:
node(t x)
{
data=x;
link=NULL;
}
};
template <class t>
class stack
{
node<t>* top;
public:
stack()
{
top=NULL;
}
void push(t);
t pop();
void display();
t topmost();
};
template<class t>
void stack<t>::push(t x)
{
node<t>*nn=new node<t>(x);
if(top)
nn->link=top;
top=nn;
}
template<class t>
t stack<t>::pop()
{
if(top)
{
node<t>* tmp=top;
top=top->link;
t x=tmp->data;

delete tmp;
return x;
}
return 0;
}
template<class t>
void stack<t>::display()
{
if(top)
{
node<t>*tmp=top;
while(tmp)
{
cout<<tmp->data<<endl;
tmp=tmp->link;
}
}
else
}
template<class t>
t stack<t>::topmost()
{
if(top)
return top->data;
return 0;
}
int main()
{
stack<int> s;
int c,d;
while(1)
{
cout<<"MENU\n1.push\n2.pop\n3.display\n4.top element\n5.exit\n";
cin>>c;
switch(c)
{
case 1:
cin>>d;
s.push(d);
break;
case 2:
d=s.pop();
if(d!=0)
else

break;
case 3:
cout<<"the contents of stack are\n";
s.display();
break;
case 4: d=s.topmost();
if(d)
cout<<"top element is : "<<d<<endl;
else
break;
case 5: exit(0);
}
}
}
OUTPUT:

6. Queue Implementation using Arrays(circular queue)

#include<iostream>
#include<stdlib.h>
template<class t>
class cirq
{
t *cq;
int front,rear,capacity;
public:
cirq(int max)
{
capacity=max;
if(capacity<1)
{
cout<<"capacity must be >=1\n";
exit(0);
}
cq=new t[capacity];
front=rear=-1;
}
int isempty()const;
void push(t &);
t pop();
t frontele()const;
t rearele()const;
void enhancecapacity();
~cirq()
{
delete []cq;
}
};
template<class t>
int cirq<t>::isempty()const
{
if(front==-1 && rear==-1)
return 1;
else
return 0;
}
template<class t>
void cirq<t>::push(t &x)
{
if(front==(rear+1)%capacity)
{
enhancecapacity();
capacity*=2;
}

rear=(rear+1)%capacity;
cq[rear]=x;
if(front==-1)
front=0;
}
template<class t>
void cirq<t>::enhancecapacity()
{
t *tmp=new t[2*capacity];
int i;
for( i=0;i<capacity;i++)
{
rear=(rear+1)%capacity;
tmp[i]=cq[rear];
}
front=0;
rear=i-1;
delete []cq;
cq=tmp;
cout<<"circularQ size is doubled\n";
}
template<class t>
t cirq<t>::pop()
{
if(isempty())
return 0;
t x=cq[front];
if(front==rear)
front=rear=-1;
else
front=(front+1)%capacity;
return x;
}
template<class t>
void cirq<t>::display()const
{
if(isempty())
cout<<"queue underflow\n";
else
{
int i=0;
if(front<=rear)
for(i=front;i<=rear;i++)
cout<<cq[i]<<endl;
else
{
for(i=front;i<capacity;i++)
cout<<cq[i]<<endl;
for(i=0;i<=rear;i++)

cout<<cq[i]<<endl;
}
}
}
template<class t>
t cirq<t>::frontele()const
{
if(isempty())
return 0;
else
return cq[front];
}
template<class t>
t cirq<t>::rearele()const
{
if(isempty())
return 0;
else
return(cq[rear]);
}
int main()
{
cirq<int> c1(2);
int c,d;
while(1)
{
cout<<"MENU\n1.push\n2.pop\n3.display\n4.frontele\n5.rearele\n6.exit\n";
cin>>c;
switch(c)
{
case 1:
cin>>d;
c1.push(d);
break;
case 2:
d=c1.pop();
if(d!=0)
else
cout<<"empty queue\n";
break;
case 3:
cout<<"the contents of circular queue are\n";
c1.display();
break;
case 4: d=c1.frontele();
if(d)

cout<<"front element is : "<<d<<endl;

else
cout<<"q underflow\n";
break;
case 5: d=c1.rearele();
if(d)
cout<<"rear element is :"<<d<<endl;
else
break;
case 6: exit(0);
}
}
}
OUTPUT:

7. Queue Implementation using Linked Lists.

#include<iostream>
#include<stdlib.h>
template<class t>
class queue;
template <class t>
class node
{
t data;
node<t>*link;
friend class queue<t>;
public:
node(t x)
{
data=x;
link=NULL;
}
};
template <class t>
class queue
{
node<t>* front,*rear;
public:
queue()
{
front=rear=NULL;
}
void push(t);
t pop();
void display();
t frontele();
t rearele();
};
template<class t>
void queue<t>::push(t x)
{
node<t>*nn=new node<t>(x);
if(rear)
rear->link=nn;
rear=nn;
if(front==NULL)
front=nn;
}
template<class t>
t queue<t>::pop()
{
if(front)
{

node<t>* tmp=front;
front=front->link;
if(front==NULL)
rear=NULL;
t x=tmp->data;
delete tmp;
return x;
}
return 0;
}
template<class t>
void queue<t>::display()
{
if(front)
{
cout<<"Q elements are:\n";
node<t>*tmp=front;
while(tmp)
{
cout<<tmp->data<<endl;
tmp=tmp->link;
}
}
else
cout<<"queue underflow\n";
}
template<class t>
t queue<t>::frontele()
{
if(front)
return front->data;
return 0;
}
template<class t>
t queue<t>::rearele()
{
if(rear)
return rear->data;
return 0;
}
int main()
{
queue<int> c1;
int c,d;
while(1)
{
cout<<"MENU\n1.push\n2.pop\n3.display\n4.frontele\n5.rearele\n6.exit\n";
cin>>c;

switch(c)
{
case 1:
cin>>d;
c1.push(d);
break;
case 2:
d=c1.pop();
if(d!=0)
else
cout<<"empty queue\n";
break;
case 3:
cout<<"the contents of queue are\n";
c1.display();
break;
case 4: d=c1.frontele();
if(d)
cout<<"front element is : "<<d<<endl;
else
break;
case 5: d=c1.rearele();
if(d)
cout<<"front element is :"<<d<<endl;
else
break;
case 6: exit(0);
}
}
}
OUTPUT:

8. Infix to postfix Conversion using Stacks.

#include<iostream>
#include<stdlib.h>
#include<cstring>
template <class t>
class stack
{
t *st;
int top,capacity,i;
public:stack(int max)
{
capacity=max;
if(capacity<1)
{
cout<<"capacity must be >1\n";
exit(0);
}
st=new t[capacity];
top=-1;
int isempty()
{
return top==-1;
}
void enhancecapacity()
{
t *tmp=new t[capacity*2];
for(i=0;i<=top;i++)
tmp[i]=st[i];
delete []st;
st=tmp;
cout<<"stack size is doubled\n";
}
void push(t &x)
{
if(top==capacity-1)
{
enhancecapacity();
capacity*=2;
}
st[++top]=x;
}
t pop()

{
if(isempty())
return -1;
t x=st[top--];
return x;
}
void disp()
{
if(isempty())
cout<<"empty\n";
else
{
for(i=top;i>=0;i--)
cout<<st[i]<<"\t";
cout<<endl;
}
}
t topmost()
{
if(isempty())
return -1;
return st[top];
}
};
int priority(char ch);
void convert(char *a)
{
int x,j=0;
stack<char>st(20);
char b[20];
int len=strlen(a);
for(int i=0;i<len;i++)
{
char ch=a[i];
if(isalpha(ch))
b[j++]=ch;
else if(isdigit(ch))
b[j++]=ch;
else if(ch=='(')
{
while(st.topmost()!='(')
b[j++]=st.pop();
st.pop();
}
else
{
while(priority(ch)<=priority(st.topmost()))
b[j++]=st.pop();
st.push(ch);

}
}
while(!st.isempty())
b[j++]=st.pop();
b[j]='\0';
cout<<"postfix expression is..."<<b;
}
int priority(char ch)

{
switch(ch)
{
case '^':return(5);
case '*':
case '/':return(4);
case '+':
case '-':return(3);
case '(':return(2);
case ')':return(1);
}
return(0);
}
main()
{
char p[20];
cout<<"enter infix expression : ";
cin>>p;
convert(p);
}
OUTPUT:

9. Evaluation of postfix Expression.

#include<iostream>
#include<ctype.h>
template <class T>
class stack
{
T *s;
int top,cap;
public:stack(int max)
{
cap=max;
if(cap<1)
{
cout<<"capacity should not be < 1"<<endl;
exit(0);
}
s=new T[cap];
top=-1;
}
int isempty()
{
if(top==-1) return 1;
else return 0;
}
void push(T x)
{
if(top==cap-1)
{
enhancecap();
cap*=2;
}
s[++top]=x;
}
void enhancecap()
{
T *temp=new T[2*cap];
for(int i=0;i<top;i++)
temp[i]=s[i];
delete s;
s=temp;
}
T pop()
{
if(isempty()) return 0;
else
{
T x=s[top--];
return x;

}
}
T topmost()
{
if(isempty()) return 0;
else return s[top];
}
};
void eval(char *b)
{
int i=0,p1,p2,p3;
stack<int> s1(20);
while(b[i]!='\0')
{
if(b[i]>='0' && b[i]<='9')
s1.push(b[i]-48);
else
{
p1=s1.pop(); p2=s1.pop();
switch(b[i])
{
case '^':p3=pow(p2,p1);
s1.push(p3); break;
case '+':p3=p2+p1;
s1.push(p3); break;
case '-':p3=p2-p1;
s1.push(p3); break;
case '*':p3=p1*p2;
s1.push(p3); break;
case '/':p3=p2/p1;
s1.push(p3); break;
}
}
i++;
}
cout<<endl<<"result :"<<s1.pop()<<endl;
}
main()
{
char p[20];
cout<<"enter the postfix expression"<<endl;
cin>>p;
eval(p);
}
OUTPUT:

10. Polynomial Arithmetic using Linked List.

#include<iostream>
#include<cmath>
template<class T>
class pol;
template<class T>
class node
{
T c;
int p;
node<T> *link;
friend class pol<T>;
};
template<class T>
class pol
{
node<T> *first;
public: pol()
{
first=NULL;
}
void append(node<T> *k)
{
node<T> *q;
k->link=NULL;
if(first==NULL)
first=k;
else
{
q=first;
while(q->link!=NULL)
q=q->link;
q->link=k;
}
}
void create()
{
node<T> *k;
T coe;
int pow;
cout<<"enter the coefficient value and power value in decreasing order";
cin>>coe;
first=NULL;
while(coe!=0)
{
cin>>pow;
k=new node<T>;
k->c=coe;

k->p=pow;
append(k);
cin>>coe;
}
}
T eval(T x)
{
T sum=0;
node<T> *temp;
temp=first;
while(temp!=NULL)
{
sum+=temp->c*pow(x,temp->p);
temp=temp->link;
}
return sum;
}
void add(pol<T> a,pol<T> b)
{
node<T> *t1,*t2,*k;
T sum;
t1=a.first;
t2=b.first;
while(t1!=NULL&&t2!=NULL)
{
if(t1->p>t2->p)
{
k=new node<T>;
k->c=t1->c;
k->p=t1->p;
append(k);
t1=t1->link;
}
else if(t1->p<t2->p)
{
k=new node<T>;
k->c=t2->c;
k->p=t2->p;
append(k);
t2=t2->link;
}
else
{
sum=t1->c+t2->c;
if(sum==0)
{
t1=t1->link;
t2=t2->link;
}

else
{
k=new node<T>;
k->c=sum;
k->p=t1->p;
append(k);
t1=t1->link;
t2=t2->link;
}
}
}
while(t1!=NULL)
{
k=new node<T>;
k->c=t1->c;
k->p=t1->p;
append(k);
t1=t1->link;
}
while(t2!=NULL)
{
k=new node<T>;
k->c=t2->c;
k->p=t2->p;
append(k);
t2=t2->link;
}
}
void display()
{
node<T> *q;
if(first==NULL)
cout<<"no polynomial created\n";
else
{
cout<<"polynomial is\n";
q=first;
while(q)
{
cout<<q->c<<"x^"<<q->p;
if(q->link!=NULL)
cout<<"+";
q=q->link;
}
}
}
void multiply(pol<T> a,pol<T> b)
{
node<T> *t1,*t2;

pol<T> d,e;
d.first=new node<T>;
t1=a.first;
t2=b.first;
while(t1!=NULL)
{
while(t2!=NULL)
{
d.first->c=t1->c*t2->c;
d.first->p=t1->p+t2->p;
d.first->link=NULL;
e.add(*this,d);
erase();
t2=t2->link;
}
t1=t1->link;
t2=b.first;
}
e.display();
}
void erase()
{
node<T> *q;
while(first!=NULL)
{
q=first;
first=first->link;
delete q;
}
}
};
main()
{
pol<int> j,l,w,r;
j.create();
l.create();
r.add(j,l);
r.display();
r.multiply(j,l);
}
OUTPUT:

11. Hashing Implementation with Arrays.

#include<iostream>
#include<cstdlib>
#include<cstdio>
const int TABLE_SIZE =5;
/*
* HashEntry Class Declaration
*/
class HashEntry
{
public:
int key;
int value;
HashEntry(int key, int value)
{
this->key = key;
this->value = value;
}
};
class HashMap
{
private:
HashEntry **table;
int neverUsed[TABLE_SIZE];
public:
HashMap()
{
table = new HashEntry * [TABLE_SIZE];
for (int i = 0; i< TABLE_SIZE; i++)
{
table[i] = NULL;
neverUsed[i]=1;
}
}
/*
* Hash Function
*/
int HashFunc(int key)
{
return key % TABLE_SIZE;
}
void Insert(int key, int value)
{
int hash = HashFunc(key);
int tmp=hash;
while (table[hash] != NULL && table[hash]->key != key)
{

hash = HashFunc(hash + 1);

if(hash==tmp){
cout<<"Table full\n";
return;
}
}
if (table[hash] != NULL)
delete table[hash];
table[hash] = new HashEntry(key, value);
neverUsed[hash]=0;
}
int Search(int key)

{
int tmp=hash;
while (!neverUsed[hash])
{
if(table[hash]==NULL || table[hash]->key != key)
else
break;
if(hash==tmp)
return -1;
}
if (neverUsed[hash])
return -1;
else
return table[hash]->value;
}
void Remove(int key)

{
int tmp=hash;
int f=0;
while (!neverUsed[hash])
{
if(table[hash]==NULL || table[hash]->key != key)
else
break;
if(hash==tmp)
{
f=1;
break;
}
}

if (neverUsed[hash]||f)
{
cout<<"Element Not Found:";
}
else
{
delete table[hash];
table[hash]=NULL;
cout<<"Element Deleted"<<endl;
}
void display()
{
for(int i=0;i<TABLE_SIZE;i++)
{
if(table[i]!=NULL)
cout<<"["<<i<<","<<table[i]->key<<","<<table[i]->value<<"] ";
else
cout<<"["<<i<<",,]";
}
}
~HashMap()
{
for (int i = 0; i < TABLE_SIZE; i++)
{
if (table[i] != NULL)
delete table[i];
delete[] table;
}
}
};
int main()
{
HashMap hash;
int key, value;
int choice;
while (1)
{
cout<<"\n----------------------"<<endl;
cout<<"Operations on Hash Table"<<endl;
cout<<"\n----------------------"<<endl;
cout<<"1.Insert element into the table"<<endl;
cout<<"2.Search element from the key"<<endl;
cout<<"3.Delete element at a key"<<endl;
cout<<"4.Display"<<endl;
cout<<"5.Exit"<<endl;
cout<<"Enter your choice: ";

cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter element to be inserted: ";
cin>>value;
cout<<"Enter key at which element to be inserted: ";
cin>>key;
hash.Insert(key, value);
break;
case 2:
cout<<"Enter key of the element to be searched: ";
cin>>key;
if (hash.Search(key) == -1)
{
cout<<"No element found at key "<<key<<endl;
continue;
}
else
{
cout<<"Element at key "<<key<<" : ";
cout<<hash.Search(key)<<endl;
}
break;
case 3:
cout<<"Enter key of the element to be deleted: ";
cin>>key;
hash.Remove(key);
break;
case 4:
hash.display();
break;
case 5:
exit(1);
default:
cout<<"\nEnter correct option\n";
}
}
return 0;
}
OUTPUT:

12. Binary Tree Traversals (Recursive)

#include <iostream>
template<class t>
//INCLUDE ARRAY QUEUE CLASS HERE
template <class T>
struct Node
{
T element;
Node<T> *left, *right;
Node()
{
left = right = NULL;
}
Node(T e)
{
element=e;
}
Node(T e, Node *lc, Node *rc)
{
left = lc;
right = rc;
}
};
template <class T>
void visit(Node<T> *x)
{
cout << x->element << ' ';
}
template <class T>

void preOrder(Node<T> *t)
{
if (t != NULL)
{
visit(t);
preOrder(t->left); // do left subtree
preOrder(t->right); // do right subtree
}
}
template <class T>
void inOrder(Node<T> *t)
{
if (t != NULL)
{
inOrder(t->left); // do left subtree
visit(t); // visit tree root
inOrder(t->right); // do right subtree

}
}
template <class T>
void postOrder(Node<T> *t)
{
if (t != NULL)
{
postOrder(t->left); // do left subtree
postOrder(t->right); // do right subtree
visit(t); // visit tree root
}
}
template <class T>
void levelOrder(Node<T> *t)
{
queue<Node<T>*> q(10);
while (t != NULL)
{
visit(t); // visit t
// put t's children on queue
if (t->left != NULL)
q.push(t->left);
if (t->right != NULL)
q.push(t->right);
// get next node to visit

if(!q.isempty())
{
t = q.frontele();
q.pop();
}
else
return;
}
}
int main(void)
{
Node<int> *n1, *n2, *n3,*n4,*n5;
bool b;int k;
n1= new Node<int> (4);
n3= new Node<int> (2,n1,n2);
cout << "Inorder sequence is ";

inOrder(n5);
cout << endl;
cout << "Preorder sequence is ";

preOrder(n5);
cout << endl;
cout << "Postorder sequence is ";
postOrder(n5);
cout << endl;
cout << "Level order sequence is ";
levelOrder(n5);
}
OUTPUT:

13. Binary Tree Traversals (Iterative)

#include <iostream>
//INCLUDE STACK CLASS CODE HERE
template <class T>
struct Node
{
T element;
Node<T> *left, // left subtree
*right; // right subtree
Node() {left = right = NULL;}

Node(T x)
{
element=x;
}
Node(T x,Node *theLeftChild,Node *theRightChild)
{
element=x;
left = theLeftChild;
right = theRightChild;
}
};
template<class t>
void inOrder(Node<t> *root)
{
if(root==NULL)
return;
stack<Node<t>*> s(20);
Node<t> *curr = root;
while (!s.isempty() || curr != NULL)
{
if (curr != NULL)
{
s.push(curr);
curr = curr->left;
}
else
{
curr = s.topmost();
s.pop();
cout << curr->element << " ";
curr = curr->right;
}
}
}
template<class t>

void preOrder(Node<t> *root)
{
if (root == NULL)
return;
stack<Node<t> *> s(20);
s.push(root);
while (!s.isempty())
{
Node<t> *curr = s.topmost();
cout<<curr->element<<" ";
s.pop();
if (curr->right)
s.push(curr->right);
if (curr->left)
s.push(curr->left);
}
}
template<class t>
void postOrder(Node<t>* root)
{
if(root==NULL)
return;
stack<Node<t>*> s(20);
s.push(root);
stack<int> out(20);
while (!s.isempty())
{
Node<t> *curr = s.topmost();
s.pop();
out.push(curr->element);
if (curr->left)
s.push(curr->left);
if (curr->right)
s.push(curr->right);
}
while (!out.isempty())
{
cout << out.topmost() << " ";
out.pop();
}
}
int main(void)
{
Node<int> *n1, *n2, *n3,*n4,*n5,*clonen5,*mirrorn5;



cout << "Inorder sequence is ";

inOrder(n5);
cout << endl;
cout << "Preorder sequence is ";
preOrder(n5);
cout << endl;
cout << "Postorder sequence is ";
postOrder(n5);
cout << endl;
return 0;
}
OUTPUT:

14. Operations on Binary Trees

#include <iostream>
//****INCLUDE QUEUE PROGRAM HERE WITHOUT MAIN
template <class T>
struct Node
{
T element;
Node<T> *left, // left subtree
*right; // right subtree
Node() {left = right = NULL;}
Node(const T& theElement):element(theElement)
{
}
Node(const T& theElement,
Node *theleft,
Node *theright)
:element(theElement)
{
left = theleft;
right = theright;
}
};
template<class t>
bool iterativeSearch(Node<t> *root,t x)
{
if (root == NULL)
return false;
queue<Node<t> *> q(20);
q.push(root);
while (!q.isempty())
{
Node<t> *curr = q.frontele();
if (curr->element == x)
return true;
q.pop();
if (curr->left != NULL)
q.push(curr->left);
if (curr->right != NULL)
q.push(curr->right);
}
return false;
}
template<class T>
int height(Node<T> *temp)
{
int h = 0;
if (temp != NULL)

{
int l_height = height (temp->left);
int r_height = height (temp->right);
int max_height = max (l_height, r_height);
h = max_height + 1;
}
return h;
}
template<class t>
void deleteTree(Node<t>* root)
{
if (root == NULL) return;
deleteTree(root->left);
deleteTree(root->right);
cout<<"\n Deleting node:"<< root->element;
delete root;
}
template<class t>
Node<t>* clone(Node<t>* root)
{
Node<t>* nn=NULL;
if(root)
{
nn=new Node<t>();
nn->element=root->element;
nn->left=clone(root->left);
nn->right=clone(root->right);
}
return nn;
}
template<class t>
Node<t>* mirror(Node<t>* root)
{
Node<t>* m_root = NULL;
if(root)
{
m_root = new Node<t>();
m_root->element=root->element;
m_root->left = mirror(root->right);
m_root->right = mirror(root->left);
}
return m_root;
}
template <class T>

void inOrder(Node<T> *t)
{
if (t != NULL)
{

inOrder(t->left); // do left subtree

cout<<t->element<<" "; // visit tree root
inOrder(t->right); // do right subtree
}
}
int main(void)
{
Node<int> *n1, *n2, *n3,*n4,*n5;

bool b;int k;
cout<<"SEARCH : Enter the Element that you want to search for:";
cin>>k;
b=iterativeSearch(n5,k);
if(b==true)
cout<<"Element is existed\n";
else
cout<<"Element is not existed in the tree\n";
cout<<"The inorder of n5 is:";
inOrder(n5);
Node<int> *m=mirror(n5);
cout<<"The inorder of tree after mirror is:";

inOrder(m);
cout<<endl;
Node<int> *n=clone(n5);
cout<<endl;
cout<<"The inorder of tree after cloning is:";
inOrder(n);
cout<<"Tree height is:"<<height(n5)<<endl;

cout<<"Deleting Entire Tree:";
deleteTree(n5);
return 0;
}
OUTPUT:

15. Binary Search Tree Implementation

#include<iostream>
struct Node
{
int data;
struct Node *left;
struct Node *right;
}*root;
class BST
{
public:
Node* insert(Node *, int );
Node* deleteNode(Node *,int);
void display(Node *, int);
BST()
{
root = NULL;
}
};
Node * minValueNode(Node* node)
{
Node* current = node;
while (current->left != NULL)
current = current->left;
return current;
}
Node* BST::deleteNode(Node* root, int data)
{
if (root == NULL)
{
cout<<"INFO: Element Not found"<<endl;
return root;
}
if ( data < root->data )
root->left = deleteNode(root->left, data);
else if( data > root->data )
root->right = deleteNode(root->right, data);
else
{
if( (root->left == NULL) || (root->right == NULL) )
{
Node *temp = root->left ? root->left : root->right;
if (temp == NULL)
{
temp = root;
root = NULL;
}
else

*root = *temp;
delete temp;
}
else
{
Node* temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
}
return root;
}
Node *BST::insert(Node *root, int value)
{
if (root == NULL)
{
root = new Node;
root->data = value;
root->left = NULL;
root->right = NULL;
return root;
}
else if (value < root->data)
{
root->left = insert(root->left, value);
}
else if (value > root->data)
{
root->right = insert(root->right, value);
}
else
{
cout<<"INFO: Element already Exist"<<endl;
return root;
}
}
void BST::display(Node *ptr, int level)
{
int i;
if (ptr!=NULL)
{
display(ptr->right, level + 1);
printf("\n");
if (ptr == root)
cout<<"Root -> ";
for (i = 0; i < level && ptr != root; i++)
cout<<" ";
cout<<ptr->data;
display(ptr->left, level + 1);

}
}
int main()
{
int choice, item;
BST avl;
while (1)
{
cout<<"\n---------------------"<<endl;
cout<<"BST Implementation"<<endl;
cout<<"\n---------------------"<<endl;
cout<<"1.Insert Element into the tree"<<endl;
cout<<"2.Delete Element"<<endl;
cout<<"3.Display Tree"<<endl;
cout<<"Enter your Choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter value to be inserted: ";
cin>>item;
root = avl.insert(root, item);
break;
case 2:
cout<<"Enter the value to be deleted:";
cin>>item;
avl.deleteNode(root,item);
break;
case 3:
if (root == NULL)
{
cout<<"Tree is Empty"<<endl;
continue;
}
cout<<"BST:"<<endl;
avl.display(root, 1);
break;
case 4:
exit(1);
break;
default:
cout<<"Wrong Choice"<<endl;
}
}
return 0;
}
OUTPUT:

16. AVL Tree Implementation

#include<iostream>
struct Node
{
int data;
struct Node *left;
struct Node *right;
}*root;
class avlTree
{
public:
int height(Node *);
int diff(Node *);
Node *rr_rotation(Node *);
Node *ll_rotation(Node *);
Node *lr_rotation(Node *);
Node *rl_rotation(Node *);
Node* balance(Node *);
Node* insert(Node *, int );
Node* deleteNode(Node *,int);
void display(Node *, int);
avlTree()
{
root = NULL;
}
};
int avlTree::height(Node *temp)
{
int h = 0;
if (temp != NULL)
{
int max_height = max (l_height, r_height);
h = max_height + 1;
}
return h;
}
int avlTree::diff(Node *temp)
{
int b_factor= l_height - r_height;
return b_factor;
}
Node *avlTree::rr_rotation(Node *parent)
{
Node *temp;

temp = parent->right;
parent->right = temp->left;
temp->left = parent;
return temp;
}
Node *avlTree::ll_rotation(Node *parent)
{
Node *temp;
temp = parent->left;
parent->left = temp->right;
temp->right = parent;
return temp;
}
Node *avlTree::lr_rotation(Node *parent)
{
Node *temp;
temp = parent->left;
parent->left = rr_rotation (temp);
return ll_rotation (parent);
}
Node *avlTree::rl_rotation(Node *parent)
{
Node *temp;
temp = parent->right;
parent->right = ll_rotation (temp);
return rr_rotation (parent);
}
Node *avlTree::balance(Node *temp)
{
int bal_factor = diff (temp);
if (bal_factor > 1)
{
if (diff (temp->left) > 0)
temp = ll_rotation (temp);
else
temp = lr_rotation (temp);
}
else if (bal_factor < -1)
{
if (diff (temp->right) > 0)
temp = rl_rotation (temp);
else
temp = rr_rotation (temp);
}
return temp;
}
Node * minValueNode(Node* node)
{
Node* current = node;

/* loop down to find the leftmost leaf */

while (current->left != NULL)
current = current->left;
return current;
}
Node* avlTree::deleteNode(Node* root, int data)
{
if (root == NULL)
return root;
if ( data < root->data )
root->left = deleteNode(root->left, data);
else if( data > root->data )
root->right = deleteNode(root->right, data);
else
{
if( (root->left == NULL) || (root->right == NULL) )
{
Node *temp = root->left ? root->left : root->right;
if (temp == NULL)
{
temp = root;
root = NULL;
}
else
*root = *temp;
delete temp;
}
else
{
Node* temp = minValueNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
}
if (root == NULL)
return root;
root=balance(root);
return root;
}
Node *avlTree::insert(Node *root, int value)
{
if (root == NULL)
{
root = new Node;
root->data = value;
root->left = NULL;
root->right = NULL;

return root;
}
else if (value < root->data)
{
root->left = insert(root->left, value);
root = balance (root);
}
else if (value >= root->data)
{
root->right = insert(root->right, value);
root = balance (root);
}
return root;
}
void avlTree::display(Node *ptr, int level)
{
int i;
if (ptr!=NULL)
{
display(ptr->right, level + 1);
printf("\n");
if (ptr == root)
cout<<"Root -> ";
for (i = 0; i < level && ptr != root; i++)
cout<<" ";
cout<<ptr->data;
display(ptr->left, level + 1);
}
}
int main()
{
int choice, item;
avlTree avl;
while (1)
{
cout<<"\n---------------------"<<endl;
cout<<"AVL Tree Implementation"<<endl;
cout<<"\n---------------------"<<endl;
cout<<"1.Insert Element into the tree"<<endl;
cout<<"2.Delete Element"<<endl;
cout<<"3.Display Balanced AVL Tree"<<endl;
cout<<"Enter your Choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter value to be inserted: ";
cin>>item;

root = avl.insert(root, item);

break;
case 2:
cout<<"Enter the value to be deleted:";
cin>>item;
avl.deleteNod-e(root,item);
break;
case 3:
if (root == NULL)
{
cout<<"Tree is Empty"<<endl;
continue;
}
cout<<"Balanced AVL Tree:"<<endl;
avl.display(root, 1);
break;
case 4:
exit(1);
break;
default:
cout<<"Wrong Choice"<<endl;
}
}
return 0;
}
OUTPUT:

17. Implementation of Selection Sort Algorithm.

#include < iostream >
class selsort {
int * a, i, j, m, n;
public: selsort() {
cout << "size" << endl;
cin >> n;
a = new int[n];
for (i = 0; i < n; i++) {
cin >> a[i];
}
}
void dis() {
cout << "elements are" << endl;
for (i = 0; i < n; i++)
cout << endl << a[i] << endl;
}
void sort() {
for (i = 0; i < n; i++) {
int min= i;
for (j = i + 1; j < n; j++) {
if (a[i] > a[j])
min = j;
}
if (min != i) {
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
}
};
int main() {
selsort s;
s.sort();
s.dis();
}
OUTPUT:

18. Implementation of Shell Sort Algorithm.

#include<iostream>
// A function implementing Shell sort.
void ShellSort(int a[], int n)
{
int i, j, k, temp;
// Gap 'i' between index of the element to be compared, initially n/2.
for(i = n/2; i > 0; i = i/2)
{
for(j = i; j < n; j++)
{
for(k = j-i; k >= 0; k = k-i)
{
// If value at higher index is greater, then break the loop.
if(a[k+i] >= a[k])
break;
else
{
temp = a[k];
a[k] = a[k+i];
a[k+i] = temp;
}
}
}
}
}
int main()
{
int n, i;
cout<<"\nEnter the number of data element to be sorted: ";
cin>>n;
int arr[n];
for(i = 0; i < n; i++)
{
cout<<"Enter element "<<i+1<<": ";
cin>>arr[i];
}
ShellSort(arr, n);
cout<<"\nSorted Data ";
for (i = 0; i < n; i++)
cout<<"->"<<arr[i];
return 0;
}
OUTPUT:

19. Implementation of Merge Sort Algorithm.

class Sorting
{
public:
Sorting()
{
cin >> n;
a = new int[n];
for (i = 0; i < n; i++)
{
cin >> a[i];
}
}
void dis()
{
for (i = 0; i < n; i++)
}
void sort()
{
mergesort(0,n-1);
}
void Merge(int low, int mid, int high)
{
// We have low to mid and mid+1 to high already sorted.
int i, j, k, temp[high-low+1];
i = low;
k = 0;
j = mid + 1;
// Merge the two parts into temp[].
while (i <= mid && j <= high)
{
if (a[i] < a[j])
{
temp[k] = a[i];
k++;
i++;
}
else
{
temp[k] = a[j];
k++;
j++;
}

}
// Insert all the remaining values from i to mid into temp[].
while (i <= mid)
{
temp[k] = a[i];
k++;
i++;
}
// Insert all the remaining values from j to high into temp[].
while (j <= high)
{
temp[k] = a[j];
k++;
j++;
}
// Assign sorted data stored in temp[] to a[].
for (i = low; i <= high; i++)
{
a[i] = temp[i];
}
}
// A function to split array into two parts.
void MergeSort(int low, int high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
// Split the data into two half.
MergeSort(low, mid);
MergeSort(mid+1, high);
// Merge them to get sorted output
Merge(low, mid,high);
}
}
};
int main()
{
Sorting s;
s.sort();
s.dis();
}
OUTPUT:

20. Implementation of Quick Sort Algorithm.

class sorting
{
public:
sorting()
{
cin >> n;
a = new int[n];
for (i = 0; i < n; i++)
{
cin >> a[i];
}
}
void dis()
{
for (i = 0; i < n; i++)
}
void sort()
{
quicksort(0,n-1);
}
void quick_sort(int low,int high)

{
int j;
if(low<high)
{
Int pivot =a[low];

i=low;
j=high;
while(i<j)
{
while(a[i]<=pivot&&i<=high)
i++;
while(pivot<a[j])
j--;
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;

}
}
a[low]=a[j];
a[j]=pivot;
quick_sort(low,j-1);
quick_sort(j+1,high);
}
}
};
int main()
{
sorting s;
s.sort();
s.dis();
}
OUTPUT:

21. Implementation of Heap Sort Algorithm.

#include<iostream>
template<class t>
class heap
{
int *a,n;
public:
heap(int x)
{
n=x;
a=new int[n];
}
void accept();
void display();
void heapsort();
void heapify(t*,int,int);
};
template<class t>
void heap<t>::heapsort()
{
t x;
for(int i=n/2-1;i>=0;i--)
heapify(a,i,n);
for(int i=n-1;i>=1;i--)
{
t x=a[i];
a[i]=a[0];
a[0]=x;
heapify(a,0,i);
}
}
template<class t>
void heap<t>::heapify(t *a,int i,int n)
{
int j;
j=2*i+1;
while(j<=n-1)
{
if(j<n-1)
{
if(a[j]<a[j+1])
j++;
}
if(a[i]<a[j])
{
t x=a[i];
a[i]=a[j];
a[j]=x;

}
i=j;
j=2*i+1;
}
}
template<class t>
void heap<t>::accept()
{
for(int i=0;i<n;i++)
cin>>a[i];
}
template<class t>
void heap<t>::display()
{
for(int i=0;i<n;i++)
cout<<a[i]<<"\t";
cout<<endl;
}
int main()
{
int k;
cout<<"enter number of elements\n";
cin>>k;
heap<int> h(k);
h.accept();
cout<<"Before sorting array is:\n";
h.display();
h.heapsort();
cout<<"After sorting array is:\n";
h.display();
}
OUTPUT:

22. Implementation of BFS graph Traversal Technique.

#include<iostream>
#include<stdlib.h>
int cost[10][10],i,j,k,n,queue[10],front=0,rear=0,v,visit[10],visited[10];
int main()
{
int m;
cout <<"enter no of vertices ";
cin >> n;
cout <<"enter 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;
queue[rear++]=j;
}
v=queue[front++];
cout<<v << " ";
k++;
visited[v]=1;
}
OUTPUT:

23. Implementation of DFS graph Traversal Technique.

#include<iostream>
#include<stdlib.h>
int cost[10][10],i,j,k,n,stack[10],top,v,visit[10],visited[10];
int main()
{
int m;
cout <<"enterno 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;
stack [top]=j;
top++;
}
v= stack [--top];
cout<<v << " ";
k++;
visited[v]=1;
}
OUTPUT:

24. Implementation of Binary Search.

#include<iostream>
int main()
{
int n, i, arr[50], search, first, last, middle;

cout<<"Enter total number of elements :";
cin>>n;
cout<<"Enter "<<n<<" number :";
for (i=0; i<n; i++)
{
cin>>arr[i];
}
cout<<"Enter a number to find :";
cin>>search;
first = 0;
last = n-1;
middle = (first+last)/2;
while (first <= last)
{
if(arr[middle] < search)
{
first = middle + 1;
}
else if(arr[middle] == search)
{
cout<<search<<" found at location "<<middle+1<<"\n";
break;
}
else
{
last = middle - 1;
}
middle = (first + last)/2;
}
if(first > last)
{
cout<<"Not found! "<<search<<" is not present in the list.";
}
}
OUTPUT:

Full Record

Uploaded by

Document Informationclick to expand document information

Copyright:

Available Formats

Full Record

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Full Record

Uploaded by

Copyright:

Available Formats

Data Structures Lab (PC351CS)

M.V.S.R ENGINEERING COLLEGE

Certified that this is a bonafide work of lab experiments carried out by

Mr/Ms._________________________________ bearing Roll.No. _______________________ under the

COMPUTER SCIENCE & ENGINEERING during the academic year 2017–2018.

Internal Examiner External Examiner

CSE Department MVSR Engineering College

M.V.S.R ENGINEERING COLLEGE

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

2 Implementation of Double Linked List.

4 Stack Implementation using Arrays.

8 Infix to postfix Conversion using Stacks.

9 Evaluation of postfix Expression.

16 AVL Tree Implementation.

CSE Department MVSR Engineering College

1. Implementation of Single Linked List.

CSE Department 1 MVSR Engineering College

CSE Department 2 MVSR Engineering College

CSE Department 3 MVSR Engineering College

CSE Department 4 MVSR Engineering College

CSE Department 5 MVSR Engineering College

CSE Department 6 MVSR Engineering College

cout<<"data at index i is: "<<e<<endl;

CSE Department 7 MVSR Engineering College

2. Implementation of Double Linked List.

CSE Department 8 MVSR Engineering College

CSE Department 9 MVSR Engineering College

int indexof(T ele)

CSE Department 10 MVSR Engineering College

CSE Department 11 MVSR Engineering College

CSE Department 12 MVSR Engineering College

3. Implementation of Circular Linked List.

CSE Department 13 MVSR Engineering College

CSE Department 14 MVSR Engineering College

CSE Department 15 MVSR Engineering College

cout<<"List contain elements\n";

CSE Department 16 MVSR Engineering College

4. Stack Implementation using Arrays.

CSE Department 17 MVSR Engineering College

CSE Department 18 MVSR Engineering College

CSE Department 19 MVSR Engineering College

5. Stack Implementation using Linked Lists.

CSE Department 20 MVSR Engineering College

CSE Department 21 MVSR Engineering College

CSE Department 22 MVSR Engineering College

6. Queue Implementation using Arrays(circular queue)

CSE Department 23 MVSR Engineering College

CSE Department 24 MVSR Engineering College

CSE Department 25 MVSR Engineering College

cout<<"front element is : "<<d<<endl;

CSE Department 26 MVSR Engineering College

7. Queue Implementation using Linked Lists.

CSE Department 27 MVSR Engineering College

CSE Department 28 MVSR Engineering College

CSE Department 29 MVSR Engineering College

8. Infix to postfix Conversion using Stacks.

CSE Department 30 MVSR Engineering College

CSE Department 31 MVSR Engineering College

Mr/Ms.___________ bearing Roll.No. _ under the

Node<int> n1, n2, n3,n4,n5,clonen5,*mirrorn5;

Node<int> n1, n2, n3,n4,*n5;