Untitled

// BST

#include <stdio.h>
#include <stdlib.h>

FILE *fptr; // creaing file pointer

// creating a node (root node)
struct Node
{
  struct Node *lchild;
  int data;
  struct Node *rchild;
}*root=NULL; // initializing as null

// creating insert function for binary tree
void Insert(int key)
{
  struct Node *t=root;
  struct Node *r=NULL,*p;
  if(root==NULL)
  {
    p=(struct Node *)malloc(sizeof(struct Node));
    p->data=key;
    p->lchild=p->rchild=NULL;
    root=p;
    return;
  }
  while(t!=NULL)
  {
    r=t;
    if(key<t->data)
    t=t->lchild;
    else if(key>t->data)
    t=t->rchild;
    else
    return;
  }
  p=(struct Node *)malloc(sizeof(struct Node));
  p->data=key;
  p->lchild=p->rchild=NULL;if(key<r->data) r->lchild=p;
  else r->rchild=p;
}

// creating function for tree traversals
void Inorder(struct Node *p)
{
  if(p)
  {
    Inorder(p->lchild);
    printf("%d ",p->data);
    Inorder(p->rchild);
  }
}

// creating a custom inorder function to write result to file
void InorderF(struct Node *p)
{
  if(p)
  {
    InorderF(p->lchild);
    fprintf(fptr,"%d ",p->data);
    InorderF(p->rchild);
  }
}

void Preorder(struct Node *p)
{
  if(p)
  {
    printf("%d ",p->data);
    Preorder(p->lchild);
    Preorder(p->rchild);
  }
}

void Postorder(struct Node *p)
{
  if(p)
  {
    Postorder(p->lchild);
    Postorder(p->rchild);
    printf("%d ",p->data);
  }
}

// driver function (compiler starts processing from main function)
int main() {
   int num; // size of the array

   fptr = fopen("elements.txt","r"); // opening file to read elements

   if(fptr == NULL) // checking if file is empty
   {
      printf("Error!");   
      exit(1);             
   }

   fscanf(fptr,"%d", &num); // reading 1st element of the file (size of the array)

   int arr[num]; // declaring array of num size

   // reading elements from file and storing in the array
   for(int i=0; i< num; i++){
     fscanf(fptr,"%d", &arr[i]);
   }

  // creating binary search tree (inserting elements)
   for(int i=0; i< num; i++){
     Insert(arr[i]);
   }
   
   // calling tree traversal functions to print
   printf("Inorder:\n");
   Inorder(root);
   printf("\n\nPostorder:\n");
   Postorder(root);
   printf("\n\nPreorder:\n");
   Preorder(root);

  // creating a file named results.txt to store the sorted result
   fptr = fopen("results.txt","w+");
   InorderF(root); // calling function to sort the array and store in file

   fclose(fptr); // closing file pointer
  return 0;
}


// BFS and DFS

#ifndef Queue_h
#define Queue_h
#include <stdlib.h>
struct Node
{
int data;
struct Node *next;
}*front=NULL,*rear=NULL;
void enqueue(int x)
{
struct Node *t;
t=(struct Node*)malloc(sizeof(struct Node));
if(t==NULL)
printf("Queue is FUll\n");
else
{
t->data=x;
t->next=NULL;
if(front==NULL)
front=rear=t;
else
{
rear->next=t;
rear=t;
}
}
}
int dequeue()
{
int x=-1;
struct Node* t;
if(front==NULL)
printf("Queue is Empty\n");
else
{
x=front->data;
t=front;front=front->next;
free(t);
}
return x;
}
int isEmpty()
{
return front==NULL;
}
#endif /* Queue_h */
#include <stdio.h>
#include "Queue.h"
void BFS(int G[][7],int start,int n)
{
int i=start,j;
int visited[7]={0};
printf("%d ",i);
visited[i]=1;
enqueue(i);
while(!isEmpty())
{
i=dequeue();
for(j=1;j<n;j++)
{
if(G[i][j]==1 && visited[j]==0)
{
printf("%d ",j);
visited[j]=1;
enqueue(j);
}
}
}
}
void DFS(int G[][7],int start,int n)
{static int visited[7]={0};
int j;
if(visited[start]==0)
{
printf("%d ",start);
visited[start]=1;
for(j=1;j<n;j++)
{
if(G[start][j]==1 && visited[j]==0)
DFS(G,j,n);
}
}
}
int main()
{
int G[7][7]={{0,0,0,0,0,0,0},
{0,0,1,1,0,0,0},
{0,1,0,0,1,0,0},
{0,1,0,0,1,0,0},
{0,0,1,1,0,1,1},
{0,0,0,0,1,0,0},
{0,0,0,0,1,0,0}};
DFS(G,4,7);
return 0;
}


