Untitled
unknown
plain_text
4 years ago
13 kB
8
Indexable
// 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; }
Editor is loading...