CPP Program for implementing stack as linked list - Data Structures

#include<iostream>
using namespace std;
struct node
{
int data;
struct node *link;
};
struct node *top=NULL;

void push(int val)
{
node *newnode =new node;
newnode->data=val;
newnode->link=top;
top=newnode;
}

void pop()
{
if(top==NULL)
cout<<"\nStack is empty!";
else
top=top->link;
}


void display()
{
node *temp=top;
if(temp==NULL)
cout<<"\nStack is empty!";
else
{
while(temp!=NULL)
{
  cout<<temp->data<<"\n";//to print horizontally we need to point from bottom, hence to avoid this we print vertically..
  temp=temp->link;
}
}
}

int main()
{
int choice,val;
while(1)
{
cout<<"\nSTACK LINKED LIST \n1.Push 2.Pop 3.Display 4.Exit \nEnter your choice:";
cin>>choice;
switch(choice)
{
case 1:
   cout<<"\nEnter value to Push:";cin>>val;
   push(val);
   break;
case 2:
   pop();
   break;
case 3:
   display();
   break;
case 4:
   return 0;
   break;
default:
cout<<"\nCheck ur input\n";
}
}
return 0;
}



OUTPUT:

STACK LINKED LIST
1.Push 2.Pop 3.Display 4.Exit
Enter your choice:1

Enter value to Push:1

STACK LINKED LIST
1.Push 2.Pop 3.Display 4.Exit
Enter your choice:1

Enter value to Push:5

STACK LINKED LIST
1.Push 2.Pop 3.Display 4.Exit
Enter your choice:1

Enter value to Push:3

STACK LINKED LIST
1.Push 2.Pop 3.Display 4.Exit
Enter your choice:3
3
5
1

STACK LINKED LIST
1.Push 2.Pop 3.Display 4.Exit
Enter your choice:2

STACK LINKED LIST
1.Push 2.Pop 3.Display 4.Exit
Enter your choice:3
5
1

STACK LINKED LIST
1.Push 2.Pop 3.Display 4.Exit
Enter your choice:

CPP Program for Single linked list - Data Structures

#include<iostream>
using namespace std;
typedef struct node
{
int data;
struct node *link;
};
node *slist=NULL;
void insBeg(int val)
{
node *newnode = new node;

newnode->data=val;
newnode->link=slist;
slist=newnode;
}
void insEnd(int val)
{

if(slist==NULL)
{
node *newnode = new node;
newnode->data=val;
newnode->link=NULL;
slist=newnode;
}
else
{
node *temp=slist;
while(temp->link!=NULL)
temp=temp->link;
node *newnode = new node;
newnode->data=val;
newnode->link=NULL;
temp->link=newnode;
}
}
int insLoc(int val,int loc)
{
node *temp=slist;

for(int i=1;i<loc;i++)
{
temp=temp->link;
if(temp==NULL)
{
cout<<"\nInvalid Location:";
return 0;
}
}
node *newnode=new node;
newnode->data=val;
newnode->link=temp->link;
temp->link=newnode;
}
int delnode(int val)
{
if(slist->link==NULL && slist->data == val)
slist=NULL;
node *temp=slist;
while(temp!=NULL)
{
node *p;
if(temp->data==val)
{
   if(temp==slist)
   slist=temp->link;
   else
   {
     p->link=temp->link;
    }
    delete temp;
     return 0;
}
else
{
p=temp;
temp=temp->link;
}
}
cout<<"\nData not found";
}

int retrive(int loc)
{
node *temp=slist;
int count=1;
while(temp!=NULL)
{
if(count==loc)
return temp->data;
temp=temp->link;
count++;
}
cout<<"Invalid location";
}
int countnode()
{
node *temp=slist;
int count=1;
while(temp->link!=NULL)
{
temp=temp->link;
count++;
}
return count;
}

void display()
{
node *temp=slist;
while(temp!=NULL)
{
cout<<temp->data<<"\t";
temp=temp->link;
}
}

