VAAGDEVI DEGREE COLLEGE -MANCHERIAL

DATA STRUCTURE PRACTICAL PROGRAMS

1. Write C++ programs to implement the following using an array a) Stack ADT b) Queue
ADT

#include <iostream.h>

int stack[100], n=100, top=-1;

void push(int val) {
if(top>=n-1)
cout<<"Stack Overflow"<<endl;
else {
top++;
stack[top]=val;
}
}
void pop() {
if(top<=-1)
cout<<"Stack Underflow"<<endl;
else {
cout<<"The popped element is "<< stack[top] <<endl;
top--;
}
}
void display() {
if(top>=0) {
cout<<"Stack elements are:";
for(int i=top; i>=0; i--)
cout<<stack[i]<<" ";
cout<<endl;
} else
cout<<"Stack is empty";
}
int main() {
int ch, val;
cout<<"1) Push in stack"<<endl;
cout<<"2) Pop from stack"<<endl;
cout<<"3) Display stack"<<endl;
cout<<"4) Exit"<<endl;
do {
cout<<"Enter choice: "<<endl;
cin>>ch;
switch(ch) {
1
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
case 1: {
cout<<"Enter value to be pushed:"<<endl;
cin>>val;
push(val);
break;
}
case 2: {
pop();
break;
}
case 3: {
display();
break;
}
case 4: {
cout<<"Exit"<<endl;
break;
}
default: {
cout<<"Invalid Choice"<<endl;
}
}
}while(ch!=4);
return 0;
}

Output

1) Push in stack
2) Pop from stack
3) Display stack
4) Exit

Enter choice: 1
Enter value to be pushed: 2

b) QUEUE
#include <iostream>
using namespace std;
2
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
int queue[100], n = 100, front = - 1, rear = - 1;
void Insert() {
int val;
if (rear == n - 1)
cout<<"Queue Overflow"<<endl;
else {
if (front == - 1)
front = 0;
cout<<"Insert the element in queue : "<<endl;
cin>>val;
rear++;
queue[rear] = val;
}
}
void Delete() {
if (front == - 1 || front > rear) {
cout<<"Queue Underflow ";
return ;
} else {
cout<<"Element deleted from queue is : "<< queue[front] <<endl;
front++;;
}
}
void Display() {
if (front == - 1)
cout<<"Queue is empty"<<endl;
else {
cout<<"Queue elements are : ";
for (int i = front; i <= rear; i++)
cout<<queue[i]<<" ";
cout<<endl;
}
}
int main() {
int ch;
cout<<"1) Insert element to queue"<<endl;
cout<<"2) Delete element from queue"<<endl;
cout<<"3) Display all the elements of queue"<<endl;
cout<<"4) Exit"<<endl;
do {
cout<<"Enter your choice : "<<endl;
3
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
cin>>ch;
switch (ch) {
case 1: Insert();
break;
case 2: Delete();
break;
case 3: Display();
break;
case 4: cout<<"Exit"<<endl;
break;
default: cout<<"Invalid choice"<<endl;
}
} while(ch!=4);
return 0;
}

The output of the above program is as follows

1) Insert element to queue

2) Delete element from queue
3) Display all the elements of queue
4) Exit
Insert the element in queue : 3
Enter your choice : 1
Insert the element in queue : 5
Enter your choice : 2
Enter your choice : 7
Invalid choice
Enter your choice : 4
Exit

2. Write a C++ program to implement Circular queue using array

#include <iostream>
using namespace std;

int cqueue[5];
int front = -1, rear = -1, n=5;

4
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
void insertCQ(int val) {
if ((front == 0 && rear == n-1) || (front == rear+1)) {
cout<<"Queue Overflow \n";
return;
}
if (front == -1) {
front = 0;
rear = 0;
} else {
if (rear == n - 1)
rear = 0;
else
rear = rear + 1;
}
cqueue[rear] = val ;
}
void deleteCQ() {
if (front == -1) {
cout<<"Queue Underflow\n";
return ;
}
cout<<"Element deleted from queue is : "<<cqueue[front]<<endl;

if (front == rear) {
front = -1;
rear = -1;
} else {
if (front == n - 1)
front = 0;
else
front = front + 1;
}
}
void displayCQ() {
int f = front, r = rear;
if (front == -1) {
cout<<"Queue is empty"<<endl;
return;
}
cout<<"Queue elements are :\n";
if (f <= r) {
5
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
while (f <= r){
cout<<cqueue[f]<<" ";
f++;
}
} else {
while (f <= n - 1) {
cout<<cqueue[f]<<" ";
f++;
}
f = 0;
while (f <= r) {
cout<<cqueue[f]<<" ";
f++;
}
}
cout<<endl;
}
int main() {

int ch, val;

cout<<"1)Insert\n";
cout<<"2)Delete\n";
cout<<"3)Display\n";
cout<<"4)Exit\n";
do {
cout<<"Enter choice : "<<endl;
cin>>ch;
switch(ch) {
case 1:
cout<<"Input for insertion: "<<endl;
cin>>val;
insertCQ(val);
break;

case 2:
deleteCQ();
break;

case 3:
displayCQ();
break;
6
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

case 4:
cout<<"Exit\n";
break;
default: cout<<"Incorrect!\n";
}
} while(ch != 4);
return 0;
}

Output

