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<process.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);
}