int main()
{
int choice,val,loc;
do
{
cout<<"\nSINGLE LINKED LIST\n1.Insert at the Beginning \n2.Insert at end\n3.Insert at location\n4.delete\n5.retrive\n6.Count\n7.Display\n8.Exit";
cin>>choice;
switch(choice)
{
case 1:
cout<<"\nEnter the data:";cin>>val;
insBeg(val);
break;
case 2:
cout<<"\nEnter the data:";cin>>val;
insEnd(val);
break;
case 3:
cout<<"\nEnter the data,location:";cin>>val;cin>>loc;
insLoc(val,loc);
break;
case 4:
cout<<"\nEnter the data:";cin>>val;
delnode(val);
break;
case 5:
cout<<"\nEnter the location:";cin>>val;
cout<<"\nretrieved data:"<<retrive(val);
break;
case 6:
cout<<"\nNumber of nodes:";cout<<countnode();
break;
case 7:
display();
break;
case 8:
return 0;
break;
}


}while(1);
return 0;
}

Queue implemented as linked list in CPP -Data Structures

#include<iostream>
using namespace std;
struct node
{
int data;
struct node *link;
};
struct node *front=NULL,*rear=NULL;

void enqueue(int val)
{
if(front==NULL && rear==NULL)
{
node *newnode=new node;
newnode->data=val;
newnode->link=NULL;
rear=front=newnode;
}
else
{
node *newnode=new node;
newnode->data=val;
newnode->link=NULL;
rear->link=newnode;
rear=newnode;
}
}
void dequeue()
{
if(front==NULL)
cout<<"\nQUEUE IS EMPTY!";
else if (front==rear)//only one node is left
{
front=NULL;
rear=NULL;
}
else
{
front=front->link;
}
}
void display()
{
if(front==NULL)
cout<<"\nQUEUE IS EMPTY!";
else
{
node *temp=front;
while(temp!=NULL)
{
cout<<temp->data<<"\t";
temp=temp->link;
}
}
}
int main()
{
int choice,val;
while(1)
{
cout<<"\nQUEUE LINKED LIST \n1.Enqueue 2.Dequeue 3.Display 4.Exit \nEnter your choice:";
cin>>choice;
switch(choice)
{
case 1:
   cout<<"\nEnter value:";cin>>val;
   enqueue(val);
   break;
case 2:
   dequeue();
   break;
case 3:
   display();
   break;
case 4:
   return 0;
   break;
default:
cout<<"\nCheck ur input\n";
}
}
return 0;
}


OUTPUT:


QUEUE LINKED LIST
1.Enqueue 2.Dequeue 3.Display 4.Exit
Enter your choice:1
Enter value:7

QUEUE LINKED LIST
1.Enqueue 2.Dequeue 3.Display 4.Exit
Enter your choice:1
Enter value:5

QUEUE LINKED LIST
1.Enqueue 2.Dequeue 3.Display 4.Exit
Enter your choice:1
Enter value:6

QUEUE LINKED LIST
1.Enqueue 2.Dequeue 3.Display 4.Exit
Enter your choice:2

QUEUE LINKED LIST
1.Enqueue 2.Dequeue 3.Display 4.Exit
Enter your choice:3

5       6

Simple Program for implementing Queue in CPP - Data Strucures

#include<iostream>
using namespace std;
int f=0,r=0,q[10];

int enqueue(int val)
{
if(r==10)
cout<<"\nQueue overflows";
else
{
q[++r]=val;
if(f==0)
f=1;
}
return q[r];
}

void dequeue()
{
if(f==0)
cout<<"\nQueue underflow";
else
{
if(f==r)
f=r=0;
else
f++;
}
}

void display()
{
for(int i=f;i<=r;i++)
cout<<q[i]<<"  ";
}

int main()
{
int choice,val;
while(1)
{
cout<<"\n1.Enqueue 2.Dequeue 3.Display 4.Exit\nEnter your choice:";
cin>>choice;
switch(choice)
{
case 1:
cout<<"\nEnter value:";cin>>val;
enqueue(val);
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
return 0;
break;
default:
cout<<"\nCheck your input";
}
}
return 0;
}

