Sunday, June 28, 2009

Some Data Structure Programs



/*1. WAP to implement searching in a linked list */

#include<iostream.h>
#include<conio.h>
#include<process.h>

class node
{
 int data;
 node *next;
 public:
 void insert();
 void search(int);
 void display();
};

node *start,*head,*temp;

void node::insert()
{
 head=new node;
 cout<<"\n Enter the data item: ";
 cin>>head->data;
 head->next=NULL;
 if(start==NULL)
 {
  start=head;
 }
 else
 {
  temp=start;
  while(temp->next!=NULL)
  {
   temp=temp->next;
  }
  temp->next=head;
 }
}

void node::display()
{
 temp=start;
 if(start==NULL)
 cout<<"\n Data list is empty ";
 else
 {
  cout<<"\n DATA LIST: ";
  while(temp!=NULL)
  {
   cout<<temp->data<<" ";
   temp=temp->next;
  }
 }
}

void node::search(int data)
{
 temp=start;
 if(start==NULL)
 cout<<"\n Data list is empty ";
 else
 {
  int flag=0;
  while(temp!=NULL)
  {
   if(data==temp->data)
   {
    cout<<"\n The data item is present in the list ";
    flag=1;
    break;
   }
   temp=temp->next;
  }
  if(flag!=1)
  cout<<"\n The data item is not found to be present ";
 }
}

void main()
{
 int ch,data;
 node ob;
 start=NULL;
 clrscr();
 do
 {
  cout<<"\n\n\n ... SINGLY LINKED LIST - SEARCH ... ";
  cout<<"\n\n 1.Insert\n 2.Display\n 3.Search\n 4. Exit\n ";
  cout<<"\n Enter your choice: ";
  cin>>ch;

  switch(ch)
  {
   case 1: ob.insert();
               break;
   case 2: ob.display();
               break;
   case 3: cout<<"\n Enter the data item to be searched: ";
               cin>>data;
               ob.search(data);
               break;
   case 4: cout<<"\n .... Thanking You! ....";
               getch();
               exit(0);
   default: cout<<"\n Invalid key-in ";
  }
 }while(1);

}



/*2. WAP to implement sorting in a linked list */

#include<iostream.h>
#include<conio.h>
#include<process.h>

class node
{
 int data;
 node *next;
 public:
 void insert();
 void sort();
 void display();
};

node *start,*head,*temp;

void node::insert()
{
 head=new node;
 cout<<"\n Enter the data item: ";
 cin>>head->data;
 head->next=NULL;
 if(start==NULL)
 {
  start=head;
 }
 else
 {
  temp=start;
  while(temp->next!=NULL)
  {
   temp=temp->next;
  }
  temp->next=head;
 }
}

void node::display()
{
 temp=start;
 if(start==NULL)
 cout<<"\n Data list is empty ";
 else
 {
  cout<<"\n DATA LIST: ";
  while(temp!=NULL)
  {
   cout<<temp->data<<" ";
   temp=temp->next;
  }
 }
}

void node::sort()
{
 if(start==NULL)
  cout<<"\n Data list is empty ";
 else
 {
  node *t1,*t2,*temp;
  for(t1=start;t1!=NULL;t1=t1->next)
  {
   for(t2=t1->next;t2!=NULL;t2=t2->next)
   {
    if(t1->data > t2->data)
    {
     temp->data=t1->data;
     t1->data=t2->data;
     t2->data=temp->data;
    }
   }
  }

  cout<<"\n List is sorted ";
 }
}

void main()
{
 int ch,data;
 node ob;
 start=NULL;
 clrscr();
 do
 {
  cout<<"\n\n\n ... SINGLY LINKED LIST - SORT ... ";
  cout<<"\n\n 1.Insert\n 2.Display\n 3.Sort\n 4. Exit\n ";
  cout<<"\n Enter your choice: ";
  cin>>ch;

  switch(ch)
  {
   case 1: ob.insert();
               break;
   case 2: ob.display();
               break;
   case 3: ob.sort();
               break;
   case 4: cout<<"\n .... Thanking You! ....";
               getch();
               exit(0);
   default: cout<<"\n Invalid key-in ";
  }
 }while(1);

}



