Diferencias

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

--- funciones2 [2013/04/12 20:00] – creado lmateu
+++ funciones2 [2014/09/24 21:36] (actual) – [Ejercicios] lmateu
@@ Línea 48: / Línea 48: @@
 === Primer ejemplo de uso ===
-El siguiente programa utiliza la función anterior para ordenar líneas lexicográficamente:
+El siguiente programa utiliza la función anterior para ordenar líneas lexicográficamente los parámetros recibos desde la línea de comandos.  Por ejemplo:
 <code>
-  #include <stdio.h>
+% ordenar juan pedro diego
-  #include <string.h>
+diego
+juan
+pedro
+</code>
-  void qsort(void *a[], int left, int right,
+Esta es la solución usando qsort:
-             int (*compare)(void *, void *));
-  #define ANCHO 1000
-  #define MAX 10000
-  int main() {
+<code>
-    char s[ANCHO];
+  int mistrcmp(void *p1, void *p2) {
-    char *linea[MAX];
+    char *s1= (char*)p1;
-    int i, j;
+    char *s2= (char*)p2;
-    /* El siguiente es el criterio para las comparaciones */
+    return strcmp(s1, s2);
-    int (*compare)(void *, void *)= (int (*)(void *, void*)) strcmp; /* Ver nota */
+  }
-    for (i= 0; fgets(s, ANCHO, stdin)!=NULL; ++i)
+  int main(int argc, char **argv) {
-      linea[i]= strdup(s);
+    int j;
-    qsort((void **)linea, 0, i-1, compare);
+    qsort((void**)argv, 1, argc-1, mistrcmp);
-    for (j= 0; j<i; ++j)
+    for (j= 1; j<argc; ++j)
-      fputs(linea[j], stdout);
+      printf("%s\n", argv[j]);
   }
+</code>
+=== Segundo ejemplo de uso ===
+Esto no es elegante pero permite usar directamente la función strcmp, sin tener que definir mistrcmp.
+<code>
+  int (*compare)(void *, void *)= (int (*)(void *, void*)) strcmp; /* Ver nota */
+  qsort((void**)argv, 1, argc-1, compare);
 </code>
@@ Línea 80: / Línea 88: @@
 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.
+de tipos.  Este cast es correcto en este caso porque todos los parámetros
+de la función son punteros y sabemos que un cast entre punteros no realiza
+ninguna conversión.  ¡Pero cuidado!  Los efectos son impredecibles si los parámetros
+no son punteros.  Por ejemplo el siguiente cast seguramente llevará a resultados
+impredescibles:
-Otra forma de hacer esto mismo:
+<code>
+  int h(int x, double y);
+  int (*f)(double x, int k)= (int (*)(double x, int k)) h;
+</code>
+Si no se coloca el cast, el compilador reclama porque no hay concordancia de tipos.
+Con el cast, el compilador no reclama, pero al invocar f mediante:
+<code>
+  int n= (*f)(3.14, 1);
+  int m= (*f)(3, 1.5);
+</code>
+En ningún caso la función h recibirá algo parecido a los argumentos usados en estas invocaciones.
+El error ocurre porque en este caso los argumentos de la función sí requieren conversión de tipo
+(entero a real o viceversa), pero debido al cast de funciones el compilador no realizará
+ninguna conversión.
+Otra forma de lograr lo mismo, aunque no es más o menos eficiente, es:
 <code>
@@ Línea 98: / Línea 128: @@
 </code>
-Lo cual es mucho más legible.
+Lo cual es más legible.
-=== Segundo ejemplo de uso ===
+=== Tercer ejemplo de uso ===
+Este ejemplo ordena los strings por valor numérico:
 <code>
-  int numcmp(char *s1, char *s2) /* compara numéricamente */ {
+  int numcmp(void *s1, void *s2) /* compara numéricamente */ {
     int i1, i2;
-    i1= atoi(s1);
-    i2= atoi(s2);
-    return i1<i2? -1 : i1==i2? 0 : 1;
-  }
-  main() {
+    i1= atoi((char*)s1);
-    char s[ANCHO];
+    i2= atoi((char*)s2);
-    char *linea[MAX];
-    int i, j;
-    Comparator compare= (Comparator)numcmp;
-    for (i= 0; fgets(s, ANCHO, stdin)!=NULL; ++i)
+    return i1<i2? -1 : i1==i2 ? 0 : 1;
-      linea[i]= strdup(s);
+  }
+  int main(int argc, char **argv) {
+    int j;
-    qsort((void **)linea, 0, i-1, compare);
+    qsort((void**)argv, 1, argc-1, numcmp);
-    for (j= 0; j<i; ++j)
+    for (j= 1; j<argc; ++j)
-      fputs(linea[j], stdout);
+      printf("%s\n", argv[j]);
   }
 </code>
@@ Línea 131: / Línea 157: @@
 un programa que recibe la opción "-n" para seleccionar el criterio de ordenamiento numérico, mientras que
 por omisión ordena alfabéticamente.
+==== Ordenar un arreglo de enteros ====
+¿Cómo se podría usar qsort para ordenar un arreglo de enteros?  Por ejemplo tenemos este arreglo:
+<code>
+  int a[6]= {3, 7, 8, 10, 1, 2};
+</code>
+Hay 2 formas: la elegante y la abreviada.  Primero veamos la elegante.  En teoría no
+podemos usar directamente el arreglo de enteros porque qsort recibe un arreglo de punteros,
+no enteros.  Entonces tenemos que fabricar un arreglo adicional que contenga punteros a los enteros:
+<code>
+  int *ap[6]= { &a[0], &a[1], &a[2], &a[3], &a[4], &a[5] };
+</code>
+Y ahora programamos la función de comparación y el main:
+<code>
+  int intcmp(void *p1, void *p2) {
+    int i1= *(int*)p1;
+    int i2= *(int*)p2;
+    if (i1<i2)
+      return -1;
+    else if (i1==i2)
+      return 0;
+    else
+      return 1;
+  }
+  int main() {
+    int i;
+    qsort((void**)ap, 0, 5, intcmp); /* Ojo: ordena el arreglo ap, no a */
+    for (i= 0; i<6; i++)
+      printf("%d\n", *ap[i]);
+    return 0;
+  }
+</code>
+El cast ''(void%%**%%)ap'' es necesario porque el tipo de ap es ''int%%**%%'' pero qsort requiere ''void%%**%%''.
+=== Forma abreviada ===
+La forma abreviada de ordenar un arreglo de enteros es hacerle creer a qsort que los enteros son punteros.
+<code>
+  /* Este programa solo funciona en plataformas de 32 bits, no cuando son de 64 bits */
+  int a[6]= {3, 7, 8, 10, 1, 2};
+  int intcmp(void *p1, void *p2) {
+    int i1= (int)p1; /* ¡la direccion almacenada es el entero! */
+    int i2= (int)p2;
+    if (i1<i2)
+      return -1;
+    else if (i1==i2)
+      return 0;
+    else
+      return 1;
+  }
+  int main() {
+    int i;
+    qsort((void**)ap, 0, 5, intcmp);
+    for (i= 0; i<6; i++)
+      printf("%d\n", a[i]); /* esta vez si ordena a */
+    return 0;
+  }
+</code>
+Este truco solo funciona en arquitecturas en donde int sea del mismo tamaño que un puntero, i.e. x86 de 32 bits.
+No funcionará en amd64 por ejemplo.  Esta es una de las tantas razones por las que los programas que corren
+correctamente en x86, al compilarlos en una arquitectura de 64 bits, ya no funcionan.
+=== Forma portable ===
+La siguiente solución debería funcionar en todas las plataformas.  El tructo está en vestir
+los enteros como punteros en el arreglo que recibe qsort:
+<code>
+  void *a[6]= {(void*)3, (void*)7, (void*)8, (void*)10, (void*)1, (void*)2};
+  int longcmp(void *p1, void *p2) {
+    long i1= (long)p1; /* la direccion almacenada es el entero! */
+    long i2= (long)p2;
+    if (i1<i2)
+      return -1;
+    else if (i1==i2)
+      return 0;
+    else
+      return 1;
+  }
+  int main() {
+    int i;
+    qsort(a, 0, 5, longcmp);
+    for (i= 0; i<6; i++)
+      printf("%ld\n", (long)a[i]); /* esta vez si ordena a */
+    return 0;
+  }
+</code>
+En Windows de 64 bits el tipo long es de 32 bits como
+se explica [[http://stackoverflow.com/questions/384502/what-is-the-bit-size-of-long-on-64-bit-windows|acá]]
+y por lo tanto no coincide con el tamaño de un puntero.  Esto podría significar que el compilador
+entregue algún warning.  Pero a pesar del warning el ordenamiento debería hacerse correctamente.
+Enfín, el autor de este documento no recomienda escribir este tipo de código, pero sí entenderlo
+porque hay abundante código del legado que recurre a este tipo de trucos y por lo tanto es importante
+ser capaz de modificarlo si se requieren cambios.
+==== Ejercicios ====
+  * Resuelva la pregunta 3 parte i.- del [[http://users.dcc.uchile.cl/~lmateu/CC3301/controles/ex-131.pdf|examen de 2013/1]].
+  * Resuelva la pregunta 1 del [[http://users.dcc.uchile.cl/~lmateu/CC3301/controles/c2-131.pdf|control 2 de 2013/1]].  Pruebe su solución usando el archivo [[http://users.dcc.uchile.cl/~lmateu/CC3301/download/colapri.zip|colapri.zip]].  Para la parte a.- complete el archivo p1a.c.  Verifique el resultado con el comando "make test-p1a".  Luego resuelva la parte b.- en el archivo ordenar.c y verifique su funcionamiento con el comando "make test-p1b".