Wiki CC3301

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
===== Estructuras =====

Una estructura (o record) agrupa a un conjunto de campos.

<code>
  #include <stdio.h>
  /* Definición de la estructura */
  struct punto {
    float x;
    float y;
  };

  int main() {       
    /* Declaraciones de variables locales */
    struct punto u, v;
    struct punto z={1.0, -2.5};
        
    /* Acceso a componentes */
    z.x=2.0;
    printf("z=(%f, %f)\n", z.x, z.y);
    return 0;
  }
</code>

Al igual que cualquier otra variable, las variables de la categoría estructura pueden ser automáticas (locales a una función), globales (viven durante toda la duración del programa) o dinámicas (se crean con malloc y destruyen con free).

==== Estructuras como parámetros y valor de retorno ====

También se pueden pasar como argumentos en funciones y se pueden retornar.

<code>
  #include <stdio.h>
  struct punto {
    float x;
    float y;
  };
  struct punto sumaPuntos(struct punto u, struct punto v) {
    struct punto z= { u.x+v.x, u.y+v.y };
    return z;
  }
  
  int main() {
    struct punto a= {1.0, -2.5}, b= {4.2, 3.0 };
    struct punto c= sumaPuntos(a, b);
    printf("c=(%f, %f)\n", c.x, c.y);
    return 0;
  }
</code>

¡Cuidado! Lo siguiente no modifica el punto que se pasa como argumento:

<code>
  void mover(struct punto u, float dx, float dy) {
    u.x += dx;
    u.y += dy;
  }
  
  int main() {
    struct punto a={1.0, -2.5};
    mover(a, 0.5, 1.2);    /* ¡No cambia a! */
    printf("a=(%f, %f)\n", a.x, a.y);
    return 0;
  }
</code>

Al igual que los tipos de datos primitivos, //las estructuras también se pasan por valor//.  Si bien este código modifica el parámetro u, no modifica el argumento a en la invocación.

==== Punteros a estructuras ====

Por lo tanto, si se necesita que una función modifique una estructura pasada como argumento, se debe pasar el puntero (recuerde la función swap):

<code>
  void mover(struct punto *u, float dx, float dy) {
    (*u).x += dx;
    (*u).y += dy;
  }
  
  int main() {
    struct punto a= {1.0, -2.5};
    mover(&a, 0.5, 1.2);
    printf("a=(%f, %f)\n", a.x, a.y);
    return 0;
  }
</code>

La notación ''(*u).x'' es incómoda.  Por eso el lenguaje C define que:

          (*u).x ≡ u->x
  
Y por lo tanto podemos reescribir la función desplazar como:

<code>
  void mover(struct punto *u, float dx, float dy) {
    u->x += dx;
    u->y += dy;
  }
</code>

==== Estructuras dinámicas ====

El siguiente código es correcto:

<code>
  struct punto nuevoPunto(float x, float y) {
    struct punto a= { x, y };
    return a;
  }
</code>

Porque no se está entregando como resultado la variable a.  Esa variable se destruye al retornar la función, pero su valor sí sobrevive y es el valor de retorno de la función.

En cambio, este código es incorrecto (aunque el compilador no reclame):

<code>
  struct punto *nuevoPunto(float x, float y) {
    struct punto a= { x, y };
    return &a;  /* ¡No haga esto! */
  }
  
  int main() {
    struct punto *p= nuevoPunto(1.0, 2.0);
    printf("(%f,%f)\n", p->x, p->y);  /* ¡Despliega los valores correctos! */
    printf("(%f,%f)\n", p->x, p->y);  /* ¡Despliega basura! */
    return 0;
  }
</code>

Aquí sí se está retornando una referencia de la variable a.  Como esta variable es destruida al retornar nuevoPunto,
la referencia almacenada en p en la función main es una //dangling reference//.  En la primera evaluación de p->x, la memoria ocupada por la antigua variable a no ha sido reescrita y por lo tanto el valor recuperado es el correcto.  Pero en la segunda evaluación de p->x, esa memoria fue ocupada para almacenar las variables locales del primer printf y por eso ahora es basura.

