二维链表数组，程序3.20

 1 #include <math.h>
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 //#include "Point.h"
 5 typedef struct node* link;
 6 
 7 typedef struct {
 8     float x;
 9     float y;
10 } point;
11 
12 
13 struct node { point p;  link next; };
14 link** grid; int G; float d; int cnt = 0;
15 float randFloat()
16 {
17     return 1.0 * rand() / RAND_MAX;
18 }
19 float distance( point a, point b)
20 {
21     float dx = a.x - b.x, dy = a.y - b.y;
22     return sqrt(dx * dx + dy * dy);
23 };
24 
25 link** malloc2d(int  r, int c)
26 {
27     int i;
28     link** t = (link **)malloc(r * sizeof(link*));
29     for(i = 0;i < r;i++)
30     t[i] = (link *)malloc(c * sizeof(link));
31     return t;
32 }
33 
34 
35 void gridinsert(float x, float y)
36 {
37     int i, j; link s;
38     int X = x * G + 1; int Y = y * G + 1;
39     link t = (link)malloc(sizeof * t);
40     t->p.x = x; t->p.y = y;
41     for (i = X - 1; i <= X + 1; i++)
42         for (j = Y - 1; j <= Y + 1; j++)
43             for (s = grid[i][j]; s != NULL; s = s->next)
44                 if (distance(s->p, t->p) < d) cnt++;
45     t->next = grid[X][Y]; grid[X][Y] = t;
46 }
47 int main(int argc, char* argv[])
48 {
49     int i, j, N = atoi(argv[1]);
50     d = atof(argv[2]); G = 1 / d;
51     grid = malloc2d(G + 2, G + 2);
52     for (i = 0; i < G + 2; i++)
53         for (j = 0; j < G + 2; j++)
54             grid[i][j] = NULL;
55     for (i = 0; i < N; i++)
56         gridinsert(randFloat(), randFloat());
57     printf("%d edges shorter than %f\n", cnt, d);
58     return 0;
59 }