ARULMIGU KALASALINGAM COLLEGE OF ARTS & SCIENCE
ANAND NAGAR, KRISHNANKOIL – 626 126.
FIRST MSC COMPUTE SCIENCE
CS 16 : LAB 2.DATA STRUCTURE AND ALGORITHMS LAB PROGRAMS
1.a)STACK IMPLEMENTATION USING ARRAY
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
class stack
{
int top,stk[5];
public:
stack()
{
top=-1;
}
void push()
{
int x;
if(top>4)
{
cout<<"stack overflow.";
return;
}
cout<<"enter the element to be inserted:";
cin>>x;
stk[++top]=x;
cout<<"\n inserted:"<<x;
}
void pop()
{
if(top<0)
{
cout<<"stack overflow:";
return;
}
cout<<"deleted"<<stk[top--];
}
void display()
{
int i;
if(top<0)
{
cout<<"stack is empty.";
return;
}
for(i=top;i>=0;i--)
{
cout<<stk[i]<<" ";
}
}
};
main()
{
int ch;
stack s;
clrscr();
while(1)
{
cout<<"\n1.puah\n2.pop\n3.display\n4.exit\nenter your choice:";
cin>>ch;
switch(ch)
{
case 1:
s.push();
break;
case 2:
s.pop();
break;
case 3:
s.display();
break;
case 4:
return(0);
break;
default:
cout<<"enter the choice correctly";
break;
}
}
}
OUTPUT:-
1.PUSH
2.POP
3.DISPLAY
4.EXIT
Enter your choice: 1
Enter the element to be inserted : 2
Inserted : 2
1.PUSH
2.POP
3.DISPLAY
4.EXIT
Enter your choice: 1
Enter the element to be inserted: 6
Inserted: 6
1.PUSH
2.POP
3.DISPLAY
4.EXIT
Enter your choice: 1
Enter the element to be inserted : 3
Inserted : 3
1.PUSH
2.POP
3.DISPLAY
4.EXIT
Enter your choice : 3
Stack list is :
362
1.PUSH
2.POP
3.DISPLAY
4.EXIT
Enter your choice : 2
Deleted : 3
1.PUSH
2.POP
3.DISPLAY
4.EXIT
Enter your choice : 3
Stack list is :
62
1.PUSH
2.POP
3.DISPLAY
4.EXIT
Enter your choice: 4
1.b)STACK IMPLEMENTATION USING LINKED LIST
#include<iostream.h>
#include<conio.h>
struct node
int data;
struct node*next;
};
class stack
struct node*top;
public:
stack()
top=NULL;
void push();
void pop();
void show();
};
void stack::push()
int value;
struct node*ptr;
cout<<"\n push operation:";
cout<<"\n enter the no to be inserted:";
cin>>value;
ptr=new node;
ptr->data=value;
ptr->next=NULL;
if(top!=NULL)
ptr->next=top;
top=ptr;
cout<<"\n new item is inserted into the stack";
void stack::pop()
struct node*temp;
if(top==NULL)
cout<<"\n stack is empty";
}
else
temp=top;
top=top->next;
cout<<"\n pop operation \n poped value is:"<<temp->data;
delete temp;
void stack::show()
struct node*ptr1=top;
if(top==NULL)
cout<<"\n the stack is empty \n";
else
cout<<"\n the stack is\n";
while(ptr1!=NULL)
cout<<"->"<<ptr1->data;
ptr1=ptr1->next;
main()
stack s;
int choice,ch;
clrscr();
cout<<"\n stack using linked list\n";
do
cout<<"1.push\n 2.pop\n 3.display\n";
cout<<"enter your choice(1-3)\n";
cin>>choice;
switch (choice)
case 1:s.push();break;
case 2:s.pop();break;
case 3:s.show();break;
default:
cout<<"\n please enter your choice";
break;
}
cout<<"\n do you want to continue 1,0 \n";
cin>>ch;
while(ch);
return(0);
OUTPUT:-
STACK USING LINKED LIST
1.PUSH
2.POP
3.DISPLAY
Enter your choice( 1 – 3)
Push operation :
Enter the no to be inserted : 2
New item is inserted into the stack
Do you want to continue 1,0
1.PUSH
2.POP
3.DISPLAY
Enter your choice(1 – 3)
Push operation :
Enter the no to be inserted : 6
New item is inserted into the stack
Do you want to continue 1,0
1.PUSH
2.POP
3.DISPLAY
Enter your choice( 1- 3)
Push operation :
Enter the no to be inserted : 4
Do you want to continue 1,0
Enter your choice( 1- 3)
The stack is :
->4->6->2
Do you want to continue 1,0
1
1.PUSH
2.POP
3.DISPLAY
Enter your choice( 1- 3)
Pop operation :
Poped value is 4
Do you want to continue 1,0
1.PUSH
2.POP
3.DISPLAY
Enter your choice( 1- 3)
The stack is
->6->2
Do you want to continue 1,0
0
2.a)QUEUE IMPLEMENTATION USING ARRAY
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
class queue
int q[5],rear,front,x;
public:
queue()
rear=-1;
front=-1;
void insert()
if(rear>4)
cout<<"queue is overflown\n";
return;
cout<<"\n enter the element";
cin>>x;
q[++rear]=x;
cout<<"inserted"<<x;
void remove()
if(front==rear)
cout<<"queue is underflown\n";
return;
cout<<"delete"<<q[++front];
void display()
int i;
if(rear==front)
cout<<"queue is empty\n";
return;
for(i=front+1;i<=rear;i++)
cout<<q[i]<<" ";
};
int main()
int ch;
queue qu;
clrscr();
while(1)
cout<<"\n1.insert\n2.deletion\n3.display\n4.exit";
cout<<"\n enter your choice";
cin>>ch;
switch(ch)
case 1:
qu.insert();
break;
case 2:
qu.remove();
case 3:
qu.display();
case 4:
return(0);
default:
cout<<"\n your choice is wrong";
break;
return(0);
OUTPUT:-
1.Insertion
2.Deletion
3.Display
4.Exit
Enter your choice : 1
Enter the element : 3
Inserted : 3
1.Insertion
2.Deletion
3.Display
4.Exit
Enter your choice : 1
Enter the element : 6
Inserted : 6
1.Insertion
2.Deletion
3.Display
4.Exit
Enter your choice : 1
Enter the element : 2
Inserted : 2
1.Insertion
2.Deletion
3.Display
4.Exit
Enter your choice : 3
362
1.Insertion
2.Deletion
3.Display
4.Exit
Enter your choice : 2
Deleted : 3
1.Insertion
2.Deletion
3.Display
4.Exit
Enter your choice : 3
62
1.Insertion
2.Deletion
3.Display
4.Exit
Enter your choice : 4
2.b) QUEUE IMPLEMENTATION USING LINKED LIST
#include<iostream.h>
#include<stdio.h>
#include<conio.h>
struct node
int data;
node *next;
};
class queue
struct node *front,*rear,*p,*np;
public:
queue()
front=NULL;
rear=NULL;
p=NULL;
np=NULL;
}
void push(int x);
void remove();
void show();
};
void queue::push(int x)
np=new node;
np->data=x;
np->next=NULL;
if(front==NULL)
front=rear=np;
rear->next=NULL;
else
rear->next=np;
rear=np;
rear->next=NULL;
}
void queue::remove()
int x;
if(front==NULL)
cout<<"empty queue\n";
else
p=front;
x=p->data;
front=front->next;
delete(p);
cout<<"\n remove value:";
cout<<x;
void queue::show()
struct node *ptr1=front;
if(front==NULL)
{
cout<<"queue empty";
else
while(ptr1!=NULL)
cout<<"->"<<ptr1->data;
ptr1=ptr1->next;
};
int main()
queue q;
int n,choice,x;
clrscr();
cout<<"queue operation\n";
while(1)
cout<<"\n1.insertion \n2.deletion \n3.display \n4.exit\n";
cout<<"\n enter your choice";
cin>>choice;
switch(choice)
case 1:
cout<<"enter the value to be inserted into queue:\n";
cin>>x;
q.push(x);
break;
case 2:
q.remove();
break;
case 3:
q.show();
break;
case 4:
return(0);
default:
cout<<"\n your choice is wrong";
break;
}
}
return(0);
OUTPUT:-
Queue Operation
1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT
ENTER YOUR CHOICE 1
Enter the value to be entered into queue
1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT
ENTER YOUR CHOICE 1
Enter the value to be entered into queue
1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT
ENTER YOUR CHOICE 1
Enter the value to be entered into queue
1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT
ENTER YOUR CHOICE 3
->4->6->5
1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT
ENTER YOUR CHOICE 2
Removed value : 4
1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT
ENTER YOUR CHOICE 3
->6->5
1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT
ENTER YOUR CHOICE 1
3) HEAP SORT
#include<iostream.h>
#include<conio.h>
void maxheap(int *a,int i,int n)
int j,temp;
temp=a[i];
j=2*i;
while(j<=n)
if(j<n&&a[j+1]>a[j])
j=j+1;
if(temp>a[j])
break;
else if(temp<=a[j])
a[j/2]=a[j];
j=2*j;
};
a[j/2]=temp;
}
void heapsort(int *a,int n)
int i,temp;
for(i=n;i>=2;i--)
temp=a[i];
a[i]=a[1];
a[1]=temp;
maxheap(a,1,i-1);
void buildmaxheap(int *a,int n)
int i;
for(i=n;i>=1;i--)
maxheap(a,i,n);
void main()
int n,a[20],i;
clrscr();
cout<<"enter the elements in array\n";
cin>>n;
cout<<"enter the elements:"<<endl;
for(i=1;i<=n;i++)
cin>>a[i];
buildmaxheap(a,n);
heapsort(a,n);
cout<<"\n sorted list\n";
for(i=1;i<=n;i++)
cout<<a[i]<<endl;
getch();
};
OUTPUT:-
Enter no of elements in array
Enter the elements :
Sorted list :
4) TREE TRAVERSAL
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
struct node
int data;
struct node*left;
struct node*right;
};
struct node*newnode(int data)
struct node*node=(struct node*)malloc(sizeof(struct node));
node->data=data;
node->left=NULL;
node->right=NULL;
return(node);
void postorder(struct node*node)
if(node==NULL)
return;
postorder(node->left);
postorder(node->right);
cout<<node->data;
void preorder(struct node*node)
if(node==NULL)
return;
cout<<node->data;
preorder(node->left);
preorder(node->right);
void inorder(struct node*node)
if(node==NULL)
return;
inorder(node->left);
cout<<node->data;
inorder(node->right);
void main()
{
clrscr();
struct node*root=newnode(1);
root->left=newnode(2);
root->right=newnode(3);
root->left->left=newnode(4);
cout<<"preorder."<<endl;
preorder(root);
cout<<endl;
cout<<"inorder."<<endl;
inorder(root);
cout<<"postorder."<<endl;
cout<<endl;
postorder(root);
getch();
OUTPUT:-
Preorder :
12453
Inorder :
42513
Postorder :
45231
5) BREADTH FIRST SEARCH
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
int cost[20][20],i,j,k,n,q[20],front,rear,v,visit[20],visited[20];
void main()
int m;
clrscr();
cout<<"Enter no of vertices:";
cin>>n;
cout<<"\n Enter no of edges:";
cin>>m;
cout<<"\n edges:\n";
for(k=1;k<=m;k++)
cin>>i>>j;
cost[i][j]=1;
cout<<"\n Enter initial vertex:";
cin>>v;
cout<<"\n Visited vertex\n";
cout<<v<<"->>";
visited[v]=1;
k=1;
while(k<n)
for(j=1;j<=n;j++)
if(cost[v][j]!=0&&visited[j]!=1&&visit[j]!=1)
visit[j]=1;
q[rear++]=j;
v=q[front++];
cout<<""<<v<<"";
k++;
visit[v]=0;
visited[v]=1;
getch();
OUTPUT:-
Enter the number of vertices:5
Enter the no of edges:4
Edges:
12
24
13
25
Enter initial vertex:
Visited vertex:
1->>2 3 4 5
6) DEPTH FIRST SEARCH
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10];
void main()
clrscr();
int m;
cout<<" Enter Number of vertices:\n";
cin>>n;
cout<<" Enter Number of vertices:\n";
cin>>m;
cout<<"\n EDGES \n";
for(k=1;k<=m;k++)
cin>>i;
cout<<"-->";
cin>>j;
cost[i][j]=1;
cout<<" Enter initial vertex:\n";
cin>>v;
cout<<" ORDERED OF VISITED VERTICES\n";
cout<<v<<"-->";
visited[v]=1;
k=1;
while(k<n)
for(j=n;j>=1;j--)
if(cost[v][j]!=0&&visited[j]!=1&&visit[j]!=1)
visit[j]=1;
stk[top]=j;
top++;
v=stk[--top];
cout<<v<<"-->";
k++;
visit[v]=0;
visited[v]=1;
getch();
OUTPUT:-
Enter number of vertices : 5
Enter number of edges : 5
Edges :
12
13
34
25
53
Initial vertex : 1
Order of visited vertex : 1->2->5->3->4
7) MERGE SORT
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
void merge(int *a,int low,int high,int mid)
{
int i,j,k,temp[20];
i=low;
k=0;
j=mid+1;
while(i<=mid&&j<=high)
{
if(a[i]<a[j])
{
temp[k]=a[i];
k++;
i++;
}
else
{
temp[k]=a[j];
k++;
j++;
}
}
while(i<=mid)
{
temp[k]=a[i];
k++;
i++;
}
while(j<=high)
{
temp[k]=a[j];
k++;
j++;
}
for(i=low;i<=high;i++)
{a[i]=temp[i-low];
}
}
void mergesort(int *a,int low,int high)
{
int mid;
if(low<high)
{
mid=(low+high)/2;
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,high,mid);
}
}
void main()
{
int n,i;
clrscr();
cout<<"enter the no of elements:";
cin>>n;
int arr[5];
for(i=0;i<n;i++)
{
cout<<"enter element"<<i+1<<":";
cin>>arr[i];
}
mergesort(arr,0,n-1);
cout<<"sorted data:";
for(i=0;i<n;i++)
cout<<"_>"<<arr[i];
getch();
}
OUTPUT:-
Enter the no of elements:5
Enter element1:5
Enter element2:2
Enter element3:7
Enter element4:4
Enter element5:3
Sorted data:->2->3->4->5->->7
8) KNAPSACK PROBLEM USING DYNAMIC PROGRAMMING
#include<iostream.h>
#include<conio.h>
int max(int a,int b)
return(a>b)?a:b;
int knapsack(int w,int wt[],int val[],int n)
if(n==0||w==0)
return 0;
if(wt[n-1]>w)
return knapsack(w,wt,val,n-1);
else
return max(val[n-1]+knapsack(w-wt[n-1],wt,val,n-
1),knapsack(w,wt,val,n-1));
void main()
clrscr();
int n,w;
cout<<" Enter the number of items in Knapsack:\t";
cin>>n;
int val[10],wt[10];
for(int i=0;i<n;i++)
cout<<" Enter value for item"<<i<<":";
cin>>val[i];
cout<<" Enter weight for item"<<i<<":";
cin>>wt[i];
cout<<" Enter the capacity of Knapsack:";
cin>>w;
cout<<" Total Profit:"<<knapsack(w,wt,val,n);
getch();
}
OUTPUT:-
Enter the number of items in knapsack : 5
Enter value for item 0: 5
Enter weight for item 0: 10
Enter value for item 1: 6
Enter weight for item 1: 20
Enter value for item 2: 7
Enter weight for item 2: 30
Enter value for item 3: 8
Enter weight for item 3: 40
Enter value for item 4: 9
Enter weight for item 4: 10
Enter capacity of knapsack : 100
Total Profit : 30
9) Warshall’s Algorithm using dynamic programming
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#include<stdio.h>
class path
int n;
int p[10][10],a[10][10],c[10][10];
public:
void get();
void pm();
void disp();
};
void path::get()
int i,j,k;
clrscr();
cout<<"enter the no of nodes in the graph:\n";
cin>>n;
cout<<"enter the adjacency matrix:\n";
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
cout<<"a["<<i<<","<<j<<"]=";
cin>>a[i][j];
p[i][j]=0;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
p[i][j]=a[i][j];
void path::disp()
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cout<<p[i][j]<<" ";
cout<<endl;
}
void path::pm()
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
p[i][j]=p[i][j]||p[i][k]&&p[k][j];
void main()
path p;
p.get();
p.pm();
cout<<"path matrix is:";
p.disp();
getch();
}
Output:
Enter no of nodes in the graph:
Enter the adjacency matrix:
a[1,1]=0
a[1,2]=1
a[1,3]=1
a[1,4]=0
a[1,5]=1
a[2,1]=0
a[2,2]=0
a[2,3]=1
a[2,4]=1
a[2,5]=1
a[3,1]=0
a[3,2]=0
a[3,3]=0
a[3,4]=1
a[3,5]=0
a[4,1]=0
a[4,2]=0
a[4,3]=0
a[4,4]=0
a[4,5]=0
a[5,1]=0
a[5,2]=0
a[5,3]=1
a[5,4]=1
a[5,5]=0
path matrix is :
01111
00111
00010
00000
00110
10) Floyd’s Algorithm
#include<iostream.h>
#include<conio.h>
void floyds(int b[10][10],int n)
int i,j,k;
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if((b[i][k]*b[k][j]!=0)&&(i!=j))
if((b[i][k]+b[k][j]<b[k][j])||(b[i][j]==0))
b[i][j]=b[i][k]+b[k][j];
for(i=0;i<n;i++)
{
cout<<"\n Minimum Cost With Respect to Node:"<<i<<endl;
for(j=0;j<n;j++)
cout<<b[i][j]<<"\t";
void main()
int i,j,b[10][10],n;
clrscr();
cout<<" Enter Number of Nodes in the group:";
cin>>n;
cout<<" Enter Values of Adjcency Matrix \n";
for(i=0;i<n;i++)
cout<<" Enter values for"<<(i+1)<<" row"<<endl;
for(j=0;j<n;j++)
cin>>b[i][j];
floyds(b,n);
getch();
Output:
Enter no of nodes:4
Enter values of adjacency matrix
0251
2004
5003
1430
Minimum cost with respect to node 0
0 2 4 1
Minimum cost with respect to node 1
2 0 6 3
Minimum cost with respect to node 2
4 6 0 3
Minimum cost with respect to node 3
1 3 3 0
11) DIJKSTRA’S ALGORITHM USING GREEDY TECHNIQUE
#include<stdio.h>
#include<iostream.h>
#include<conio.h>
#define MAXNODES 50
#define MAX1 150
#define INFINITY 5000
int weight[MAXNODES][MAXNODES],i,j,distance[MAXNODES],visit[MAXNODES];
int precede[MAXNODES],final=0;
int path[MAX1];
int smalldist,newdist,k,s,d,current,n,distcurr;
void display()
i=d;
path[final]=d;
final++;
while(precede[i]!=s)
j=precede[i];
i=j;
path[final]=i;
final++;
path[final]=s;
cout<<"The shortest path is:"<<endl;
for(i=final;i>0;i--)
cout<<"\n("<<path[i]<<"->"<<path[i-1]<<")"<<"with cost="<<weight[path[i]][path[i-1]];
cout<<endl;
cout<<"Total cost="<<distance[d];
void main()
clrscr();
cout<<"Enter the no of nodes :";
cin>>n;
cout<<"Enter the cost matrix :"<<endl;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cin>>weight[i][j];
cout<<"Enter the source node :";
cin>>s;
cout<<"Enter the destination node :";
cin>>d;
for(i=1;i<=n;i++)
distance[i]=INFINITY;
precede[i]=INFINITY;
distance[s]=0;
current=s;
visit[current]=1;
while(current!=d)
distcurr=distance[current];
smalldist=INFINITY;
for(i=1;i<=n;i++)
if(visit[i]==0)
newdist=distcurr+weight[current][i];
if(newdist<distance[i])
distance[i]=newdist;
precede[i]=current;
if(distance[i]<smalldist)
smalldist=distance[i];
k=i;
current=k;
visit[current]=1;
}
display();
getch();
OUTPUT:-
Enter the no of nodes : 4
Enter the cost matrix :
0254
2 0 5000 3
5 5000 0 1
4310
Enter the source node : 2
Enter the destination node : 3
The shortest path is :
2->4with cost=3
4->3with cost=1
Total cost=4
12) PRIM’S ALGORITHM
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
int weight[20][10],visited[20],d[10],p[20];
int v,e;
void creategraph()
int i,j,a,b,w;
cout<<"Enter no of vertices :";
cin>>v;
cout<<"\nEnter no of edges :";
cin>>e;
for(i=1;i<=v;i++)
for(j=1;j<=v;j++)
weight[i][j]=0;
for(i=1;i<=v;i++)
p[i]=visited[i]=0;
d[i]=32767;
for(i=1;i<=e;i++)
cout<<"\nEnter edge a,b and weight w";
cin>>a>>b>>w;
weight[a][b]=weight[b][a]=w;
void prim()
int current,i,totalvisit,mincost;
current=1;
d[current]=0;
totalvisit=1;
visited[current]=1;
while(totalvisit!=v)
for(i=1;i<=v;i++)
if(weight[current][i]!=0)
if(visited[i]==0)
if(d[i]>weight[current][i])
d[i]=weight[current][i];
p[i]=current;
mincost=32767;
for(i=1;i<=v;i++)
{
if(visited[i]==0)
if(d[i]<mincost)
mincost=d[i];
current=i;
visited[current]=1;
totalvisit++;
mincost=0;
for(i=1;i<=v;i++)
mincost+=d[i];
cout<<"\nminimum cost"<<mincost<<endl;
cout<<"\nminimum spanning tree is :"<<endl;
for(i=1;i<=v;i++)
cout<<"vertex"<<i<<"is connected to :"<<p[i]<<endl;
void main()
clrscr();
creategraph();
prim();
getch();
13) N-QUEENS PROBLEM USING BACKTRACKING
#include<iostream.h>
#include<conio.h>
#include<math.h>
int board[20],count;
void print(int n)
int i,j;
cout<<"\n\n solution"<<++count<<":\n";
for(i=1;i<=n;i++)
cout<<"\n\n";
for(j=1;j<=n;++j)
if(board[i]==j)
cout<<"Q";
else
cout<<"X";
int place(int row,int col)
int i;
for(i=1;i<=row-1;i++)
{
if(board[i]==col)
return 0;
else
if(abs(board[i]-col)==abs(i-row))
return 0;
return 1;
void queen(int row,int n)
int col;
for(col=1;col<=n;++col)
if(place(row,col))
board[row]=col;
if(row==n)
print(n);
else
queen(row+1,n);
}
void main()
clrscr();
int n,i,j;
void queen(int row,int n);
cout<<"Enter no of queens : ";
cin>>n;
queen(1,n);
getch();
OUTPUT:-
Enter no of queens : 4
Solution 1:
XQXX
XXXQ
QXXX
XXQX
Solution 2:
XXQX
QXXX
XXXQ
XQXX