The output of the above program is as follows −

1)Insert
2)Delete
3)Display
4)Exit

Enter choice : 1
Input for insertion:
Enter choice : 1
Enter choice : 2
Enter choice : 3
Queue elements are :
796
Enter choice : 4
Exit

3. Write C++ programs to implement the following using a single linked list. a) Stack ADT
b) Queue ADT

#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *next;
};
struct Node* top = NULL;
7
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
void push(int val) {
struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
newnode->data = val;
newnode->next = top;
top = newnode;
}
void pop() {
if(top==NULL)
cout<<"Stack Underflow"<<endl;
else {
cout<<"The popped element is "<< top->data <<endl;
top = top->next;
}
}
void display() {
struct Node* ptr;
if(top==NULL)
cout<<"stack is empty";
else {
ptr = top;
cout<<"Stack elements are: ";
while (ptr != NULL) {
cout<< ptr->data <<" ";
ptr = ptr->next;
}
}
cout<<endl;
}
int main() {
int ch, val;
cout<<"1) Push in stack"<<endl;
cout<<"2) Pop from stack"<<endl;
cout<<"3) Display stack"<<endl;
cout<<"4) Exit"<<endl;
do {
cout<<"Enter choice: "<<endl;
cin>>ch;
switch(ch) {
case 1: {
cout<<"Enter value to be pushed:"<<endl;
cin>>val;
8
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
push(val);
break;
}
case 2: {
pop();
break;
}
case 3: {
display();
break;
}
case 4: {
cout<<"Exit"<<endl;
break;
}
default: {
cout<<"Invalid Choice"<<endl;
}
}
}while(ch!=4);
return 0;
}

4. Write a C++ program to implement Circular queue using Single linked list.
#include <iostream>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node* front = NULL;
struct node* rear = NULL;
struct node* temp;
void Insert() {
int val;
cout<<"Insert the element in queue : "<<endl;
cin>>val;
if (rear == NULL) {
rear = (struct node *)malloc(sizeof(struct node));
rear->next = NULL;
9
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
rear->data = val;
front = rear;
} else {
temp=(struct node *)malloc(sizeof(struct node));
rear->next = temp;
temp->data = val;
temp->next = NULL;
rear = temp;
}
}
void Delete() {
temp = front;
if (front == NULL) {
cout<<"Underflow"<<endl;
return;
}
else
if (temp->next != NULL) {
temp = temp->next;
cout<<"Element deleted from queue is : "<<front->data<<endl;
free(front);
front = temp;
} else {
cout<<"Element deleted from queue is : "<<front->data<<endl;
free(front);
front = NULL;
rear = NULL;
}
}
void Display() {
temp = front;
if ((front == NULL) && (rear == NULL)) {
cout<<"Queue is empty"<<endl;
return;
}
cout<<"Queue elements are: ";
while (temp != NULL) {
cout<<temp->data<<" ";
temp = temp->next;
}
cout<<endl;
10
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
}
int main() {
int ch;
cout<<"1) Insert element to queue"<<endl;
cout<<"2) Delete element from queue"<<endl;
cout<<"3) Display all the elements of queue"<<endl;
cout<<"4) Exit"<<endl;
do {
cout<<"Enter your choice : "<<endl;
cin>>ch;
switch (ch) {
case 1: Insert();
break;
case 2: Delete();
break;
case 3: Display();
break;
case 4: cout<<"Exit"<<endl;
break;
default: cout<<"Invalid choice"<<endl;
}
} while(ch!=4);
return 0;
}

Output

The output of the above program is as follows

1) Insert element to queue

2) Delete element from queue
3) Display all the elements of queue
4) Exit

5. Write a C++ program to implement the double ended queue ADT using double linked
list.
#include <iostream>
using namespace std;
struct Node {

11
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
int data;
struct Node *prev;
struct Node *next;
};
struct Node* head = NULL;
void insert(int newdata) {
struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
newnode->data = newdata;
newnode->prev = NULL;
newnode->next = head;
if(head != NULL)
head->prev = newnode ;
head = newnode;
}
void display() {
struct Node* ptr;
ptr = head;
while(ptr != NULL) {
cout<< ptr->data <<" ";
ptr = ptr->next;
}
}
int main() {
insert(3);
insert(1);
insert(7);
insert(2);
insert(9);
cout<<"The doubly linked list is: ";
display();
return 0;
}

output

6. Write a C++ program to solve tower of Hanoi problem recursively

#include <iostream>
12
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
using namespace std;

//tower of HANOI function implementation

void TOH(int n, char Sour, char Aux, char Des)
{
if (n == 1) {
cout << "Move Disk " << n << " from " << Sour << " to " << Des << endl;
return;
}

TOH(n - 1, Sour, Des, Aux);

cout << "Move Disk " << n << " from " << Sour << " to " << Des << endl;
TOH(n - 1, Aux, Sour, Des);
}

//main program
int main()
{
int n;

cout << "Enter no. of disks:";

cin >> n;
//calling the TOH
TOH(n, 'A', 'B', 'C');

return 0;
}

7. Write C++ program to perform the following operations:

a) Insert an element into a binary search tree.
b) Delete an element from binary search tree.
c) Search for a key in a binary search tree

#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;

13
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
void insert(int,int );
void delte(int);
void display(int);
int search(int);
int search1(int,int);
int tree[40],t=1,s,x,i;

