Estructuras de datos

Datos compuestos

  • Ya vimos como agrupamos datos del mismo tipo. Tenemos arreglos (vectores y matrices) o strings (cadenas de caracteres).
  • ¿Como agrupamos datos de distinto tipo?
    • Palabras clave: struct y union
  • ¿Por que podemos querer hacerlo?
    • Ejemplo: Entidad alumno tiene distintos datos como nombre, apellido, edad, legajo, etc...
    • Para hacer que los programas sean mas simples, sencillos, ordenados y naturales.

El tipo "struct"

  • La estructura ("struct") es un conjunto de una o mas variables, agrupadas u organizadas bajo un único nombre, cuyos miembros pueden ser de tipos diferentes
  • La estructura la define el programador y es un nuevo tipo de dato
  • Declaración:

struct identificador-nombre {
    tipo1 componente1;
    tipo2 componente2;
    ...
    tipoN componenteN;
} lista_variables;

Ejemplo: estructura para puntos en la pantalla


struct point {
    int x;
    int y;
};

struct point punto;

/* var tipo point */
struct point puntoMax = {640, 480};

punto.x = 300;      /* acceso al elemento con */
punto.y = 200;      /* sintaxis operador punto */

Estructura: Acceso a campos

  • Accediendo como variable:
    • Uso el punto ( . )
    • 
      punto.x = 300;
      

  • Accediendo como puntero:
    • Uso la flecha ( -> )

struct point A = {640, 480}, B;
struct point *pA,*pB;
pA = &A; pB = &B;
pB -> x = pA -> x;
pB -> y = 200; // B = {640,200}


Notas: Punto/Flecha... ¿Por qué? & Dennis about C

Ejemplo: estructura para puntos en la pantalla

  • Prototipo de función que trabaja con estructuras:

struct point sumaPuntos (struct point p1,
                         struct point p2);

  • Función implementada:

struct point sumaPuntos (struct point p1,
                         struct point p2) {
    p1.x += p2.x;
    p1.y += p2.y;
    return p1;
}

