Archive for April 2014
#include< iostream >
#include< cstdlib >
#include< string >
using namespace std;
struct tree
{
int info;
tree *Left, *Right;
};
tree *root;
class Binary_tree
{
string path;
public:
Binary_tree();
void insert1(int);
tree *insert2(tree *, tree *);
void search(int);
void pretrav(tree *);
void intrav(tree *);
void posttrav(tree *);
};
Binary_tree::Binary_tree()
{
root = NULL;
}
tree* Binary_tree::insert2(tree *temp,tree *newnode)
{
if(temp==NULL)
{
temp=newnode;
}
else if(temp->info < newnode->info)
{
insert2(temp->Right,newnode);
if(temp->Right==NULL)
temp->Right=newnode;
}
else
{
insert2(temp->Left,newnode);
if(temp->Left==NULL) temp->Left=newnode;
}
return temp;
}
void Binary_tree::insert1(int n)
{
tree *temp=root,*newnode;
newnode=new tree;
newnode->Left=NULL;
newnode->Right=NULL;
newnode->info=n;
root=insert2(temp,newnode);
}
void Binary_tree::pretrav(tree *t = root)
{
if(root == NULL)
{
cout<<"Nothing to display";
}
else if(t != NULL)
{
cout<< t->info<<" ";
pretrav(t->Left);
pretrav(t->Right);
}
}
void Binary_tree::intrav(tree *t = root)
{
if(root==NULL)
{
cout<<"Nothing to display";
}
else if(t!=NULL)
{
intrav(t->Left);
cout<< t->info<<" ";
intrav(t->Right);
}
}
void Binary_tree::posttrav(tree *t = root)
{
if(root==NULL)
{
cout<<"Nothing to display";
}
else if(t!=NULL)
{
posttrav(t->Left);
posttrav(t->Right);
cout<< t->info<<" ";
}
}
void Binary_tree::search(int key)
{
tree *temp=root,*parent=root;
path = "";
if(temp==NULL)
{
cout<<"The tree is empty"<< endl;
}
else
{
path = "root";
while(temp!=NULL && temp->info!=key)
{
parent=temp;
if(temp->info< key)
{
temp=temp->Right;
path += "->Right";
}
else
{
temp=temp->Left;
path += "->Left";
}
}
}
if(temp==NULL)
{
cout<<"Key not found!";
}
else
{
cout<<"Key is found\n";
cout<<"Paht is: ";
cout<< path;
}
}
int main()
{
Binary_tree bt;
int choice, n, key;
while(1)
{
cout<<"\n\t1. Insert\n\t2. Search\n\t3. Preorder Traversal\n\t4. Inorder Treversal\n\t5. Postorder Traversal\n\t6. Exit"<< endl;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter item: ";
cin>>n;
bt.insert1(n);
break;
case 2:
cout<<"Enter element to search: ";
cin>>key;
bt.search(key);
break;
case 3:
cout<< endl;
bt.pretrav();
break;
case 4:
cout<< endl;
bt.intrav();
break;
case 5:
cout<< endl;
bt.posttrav();
break;
case 6:
exit(0);
}
}
return 0;
}
Sorted Doubly Linked List with Insertion and Deletion
Posted by Naveen's Blogs
Tag :
Data Structures,
Linked list
#include < iostream >
#include < cstdlib >
#include < string >
using namespace std;
class Dllist
{
private:
typedef struct Node
{
string name;
Node* next;
Node* prev;
};
Node* head;
Node* last;
public:
Dllist()
{
head = NULL;
last = NULL;
}
bool empty() const { return head==NULL; }
friend ostream& operator <<(ostream& ,const Dllist& );
void Insert(const string& );
void Remove(const string& );
};
void Dllist::Insert(const string& s)
{
// Insertion into an Empty List.
if(empty())
{
Node* temp = new Node;
head = temp;
last = temp;
temp->prev = NULL;
temp->next = NULL;
temp->name = s;
}
else
{
Node* curr;
curr = head;
while( s>curr->name && curr->next != last->next) curr = curr->next;
if(curr == head)
{
Node* temp = new Node;
temp->name = s;
temp->prev = curr;
temp->next = NULL;
head->next = temp;
last = temp;
// cout<<" Inserted "<< s <<" After "<< curr->name << endl;
}
else
{
if(curr == last && s>last->name)
{
last->next = new Node;
(last->next)->prev = last;
last = last->next;
last->next = NULL;
last->name = s;
// cout<<" Added "<< s <<" at the end "<< endl;
}
else
{
Node* temp = new Node;
temp->name = s;
temp->next = curr;
(curr->prev)->next = temp;
temp->prev = curr->prev;
curr->prev = temp;
// cout<<" Inserted "<< s <<" Before "<< curr->name<< endl;
}
}
}
}
ostream& operator<<(ostream& ostr, const Dllist& dl )
{
if(dl.empty()) ostr << " The list is empty. "<< endl;
else
{
Dllist::Node* curr;
for(curr = dl.head; curr != dl.last->next; curr=curr->next)
ostr << curr->name <<" ";
ostr << endl;
ostr << endl;
return ostr;
}
}
void Dllist::Remove(const string& s)
{
bool found = false;
if(empty())
{
cout<<" This is an empty list! "<< endl;
return;
}
else
{
Node* curr;
for(curr = head; curr != last->next; curr = curr->next)
{
if(curr->name == s)
{
found = true;
break;
}
}
if(found == false)
{
cout<<" The list does not contain specified Node"< return;
}
else
{
// Curr points to the node to be removed.
if (curr == head && found)
{
if(curr->next != NULL)
{
head = curr->next;
delete curr;
return;
}
else
{
delete curr;
head = NULL;
last = NULL;
return;
}
}
if (curr == last && found)
{
last = curr->prev;
delete curr;
return;
}
(curr->prev)->next = curr->next;
(curr->next)->prev = curr->prev;
delete curr;
}
}
}
int main()
{
Dllist d1;
int ch;
string temp;
while(1)
{
cout<< endl;
cout<<" Doubly Linked List Operations "<< endl;
cout<<" ------------------------------"<< endl;
cout<<" 1. Insertion "<< endl;
cout<<" 2. Deletion "<< endl;
cout<<" 3. Display "<< endl;
cout<<" 4. Exit "<< endl;
cout<<" Enter your choice : ";
cin>>ch;
switch(ch)
{
case 1: cout<<" Enter Name to be inserted : ";
cin>>temp;
d1.Insert(temp);
break;
case 2: cout<<" Enter Name to be deleted : ";
cin>>temp;
d1.Remove(temp);
break;
case 3: cout<<" The List contains : ";
cout<< d1;
break;
case 4: system("pause");
return 0;
break;
}
}
}
#include< iostream.h >
#include< conio.h >
#include< stdlib.h >
class list
{
struct node
{
int data;
node *link;
}*p;
public:
void inslast(int);
void insbeg(int);
void insnext(int,int);
void delelement(int);
void delbeg();
void dellast();
void disp();
int seek(int);
list(){p=NULL;}
~list();
};
void list::inslast(int x)
{
node *q,*t;
if(p==NULL)
{
p=new node;
p->data=x;
p->link=NULL;
}
else
{
q=p;
while(q->link!=NULL)
q=q->link;
t=new node;
t->data=x;
t->link=NULL;
q->link=t;
}
cout<<"Inserted successfully at the end..";
disp();
}
void list:: insbeg(int x)
{
node *q;
q=p;
p=new node;
p->data=x;
p->link=q;
cout<<"Inserted successfully at the begining..";
disp();
}
void list::delelement(int x)
{
node *q,*r;
q=p;
if(q->data==x)
{
p=q->link;
delete q;
return;
}
r=q;
while(q!=NULL)
{
if(q->data==x)
{
r->link=q->link;
delete q;
return;
}
r=q;
q=q->link;
}
cout<<"Element u entered "<< x <<" is not found..";
}
void list:: delbeg()
{
cout<<"The list before deletion:";
disp();
node *q;
q=p;
if(q==NULL)
{
cout<<"No data is present..";
return;
}
p=q->link;
delete q;
return;
}
void list:: dellast()
{
cout<<"The list before deletion:";
disp();
node *q,*t;
q=p;
if(q==NULL)
{
cout<<"There is no data in the list..";
return;
}
if(q->link==NULL)
{
p=q->link;
delete q;
return;
}
while(q->link->link!=NULL)
q=q->link;
q->link=NULL;
return;
}
list::~list()
{
node *q;
if(p==NULL) return;
while(p!=NULL)
{
q=p->link;
delete p;
p=q;
}
}
void list::disp()
{
node *q;
q=p;
if(q==NULL)
{
cout<<" No data is in the list..";
return;
}
cout<<"The items present in the list are :";
while(q!=NULL)
{
cout<<" "<< q->data;
q=q->link;
}
}
void list :: insnext(int value,int position)
{
node *temp,*temp1;
temp=p;
if(temp1==NULL)
{
temp1= new node;
temp1->data=value;
temp1->link=NULL;
p=temp1;
return;
}
for(int i=0;((i< position) && (temp->link!=NULL)) ;i++)
{
if(i==(position-1))
{
temp1= new node;
temp1->data= value;
temp1->link=temp->link;
temp->link=temp1;
}
temp=temp->link;
}
//cout<<"Inserted successfully at the position.."<< position;
disp();
}
int list::seek(int value)
{
node *temp;
temp=p;
int position=0;
while(temp!=NULL)
{
if(temp->data==value)
return position+1;
else
{
temp=temp->link;
position=position+1;
}
}
cout<<"Element "<< value <<" not found";
return 0;
}
void main()
{
list l;
int ch,v,p,ps;
do
{
clrscr();
cout<<"Operations on List..";
cout<<"
1.Insertion
2.Deletion
3.Display
4.Seek
5.Exit";
cout<<" Enter ur choice:";
cin>>ch;
switch(ch)
{
case 1:
cout<<"1.Insertion at begining
2.Insertion at the end";
cout<<"3.Insertion after the mentioned position";
cout<<"Enter ur choice:";
cin>>ps;
cout<<" Enter the value to insert:";
cin>>v;
switch(ps)
{
case 1:
l.insbeg(v);
break;
case 2:
l.inslast(v);
break;
case 3:
cout << "Enter the position to insert the value:";
cin>>p;
l.insnext(v,p);
break;
default:
cout<<"The choice is invalid";
return;
}
break;
case 2:
cout<<"1.Delete the first element
2.Delete the last element";
cout<<"3.Enter the element to delete from the list";
cout<<"Enter ur choice:";
cin>>ps;
switch(ps)
{
case 1:
l.delbeg();
cout<<"The list after deletion:";
l.disp();
break;
case 2:
l.dellast();
cout<<"The list after deletion:";
l.disp();
break;
case 3:
l.disp();
cout<<"Enter the element to delete : ";
cin>>v;
l.delelement(v);
cout<<"The list after deletion:";
l.disp();
break;
default:
cout<<"The option is invalid...";
break;
}
break;
case 3:
l.disp();
break;
case 4:
l.disp();
cout<<"Enter the element to search:";
cin>>v;
cout<<" The position of the element "<< v <<" is "<< l.seek(v);
getch();
break;
case 5:
exit(1);
default:
cout<<"The option is invalid...";
return;
}
getch();
}while(ch!=5);
getch();
return;
}
#include< iostream.h >
#include< constream.h >
void read(int a[10],int n)
{
cout << "reading\n";
for(int i=0;i < n;i++)
cin >> a[i];
}
void display(int a[10],int n)
{
for(int i=0;i < n;i++)
cout << a[i] <<"\t";
}
void shellsort(int a[10],int n)
{
int gap=n/2;
do
{
int swap;
do
{
swap=0;
for(int i=0;i < n-gap;i++)
if(a[i] > a[i+gap])
{
int t=a[i];
a[i]=a[i+gap];
a[i+gap]=t;
swap=1;
}
}
while(swap);
}
while(gap=gap/2);
}
void main()
{
int a[10];
int n;
clrscr();
cout<<"enter n\n";
cin>>n;
read(a,n);
cout<<"before sorting\n";
display(a,n);
shellsort(a,n);
cout<<"\nafter sorting\n";
display(a,n);
getch();
}
#include< iostream >
using namespace std;
int main()
{
int arr[10];
int no_of_elements, key;
bool found = false;
cout<<"Enter the number of element: ";
cin>>no_of_elements;
for(int i = 0; i < no_of_elements; i++)
{
cout<<"arr["<< i <<"]: ";
cin>>arr[i];
}
cout<<"Enter the value to search: ";
cin>>key;
for(int i=0;i< no_of_elements;i++)
{
if(key == arr[i])
{
found = true;
cout<<"The value is found at index arr["<< i <<"]";
}
}
if(!found)
{
cout<<"Key not found!";
}
return 0;
}
#include < iostream.h >
const int MAX = 10 ;
class array
{
private :
int arr[MAX] ;
int count ;
public :
array( ) ;
void add ( int item ) ;
void sort( ) ;
void display( ) ;
} ;
array :: array( )
{
count = 0 ;
for ( int i = 0 ; i < MAX ; i++ )
arr[i] = 0 ;
}
void array :: add ( int item )
{
if ( count < MAX )
{
arr[count] = item ;
count++ ;
}
else
cout << "\nArray is full" << endl ;
}
void array :: sort( )
{
int temp ;
for ( int i = 0 ; i <= count - 2 ; i++ )
{
for ( int j = i + 1 ; j <= count - 1 ; j++ )
{
if ( arr[i] > arr[j] )
{
temp = arr[i] ;
arr[i] = arr[j] ;
arr[j] = temp ;
}
}
}
}
void array :: display( )
{
for ( int i = 0 ; i < count ; i++ )
cout << arr[i] << " " ;
cout << endl ;
}
void main( )
{
array a ;
a.add ( 25 ) ;
a.add ( 17 ) ;
a.add ( 31 ) ;
a.add ( 13 ) ;
a.add ( 2 ) ;
cout << "\nSelection sort.\n" ;
cout << "\nArray before sorting:" << endl ;
a.display( ) ;
a.sort( ) ;
cout << "\nArray after selection sorting:" << endl ;
a.display( ) ;
}
#include#include #include #include int Partition(int low,int high,int arr[]); void Quick_sort(int low,int high,int arr[]); void main() { int *a,n,low,high,i; clrscr(); cout<<"Quick Sort Algorithm";<< endl cout<<"Enter number of elements:"; cin>>n; a=new int[n]; /* cout<<"enter the elements:"; for(i=0;i< n;i++) cin>>a;*/ for(i=0;i < n;i++) a[i]=rand()%100; clrscr(); cout<<"Initial Order of elements"; for(i=0;i< n;i++) cout<< a[i] <<" "; cout <<""; high=n-1; low=0; Quick_sort(low,high,a); cout <<"Final Array After Sorting:"; for(i=0;i < n;i++) cout << a[i] <<" "; getch(); } /*Function for partitioning the array*/ int Partition(int low,int high,int arr[]) { int i,high_vac,low_vac,pivot/*,itr*/; pivot=arr[low]; while(high>low) { high_vac=arr[high]; while(pivot< high_vac) { if(high < =low) break; high--; high_vac=arr[high]; } arr[low]=high_vac; low_vac=arr[low]; while(pivot > low_vac) { if(high < =low) break; low++; low_vac=arr[low]; } arr[high]=low_vac; } arr[low]=pivot; return low; } void Quick_sort(int low,int high,int arr[]) { int Piv_index,i; if(low < high) { Piv_index=Partition(low,high,arr); Quick_sort(low,Piv_index-1,arr); Quick_sort(Piv_index+1,high,arr); } }
#include < iostream.h >
#include < conio.h >
#include < stdlib.h >
struct node
{
char name[20];
int age;
float height;
node *nxt;
};
node *start_ptr=NULL;
int main()
{
void push ();
void pop();
char ch;
clrscr();
cout<<"Queue";
cout<<"-----";
do
{
cout<<"Select an operation";
cout<<"u->push";
cout<<"o->pop";
cout<<"e->exit";
cin>>ch;
switch(ch)
{
case 'u':
push();
break;
case 'o':
pop();
break;
case 'e':
exit(0);
}
}while(ch!='e');
return 0;
}
void pop()
{
node *temp1,*temp2;
if(start_ptr==NULL)
cout<<"The list is empty";
else
{
temp1=start_ptr;
temp2=temp1;
while(temp1->nxt!=NULL)
{
temp2=temp1;
temp1=temp1->nxt;
}
if(temp1==temp2)
{
cout<< temp1->name<<",";
cout<< temp1->age<<", ";
cout<< temp1->height;
start_ptr=NULL;
}
else
{
cout<< temp1->name<<", ";
cout<< temp1->age<<", ";
cout<< temp1->height;
temp2->nxt=NULL;
delete temp1;
}
}
}
void push ()
{
node *temp;
temp = new node;
cout << "Please enter the name of the person: ";
cin >> temp->name;
cout << "Please enter the age of the person: ";
cin >> temp->age;
cout << "Please enter the height of the person: ";
cin >> temp->height;
if (start_ptr == NULL)
{
temp->nxt=NULL;
start_ptr = temp;
}
else
{
temp->nxt=start_ptr;
start_ptr=temp;
}
}
#include< iostream.h >
#include< conio.h >
const int MAX=5;
class pqueue
{
int front,rear;
public:
struct data
{
int val,p,o;
}d[MAX];
pqueue()
{
front=rear=-1;
}
void insert(data d1);
data deletion();
void display();
};
void pqueue :: insert(data d1)
{
if(rear==MAX-1)
cout<<"Priority Queue is Full";
else
{
rear++;
d[rear]=d1;
if(front==-1)
front=0;
data temp;
for(int i=front;i<=rear;i++)
for(int j=i+1;j<=rear;j++)
{
if(d[i].p > d[j].p)
{
temp=d[i];
d[i]=d[j];
d[j]=temp;
}
else
{
if(d[i].p==d[j].p)
{
if(d[i].o > d[j].o)
{
temp=d[i];
d[i]=d[j];
d[j]=temp;
}
}
}
}
}
}
data pqueue :: deletion()
{
data d1;
if(front==-1)
cout<<"Priority Queue is Empty";
else
{
d1=d[front];
if(front==rear)
front=rear=-1;
else
front++;
}
return d1;
}
void pqueue :: display()
{
if(front==-1)
cout<<"Priority Queue is Empty";
else
{
for(int i=front;i<=rear;i++)
{
cout<<"Object :"<< i+1<< endl;
cout<<"Value ="<< d[i].val<< endl;
cout<<"Priority="<< d[i].p<< endl;
cout<<"Order = "<< d[i].o<< endl;
}
}
}
void main()
{
pqueue p1;
data d1;
char op;
do
{
int ch;
clrscr();
cout<<"----------Menu-------------";
cout<<" 1.Insertion
2.Deletion
3.Display
4.Exit";
cout<<"Enter your Choice<1..4> ?";
cin>>ch;
switch(ch)
{
case 1 : cout<<"Enter Value ?";
cin>>d1.val;
cout<<"Enter Priority?";
cin>>d1.p;
cout<<"Enter Order ?";
cin>>d1.o;
p1.insert(d1);
break;
case 2 : d1=p1.deletion();
cout<<"Value = "<< d1.val<< endl;
cout<<"Priority = "<< d1.p<< endl;
cout<<"Order ="<< d1.o<< endl;
break;
case 3 : p1.display();
break;
}
cout<<"Do You Want to Continue < Y/N > ?";
cin>>op;
}while(op=='Y' || op=='y');
getch();
}
#include< iostream.h >
#include< conio.h >
const int MAX = 5;
class cqueue
{
int a[MAX],front,rear;
public :
cqueue()
{
front=rear=-1;
}
void insert(int );
int deletion();
void display();
};
void cqueue :: insert(int val)
{
if((front==0 && rear==MAX-1) || (rear+1==front))
cout<<" Circular Queue is Full";
else
{
if(rear==MAX-1)
rear=0;
else
rear++;
a[rear]=val;
}
if(front==-1)
front=0;
}
int cqueue :: deletion()
{
int k;
if(front==-1)
cout<<"Circular Queue is Empty";
else
{
k=a[front];
if(front==rear)
front=rear=-1;
else
{
if(front==MAX-1)
front=0;
else
front++;
}
}
return k;
}
void cqueue :: display()
{
int i;
if(front==-1)
cout<<"Circular Queue is Empty";
else
{
if(rear < front)
{
for(i=front;i<=MAX-1;i++)
cout<< a[i] <<" ";
for(i=0;i<=rear;i++)
cout<< a[i] <<" ";
}
else
{
for(i=front;i<=rear;i++)
cout<< a[i]<<" ";
cout<< endl;
}
}
}
void main()
{
cqueue c1;
int ch,val;
char op;
do
{
clrscr();
cout<<"-----------Menu-------------";
cout<<"1.Insertion
2.Deletion
3.Display
4.Exit";
cout<<"Enter Your Choice <1..4> ?";
cin>>ch;
switch(ch)
{
case 1 : cout<<"Enter Element to Insert ?";
cin>>val;
c1.insert(val);
break;
case 2 : val=c1.deletion();
cout<<"Deleted Element :"<< val<< endl;
break;
case 3 : c1.display();
break;
}
cout<<"Do you want to continue < Y/N > ?";
cin>>op;
}while(op=='Y' || op=='y');
getch();
}
Merge Two Sorted Linked List To Form A Third Linked List
Posted by Naveen's Blogs
Tag :
Data Structures,
Linked list
#include< iostream.h >
#include< conio.h >
#include< process.h >
// Creating a NODE Structure
struct node
{
int data; // data
struct node *next; // link to next node and previous node
};
// Creating a class LIST
class list
{
struct node *start;
public:
void create(); // to create a list
void show(); // show
void merge(list,list); // Merge two list's
};
// Main function
int main()
{
clrscr();
list l1,l2,l3;
cout<<"Enter the First List in ascending order.";
l1.create(); // to create a first list
cout<<"Enter the Second List in ascending order.";
l2.create(); // to create a second list
cout<<"The first list is";
l1.show();
cout<<"The second list is";
l2.show();
l3.merge(l1,l2);
l3.show();
getch();
return (0);
}
// Functions
// Creating a new node
void list::create()
{
struct node *nxt_node,*pre_node;
int value,no,i;
start=nxt_node=pre_node=NULL;
cout<<"How many nodes : ";
cin>>no;
cout<<"Enter "<< no <<" Elements: ";
for(i=1;i<=no;i++)
{
cin>>value;
nxt_node=new node;
nxt_node->data=value;
nxt_node->next=NULL;
if(start==NULL)
start=nxt_node;
else
pre_node->next=nxt_node;
pre_node=nxt_node;
}
cout<<"The list is created!";
}
// Displaying LIST
void list::show()
{
struct node *ptr=start;
cout<<"The List is ";
while(ptr!=NULL)
{
cout<< ptr->data<<" -> ";
ptr=ptr->next;
}
cout<<" ";
}
void list::merge(list l1,list l2)
{
struct node *nxt_node,*pre_node,*pptr,*qptr;
int dat;
pptr=l1.start;
qptr=l2.start;
start=nxt_node=pre_node=NULL;
while(pptr!=NULL && qptr!=NULL)
{
if(pptr->data<=qptr->data)
{
dat=pptr->data;
pptr=pptr->next;
}
else
{
dat=qptr->data;
qptr=qptr->next;
}
nxt_node=new node;
nxt_node->data=dat;
nxt_node->next=NULL;
if(start==NULL)
start=nxt_node;
else
pre_node->next=nxt_node;
pre_node=nxt_node;
}
if(pptr==NULL)
{
while(qptr!=NULL)
{
nxt_node=new node;
nxt_node->data=qptr->data;
nxt_node->next=NULL;
if(start==NULL)
start=nxt_node;
else
pre_node->next=nxt_node;
pre_node=nxt_node;
qptr=qptr->next;
}
}
else if(qptr==NULL)
{
while(pptr!=NULL)
{
nxt_node=new node;
nxt_node->data=pptr->data;
nxt_node->next=NULL;
if(start==NULL)
start=nxt_node;
else
pre_node->next=nxt_node;
pre_node=nxt_node;
pptr=pptr->next;
}
}
cout<<"The lists are merged.";
return;
}
#include <iostream.h>
int a[50];
void merge(int,int,int);
void merge_sort(int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
merge_sort(low,mid);
merge_sort(mid+1,high);
merge(low,mid,high);
}
}
void merge(int low,int mid,int high)
{
int h,i,j,b[50],k;
h=low;
i=low;
j=mid+1;
while((h<=mid)&&(j<=high))
{
if(a[h]<=a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}
if(h>mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i++;
}
}
for(k=low;k<=high;k++)
a[k]=b[k];
}
void main()
{
int num,i;
cout<<"MERGE SORT PROGRAM"<<endl;
cout<<"Please Enter THE NUMBER OF ELEMENTS you want to sort [THEN
PRESS ENTER]:"<<endl;
cin>>num;
cout<<endl;
cout<<"Now, Please Enter the ( "<< num <<" ) numbers (ELEMENTS) [THEN
PRESS ENTER]:"<<endl;
for(i=1;i<=num;i++)
{
cin>>a[i] ;
}
merge_sort(1,num);
cout<<endl;
cout<<"So, the sorted list (using MERGE SORT) will be :"<<endl;
cout<<endl<<endl;
for(i=1;i<<=num;i++)
cout<<a[i]<<" ";
cout<<endl<<endl<<endl<<endl;
}
#include < iostream.h >
const int MAX = 10 ;
class array
{
private :
int arr[MAX] ;
int count ;
public :
array( ) ;
void add ( int item ) ;
void sort( ) ;
void display( ) ;
} ;
array :: array( )
{
count = 0 ;
for ( int i = 0 ; i < MAX ; i++ )
arr[i] = 0 ;
}
void array :: add ( int item )
{
if ( count < MAX )
{
arr[count] = item ;
count++ ;
}
else
cout << "\nArray is full" << endl ;
}
void array :: sort( )
{
int temp ;
for ( int i = 1 ; i <= count - 1 ; i++ )
{
for ( int j = 0 ; j < i ; j++ )
{
if ( arr[j] > arr[i] )
{
temp = arr[j] ;
arr[j] = arr[i] ;
for ( int k = i ; k > j ; k-- )
arr[k] = arr[k - 1] ;
arr[k + 1] = temp ;
}
}
}
}
void array :: display( )
{
for ( int i = 0 ; i < count ; i++ )
cout << arr[i] << "\t" ;
cout << endl ;
}
void main( )
{
array a ;
a.add ( 25 ) ;
a.add ( 17 ) ;
a.add ( 31 ) ;
a.add ( 13 ) ;
a.add ( 2 ) ;
cout << "\nInsertion sort.\n" ;
cout << "\nArray before sorting:" << endl ;
a.display( ) ;
a.sort( ) ;
cout << "\nArray after insertion sorting:" << endl ;
a.display( ) ;
}
Inserting, deleting and displaying elements in the Double Circular Linked List
Posted by Naveen's Blogs
Tag :
Data Structures,
Linked list
#include< iostream.h >
#include< conio.h >
class cirdlink
{
struct node
{
int data;
node *rnext;
node *lnext;
}*new1,*head,*tail,*ptr,*temp;
public:
cirdlink()
{
head=tail=NULL;
}
void creation();
void insertion();
void deletion();
void display();
};
void cirdlink :: creation()
{
if(head==NULL)
{
new1=new node[sizeof(node)];
new1->rnext=NULL;
new1->lnext=NULL;
cout<<"enter student number :";
cin>>new1->data;
head=new1;
tail=new1;
head->rnext=tail;
head->lnext=tail;
tail->rnext=head;
tail->lnext=head;
}
else
cout<<" creation done only once !";
}
void cirdlink :: insertion()
{
int i,pos;
new1=new node[sizeof(node)];
new1->rnext=NULL;
new1->lnext=NULL;
cout<<"enter student number :";
cin>>new1->data;
cout<<"enter position you want to insert :";
cin>>pos;
if(pos==1)
{
new1->rnext=head;
head=new1;
tail->lnext=head;
tail->rnext=head;
head->lnext=tail;
}
else
{
i=1;
temp=head;
while(i < pos-1 && temp->rnext!=tail)
{
i++;
temp=temp->rnext;
}
if(temp->rnext==tail)
{
new1->rnext=tail->rnext;
tail->rnext=new1;
new1->lnext=tail;
tail=new1;
head->lnext=tail;
}
else
{
new1->rnext=temp->rnext;
new1->lnext=temp;
temp->rnext=new1;
new1->rnext->lnext=new1;
}
}
}
void cirdlink :: deletion()
{
int pos,i;
cout<<"Enter Position you want to Delete ?";
cin>>pos;
if(pos==1 && head!=tail)
{
ptr=head;
head=head->rnext;
head->lnext=tail;
tail->rnext=head;
delete ptr;
}
else
{
i=1;
temp=head;
while(i < pos-1 && temp->rnext!=tail)
{
i++;
temp=temp->rnext;
}
if(temp->rnext!=tail)
{
ptr=temp->rnext;
temp->rnext=ptr->rnext;
ptr->rnext->lnext=ptr->lnext;
delete ptr;
}
else
{
if(temp->rnext==tail && head!=tail)
{
ptr=tail;
tail=temp;
tail->rnext=head;
head->lnext=tail;
delete ptr;
}
else
{
head=NULL;
tail=NULL;
delete head;
delete tail;
}
}
}
}
void cirdlink::display()
{
int ch;
cout<<"1.forward
2.backward:";
cout<<"Enter your choice<1/2>?";
cin>>ch;
switch(ch)
{
case 1: if(head!=NULL)
{
temp=head;
while(temp!=tail)
{
cout<< temp->data<<" ";
temp=temp->rnext;
}
if(temp==tail)
cout<< temp->data;
}
break;
case 2 : if(tail!=NULL)
{
temp=tail;
while(temp!=head)
{
cout<< temp->data<<" ";
temp=temp->lnext;
}
if(temp==head)
cout<< temp->data;
}
break;
}
}
void main()
{
cirdlink c1;
int ch;
char op;
do
{
clrscr();
cout<<"----------Menu------------";
cout<<" 1.Creation
2.Insertion
3.Deletion
4.Display ";
cout<<"Enter Your choice <1..4> ?";
cin>>ch;
switch(ch)
{
case 1 : c1.creation();
break;
case 2 : c1.insertion();
break;
case 3 : c1.deletion();
break;
case 4 : c1.display();
break;
}
cout<<"Do you want to continue < Y/N > ?";
cin>>op;
}while(op=='y' || op=='Y');
getch();
}
#include< iostream.h>
#include< conio.h>
#define SIZE 20
class stack
{
int a[SIZE];
int tos; // Top of Stack
public:
stack();
void push(int);
int pop();
int isempty();
int isfull();
};
stack::stack()
{
tos=0; //Initialize Top of Stack
}
int stack::isempty()
{
return (tos==0?1:0);
}
int stack::isfull()
{
return (tos==SIZE?1:0);
}
void stack::push(int i)
{
if(!isfull())
{
cout<<"Pushing "<< i<< endl;
a[tos]=i;
tos++;
}
else
{
cerr<<"Stack overflow error !
Possible Data Loss !";
}
}
int stack::pop()
{
if(!isempty())
{
cout<<"Popping "<< a[tos-1]<< endl;
return(a[--tos]);
}
else
{
cerr<<"Stack is empty! What to pop...!";
}
return 0;
}
void reverse(stack s)
{
stack s2;
while(!s.isempty())
{
s2.push(s.pop());
}
cout<<"Reversed contents of the stack..."<< endl;
while(!s2.isempty())
{
cout<< s2.pop()<< endl;
}
}//end of fn.
void main()
{
clrscr();
stack s;
s.push(1);
s.push(2);
s.push(3);
reverse(s);
getch();
}
# include < iostream.h >
# include < conio.h >
# define SIZE 20
class queue
{
int a[SIZE];
int front;
int rear;
public:
queue();
~queue();
void insert(int i);
int remove();
int isempty();
int isfull();
};
queue::queue()
{
front=0;
rear=0;
}
queue::~queue()
{
delete []a;
}
void queue::insert(int i)
{
if(isfull())
{
cout<<"*Queue is FULL !!!No insertion allowed further.*";
return;
}
a[rear] = i;
rear++;
}
int queue::remove()
{
if(isempty())
{
cout<<"*Queue Empty !!!Value returned will be garbage.*";
return (-9999);
}
return(a[front++]);
}
int queue::isempty()
{
if(front == rear)
return 1;
else
return 0;
}
int queue::isfull()
{
if(rear == SIZE)
return 1;
else
return 0;
}
void main()
{
clrscr();
queue q;
q.insert(1);
q.insert(2);
cout<<""<< q.remove();
cout<<""<< q.remove();
cout<<"" << q.remove();
getch();
}
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
class path
{
int n;
int p[10][10];
int a[10][10];
int c[10][10];
public:
void get();
void pm();
void ap();
void disp();
};
void path::get()
{
int i,j,k;
clrscr();
cout<<"Enter the no. of nodes in the graph :";
cin>>n;
cout<<"Enter the adjacency matrix :";
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cin>>a[i][j];
p[i][j]=0;
}
}
cout<<"Enter The cost matrix is :";
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cin>>c[i][j];
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
p[i][j]=a[i][j];
}
}
}
void path::disp()
{
// cout<<"The output matrix for the given graph is :";
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<p[i][j]<< " ";
}
cout<<endl;
}
}
void path::pm()
{
int i,j,k;
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
p[i][j]=p[i][j] || p[i][k] && p[k][j];
}
}
}
}
void path::ap()
{
int i,j,k;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
p[i][j]=c[i][j];
}
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(p[i][j]<p[i][k]+p[k][j])
{
p[i][j]=p[i][j];
}
else
{
p[i][j]=p[i][k]+p[k][j];
}
}
}
}
}
void main()
{
path p;
p.get();
p.pm();
cout<<"path matrix is :";
p.disp();
getch();
p.ap();
cout<<"all pair shortest path matrix is :";
p.disp();
getch();
}
#include < iostream >
#include < cstdlib >
#include < string >
using namespace std;
class Dllist
{
private:
typedef struct Node
{
string name;
Node* next;
Node* prev;
};
Node* head;
Node* last;
public:
Dllist()
{
head = NULL;
last = NULL;
}
bool empty() const { return head==NULL; }
friend ostream& operator<<(ostream& ,const Dllist& );
void Insert(const string& );
void Remove(const string& );
};
void Dllist::Insert(const string& s)
{
// Insertion into an Empty List.
if(empty())
{
Node* temp = new Node;
head = temp;
last = temp;
temp->prev = NULL;
temp->next = NULL;
temp->name = s;
}
else
{
Node* curr;
curr = head;
while( s>curr->name && curr->next != last->next)
curr = curr->next;
if(curr == head)
{
Node* temp = new Node;
temp->name = s;
temp->prev = curr;
temp->next = NULL;
head->next = temp;
last = temp;
// cout<<" Inserted "<< s <<" After " << curr->name << endl;
}
else
{
if(curr == last && s>last->name)
{
last->next = new Node;
(last->next)->prev = last;
last = last->next;
last->next = NULL;
last->name = s;
// cout<<" Added "<< s <<" at the end "<< endl;
}
else
{
Node* temp = new Node;
temp->name = s;
temp->next = curr;
(curr->prev)->next = temp;
temp->prev = curr->prev;
curr->prev = temp;
// cout<<" Inserted "<< s <<" Before "<< curr->name << endl;
}
}
}
}
ostream& operator<<(ostream& ostr, const Dllist& dl )
{
if(dl.empty()) ostr<<" The list is empty. "<< endl;
else
{
Dllist::Node* curr;
for(curr = dl.head; curr != dl.last->next; curr=curr->next)
ostr<< curr->name<<" ";
ostr<< endl;
ostr<< endl;
return ostr;
}
}
void Dllist::Remove(const string& s)
{
bool found = false;
if(empty())
{
cout<<" This is an empty list! "<< endl;
return;
}
else
{
Node* curr;
for(curr = head; curr != last->next; curr = curr->next)
{
if(curr->name == s)
{
found = true;
break;
}
}
if(found == false)
{
cout<<" The list does not contain specified Node"<< endl;
return;
}
else
{
// Curr points to the node to be removed.
if (curr == head && found)
{
if(curr->next != NULL)
{
head = curr->next;
delete curr;
return;
}
else
{
delete curr;
head = NULL;
last = NULL;
return;
}
}
if (curr == last && found)
{
last = curr->prev;
delete curr;
return;
}
(curr->prev)->next = curr->next;
(curr->next)->prev = curr->prev;
delete curr;
}
}
}
int main()
{
Dllist d1;
int ch;
string temp;
while(1)
{
cout<< endl;
cout<<" Doubly Linked List Operations "<< endl;
cout<<" ------------------------------"<< endl;
cout<<" 1. Insertion "<< endl;
cout<<" 2. Deletion "<< endl;
cout<<" 3. Display "<< endl;
cout<<" 4. Exit "<< endl;
cout<<" Enter your choice : ";
cin>>ch;
switch(ch)
{
case 1: cout<<" Enter Name to be inserted : ";
cin>>temp;
d1.Insert(temp);
break;
case 2: cout<<" Enter Name to be deleted : ";
cin>>temp;
d1.Remove(temp);
break;
case 3: cout<<" The List contains : ";
cout<< d1;
break;
case 4: system("pause");
return 0;
break;
}
}
}
#include< iostream >
#define INFINITY 999
using namespace std;
class Dijkstra
{
private:
int adjMatrix[15][15];
int predecessor[15],distance[15];
bool mark[15]; //keep track of visited node
int source;
int numOfVertices;
public:
/*
* Function read() reads No of vertices, Adjacency Matrix and source
* Matrix from the user. The number of vertices must be greather than
* zero, all members of Adjacency Matrix must be postive as distances
* are always positive. The source vertex must also be positive from 0
* to noOfVertices - 1
*/
void read();
/*
* Function initialize initializes all the data members at the begining of
* the execution. The distance between source to source is zero and all other
* distances between source and vertices are infinity. The mark is initialized
* to false and predecessor is initialized to -1
*/
void initialize();
/*
* Function getClosestUnmarkedNode returns the node which is nearest from the
* Predecessor marked node. If the node is already marked as visited, then it search
* for another node.
*/
int getClosestUnmarkedNode();
/*
* Function calculateDistance calculates the minimum distances from the source node to
* Other node.
*/
void calculateDistance();
/*
* Function output prints the results
*/
void output();
void printPath(int);
};
void Dijkstra::read()
{
cout<<"Enter the number of vertices of the graph(should be > 0)\n";
cin>>numOfVertices;
while(numOfVertices <= 0)
{
cout<<"Enter the number of vertices of the graph(should be > 0)\n";
cin>>numOfVertices;
}
cout<<"Enter the adjacency matrix for the graph\n";
cout<<"To enter infinity enter "<< INFINITY<< endl;
for(int i=0;i< numOfVertices;i++)
{
cout<<"Enter the (+ve)weights for the row "<< i << endl;
for(int j=0;j< numOfVertices;j++)
{
cin>>adjMatrix[i][j];
while(adjMatrix[i][j]<0)
{
cout<<"Weights should be +ve. Enter the weight again\n";
cin>>adjMatrix[i][j];
}
}
}
cout<<"Enter the source vertex\n";
cin>>source;
while((source<0) && (source>numOfVertices-1))
{
cout<<"Source vertex should be between 0 and"<< numOfVertices-1<< endl;
cout<<"Enter the source vertex again\n";
cin>>source;
}
}
voidpre Dijkstra::initialize()
{
for(int i=0;i< numOfVertices;i++)
{
mark[i] = false;
predecessor[i] = -1;
distance[i] = INFINITY;
}
distance[source]= 0;
}
int Dijkstra::getClosestUnmarkedNode()
{
int minDistance = INFINITY;
int closestUnmarkedNode;
for(int i=0;i< numOfVertices;i++)
{
if((!mark[i]) && ( minDistance >= distance[i]))
{
minDistance = distance[i];
closestUnmarkedNode = i;
}
}
return closestUnmarkedNode;
}
void Dijkstra::calculateDistance()
{
initialize();
int minDistance = INFINITY;
int closestUnmarkedNode;
int count = 0;
while(count < numOfVertices)
{
closestUnmarkedNode = getClosestUnmarkedNode();
mark[closestUnmarkedNode] = true;
for(int i=0;i< numOfVertices;i++)
{
if((!mark[i]) && (adjMatrix[closestUnmarkedNode][i]>0) )
{
if(distance[i] > distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i])
{
distance[i] = distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i];
predecessor[i] = closestUnmarkedNode;
}
}
}
count++;
}
}
void Dijkstra::printPath(int node)
{
if(node == source)
cout<<(char)(node + 97)<<"..";
else if(predecessor[node] == -1)
cout<<"No path from “<< source<<”to "<<(char)(node + 97)<< endl;
else
{
printPath(predecessor[node]);
cout<<(char) (node + 97)<<"..";
}
}
void Dijkstra::output()
{
for(int i=0;i< numOfVertices;i++)
{
if(i == source)
cout<<(char)(source + 97)<<".."<< source;
else
printPath(i);
cout<<"->"<< distance[i]<< endl;
}
}
int main()
{
Dijkstra G;
G.read();
G.calculateDistance();
G.output();
return 0;
}
#include<iostream>
#include<stdlib.h>
using namespace std;
void create(); // For creating a graph
void dfs(); // For Deapth First Search(DFS) Traversal.
void bfs(); // For Breadth First Search(BFS) Traversal.
struct node // Structure for elements in the graph
{
int data,status;
struct node *next;
struct link *adj;
};
struct link // Structure for adjacency list
{
struct node *next;
struct link *adj;
};
struct node *start,*p,*q;
struct link *l,*k;
int main()
{
int choice;
clrscr();
create();
while(1)
{
cout<<"
1: DFS
2: BSF
3: Exit
Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
dfs();
break;
case 2:
bfs();
break;
case 3:
exit(0);
break;
default:
cout<<"
Incorrect choice!
Re-enter your choice.";
getch();
}
}
return 0;
}
void create() // Creating a graph
{
int dat,flag=0;
start=NULL;
cout<<"
Enter the nodes in the graph(0 to end): ";
while(1)
{
cin>>dat;
if(dat==0)
break;
p=new node;
p->data=dat;
p->status=0;
p->next=NULL;
p->adj=NULL;
if(flag==0)
{
start=p;
q=p;
flag++;
}
else
{
q->next=p;
q=p;
}
}
p=start;
while(p!=NULL)
{
cout<<"Enter the links to "<< p->data<<" (0 to end) : ";
flag=0;
while(1)
{
cin>>dat;
if(dat==0)
break;
k=new link;
k->adj=NULL;
if(flag==0)
{
p->adj=k;
l=k;
flag++;
}
else
{
l->adj=k;
l=k;
}
q=start;
while(q!=NULL)
{
if(q->data==dat)
k->next=q;
q=q->next;
}
}
p=p->next;
}
cout<<"-------------------------";
return;
}
// Deapth First Search(DFS) Traversal.
void bfs()
{
int qu[20],i=1,j=0;
p=start;
while(p!=NULL)
{
p->status=0;
p=p->next;
}
p=start;
qu[0]=p->data;
p->status=1;
while(1)
{
if(qu[j]==0)
break;
p=start;
while(p!=NULL)
{
if(p->data==qu[j])
break;
p=p->next;
}
k=p->adj;
while(k!=NULL)
{
q=k->next;
if(q->status==0)
{
qu[i]=q->data;
q->status=1;
qu[i+1]=0;
i++;
}
k=k->adj;
}
j++;
}
j=0;
cout<<"Breadth First Search Results";
cout<<"---------------------------";
while(qu[j]!=0)
{
cout<< qu[j] << " ";
j++;
}
getch();
return;
}
// Breadth First Search(BFS) Traversal.
void dfs()
{
int stack[25],top=1;
cout<<"Deapth First Search Results";
cout<<"---------------------------";
p=start;
while(p!=NULL)
{
p->status=0;
p=p->next;
}
p=start;
stack[0]=0;
stack[top]=p->data;
p->status=1;
while(1)
{
if(stack[top]==0)
break;
p=start;
while(p!=NULL)
{
if(p->data==stack[top])
break;
p=p->next;
}
cout<< stack[top]<<" ";
top--;
k=p->adj;
while(k!=NULL)
{
q=k->next;
if(q->status==0)
{
top++;
stack[top]=q->data;
q->status=1;
}
k=k->adj;
}
}
getch();
return;
}
Program Limitations
* This program Only process single digit operations
* Can't handle unary operation
* Only process left to right associativity
#include< iostream >
#include< cmath >
#include< cstdlib >
#include< string >
#define MAX_SIZE 20
using namespace std;
template< class T >
class Stack
{
private:
T item[MAX_SIZE];
int top;
public:
Stack()
{
top = -1;
}
void push(T data)
{
if(!this->is_full())
item[++top] = data;
else
{
cout<<"Stack Error"<< endl;
exit(10);
}
}
T pop()
{
if(!this->is_empty())
return item[top--];
else
{
cout<<"Stack is Empty"<< endl;
exit(11);
}
}
int size()
{
return top+1;
}
bool is_empty()
{
if(top==-1)
return true;
else
return false;
}
bool is_full()
{
if(top==MAX_SIZE-1)
return true;
else
return false;
}
void display()
{
for(int i=0; i< this->size(); i++)
{
cout<< item[i]<<" ";
}
cout<< endl;
}
T return_top()
{
return item[top];
}
};
class Convert
{
private:
bool num_flag;
bool two_digit_flag;
public:
Convert();
string return_with_bracket(string infix);
void to_Postfix(string infix,char postfix[]);
bool prcd(char op1, char op2);
int isOperand(char op);
int isOperator(char op);
bool return_flag()
{
return num_flag;
}
};
Convert::Convert()
{
this->num_flag = false;
this->two_digit_flag = false;
}
string Convert::return_with_bracket(string infix)
{
return("(" + infix + ")");
}
bool Convert::prcd(char op1, char op2)
{
if((op1=='+' || op1=='-' || op1=='*' || op1=='/') && op2=='(' )
return true;
if(op1=='+' && op2=='+')
return true;
if(op1=='-' && op2=='-')
return false;
if(op1=='-' && op2=='+')
return false;
if(op1=='+' && op2=='-')
return false;
if(op1=='/' && op2=='/')
return false;
if(op1=='/' && (op2=='-' || op2=='+'))
return true;
if(op1=='*' && (op2=='+' || op2=='-'))
return true;
if((op1 == '-' || op1 == '+') && (op2 =='*' || op2 == '/'))
return false;
if((op1 == '$' || op1 == '+') && (op2 =='*' || op2 == '/' || op2=='-'))
return true;
if((op1 == '-' || op1 == '+' || op1 =='*' || op1 == '/')&& op2=='^')
return false;
if(op1 == '^' && ( op2 == '+' || op2 =='*' || op2 == '/' || op2=='-'))
return false;
}
int Convert::isOperand(char op)
{
return(op>= '0' && op <= '9');
}
int Convert::isOperator(char op)
{
return(op=='+' || op=='-' || op == '/' || op=='*' || op=='^');
}
void Convert::to_Postfix(string infix, char postfix[])
{
int position, outpos=0;
char c;
int count = 0;
char temp;
char stacktop ;
Stack < char > stack;
for(position = 0; (c = infix[position])!='\0'; position++)
{
if(this->isOperand(c))
{
postfix[outpos++] = c;
this->num_flag = true;
count++;
if(count>=2)
{
this->two_digit_flag = true;
}
}
else if(this->isOperator(c))
{
count = 0;
if(isOperator(infix[position]) && isOperator(infix[position+1]))
{
cout<<"\aMissing argument in between "<< infix[position]<<" and "<< infix[position+1]
<<" in column "<< position+1<< endl;
exit(9);
}
if(this->prcd(c, stacktop))
{
stacktop=stack.return_top();
stack.push(c);
stacktop = c;
}
else
{
while(true)
{
temp = stack.pop();
postfix[outpos++] =temp;
stacktop = stack.return_top();
if(prcd(c, stacktop) || stacktop=='(')
break;
}
stack.push(c);
stacktop = stack.return_top();
}
}
else if(c=='(')
{
count = 0;
stack.push(c);
stacktop = stack.return_top();
}
else if(c==')')
{
count = 0;
while(1)
{
if(stack.size()==0)
{
cout<<"Warning!! Number of ')' is greater than '('" << endl;
exit(2);
}
temp = stack.pop();
if(temp!='(')
{
postfix[outpos++] = temp;
}
else
{
break;
}
}
stacktop =stack.return_top();
}
else
{
cout<<"Invalid input";
exit(3);
}
if(infix[position]==')' && infix[position+1]=='(')
{
stack.push('*');
stacktop = stack.return_top();
}
}
if(stack.size()!=0)
{
cout<<"Warning!!Number of '(' is greater than ')'"<< endl;
// exit(6);
}
if(!this->return_flag())
{
cout<<"You must Enter Numeric value for calculation"<< endl;
cout<<"This program cannot perform operations on variables";
exit(5);
}
if(this->two_digit_flag)
{
cout<<"Sory! Althoug u may have entered right string"<< endl;
cout<<"this program is only for single digit operation"<< endl;
exit(8);
}
postfix[outpos] = '\0';
}
class Evaluate
{
public:
double eval(char expr[], Convert &);
double oper(int symb, double op1, double op2);
};
double Evaluate::oper(int symb, double op1, double op2)
{
switch(symb)
{
case '+': return (op1 + op2);
case '-': return (op1 - op2);
case '*': return (op1 * op2);
case '/': return (op1 / op2);
case '^': return (pow(op1, op2));
}
}
double Evaluate::eval(char expr[],Convert &convert)
{
int c, position;
char temp1;
int count = 0;
double opnd1, opnd2, value;
Stack< double > stack;
for(position = 0; (c = expr[position])!='\0'; position++)
{
if(convert.isOperand(c))
{
temp1 = double(c-'0');
stack.push(temp1);
}
else
{
opnd2 = stack.pop();
if(stack.size()==0)
{
cout<<"This program cannot process unary operation";
exit(1);
}
opnd1 = stack.pop();
value = oper(c, opnd1, opnd2);
stack.push(value);
}
}
if(stack.size()>=2)
{
cout<<"Sory! this program cannot calculate this"<< endl;
cout<<"Enter +, *, /, - or ^ between bracket"<< endl;
exit(4);
}
return (stack.pop());
}
int main()
{
Convert convert;
Evaluate evaluate;
string bracketted_infix;
char infix[50], postfix[50];
char choice;
while(1)
{
cout<<"Enter string: ";
cin>>infix;
cout<< endl;
cout<<"Entered String: "<< infix<< endl;
bracketted_infix = convert.return_with_bracket(infix);
convert.to_Postfix(bracketted_infix, postfix);
cout<<"Equivalent Postfix string: "<< postfix<< endl;
cout<<"RESULT: ";
cout<< evaluate.eval(postfix, convert);
cout<<"\nCalculate another string?(y/n) ";
cin>>choice;
cout<< endl;
if(choice=='n')
break;
}
return 0;
}
#include<iostream>
#include<stdlib.h>
using namespace std;
struct node
{
node *left;
int value;
node *right;
};
node *curr=NULL;
int addnode(node *, node *);
int inorder(node *);
int preorder(node *);
int postorder(node *);
void main()
{
char c;
int v;
clrscr();
do
{
cout<<"Select any one";
cout<<"0 ->Exit";
cout<<"1 ->Add node";
cout<<"2 ->Inorder traversal";
cout<<"3 ->Preorder traversal";
cout<<"4 ->Postorder trversal :";
cin>>c;
switch(c)
{
case '0':
exit(1);
case '1':
node *temp;
temp = new node;
cout<<" Enter the value of the node : ";
cin>>temp->value;
if(curr==NULL)
{
curr=new node;
curr->value=temp->value;
curr->left=NULL;
curr->right=NULL;
cout<<" The root node is added";
}
else
v=addnode(curr,temp);
if(v==1)
cout<<" The node is added to the left";
else if(v==2)
cout<<" The node is added to the right";
else if(v==3)
cout<<" The same value exists";
break;
case '2':
v=inorder(curr);
if(v==0)
cout<<"The tree is empty";
break;
case '3':
v=preorder(curr);
if(v==0)
cout<<"The tree is empty";
break;
case '4':
v=postorder(curr);
if(v==0)
cout<<"The tree is empty";
break;
default:
cout<<"Invalid entry";
break;
}
}while(c!='0');
getch();
}
int addnode(node *fcurr, node *fnew )
{
if(fcurr->value==fnew->value)
{
return 3;
}
else
{
if(fcurr->value > fnew->value)
{
if(fcurr->left != NULL)
addnode(fcurr->left, fnew);
else
{
fcurr->left = fnew;
(fcurr->left)->left=NULL;
(fcurr->left)->right=NULL;
return 1;
}
}
else
{
if(fcurr->right != NULL)
addnode(fcurr->right, fnew);
else
{
fcurr->right = fnew;
(fcurr->right)->left=NULL;
(fcurr->right)->right=NULL;
return 2;
}
}
}
}
int inorder(node *fincurr)
{
if(fincurr == NULL)
return 0;
else
{
if(fincurr->left != NULL)
inorder(fincurr->left);
cout << fincurr->value<<" ";
if(fincurr->right != NULL)
inorder(fincurr->right);
}
}
int preorder(node *fprcurr)
{
if(fprcurr == NULL)
return 0;
else
{
cout << fprcurr->value<<" ";
if(fprcurr->left != NULL)
preorder(fprcurr->left);
if(fprcurr->right != NULL)
preorder(fprcurr->right);
}
}
int postorder(node *fpocurr)
{
if(fpocurr == NULL)
return 0;
else
{
if(fpocurr->left != NULL)
postorder(fpocurr->left);
if(fpocurr->right != NULL)
postorder(fpocurr->right);
cout << fpocurr->value<<" ";
}
}
AVL Tree with Insertion,Deletion and balancing Height
Posted by Naveen's Blogs
Tag :
Data Structures,
trees
#include<iostream>
#include<stdlib>
#include<conio>
using namespace std;
struct node
{
int element;
node *left;
node *right;
int height;
};
typedef struct node *nodeptr;
class bstree
{
public:
void insert(int,nodeptr &);
void del(int, nodeptr &);
int deletemin(nodeptr &);
void find(int,nodeptr &);
nodeptr findmin(nodeptr);
nodeptr findmax(nodeptr);
void copy(nodeptr &,nodeptr &);
void makeempty(nodeptr &);
nodeptr nodecopy(nodeptr &);
void preorder(nodeptr);
void inorder(nodeptr);
void postorder(nodeptr);
; int bsheight(nodeptr);
nodeptr srl(nodeptr &);
nodeptr drl(nodeptr &);
nodeptr srr(nodeptr &);
nodeptr drr(nodeptr &);
int max(int,int);
int nonodes(nodeptr);
};
// Inserting a node
void bstree::insert(int x,nodeptr &p)
{
if (p == NULL)
{
p = new node;
p->element = x;
p->left=NULL;
p->right = NULL;
p->height=0;
if (p==NULL)
cout<<"Out of Space";
}
else
{
if (x< p-> element)
{
insert(x,p->left);
if ((bsheight(p->left) - bsheight(p->right))==2)
{
if (x < p->left->element)
p=srl(p);
else
p = drl(p);
}
}
else if (x>p->element)
{
insert(x,p->right);
if ((bsheight(p->right) - bsheight(p->left))==2)
{
if (x > p->right->element)
p=srr(p);
else
p = drr(p);
}
}
else
cout<<"Element Exists";
}
int m,n,d;
m=bsheight(p->left);
n=bsheight(p->right);
d=max(m,n);
p->height = d + 1;
}
// Finding the Smallest
nodeptr bstree::findmin(nodeptr p)
{
if (p==NULL)
{
cout<<"Empty Tree";
return p;
}
else
{
while(p->left !=NULL)
p=p->left;
return p;
}
}
// Finding the Largest
nodeptr bstree::findmax(nodeptr p)
{
if (p==NULL)
{
cout<<"Empty Tree";
return p;
}
else
{
while(p->right !=NULL)
p=p->right;
return p;
}
}
// Finding an element
void bstree::find(int x,nodeptr &p)
{
if (p==NULL)
cout<<"Element not found";
else
if (x < p->element)
find(x,p->left);
else
if (x>p->element)
find(x,p->right);
else
cout<<"Element found !";
}
// Copy a tree
void bstree::copy(nodeptr &p,nodeptr &p1)
{
makeempty(p1);
p1 = nodecopy(p);
}
// Make a tree empty
void bstree::makeempty(nodeptr &p)
{
nodeptr d;
if (p != NULL)
{
makeempty(p->left);
makeempty(p->right);
d=p;
free(d);
p=NULL;
}
}
// Copy the nodes
nodeptr bstree::nodecopy(nodeptr &p)
{
nodeptr temp;
if (p==NULL)
return p;
else
{
temp = new node;
temp->element = p->element;
temp->left = nodecopy(p->left);
temp->right = nodecopy(p->right);
return temp;
}
}
// Deleting a node
void bstree::del(int x,nodeptr &p)
{
nodeptr d;
if (p==NULL)
cout<<"Element not found ";
else if ( x < p->element)
del(x,p->left);
else if (x > p->element)
del(x,p->right);
else if ((p->left == NULL) && (p->right == NULL))
{
d=p;
free(d);
p=NULL;
cout<<"Element deleted !";
}
else if (p->left == NULL)
{
d=p;
free(d);
p=p->right;
cout<<"Element deleted !";
}
else if (p->right == NULL)
{
d=p;
p=p->left;
free(d);
cout<<"Element deleted !";
}
else
p->element = deletemin(p->right);
}
int bstree::deletemin(nodeptr &p)
{
int c;
cout<<"inside deltemin ";
if (p->left == NULL)
{
c=p->element;
p=p->right;
return c;
}
else
{
c=deletemin(p->left);
return c;
}
}
void bstree::preorder(nodeptr p)
{
if (p!=NULL)
{
cout<< p-> element <<"-->";
preorder(p->left);
preorder(p->right);
}
}
// Inorder Printing
void bstree::inorder(nodeptr p)
{
if (p!=NULL)
{
inorder(p->left);
cout<< p->element <<"-->";
inorder(p->right);
}
}
// PostOrder Printing
void bstree::postorder(nodeptr p)
{
if (p!=NULL)
{
postorder(p->left);
postorder(p->right);
cout<< p->element<<"-->";
}
}
int bstree::max(int value1, int value2)
{
return ((value1 > value2) ? value1 : value2);
}
int bstree::bsheight(nodeptr p)
{
int t;
if (p == NULL)
return -1;
else
{
t = p->height;
return t;
}
}
nodeptr bstree:: srl(nodeptr &p1)
{
nodeptr p2;
p2 = p1->left;
p1->left = p2->right;
p2->right = p1;
p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
p2->height = max(bsheight(p2->left),p1->height) + 1;
return p2;
}
nodeptr bstree:: srr(nodeptr &p1)
{
nodeptr p2;
p2 = p1->right;
p1->right = p2->left;
p2->left = p1;
p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
p2->height = max(p1->height,bsheight(p2->right)) + 1;
return p2;
}
nodeptr bstree:: drl(nodeptr &p1)
{
p1->left=srr(p1->left);
return srl(p1);
}
nodeptr bstree::drr(nodeptr &p1)
{
p1->right = srl(p1->right);
return srr(p1);
}
int bstree::nonodes(nodeptr p)
{
int count=0;
if (p!=NULL)
{
nonodes(p->left);
nonodes(p->right);
count++;
}
return count;
}
int main()
{
clrscr();
nodeptr root,root1,min,max;//,flag;
int a,choice,findele,delele,leftele,rightele,flag;
char ch='y';
bstree bst;
//system("clear");
root = NULL;
root1=NULL;
cout<<"AVL Tree";
cout<<"========";
do
{
cout<<"
1.Insertion
2.FindMin
";
cout<<"3.FindMax
4.Find
5.Copy
";
cout<<"6.Delete
7.Preorder
8.Inorder
";
cout<<"9.Postorder
10.height
";
cout<<"Enter the choice:";
cin>>choice;
switch(choice)
{
case 1:
cout<<"New node's value ?";
cin>>a;
bst.insert(a,root);
break;
case 2:
if (root !=NULL)
{
min=bst.findmin(root);
cout<<"Min element : "<< min->element;
}
break;
case 3:
if (root !=NULL)
{
max=bst.findmax(root);
cout<<"Max element : "<< max->element;
}
break;
case 4:
cout<<"Search node : ";
cin>>findele;
if (root != NULL)
bst.find(findele,root);
break;
case 5:
bst.copy(root,root1);
bst.inorder(root1);
break;
case 6:
cout<<"Delete Node ?";
cin>>delele;
bst.del(delele,root);
bst.inorder(root);
break;
case 7:
cout<<"Preorder Printing... :";
bst.preorder(root);
break;
case 8:
cout<<"Inorder Printing.... :";
bst.inorder(root);
break;
case 9:
cout<<"Postorder Printing... :";
bst.postorder(root);
break;
case 10:
cout<<"Height and Depth is ";
cout<< bst.bsheight(root);
cout<<"No. of nodes:- "<< bst.nonodes(root);
break;
}
cout<<"Do u want to continue (y/n) ?";
cin>>ch;
}while(ch=='y');
return 0;
}
Appending Two Linked List based upon two data members
Posted by Naveen's Blogs
Tag :
Data Structures,
Linked list
#include<iostream>
using namespace std;
class CClass1
{
public:
char mStringData[10];;
long int mDataMember1;
long int mDataMember2;
CClass1 *structpNextValue;
void SetValue(CString string, long int a, long int b)
{
strcpy(mStringData, string);
mDataMember1 = a;
mDataMember2 = b;
}
CClass1(void);
~CClass1(void);
};
class CClass2
{
public:
char mStringData[10];
long int mDataMember1;
long int mDataMember2;
CClass2 *structpNextValue;
void SetValue(CString string, long int a, long int b)
{
strcpy(mStringData, string);
mDataMember1 = a;
mDataMember2 = b;
}
CClass2(void);
~CClass2(void);
};
CClass1 *pstrTemp;
lTemp = lNumOrphanRecord;
pstrTemp = (CClass1*)malloc(sizeof(CClass1));
pstrTemp->structpNextValue = NULL;
CClass2 *pstrExcTemp = &mObject2[0];
while(lTemp > 0)
{
pstrTemp->mDataMember1 = pstrExcTemp->mDataMember1;
strcpy(pstrTemp->mStringData, pstrExcTemp->mStringData);
pstrTemp->mDataMember2 = pstrExcTemp->mDataMember2;
pstrExcTemp = pstrExcTemp->structpNextValue;
if (mObject1->mDataMember1 == 0)
{
mObject1 = pstrTemp;
}
else
{
CClass1 *pstrPrev = NULL;
CClass1 *pstrCurr = mObject1;
long int tempSeqNum = mObject1->mDataMember1;
int Icount=0;
while ( (pstrCurr) &&(pstrCurr->mDataMember1 !=0) &&
(pstrCurr->mDataMember1 < pstrTemp->mDataMember1) )
{
pstrPrev = pstrCurr;
pstrCurr = pstrCurr->structpNextValue;
}
if ((pstrCurr) && (pstrCurr->mDataMember1 == pstrTemp->mDataMember1) )
{
if (pstrCurr->mDataMember2 < pstrTemp->mDataMember2)
{
pstrTemp->structpNextValue = pstrCurr->structpNextValue;
free(pstrCurr);
pstrCurr = pstrTemp;
if (tempSeqNum == pstrTemp->mDataMember1)
{
mObject1 = pstrCurr;
}
if(pstrPrev)
{
pstrPrev->structpNextValue = pstrCurr;
}
}
if(!pstrTemp)
pstrTemp = NULL;
lNumOrphanRecord--;
}
else
{
if (pstrPrev)
{
pstrPrev->structpNextValue = pstrTemp;
pstrTemp->structpNextValue = pstrCurr;
}
else
{
pstrTemp->structpNextValue = pstrCurr;
mObject1 = pstrTemp;
}
}
}
pstrTemp = (CClass1*)malloc(sizeof(CClass1));
pstrTemp->structpNextValue = NULL;
lTemp--;
}
lNumRecord += lNumOrphanRecord;
pstrExcTemp = &mObject2[0];
pstrExcTemp = pstrExcTemp->structpNextValue;
while(mObject2->structpNextValue != NULL)
{
pstrExcTemp = mObject2->structpNextValue;
mObject2->structpNextValue = pstrExcTemp->structpNextValue;
if(!pstrExcTemp)
pstrExcTemp = NULL;
}
#include <iostream>
using namespace std;
template <class X>
void bubble(X *data, int size)
{
register int a, b;
X t;
for(a=1; a < size; a++)
for(b=size-1; b >= a; b--)
if(data[b-1] > data[b])
{
t = data[b-1];
data[b-1] = data[b];
data[b] = t;
}
}
int main()
{
int i[] = {3, 2, 5, 6, 1, 8, 9, 3, 6, 9};
double d[] = {1.2, 5.5, 2.2, 3.3};
int j;
bubble(i, 10); // sort ints
bubble(d, 4); // sort doubles
for(j=0; j<10; j++)
cout << i[j] << ' ';
cout << endl;
for(j=0; j<4; j++)
cout << d[j] << ' ';
cout << endl;
return 0;
}