main()
{
int ch,y;
for(i=1;i<40;i++)
tree[i]=-1;
while(1)
{
cout <<"[Link]\[Link]\[Link]\[Link]\[Link]\nEnter your choice:";
cin >> ch;
switch(ch)
{
case 1:
cout <<"enter the element to insert";
cin >> ch;
insert(1,ch);
break;
case 2:
cout <<"enter the element to delete";
cin >>x;
y=search(1);
if(y!=-1) delte(y);
else cout<<"no such element in tree";
break;
case 3:
display(1);
cout<<"\n";
for(int i=0;i<=32;i++)
cout <<i;
cout <<"\n";
break;
case 4:
cout <<"enter the element to search:";
cin >> x;
y=search(1);
14
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
if(y == -1) cout <<"no such element in tree";
else cout <<x << "is in" <<y <<"position";
break;
case 5:
exit(0);
}
}
}

void insert(int s,int ch )

{
int x;
if(t==1)
{
tree[t++]=ch;
return;
}
x=search1(s,ch);
if(tree[x]>ch)
tree[2*x]=ch;
else
tree[2*x+1]=ch;
t++;
}
void delte(int x)
{
if( tree[2*x]==-1 && tree[2*x+1]==-1)
tree[x]=-1;
else if(tree[2*x]==-1)
{ tree[x]=tree[2*x+1];
tree[2*x+1]=-1;
}
else if(tree[2*x+1]==-1)
{ tree[x]=tree[2*x];
tree[2*x]=-1;
}
else
{
tree[x]=tree[2*x];
delte(2*x);
}
15
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
t--;
}

int search(int s)
{
if(t==1)
{
cout <<"no element in tree";
return -1;
}
if(tree[s]==-1)
return tree[s];
if(tree[s]>x)
search(2*s);
else if(tree[s]<x)
search(2*s+1);
else
return s;
}

void display(int s)
{
if(t==1)
{cout <<"no element in tree:";
return;}
for(int i=1;i<40;i++)
if(tree[i]==-1)
cout <<" ";
else cout <<tree[i];
return ;
}

int search1(int s,int ch)

{
if(t==1)
{
cout <<"no element in tree";
return -1;
}
if(tree[s]==-1)
return s/2;
16
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
if(tree[s] > ch)
search1(2*s,ch);
else search1(2*s+1,ch);
}

8. Write C++ programs for the implementation tree traversal technique A) BFS

#include<iostream.>
#include<queue>
#define NODE 6
using namespace std;
typedef struct node{
int val;
int state; //status
}node;
int graph[NODE][NODE] = {
{0, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0},
{1, 0, 0, 1, 0, 1},
{1, 1, 1, 0, 1, 1},
{0, 1, 0, 1, 0, 1},
{0, 0, 1, 1, 1, 0}
};
void bfs(node *vert, node s){
node u;
int i, j;
queue<node> que;
for(i = 0; i<NODE; i++){
vert[i].state = 0; //not visited
}
vert[[Link]].state = 1;//visited
[Link](s); //insert starting node
while(![Link]()){
u = [Link](); //delete from queue and print
[Link]();
cout << char([Link]+'A') << " ";
for(i = 0; i<NODE; i++){
if(graph[i][[Link]]){
//when the node is non-visited
if(vert[i].state == 0){
17
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
vert[i].state = 1;
[Link](vert[i]);
}
}
}
[Link] = 2;//completed for node u
}
}
int main(){
node vertices[NODE];
node start;
char s;
for(int i = 0; i<NODE; i++){
vertices[i].val = i;
}
s = 'B';//starting vertex B
[Link] = s-'A';
cout << "BFS Traversal: ";
bfs(vertices, start);
cout << endl;
}

Output

BFS Traversal: B A D E C F

9. Write a C++ program that uses recursive functions to traverse a binary search tree. a)
Pre-order b) In-order c) Post-order

#include<iostream>
using namespace std;
struct node {
int data;
struct node *left;
struct node *right;
};
struct node *createNode(int val) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->data = val;
temp->left = temp->right = NULL;
18
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
return temp;
}
void preorder(struct node *root) {
if (root != NULL) {
cout<<root->data<<" ";
preorder(root->left);
preorder(root->right);
}
}
struct node* insertNode(struct node* node, int val) {
if (node == NULL) return createNode(val);
if (val < node->data)
node->left = insertNode(node->left, val);
else if (val > node->data)
node->right = insertNode(node->right, val);
return node;
}
int main() {
struct node *root = NULL;
root = insertNode(root, 4);
insertNode(root, 5);
insertNode(root, 2);
insertNode(root, 9);
insertNode(root, 1);
insertNode(root, 3);
cout<<"Pre-Order traversal of the Binary Search Tree is: ";
preorder(root);
return 0;
}

Output

Pre-Order traversal of the Binary Search Tree is: 4 2 1 3 5 9

10. Write a C++ program to find height of a tree