/* 3.WAP to reverse a linked list, start pointer is given */

#include<iostream.h>
#include<conio.h>
#include<process.h>

class node
{
 int data;
 node *next;
 public:
 void insert();
 void reverse(node *);
 void display();
};

node *start,*head,*temp;

void node::insert()
{
 head=new node;
 cout<<"\n Enter the data item: ";
 cin>>head->data;
 head->next=NULL;
 if(start==NULL)
 {
  start=head;
 }
 else
 {
  temp=start;
  while(temp->next!=NULL)
  {
   temp=temp->next;
  }
  temp->next=head;
 }
}

void node::display()
{
 temp=start;
 if(start==NULL)
 cout<<"\n Data list is empty ";
 else
 {
  cout<<"\n DATA LIST: ";
  while(temp!=NULL)
  {
   cout<<temp->data<<" ";
   temp=temp->next;
  }
 }
}

void node::reverse(node *start)
{
 if(start==NULL)
  cout<<"\n Data list is empty ";
 else
 {
  int a[50],i=0,n;
  temp=start;
  //storing the data items to an array
  while(temp!=NULL)
  {
   a[i]=temp->data;
   temp=temp->next;
   n=i++;
  }
  i=n;
  temp=start;
  //forming linked list in reversed order
  while(temp!=NULL)
  {
   temp->data=a[i];
   temp=temp->next;
   i--;
  }

  cout<<"\n List is reversed ";
 }
}

void main()
{
 int ch,data;
 node ob;
 start=NULL;
 clrscr();
 do
 {
  cout<<"\n\n\n ... SINGLY LINKED LIST - REVERSE ... ";
  cout<<"\n\n 1.Insert\n 2.Display\n 3.Reverse\n 4. Exit\n ";
  cout<<"\n Enter your choice: ";
  cin>>ch;

  switch(ch)
  {
   case 1: ob.insert();
               break;
   case 2: ob.display();
               break;
   case 3: ob.reverse(start);
               break;
   case 4: cout<<"\n .... Thanking You! ....";
               getch();
               exit(0);
   default: cout<<"\n Invalid key-in ";
  }
 }while(1);

}


/*4. WAP to reverse a linked list within the list */

#include<iostream.h>
#include<conio.h>
#include<process.h>

class node
{
 int data;
 node *next;
 node *prev;
 public:
 void insert();
 void reverse();
 void display();
};

node *start,*head,*temp,*last;

void node::insert()
{
 head=new node;
 cout<<"\n Enter the data item: ";
 cin>>head->data;
 head->next=head->prev=NULL;
 if(start==NULL)
 {
  start=head;
  last=head;
 }
 else
 {
  last->next=head;
  head->prev=last;
  last=head;
 }
}

void node::display()
{
 temp=start;
 if(start==NULL)
 cout<<"\n Data list is empty ";
 else
 {
  cout<<"\n DATA LIST: ";
  while(temp!=NULL)
  {
   cout<<temp->data<<" ";
   temp=temp->next;
  }
 }
}

void node::reverse()
{
 if(start==NULL)
  cout<<"\n Data list is empty ";
 else
 {
  int len=0,lenM=0;
  temp=start;
  while(temp!=NULL)
  {
   len++;
   temp=temp->next;
  }
  node *t1,*t2,*temp;
  t1=start;
  t2=last;
  while(lenM<len/2)
  {
   temp->data=t1->data;
   t1->data=t2->data;
   t2->data=temp->data;
   t1=t1->next;
   t2=t2->prev;
   lenM++;
  }
  cout<<"\n List is reversed ";
 }
}