CPP program for merge sort - Data Structures

#include<iostream>           // Ref note
using namespace std;
int k[30];
void merge(int low,int mid,int high)
{
int i=low,j=mid+1,h=low;
int temp[30];           //temp is to contain the result(we may just print out inorder to avoid temp)
while(i<=mid && j<=high)         //i is for first half and j is for second half
{
   if(k[i]<=k[j])      // if first half element is lesser than second half
     {
        temp[h]=k[i];  
        i++;          
      }
    else
     {
      temp[h]=k[j];
       j++;          // increase corresponding iterative variable
     }
  h++;              // h is temp index
}
if(i>mid)          // if all first half elements are sorted and copied
{
   while(j<=high)  // copy the remaining elements from second half
    {
      temp[h]=k[j];
       j++;
       h++;
    }
}
else            // if all second half elements are copied and sorted
{
   while(i<=mid)  // copy the remaining elements of first half
   {
     temp[h]=k[i];
      i++;
      h++;
   }
}
i=low;
while(i<=high)  // just copying
{
k[i]=temp[i];
i++;
}


}

void mergesort(int low,int high)//this function splits the array into two until reaches single element and then merge
{
int mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(low,mid);         //first half
mergesort(mid+1,high);      //second half
merge(low,mid,high);        //sort and merge the two halves
}
}


int main()
{
int n,i;
cout<<"\nEnter no of elements:";cin>>n;
cout<<"\nEnter the elements:";
for(i=1;i<=n;i++)
cin>>k[i];
mergesort(1,n);
cout<<"\nAfter sorting:";
for(i=1;i<=n;i++)
cout<<k[i]<<"\t";
return 0;
}

CPP Program for converting infix expression into postfix expression - Data Structures

#include<iostream>
using namespace std;
char s[100],top=-1;
void push(char val)
{
s[++top]=val;
}
char pop()
{char cc;
cc=s[top];
top--;
return cc;
}

int isempty()
{
if(top==-1)
return 1;
}

int priority(char toptok)
{
if(toptok=='*'||toptok=='/')
return 2;
else if(toptok=='+'||toptok=='-')
return 1;
return 0;
}

int main()
{
char a[20],c,tptk,t;
int i=0;
cout<<"\nEnter the infix:";
cin>>a;
cout<<"\nPostfix:";
while(a[i]!='\0')
{
c=a[i];
if(c=='(')
push('(');
else if(c==')')
{
    c=pop();
  while(c!='(')
   {
     
      cout<<c;
       c=pop();
    }
}
else if(c=='*'||c=='/'||c=='+'||c=='-')
{
tptk=s[top];
while(!isempty() && priority(c)<=priority(tptk))
{t=pop();
 cout<<t;
  tptk=s[top];
}
push(c);
}
else
cout<<c;
i++;
}

while(!isempty())
{
c=pop();
cout<<c;
}
return 0;
}


OUTPUT:
Enter the infix:(a+b)*(c-d)/e

Postfix:ab+cd-*e/


Enter the infix:2+4

Postfix:24+

HeapSort program in CPP - Data Structures

#include<iostream>
using namespace std;
int k[20],heapsize;

void adjust(int i)
{
int left=2*i;
int right=2*i+1;
int largest,temp;
if(left<=heapsize && k[left]>k[i])
largest=left;
else
largest=i;
if(right<=heapsize && k[largest]<k[right])
largest=right;
if(largest!=i)
{
temp=k[i];
k[i]=k[largest];
k[largest]=temp;
adjust(largest);
}
}


void heapify(int n)
{
heapsize=n;
int i=n/2;
while(i>=1)
{
adjust(i);
i--;
}
}


void heapsort(int n)
{
int q=n;
heapify(n);
while(q>=2)
{
int temp=k[1];
k[1]=k[q];
k[q]=temp;
heapsize--;
adjust(1);
q--;
}
}