Si se requiere que una estructura viva más allá de la función en donde se crea, use estructuras dinámicas:

<code>
  struct punto *nuevoPunto(float x, float y) {
    /* se pide espacio para un punto en el heap */
    struct punto *pa= malloc(sizeof(struct punto));
    pa->x= x;
    pa->y= y;
    return pa;
  }
  
  int main() {
    struct punto *p= nuevoPunto(1.0, 2.0);
    printf("(%f,%f)\n", p->x, p->y);
    free(p); /* libera el espacio ocupado por la estructura */
    return 0;
  }
</code>

Los objetos de Java corresponden a las estructuras de C.  Pero en Java no existen los objetos globales o automáticos.  Todos los objetos se crean en el heap y solo el recolector de basuras puede liberar su espacio.  Esta fue una decisión de diseño para mantener la robustez de Java, porque así se evitan las 2 únicas fuentes de referencias colgantes: (i) punteros a variables automáticas creadas en una función que ya retornó, o (ii) punteros a variables dinámicas que ya fueron destruidas con free.

==== Typedef ====

Escribir siempre //struct punto// en cada declaración resulta pesado sintácticamente.  Por eso el lenguaje ofrece la declaración //typedef//.  Por ejemplo:

<code>
  typedef int ENTERO, *PUNTERO;
</code>

Esto intruduce 2 nuevos tipos: //ENTERO// y //PUNTERO//.  Se pueden usar para declarar variables:

<code>
  ENTERO x;
  PUNTERO p= &x;
</code>

Esto es equivalente a haber escrito:

<code>
  int x, *p= &x;
</code>

Es como haber eliminado el //typedef// y substituido //ENTERO// por //x// y //PUNTERO// por //p//.

¿A qué sería equivamente escribir lo siguiente?

<code>
  PUNTERO *q;
</code>

De la misma forma se pueden declarar el tipo //Punto//:

<code>
  typedef struct punto Punto;
  Punto a, b;
</code>

O simplemente escribir directamente:

<code>
  typedef struct {
    float x, y;
  } Punto;
  
  Punto a, b;
</code>

Observe que la etiqueta que viene después de //struct// es opcional.
También se pudo haber colocado explícitamente la etiqueta //punto//:

<code>
  typedef struct punto {
    float x, y;
  } Punto;
</code>

//La etiqueta del struct se puede omitir cuando no se va a usar a continuación en el archivo.//
==== Estructuras recursivas ====

Una lista enlazada es una estructura de datos recursiva porque uno de los campos de un nodo es un puntero a otro nodo:

<code>
  struct node {
    int x;
    struct node *next;
  };
  
  typedef struct node Node;
  
  Node n1= { 5, NULL};
  Node n2= { 1, &n1};
  Node* h= &n2;   /* puntero al primer nodo de la lista */
</code>

La declaración de //Node// también se puede escribir como:

<code>
  typedef struct node {
    int x;
    struct node *next;
  } Node;
</code>

Observe que en este caso la etiqueta //node// sí se debe especificar porque se usa dentro de //Nodo//.
No se puede usar //Node// directamente como en el ejemplo de más abajo porque se generaría un error en la compilación:

<code>
  typedef struct node {
    int x;
    Node *next;  /* Error al compilar */
  } Node;
</code>

El problema es que el tipo Node es desconocido en el momento de declarar el campo next.  Recuerde que en C, el alcance de un identificador comienza en el punto del programa en donde se definió.  Por otra parte, las etiquetas de los struct tienen reglas distintas: son válidas en cualquier parte siempre y cuando se usen para declarar punteros.

=== Ejemplo: recorrer una lista enlazada ===

