TDA ARRAYU

TDA ARRAYU

ESTRUCTURAS DE DATOS

OBJETIVOS

Definir un nuevo TDA utilizando las técnicas ya revisadas

Implementar TDAs usando un lenguaje de programación y

técnicas de modularización

Reconocer la utilidad de un tipo de dato Generico

Utilizar TDAs ya creados para resolver problemas

INTRODUCCION Los tipos de datos básicos

Enteros, reales, caracteres, lógicos Son también de alguna forma TDAs

Cuando se desea sumar dos enteros No es necesario conocer la representación binaria de cada valor

entero Solo debe conocerse el comportamiento que hace la suma: (+)

Básicamente todos los tipos de datos se pueden considerar TDAs

¿Qué ES UN ARREGLO? El arreglo es un tipo de dato compuesto Permite agrupar elementos del mismo tipo Permite acceder a CADA elementos utilizando su

posición, recordemos que se puede Consultar el valor de un elemento Modificar el valor de un elemento

Lenguaje C si nos permite trabajar con arreglos

ARREGLOS EN C C ya provee de una forma de trabajo con arreglos

En forma estática o dinámica, como se desee Podemos declararlos. Ejemplo:

int A[20] o int *A; Y modificar y consultar los elementos. Ejemplo:

A[5] = 4 o printf(“%d”, A[5])

Si el TDA Arreglo en C ya provee el comportamiento necesario ¿Por que crear otro tipo de dato que lo sustituya?

LOS PROBLEMAS Características negativas de un arreglo en C

Si es un arreglo estático, El tamaño real debe ser determinado desde el inicio, lo cual es muy molestoso

Si es un arreglo dinámico El uso de malloc para crearlo abarca una cierta “complejidad” que podriamos

ocultar Puedo intentar asignar valores a elementos fuera del rango del arreglo Los índices siempre comienzan desde 0 y eso no se puede cambiar El tamaño del arreglo no es parte del arreglo etc.…

Existen demasiadas características de los arreglos Que añaden complejidad al manejo de arreglos Recordemos la abstracción: quitar complejidad, dejar solo lo necesario

UN NUEVO TDA: ARRAYU

Una abstracción “arreglaría” estos detalles Crearíamos un nuevo tipo de dato que

Solo muestre lo que se necesita y esconda la complejidad

Podríamos crear el nuevo TDA para arreglos unitarios

ArrayU

DISEÑO DEL TDA: NIVEL LOGICO El diseño de un TDA implica

Determinar el comportamiento del mismo: operaciones Determinar la definición interna del mismo:

características Este diseño también se puede llamar

Nivel lógico del TDA Pensemos en el nivel lógico para

Nuestro nuevo arreglo: ArrayU

ArrayU: COMPORTAMIENTO Existen dos niveles de comportamiento:

Básico: sin el cual no se puede trabajar con el TDA Complementario: operaciones que facilitan el manejo del TDA

Comportamiento básico: A un ArrayU se debe poder Crearlo, de cualquier tamaño Destruirlo Asignar un valor a uno de sus elementos Consultar el valor de uno de sus elementos Consultar el tamaño máximo del arreglo

Comportamiento complementario Ordenarlo Buscar un elemento dado su valor, etc.

ArrayU: ESTADO Primero es útil pensar la definición de nuestro TDA Un arreglo es

Una colección de elementos finita y de tamaño fijo. A cada elemento se lo puede acceder por un índice

El índice del primer elemento puede comenzar desde un numero dado El índice del ultimo elemento seria igual a: indice_primero + tamaño -1

<arreglo> ::= {<elemento><inicial>, ... , <elemento><iterador>, <elemento><final>}

<iterador> ::= (<inicial>|<inicial>+1|<inicial>+2|...|<final>)

<inicial> ::= <entero_positivo>

<final> ::= <inicial>+<nreal>-1

<nreal> ::= <digito>{<digito>}

<elemento> ::= <dato>{<dato>}

TDAs: NIVEL DE IMPLEMENTACION Una vez completo el nivel lógico,

Podemos pasar al nivel de implementación Usando un lenguaje de programación determinado