#include <iostream>
using namespace std;
19
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
class node {
public:
int data;
node* left;
node* right;
};
int height(node* node) {
if (node == NULL)
return 0;
else {
int lDepth = height(node->left);
int rDepth = height(node->right);
if (lDepth > rDepth)
return(lDepth + 1);
else return(rDepth + 1);
}
}
node* insertNode(int data) {
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
int main() {
node *root = insertNode(4);
root->left = insertNode(5);
root->right = insertNode(0);
root->left->left = insertNode(1);
root->left->right = insertNode(9);
cout<<"The height of the given binary tree is "<<height(root);
return 0;
}

Output

The height of the given binary tree is 3

20
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

11 Write a C++ program to find MIN and MAX element of a BST.

#include <iostream>
using namespace std;

class Node {
public:
int data;
Node *left, *right;

Node(int data) {
this->data = data;
this->left = NULL;
this->right = NULL;
}
};

int findMaxNode(Node* root) {

if (root == NULL)
return -100;

int maxVal = root->data;

int leftMaxVal = findMaxNode(root->left);
int rightMaxVal = findMaxNode(root->right);
if (leftMaxVal > maxVal)
maxVal = leftMaxVal;
if (rightMaxVal > maxVal)
maxVal = rightMaxVal;
return maxVal;
}

int main() {

Node* NewRoot = NULL;

Node* root = new Node(5);
root->left = new Node(3);
root->right = new Node(2);
root->left->left = new Node(1);
21
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
root->left->right = new Node(8);
root->right->left = new Node(6);
root->right->right = new Node(9);
cout<<"The Maximum element of Binary Tree is "<<findMaxNode(root) << endl;
return 0;
}

Output

The Maximum element of Binary Tree is 9

12 Write a C++ program to find Inorder Successor of a given node.

#Iinclude<iostream.h>

#include<stdlib.h>
using namespace std;
int cost[10][10],i,j,k,n,qu[10],front,rare,v,visit[10],visited[10];
int main()
{
int m;
cout <<"Enter no of vertices:";
cin >> n;
cout <<"Enter no of edges:";
cin >> m;
cout <<"\nEDGES \n";
for(k=1; k<=m; k++)
{
cin >>i>>j;
cost[i][j]=1;
}
cout <<"Enter initial vertex to traverse from:";
cin >>v;
cout <<"Visitied vertices:";
cout <<v<<" ";
visited[v]=1;
k=1;
while(k<n)
{
22
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
for(j=1; j<=n; j++)
if(cost[v][j]!=0 && visited[j]!=1 && visit[j]!=1)
{
visit[j]=1;
qu[rare++]=j;
}
v=qu[front++];
cout<<v <<" ";
k++;
visit[v]=0;
visited[v]=1;
}
return 0;
}

13. Write C++ programs to perform the following operations on B-Trees and AVL Trees. a)
Insertion b) Deletion

include<iostream>
#include<cstdio>
#include<sstream>
#include<algorithm>
#define pow2(n) (1 << (n))
using namespace std;
struct avl {
int d;
struct avl *l;
struct avl *r;
}*r;
class avl_tree {
public:
int height(avl *);
int difference(avl *);
avl *rr_rotat(avl *);
avl *ll_rotat(avl *);
avl *lr_rotat(avl*);
avl *rl_rotat(avl *);
avl * balance(avl *);
avl * insert(avl*, int);
void show(avl*, int);

23
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
void inorder(avl *);
void preorder(avl *);
void postorder(avl*);
avl_tree() {
r = NULL;
}
};
int avl_tree::height(avl *t) {
int h = 0;
if (t != NULL) {
int l_height = height(t->l);
int r_height = height(t->r);
int max_height = max(l_height, r_height);
h = max_height + 1;
}
return h;
}
int avl_tree::difference(avl *t) {
int l_height = height(t->l);
int r_height = height(t->r);
int b_factor = l_height - r_height;
return b_factor;
}
avl *avl_tree::rr_rotat(avl *parent) {
avl *t;
t = parent->r;
parent->r = t->l;
t->l = parent;
cout<<"Right-Right Rotation";
return t;
}
avl *avl_tree::ll_rotat(avl *parent) {
avl *t;
t = parent->l;
parent->l = t->r;
t->r = parent;
cout<<"Left-Left Rotation";
return t;
}
avl *avl_tree::lr_rotat(avl *parent) {
avl *t;
t = parent->l;
parent->l = rr_rotat(t);
24
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
cout<<"Left-Right Rotation";
return ll_rotat(parent);
}
avl *avl_tree::rl_rotat(avl *parent) {
avl *t;
t = parent->r;
parent->r = ll_rotat(t);
cout<<"Right-Left Rotation";
return rr_rotat(parent);
}
avl *avl_tree::balance(avl *t) {
int bal_factor = difference(t);
if (bal_factor > 1) {
if (difference(t->l) > 0)
t = ll_rotat(t);
else
t = lr_rotat(t);
} else if (bal_factor < -1) {
if (difference(t->r) > 0)
t = rl_rotat(t);
else
t = rr_rotat(t);
}
return t;
}
avl *avl_tree::insert(avl *r, int v) {
if (r == NULL) {
r = new avl;
r->d = v;
r->l = NULL;
r->r = NULL;
return r;
} else if (v< r->d) {
r->l = insert(r->l, v);
r = balance(r);
} else if (v >= r->d) {
r->r = insert(r->r, v);
r = balance(r);
} return r;
}
void avl_tree::show(avl *p, int l) {
int i;
if (p != NULL) {
25
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
show(p->r, l+ 1);
cout<<" ";
if (p == r)
cout << "Root -> ";
for (i = 0; i < l&& p != r; i++)
cout << " ";
cout << p->d;
show(p->l, l + 1);
}
}
void avl_tree::inorder(avl *t) {
if (t == NULL)
return;
inorder(t->l);
cout << t->d << " ";
inorder(t->r);
}
void avl_tree::preorder(avl *t) {
if (t == NULL)
return;
cout << t->d << " ";
preorder(t->l);
preorder(t->r);
}
void avl_tree::postorder(avl *t) {
if (t == NULL)
return;
postorder(t ->l);
postorder(t ->r);
cout << t->d << " ";
}
int main() {
int c, i;
avl_tree avl;
while (1) {
cout << "[Link] Element into the tree" << endl;
cout << "[Link] Balanced AVL Tree" << endl;
cout << "[Link] traversal" << endl;
cout << "[Link] traversal" << endl;
cout << "[Link] traversal" << endl;
cout << "[Link]" << endl;
cout << "Enter your Choice: ";
cin >> c;
26
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
switch (c) {
case 1:
cout << "Enter value to be inserted: ";
cin >> i;
r = [Link](r, i);
break;
case 2:
if (r == NULL) {
cout << "Tree is Empty" << endl;
continue;
}
cout << "Balanced AVL Tree:" << endl;
[Link](r, 1);
cout<<endl;
break;
case 3:
cout << "Inorder Traversal:" << endl;
[Link](r);
cout << endl;
break;
case 4:
cout << "Preorder Traversal:" << endl;
[Link](r);
cout << endl;
break;
case 5:
cout << "Postorder Traversal:" << endl;
[Link](r);
cout << endl;
break;
case 6:
exit(1);
break;
default:
cout << "Wrong Choice" << endl;
}
}
return 0;
}