<code>
  void mostrarLista(Node *n) {
    while (n!=NULL) {
      printf("%d ", n->x);
      n= n->next;
    }
    printf("\n"); /* Fin de línea */
  }
</code>

=== Ejemplo: inserción ===

La inserción de un elemento y en una lista ordenada se puede escribir de la siguiente forma:

<code>
  void insertar(Node **ppnode, int y) {
    Node *pnode= *ppnode;
    while (pnode != NULL  &&  pnode->x < y) {
      ppnode= & pnode->next;
      pnode= *ppnode;
    }
  
    Node *ins= malloc(sizeof(Node));
    ins->x= y;
    ins->next= pnode;
    *ppnode= ins;
  }
</code>

Observe que insertar recibe un puntero al puntero que referencia el primer nodo de la lista.
Pruebe esta función con este código:

<code>
  int main() {
    Node n1= {5, NULL};
    Node n2= {1, &n1};
    Node *h= &n2;
    mostrarLista(h);
    insertar(&h, 3);
    mostrarLista(h);
    return 0;
  }
</code>

Haga un diagrama de variables y punteros para ver como se inserta el 3.

=== Ejercicio 1 ===

Suponga que la lista enlazada tiene una cabeza de mentira como en el ejercicio anterior.  Pero ahora la lista está desordenada.  Programe la función ''void append(Node **pphead, int y)'' que agrega un nodo al final de la lista.

=== Ejercicio 2 ===