Hay algunas consideraciones que tomar Estándar para nombrar TDAs y operaciones

Es preferible crear un estándar Útil para todos los TDAs que se vayan a crear Ejemplo: <nombre_TDA>_<nombre_funcion> o <nombre_funcion><nombre_TDA>

Uso de modularidad a nivel de archivo

MODULARIZACION DE ARCHIVOS En la programación estructurada, los TDAs se implementan en

módulos Un modulo normalmente esta compuesto por:

Interfaz o especificación, en lenguaje C, se refiere a los archivos .h: Contienen la declaración del nuevo tipo y Los prototipos de las operaciones que estarán disponibles

Implementación, en lenguaje C, se refiere a los archivos .c Contendrá el código fuente de cada operación Cada implementación o “forma de llevarse a cabo” de las operaciones, estarán

ocultas para el mundo exterior

En resumen, un TDA bien modularizado a nivel de archivo, ocupará Dos archivos, un .h y un .c, con el nombre del TDA

ARRAYU: NIVEL DE IMPLEMENTACION Crear

Dado un tamaño, ArrayU almacenara una arreglo de dicho tamañoArrayU *ArrayU_Crear (int tamanio, int inicial);

Eliminar Dado un arreglo, se eliminara de memoriavoid ArrayU_Eliminar(ArrayU **A);

Consultarint ArrayU_ GetElemento(ArrayU *A, int indice);Int ArrayU_GetTam(ArrayU *A);int ArrayU_GetInicial(ArrayU *A);Int ArrayU_GetFinal(ArrayU *A);

Modificar void ArrayU_SetElemento(ArrayU *A, int indice, int valor);

ARRAYU: NIVEL DE IMPLEMENTACION

Consideraciones Un arreglo es el conjunto de elementos Con un tamaño dado y un numero de índice inicial

Declaración:

typedef struct{int *Arreglo;int nreal;int inicial;

}ArrayU;

OJO: ArrayU solo servirá

para arreglos de enteros

ARRAYU: NIVEL DE APLICACION

Ahora que hemos construido nuestro nuevo TDA Podemos usarlo en un programa

Veamos un ejemplo de esto en el siguiente ejercicio Pedir n elementos por teclado, almacenarlos en un

arreglo y luego mostrar la mitad de cada valor ingresado No usaremos mas los arreglos que conocíamos

Usemos nuestra propia abstracción

LEER, CAMBIAR E IMPRIMIRmain(){

ArrayU *Datos;int n, valor;printf(¿Cuántos datos maximo desea ingresar?);n = GetInteger();Datos = ArrayU_Crear(n,1);for(i = ArrayU_GetInicio(*Datos); i <= ArrayU_GetFinal(*Datos);i++){ //Inicio i en el for desde 1, no desde 0

printf(“Ingrese el dato No.”, i);valor = GetInteger();ArrayU_SetElemento(Datos,i, valor); //Pido el elemento i

}for(i = ArrayU_GetInicio(*Datos); i <= ArrayU_GetFinal(*Datos);i++){

valor = ArrayU_GetElemento(*Datos,i)/2;ArrayU_SetElemento(Datos, i, valor);printf(“Mitad del elemento %d: “, valor);

} ArrayU_Eliminar(&Datos);

}

SOLO PARA ENTEROS ArrayU ha sido un éxito, pero

Lo implementamos solo para enteros Dos posibles soluciones

Crear un TDA para cada tipo de dato ArrayUI, solo para enteros, ArrayUF, para reales ArrayUS, para strings, etc.

Crear un tipo de dato súper general: Generico Modificar ArrayU para que sea un arreglo de cualquier tipo

de dato un arreglo de genericos

TIPO DE DATO GENERICO

Cualquier TDA que represente un conjuntos de datos, tendrá este problema ¿De que tipo son esos elementos? Si lo definimos de un tipo especifico, nuestro TDA quedará muy

limitado

¿Qué podemos hacer? Abstraernos y crear un Tipo de Dato Generico Este nuevo TDA permitirá representar cualquier tipo de dato, sea

un entero, un real, u otro TDA