// Bubble sort

#include <stdio.h>
#include<stdlib.h>
void swap(int *x,int *y)
{
int temp=*x;
*x=*y;
*y=temp;
}
void Bubble(int A[],int n)
{
int i,j,flag=0;
for(i=0;i<n-1;i++)
{
flag=0;
for(j=0;j<n-i-1;j++)
{
if(A[j]>A[j+1])
{
swap(&A[j],&A[j+1]);
flag=1;
}
}
if(flag==0)
break;
}
}
int main()
{
int A[]={11,13,7,12,16,9,24,5,10,3},n=10,i;
Bubble(A,n);for(i=0;i<10;i++)
printf("%d ",A[i]);
printf("\n");
return 0;
}

// Selection sort

Selection Sort
#include <stdio.h>
#include<stdlib.h>
void swap(int *x,int *y)
{
int temp=*x;
*x=*y;
*y=temp;
}
void SelectionSort(int A[],int n)
{
int i,j,k;
for(i=0;i<n-1;i++)
{
for(j=k=i;j<n;j++)
{
if(A[j]<A[k])
k=j;
}
swap(&A[i],&A[k]);
}
}
int main()
{
int A[]={11,13,7,12,16,9,24,5,10,3},n=10,i;
SelectionSort(A,n);
for(i=0;i<10;i++)
printf("%d ",A[i]);
printf("\n");
return 0;}

// Insertion Sort

Insertion Sort
#include <stdio.h>
#include<stdlib.h>
void swap(int *x,int *y)
{
int temp=*x;
*x=*y;
*y=temp;
}
void Insertion(int A[],int n)
{
int i,j,x;
for(i=1;i<n;i++)
{
j=i-1;
x=A[i];
while(j>-1 && A[j]>x)
{
A[j+1]=A[j];
j--;
}
A[j+1]=x;
}
}
int main()
{
int A[]={11,13,7,12,16,9,24,5,10,3},n=10,i;
Insertion(A,n);
for(i=0;i<10;i++)
printf("%d ",A[i]);
printf("\n");return 0;
}

// Merge Sort

Merge Sort
#include <stdio.h>
#include<stdlib.h>
void swap(int *x,int *y)
{
int temp=*x;
*x=*y;
*y=temp;
}
void Merge(int A[],int l,int mid,int h)
{
int i=l,j=mid+1,k=l;
int B[100];
while(i<=mid && j<=h)
{
if(A[i]<A[j])
B[k++]=A[i++];
else
B[k++]=A[j++];
}
for(;i<=mid;i++)
B[k++]=A[i];
for(;j<=h;j++)
B[k++]=A[j];
for(i=l;i<=h;i++)
A[i]=B[i];
}
void IMergeSort(int A[],int n)
{
int p,l,h,mid,i;
for(p=2;p<=n;p=p*2)
{for(i=0;i+p-1<=n;i=i+p)
{
l=i;
h=i+p-1;
mid=(l+h)/2;
Merge(A,l,mid,h);
}
}
if(p/2<n)
Merge(A,0,p/2-1,n);
}
int main()
{
int A[]={11,13,7,12,16,9,24,5,10,3},n=10,i;
IMergeSort(A,n);
for(i=0;i<10;i++)
printf("%d ",A[i]);
printf("\n");
return 0;
}


// Quick Sort

Quick Sort
#include <stdio.h>
#include<stdlib.h>
void swap(int *x,int *y)
{
int temp=*x;
*x=*y;
*y=temp;
}
int partition(int A[],int l,int h)
{
int pivot=A[l];
int i=l,j=h;
do
{
do{i++;}while(A[i]<=pivot);
do{j--;}while(A[j]>pivot);
if(i<j)swap(&A[i],&A[j]);
}while(i<j);
swap(&A[l],&A[j]);
return j;
}
void QuickSort(int A[],int l,int h)
{
int j;
if(l<h)
{
j=partition(A,l,h);
QuickSort(A,l,j);
QuickSort(A,j+1,h);
}}
int main()
{
int A[]={11,13,7,12,16,9,24,5,10,3},n=10,i;
QuickSort(A,n);
for(i=0;i<10;i++)
printf("%d ",A[i]);
printf("\n");
return 0;
}


