Diferencias

Muestra las diferencias entre dos versiones de la página.

--- funciones [2012/08/27 00:09] – creado lmateu
+++ funciones [2012/08/27 01:01] (actual) – lmateu
@@ Línea 5: / Línea 5: @@
 <code>
-        /* ordena datos de cualquier tipo usando Quicksort */
+  /* ordena datos de cualquier tipo usando Quicksort */
-        void swap(void *v[], int i, int j)
+  void swap(void *v[], int i, int j) {
-          {
+    void *aux;
-            void *aux;
+    aux= v[i];
-            aux=v[i];
+    v[i]= v[j];
-            v[i]=v[j];
+    v[j]= aux;
-            v[j]=aux;
+  }
-          }
+  void qsort(void *a[], int left, int right,
-        void qsort(void *a[], int left, int right,
+             int (*compare)(void *, void *)) {
-                   int (*compare)(void *, void *))
+    int i, last;
-          {
-            int i, last;
+    if (left>=right)
+      return;
-            if(left>=right)
-                return;
+    swap(a, left, (left+right)/2);
+    last= left;
-            swap(a, left, (left+right)/2);
-            last=left;
+    /*
+      +--+-----------+--------+--------------+
-            /*
+      |  |///////////|\\\\\\\\|              |
-                  +--+-----------+--------+--------------+
+      +--+-----------+--------+--------------+
-                  |  |///////////|\\\\\\\\|              |
+      left        last         i         right
-                  +--+-----------+--------+--------------+
+    */
-                  left        last         i         right
-            */
+    for (i= left+1; i<=right; ++i)
+      if ((*compare)(a[i], a[left])<0)
-            for(i=left+1; i<=right; ++i)
+        swap(a, ++last, i);
-                if((*compare)(a[i], a[left])<0)
+    swap(a, left, last);
-                    swap(a, ++last, i);
-            swap(a, left, last);
+    qsort(a, left, last-1, compare);
+    qsort(a, last+1, right, compare);
-            qsort(a, left, last-1, compare);
+  }
-            qsort(a, last+1, right, compare);
+</code>
-          }
+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.
+=== Primer ejemplo de uso ===
+El siguiente programa utiliza la función anterior para ordenar líneas lexicográficamente:
+<code>
+  #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);
+  }
+</code>
+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:
+<code>
+  typedef int (*Comparator)(void *, void *);
+  void qsort(void *a[], int left, int right, Comparator compare) {
+    ...
+  }
+  int main() {
+    ...
+    Comparator compare= (Comparator)strcmp;
+    ...
+  }
+</code>
+Lo cual es mucho más legible.
+=== Segundo ejemplo de uso ===
+<code>
+  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);
+  }
+</code>
+Estudie en los [[http://users.dcc.uchile.cl/~lmateu/CC3301/apuntes/LenguajeC/#19|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.