19/04/2013 - Clase 3: Tipo de Dato Abstracto (TDA)

Fecha de publicación: 19-abr-2013 19:29:55

Arrancamos la clase terminando de hacer andar el entorno de trabajo, resolviendo problemas con el MinGW.

En la segunda parte de la clase entramos entonces a ver un tema nuevo, de la unidad 2, Tipo de Dato Abstracto.

Deben leer:

• este apunte, donde está la teoría
• y este otro apunte donde se explica como implementar un TDA en c.

Ambas páginas se pueden acceder desde la página de la Unidad 2

Para repasar acá, de entrada comenzamos definiendo la idea de Diccionario o Mapa que es un concepto/estructura bastante útil en cualquier lenguaje de programación. Donde podemos agrupar claves con valores. Al igual que en un diccionario físico. El diccionario no puede contener dos entradas para una misma clave. Y claro, se llama clave, porque la idea es que dada una clave puedo acceder a su valor asociado.

Entonces, pusimos un ejemplo donde las claves eran nombres de personas y los valores números que representaban sus edades.

Después fuimos pensando qué operaciones tenían sentido sobre el Diccionario:

• buscar(diccionario, clave) -> valor: retorna el valor asociado a la clave dada, en este diccionario.
• agregar(diccionario, clave, valor) -> void: agregar una nueva entrada con clave - valor.
• modificar(diccionario, clave, nuevoValor) -> void
• modificarClave(diccionario, clave, claveNueva) ->

Y hasta podemos definir acá un par más:

• estaVacio(diccionario) -> boolean: indica si el diccionario está vacío, es decir no tiene ninguna entrada.
• contiene(diccionario, clave) -> boolean: indica si el diccionario contiene una entrada con la clave dada.

Dijimos entonces que estas operaciones conformaban la interfaz de un tipo de dato nuevo que estamos construyendo, llamado Diccionario. Y esta interfaz es lo único que debería interesarle a nuestras aplicaciones que necesiten trabajar con un diccionario.

No importa el cómo están implementadas estas funciones.

No importa cómo internamente se van a guardar las claves y los valores. Vimos dos posibles implementaciones, una con dos arreglos en paralelo (uno para la claves, y otro para los valores) y otra con un solo arreglo de Entradas, que cada una de éstas tendría una clave y un valor.

Vimos entonces que un Tipo Abstracto de Dato es:

• una definición de un tipo, en nuestro caso Diccionario
• más la definición de las operaciones que puedo realizar sobre el Diccionario
  • manteniendo los detalles de implementación interna ocultos.

Esto prové flexibilidad a las aplicaciones.

Con esta idea en mente vimos como implementar el TDA Dado, en el lenguaje C.

Pero antes nos dimos cuenta que nos faltaba algo. Si la estructura "real" del diccionario iba a depender de la implementación, nuestra aplicación no iba a poder crear un diccionario, si no que debería también delegarle esta responsabilidad a la implementación. Entonces agregamos una nueva operación:

• crear() -> Diccionario

Estas operaciones se suelen llamar constructores. Ya que son funciones que construyen una instancia del TDA.

TDA Dado

Definimos entonces el TDA dado:

• Tipo: Dado
• Operaciones:
  • nuevoDado( cantidadDeCaras, caras) -> Dado: sirve para construir un nuevo Dado. Le especificamos las caras, como una lista de números. Eventualmente en C va a ser un puntero a numero. Y como siempre que pasamos un puntero a varios elementos, necesitamos especificar el tamaño.
  • tirar(dado) -> cara: la operación principal del dado es poder tirarlo. Esto devuelve la cara que salió.
  • liberar(dado) -> void: por último, así como no podemos crear el dado, porque no sabemos cuánta memoria alocar, al no conocer desde afuera como guarda los datos, necesitamos tener una operación similar al "free", donde cada implementación del Dado va a encargarse de liberar todos los punteros que haya creado.

Creando el TDA en un proyecto DadoUniforme

Entonces creamos un proyecto de tipo librería:

File-> New-> C Project

Pero esta vez en el wizard seleccionamos la opción "Empty Project" bajo la carpeta "Static Library". Luego el nombre de proyecto etc.

Dentro del nuevo proyecto, llamémoslo DadoUniforme, hicimos un archivo Dado.h donde definimos el TDA Dado, independiente de la implementación:

#ifndef DADO_H_

#define DADO_H_

struct DadoStruct;

typedef struct DadoStruct Dado;