// Dijkstra's algorithm

// A C++ program for Dijkstra's single source shortest path algorithm. 
// The program is for adjacency matrix representation of the graph 

#include <limits.h> 
#include <stdio.h> 

// Number of vertices in the graph 
#define V 9 

// A utility function to find the vertex with minimum distance value, from 
// the set of vertices not yet included in shortest path tree 
int minDistance(int dist[], bool sptSet[]) 
{ 
	// Initialize min value 
	int min = INT_MAX, min_index; 

	for (int v = 0; v < V; v++) 
		if (sptSet[v] == false && dist[v] <= min) 
			min = dist[v], min_index = v; 

	return min_index; 
} 

// A utility function to print the constructed distance array 
void printSolution(int dist[]) 
{ 
	printf("Vertex \t\t Distance from Source\n"); 
	for (int i = 0; i < V; i++) 
		printf("%d \t\t %d\n", i, dist[i]); 
} 

// Function that implements Dijkstra's single source shortest path algorithm 
// for a graph represented using adjacency matrix representation 
void dijkstra(int graph[V][V], int src) 
{ 
	int dist[V]; // The output array. dist[i] will hold the shortest 
	// distance from src to i 

	bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest 
	// path tree or shortest distance from src to i is finalized 

	// Initialize all distances as INFINITE and stpSet[] as false 
	for (int i = 0; i < V; i++) 
		dist[i] = INT_MAX, sptSet[i] = false; 

	// Distance of source vertex from itself is always 0 
	dist[src] = 0; 

	// Find shortest path for all vertices 
	for (int count = 0; count < V - 1; count++) { 
		// Pick the minimum distance vertex from the set of vertices not 
		// yet processed. u is always equal to src in the first iteration. 
		int u = minDistance(dist, sptSet); 

		// Mark the picked vertex as processed 
		sptSet[u] = true; 

		// Update dist value of the adjacent vertices of the picked vertex. 
		for (int v = 0; v < V; v++) 

			// Update dist[v] only if is not in sptSet, there is an edge from 
			// u to v, and total weight of path from src to v through u is 
			// smaller than current value of dist[v] 
			if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX 
				&& dist[u] + graph[u][v] < dist[v]) 
				dist[v] = dist[u] + graph[u][v]; 
	} 

	// print the constructed distance array 
	printSolution(dist); 
} 

// driver program to test above function 
int main() 
{ 
	/* Let us create the example graph discussed above */
	int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, 
						{ 4, 0, 8, 0, 0, 0, 0, 11, 0 }, 
						{ 0, 8, 0, 7, 0, 4, 0, 0, 2 }, 
						{ 0, 0, 7, 0, 9, 14, 0, 0, 0 }, 
						{ 0, 0, 0, 9, 0, 10, 0, 0, 0 }, 
						{ 0, 0, 4, 14, 10, 0, 2, 0, 0 }, 
						{ 0, 0, 0, 0, 0, 2, 0, 1, 6 }, 
						{ 8, 11, 0, 0, 0, 0, 1, 0, 7 }, 
						{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } }; 

	dijkstra(graph, 0); 

	return 0; 
} 


// Kruskal's

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
    int i,j,k,a,b,u,v,n,ne=1;
    int min,mincost=0,cost[9][9],parent[9];
    int find(int);
    int uni(int,int);
    int main()
    {
    	printf("\n\tImplementation of Kruskal's Algorithm\n");
    	printf("\nEnter the no. of vertices:");
    	scanf("%d",&n);
    	printf("\nEnter the cost adjacency matrix:\n");
    	for(i=1;i<=n;i++)
    	{
    	for(j=1;j<=n;j++)
    	{
    	scanf("%d",&cost[i][j]);
    	if(cost[i][j]==0)
    	cost[i][j]=999;
    	}
    	}
    	printf("The edges of Minimum Cost Spanning Tree are\n");
    	while(ne < n)
    	{
    	for(i=1,min=999;i<=n;i++)
    	{
    	for(j=1;j <= n;j++)
    	{
    	if(cost[i][j] < min)
    	{
    	min=cost[i][j];
    	a=u=i;
    	b=v=j;
    	}
    	}
    	}
    	u=find(u);
    	v=find(v);
    	if(uni(u,v))
    	{
    	printf("%d edge (%d,%d) =%d\n",ne++,a,b,min);
    	mincost +=min;
    	}
    	cost[a][b]=cost[b][a]=999;
    	}
    	printf("\n\tMinimum cost = %d\n",mincost);
    	getch();
    }
    int find(int i)
    {
    	while(parent[i])
    	i=parent[i];
    	return i;
    }
    int uni(int i,int j)
    {
    	if(i!=j)
    	{
    	parent[j]=i;
    	return 1;
    	}
    	return 0;
    }


