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


Son también de alguna forma TDAs




Enteros, reales, caracteres, lógicos
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:



Y modificar y consultar los elementos. Ejemplo:


int A[20] o int *A;
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,


Si es un arreglo dinámico






El tamaño real debe ser determinado desde el inicio, lo cual es muy molestoso
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:



Comportamiento básico: A un ArrayU se debe poder






Básico: sin el cual no se puede trabajar con el TDA
Complementario: operaciones que facilitan el manejo del TDA
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ño
ArrayU *ArrayU_Crear (int tamanio, int inicial);


Eliminar
Dado un arreglo, se eliminara de memoria
void ArrayU_Eliminar(ArrayU **A);


Consultar
int 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:
OJO: ArrayU
solo servirá
para arreglos
de enteros
typedef struct{
int *Arreglo;
int nreal;
int inicial;
}ArrayU;
ARRAYU: NIVEL DE
APLICACION

Ahora que hemos construido nuestro nuevo TDA


Veamos un ejemplo de esto en el siguiente ejercicio


Podemos usarlo en un programa
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 IMPRIMIR
main(){
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
g
g
4
6
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”);
g
Mama
g
Papa
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 LOGICO

¿Qué representa el Generico?


A cualquier tipo de dato, ya sea básico como compuesto
Es decir
<generico> ::= <dato>
<dato>
::= <básico>|<compuesto>
<básico>
::= <int>|<float>|<double>|<char>|<string>
<compuesto>::= <arreglo>|<estructura>|<union>|<user_defined>
GENERICO: NIVEL DE
IMPLEMENTACION

Que un valor sea Generico implica que




Esto implicaría



Reserva de memoria dinámica y
Conversión explicita de un tipo a otro
En lenguaje C


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
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


Eliminar


Generico_Eliminar(Generico g);
Modificar y Consultar



Generico Generico_CrearEntero(int valor);
void Generico_AsignarEntero(Generico g, int valor);
int Generico_ObtenerEntero(Generico g);
Declaración

typedef void * Generico ;
GENERICO: EN C
1007
72
5
Generico g;
g = Generico_CrearInt(5);
G
Generico_SetInt(g,Generico_GetInt(g)+67);
2056
printf(“%d\n”, Generico_GetInt(g));
“Mama
“Mama”
y Papa”
Generico_Eliminar(g);
g = Generico_CrearString(“Mama”);
1343
strcpy(cad,Generico_GetString(g));
strcat(cad,” y Papa”);
“Mama
“Mama”
y Papa”
Generico_SetString(g, cad);
printf(“%d\n”, Generico_GetString(g));
Generico_Eliminar(g);
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,


Pero habría un problema para implementar esta
herramienta


Desear que se imprima todo el arreglo por pantalla
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);
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
void
void
void
ImprimirEntero(int *valor);
ImprimirCadena(char *cadena);
Estudiante_Imprimir(Estudiante *E);
Quebrado_Imprimir(Quebrado *Q);
main(){
ArrayU *A;
A = ArrayU_Crear(10);
//Se piden 10 Estudiante por teclado
//y se almacenan en A
ArrayU_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:



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:



button newbutton(char *text, rect r, actionfn fn);
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 IMPRESION
void 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