Wiki CC3301

No existen variables de tipo “función”, pero es posible tener una variable que es un puntero a una función. Esto es especialmente útil como parámetros para funciones. El siguiente es un ejemplo de un función de ordenamiento genérico, es decir permite ordenar objetos de acuerdo a un criterio definido por una función que se se recibe como parámetro:

  /* ordena datos de cualquier tipo usando Quicksort */

  void swap(void *v[], int i, int j) {
    void *aux;

    aux= v[i];
    v[i]= v[j];
    v[j]= aux;
  }

  void qsort(void *a[], int left, int right,
             int (*compare)(void *, void *)) {
    int i, last;

    if (left>=right)
      return;

    swap(a, left, (left+right)/2);
    last= left;

    /*
      +--+-----------+--------+--------------+
      |  |///////////|\\\\\\\\|              |
      +--+-----------+--------+--------------+
      left        last         i         right
    */

    for (i= left+1; i<=right; ++i)
      if ((*compare)(a[i], a[left])<0)
        swap(a, ++last, i);
    swap(a, left, last);

    qsort(a, left, last-1, compare);
    qsort(a, last+1, right, compare);
  }

La declaración int (*compare)(void *, void *) es para declarar un puntero a una función. Esto se lee de la siguiente forma. Dados 2 punteros a cualquier tipo p y q, la expresion (*compare)(p, q) es de tipo int.

El siguiente programa utiliza la función anterior para ordenar líneas lexicográficamente:

  #include <stdio.h>
  #include <string.h>

  void qsort(void *a[], int left, int right,
             int (*compare)(void *, void *));
             
  #define ANCHO 1000
  #define MAX 10000

  int main() {
    char s[ANCHO];
    char *linea[MAX];
    int i, j;
    /* El siguiente es el criterio para las comparaciones */
    int (*compare)(void *, void *)= (int (*)(void *, void*)) strcmp; /* Ver nota */

    for (i= 0; fgets(s, ANCHO, stdin)!=NULL; ++i)
      linea[i]= strdup(s);

    qsort((void **)linea, 0, i-1, compare);

    for (j= 0; j<i; ++j)
      fputs(linea[j], stdout);
  }

La expresión (int (*)(void *, void*)) es un cast. Se necesita para compatibilizar strcmp con el tipo de la variable asignada. Si se pasa directamente strcmp a qsort, el compilador podría reclamar conflicto de tipos.

Otra forma de hacer esto mismo:

  typedef int (*Comparator)(void *, void *);

  void qsort(void *a[], int left, int right, Comparator compare) {
    ...
  }
  
  int main() {
    ...
    Comparator compare= (Comparator)strcmp;
    ...
  }

Lo cual es mucho más legible.

  int numcmp(char *s1, char *s2) /* compara numéricamente */ {
    int i1, i2;
 
    i1= atoi(s1);
    i2= atoi(s2);
 
    return i1<i2? -1 : i1==i2? 0 : 1;
  } 

  main() {
    char s[ANCHO];
    char *linea[MAX];
    int i, j;
    Comparator compare= (Comparator)numcmp;

    for (i= 0; fgets(s, ANCHO, stdin)!=NULL; ++i)
      linea[i]= strdup(s);

    qsort((void **)linea, 0, i-1, compare);

    for (j= 0; j<i; ++j)
      fputs(linea[j], stdout);
  }

Estudie en los apuntes de Patricio Poblete un programa que recibe la opción “-n” para seleccionar el criterio de ordenamiento numérico, mientras que por omisión ordena alfabéticamente.