Dado * nuevoDado(int cantidadCaras, int* caras);

void liberar(Dado *);

int tirar(Dado * dado);

#endif /* DADO_H_ */

Luego hicimos otro proyecto, esta vez uno "normal", llamémoslo "UsoDado" con un único archivo Main.c

#include <stdio.h>

#include "Dado.h"

void tirarEImprimir(Dado * dado) {

    printf("NuevaTirada: %i\n", tirar(dado));

}

void jugar(int cantidadCaras, int* caras) {

    Dado * dado = nuevoDado(cantidadCaras,caras);

    int i;

    for(i=0; i < 30; i++) {

        tirarEImprimir(dado);

    }

    liberar(dado);

}

int main(int argc, char **argv) {

    int carasDadoComun[] = {1,2,3,4,5,6};

    printf("Dado Normal\n");

    jugar(6, carasDadoComun);

    int carasFibonacci[] = {1,2,3,5,8,13,21,34,55,89,144};

    printf("Dado Fibonacci\n");

    jugar(11,carasFibonacci);

    return 0;

}

Acá vemos como estamos usando el Dado, al crearlo y luego tirarlo 15 veces e ir imprimiéndolo.

Todo esto, sin siquiera haber implementado el Dado. Y por supuesto sin saber cómo estará implementado.

Es decir que nuestra aplicación quedó desacoplada de la implementación del TDA.

Configurando la dependencia entre el proyecto UsoDado y DadoUniforme

Para que esto compile tuvimos que, desde este proyecto hacer referencia al otro, para poder ver el archivo Dado.h

Para hacer esto, sobre el proyecto UsoDado:

• botón derecho "Properties"
• En la izquierda, menú "Project References"
  • Y a la derecha marcamos el proyecto DadoUniforme, que es el que queremos "ver".
• Luego en la misma ventana, pero menú de la izquierda "C/C++ General / Paths and Symbols"
  • A la derecha, seleccionamos la solapa "References" y ahí checkeamos también el proyecto "DadoUniforme".

Implementación de DadoUniforme

Ahora sí volvimos al proyecto DadoUniforme y creamos el archivo Dado.c con la implementación que tira el dado utilizando un número aleatorio (random).

#include "Dado.h"

#include <stdlib.h>

#include <time.h>

struct DadoStruct {

    int cantidadCaras;

    int* caras;

};

void iniciarSemillaRandom() {

    time_t t;

    time(&t);

    srand(t);

}

Dado * nuevoDado(int cantidadCaras, int* caras) {

    iniciarSemillaRandom();

    Dado * output;

    //reserva la memoria para el dado

    output = malloc(sizeof(Dado));

    //copia la cantidad de caras

    output->cantidadCaras = cantidadCaras;

    //reserva la memoria para las caras

    output->caras = malloc(cantidadCaras * sizeof(int));

    //copia los valores de las caras

    int i;

    for (i = 0; i < cantidadCaras; i++) {

        output->caras[i] = caras[i];

    }

    return output;

}

void liberar(Dado* dado) {

    free(dado->caras);

    free(dado);

}

int tirar(Dado * dado) {

    return dado->caras[rand() % dado->cantidadCaras];

}

Ahora sí, pudimos ejecutar el Main.c

Y vimos algo como:

Dado Normal

NuevaTirada: 1

NuevaTirada: 1

NuevaTirada: 1

NuevaTirada: 1

NuevaTirada: 6

NuevaTirada: 1

NuevaTirada: 4

NuevaTirada: 6

NuevaTirada: 5

NuevaTirada: 2

NuevaTirada: 4

NuevaTirada: 4

NuevaTirada: 4

NuevaTirada: 5

NuevaTirada: 5

...

Implementación alternativa: DadoCargado

Luego Leo mostró a modo de ejemplo una implementación del dado alternativa, como un dado "trucado", que favorecía una de sus caras el 50% de las veces. Es decir que el 50% de las veces saldrá siempre un mismo número, el otro 50% será un random.

El número "favorecido" será el más grande que le pasemos. En el caso del dado común, de 6 lados, será el número 6.

Para esto Leo había creado otro proyecto de tipo Static Library, como el DadoUniforme, ésta vez con nombre DadoCargado.

Dentro, tuvimos que copiar y pegar Dado.h, pero porque no encontramos una forma de poder reutilizarlo. En realidad es exáctamente el mismo .h

Pero además, teníamos un Dado.c que tenía esta implementación de dado "cargado".

#include "Dado.h"