Output
[Link] Element into the tree
27
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
[Link] Balanced AVL Tree
[Link] traversal
[Link] traversal
[Link] traversal
[Link]

14 Write C++ programs for sorting a given list of elements in ascending order using
the following sorting methods.
a) Quick sort
b) Merge sort
#include <iostream>
using namespace std;

int partition(int arr[], int start, int end)

{

int pivot = arr[start];

int count = 0;
for (int i = start + 1; i <= end; i++) {
if (arr[i] <= pivot)
count++;
}

// Giving pivot element its correct position

int pivotIndex = start + count;
swap(arr[pivotIndex], arr[start]);

// Sorting left and right parts of the pivot element

int i = start, j = end;

while (i < pivotIndex && j > pivotIndex) {

while (arr[i] <= pivot) {

i++;
}
28
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

while (arr[j] > pivot) {

j--;
}

if (i < pivotIndex && j > pivotIndex) {

swap(arr[i++], arr[j--]);
}
}

return pivotIndex;
}

void quickSort(int arr[], int start, int end)

{

// base case
if (start >= end)
return;

// partitioning the array

int p = partition(arr, start, end);

// Sorting the left part

quickSort(arr, start, p - 1);

// Sorting the right part

quickSort(arr, p + 1, end);
}

int main()
{

int arr[] = { 9, 3, 4, 2, 1, 8 };
int n = 6;

quickSort(arr, 0, n - 1);

for (int i = 0; i < n; i++) {

cout << arr[i] << " ";
}
29
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

return 0;
}

B) Merge Sort

#include <iostream>

void merge(int array[], int const left,

int const mid, int const right)
{
auto const subArrayOne = mid - left + 1;
auto const subArrayTwo = right - mid;

// Create temp arrays

auto *leftArray = new int[subArrayOne],
*rightArray = new int[subArrayTwo];

// Copy data to temp arrays leftArray[]

// and rightArray[]
for (auto i = 0; i < subArrayOne; i++)
leftArray[i] = array[left + i];
for (auto j = 0; j < subArrayTwo; j++)
rightArray[j] = array[mid + 1 + j];

// Initial index of first sub-array

// Initial index of second sub-array
auto indexOfSubArrayOne = 0,
indexOfSubArrayTwo = 0;

// Initial index of merged array

int indexOfMergedArray = left;

// Merge the temp arrays back into

// array[left..right]
while (indexOfSubArrayOne < subArrayOne &&
indexOfSubArrayTwo < subArrayTwo)
{
if (leftArray[indexOfSubArrayOne] <=
rightArray[indexOfSubArrayTwo])
{
30
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
array[indexOfMergedArray] =
leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
}
else
{
array[indexOfMergedArray] =
rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
}
indexOfMergedArray++;
}

// Copy the remaining elements of

// left[], if there are any
while (indexOfSubArrayOne < subArrayOne)
{
array[indexOfMergedArray] =
leftArray[indexOfSubArrayOne];
indexOfSubArrayOne++;
indexOfMergedArray++;
}

// Copy the remaining elements of

// right[], if there are any
while (indexOfSubArrayTwo < subArrayTwo)
{
array[indexOfMergedArray] =
rightArray[indexOfSubArrayTwo];
indexOfSubArrayTwo++;
indexOfMergedArray++;
}
}

// begin is for left index and end is

// right index of the sub-array
// of arr to be sorted */
void mergeSort(int array[],
int const begin,
int const end)
{
31
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS
// Returns recursively
if (begin >= end)
return;

auto mid = begin + (end - begin) / 2;

mergeSort(array, begin, mid);
mergeSort(array, mid + 1, end);
merge(array, begin, mid, end);
}