void main()
{
 int ch,data;
 node ob;
 start=last=NULL;
 clrscr();
 do
 {
  cout<<"\n\n\n ... SINGLY LINKED LIST - REVERSE WITHIN THE LIST ... ";
  cout<<"\n\n 1.Insert\n 2.Display\n 3.Reverse\n 4.Exit\n ";
  cout<<"\n Enter your choice: ";
  cin>>ch;

  switch(ch)
  {
   case 1: ob.insert();
               break;
   case 2: ob.display();
               break;
   case 3: ob.reverse();
               break;
   case 4: cout<<"\n .... Thanking You! ....";
               getch();
               exit(0);
   default: cout<<"\n Invalid key-in ";
  }
 }while(1);

}


/*5. WAP to remove first & last occurence of an element in a linked list */

#include<iostream.h>
#include<conio.h>
#include<process.h>

class node
{
 int data;
 node *next;
 public:
 void insert();
 void delet(int);
 void display();
};

node *start,*head,*temp;

void node::insert()
{
 head=new node;
 cout<<"\n Enter the data item: ";
 cin>>head->data;
 head->next=NULL;
 if(start==NULL)
 {
  start=head;
 }
 else
 {
  temp=start;
  while(temp->next!=NULL)
  {
   temp=temp->next;
  }
  temp->next=head;
 }
}

void node::display()
{
 temp=start;
 if(start==NULL)
 cout<<"\n Data list is empty ";
 else
 {
  cout<<"\n DATA LIST: ";
  while(temp!=NULL)
  {
   cout<<temp->data<<" ";
   temp=temp->next;
  }
 }
}

void node::delet(int data)
{
 temp=start;
 if(start==NULL)
 cout<<"\n Data list is empty ";
 else
 {
  //counting no. of occurence
  int count=0;
  while(temp!=NULL)
  {
   if(data==temp->data)
   {
    count++;
   }
   temp=temp->next;
  }

  //storing the position of occurence into an array
  int a[50],i=1,n,p=0;
  int pos[20];
  temp=start;
  while(temp!=NULL)
  {
   if(data==temp->data && i<=count)
   {
    pos[i]=p;
    i++;
   }
   temp=temp->next;
   p++;
  }

  //deleting first and last occurence
  int fst=pos[1];
  int lst=pos[count];
  node *t;
  temp=start;
  p=0;
  while(temp!=NULL)
  {
   if(data==temp->data && (fst==p || lst==p))
   {
    if(temp==start)
    {
     start=temp->next;
    }
    else
    {
     t->next=temp->next;
    }
   }
   t=temp;
   temp=temp->next;
   p++;
  }

 }
}

void main()
{
 int ch,data;
 node ob;
 start=NULL;
 clrscr();
 do
 {
  cout<<"\n\n\n ... SINGLY LINKED LIST - DELETE ... ";
  cout<<"\n\n 1.Insert\n 2.Display\n 3.Delete\n 4.Exit\n ";
  cout<<"\n Enter your choice: ";
  cin>>ch;

  switch(ch)
  {
   case 1: ob.insert();
               break;
   case 2: ob.display();
               break;
   case 3: cout<<"\n Enter the data item to be deleted: ";
               cin>>data;
               ob.delet(data);
               break;
   case 4: cout<<"\n .... Thanking You! ....";
               getch();
               exit(0);
   default: cout<<"\n Invalid key-in ";
  }
 }while(1);

}


/* 6.WAP to create a tree from inorder & preorder traversal sequences */

#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<process.h>
#include<string.h>

char inorder[20];
struct node
{
 char data;
 int num;
 node *left;
 node *right;
};

node *root;

class bst
{
 public:
 bst()
 {
  root=NULL;
 }
 node * insert(node *,int,char);
 node * create(char []);
 void postorder(node *);

};

int pos(char a)
{
 int p;
 for(int i=0;inorder[i]!='\0';i++)
 {
  if(inorder[i]==a)
  {
   p=i;
   break;
  }
 }
 return p;
}


node * bst::insert(node *root,int num, char data)
{
 if(root==NULL)
 {
  root=new node;
  root->data=data;
  root->num=num;
  root->left=root->right=NULL;
 }
 else if(num<root->num)
  root->left=insert(root->left,num,data);
 else
  root->right=insert(root->right,num,data);

 return root;

}