#include <stdlib.h>

#include <time.h>

struct DadoStruct {

    int cantidadCaras;

    int* caras;

    int caraCargada;

};

void iniciarSemillaRandom() {

    time_t t;

    time(&t);

    srand(t);

}

Dado * nuevoDado(int cantidadCaras, int* caras) {

    iniciarSemillaRandom();

    Dado * output;

    //reserva la memoria para el dado

    output = malloc(sizeof(Dado));

    //copia la cantidad de caras

    output->cantidadCaras = cantidadCaras;

    //reserva la memoria para las caras

    output->caras = malloc(cantidadCaras * sizeof(int));

    //copia los calores de las caras y carga la cara más pesada

    int i;

    output->caraCargada = caras[0];

    for(i = 0; i < cantidadCaras; i++) {

        output->caras[i] = caras[i];

        //va guardando en cara cargada la cara más grande.

        if(caras[i] > output->caraCargada) {

            output->caraCargada = caras[i];

        }

    }

    return output;

}

void liberar(Dado* dado) {

    free(dado->caras);

    free(dado);

}

//El 50% de las veces sale la primer cara, el resto es uniforme

int tirar(Dado * dado) {

    if(rand()%2) {

        return dado->caraCargada;

    }

    else {

        return dado->caras[(rand() % (dado->cantidadCaras))];

    }

}

Acá hay algunos detalles no tan imporantes, como que para generar el random necesitamos primero setear una "semilla". Si alguien se quedó con ganas de saber más sobre la generación de números aleatorios puede arrancar por acá. Aunque no es objetivo de la materia.

También utilizamos el operador %, es decir módulo de la división para transformar un número muy grande, el generado aleatoriamente, en un número que vaya entre el 0 y la cantidad de caras del dado. Por ejemplo entre 0 y 5 para el dado regular, y entre 0 y 7 para el ejemplo de fibonacci.

Todo resto de la división entera es un número menor al divisor. (acá está la explicación matemática) con lo cual nos sirve perfecto para lo que queremos.

De hecho es muy común utilizar este operador para estos casos.

Volviendo. Aca entonces fuimos a las Propiedades de nuestro proyecto UsaDado y modificamos ambas cosas que mencionamos antes, en Project References ahora solo checkeamos DadoCargado, y lo mismo en la parte de C/C++ General.

Luego ejecutamos de nuevo el ejemplo y notamos que muchas veces salía el valor 6, por usar el dado cargado.

Dado Normal

NuevaTirada: 6

NuevaTirada: 6

NuevaTirada: 1

NuevaTirada: 6

NuevaTirada: 2

NuevaTirada: 6

NuevaTirada: 2

NuevaTirada: 5

NuevaTirada: 3

NuevaTirada: 6

NuevaTirada: 6

NuevaTirada: 6

NuevaTirada: 6

NuevaTirada: 6

NuevaTirada: 6

NuevaTirada: 4

NuevaTirada: 4

NuevaTirada: 6

NuevaTirada: 6

NuevaTirada: 6

Código Fuente

Adjunto acá un zip con los tres proyectos.

Para importarlos tendrán que descomprimirlo en su carpeta "workspace"

Y luego desde el eclipse File->Import-> Existing project into workspace.

Luego ir con el explorador de archivos que se va a abrir, hasta la carpeta workspace y seleccionar cada una de las carpetas de los tres proyectos.

Otro Ejemplo: Fracciones

En la página del sitio que ya nombramos más arriba, hay otro ejemplo de TDA, para definir un tipo de dato Fraccion, es decir un número que se expresa como la división de otros dos.

Pueden practicar hacerlo o ver ese mismo código como algo extra para sacarse dudas.

Próxima Clase y Trabajo Práctico

La clase que viene vamos a seguir viendo temas de la materia, pero por otro lado recuerden que según la planificación tenemos la entrega del trabajo práctico número 1.

Asumimos que están todos avisados, desde la primer clase en que pusimos a disposición la planificación. Ustedes son responsables de mirar la planificación y tener presente cuando son las fechas de entrega.

La intención es durante la clase ir pasando por los grupos a corregir con ustedes mismos. Así se hace más fácil poder preguntarles y que ustedes expliquen qué y cómo quisieron hacerlo. Además de nosotros poder sugerirles cambios/mejoras y explicarles criterios.

Entonces, traigan de alguna forma (pendrive, disco, o bien mándense por mail) el TP completo, así lo pueden abrir en clase.

Saludos !