// UTILITY FUNCTIONS
// Function to print an array
void printArray(int A[], int size)
{
for (auto i = 0; i < size; i++)
cout << A[i] << " ";
cout<<endl;
}

// Driver code
int main()
{
int arr[] = { 12, 11, 13, 5, 6, 7 };
auto arr_size = sizeof(arr) / sizeof(arr[0]);

cout << "Given array is "<<endl;

printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

cout << "Sorted array is "<<endl;

printArray(arr, arr_size);
return 0;
}

15. Write a C++ program to find optimal ordering of matrix multiplication.

32
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

#include <bits/stdc++.h>

// Matrix Ai has dimension p[i-1] x p[i]

// for i = 1 . . . n
int MatrixChainOrder(int p[], int i, int j)
{
if (i == j)
return 0;
int k;
int mini = INT_MAX;
int count;

// Place parenthesis at different places

// between first and last matrix,
// recursively calculate count of multiplications
// for each parenthesis placement
// and return the minimum count
for (k = i; k < j; k++)
{
count = MatrixChainOrder(p, i, k)
+ MatrixChainOrder(p, k + 1, j)
+ p[i - 1] * p[k] * p[j];

mini = min(count, mini);

}

// Return minimum count

return mini;
}

// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 3 };
int N = sizeof(arr) / sizeof(arr[0]);

// Function call
cout << "Minimum number of multiplications is "
<< MatrixChainOrder(arr, 1, N - 1);
return 0;
33
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

}
16. Write a C++ program that uses dynamic programming algorithm to solve the optimal
binary search tree problem
#include <iostream>
using namespace std;

int sum(int freq[], int low, int high) { //sum of frequency

from low to high range
int sum = 0;
for (int k = low; k <=high; k++)
sum += freq[k];
return sum;
}

int minCostBST(int keys[], int freq[], int n) {

int cost[n][n];

for (int i = 0; i < n; i++) //when only one key, move

along diagonal elements
cost[i][i] = freq[i];

for (int length=2; length<=n; length++) {

for (int i=0; i<=n-length+1; i++) { //from 0th row to
n-length+1 row as i
int j = i+length-1;
cost[i][j] = INT_MAX; //initially store to infinity

for (int r=i; r<=j; r++) {

//find cost when r is root of subtree
int c = ((r > i)?cost[i][r-1]:0)+((r <
j)?cost[r+1][j]:0)+sum(freq, i, j);
if (c < cost[i][j])
cost[i][j] = c;
}
}
}
return cost[0][n-1];
}

int main() {
int keys[] = {10, 12, 20};

34
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

int freq[] = {34, 8, 50};

int n = 3;
cout << "Cost of Optimal BST is: "<< minCostBST(keys, freq,
n);
}

Output
Cost of Optimal BST is: 142

17. Write a C++ program to implement Hash Table

#include<iostream>
#include<cstdlib>
#include<string>
#include<cstdio>
using namespace std;
const int TABLE_SIZE = 128;

/*
* HashEntry Class Declaration
*/
class HashEntry
{
public:
int key;
int value;
HashEntry(int key, int value)
{
this->key = key;
this->value = value;
}
};

/*
* HashMap Class Declaration
*/
class HashMap
{
private:
35
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

HashEntry **table;
public:
HashMap()
{
table = new HashEntry * [TABLE_SIZE];
for (int i = 0; i< TABLE_SIZE; i++)
{
table[i] = NULL;
}
}
/*
* Hash Function
*/
int HashFunc(int key)
{
return key % TABLE_SIZE;
}
/*
* Insert Element at a key
*/
void Insert(int key, int value)
{
int hash = HashFunc(key);
while (table[hash] != NULL && table[hash]->key != key)
{
hash = HashFunc(hash + 1);
}
if (table[hash] != NULL)
delete table[hash];
table[hash] = new HashEntry(key, value);
}
/*
* Search Element at a key
*/
int Search(int key)
{
int hash = HashFunc(key);
while (table[hash] != NULL && table[hash]->key != key)
{
hash = HashFunc(hash + 1);
36
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

}
if (table[hash] == NULL)
return -1;
else
return table[hash]->value;
}

/*
* Remove Element at a key
*/
void Remove(int key)
{
int hash = HashFunc(key);
while (table[hash] != NULL)
{
if (table[hash]->key == key)
break;
hash = HashFunc(hash + 1);
}
if (table[hash] == NULL)
{
cout<<"No Element found at key "<<key<<endl;
return;
}
else
{
delete table[hash];
}
cout<<"Element Deleted"<<endl;
}
~HashMap()
{
for (int i = 0; i < TABLE_SIZE; i++)
{
if (table[i] != NULL)
delete table[i];
delete[] table;
}
}
};
37
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

