Sunday, June 28, 2009

DS Extra programs_July 09

 


/*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);

 

}



--


<keep mailing>
d!-i@!\iOop™