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