/*
* Main Contains Menu
*/
int main()
{
HashMap hash;
int key, value;
int choice;
while (1)
{
cout<<"\n----------------------"<<endl;
cout<<"Operations on Hash Table"<<endl;
cout<<"\n----------------------"<<endl;
cout<<"[Link] element into the table"<<endl;
cout<<"[Link] element from the key"<<endl;
cout<<"[Link] element at a key"<<endl;
cout<<"[Link]"<<endl;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter element to be inserted: ";
cin>>value;
cout<<"Enter key at which element to be inserted: ";
cin>>key;
[Link](key, value);
break;
case 2:
cout<<"Enter key of the element to be searched: ";
cin>>key;
if ([Link](key) == -1)
{
cout<<"No element found at key "<<key<<endl;
continue;
}
else
{
cout<<"Element at key "<<key<<" : ";
cout<<[Link](key)<<endl;
38
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

}
break;
case 3:
cout<<"Enter key of the element to be deleted: ";
cin>>key;
[Link](key);
break;
case 4:
exit(1);
default:
cout<<"\nEnter correct option\n";
}
}
return 0;
}

18. Write C++ programs to perform the following on Heap

a) Build Heap
b) Insertion
c) Deletion

#include <iostream>

using namespace std;

// To heapify a subtree rooted with node i which is

// an index of arr[] and n is the size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2

// If left child is larger than root

if (l < n && arr[l] > arr[largest])
largest = l;

39
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

// If right child is larger than largest so far

if (r < n && arr[r] > arr[largest])
largest = r;

// If largest is not root

if (largest != i) {
swap(arr[i], arr[largest]);

// Recursively heapify the affected sub-tree

heapify(arr, n, largest);
}
}

// Function to delete the root from Heap

void deleteRoot(int arr[], int& n)
{
// Get the last element
int lastElement = arr[n - 1];

// Replace root with last element

arr[0] = lastElement;

// Decrease size of heap by 1

n = n - 1;

// heapify the root node

heapify(arr, n, 0);
}

/* A utility function to print array of size n */

void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n";
}

// Driver Code
int main()
{
40
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

int arr[] = { 10, 5, 3, 2, 4 };

int n = sizeof(arr) / sizeof(arr[0]);

deleteRoot(arr, n);

printArray(arr, n);

return 0;
}

19. Write C++ programs to perform following operations on Skip List

a) Insertion
b) Deletion
#include <bits/stdc++.h>
using namespace std;

// Class to implement node

class Node
{
public:
int key;

// Array to hold pointers to node of different level

Node **forward;
Node(int, int);
};

Node::Node(int key, int level)

{
this->key = key;

// Allocate memory to forward

forward = new Node*[level+1];

// Fill forward array with 0(NULL)

memset(forward, 0, sizeof(Node*)*(level+1));
};

// Class for Skip list

41
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

class SkipList
{
// Maximum level for this skip list
int MAXLVL;

// P is the fraction of the nodes with level

// i pointers also having level i+1 pointers
float P;

// current level of skip list

int level;

// pointer to header node

Node *header;
public:
SkipList(int, float);
int randomLevel();
Node* createNode(int, int);
void insertElement(int);
void displayList();
};

SkipList::SkipList(int MAXLVL, float P)

{
this->MAXLVL = MAXLVL;
this->P = P;
level = 0;

// create header node and initialize key to -1

header = new Node(-1, MAXLVL);
};

// create random level for node

int SkipList::randomLevel()
{
float r = (float)rand()/RAND_MAX;
int lvl = 0;
while (r < P && lvl < MAXLVL)
{
lvl++;
42
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

r = (float)rand()/RAND_MAX;
}
return lvl;
};

// create new node

Node* SkipList::createNode(int key, int level)
{
Node *n = new Node(key, level);
return n;
};

// Insert given key in skip list

void SkipList::insertElement(int key)
{
Node *current = header;

// create update array and initialize it

Node *update[MAXLVL+1];
memset(update, 0, sizeof(Node*)*(MAXLVL+1));

/* start from highest level of skip list

move the current pointer forward while key
is greater than key of node next to current
Otherwise inserted current in update and
move one level down and continue search
*/
for (int i = level; i >= 0; i--)
{
while (current->forward[i] != NULL &&
current->forward[i]->key < key)
current = current->forward[i];
update[i] = current;
}

current = current->forward[0];

if (current == NULL || current->key != key)

{

43
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

if (rlevel > level)

{
for (int i=level+1;i<rlevel+1;i++)
update[i] = header;

level = rlevel;
}

Node* n = createNode(key, rlevel);

for (int i=0;i<=rlevel;i++)

{
n->forward[i] = update[i]->forward[i];
update[i]->forward[i] = n;
}
cout << "Successfully Inserted key " << key << "\n";
}
};

// Display skip list level wise

void SkipList::displayList()
{
cout<<"\n*****Skip List*****"<<"\n";
for (int i=0;i<=level;i++)
{
Node *node = header->forward[i];
cout << "Level " << i << ": ";
while (node != NULL)
{
cout << node->key<<" ";
node = node->forward[i];
}
cout << "\n";
}
};

// Driver to test above code

int main()
{
// Seed random number generator
44
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

srand((unsigned)time(0));

// create SkipList object with MAXLVL and P

SkipList lst(3, 0.5);

[Link](3);
[Link](6);
[Link](7);
[Link](9);
[Link](12);
[Link](19);
[Link](17);
[Link](26);
[Link](21);
[Link](25);
[Link]();
}

