Hashing line segments C Program Code

Below the information to understand the program completely.

Input:
R = a rectangular region with bottom-left corner at (0,0) and top-right corner at (X,Y), X and Y being user-specified.
n = Number of line segments whose endpoints have integer coordinates and lie in R.
Task:  Use hashing to store the line segments one by one in a suitable data structure T. While generating, the two endpoints of each segment should be randomly selected and a newly generated segment should be inserted in T only if it is not already there in T.

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

typedef struct nodetype
{
int x1;
int x2;
int y1;
int y2;
struct nodetype *next;
}node;

node* lastnode(node *);
int findduplicate(node **,int,int,int,int,int);
void display(node **,int);

main()
{
int X,Y,x1,y1,x2,y2,n,i=0,j,c,exist,s=1;
node  **A=NULL,*ptr=NULL,*last=NULL;

printf(“*****************************************************************************\n”);
printf(“\t\tPROGRAM:\tHASHING LINE SEGMENTS\n”);
printf(“\t\tPROGRAMMER:\tKALPATARU MALLICK\n”);
printf(“*****************************************************************************\n”);

printf(“\n Enter the Second co-orinates of the Rectangle as integer value (X,Y) respectively :”);
scanf(“%d%d”,&X,&Y);
printf(“\n Enter the no. of segments must be less than or equals to (Y+1)^2*(Y+1)^2-2(X+1)*(Y+1) :\n”);
scanf(“%d”,&n);

A=(node **)malloc(sizeof(node *)*n);
for(j=0;j<n;j++)
A[j]=NULL;

while(i<n)
{
x1=rand()%(X+1);
y1=rand()%(Y+1);
x2=rand()%(X+1);
y2=rand()%(Y+1);
if((x1!=x2)||(y1!=y2))
{
exist = findduplicate(A,n,x1,x2,y1,y2);
if(exist==0)
{
i++;
ptr=(node *)malloc(sizeof(node));
ptr->next=NULL;

ptr->x1=x1;
ptr->x2=x2;
ptr->y1=y1;
ptr->y2=y2;

c=rand()%n;

if(A[c]==NULL)
{
A[c]=ptr;
}
else
{
last=lastnode(A[c]);
last->next=ptr;
}
}
}
}
printf(“\n\nThe cordinates of all segments are:\n “);
display(A,n);
printf(“\n”);
}

int findduplicate(node **A,int n,int x1,int x2,int y1,int y2)
{
int j;
node *head;
for(j=0;j<n;j++)
{
if (A[j] == NULL)
continue;
head=A[j];
while(head!=NULL)
{
if(((head->x1==x1)&&(head->y1==y1)&&(head->x2==x2)&&(head->y2==y2))||((head->x2==x2)&&(head->y2==y2)&&(head->x1==x1)&&(head->y1==y1)))
{
return 1;
}
head=head->next;
}
}
return 0;
}

node* lastnode(node *head)
{
while(head->next!=NULL)
{
head=head->next;
}
return head;
}

void display(node **A,int n)
{
node *head=NULL;
int k;
if(n==0)
printf(“\n no segments created\n”);
for(k=0;k<n;k++)
{
printf(“\n%d”,k+1);
if(A[k]!=NULL)
{
head=A[k];
while(head!=NULL)
{
printf(“\t(x1=%d”,head->x1);
printf(“\tx2=%d”,head->x2);
printf(“\ty1=%d”,head->y1);
printf(“\ty2=%d)”,head->y2);
head=head->next;
}
}
}
}

Note :The Above code is compiled on a linux environment 


Share your review and thoughts with us 

Comments

Popular posts from this blog

AGRICULTURAL SCIENTIST RECRUITMENT BOARD

HSC Exam Time Table 2013 Arts, Commerce, Science

CIVIL SERVICES' (I.A.S.) EXAMINATION