Program 3.20, Sedgewick

  #include <math.h>
  #include <stdio.h>
  #include <stdlib.h>
  #include "Point.h"
  
  typedef struct node *link;
  struct node { 
     point p;  
     link  next; 
  };
  link **grid; 
  int G; 
  float d; 
  int cnt = 0;
  
  gridinsert(float x, float y) { 
      int i, j; 
      link s;
      int X = x*G + 1; 
      int Y = y*G + 1;
      link t = malloc(sizeof *t);
      t->p.x = x; 
      t->p.y = y; 
      for (i = X-1; i <= X+1; i++)
         for (j = Y-1; j <= Y+1; j++)
            for (s = grid[i][j]; s != NULL; s = s->next)
               if (distance(s->p, t->p) < d) cnt++; 
      t->next = grid[X][Y]; 
      grid[X][Y] = t;
  }
  
  float randFloat (void) {
     return 1.0 * rand() / RAND_MAX; 
     // erro no Sedgewick: o denominador deveria ser 
     // ((float)RAND_MAX + 1.0) 
  }
  
  main(int argc, char *argv[]) { 
     int i, j, N = atoi(argv[1]);
     d = atof(argv[2]); 
     G = 1/d;                    // G <= 1/d < G+1
     grid = malloc2d(G+2, G+2);
     for (i = 0; i < G+2; i++)
        for (j = 0; j < G+2; j++)
           grid[i][j] = NULL;
     for (i = 0; i < N; i++)
        gridinsert(randFloat(), randFloat());
     printf("%d edges shorter than %f\n", cnt, d);
  }

A função malloc2d precisa ser adaptada a partir do seguinte Program 3.16 (two-dimensional array allocation):

  // Aloca, dinamicamente, uma matriz inteira
  // r-por-c, ou seja, uma matriz de r linhas e c 
  // colunas cujos elementos são int. Devolve o
  // endereço da matriz alocada. 
  //
  int **malloc2d(int r, int c) { 
      int i;
      int **a = malloc(r * sizeof (int*));
      for (i = 0; i < r; i++)
         a[i] = malloc(c * sizeof (int));
      return a;
  }

Eis o arquivo Point.h:

  // Program 3.3 (Point data type interface) 
  //
  typedef struct { 
     float x; 
     float y; 
  } point;
  float distance(point a, point b);

Eis o arquivo Point.c:

  // Program 3.4 (Point data type implementation) 
  //
  #include <math.h>
  #include "Point.h"
  float distance(point a, point b) { 
      float dx = a.x - b.x, dy = a.y - b.y;
      return sqrt(dx * dx + dy * dy);
  }