Wiki CC3301

Herramientas de usuario

Herramientas del sitio

Estás aquí: start » estructuras
Traza:
estructuras

Diferencias

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

Enlace a la vista de comparación

Próxima revisión		Revisión previa
estructuras [2012/08/23 02:12] – creado lmateuestructuras [2015/09/30 20:03] (actual) – [Estructuras recursivas] lmateu
Línea 88: Línea 88:
           (*u).x ≡ u->x           (*u).x ≡ u->x
      
-Y por lo tanto podemos reescribir la función dezplazar como:+Y por lo tanto podemos reescribir la función desplazar como:
  
 <code> <code>
Línea 134: Línea 134:
   struct punto *nuevoPunto(float x, float y) {   struct punto *nuevoPunto(float x, float y) {
     /* se pide espacio para un punto en el heap */     /* se pide espacio para un punto en el heap */
-    struct punto *pa= (struct punto*)malloc(sizeof(struct punto));+    struct punto *pa= malloc(sizeof(struct punto));
     pa->x= x;     pa->x= x;
     pa->y= y;     pa->y= y;
Línea 152: Línea 152:
 ==== Typedef ==== ==== Typedef ====
  
-Escribir siempre struct punto en cada declaración resulta pesado sintácticamente.  Por eso el lenguaje permite la declaración typedef.  Por ejemplo:+Escribir siempre //struct punto// en cada declaración resulta pesado sintácticamente.  Por eso el lenguaje ofrece la declaración //typedef//.  Por ejemplo:
  
 <code> <code>
Línea 158: Línea 158:
 </code> </code>
  
-Esto intruduce 2 nuevos tipos: ENTERO y PUNTERO.  Se pueden usar para declarar variables:+Esto intruduce 2 nuevos tipos: //ENTERO// y //PUNTERO//.  Se pueden usar para declarar variables:
  
 <code> <code>
Línea 171: Línea 171:
 </code> </code>
  
-Es como haber eliminado el typedef y substituido ENTERO por x y PUNTERO por p.+Es como haber eliminado el //typedef// y substituido //ENTERO// por //x// y //PUNTERO// por //p//.
  
 ¿A qué sería equivamente escribir lo siguiente? ¿A qué sería equivamente escribir lo siguiente?
Línea 179: Línea 179:
 </code> </code>
  
-De la misma forma se pueden declarar el tipo Punto:+De la misma forma se pueden declarar el tipo //Punto//:
  
 <code> <code>
Línea 196: Línea 196:
 </code> </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 ==== ==== Estructuras recursivas ====
  
Línea 213: Línea 223:
 </code> </code>
  
-La declaración de Node también se puede escribir como:+La declaración de //Node// también se puede escribir como:
  
 <code> <code>
Línea 222: Línea 232:
 </code> </code>
  
-Pero esto genera un error en la compilación:+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> <code>
Línea 231: Línea 242:
 </code> </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 de 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.+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 === === Ejemplo: recorrer una lista enlazada ===
Línea 247: Línea 258:
 === Ejemplo: inserción === === Ejemplo: inserción ===
  
-Supongamos que la lista enlazada posee una cabeza de mentira para facilitar las inserciones y que la lista esta ordenada ascendentemente.  Entonces la inserción se puede escribir de la siguiente forma:+La inserción de un elemento y en una lista ordenada se puede escribir de la siguiente forma:
  
 <code> <code>
   void insertar(Node **ppnode, int y) {   void insertar(Node **ppnode, int y) {
-    Node *ins; +    Node *pnode= *ppnode; 
-    while (*ppnode!=NULL && (*ppnode)->x<y) +    while (pnode != NULL  &&  pnode->x < y) { 
-      ppnode= &(*pnode)->next; +      ppnode= & pnode->next; 
-     +      pnode= *ppnode; 
-    ins= (Node*)malloc(sizeof(Node));+    } 
 +   
 +    Node *ins= malloc(sizeof(Node));
     ins->x= y;     ins->x= y;
-    ins->next= *ppnode;+    ins->next= pnode;
     *ppnode= ins;     *ppnode= ins;
   }   }
 </code> </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: Pruebe esta función con este código:
  
Línea 278: Línea 292:
 Haga un diagrama de variables y punteros para ver como se inserta el 3. Haga un diagrama de variables y punteros para ver como se inserta el 3.
  
-=== Ejercicio ===+=== 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. 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 ==== ==== Enum ====
  
Línea 299: Línea 316:
  
 Los identificadores INT y FLOAT son constantes y por lo tanto no pueden aparecer al lado izquierdo de una asignación. 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: Para hacer que las etiquetas comiencen de 1:
Línea 386: Línea 417:
 Para poder deducir la respuesta primero hay que enunciar un requerimiento de hardware: los microprocesadores 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//. modernos leen y escriben más eficientemente variables de tipos primitivos cuando ellas están //alineadas//.
-Una variabble está //alineada// cuando su dirección es múltiplo de+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 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 punto flotante de doble precisión (double) debe ser múltiplo de 8.  Por esta razón los compiladores de
Línea 411: Línea 442:
 </code> </code>
  
-¿Cómo se puede garantizar que n esté alineado?  La función malloc decide la ubicación en memoria de la+¿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, 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 +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.+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 +Pero aún así si el compilador asigna un desplazamiento 0 para //c// y un desplazamiento 1 para //n//, 
-estaría desalineada.  La solución está en que el compilador asigna un desplazamiento 4 para n y deja sin +la variable //n// estaría desalineada. 
-ocupar los bytes 1, 2 y 3 de la estructura.  ¡Por lo tanto el tamaño de la estructura U es 8!+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 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. una variable no está alineada, el procesador requiere más ciclos del reloj para leerla o modificarla.
Línea 424: Línea 456:
 //bus error// y el programa no continúa. //bus error// y el programa no continúa.
  
-Para responder cual es el tamaño de ''sizeof struct T'' consideremos este código:+Para responder cual es el tamaño de //sizeof struct T// consideremos este código:
  
 <code> <code>
estructuras.1345687962.txt.gz · Última modificación: 2012/08/23 02:12 por lmateu