20. Write a C++ Program to Create a Graph using Adjacency Matrix Representation
#include<iostream>
using namespace std;
int vertArr[20][20]; //the adjacency matrix initially 0
int count = 0;
void displayMatrix(int v) {
int i, j;
for(i = 0; i < v; i++) {
for(j = 0; j < v; j++) {
cout << vertArr[i][j] << " ";
}
cout << endl;
}
}
void add_edge(int u, int v) { //function to add edge into the matrix
vertArr[u][v] = 1;
vertArr[v][u] = 1;
}
main(int argc, char* argv[]) {
int v = 6; //there are 6 vertices in the graph
add_edge(0, 4);

45
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

add_edge(0, 3);
add_edge(1, 2);
add_edge(1, 4);
add_edge(1, 5);
add_edge(2, 3);
add_edge(2, 5);
add_edge(5, 3);
add_edge(5, 4);
displayMatrix(v);
}

21. Write a C++ program to implement graph traversal techniques a) BFS b) DFS

#include <bits/stdc++.h>
using namespace std;

// This class represents a directed graph using

// adjacency list representation
class Graph {

// No. of vertices
int V;

// Pointer to an array containing adjacency lists

vector<list<int> > adj;

public:
// Constructor
Graph(int V);

// Function to add an edge to graph

void addEdge(int v, int w);

// Prints BFS traversal from a given source s

void BFS(int s);
};

46
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

Graph::Graph(int V)
{
this->V = V;
[Link](V);
}

void Graph::addEdge(int v, int w)

{
// Add w to v’s list.
adj[v].push_back(w);
}

void Graph::BFS(int s)
{
// Mark all the vertices as not visited
vector<bool> visited;
[Link](V, false);

// Create a queue for BFS

list<int> queue;

// Mark the current node as visited and enqueue it

visited[s] = true;
queue.push_back(s);

while (![Link]()) {

// Dequeue a vertex from queue and print it

s = [Link]();
cout << s << " ";
queue.pop_front();

// Get all adjacent vertices of the dequeued

// vertex s.
// If an adjacent has not been visited,
// then mark it visited and enqueue it
for (auto adjacent : adj[s]) {
if (!visited[adjacent]) {

47
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

visited[adjacent] = true;
queue.push_back(adjacent);
}
}
}
}

// Driver code
int main()
{
// Create a graph given in the above diagram
Graph g(4);
[Link](0, 1);
[Link](0, 2);
[Link](1, 2);
[Link](2, 0);
[Link](2, 3);
[Link](3, 3);

cout << "Following is Breadth First Traversal "

<< "(starting from vertex 2) \n";
[Link](2);

return 0;
}

Output
Following is Breadth First Traversal (starting from vertex 2)
2031
Time Complexity: O(V+E), where V is the number of nodes and E is the number of edges.
Auxiliary Space: O(V)

// C++ program to print DFS traversal from

// a given vertex in a given graph
#include <bits/stdc++.h>
using namespace std;

48
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

// Graph class represents a directed graph

// using adjacency list representation
class Graph {
public:
map<int, bool> visited;
map<int, list<int> > adj;

// Function to add an edge to graph

void addEdge(int v, int w);

// DFS traversal of the vertices

// reachable from v
void DFS(int v);
};

void Graph::addEdge(int v, int w)

{
// Add w to v’s list.
adj[v].push_back(w);
}

void Graph::DFS(int v)
{
// Mark the current node as visited and
// print it
visited[v] = true;
cout << v << " ";

// Recur for all the vertices adjacent

// to this vertex
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFS(*i);
}

// Driver code

49
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

int main()
{
// Create a graph given in the above diagram
Graph g;
[Link](0, 1);
[Link](0, 2);
[Link](1, 2);
[Link](2, 0);
[Link](2, 3);
[Link](3, 3);

cout << "Following is Depth First Traversal"

" (starting from vertex 2) \n";

// Function call
[Link](2);

return 0;
}

Output
Following is Depth First Traversal (starting from vertex 2)
2013

22. Write a C++ program to Heap sort using tree structure.

#include <iostream>
using namespace std;

// To heapify a subtree rooted with node i which is

// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root Since we are using 0 based indexing
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2

50
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

// If left child is larger than root

if (l < n && arr[l] > arr[largest])
largest = l;

// If right child is larger than largest so far

if (r < n && arr[r] > arr[largest])
largest = r;

// If largest is not root

if (largest != i) {
swap(arr[i], arr[largest]);

// Recursively heapify the affected sub-tree

heapify(arr, n, largest);
}
}

// main function to do heap sort

void heapSort(int arr[], int n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);

// One by one extract an element from heap

for (int i = n - 1; i >= 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);

// call max heapify on the reduced heap

heapify(arr, i, 0);
}
}

/* A utility function to print array of size n */

void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
51
 VAAGDEVI DEGREE COLLEGE -MANCHERIAL
DATA STRUCTURE PRACTICAL PROGRAMS

cout << "\n";

}

// Driver program
int main()
{
int arr[] = { 60 ,20 ,40 ,70, 30, 10};
int n = sizeof(arr) / sizeof(arr[0]);
//heapify algorithm
// the loop must go reverse you will get after analyzing manually
// (i=n/2 -1) because other nodes/ ele's are leaf nodes
// (i=n/2 -1) for 0 based indexing
// (i=n/2) for 1 based indexing
for(int i=n/2 -1;i>=0;i--){
heapify(arr,n,i);
}

cout << "After heapifying array is \n";

printArray(arr, n);

heapSort(arr, n);

cout << "Sorted array is \n";

printArray(arr, n);

return 0;
}

52