¿Y COMO SE COMPORTARIA UN GENERICO? La idea es lograr “almacenar” cualquier tipo de

dato dentro de una variable de tipo Generico Una variable de tipo generico se puede crear

Pero al hacerlo, habrá que especificar memoria para que tipo de dato exactamente

Esto dependerá del tipo del valor que va a almacenar

También se le puede cambiar o consultar el valor que almacena

Generico g;g = CrearEntero(4);CambiarEntero(g, 6);g = CrearCadena(“Mama”);CambiarCadena(g, “Papa”);

4

g

g

Mama

g

Papa

6

g

GENERICO: NIVEL LOGICO Un tipo de dato Generico, debe permitir

Crear un Generico, escondiendo un valor que cualquier tipo Generico g; g = CrearEntero(4);

Eliminar una variable de tipo Generico Consultar y Modificar el valor escondido dentro

Modificar el valor escondido, Ej. Con enteros SetEntero(G,5);

Consultar el valor que el Generico almacena, Ej. Con Enteros valor = GetEntero(g);

GENERICO: NIVEL DE IMPLEMENTACION Que un valor sea Generico implica que

No debe ser de ningún tipo al ser declarado Y dependiendo de quien lo use, En algún momento se “convertira” al tipo deseado

Esto implicaría Reserva de memoria dinámica y Conversión explicita de un tipo a otro

En lenguaje C El único tipo de dato que no es NADA es el void

Entonces Una variable Generico, seria realmente de “tipo”: void *

Que al inicio no es de ningún tipo

void * puede apuntar a cualquier tipo de

variable

GENERICO: NIVEL DE IMPLEMENTACION Operaciones

Creación Generico Generico_CrearEntero(int valor);

Eliminar Generico_Eliminar(Generico g);

Modificar y Consultar void Generico_AsignarEntero(Generico g, int valor); int Generico_ObtenerEntero(Generico g);

Declaración typedef void * Generico ;

GENERICO: EN CGenerico g;

g = Generico_CrearInt(5);

Generico_SetInt(g,Generico_GetInt(g)+67);

printf(“%d\n”, Generico_GetInt(g));

Generico_Eliminar(g);

g = Generico_CrearString(“Mama”);

strcpy(cad,Generico_GetString(g));

strcat(cad,” y Papa”);

Generico_SetString(g, cad);

printf(“%d\n”, Generico_GetString(g));

Generico_Eliminar(g);

GG

5

1007

72

1007

“Mama”

2056

“Mama y Papa”

2056

“Mama”

1343

“Mama y Papa”

1343

GENERICO: NIVEL DE APLICACION Bien utilizado

El tipo de dato Generico puede ser sumamente útil A lo largo de todo el curso

Para usarlo hay que considerar Nunca olvidar que las conversiones serán necesarias Si las dejamos a un lado, el resultado será no esperado ni

deseado

REDEFINICION DE ARRAYU Necesitamos redeclarar el TDA ArrayU

Para definirlo como un arreglo de cualquier tipo de dato OJO: la definición en el nivel lógico sigue igual Solo cambiara el nivel de implementación

typedef struct{Generico *Arreglo;int nreal;int inicial;

}ArrayU;

ARRAYU GENERICO: NIVEL DE APLICACION Tratemos ahora de usar el ArrayU Generico

Apliquémoslo en el mismo ejemplo anterior: Pedir n elementos por teclado, almacenarlos en un

arreglo y luego mostrar la mitad de cada valor ingresado

main(){

ArrayU *Datos;

int n, valor;

Generico g;

printf(¿Cuántos datos maximo desea ingresar?);

n = GetInteger();

Datos = ArrayU_Crear(n,1);

for(i = ArrayU_GetInicio(Datos); i <=ArrayU_GetFinal(Datos);i++){ //Inicio i en el for desde 1, no desde 0

printf(“Ingrese el dato No.”, i);

valor = GetInteger();

g = Generico_CrearEntero(valor);

ArrayU_SetElemento(Datos,i, g); //Pido el elemento i

}

for(i = 1; i <= Datos.n ; i++){

g = ArrayU_GetElemento(Datos,i);

valor= Generico_GetEntero(g)/2;

Generico_SetEntero(g, valor);

printf(“Mitad del elemento %d: “,

Generico_GetEntero(g));

}

ArrayU_Eliminar(&Datos);

}