// Floyd's

// C Program for Floyd Warshall Algorithm
#include<stdio.h>

// Number of vertices in the graph
#define V 4

/* Define Infinite as a large enough 
value. This value will be used
for vertices not connected to each other */
#define INF 99999

// A function to print the solution matrix
void printSolution(int dist[][V]);

// Solves the all-pairs shortest path 
// problem using Floyd Warshall algorithm
void floydWarshall (int graph[][V])
{
	/* dist[][] will be the output matrix 
	that will finally have the shortest 
	distances between every pair of vertices */
	int dist[V][V], i, j, k;

	/* Initialize the solution matrix 
	same as input graph matrix. Or 
	we can say the initial values of 
	shortest distances are based
	on shortest paths considering no 
	intermediate vertex. */
	for (i = 0; i < V; i++)
		for (j = 0; j < V; j++)
			dist[i][j] = graph[i][j];

	/* Add all vertices one by one to 
	the set of intermediate vertices.
	---> Before start of an iteration, we 
	have shortest distances between all
	pairs of vertices such that the shortest 
	distances consider only the
	vertices in set {0, 1, 2, .. k-1} as 
	intermediate vertices.
	----> After the end of an iteration, 
	vertex no. k is added to the set of
	intermediate vertices and the set 
	becomes {0, 1, 2, .. k} */
	for (k = 0; k < V; k++)
	{
		// Pick all vertices as source one by one
		for (i = 0; i < V; i++)
		{
			// Pick all vertices as destination for the
			// above picked source
			for (j = 0; j < V; j++)
			{
				// If vertex k is on the shortest path from
				// i to j, then update the value of dist[i][j]
				if (dist[i][k] + dist[k][j] < dist[i][j])
					dist[i][j] = dist[i][k] + dist[k][j];
			}
		}
	}

	// Print the shortest distance matrix
	printSolution(dist);
}

/* A utility function to print solution */
void printSolution(int dist[][V])
{
	printf ("The following matrix shows the shortest distances"
			" between every pair of vertices \n");
	for (int i = 0; i < V; i++)
	{
		for (int j = 0; j < V; j++)
		{
			if (dist[i][j] == INF)
				printf("%7s", "INF");
			else
				printf ("%7d", dist[i][j]);
		}
		printf("\n");
	}
}

// driver program to test above function
int main()
{
	/* Let us create the following weighted graph
			10
	(0)------->(3)
		|		 /|\
	5 |		 |
		|		 | 1
	\|/		 |
	(1)------->(2)
			3		 */
	int graph[V][V] = { {0, 5, INF, 10},
						{INF, 0, 3, INF},
						{INF, INF, 0, 1},
						{INF, INF, INF, 0}
					};

	// Print the solution
	floydWarshall(graph);
	return 0;
}


// Heap Sort

Heap Sort
#include <stdio.h>
void Insert(int A[],int n)
{
int i=n,temp;
temp=A[i];
while(i>1 && temp>A[i/2])
{
A[i]=A[i/2];
i=i/2;
}
A[i]=temp;
}
int Delete(int A[],int n)
{
int i,j,x,temp,val;
val=A[1];
x=A[n];
A[1]=A[n];
A[n]=val;
i=1;j=i*2;
while(j<n-1)
{
if(A[j+1]>A[j])
j=j+1;
if(A[i]<A[j])
{
temp=A[i];
A[i]=A[j];
A[j]=temp;
i=j;
j=2*j;
}
else
break;
}
return val;
}int main()
{
int H[]={0,10,20,30,25,5,40,35};
// 40,25,35,10,5,20,30
int i;
for(i=2;i<=7;i++)
Insert(H,i);
for(i=7;i>1;i--)
{
Delete(H,i);
}
for(i=1;i<=7;i++)
printf("%d ",H[i]);
printf("\n");
return 0;
}