Resuelva la parte b de la pregunta 2 del [[http://users.dcc.uchile.cl/~lmateu/CC3301/controles/c1-141.pdf|control 1 del semestre Otoño 2014]].  Pruebe su solución con el archivo [[http://users.dcc.uchile.cl/~lmateu/CC3301/download/rama.zip|rama.zip]]. Implemente su solución en el archivo rama.c. Compílelo con make y ejecútelo. El programa le dirá si su solución satisface todos el test del enunciado.
==== Enum ====

Se usan para definir constantes que servirán para etiquetar entidades.  Considere por ejemplo:

<code>
  #include <stdio.h>

  enum tag { INT, FLOAT };

  int main() {
    enum tag a= INT;
    enum tag b= FLOAT;
    printf("a=%d b=%d\n", a, b); /* a=0 b=1 */
  }
</code>

Los identificadores INT y FLOAT son constantes y por lo tanto no pueden aparecer al lado izquierdo de una asignación.

Alternativamente se puede usar typedef para poder usar el tipo Tag en vez de enum tag que es muy largo:

<code>
  #include <stdio.h>

  typedef enum { INT, FLOAT } Tag;

  int main() {
    Tag a= INT;
    Tag b= FLOAT;
    printf("a=%d b=%d\n", a, b); /* a=0 b=1 */
  }
</code>

Para hacer que las etiquetas comiencen de 1:

  enum tag { INT=1, FLOAT };
  
==== Union ====

Los //union// de C son similares a los //struct//.  Por ejemplo:

<code>
  union numero {
    int n;
    double x;
  };
  
  main() {
    union numero a;
    a.n= 1;
    printf("n=%d\n", a.n); /* n=1 */
    a.x= 0.3;
    printf("¡n=%d! x=%f\n", a.n, a.x); /* ¡n=858993459! x=0.300000 */
    return 0;
  }
</code>

Esto ocurre porque todos los campos de un union comparten el mismo espacio en memoria.  La idea es que un union
se usa para almacenar un solo dato pero cuyo tipo depende del contexto.  Considere este ejemplo:

<code>
  #include <stdio.h>

  struct numero {
    int tipo; /* selector */
    union {
      int ival;
      float fval;
    } u;
  };

  enum {INT, FLOAT};

  void imprimir(struct numero a) {
    switch(a.tipo) {
      case INT:
        printf("%d\n", a.u.ival);
        break;

      case FLOAT:
        printf("%f\n", a.u.fval);
    }
  }

  main() {
    struct numero x;

    x.tipo=INT;
    x.u.ival=5;
    imprimir(x);

    x.tipo=FLOAT;
    x.u.fval=3.14;
    imprimir(x);
    return 0;
  }
</code>

==== Alineamiento ====

Previamente vamos a dejar planteada una pregunta.  Suponga que tiene el siguiente código:

<code>
  #include <stdio.h>
  
  struct T {
    int n;
    char c;
  };
  
  int main() {
    printf("%d\n", sizeof(struct T));
  }
</code>

¿Qué valor cree Ud. que despliega este programa?

Para poder deducir la respuesta primero hay que enunciar un requerimiento de hardware: los microprocesadores
modernos leen y escriben más eficientemente variables de tipos primitivos cuando ellas están //alineadas//.
Una variable está //alineada// cuando su dirección es múltiplo de
su tamaño.  Por ejemplo la dirección de una variable alineada de tipo entero debe ser múltiplo de 4 y si es de tipo
punto flotante de doble precisión (double) debe ser múltiplo de 8.  Por esta razón los compiladores de
C generan su código de manera que las variables de tipos primitivos están alineadas.

Con esta información es más fácil responder la siguiente pregunta.  ¿Que despliega el siguiente programa?

<code>
  #include <stdio.h>
  #include <stdlib.h>
  
  struct U {
    char c; /* Observe que primero viene el caracter */
    int n;
  };
  
  int main() {
    struct U *u= (struct U *)malloc(sizeof(struct U));
    printf("%p\n", u);
    printf("%d\n", sizeof(struct U));
    printf("desplazamiento de c=%d\n", (char*)&u->c-(char*)u);
    printf("desplazamiento de n=%d\n", (char*)&u->n-(char*)u);
  }
</code>

¿Cómo se puede garantizar que //n// esté alineado?  La función //malloc// decide la ubicación en memoria de la
estructura sin saber su tipo.  Conoce el tamaño la región pedida, pero no sabe si es para un arreglo de 8 caracteres,
para el cual no hay requerimiento de alineamiento, o si es un //double//, que debe estar alineado a 8 bytes.  Como //malloc// no sabe cual es el requerimiento de alineamiento
se pone en el peor caso: 8.  //Malloc// siempre retorna direcciones múltiplo de 8.

Pero aún así si el compilador asigna un desplazamiento 0 para //c// y un desplazamiento 1 para //n//,
la variable //n// estaría desalineada.
La solución está en que el compilador asigna un desplazamiento 4 para //n// y deja sin
ocupar los bytes 1, 2 y 3 de la estructura.  ¡Por lo tanto el tamaño de la estructura //U// es 8!
El compilador sacrifica un poco de memoria para ganar eficiencia en tiempo de ejecución.  Cuando
una variable no está alineada, el procesador requiere más ciclos del reloj para leerla o modificarla.
Incluso existen procesadores en donde acceder a una variable no alineada produce una falla que se denomina
//bus error// y el programa no continúa.

Para responder cual es el tamaño de //sizeof struct T// consideremos este código:

<code>
  int main() {
    int i;
    struct T *t= (struct T*)malloc(10*sizeof(struct T));
    for (i=0; i<9; i++) {
      t[i].c= '0';
      t[i].n= 0;
    }
  }
</code>

Si C determina que el tamaño de la estructura es 5, entonces ''t[0].n'' estaría correctamente alineada
pero ''t[1].n'', no lo estaría.  La solución nuevamente está en que el compilador dejar 3 bytes no utilizados
al final de la estructura, con lo cual //el tamaño de la estructura T es 8//, nuevamente.  Eso garantiza
que todas las variables n en el arreglo t estarán alineados.
    
Esto lo podemos resumir en que (i) el requerimiento de alineamiento de una estructura es el máximo requerimiento
de alineamiento de sus miembros, y (ii) el tamaño de la estructura es siempre un múltiplo de su requerimiento de
alineamiento.