#include #include #include #include typedef struct _node { double x, y; struct _node *next; } node; typedef node *nodePointer; typedef nodePointer **hashTable; #define NSRCH 10 /* Create an m x m hash table of n randomly generated points */ hashTable genRandomPoints ( int n, int m ) { int i, j, k; double x, y; hashTable H; nodePointer p; /* First create an m x m array of list headers */ H = (nodePointer **)malloc(m * sizeof(nodePointer *)); for (i=0; i x = x; p -> y = y; p -> next = H[i][j]; H[i][j] = p; } return H; } /* Print statistics for the hash table of n points */ void getHashStatus ( hashTable H, int n, int m ) { int *freq, i, j, k, max, min; nodePointer p; max = -1; min = n + 1; /* freq[i] stores the number of lists with exactly i entries. In the worst case, a list may be as long as containing all the input points. */ freq = (int *)malloc((n+1) * sizeof(int)); for (i=0; i<=n; ++i) freq[i] = 0; for (i=0; i next; } ++freq[k]; if (k > max) max = k; if (k < min) min = k; } printf("Minimum number of points in a cell = %d\n", min); printf("Maximum number of points in a cell = %d\n", max); for (k=min; k<=max; ++k) if (freq[k] > 0) printf("\t%d cells with %d points\n", freq[k], k); free(freq); } /* This is the search primitive in a cell with the following parameters. H is the m x m hash table storing n entries. Search needs to be carried out in the (i,j)-th list. The query point is (x,y). min stores the current minimum distance from (x,y) to an input point stored in (*X,*Y). If a closer point is located in the (i,j)-th cell, min, *X and *Y are updated. */ double searchCell ( hashTable H, int m, int i, int j, double x, double y, double min, double *X, double *Y ) { nodePointer p; double dist; /* If (i,j) is not a valid cell in the m x m hash table, do nothing */ if ((i < 0) || (i >= m) || (j < 0) || (j >= m)) return min; /* Otherwise, find the distance between the query point and each point in the current cell. If a point closer than thecurrent minimum is located, update min, *X and *Y accordingly. */ p = H[i][j]; while (p != NULL) { dist = sqrt((x - p->x)*(x - p->x) + (y - p->y)*(y - p->y)); if (dist < min) { min = dist; *X = p -> x; *Y = p -> y; } p = p -> next; } return min; } /* This is the search function for finding the closest point. H is the m x m hash table storing n elements. The query point is (x,y). */ void findClosest ( hashTable H, int n, int m, double x, double y ) { int i, j, r, s, t; double min = 2, X, Y; /* First, locate the cell (s,t) to which the query point (x,y) belongs */ s = (int)(x * (double)m); t = (int)(y * (double)m); /* Search in gradually expanding squares centered at (s,t) */ r = 0; X = Y = -1; while (1) { /* At this point, the subsquare corresponding to r-1 is already processed. It is now necessary to process only the outermost layer in the search square for the current value of r. */ for (i=s-r; i<=s+r; ++i) min = searchCell(H,m,i,t-r,x,y,min,&X,&Y); /* Bottom side of the square */ for (i=s-r; i<=s+r; ++i) min = searchCell(H,m,i,t+r,x,y,min,&X,&Y); /* Top side of the square */ for (j=t-r+1; j s+r) { for (j=(y-min)*m; j<=(y+min)*m; ++j) min = searchCell(H,m,i,j,x,y,min,&X,&Y); --i; } j = (int)((y - min) * (double)m); /* This is the bottommost j to be considered */ while (j < t-r) { for (i=s-r; i<=s+r; ++i) min = searchCell(H,m,i,j,x,y,min,&X,&Y); ++j; } j = (int)((y + min) * (double)m); /* This is the topmost j to be considered */ while (j > t+r) { for (i=s-r; i<=s+r; ++i) min = searchCell(H,m,i,j,x,y,min,&X,&Y); --j; } printf("\tThe correct result is (%7.5lf,%7.5lf)\n", X, Y); } /* Free all dynamically allocated memory*/ void windUp ( hashTable H, int m ) { int i, j; nodePointer p, q; for (i=0; i next; free(p); p = q; } } free(H[i]); } free(H); } int main ( int argc, char *argv[] ) { int n, m, i; hashTable H; double x, y; srand((unsigned int)time(NULL)); if (argc >= 2) n = atoi(argv[1]); else { printf("n = "); scanf("%d", &n); } /* Set m to the ceiling of the square root of n */ m = (int)sqrt(n); if (n != m * m) ++m; /* Populate the m x m hash table with n points */ H = genRandomPoints(n,m); /* Print the statistics of the hash table */ getHashStatus(H,n,m); /* Loop for search of query points */ for (i=0; i