VENTAJAS Y DESVENTAJAS Ventajas

Logramos definir un arreglo mas funcional Siempre tiene consigo su tamaño, su índice inicial y Sirve para cualquier tipo de dato

Ocultamos todos los detalles.. “la verdad”, detrás de la abstracción

Desventajas Como estamos muy acostumbrados al arreglo normal Este parece poco necesario

ARRAYU: AÑADIR MAS COMPORTAMIENTO

Podríamos en algunos caso, Desear que se imprima todo el arreglo por pantalla

Pero habría un problema para implementar esta herramienta Considerando que nuestro arreglo es Generico

¿Qué problema/s podrían surgir al tratar de hacer esta herramienta?

LO QUE DESEAMOS Una herramienta que imprima un arreglo…

Que no le importe el tipo Analicemos que necesita esta función para cumplir bien su

propósito Necesitaría el arreglo, para poder imprimirlo y… Pero como sabría como imprimir cada elemento???

Cada elemento es Generico, ArrayU no conoce el tipo de dicho Generico, y por lo tanto, no puede imprimirlo

La función debería recibir : Un ArrayU, que es el que se desea imprimir Y “algo” que le indique como imprimir cada elemento del arreglo Pues desde dentro del TDA se desconoce como hacerlo

UNA PRIMERA SOLUCIÓN Que la función reciba una enumeracion que indique

de que tipo es el ArrayU void ArrayU_Imprimir(ArrayU *A, TipoDato tipo); En ese caso, la función debería elegir como imprimir el

arreglo, dependiendo del tipo:

void ArrayU_Imprimir(ArrayU *A, TipoDato tipo){for(i = 0; i< A->tmax; i++){

switch(tipo){int

*valor_int;char

*cadena;Estudiante

*E;Quebrado *Q;case ENTERO:

valor_int = A->Elementos[i];

printf(“%d\n”, *valor_int);

break;case CADENA:

cadena = A->Elementos[i];

printf(“%s\n”, cadena);

break;case

ESTUDIANTE:E =

A->Elementos[i];

Estudiante_Imprimir(E);

break;case

QUEBRADO:Q =

A->Elementos[i];

Quebrado_Imprimir(Q);

break;}

}

}

void ArrayU_Imprimir(ArrayU *A, TipoDato tipo){for(i = 0; i< A->tmax; i++){

switch(tipo){int

*valor_int;char

*cadena;Estudiante

*E;Quebrado *Q;case ENTERO:

valor_int = A->Elementos[i];

printf(“%d\n”, *valor_int);

break;case CADENA:

cadena = A->Elementos[i];

printf(“%s\n”, cadena);

break;case

ESTUDIANTE:E =

A->Elementos[i];

Estudiante_Imprimir(E);

break;case

QUEBRADO:Q =

A->Elementos[i];

Quebrado_Imprimir(Q);

break;}

}

}

DESVENTAJAS Son obvias:

Esta función no sirve para cualquier tipo de dato Para que ArrayU soporte un nuevo tipo de dato hay que

modificar la función Buscar al creador del TDA Pedirle que añada un case para el nuevo tipo de dato Pedirle que recompile la librería Pedirle el nuevo .h y el nuevo .lib

MUCHO TRABAJO!! Esta solución no favorece la expandibilidad del TDA

SEGUNDA SOLUCIÓN Implementar la función igual que si conociera el tipo

de dato Enfocarnos en el algoritmo, no en el tipo de dato

Pero.. Aquello que no sepamos como hacer Porque desconocemos el tipo de dato Lo debemos recibir como parametro

Y no seria un valor Sería una acción una función, como parametro

void ArrayU_Imprimir(ArrayU *A, procfn Imprimir){for(i = 0; i< A->tmax; i++){

//Imprimir A->Elementos[i], NO SE COMO HACERLO

//Llamo a la funcion Imprimir recibida como parametro

Imprimir(A->Elementos[i]);

}

}

