ADS Practice Programs
Disclaimer
The information provided by Yagnesh-ADS Blog ("we," "us", or "our") on https://yagnesh-ads.blogspot.com/ (the "Blog") is for general informational purposes only. All information on the Blog is provided in good faith, however we make no representation or warranty of any kind, express or implied, regarding the accuracy, adequacy, validity, reliability, availability or completeness of any information on the Blog. UNDER NO CIRCUMSTANCE SHALL WE HAVE ANY LIABILITY TO YOU FOR ANY LOSS OR DAMAGE OF ANY KIND INCURRED AS A RESULT OF THE USE OF THE BLOG OR RELIANCE ON ANY INFORMATION PROVIDED ON THE BLOG. YOUR USE OF THE BLOG AND YOUR RELIANCE ON ANY INFORMATION ON THE BLOG IS SOLELY AT YOUR OWN RISK.
Note: Try Not to Copy the Code. This Blog or the Blog owner is not responsible for any Malpractice activities.
BST
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *left;
struct Node *right;
};
struct Node* createNode(int data)
{
struct Node *temp=(struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->left = NULL;
temp->right= NULL;
return temp;
}
struct Node* insert(struct Node* node, int data)
{
if(node==NULL)
return createNode(data);
else if(data<node->data)
node->left = insert(node->left, data);
else if(data>node->data)
node->right = insert(node->right,data);
return node;
}
int Height(struct 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);
}
}
int main()
{
struct Node *root=NULL;
int i,info,N,q;
scanf("%d",&q);
for(i=0;i<q;i++)
{
scanf("%d",&N);
if(N==0)
{
scanf("%d",&info);
root=insert(root,info);
}
else if(N==1)
{
if(Height(root)==0)
{
printf("-1\n");
}
else
{
printf("%d\n",Height(root));
}
}
}
return 0;
}
Min Heap
#include <stdio.h>
int size = 0;
void swap(int *a, int *b)
{
int temp = *b;
*b = *a;
*a = temp;
}
void heapify(int array[], int size, int i)
{
{
int smallest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < size && array[l] < array[i])
smallest = l;
if (r < size && array[r] < array[smallest])
smallest = r;
if (smallest != i)
{
swap(&array[i], &array[smallest]);
heapify(array, size, smallest);
}
}
}
void insert(int array[], int newNum)
{
if (size == 0)
{
array[0] = newNum;
size += 1;
}
else
{
array[size] = newNum;
size += 1;
for (int i = size / 2 - 1; i >= 0; i--)
{
heapify(array, size, i);
}
}
}
void deleteRoot(int array[])
{
int i;
array[0]=array[size-1];
size -= 1;
heapify(array,size,0);
}
void printArray(int array[], int size)
{
for (int i = 0; i < size; ++i)
printf("%d ", array[i]);
printf("\n");
}
int main()
{
int array[1000];
int q,i,num,cho;
scanf("%d",&q);
for(i=0;i<q;i++)
{
scanf("%d",&cho);
if(cho==1)
{
scanf("%d",&num);
insert(array,num);
}
else if(cho==2)
{
deleteRoot(array);
}
else if(cho==3)
{
printf("%d\n",size);
}
else if(cho==4)
{
printf("%d\n",array[0]);
}
}
}
AVL Tree Insertion
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int key;
struct Node *left;
struct Node *right;
int height;
};
int max(int a, int b);
int height(struct Node *N)
{
if (N == NULL)
return 0;
return N->height;
}
int max(int a, int b)
{
return (a > b)? a : b;
}
struct Node* newNode(int key)
{
struct Node* node = (struct Node*)
malloc(sizeof(struct Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
return(node);
}
struct Node *rightRotate(struct Node *y)
{
struct Node *x = y->left;
struct Node *T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right))+1;
x->height = max(height(x->left), height(x->right))+1;
return x;
}
struct Node *leftRotate(struct Node *x)
{
struct Node *y = x->right;
struct Node *T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right))+1;
y->height = max(height(y->left), height(y->right))+1;
return y;
}
int getBalance(struct Node *N)
{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}
struct Node* insert(struct Node* node, int key)
{
if (node == NULL)
return(newNode(key));
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else
return node;
node->height = 1 + max(height(node->left),height(node->right));
int balance = getBalance(node);
if (balance > 1 && key < node->left->key)
return rightRotate(node);
if (balance < -1 && key > node->right->key)
return leftRotate(node);
if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
void preOrder(struct Node *root)
{
if(root != NULL)
{
printf("%d ", root->key);
preOrder(root->left);
preOrder(root->right);
}
}
void postOrder(struct Node* node)
{
if (node == NULL)
return;
postOrder(node->left);
postOrder(node->right);
printf("%d ", node->key);
}
void inOrder(struct Node* node)
{
if (node == NULL)
return;
inOrder(node->left);
printf("%d ", node->key);
inOrder(node->right);
}
int main()
{
struct Node *root = NULL;
int q,i,num;
scanf("%d",&q);
for(i=0;i<q;i++)
{
scanf("%d",&num);
root = insert(root,num);
}
inOrder(root);
printf("\n");
preOrder(root);
printf("\n");
postOrder(root);
return 0;
}
Dijkstra's Algorithm
#include<stdio.h>
#include<stdlib.h>
struct Graph
{
int v;
int adjMat[20][20];
};
struct Graph* createGraph(int n)
{
int i,j;
struct Graph* g=(struct Graph*)malloc(sizeof(struct Graph));
g->v=n;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&g->adjMat[i][j]);
}
}
return g;
}
int minDistance(struct Graph* g,int dist[100],int SPT[100])
{
int i,minIndex,Min=10000;
for(i=0;i<g->v;i++)
{
if(SPT[i]==0&&dist[i]<=Min)
{
Min=dist[i];
minIndex=i;
}
}
return minIndex;
}
void dijkstraAlgo(struct Graph* g,int src,int dest)
{
int i,j,k,TC,dist[g->v],key[g->v],parent[g->v],SPT[g->v];
for(i=0;i<g->v;i++)
{
dist[i]=10000;
SPT[i]=0;
}
dist[src]=0;
parent[0]=-1;
for(i=0;i<g->v-1;i++)
{
j=minDistance(g,dist,SPT);
SPT[j]=1;
for(k=0;k<g->v;k++)
{
if(!SPT[k]&&g->adjMat[j][k]&&dist[j]!=10000&&dist[j]+g->adjMat[j][k]<dist[k])
{
parent[k]=j;
key[k]=g->adjMat[j][k];
dist[k]=dist[j]+g->adjMat[j][k];
}
}
}
printf("%d\n",dist[dest]);
}
int main()
{
int n,q,i,src,dest;
scanf("%d",&n);
struct Graph* g=createGraph(n);
scanf("%d",&q);
for(i=0;i<q;i++)
{
scanf("%d%d",&src,&dest);
dijkstraAlgo(g,src,dest);
}
return 0;
}
Minimum Spanning Tree
#include<stdio.h>
#include<stdlib.h>
struct Graph
{
int v;
int e;
int adjMat[20][20];
};
struct Graph* createGraph(int v,int e)
{
int i,j,src,dest,weight;
struct Graph* g=(struct Graph*)malloc(sizeof(struct Graph));
g->v=v;
g->e=e;
for(i=0;i<v;i++)
{
for(j=0;j<v;j++)
{
g->adjMat[i][j]=0;
}
}
return g;
}
void insertEdges(struct Graph* g)
{
int i,src,dest,weight;
//printf("\n Enter Source and Destination Vertices for each edge: ");
i=0;
while(i<g->e)
{
//printf("\n Edge %d : ",i+1);
//printf("\n Source Vertex : ");
scanf("%d",&src);
//printf(" Destination Vertex : ");
scanf("%d",&dest);
if(src>g->v||dest>g->v)
{
printf("\n Vertex does not exists! Enter Again! \n");
}
else if(g->adjMat[src][dest]>0)
{
printf("\n Edge already exists! Enter Again! \n");
}
else
{
//printf(" Enter Weight : ");
scanf("%d",&weight);
g->adjMat[src][dest]=weight;
g->adjMat[dest][src]=weight;
i++;
}
}
}
void displayGraph(struct Graph* g)
{
int i,j;
printf("\n Adjacency Matrix Representation : \n");
for(i=0;i<g->v;i++)
{
printf("\n");
for(j=0;j<g->v;j++)
{
printf(" %d",g->adjMat[i][j]);
}
}
printf("\n");
}
int minKey(struct Graph* g,int key[100],int mstSet[100])
{
int i,minIndex,Min=10000;
for(i=0;i<g->v;i++)
{
if(mstSet[i]==0&&key[i]<Min)
{
Min=key[i];
minIndex=i;
}
}
return minIndex;
}
void primsMST(struct Graph* g)
{
int i,TC,dest,src,parent[g->v],key[g->v], mstSet[g->v];
for(i=0;i<g->v;i++)
{
key[i]=10000;
mstSet[i]=0;
}
key[0]=0;
parent[0]=-1;
for(i=0;i<g->v-1;i++)
{
src=minKey(g,key,mstSet);
mstSet[src]=1;
for(dest=0;dest<g->v;dest++)
{
if(g->adjMat[src][dest]!=0&&mstSet[dest]==0&&g->adjMat[src][dest]<key[dest])
{
parent[dest]=src;
key[dest]=g->adjMat[src][dest];
}
}
}
//printf("\n Minimum Spanning Tree: \n");
struct Graph* MST=createGraph(g->v,g->v-1);
TC=0;
for(i=1;i<g->v;i++)
{
MST->adjMat[parent[i]][i]=g->adjMat[i][parent[i]];
MST->adjMat[i][parent[i]]=g->adjMat[i][parent[i]];
TC=TC+g->adjMat[i][parent[i]];
}
//displayGraph(MST);
printf("%d",TC);
}
int main()
{
int v,e;
scanf("%d",&v);
scanf("%d",&e);
struct Graph* g=createGraph(v,e);
insertEdges(g);
primsMST(g);
return 0;
}
Linear Probing
#include <stdio.h>
int main()
{
int n,i,j,q,cho,size,key,flag,Hash_Table[1000],Temp_Table[1000];
scanf("%d",&size);
for(i=0;i<size;i++)
{
Hash_Table[i]=-1;
Temp_Table[i]=-1;
}
scanf("%d",&q);
for(i=0;i<q;i++)
{
scanf("%d",&cho);
if(cho==1)
{
scanf("%d",&key);
n=key%size;
while(Hash_Table[n]!=-1)
{
n++;
if(n>=size)
{
n=0;
}
}
Hash_Table[n]=key;
}
else if(cho==2)
{
scanf("%d",&key);
n=key%size;
flag=1;
while(key!=Hash_Table[n]&&flag==1)
{
n++;
if(n>=size)
{
n=0;
}
if(n==key%size)
{
flag=0;
}
}
if(flag==1)
{
Hash_Table[n]=-1;
for(j=0;j<size;j++)
{
Temp_Table[j]=Hash_Table[j];
Hash_Table[j]=-1;
}
for(j=0;j<size;j++)
{
if(Temp_Table[j]!=-1)
{
n=Temp_Table[j]%size;
while(Hash_Table[n]!=-1)
{
n++;
if(n>=size)
{
n=0;
}
}
Hash_Table[n]=Temp_Table[j];
}
}
}
}
else if(cho==3)
{
for(j=0;j<size;j++)
{
printf("%d ",Hash_Table[j]);
}
printf("\n");
}
}
return 0;
}
Digit Tries
#include<stdio.h>
#include<string.h>
struct Trie
{
int info;
struct Trie* children[10];
int EOD; //End of Digit
};
struct Trie* newNode(int key)
{
int i;
struct Trie* Node=(struct Trie*)malloc(sizeof(struct Trie));
Node->info=key;
for(i=0;i<10;i++)
{
Node->children[i]=NULL;
}
Node->EOD=0;
return Node;
}
void insert(struct Trie* root, char num[100000])
{
struct Trie* temp=root;
for(int i=0;i<strlen(num);i++)
{
int p=num[i]-'0';
if(temp->children[p]!=NULL)
{
temp=temp->children[p];
}
else
{
temp->children[p]=newNode(0);
temp=temp->children[p];
}
}
if(temp->EOD==0)
{
printf("%s\n",num);
}
temp->EOD=1;
}
int main()
{
int n;
struct Trie* root=newNode(0);
scanf("%d",&n);
for(int i=0;i<n;i++)
{
char k[1000];
scanf("%s",k);
insert(root,k);
}
}
The Proposal DFS
#include<stdio.h>
#include<limits.h>
int graph[1001][1001];
int minDist=INT_MAX,id=INT_MAX;
void dfs(int source,int dest,int visited[],int l,int n)
{
visited[source]=1;
if(source==dest)
{
if(minDist>=l)
{
minDist=l;
if(id>source)
{
id=source;
}
}
}
for(int i=0;i<n;i++)
{
if(graph[source][i]==1 && visited[i]==0)
{
dfs(i,dest,visited,l+1,n);
}
}
}
int main()
{
int i,n,u,v,q,a;
for(i=0;i<1001;i++)
{
for(int j=0;j<1001;j++)
{
graph[i][j]=0;
}
}
scanf("%d",&n);
for(i=0;i<n-1;i++)
{
scanf("%d %d",&u,&v);
graph[u][v]=1;
graph[v][u]=1;
}
scanf("%d",&q);
for(i=0;i<q;i++)
{
scanf("%d",&a);
int visited[n+1];
for(i=0;i<=n+1;i++)
{
visited[i]=0;
}
dfs(1,a,visited,0,n+1);
}
printf("%d",id);
return 0;
}
No comments:
Post a Comment