node * bst::create(char pre[])
{
 const len=strlen(pre);
 char data;
 int num;
 for(int i=0;i<len;i++)
 {
  data=pre[i];
  num=pos(pre[i]);
  root=this->insert(root,num,data);
 }
 return root;
}


void bst::postorder(node * root)
{
 if(root!=NULL)
 {
  postorder(root->left);
  postorder(root->right);
  cout<<root->data<<" ";
 }
}


void main()
{
 clrscr();
 bst ob;
 char ino[25],pre[25];
 cout<<"\n Enter the inorder sequence: ";
 gets(ino);
 cout<<"\n Enter the preorder sequence: ";
 gets(pre);
 strcpy(inorder,ino);
 root=ob.create(pre);
 cout<<"\n The tree is created and the post order sequence is: ";
 ob.postorder(root);
 getch();

}


/* 7.WAP to exchange right and left subtree of each node OR to produce mirror image of the tree */

#include<iostream.h>
#include<conio.h>
#include<process.h>

struct node
{
 char data;
 node *lchild,*rchild;
};

node *head;

class tree
{
 node *root;
 public:
 tree()
 {
  root=NULL;
 }
 node * read();
 node * makenode(char);
 void createtree(node *);
 void inorder(node *);
 void preorder(node *);
 void postorder(node *);
 void exchange(node *);
};

node * tree::read()
{
 char item;
 cout<<"\n Enter data: ";
 cin>>item;
 root=makenode(item);
 createtree(root);
 return root;
}

node * tree::makenode(char x)
{
 head=new node;
 head->data=x;
 head->lchild=head->rchild=NULL;
 return head;
}

void tree::createtree(node *root)
{
 int ch;
 char item;
 if(root!=NULL)
 {
  cout<<"\n Create left child for "<<root->data<<" (if so press \"1\")";
  cin>>ch;
  if(ch==1)
  {
   cout<<"\n Enter data: ";
   cin>>item;
   root->lchild=makenode(item);
   createtree(root->lchild);
  }

  cout<<"\n Create right child for "<<root->data<<" (if so press \"1\")";
  cin>>ch;
  if(ch==1)
  {
   cout<<"\n Enter data: ";
   cin>>item;
   root->rchild=makenode(item);
   createtree(root->rchild);
  }
 }
}

void tree::inorder(node *root)
{
 if(root!=NULL)
 {
  inorder(root->lchild);
  cout<<root->data<<" ";
  inorder(root->rchild);
 }
}

void tree::preorder(node *root)
{
 if(root!=NULL)
 {
  cout<<root->data<<" ";
  preorder(root->lchild);
  preorder(root->rchild);
 }
}

void tree::postorder(node *root)
{
 if(root!=NULL)
 {
  postorder(root->lchild);
  postorder(root->rchild);
  cout<<root->data<<" ";
 }
}

void tree::exchange(node *root)
{
  if(root!=NULL)
  {
   exchange(root->lchild);
   exchange(root->rchild);
   node *temp;
   temp=root->lchild;
   root->lchild=root->rchild;
   root->rchild=temp;
  }
}

void main()
{
tree ob;
node *root;
int ch;
clrscr();
do
{
cout<<"\n\n.... BINARY TREE ....\n\n";
cout<<"\n1.Creation\n2.Inorder Traversal\n3.Preorder Traversal";
cout<<"\n4.Postorder Traversal\n5.Exchange\n6.Exit";
cout<<"\n\t Enter your choice: ";
cin>>ch;
switch(ch)
{
 case 1:root=ob.read();
            break;
 case 2:ob.inorder(root);
            break;
 case 3:ob.preorder(root);
            break;
 case 4:ob.postorder(root);
            break;
 case 5:ob.exchange(root);
            break;
 case 6:cout<<"\n\n\t... Thanking You ...";
            getch();
            exit(0);
 default:cout<<"\n Invalid key-in ";
}

}while(1);

}


0 comments:

Post a Comment

Contact Form

Name

Email *

Message *

The Insane Techie - Android App

Launched an android app for the blog on 07th June 2016. Get it from google play store... Tips for using the app Use in landscape mo...