int main()
{
int n;
cout<<"\nEnter no of elements:";cin>>n;
cout<<"\nEnter elements:";
for(int i=1;i<=n;i++)
cin>>k[i];
heapsort(n);
for(int i=1;i<=n;i++)
cout<<k[i];
return 0;
}

OUTPUT:


Enter no of elements:6

Enter elements:4 1 5 3 2 6
123456

Conversion of General tree to binary Program in CPP - Data Structures

SOURCE CODE:

#include<iostream>
using namespace std;
struct node
{
char data;
struct node *left;
struct node *right;
};
struct node *head;

struct info
{
int level;
struct node *loc;
};
int nlev;
char nname;
info s[100];
int top=-1;

info push(info c)
{
top++;
s[top]=c;

return s[top];
}

void pop()
{
top--;
}

info peek()
{
return s[top];
}

void preorder(node *root)
{
if(root!=NULL)
{
cout<<root->data<<" ";
preorder(root->left);
preorder(root->right);
}
}
void inorder(node *root)
{
if(root!=NULL)
{
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}
int main()
{
char c;
int i=0;
cout<<"\nGENERAL TREE TO BINARY TREE\n Note: Input must be the preorder sequence of the general tree";
node *newnode = new node;
head=newnode;
head->left=NULL;
head->right=NULL;
info a;
a.level=-1;
a.loc=head;
push(a);
do
{
cout<<"\nEnter the level,name:";
cin>>nlev;
cin>>nname;
node* newnode=new node;
newnode->left=newnode->right=NULL;
newnode->data=nname;
info Pred=peek();
if(Pred.level< nlev)         //if different levels add to left -1<0,0<1,1<2
{ Pred.loc->left=newnode;}
else
{               //if levels match or lesser  2<1,1<1
    while(Pred.level>nlev)
    {
     pop();               //popped until we get a sibling
     Pred=peek();
     }
    if(Pred.level<nlev)  
    {
    cout<<"\nError in input.Mixed Level numbers\n";
    return 0;
    }
   Pred.loc->right=newnode;   //sibling added to the right
   pop(); //pop added node
}
a.level=nlev;
a.loc=newnode;
push(a);
cout<<"\nDo you wanna continue(y/n)?:";
cin>>c;
}while(c=='y');
cout<<"\nBinary Tree\nPreorder:";
preorder(head);
cout<<"\ninorder:";
inorder(head);
return 0;
}

OUTPUT:

GENERAL TREE TO BINARY TREE
 Note: Input must be the preorder sequence of the general tree


Enter the level,name:0 a

Do you wanna continue(y/n)?:y

Enter the level,name:1 b

Do you wanna continue(y/n)?:y

Enter the level,name:2 e

Do you wanna continue(y/n)?:y

Enter the level,name:1 c

Do you wanna continue(y/n)?:y

Enter the level,name:1 d

Do you wanna continue(y/n)?:y

Enter the level,name:2 f

Do you wanna continue(y/n)?:y

Enter the level,name:2 g

Do you wanna continue(y/n)?:y

Enter the level,name:2 h

Do you wanna continue(y/n)?:n

Binary Tree
Preorder: a b e c d f g h
inorder:   e b c f g h d a

Double linked list program in CPP - Data Structures

#include<iostream>
using namespace std;
typedef struct node
{
int data;
struct node *plink;
struct node *slink;
};
node *slist=NULL;
int insBeg(int val)
{
node *newnode=new node;
newnode->data=val;
newnode->plink=NULL;
newnode->slink=slist;
slist=newnode;
return 0;
}
void insEnd(int val)
{
if(slist==NULL)
{
node *newnode=new node;
newnode->data=val;
newnode->plink=NULL;
newnode->slink=NULL;
slist=newnode;
}
else
{
node *temp=slist;
while(temp->slink!=NULL)
temp=temp->slink;
node *newnode =new node;
newnode->data=val;
newnode->plink=temp;
newnode->slink=NULL;
temp->slink=newnode;
}
}
int insLoc(int val,int loc)
{
node *temp=slist;
for(int i=1;i<loc;i++)
{
temp=temp->slink;
if(temp==NULL)
{
cout<<"\nINVALID LOCATION";
return 0;
}
}
node *newnode=new node;
newnode->data=val;
newnode->plink=temp;
newnode->slink=temp->slink;
temp->slink->plink=newnode;
temp->slink=newnode;
}

int delnode(int val)
{
if(slist->slink==NULL && slist->data==val)
{
slist=NULL;
return 0;
}
node *temp=slist;
while(temp!=NULL)
{
if(temp->data==val)
{
   if(temp==slist)
      {
      slist=temp->slink;
      slist->plink=NULL;
      }
    else if(temp->slink==NULL)
      temp->plink->slink=NULL;
     else
      {
       temp->plink->slink=temp->slink;
       temp->slink->plink=temp->plink;
      }
     delete temp;
     return 0;
}
temp=temp->slink;
}
cout<<"\nData not found";
return 0;
}
int retrieve(int loc)
{
node *temp=slist;
int count=1;
while(temp!=NULL)
 {
 if(count==loc)
  return temp->data;
temp=temp->slink;
if(temp==slist)
break;
count++;
}
cout<<"\nInvalid location";
return 0;
}
int count()
{
node *temp=slist;
int count=0;
while(temp!=NULL)
{
temp=temp->slink;
count++;
if(temp==slist)
break;
}
return count;
}
void display()
{
node *temp=slist;
while(temp!=NULL)
{
cout<<temp->data<<"\t";
temp=temp->slink;
}
}


int main()
{
int choice,val,loc;
while(1)
{
cout<<"\nDOUBLE LINKED LIST\n1.Insert at the Beginning \n2.Insert at end\n3.Insert at location\n4.delete\n5.retrive\n6.Count\n7.Display\n8.Exit\nEnter choice:";
cin>>choice;
switch(choice)
{
case 1:
cout<<"\nEnter the data:";cin>>val;
insBeg(val);
break;
case 2:
cout<<"\nEnter the data:";cin>>val;
insEnd(val);
break;
case 3:
cout<<"\nEnter the data,location:";cin>>val;cin>>loc;
insLoc(val,loc);
break;
case 4:
cout<<"\nEnter the data:";cin>>val;
delnode(val);
break;
case 5:
cout<<"\nEnter the location:";cin>>loc;
cout<<"\nretrieved data:"<<retrieve(loc);
break;
case 6:
cout<<"\nNumber of nodes:";cout<<count();
break;
case 7:
display();
break;
case 8:
return 0;
break;
}


}
return 0;
}



OUTPUT:
DOUBLE LINKED LIST
1.Insert at the Beginning
2.Insert at end
3.Insert at location
4.delete
5.retrieve
6.Count
7.Display
8.Exit

Enter choice:1
Enter the data:10

Enter choice:2

Enter the data:30

Enter choice:2

Enter the data:20

Enter choice:3

Enter the data,location:15 2

Enter choice:7

10      30      15      20

Enter choice:4

Enter the data:30

Enter choice:5

Enter the location:2

retrieved data:15

Enter choice:6

Number of nodes:3

Enter choice:7

10      15      20

Quick sort program in C - Data Structures

#include<stdio.h>
int a[20];

int partition(int p, int r)
{
int x=a[r];
    int i=p-1;
    int j;
    for(j=p; j<=r-1;j++)
    {
    if(a[j]<=x)
    {
    i++;
    int temp=a[i];
    a[i]=a[j];
    a[j]=temp;
       }
    }
int temp=a[i+1];
a[i+1]=a[r];
a[r]=temp;
return i+1;
}
void quicksort(int p,int r)
{
if(p<r)
{
int q=partition(p,r);
quicksort(p,q-1);
quicksort(q+1,r);
}
}

void main()
{
int n,i;
printf("\n Enter no of elements");
scanf("%d",&n);
printf("\nEnter elements:");
for( i=1;i<=n;i++)
scanf("%d",&a[i]);
quicksort(1,n);
    printf("\n After sorting:");
    for( i=1;i<=n;i++)
    printf("%d ",a[i]);
}