Program to Find LCA [Least Common Ancestor] in C Using Threads & Semaphores [System Programming]
This is the C program to find the lca using threads and semaphores
Given a binary tree (not a binary search tree) and two values say n1 and n2, write a program to find the least common ancestor.
Following is definition of LCA from Wikipedia:
Let T be a rooted tree. The lowest common ancestor between two nodes n1 and n2 is defined as the lowest node in T that has both n1 and n2 as descendants (where we allow a node to be a descendant of itself).
The LCA of n1 and n2 in T is the shared ancestor of n1 and n2 that is located farthest from the root. Computation of lowest common ancestors may be useful, for instance, as part of a procedure for determining the distance between pairs of nodes in a tree: the distance from n1 to n2 can be computed as the distance from the root to n1, plus the distance from the root to n2, minus twice the distance from the root to their lowest common ancestor.
#include<stdio.h>
#include<string.h>
#include<unistd.h>
#include<semaphore.h>
#include<pthread.h>
#include<sys/ipc.h>
#include<sys/shm.h>
#include<sys/types.h>
int a[100];
main()
{
int n,node1,node2,shmid1,shmid2,pid,i;
struct sem_struct
{
sem_t s1;
sem_t s2;
};
struct int_struct
{
int x1;
int x2;
int found;
};
struct sem_struct *buf1,S;
struct int_struct *buf2,X;
shmid1=shmget(10,4096,IPC_CREAT|0666);
shmid2=shmget(16,4096,IPC_CREAT|0666);
printf("Shared Memory ID %d and %dn",shmid1,shmid2);
buf1=shmat(shmid1,0,0);
buf2=shmat(shmid2,0,0);
printf("BUFFER ID %d and %dn",buf1,buf2);
printf("BUFFER VALUE %d and %dn",&buf1,&buf2);
sem_init(&S.s1,0,1);
sem_init(&S.s2,0,0);
printf("Enter the Number of nodesn");
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("Enter Node1n");
scanf("%d",&node1);
printf("Enter Node2n");
scanf("%d",&node2);
for(i=0;i<n;i++)
{
if(node1==a[i]) X.x1=i;
if(node2==a[i]) X.x2=i;
}
X.x1++;X.x2++;X.found=0;
memcpy(buf1,&S,sizeof(struct sem_struct));
memcpy(buf2,&X,sizeof(struct int_struct));
pid=fork();
if(pid!=0)
{
while(1)
{
sem_wait(&buf1->s1);
if(buf2->x1==buf2->x2)
{
buf2->found=1;
sem_post(&buf1->s2);
break;
}
else
{
buf2->x1=(buf2->x1)/2;
break;
}
sem_post(&buf1->s2);
}
if(buf2->x1==0) printf("The Common Ancestor is %dn",a[(buf2->x1)]);
else printf("THE COMMON ANCESTOR IS %dn",a[--(buf2->x1)]);
wait(NULL);
}
else
{
while(1)
{
sem_wait(&buf1->s2);
buf2->x2=(buf2->x2)/2;
if(buf2->found==1)
{
sem_post(&buf1->s1);
break;
}
sem_post(&buf1->s1);
}
}
}
Recent Comments