// STACK OPERATIONS
#include<stdio.h>
#include<conio.h>
#define MAX_SIZE 10
void push (int element);
void pop();
void display();
int stack[MAX_SIZE];
int top=-1;
int i;
int main()
{
int choice,element;
clrscr();
do
{
printf("\n\t STACK OPERATION\n");
printf("\n\t******************");
printf("[Link]\n");
printf("[Link]\n");
printf("[Link]\n");
printf("[Link]\n");
printf("\nEnter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter the element to push:");
scanf("%d",&element);
push(element);
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
printf("Exiting the program.\n");
break;
default:
printf("Invalid choice please enter avalid option.\n");
}
} while(choice!=4);
return 0;
}
void push (int element)
{
if(top==MAX_SIZE-1)
{
printf("stack overflow cannot push element.\n");
}
else
{
top++;
stack[top]=element;
printf("%d pushed to the stack.\n",element);
}
}
void pop()
{
if(top==-1)
{
printf("stack undeflow cannot pop element.\n");
}
else
{
printf("%d popped from the stack\n",stack[top]);
top--;
}
}
void display()
{
if(top==-1)
{
printf("stack is empty\n");
}
else
{
printf("Element in the stack are;\n");
for(i=0;i<=top;i++)
{
printf("%d",stack[i]);
}
printf("\n");
}
}
STACK OPERATION
*******************
[Link]
[Link]
[Link]
[Link]
Enter your choice: 1
Enter the element to push : 10
10 pushed to the stack
STACK OPERATION
*******************
[Link]
[Link]
[Link]
[Link]
Enter your choice: 1
Enter the element to push : 20
20 pushed to the stack
STACK OPERATION
*******************
[Link]
[Link]
[Link]
[Link]
Enter your choice: 3
Element in the stack are : 10 20
STACK OPERATION
*******************
[Link]
[Link]
[Link]
[Link]
Enter your choice: 2
20 popped from the stack
STACK OPERATION
*******************
[Link]
[Link]
[Link]
[Link]
Enter your choice: 3
Element in the stack are : 10
// QUEUE OPERATION
#include<stdio.h>
#define MAX_SIZE 10
voidenqueue(int element);
voiddequeue();
void display();
int queue[MAX_SIZE];
int front=-1,rear=-1;
int i;
int main()
{
int choice,element;
clrscr();
do
{
printf("\n\t QUEUE OPERATIONS");
printf("\n\t ******************\n");
printf("[Link]\n");
printf("[Link]\n");
printf("[Link]\n");
printf("[Link]\n");
printf("Enter your choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
printf("Enter the element to inserted:");
scanf("%d",&element);
enqueue(element);
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
printf("Exiting the program.\n");
break;
default:
printf("Invalid choice,please enter a valid operations.\n");
}
}
while(choice!=4);
return 0;
getch();
}
voidenqueue(int element)
{
if(rear==MAX_SIZE-1)
{
printf("Queue overflow cannot enqueue element.\n");
}
else
{
if(front==-1)
{
front=0;
}
rear++;
queue[rear]=element;
printf("%d enqueued to the queue.\n",element);
}
}
voiddequeue()
{
if(front==-1)
{
printf("Queue underflow cannot dequeue element.\n");
}
else
{
printf("%d Dequeued from the queue.\n",queue[front]);
if(front==rear)
{
front=rear=-1;
}
else
{
front++;
}
}
}
void display()
{
if(front==-1)
{
printf("Queue is empty\n");
}
else
{
printf("element in the queue are:\n");
for(i=front;i<=rear;i++)
{
printf("%d",queue[i]);
}
printf("\n");
}
}
QUEUE OPERATIONS
********************
[Link]
[Link]
[Link]
[Link]
Enter your choice: 1
Enter the element to inserted : 10
10 enqueued to the queue.
QUEUE OPERATIONS
********************
[Link]
[Link]
[Link]
[Link]
Enter your choice: 1
Enter the element to inserted : 20
10 enqueued to the queue.
QUEUE OPERATIONS
********************
[Link]
[Link]
[Link]
[Link]
Enter your choice: 3
Element in the queue. 10 20
QUEUE OPERATIONS
********************
[Link]
[Link]
[Link]
[Link]
Enter your choice: 2
10 Dequeued from the queue
// TREE TRAVERSAL
#include<stdio.h>
#include<conio.h>
struct treenode
{
int data;
struct treenode *left,*right;
};
struct treenode *createnode(int data)
{
struct treenode *newnode=(struct treenode*)malloc(sizeof(struct treenode));
newnode->data=data;
newnode->left=newnode->right=NULL;
returnnewnode;
};
struct treenode *insertnode(structtreenode *root,int data)
{
if(root==NULL)
return createnode(data);
if(data<root->data)
root->left=insertnode(root->left,data);
else if(data>root->data)
root->right=insertnode(root->right,data);
return root;
};
void inorder(struct treenode *root)
{
if(root!=NULL)
{
inorder(root->left);
printf("\n%d",root->data);
inorder(root->right);
}
}
void preorder(struct treenode *root)
{
if(root!=NULL)
{
printf("\n%d",root->data);
preorder(root->left);
preorder(root->right);
}
}
void postorder(struct treenode *root)
{
if(root!=NULL)
{
postorder(root->left);
postorder(root->right);
printf("\n%d",root->data);
}
}
int main()
{
struct treenode *root=NULL;
root=insertnode(root,20);
insertnode(root,10);
insertnode(root,30);
insertnode(root,5);
insertnode(root,15);
clrscr();
printf("\n\tTREE TRAVERSAL");
printf("\n\t***************");
printf("\n\tINORDER");
inorder(root);
printf("\n");
printf("\n\tPREORDER");
preorder(root);
printf("\n");
printf("\n\POSTORDER");
postorder(root);
printf("\n");
return 0;
}
TREE TRAVERSAL
******************
INORDER
5
10
15
20
30
PREORDER
10
20
5
15
30
POST ORDER
5
15
10
30
20
// LINEAR SEARCH
#include<stdio.h>
int main()
{
Int n,selement;
int found=0,i;
int arr[10];
clrscr();
printf("\n\tLINEAR SEARCH");
printf("\n\t**************");
printf("\nEnter the size of the array:");
scanf("%d",&n);
printf("Enter the array elements:\n");
for(i=0;i<=n;i++)
{
scanf("%d",&arr[i]);
}
printf("\nEnter the element to be searched:");
scanf("%d",&selement);
for(i=0;i<n;i++)
{
if(arr[i]==selement)
{
found=1;
break;
}
}
if(found)
{
printf("Element found at index %d\n",i);
}
else
{
printf("Element not found in the array\n");
}
return 0;
getch();
}
LINEAR SEARCH
*****************
Enter the size of the array: 5
Enter the array elements:
10
20
30
40
50
Enter the element to be searched: 30
Element found at index 2.
//BINARY SEARCH
#include<stdio.h>
#include<math.h>
#include<conio.h>
int main()
{
int n,selement,found=0;
int i;
int low=0,high,mid;
intarr[10];
clrscr();
printf("\n\tBINARY SEARCH");
printf("\n\t**************");
printf("\n\t Enter the size of the array");
scanf("%d",&n);
printf("\n\tEnter the sorted array elements");
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
printf("\n\tEnter the element to be searched");
scanf("%d",&selement);
high=n-1;
low=0;
while(low<=high)
{
mid=(low+high)/2;
if(arr[mid]==selement)
{
found=1;
break;
}
else if(arr[mid]<selement)
{
low=mid+1;
}
else
{
high=mid-1;
}
}
if(found)
{
printf("\n\tElement found at index %d\n",mid);
}
else
{
printf("\n\tElement not found in the array");
}
return 0;
}
BINARY SEARCH
******************
Enter the size of the array 5
Enter the stored array elements
Enter the element to be searched
Element found at index 2
// MERGE SORT
#include<stdio.h>
#include<conio.h>
void merge(int arr[],int left,int mid,int right)
{
int n1=mid-left+1;
int n2=right-mid;
int l[10],r[10];
inti,j,k;
for(i=0;i<n1;i++)
l[i]=arr[left+i];
for(j=0;j<n2;j++)
r[j]=arr[mid+1+j];
i=0,j=0,k=left;
while(i<n1 && j<n2)
arr[k++]=(l[i]<=r[j])?l[i++]:r[j++];
while(i<n1)
arr[k++]=l[i++];
while(j<n2)
arr[k++]=r[j++];
}
void mergesort(int arr[],int left,int right)
{
if(left<right)
{
int mid=left+(right-left)/2;
mergesort(arr,left,mid);
mergesort(arr,mid+1,right);
merge(arr,left,mid,right);
}
}
void printarray(int arr[],int size)
{
int i;
for(i=0;i<size;i++)
printf("\n%d",arr[i]);
printf("\n");
}
int main()
{
int arr[]={12,11,13,5,6,7};
int arrsize=sizeof(arr)/sizeof(arr[0]);
clrscr();
printf("\n\tMERGE SORT");
printf("\n\t************");
printf("\n\tGIVEN ARRRAY");
printarray(arr,arrsize);
mergesort(arr,0,arrsize-1);
printf("\n\tSORTED ARRAY");
printarray(arr,arrsize);
return 0;
}
MERGE SORT
**************
GIVEN ARRAY
12
11
13
SORTED ARRAY
*****************
11
12
13
// QUICK SORT
#include<stdio.h>
#include<conio.h>
#include<math.h>
void swap(int *a,int *b)
{
int t=*a;
*a=*b;
*b=t;
}
int partition(int arr[],int low,int high)
{
int j;
int pivot=arr[high];
int i=low-1;
for(j=low;j<=high-1;j++)
{
if(arr[j]<pivot)
{
i++;
swap(&arr[i],&arr[j]);
}
}
swap(&arr[i+1],&arr[high]);
return(i+1);
}
void quicksort(int arr[],int low,int high)
{
if(low<high)
{
int pi=partition(arr,low,high);
quicksort(arr,low,pi-1);
quicksort(arr,pi+1,high);
}
}
void printarray(int arr[],int size)
{
int i;
for(i=0;i<size;i++)
printf("\n%d",arr[i]);
printf("\n");
}
int main()
{
intarr[]= { 12,17,6,25,5 };
int n=sizeof(arr);
clrscr();
printf("\n\tQUICK SORT");
printf("\n\t************");
printf("\n\tUNSORTED ARRAY");
printarray(arr,n);
quicksort(arr,0,n-1);
printf("\n\tSORTED ARRAY");
printarray(arr,n);
return 0;
getch();
}
QUICK SORT
************
UNSORTED ARRAY
12
17
6
25
5
SORTED ARRAY
5
6
12
17
25
// FIND THE KTH SMALLEST ELEMENT
#include<stdio.h>
#include<stdlib.h>
voidselectionSort(intarr[],int n)
{
inti,j,minIndex,temp;
for(i=0;i<n-1;i++)
{
minIndex=i;
for(j=i+1;j<n;j++)
{
if(arr[j]<arr[minIndex])
minIndex=j;
}
temp=arr[minIndex];
arr[minIndex]=arr[i];
arr[i]=temp;
}
}
intkthSmallest(intarr[],intn,int k)
{
int i;
if(k<1||k>n)
{
printf("\nInvalid value ofK.K should be between 1 and %d.\n",n);
return-1;
}
selectionSort(arr,n);
printf("\n\tFIND THE SMALLEST ELEMENT ");
printf("\n\t************************");
printf("\nSorted array:");
for(i=0; i<n; i++)
printf("\n\t%d", arr[i]);
printf("\n");
returnarr[k-1];
}
int main()
{
intarr[]={12, 11, 13, 5, 6};
intarr_size=sizeof(arr)/sizeof(arr[0]);
int K=2;
int result=kthSmallest(arr,arr_size,K);
if(result!=-1)
printf("The%dth smallest element is:%d\n",K,result);
return 0;
}
FIND THE KTH SMALLEST ELEMENT
******************************
SORTED ARRAY
11
12
13
The 2nd smallest element is : 6
#include <stdio.h>
#include <stdlib.h>
struct Item
{
int value;
int weight;
};
int compare(const void* a, const void* b)
{
doubleratioA = ((struct Item*)a)->value / (double)((struct Item*)a)->weight;
doubleratioB = ((struct Item*)b)->value / (double)((struct Item*)b)->weight;
return (ratioB>ratioA) ? 1 : -1;
}
voidknapsackGreedy(struct Item items[], int n, int capacity)
{
qsort(items, n, sizeof(struct Item), compare);
intcurrentWeight = 0;
doubletotalValue = 0.0;
for (int i = 0; i < n; i++)
{
if (currentWeight + items[i].weight <= capacity)
{
currentWeight += items[i].weight;
totalValue += items[i].value;
}
else
{
double fraction = (double)(capacity - currentWeight) / items[i].weight;
currentWeight += fraction * items[i].weight;
totalValue += fraction * items[i].value;
break;
}
}
printf("Optimal value in Knapsack: %.2lf\n", totalValue);
}
int main()
{
struct Item items[] = {{60, 10}, {100, 20}, {120, 30}};
int n = sizeof(items) / sizeof(items[0]);
int capacity = 50;
knapsackGreedy(items, n, capacity);
return 0;
}
OUTPUT
Optimal value in Knapsack: 240.00
// FIND THE ALL PAIRS SHORTEST PATH PROBLEM USING DYNAMICS
PROGRAMMING
#include<stdio.h>
#include<stdio.h>
#include<conio.h>
int min(int,int);
voidfloyds(int p[10][10],int n)
{
inti,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j)
p[i][j]=0;
else
p[i][j]=min(p[i][j],p[i][k]+p[k][j]);
}
int min(inta,int b)
{
if(a<b)
return(a);
else
return(b);
}
void main()
{
int p[10][10];
intw,n,e,u,v,i,j;
clrscr();
printf("\n\n\t FIND THE SHORTEST PATH USING DYNAMICS
PROGRAMMING");
printf("\n\t\t**************************************************");
printf("\n\t Enter the number of vertices");
scanf("%d",&n);
printf("\n\tEnter the number of edges");
scanf("%d",&e);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
p[i][j]=999;
}
for(i=1;i<=e;i++)
{
printf("\n\t Enter the end vertices of edge %d with its weight",i);
scanf("%d%d%d",&u,&v,&w);
p[u][v]=w;
}
printf("\n\t MATRIX INPUT DATA");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("\n%d\t",p[i][j]);
printf("\n");
}
floyds(p,n);
printf("\n TRANSITIVE CLOSURE");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d\t", p[i][j]);
printf("\n");
}
printf("\n\tShortest paths are:");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i!=j)
printf("\n<%d, %d>=%d",i,j,p[i][j]);
}
getch();
}
FIND THE SHORTEST PATH USING DYNAMICS PROGRAMMING
*************************************************************
Enter the vertices 3
Enter the edges 3
Enter the end vertices of edge 1 with its weight
1
2
40
Enter the end vertices of edge 2 with its weight
2
3
30
Enter the end vertices of edge 3 with its weight
3
2
50
MATRIX INPUT DATA
*********************
999
40
999
999
999
30
999
999
999
TRANSITIVE CLOUSURE
0 40 70
999 0 30
999 999 0
// TRAVELLING SALESMAN PROBLEM
#include<stdio.h>
Int ary[10][10],completed[10],n,cost=0;
voidtakeInput()
{
int i,j;
printf("Enter the number of villages: ");
scanf("%d",&n);
printf("\nEnter the Cost Matrix\n");
for(i=0;i <n;i++)
{
printf("\nEnter Elements of Row: %d\n",i+1);
for( j=0;j <n;j++)
scanf("%d",&ary[i][j]);
completed[i]=0;
}
printf("\n\nThe cost list is:");
for( i=0;i <n;i++)
{
printf("\n");
for(j=0;j <n;j++)
printf("\t%d",ary[i][j]);
}
}
voidmincost(int city)
{
int i,ncity;
completed[city]=1;
printf("%d--->",city+1);
ncity=least(city);
if(ncity==999)
{
ncity=0;
printf("%d",ncity+1);
cost+=ary[city][ncity];
return;
}
mincost(ncity);
}
int least(int c)
{
Inti, nc=999;
int min=999,kmin;
for(i=0;i <n;i++)
{
if((ary[c][i]!=0)&&(completed[i]==0))
if(ary[c][i]+ary[i][c] < min)
{
min=ary[i][0]+ary[c][i];
kmin=ary[c][i];
nc=i;
}
}
if(min!=999)
cost+=kmin;
returnnc;
}
int main()
{
takeInput();
printf("\n\nThe Path is:\n");
mincost(0); //passing 0 because starting vertex
printf("\n\nMinimum cost is %d\n ",cost);
return 0;
}
TRAVELLING SALESMAN PROBLEM
Enter elements of row : 1
0 41 3
Enter elements of row : 2
1 2 0 5
Enter the element of row : 3
4 0 2 1
Enter the element of row : 4
3 1 5 0
The cost list is :
0 4 1 3
1 2 0 5
4 0 2 1
3 1 5 0
The path is :
12431
Minimum cost is 18
// N QUEEN PROBLEM
#include<stdio.h>
#include<conio.h>
#include<math.h>
int board[20],count=0;
int main()
{
int n,i,j;
void queen(int row,int n);
clrscr();
printf("\n\tN QUEEN PROBLEM USING BACKTARACKING");
printf("\n\t************************************");
printf("\n\tEnter the number of queens");
scanf("%d",&n);
queen(1,n);
return 0;
getch();
}
void print(int n)
{
int i,j;
printf("\n\nSolution%d:\n\n",++count);
for(i=1;i<=n;++i)
printf("\t%d",i);
printf("\n\t%d",i);
for(i=1;i<=n;++i)
{
printf("\n\n%d",i);
for(j=1;j<=n;++j)
{
if(board[i]==j)
printf("\tQ");
else
printf("\t-");
}
}
}
int place(int row, int column)
{
int i;
for(i=1;i<=row-1;++i)
{
if(board[i]==column)
return 0;
else
if(abs(board[i]-column)==abs(i-row))
return 0;
}
return 1;
}
void queen(int row, int n)
{
int column;
for(column=1;column<=n;++column)
{
if(place(row,column))
{
board[row]=column;
if(row==n)
print(n);
else
queen(row+1,n);
}
}
}
N QUEEN PROBLEM USING BACK TRACKING
******************************************
Enter the number of queens : 4
Solution 1 :
1 2 3 4
1 - Q - -
2 - - - Q
3 Q - - -
4 - - Q -
Solution 2 :
1 2 3 4
1 - - Q -
2 Q - - -
3 - - - Q
4 - Q - -
// HAMILTONIAN CYCLE USING BACK TRACKING
#include<stdio.h>
#include<stdlib.h>
#define V 5
voidprintSolution(int path[]);
//intgraph[10][10];
intisSafe(intv,int graph[V][V],int path[],intpos)
{
int i;
if(graph[path[pos-1]][v] == 0)
return 0;
for(i=0;i<pos;i++)
if(path[i] == v)
return 0;
return 1;
}
inthamCycleUtil(int graph[V][V],int path[],intpos)
{
int v;
if(pos == V)
{
if(graph[path[pos-1]][path[0]] == 1)
return 1;
else
return 0;
}
for(v=1;v<V;v++)
{
if(isSafe(v,graph,path,pos))
{
path[pos] = v;
if(hamCycleUtil(graph,path,pos + 1) == 1)
return 1;
path[pos] = -1;
}
}
return 0;
}
inthamCycle(int graph[V][V])
{
int *path[V];
int i;
for(i=0;i<V;i++)
path[i] = -1;
path[0] = 0;
if(hamCycleUtil(graph,path,1)==0)
{
printf("\nSolution does not exist");
return 0;
}
printSolution(path);
return 1;
}
voidprintSolution(int path[])
{
int i;
printf("\nSolution Exists:"
"\nFollowing is one Hamiltonian Cycle \n");
for(i=0;i<V;i++)
printf("%d",path[i]);
printf("%d",path[0]);
printf("\n");
}
int main()
{
int graph1[V][V] = {{0,1,0,1,0},{1,0,1,1,1},{0,1,0,0,1},{1,1,0,0,1},{0,1,1,1,0},};
int graph2[V][V] = {{0,1,0,1,0},{1,0,1,1,1},{0,1,0,0,1},{1,1,0,0,0},{0,1,1,0,0},};
clrscr();
printf("\n\tHAMILTONIAN CYCLE");
printf("\n\t******************");
hamCycle(graph1);
hamCycle(graph2);
return 0;
}
HAMILTONIAN CYCLE
***********************
Solution Exists:
Following is one Hamiltonian Cycle
0 1 2 4 3 0
Solution does not exists
INDEX
DATA
STRUCTURES AND
ALGORITHMS
INDEX
S.N PAGE
DATE PROGRAM NAME
o No
1 PERFORM STACK OPERATIONS
2 PERFORM QUEUE OPERATIONS
3 PERFORM TREE TRAVERSAL OPERATIONS
SEARCH AN ELEMENT IN AN ARRAY USING
4
LINEAR SEARCH
SEARCH AN ELEMENT IN AN ARRAY USING
5
BINARY SEARCH
SORT THE GIVEN SET OF ELEMENTS USING MERGE
6
SORT
SORT THE GIVEN SET OF ELEMENTS USING QUICK
7
SORT
SEARCH THE KTH SMALLEST ELEMENT USING
8
SELECTION SORT
FIND THE OPTIMAL SOLUTION FOR THE GIVEN
9
KNAPSACK PROBLEM USING GREEDY METHOD
FIND ALL PAIRS SHORTEST PATH FOR THE
10 GIVEN GRAPH USING DYNAMIC PROGRAMMING
METHOD
FIND ALL PAIRS SHORTEST PATH FOR THE GIVEN
11 TRAVELING SALESMAN USING DYNAMIC
PROGRAMMING METHOD
FIND ALL POSSIBLE SOLUTION FOR N QUEEN
12
PROBLEM USING BACK TRACKING
FIND ALL POSSIBLE HAMILTONIAN CYCLE FOR
13
GIVEN GRAPH USING BACK TRACKING