Formas de operar con struct (1)

  • Uso de un campo
    • estructura.componente
  • 
    a2.nota1 = 7.5;
    

  • Asignación de una estructura a otra:
  • 
    a2 = a1;
    

    La copia es como un memcpy(), byte a byte. Pero existe el problema de "shallow copy" si tenemos punteros dentro de la estructura (Articulo (EN), presentacion (EN), y resumen (HTML).

Formas de operar con struct (2)

  • Declaración y asignación
  • 
    struct Alumnos a = {"Celeste Carballo",
                                    "7654321",
                                    6.0, 5.5, 5.0, 5.5};
    

  • Función que retorna una estructura
  • 
    struct Alumnos nuevoAlumno(char nombre[ ]) { ...
    

  • Función que recibe como argumento una estructura
  • 
    void calculaNota(struct Alumnos a1) { ...
    

Estructuras anidadas


struct fecha {
    int dia, mes, anio;
};

struct persona {
    char nombre[20];
    char apellido[20];
    struct fecha nacimiento;
    unsigned long telefono;
};

struct persona amigo[30];   /* array */

amigo[15].nacimiento.anio = 1982;

typedef

  • Es una palabra clave que permite definir nuevos tipo de datos:

struct point {
    int x;
    int y;
};

typedef struct point punto;

punto A,B;

A.x =1;

typedef

Uso de typedef para independizarse del compilador

Dependiendo del compilador elijo que definicion usar



/* Si tengo el tipo de dato bit disponible */
typedef bit bool;

/* Si no lo tengo disponible */
typedef char bool;

/* Si mi compilador soporta C99 */
typedef _BOOL bool;

sizeof struct


Es importante en estructuras (así como con tipos de datos simples) utilizar el operador sizeof para averiguar su tamaño.


Esto es así por que queremos escribir programas portables, y para que sean portables debemos averiguar el tamaño de cada dato en tiempo de compilación.


Un detalle de color en intel 64bits es que dependiendo del orden puede ocupar distinto tamaño los mismos datos, dependiendo del orden. El mínimo a reservar en un campo será 4bytes. La única excepción será si puede "empacarlos" (ver en el ejemplo "estructuras.c" el tipo de datos_t4).

Articulos (EN): "Data structure alignment (Wikipedia)" & "Coding for Performance (Intel)".

Union

  • Las uniones son agrupaciones de datos cuyos miembros comparten la misma memoria (es decir, se solapan).
  • El tamaño total ocupado es el del miembro mas grande.
    
    union equivalencia {
        short i;
        char b[2];
    };
    
    union equivalencia x;
    
    x.i = 0x4892;
    printf("%x",x.b[0]);
    printf("%x",x.b[1]);
    


    Nota:
  • Ambos están en la misma posición de memoria.
  • Por lo tanto la 'A' sobre escribe al 5.

Union


Campos de bits

  • Son estructuras (struct) pero de tamaño menor a 1 byte (char).
  • Se puede definir de cada campo que tamaño en bits tiene.
  • Esto le permite a C un acceso a datos a nivel de bit agregandole flexibilidad y elegancia.
  • Las otras técnicas de acceso son mucho menos claras (mascaras y operadores a nivel de bit).

Campos de bits


typedef unsigned char uchar;

struct hexa {
	uchar nl:4;
	uchar nh:4;
};

union byte {
	uchar b;
	struct hexa h;
};

union byte A;
char str[3];

A.b=0x48;
printf("%d",A.h.nh); /* Muestra 4 */
printf("%d",A.h.nl); /* Muestra 8 */

/* Convirtiendo en string */
str[0] = '0' + A.h.nh; // Version simplificada
str[1] = '0' + A.h.nl; // Falta 'A', ver union_ej2.c
str[2] = NULL;

Bajar union_ej2.c para correrlo.

Campo de Bits y Uniones


  • Uniones: Código ejemplo

  • Ejercicios:
    1. Realizar un programa que devuelva el primer carácter (inicial) de un string/nombre usando uniones.
    2. Realizar un programa que tome un número en punto flotante y devuelva sus partes usando uniones y campos de bit. (resC+resH)

Acceso bit a bit con campos de bits

Máscaras (I)


Recordemos las operaciones lógicas (vistas previamente)



&& : AND logico

& : AND binario (bit a bit)

A B R
0 0 0 --> Como A esta en 0 vale 0
0 1 0 --> Como A esta en 0 vale 0
1 0 0 --> Como A esta en 1 vale B
1 1 1 --> Como A esta en 1 vale B

	=> Para poner en 0 usamos una AND

Máscaras (II)



|| : OR logico

| : OR binario (bit a bit)

A B R
0 0 0 --> Como A esta en 0 vale B
0 1 1 --> Como A esta en 0 vale B
1 0 1 --> Como A esta en 1 vale 1
1 1 1 --> Como A esta en 1 vale 1

	=> Para poner en 1 usamos una OR

Acceder a los bits de un byte utilizando una mascara:
bits-de-un-byte-mascara.c

Operadores de desplazamiento


Recordemos los Operadores (vistos previamente)

  • >> : Mover bits a la derecha
  • << : Mover bits a la izquierda


masc_b0 = 0x01; // 0000'0001
masc_b1 = 0x02; // 0000'0010
masc_b2 = 0x04; // 0000'0100
masc_b3 = 0x08; // 0000'1000

byte = 0xFF;    // 1111'1111

res0 = byte & masc_b0; // 0000'0001
res = res0 >> 0;       // 0000'0001
res1 = byte & masc_b1; // 0000'0010
res = res1 >> 1;       // 0000'0001
res2 = byte & masc_b2; // 0000'0100
res = res2 >> 2;       // 0000'0001

Desplazamiento y rotación


Si bien esto no está soportado directamente por C, usando desplazamiento y mascaras se puede lograr también rotar. Y ciertos compiladores con GCC pueden detectar este código y traducirlo correctamente a una operación de assembler de rotación.


unsigned int data=0x0F;
data= data>> (unsigned) 1 | data<< (unsigned)31;

compiles to ASM:


ror  %eax

Rotando (además de desplazando) bits: bit_rotate.c

Ejemplos de desplazamiento y rotación bit a bit: operadores_bits_y_rotacion.txt

Enumeraciones

  • Un tipo de datos enumerado es una manera de asociar nombres a números, y por consiguiente de ofrecer más significado a alguien que lea el código.
  • La palabra reservada enum (de C) enumera automáticamente cualquier lista de identificadores que se le pase, asignándoles valores de 0, 1, 2, etc (enteros).
    • O sea, permiten crear conjuntos de constantes nombradas
    • Si no son forzados el primer nombre del enum tiene valor 0, el siguiente 1 y así sucesivamente
  • Se pueden declarar variables enum (que se representan siempre como valores enteros).
  • La declaración de un enum se parece a la declaración de un struct, tiene la misma sintaxis.

Enumeraciones

  • enum {lista_de_identificadores};

    • enum nombre_de_tipo {lista_de_identificadores};
    • typedef enum {lista_de_identificadores} nombre_enumeracion;

  • Ejemplo creando un tipo boolean:
    
    typedef enum {FALSE = 0, TRUE = 1} boolean;
    

  • En C99 las definiciones de enum son globales. Esto hace que podamos usar las enum como una definición de constantes (tipo DEFINE) pero jerarquizadas.

Enumeraciones

  • Enumeraciones - Ejemplos

  • Enumeraciones - Ejercicios
    • Construir un programa que dados los colores de una resistencia nos de su valor en ohm.
    • Construir un programa que muestre un menú y e indique la opción seleccionada, empleando una enumeración y una lista de cadenas.

Recordemos memoria dinámica


  • Libreria: stdlib.h
  • Funciones mas usadas:
    • void *malloc(size_t size);
    • void free(void *ptr);
    • ...



#include <stdlib.h>

int *p;

p = (int *) malloc( sizeof(int) );

Estructuras dinámicas de datos



Por ejemplo, puedo crear un string en forma dinámica:


#include <stdlib.h>
#include <stdio.h>

void main(void) {
	char *str, tam;
	printf("Ingrese el tamaño de cadena deseado: ");
	scanf("%d",&tam);
	str = (char *) malloc ( sizeof(char) * tam );
	printf("Ingrese su cadena: ");
	scanf("%s",str);
	printf("\nSu cadena es: %s",str);
}

Estructuras dinámicas de datos


Pero no solo de chars...

De cualquier tipo de dato puedo pedir...

¡Incluso estructuras!


struct vendedor {
	char nom[40];
	float com,acum;
	int vent;
} *vec;

/* Creo un vector de 10 posiciones dinamicamente */
vec = (struct vendedor *) malloc( sizeof( struct vendedor ) * 10);

Introducción a listas


  • Como debemos asignar un vector: Todo de un bloque. Las posiciones de memoria deben ser contiguas.

  • Entonces...
    • ¿Como puedo hacer para pedir memoria a medida que la necesito?
    • Respuesta: Usaremos listas de datos

Introducción a listas

Matriz Dinámica



#define FIL 5
#define COL 5

void main(void) {
	int **v, i, j;
	v = malloc(sizeof(*int)*FIL);
	for(i=0;i<FIL;i++) {
		v[i] = malloc(sizeof(int)*COL);

	srandom(15);
	for(i=0;i<FIL;i++) {
		for(j=0;j<COL;j++) {
...

Introducción a listas


void *p = NULL;

struct vendedor *q, *r;

q = (struct vendedor *) malloc ( sizeof(struct vendedor) );

r = (struct vendedor *) malloc ( sizeof(struct vendedor) * 10 );

struct vendedor **vp[100];

struct nodo {
	struct vendedor dato;
	struct nodo *sig;
	};

struct nodo *p1;

Ejercicio

Realizar un programa que maneje el ingreso de vendedores.

Debe poder agregarse un vendedor y luego agregar ventas de ese vendedor.

Se debera poder listar las ventas durante el mes, y al final del mes se debe generar un cierre del mes informando el monto total de las ventas y comisiones a pagar.

Las comisiones son 10% del monto vendido por vendedor.

  1. Comenzar generando una solución basada en un vector de vendedores de 20 posiciones.
  2. Una vez resuelto el problema migrar a una solución que use una lista simplemente enlazada (agregando al final).
  3. Realizar una funcion que permita ordenar la lista por nombre.
  4. Al finalizar el programa los datos en memoria deberan guardarse en un archivo (binario).
  5. Al comenzar el programa los datos deberan ser leidos del archivo guardado anteriormente.
  6. Levantar los datos de un archivo de texto con un formato prefijado por usted (por ejemplo como delimitado).