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