void ArrayU_Imprimir(ArrayU *A, procfn Imprimir){for(i = 0; i< A->tmax; i++){

//Imprimir A->Elementos[i], NO SE COMO HACERLO

//Llamo a la funcion Imprimir recibida como parametro

Imprimir(A->Elementos[i]);

}

}void ImprimirEntero(int *valor);void ImprimirCadena(char *cadena);void Estudiante_Imprimir(Estudiante *E);void Quebrado_Imprimir(Quebrado *Q);

main(){ArrayU *A;A = ArrayU_Crear(10);//Se piden 10 Estudiante por teclado//y se almacenan en AArrayU_Imprimir(A, Estudiante_Imprimir);

}

void ImprimirEntero(int *valor);void ImprimirCadena(char *cadena);void Estudiante_Imprimir(Estudiante *E);void Quebrado_Imprimir(Quebrado *Q);

main(){ArrayU *A;A = ArrayU_Crear(10);//Se piden 10 Estudiante por teclado//y se almacenan en AArrayU_Imprimir(A, Estudiante_Imprimir);

}

FUNCIONES CALLBACKS Es una herramientas de programación que nos ofrece

lenguaje C Permite crear un tipo de dato que describa una función

En forma muy genérica Se indica tipo de dato de retorno Se indica los tipos de datos de entrada Ejemplo:

typedef TipoRetorno (*Nombre_Nuevo_Tipo)(<valores de entrada>);

Cualquier función que coincida con este prototipo Puede decirse que pertenece al nuevo tipo de dato declarado

EJEMPLO: LA GRAPHAPP El prototipo de la función que crea un nuevo botón es:

button newbutton(char *text, rect r, actionfn fn); Recibe un texto, un rectángulo y al parecer una variable de tipo

actionfn Actionfn debe ser un nuevo tipo de dato, su declaración es:

typedef void (*actionfn)(button b); Esto indica que cualquier función que coincida con el prototipo declarado para

actionfn será de tipo actionfn Ejemplo:

void CalcularSalarios(button b);//….button b;b = newbutton(“Aceptar”, rect(10,10,10,10), CalcularSalarios);

SU UTILIDAD Ese mecanismo nos va a permitir

Crear funciones que necesiten llamar a otras funciones Volviendo a nuestro caso,

La función callback que necesitamos cumplirá la tarea de imprimir un dato Generico:

typedef void (*Generico_Imprimir)(Generico);

Cualquier función que tenga este prototipo caerá en este tipo. Ejemplo:

void Imprimir_Entero(int *a); o void Imprimir_String(char *s);

USANDO UNA FUNCION COMO PARAMETRO Nuestra función para imprimir un ArrayU quedaría entonces

void ArrayU_Imprimir(ArrayU *A, Generico_Imprimir fn);

La implementación de esta función quedaría algo como:

void ArrayU_Imprimir(ArrayU *A, Generico_Imprimir fn){

int i;

for(i = 0; i < A->nreal;i++){

fn(ArrayU_ElemC(A,i););

}

}

LLAMANDO A LA IMPRESIONvoid Imprimir_Entero(int *valor);

main(){

ArrayU *Datos;

int n, valor;

Generico g;

printf(¿Cuántos datos maximo desea ingresar?);

n = GetInteger();

Datos = ArrayU_Crear(n,1);

for(i = ArrayU_Inicio(Datos); i <= ArrayU_Final(Datos) ;i++){

printf(“Ingrese el dato No.”, i);

valor = GetInteger();

g = Generico_CrearInt(valor/2);

ArrayU_SetElementos(Datos,i,g);

}

ArrayU_Imprimir(Datos, Imprimir_Entero);

ArrayU_Eliminar(&Datos);

}

void Imprimir_Entero(int *valor){

printf(“%d”, *valor);

}

VENTAJAS DEL CALLBACK Puedo definir funciones “genericas”

A través de la definición de tipos de datos de funciones

Son útiles cuando un procedimiento que se ejecutará es variable en el problema Todos los procedimientos posibles de llamar Deben tener el prototipo en común

TDA ARRAYU

Documents

Transcript of TDA ARRAYU