TECNICATURA EN PROGRAMACIÓN

ALGORITMOS Y ESTRUCTURAS DE
DATOS II
GUIA DE LA UNIDAD Nro. 1
CONCEPTOS BÁSICOS
Contenidista: ING. MARIANO APREA
 INDICE – UNIDAD 1:

1. CONCEPTOS BÁSICOS..................................................................................................... 6

1.1. TIPOS DE DATOS............................................................................................................... 6

FORO ........................................................................................................................................... 10
FORO ........................................................................................................................................... 14
ACTIVIDAD 1 (Autoevaluación) ....................................................................................... 18
1.2. SISTEMAS DE TIPOS ..................................................................................................... 18
1.3. GESTIÓN DE LA MEMORIA ........................................................................................ 22
1.4. INTRODUCCIÓN A TIPOS ABSTRACTOS DE DATOS ........................................ 25
ACTIVIDAD 2 (Tarea) ........................................................................................................... 36
SINTESIS DE LA UNIDAD .................................................................................................... 37

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 2

MAPA DE LA UNIDAD 1: CONCEPTOS BÁSICOS

PROPÓSITOS

En esta unidad nos proponemos hacer un repaso y profundizar sobre conceptos básicos de
la programación adquiridos en cursos anteriores para facilitar el proceso de aprendizaje al
tratar con estructuras de datos complejas; y trabajaremos con énfasis en uno de los
principios más importantes del diseño de sistemas que se conoce como abstracción.

OBJETIVOS
✓ Diferenciar los lenguajes compilados de los interpretados
✓ Analizar las bases de algunos de los paradigmas de programación más populares
✓ Enumerar y clasificar los tipos de datos predefinidos en los lenguajes
✓ Definir nuevos tipos de datos a partir de existentes
✓ Describir los diferentes sistemas de tipo que incorporan los lenguajes de
programación
✓ Diferenciar los tipos de variables según el momento de asignación de memoria
✓ Modelar soluciones correctas de problemas del mundo real a través de Tipos
Abstractos de Datos

CONTENIDOS

1. CONCEPTOS BÁSICOS
Unidad de repaso

1.1. TIPOS DE DATOS

1.1.1. ¿Por qué necesitamos definir Tipos de Datos?
1.1.1.1. Generaciones de Lenguajes
1.1.1.2. Paradigmas de programación
1.1.1.3. Abstracción
1.1.2. Tipos básicos y estructurados
1.1.2.1. Punteros

1.2. SISTEMAS DE TIPOS

1.2.1. Estático vs Dinámico
1.2.2. Fuerte vs Débil

1.3. GESTIÓN DE LA MEMORIA

1.3.1. La Pila de Ejecución
1.3.2. La Memoria Dinámica (HEAP)

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 3

 1.4. INTRODUCCIÓN A TIPOS ABSTRACTOS DE DATOS
1.4.1. Conceptos de diseño
1.4.1.1. Encapsulamiento
1.4.1.2. Ocultamiento de la información
1.4.2. Necesidad de definir un TAD
1.4.3. Operaciones de un TAD
1.4.4. Igualdad en el TAD
1.4.5. Creando un TAD

PALABRAS CLAVES

Tipos de datos – Tipos Abstractos de Datos – Sistema de Tipo – Tipificación Fuerte –

Tipificación Débil – Chequeo de Tipos – Tiempo de ejecución – Tiempo de compilación –
Abstracción – Encapsulamiento – Ocultamiento de Información – Constructores –
Proyectores – Modificadores – Destructores

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 4

BIBLIOGRAFÍA

AHO, A. - HOPCROFT, J. - ULLMAN, J. (1998) Estructuras de Datos y Algoritmos. Naucalpan

de Juárez, Edo. De México: Addison Wesley Longman

CORMEN, T. - LEISERSON, C. – RIVEST, R. – STEIN, C. (2009). Introduction to Algorithms.

(Third Edition). The Mit Press.

WIRTH, N. (1986). Algoritmos y Estructuras de datos. Prentice Hall Hispanoamericana.

BIBLIOGRAFÍA COMPLEMENTARIA

ABELSON, H. – SUSSMAN, G. J. (1996). Structure and Interpretation of Computer Programs;

2nd Edition. The MIT Press.

CARDELLI, L. – WEGNER, P. (1985) On Understanding Types, Data Abstraction, and

Polymorphism. Computing Surveys, Vol 17 n. 4, pp 471-522

LISKOV, B. – ZILLES, S. (1974) Programming with Abstract Data Types, SIGPLAN Notices

PIERCE, B. (2002) Types and Programming Languages, The MIT Press

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 5

1. CONCEPTOS BÁSICOS
El estudio de esta unidad servirá de base para avanzar luego con la implementación de
soluciones complejas. Comenzaremos trabajando sobre conceptos aprendidos en el curso
previo de Algoritmos y Estructuras de Datos I y profundizaremos sobre algunos de ellos
para facilitar la comprensión de los temas que veremos más adelante.

COMENCEMOS ABORDANDO LOS PRIMEROS OBJETIVOS

✓ Diferenciar los lenguajes compilados de los interpretados

✓ Analizar las bases de algunos de los paradigmas de programación más populares
✓ Enumerar y clasificar los tipos de datos predefinidos en los lenguajes
✓ Definir nuevos tipos de datos a partir de existentes

1.1. TIPOS DE DATOS

Uno de los conceptos más importantes en el campo de la programación son los tipos de
datos, los cuales proveen varios atributos al software construido. Seguramente usted ya
conoce su definición y los ha utilizado en asignaturas previas, pero quisiera que veamos en
detalle algunas consideraciones que serán de gran relevancia antes de abordar otros
conceptos, entre ellos, la recursión.

1.1.1. ¿Por qué necesitamos definir Tipos de Datos?

Comencemos imaginando una situación donde se le solicita diseñar un sencillo programa

que permita sumar dos números. Obviamente, esta función resulta trivial para los lenguajes
modernos, donde ya se encuentra implementada y lista para consumir por el desarrollador.

Aun así, es posible que nos encontremos con la necesidad de programar nuestra propia
función suma, por ejemplo, en sistemas embebidos donde no se disponga de un lenguaje
prexistente para un hardware específico.

Veamos ahora una de las complicaciones que pueden surgir como consecuencia de la
implementación de dicha función. En primer lugar, usted podría definir la función suma con
dos parámetros de entrada y la misma devolverá un valor con el resultado. Le propongo
reflexionar sobre las siguientes preguntas:

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 6

 ¿Qué complicación podría aparecer si los parámetros de entrada no tienen un tipo
de dato asociado?
¿Con qué problema podríamos encontrarnos si el valor de retorno no tiene un tipo
asociado?

Este sencillo ejemplo permite demostrar la importancia de los tipos de datos. En primer
lugar, si no definimos el tipo de datos de los parámetros, estaremos realizando una
operación sobre dos valores donde asumimos que tienen una representación
preestablecida. Este supuesto es realmente muy fuerte, ya que la función será correcta
siempre y cuando los valores establecidos como parámetros tengan una representación
consistente con la implementación de la función.

Por ejemplo, si usted decide implementar la función suma para dos números enteros, en el
programa no disponemos de ninguna restricción que un usuario de la función realice la
suma de dos números reales, imaginarios, complejos, etc. Por lo tanto, el usuario tiene
libertad absoluta en asignar valores para dichos parámetros y la función suma devolverá un
valor que no siempre será el correcto, según la especificación de nuestra operación.

Lo mismo puede decirse para el valor de retorno, ya que el usuario puede interpretar dicho
valor con total libertad. Sería posible intentar realizar la suma de dos cadenas y esperar
como resultado la cantidad de caracteres de ambas cadenas.

Claramente, no es el resultado que devolverá la función según se especificó.

Es cierto que los ejemplos son un tanto obvios, ya que se podría argumentar que para la
implementación de la función suma existe un documento que describe qué valores espera y
qué valores retorna. El problema yace en que dependemos de la buena voluntad y atención
del usuario para que utilice de forma correcta la función que hemos definido, porque no
tendremos forma de comprobarlo desde nuestra implementación.

Recuerde que, si no se dispone de un tipo de datos, estaremos trabajando con

expresiones sin forma, o más precisamente, con un conjunto de bits que pueden
representar diferentes conceptos dependiendo quien los interprete.

Los tipos de datos determinan los valores que puede adoptar una
entidad y cuáles son las operaciones que se pueden aplicar sobre la
misma

Las entidades a las que nos referimos en el campo de la programación son análogas a las
utilizadas en las matemáticas: expresiones, funciones (retorno), variables y constantes.

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 7

Generaciones de Lenguajes

En los comienzos de la programación, las computadoras completaban las tareas diseñadas

a través de la ejecución secuencial de instrucciones. Este fue el primer paradigma, conocido
como Programación No Estructurada, y se basaba un único flujo de ejecución donde sólo
era posible realizar saltos a distintos puntos del mismo (utilizando la conocida sentencia
GOTO). En aquellos tiempos las instrucciones se escribían en código máquina, es decir, en
un código que sólo podía ser interpretado por el hardware para el cual se definía. El lenguaje
entonces se componía de un conjunto de instrucciones dedicadas y era propio de cada
modelo de computadora. Se los conoce como lenguajes de primera generación y es donde
se puede programar en un nivel más bajo (más cercano al hardware).

Los tipos de datos aún no estaban implementados, sino que el intercambio de información
se realizaba mediante la escritura y lectura de registros. El contenido de los registros tenía
un límite sin dudas, pero no tenía una forma asociada. Era posible escribir cualquier
combinación binaria en el mismo. Por ejemplo, la computadora utilizada en la misión Apollo
de la NASA (AGC) tenía codificada todas sus instrucciones mediante una memoria fija
(ROM), compuesta por una grilla de núcleos magnéticos en forma de toroide que se cosían
a mano con alambres de cobre para definir la dirección del campo (0/1 en representación
binaria). Es evidente que en aquellas épocas el lenguaje máquina presentaba un esfuerzo de
implementación importante.

Los lenguajes de segunda generación incorporan un proceso de transformación donde se

traduce un código fuente al código máquina para su ejecución, denominado ensamblaje. Es
por ello por lo que se lo conoce como código ensamblado. La principal ventaja frente a la
generación de lenguajes previa radica en que se dispone de un lenguaje de mejor
interpretación para el desarrollador y es posible escribir y leer las instrucciones sin la
necesidad de saber cómo está construida la computadora donde correrán. Aun así, el código
ensamblado continúa siendo dependiente de la arquitectura subyacente y el programador
es responsable de gestionar en detalle los recursos de esta, como lo son la unidad de
procesamiento y los registros de memoria.

Hasta ese momento, se mantenía el mismo paradigma de programación. Es a partir de los

lenguajes de tercera generación que aparece un nuevo paradigma llamado Programación
Estructurada. Este nuevo enfoque incorpora conceptos clave como las estructuras de
control del flujo y las subrutinas.

En la programación no estructurada, toda ejecución de instrucciones era secuencial, una

serie de pasos, a excepción de la sentencia de salto que permitía interrumpir dicho flujo para
continuar en otro lugar del programa. Las estructuras de control incorporadas fueron las de
selección (si-entonces-sino) y de iteración (para-mientras-repetir), permitiendo lograr
programas más compactos y comprensibles. El concepto de subrutinas abrió el camino a
paradigmas de diseño como divide y vencerás (divide & conquer), descomponiendo así
problemas complejos y reduciendo la necesidad de escribir código repetido.

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 8

Las ventajas de esta generación de lenguajes no sólo se suscriben al diseño de programas.
Una de las más importantes novedades yace en que se elimina la dependencia del código
fuente con la arquitectura de la máquina. Por lo tanto, un programador ya no necesita
estudiar el código ensamblado para cierto controlador o procesador, sino que puede
aprender un lenguaje que eventualmente pueda ejecutarse en diversas máquinas sin
la necesidad de conocer su arquitectura interna. Es necesario así un proceso de
transformación similar al ensamblado previo para realizar la traducción del código fuente
al código máquina, por lo cual el programador ya no tiene un acceso directo a las
instrucciones propias del procesador y tampoco necesita gestionar detalles internos como
el movimiento de datos entre registros.

Como era de esperarse, en esta generación de lenguajes aparecen los tipos de datos. Dado
que el desarrollador ya no debe operar a bajo nivel con la memoria de la máquina, se
dispone de ubicaciones de almacenamiento dedicadas a ciertos valores de datos. Es
necesario entonces que el lenguaje sepa interpretar el tipo de datos asociado a dichas
ubicaciones, de forma que pueda realizar la carga y descarga en memoria correctamente.

Dentro de los lenguajes de tercera generación nos encontramos con dos clasificaciones que
se determinan según el momento en el cual se realiza la transformación a código máquina.
Un lenguaje compilado realiza dicha transformación en una instancia intermedia, previa a
la ejecución del programa.

El desarrollador escribe el código fuente en cierto lenguaje y luego un compilador lo traduce

a código máquina para su eventual ejecución. La tarea del compilador es muy importante
ya que puede realizar verificaciones sintácticas y semánticas previo a la ejecución de un
programa, lo cual permite identificar problemas de forma temprana y evitar eventos
indeseados. Inclusive, al disponer de información acerca de los tipos de datos utilizados, el
compilador puede asignar las distintas ubicaciones en memoria para realizar la carga y
descarga de los datos eficientemente. Todas las acciones que lleva a cabo el compilador
ocurren en la instancia de compilación o, como suele decirse, en tiempo de compilación.

Existen otro tipo de lenguajes que simplemente no tienen un proceso de compilación

asociado, se los denomina lenguajes interpretados. En este caso, la transformación a
código máquina la realiza un intérprete en el momento que se ejecuta cada bloque de código
o sentencia, según la implementación particular de cada lenguaje. No se dispone de la
instancia intermedia que se puede encontrar en lenguajes compilados, por lo cual todas las
tareas de validación y conversión de código se realizan en lo que se llama tiempo de
ejecución. Debido a que no se genera el código máquina, se puede decir que los lenguajes
interpretados ofrecen la mayor independencia frente a la arquitectura donde corren, ya que
sólo requieren disponer de un intérprete que los ejecute.

Entonces, si existe un intérprete implementado para cierta arquitectura, el código fuente

podrá ser ejecutado sin problemas, dando lugar a un lenguaje portable (cross-platform).

También es posible encontrar lenguajes que incorporan ambas técnicas, como lo es el caso
de Java, donde existen dos procesos de compilación: el primero desde código fuente al

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 9

bytecode de Java (código interpretable por la JVM), y el segundo del bytecode a código
máquina. La segunda fase de compilación es en realidad una técnica llamada Just In Time
Compilation (JIT) que realiza la Java Virtual Machine (JVM) al momento de ejecutar el código
precompilado en bytecode, la cual puede evitarse y así interpretar directamente el
bytecode. Se verá más adelante al introducir el lenguaje Java.

Implementación Tiempo de Tiempo de

Compilación Ejecución
Lenguaje Código Fuente Código
Compilado Compilado Código Máquina

Código Fuente
Lenguaje
Interpretado

FORO
Ahora le proponemos en el Foro que se encuentra en el campus algunas preguntas para
que comparta sus ideas con sus colegas en el foro.

Paradigmas de Programación

Cada lenguaje de programación fue diseñado para ofrecer una o más soluciones a un
conjunto de problemas abordándolos desde cierta perspectiva. En algunos casos la
perspectiva es única y en otros es posible que el lenguaje permita construir soluciones
desde más de una. Estas perspectivas se diferencian o caracterizan de acuerdo al estilo de
programación o formas de pensar los problemas. Si bien no existe una taxonomía
generalizada de todos los paradigmas de programación existentes, vamos a describir
algunos de los más populares para poder entender cuáles son sus ventajas y desventajas
básicas.

Es importante comprender que un paradigma no es mejor o peor que otro, sino que puede
resultar más adecuado (o no) que otro para cierta situación.

El paradigma de programación con el que más se ha trabajado hasta el momento es

claramente el paradigma estructurado. Prácticamente todo lo enseñado se apoya en este

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 10

paradigma ya que suele ser útil para traducir soluciones procedimentales a un programa.
Por ejemplo, al intentar resolver un problema que requiere completar ciertas tareas, el
programador piensa la solución basada en desarrollar un programa que involucre llamar a
subrutinas o subprogramas que modelen la solución de aquellas tareas. Esta
descomposición puede resultar en modularizar inclusive un programa donde existan tareas
repetitivas, lo cual lleva a la reutilización.

Ese conocido paradigma surge de uno previo que se basa en modelar soluciones a partir de
cambios de estado del programa, es decir, considerando modificaciones sobre valores
asignados en una memoria. A este viejo paradigma se lo denomina imperativo. Por lo tanto,
un lenguaje que soporta un paradigma de programación estructurado también soporta al
imperativo. Es por ello que se suele hablar de forma más amplia y en general del paradigma
imperativo. Un ejemplo de lenguaje de programación que soporta este paradigma es el de
código ensamblado, donde se diseñan soluciones a través de instrucciones secuenciales que
modifican el estado de la memoria del programa.

Este concepto de estado del programa es clave para diseñar las soluciones ya que se
pretende establecer una relación entre instrucciones, rutinas o bloques de código
(funciones o procedimientos) y cómo interactúan a través de resultados de sus
ejecuciones que se manifiestan en la memoria.

Esto nos dice que la ejecución de cierto bloque de código puede producir algún cambio en
el programa, es decir, tiene un efecto más allá del resultado explícito que puede dar (en el
caso de que sea una función). Por ejemplo, en un paradigma imperativo puedo definir una
función que retorne un valor y a la vez modifique una variable en memoria.

Ahora bien, si pensamos en dar soluciones basadas en procedimientos veremos que

claramente estamos encarando el problema desde un paradigma imperativo, ya que un
procedimiento no retorna un valor ante su ejecución, sino que justamente produce algún
cambio en el programa. Una consecuencia de este comportamiento es que se tiene una
temporalidad en la ejecución del programa, no resulta indistinto invocar una sentencia
antes o después de otra, el orden en el cual se ejecutan es relevante.

Un contraste evidente con esta forma de diseñar programas está en el paradigma

funcional, donde el problema se resuelve a través de la evaluación de funciones.

Notemos la diferencia fundamental entre lo que antes llamábamos ejecutar instrucciones o

bloques, frente a la evaluación de una función. En este caso, debemos pensar las soluciones
en evaluar una función con ciertos parámetros para obtener un resultado, el cual
obviamente puede utilizarse como parámetro de otra función para dar lugar a programas
más complejos. Por lo tanto, un lenguaje funcional, como pueden ser Haskell o Lisp, evalúa
funciones para obtener expresiones de forma similar a cómo se trabaja en la matemática.
Esto ofrece una gran ventaja frente al paradigma imperativo, ya que una función siempre
retornará el mismo resultado al ser evaluada con los mismos parámetros, lo cual se
desprende de la propiedad de transparencia referencial, propia de este paradigma.

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 11

 Entonces, la transparencia referencial permite que la evaluación de una función no
dependa del momento dentro del programa o del orden en el cual se la llama, sino que
depende sólo de sus parámetros.

El resultado de esta propiedad es muy potente porque nos permite trabajar con absoluta
independencia en cada función sin la necesidad de contemplar estados del programa o
efectos colaterales, es decir, nos permite centrarnos en diseñar la función para resolver
estrictamente lo que está especificado que haga. Entonces este paradigma nos facilitará el
mantenimiento y la verificación formal del programa.

Al hablar de verificación formal nos referimos a apoyarnos en reglas y propiedades para dar
validez a la especificación de un programa de forma similar a una demostración matemática.

En este curso no estaremos viendo cómo especificar un programa, pero para ello
mencionaremos que existe un paradigma declarativo que permite diseñar soluciones sin
contemplar detalles de implementación.

Si evitamos entrar en detalles de cómo implementar un programa, podremos hacer foco en

qué debe hacer el programa para satisfacer los requerimientos. Esta definición del qué debe
hacerse es lo que se describe como especificación.

Entonces, un lenguaje que soporte el paradigma declarativo hará foco en establecer las
reglas y propiedades bajo las cuales se resuelve un problema, sin dar importancia a
cuestiones de temporalidad, capacidad de recursos, estados del programa, etc. Nos
permite abstraernos de estos detalles propios de la implementación imperativa. Esto
último podría decirse que se comparte también con el paradigma funcional.

A lo largo de esta materia continuaremos trabajando con el paradigma imperativo o

estructurado, pero también abordaremos el paradigma orientado a objetos. Si bien
ambos comparten el concepto principal de estado del programa, este último ofrece una
abstracción mayor porque incorpora de forma nativa todos los beneficios de trabajar con
TADs y agrega la idea de herencia.

Lo analizaremos con más detalle más adelante….

Abstracción

El proceso de construcción de un sistema implica una serie de pasos o actividades que se

definen en el marco de la ingeniería de software.

A grandes rasgos, el ciclo de vida del software se divide en diferentes etapas: Elicitación,
Análisis, Diseño, Implementación, Pruebas, Lanzamiento y Mantenimiento.

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 12

Dependiendo del proceso elegido, dichas etapas pueden ejecutarse secuencialmente, con
una o varias iteraciones, en forma espiralada, entre otros. En esta materia nos centraremos
en la implementación de algoritmos y estructuras, pero es necesario comprender algunos
conceptos básicos de las actividades previas.

De la misma forma que un arquitecto realiza el diseño de un edificio, con su estructura base
y diversos elementos que la componen, un ingeniero de software recorre un proceso similar
para construir un producto.

El arquitecto debe contemplar algunos aspectos claves del edificio antes de comenzar su
construcción (implementación), para lo cual utiliza modelos que son plasmados en diversos
planos. Los modelos permiten así representar un diseño de lo que se desea elaborar, cada
uno de ellos haciendo hincapié en ciertas características. Por ejemplo, en etapas tempranas
del proyecto, el arquitecto comienza dibujando un plano que describe la estructura inicial
describiendo las plantas y sus dimensiones, pero sin precisar el detalle de cómo serán las
terminaciones de los pisos o paredes internas. Lo relevante hasta aquí es determinar la
factibilidad del proyecto en el suelo del terreno y la habilitación según los metros cuadrados
a construir, junto con algunos detalles particulares del dominio que serán de utilidad para
un calculista. Esta distinción es muy importante ya que sería muy complejo realizar un plano
de un edificio con todos los detalles incluidos, sería una gran cantidad de información que
no es necesaria para ciertas actividades.

Este proceso de seleccionar características relevantes a representar de un problema se lo

conoce como abstracción.

La abstracción es un mecanismo que permite expresar lo relevante

y omitir detalles irrelevantes

Llevemos este concepto a la construcción del software. Un desarrollador necesita modelar

inicialmente una solución a un problema de la realidad, es decir, realizar una virtualización
de la misma. Un lenguaje de programación ya ofrece varias abstracciones que nos facilitan
la implementación, por ejemplo, los tipos de datos primitivos. Un tipo de dato Entero es una
abstracción, tanto a nivel de dato como a nivel de funcionalidad. En primer lugar, un tipo de
dato Entero representa el conjunto de todos los números enteros que nos servirán para
construir nuevas abstracciones (edad, días del mes, número de piso, etc). No necesitamos
conocer el detalle de cómo se estructura un Entero en el lenguaje de programación, podría
estar representado internamente como un número binario, un conjunto de celdas de
memoria, etc. No es relevante para nosotros conocer dicha representación interna, sino que
hacemos uso del concepto abstracto de número entero. En segundo lugar, las operaciones
asociadas a los números enteros también se encuentran abstraídas, como lo son la suma,
resta, producto, igualdad, entre otras. Por lo tanto, cuando deseamos comprobar que dos

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 13

números enteros son iguales, no es relevante conocer cómo se realiza dicha comparación
internamente.

Al final de esta unidad veremos más ejemplos de cómo se construyen dichos modelos, pero
es importante tener en cuenta que no existe un método genérico que nos permita aplicar
este concepto. Se requiere práctica y conocimiento del dominio para efectuar una
abstracción correcta.

FORO

Le pedimos que a continuación participe del Foro que le proponemos en el campus para
intercambiar análisis con sus compañeros.

1.1.2. Tipos básicos y estructurados

Como usted ya conoce, los tipos de datos se clasifican en básicos o estructurados.

Generalmente, los tipos básicos, también conocidos como tipos primitivos, ya vienen
incorporados en los lenguajes de programación de forma nativa. La construcción de nuevos
tipos de datos que nos permitirán generar nuevas abstracciones apropiadas para resolver
un problema dado se apoyará en estos tipos de datos predefinidos. A continuación, se
recuerdan los más comunes.

Tipo de Dato Básico Valores

ENTERO Números enteros
REAL Números reales
CARACTER Símbolo de texto que pertenece a cierto alfabeto
(Unicode, ASCII, etc)
ENUMERABLE / ENUM Conjunto de elementos constantes
LÓGICO / BOOLEAN VERDADERO | FALSO

Los tipos de datos estructurados son aquellos que se construyen a partir de los tipos de
datos primitivos, por lo tanto, suelen denominarse tipos de datos compuestos. Al igual que
en el caso de los tipos básicos, éstos también suelen definirse nativamente en los lenguajes
y permiten generar estructuras de datos más avanzadas.

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 14

 Tipo de Dato Valores
Compuesto
ARREGLO Conjuntos de elementos (indexados) del mismo
tipo de dato. Puede ser de varias dimensiones.
REGISTRO Producto cartesiano de los elementos que lo
componen
UNION Unión conjunta de los elementos que lo
componen

Punteros

Un tipo de dato especial que algunos autores lo clasifican como primitivo es el puntero o
referencia. Si bien existe una diferencia entre la definición de puntero y referencia según
el lenguaje que utilicemos, por el momento nos referiremos a este tipo de dato por
cualquiera de los dos nombres. Se dice que es un tipo de dato especial porque incorpora un
concepto extraño: la ausencia de valor.

Un puntero puede contener entonces un valor asociado a un tipo de dato específico o

no contener valor alguno.

En la programación funcional se lo conoce como el tipo de dato paramétrico Maybe(a),

donde a es una variable de tipo que identifica el tipo de dato al cual referencia el puntero.
Exploraremos los tipos paramétricos más adelante.

El puntero cobra gran importancia para definir estructuras dinámicas que pueden variar en
tamaño en tiempo de ejecución. Hasta el momento, todos los tipos de datos que habíamos
visto tienen un tamaño que está determinado por la cantidad de elementos o valores que
puede adoptar dicho tipo de dato. Por ejemplo, un tipo booleano está compuesto por dos
elementos básicos (constantes) que lo definen: Verdadero y Falso. Los lenguajes de
programación representan a dicho tipo de dato con un 1 bit, generalmente asociando un 1
a Verdadero y 0 a Falso. Recordemos que dicha representación interna no nos es relevante,
nosotros haremos uso de la abstracción del tipo de dato booleano, pero sí nos interesa saber
qué tamaño tiene asociado un tipo de dato. El Entero, como cualquier otro tipo primitivo, se
representa con una cantidad finita de memoria, por lo cual no es posible representar todos
los números enteros con dicho tipo de dato. Necesitaríamos una cantidad infinita de
memoria para hacerlo. Por ello es importante conocer cuál es el valor máximo que se puede
representar para evitar problemas de diseño.

Cuando necesitamos definir una estructura infinita o variable en el tiempo (dinámica), el

puntero es la solución para diseñarla. La explicación está en la naturaleza del puntero.

Como mencionamos, el puntero puede contener un valor asociado a un tipo de

datos, o no. Entonces se dice que el puntero hace referencia a un valor de cierto
tipo de dato, o no.

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 15

Por lo tanto, un tipo de dato Puntero a Entero (↑Entero) en realidad tiene como valor una
dirección de memoria, o ninguna. Cuando un puntero no tiene asignada una dirección de
memoria se dice que apunta a nada (NIL o NULL). Es el concepto de ausencia de valor.

Ahora bien, si nuestro Puntero a Entero sólo puede contener valores que son direcciones de
memoria, ¿cómo se puede acceder al valor (el número en sí) de tipo Entero? La respuesta
está en la operación de desreferencia.

El uso del puntero apareció como una abstracción de las operaciones directas a memoria
que se realizaban en los lenguajes ensambladores. En aquellos tiempos no existía otra
opción que manipular los registros de memoria para hacer las transformaciones en los
datos. En los lenguajes de alto nivel el puntero sirve para acceder a porciones de la memoria,
aunque va a depender del lenguaje qué operaciones están asociadas a este tipo de datos. La
operación de desreferencia está siempre presente, ya que permite acceder al valor
contenido en la dirección de memoria que está referenciada por el puntero. Esta operación
se utiliza tanto para leer o escribir el valor del tipo de dato que referencia el puntero.
Recuerde que si tiene una variable de tipo de dato puntero que no tiene definida una
referencia a memoria, es decir, su valor es ausente (NIL), la operación de desreferencia no
puede realizarse.

La operación de desreferencia permite el acceso al valor del tipo de

dato que apunta un puntero. Antes de aplicarla, se debe validar que
no referencie a NIL.

Cuando se inicia la ejecución de un programa toda variable de tipo puntero apunta a NIL,
por lo tanto, se debe realizar una asignación a una región de memoria antes de poder
desreferenciarla. Esta asignación, en algunos lenguajes, es posible realizarla apuntando a la
dirección de memoria de otras variables (utilizando el operador & en el lenguaje C, por
ejemplo), pero siempre es posible asignar la dirección de memoria de otro puntero con el
operador de asignación (<- en pseudocódigo). También es posible asignar una región de
memoria inicial vacía a una variable de tipo puntero mediante la operación nuevo. En ese
caso, en tiempo de ejecución se asigna un espacio de memoria de tamaño determinado por
el tipo de dato al cual apunta el puntero. Veamos el siguiente ejemplo para reforzar estos
conceptos:

1 Tipo:
2 PunteroEntero = ↑Entero
3 DoblePunteroEntero = ↑PunteroEntero
4
5 Variables Locales:
6 p1: PunteroEntero
7 p2: PunteroEntero

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 16

 8 p3: DoblePunteroEntero
9
10 nuevo(p1)
11 p1↑ <- 5
12 p2 <- p1
13 nuevo(p3)
14 p3↑ <- p2
15 p2↑ <- p1^ + 5

En principio se definen dos nuevos tipos de datos PunteroEntero y DoblePunteroEntero, que

simplemente son alias a otro tipo de datos ya conocido (Puntero a Entero y Puntero a
Puntero a Entero). Luego se declaran las variables p1, p2 y p3 con sus tipos de datos
asociados (líneas 6 a 8). La primera sentencia (10) solicita un lugar en memoria para
almacenar un valor de tipo Entero y asigna la dirección de dicho segmento de memoria a la
variable p1. Hasta el momento, es posible desreferenciar la variable p1, la cual devolvería el
valor contenido en dicho segmento nuevo de memoria. Como no conocemos qué tiene ese
espacio de memoria, se dice que ahora p1 apunta a un valor basura. Tanto p2 como p3
apuntan a NIL, por lo cual no podrían ser desreferenciados.
En la línea 11 se desreferencia p1 y se le asigna el valor 5. Esta operación es válida porque
5 es una expresión de tipo Entero y la referencia de p1 también es de tipo Entero. Siempre
se debe tener en cuenta estas consistencias en la programación. En la línea 12 se define que
p2 ahora apunta a la misma región de memoria que p1, mientras que luego p3 apunta a p2
(línea 14). Esta última instrucción también es correcta porque la desreferencia de p3 es en
realidad de tipo PunteroEntero, mientras que p2 también lo es. Finalmente, la línea 15
instruye que el valor al cual apunta p2 ahora será el valor al cual apuntaba p1 sumado con
5. Veamos el resultado de dichas operaciones:

Dirección Valor
p1 (#0023901) 0023901 #0023904
0023902 #0023904
10 0023903 #0023902
p2 (#0023902) 0023904
(#0023904-08)
(entero 10)

p3 (#0023903) 0023908
0023909

Ubicaciones en Memoria Dinámica (HEAP)

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 17

ACTIVIDAD 1 (Autoevaluación)

Le pedimos que realice la Actividad que le proponemos en el campus relacionada con la

operación de punteros.

1.2. SISTEMAS DE TIPOS

ABORDEMOS EL LOGRO DEL SIGUIENTE OBJETIVO

✓ Describir los diferentes sistemas de tipo que incorporan los lenguajes de

programación

Como hemos visto en la primera sección, los tipos de datos son importantes para construir
abstracciones. Si bien existe una completa e interesante teoría formal de tipos que surge
de la rama de la matemática, nosotros sólo repasaremos cómo los diversos lenguajes de
programación aplican dicha teoría para proveer distintos beneficios al momento de
implementar un programa.

Siempre que implementemos el código de un programa, es inevitable que eventualmente

cometamos algún error e introduzcamos un defecto en el programa. Cuando se manifiesta
dicho defecto durante la ejecución, se dice que se detectó un bug en el mismo. La detección
de bugs es una tarea compleja, demanda tiempo y esfuerzo, como lo es también la tarea de
resolución de los defectos encontrados. Ambas son parte de la fase de mantenimiento en el
ciclo de vida del software, aunque pueden suceder inclusive en etapas tempranas del
desarrollo. Como se verá en ingeniería de software, no es posible garantizar un producto
que se encuentre libre de defectos.

La mayoría de los lenguajes de programación ofrecen un mecanismo que permiten reducir

la introducción de defectos en el software. Este mecanismo es el sistema de tipos (type

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 18

system), el cual permite prevenir la ocurrencia de errores durante la ejecución del
programa. Un sistema de tipos provee al lenguaje la capacidad de verificar la correcta
utilización de los distintos tipos asignados a funciones, variables, expresiones, etc., a través
del chequeo de tipos (type checking). Esto incluye evitar la ambigüedad que suele surgir
en distintas situaciones, como es el caso de sumar un entero con una cadena. Veamos el
siguiente ejemplo:

1 x: Entero
2 y: Cadena
4 x <- 10
5 y <- “21”
6 mostrar(x + y)

En el fragmento de código presentado vemos un caso de ambigüedad, donde la operación x

+ y (línea 6) no puede resolverse sin información adicional. Por un lado, podríamos suponer
que el operador ‘+’ corresponde a concatenación de cadenas, por lo cual pretendemos
mostrar “1021”. En cambio, se podría suponer que el operador ‘+’ actúa como suma de
enteros, por lo cual esperaríamos el resultado 31 que requeriría convertir implícitamente a
la variable y en tipo Entero. Es por ello que un sistema de tipos fuerte no permitirá la
ejecución.

El trabajo del chequeador de tipos (type checker) es justamente determinar si el código

escrito es consistente con el sistema de tipos del lenguaje. De esta forma se busca evitar
errores de ejecución, tal como hemos visto que no es el caso de los lenguajes ensambladores
donde no es posible determinar si cierto valor en memoria corresponde a un tipo de dato
particular. En esos casos podríamos estar operando con valores inesperados y llevarían a
un comportamiento erróneo del programa. En algunos lenguajes también podremos
realizar el chequeo previo a la ejecución del programa, lo cual provee al lenguaje un nivel
de seguridad mayor.

1.2.1. Estático vs Dinámico

Recordemos el caso de los lenguajes de programación compilados donde existe una etapa
previa a la ejecución que permite realizar tareas de detección temprana de errores. Aquí el
chequeador de tipos realiza la verificación estática de los tipos de datos. El implementador
debe entonces declarar de forma explícita los tipos de datos de cada uno de los elementos
del programa para que el chequeo pueda realizarse. Se dice estático porque la asignación de
los tipos de datos a los distintos elementos no depende de un momento específico durante
la ejecución, es decir, una variable declarada como Entero en cierta sección del código
siempre tendrá asociado un valor de tipo Entero.

El chequeo estático de tipos se realiza en tiempo de compilación,

mientras que el dinámico en tiempo de ejecución.

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 19

Algunos lenguajes no requieren la declaración explícita de las variables, sino que pueden
asignársele un valor de forma directa sin la necesidad de haberla declarado previamente.
En esos casos se puede decir que el lenguaje infiere el tipo de dato a partir del tipo de dato
del valor asignado. Si un lenguaje permite la inferencia de tipos puede también realizar un
chequeo estático, pero es necesario tener en cuenta las reglas de inferencia que asume el
lenguaje. Es necesario mencionar que una de las ventajas de declarar los tipos de datos es
que sirve como documentación integrada en el código, mejorando así la interpretación del
mismo. Haskell es un ejemplo de lenguaje con chequeo estático y que soporta la inferencia
de tipos.

Otra gran ventaja del chequeo estático es la optimización de la ejecución del programa, ya
que durante el proceso de compilación se puede determinar el tipo de datos asociado cada
elemento y así traducir a código máquina utilizando operaciones apropiadas para trabajar
cada tipo de dato, como lo es el caso de operaciones sobre vectores y matrices, por ejemplo.

Si bien el chequeo estático es de gran importancia, no resulta suficiente para obtener un

lenguaje seguro. Es necesario disponer de un chequeo de tipos durante la ejecución del
programa, lo cual se denomina verificación dinámica. En general, los lenguajes asocian en
su entorno de ejecución una etiqueta a cada variable, función, expresión, etc., que especifica
el tipo de dato de la misma en cada momento, de forma que sea posible realizar la validación
del valor asociado con el tipo de dato esperado. Veamos un simple ejemplo de este tipo de
validación:

1 x: Entero
2 leer(x)

La variable x es declarada como un Entero, pero no tiene valor asignado hasta que lo ingrese
el usuario con la operación leer. Por lo tanto, el compilador no puede realizar la validación
del tipo correspondiente ya que en dicha etapa de compilación el valor es aún desconocido.
En este caso, el chequeador de tipos debe realizar la verificación durante la ejecución, más
precisamente, al momento en que el usuario ingresa el valor asignado a x en el teclado (línea
2). Internamente, dependiendo del lenguaje utilizado, se realizará una conversión implícita
del tipo de dato Cadena a Entero, porque el ingreso por teclado suele ser representado en
una cadena de texto. Entonces el chequeador de tipos valida durante dicha conversión que
el tipo a asignar a x sea Entero, caso contrario el programa puede lanzar una excepción,
truncar el valor, asignar un cero, etc. Si el lenguaje no implementase un chequeo dinámico,
el programa podría continuar sin detectar si lo ingresado por el usuario fue un valor
numérico o caracteres resultando así en un comportamiento errático e imprevisible.

1.2.2. Fuerte vs Débil

Es común considerar que un lenguaje de tipado estático es considerado también de tipado

fuerte, pero en realidad no existe una relación estricta entre ambas clasificaciones. Así como
la distinción entre el chequeo estático y dinámico se basa en el momento en el cual se realiza
la verificación, la diferenciación entre un lenguaje de tipado fuerte o débil radica en el nivel
de restricción de las reglas del sistema de tipos. En otras palabras, un lenguaje de tipado

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 20

fuerte no permitirá ejecutar código que presente ambigüedades de tipos o se intenten
realizar acciones inseguras.

Existe entonces una relación entre el nivel de las restricciones del sistema de tipo y la
seguridad que provee el lenguaje (type safety). Una restricción o limitación fuerte requiere
generalmente que toda conversión de un tipo de dato a otro sea definida por el usuario
explícitamente, a menos que la misma sea libre de cualquier ambigüedad. Esto deriva en
una reducción de errores en tiempo de ejecución relacionados con las conversiones de tipo
(casting). Por el contrario, si se dispone de un lenguaje con un chequeo débil, ofrecerá mayor
libertad al implementador ofreciendo más flexibilidad al momento de escribir código y, en
consecuencia, permitiendo construir programas donde sea posible diseñar abstracciones
de mayor nivel.

El nivel de restricción de un sistema de tipos se suele clasificar como

fuerte o débil.

Un clásico ejemplo es el lenguaje C, donde se permite la operación aritmética de punteros y

así el usuario tiene acceso a regiones de memoria que no necesariamente contienen valores
del tipo de dato que representa el puntero, lo cual la convierte en una operación insegura
en relación al sistema de tipos. En cambio, si consideramos el lenguaje interpretado Python,
veremos que un ejemplo como el mencionado previamente con la suma entre un Entero y
una Cadena, resulta que no es posible ejecutar dicha instrucción sin antes realizar la
conversión explícita al tipo de dato deseado, tal como se muestra a continuación:

# Código Python
1 x = 10
2 y = “21”
4 print(x + int(y)) # muestra 31
5 print(str(x) + y) # muestra 1021

Es interesante observar que un lenguaje como C que es compilado y realiza chequeo estático
de tipos resulta en un lenguaje de tipado débil, mientras que un lenguaje como Python que
sólo realiza su chequeo de forma dinámica, porque es un lenguaje interpretado, en cambio
se lo considera de tipado fuerte ya que no permite la coerción de tipos implícita. En el
ejemplo previo de Python se puede observar que en las líneas 4 y 5 se debe realizar una
conversión explícita al tipo de dato de una de las variables para que coincida con el tipo de
dato de la restante y así poder aplicar la operación suma.

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 21

1.3. GESTIÓN DE LA MEMORIA

ABORDEMOS EL LOGRO DEL SIGUIENTE OBJETIVO

✓ Diferenciar los tipos de variables según el momento de asignación de memoria

Cada lenguaje incorpora su propio gestor de memoria, por lo cual estableceremos un

modelo genérico para comprender las diferencias de asignación, siendo clave su correcta
interpretación al momento de trabajar con el concepto de recursión. Uno de los errores más
comunes entre los desarrolladores inexpertos es desconocer por completo cómo se
administra la memoria en un programa, dando lugar a problemas clásicos como el desborde
de la pila de ejecución o fuga de la memoria dinámica. En primer lugar, estableceremos esta
distinción entre las dos regiones mencionadas, pero tenga presente que se tratarán de
forma conceptual sin especificar implementaciones propias de cada lenguaje.

1.3.1. La Pila de Ejecución

La pila de ejecución (execution stack o call stack) suele ser una región de la memoria del
sistema de rápido acceso, optimizada en sus operaciones de lectura y escritura. El modelo
de la estructura es el conocido LIFO (Last in, First Out). Cuando se ejecuta un programa, toda
asignación de memoria estática se carga en la ubicación superior (o inferior, dependiendo
de cómo se represente el modelo) en la pila de ejecución. Esta ubicación se indica mediante
un puntero de pila o stack pointer, el cual se desliza a la nueva ubicación superior al
finalizar la carga inicial. En cada llamada a procedimiento o función subsiguiente, dicho
puntero será deslizado a la posición superior. Por lo tanto, la pilua de ejecución queda
estructurada con distintos entornos de ejecución que representan a cada llamada a nuevas
subrutinas. Una vez finalizada la ejecución de una subrutina, se elimina dicho entorno de la
pila de ejecución. Veamos el siguiente ejemplo con el estado de la pila de ejecución.

1 funcion suma(x,y): Entero

2 devolver (x + y)
3 finFuncion

4 funcion producto(x,y): Entero

5 vars_loc
6 resultado: Entero
7 resultado <- 0
8 mientras y > 0 hacer
9 resultado <- suma(resultado,x)

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 22

 10 y <- y – 1
11 finMientras
12 devolver resultado
13 finFuncion
14
# MAIN
15 a, b, c: Entero
16 a <- 3
17 b <- 2
18 c <- producto(a, b)

Estados de la pila de ejecución según el ejemplo:

-- suma –
x=0, y=3
-- producto – -- producto – -- producto –
resultado=0, x=3, y=2 resultado=0, x=3, y=2 resultado=3, x=3, y=2
-- MAIN – -- MAIN – -- MAIN – -- MAIN –
a=3, b=2, c=0 a=3, b=2, c=0 a=3, b=2, c=0 a=3, b=2, c=0
Carga del MAIN Ejecución producto Ejecución #1 suma Finaliza #1 suma

-- suma –
x=3, y=3
-- producto – -- producto –
resultado=3, x=3, y=1 resultado=6, x=3, y=1
-- MAIN – -- MAIN – -- MAIN –
a=3, b=2, c=0 a=3, b=2, c=0 a=3, b=2, c=6
Ejecución #2 suma Finaliza #2 suma Finaliza producto Finaliza MAIN

Como se puede observar en los diferentes estados presentados, la pila de ejecución

almacena para cada ejecución de una subrutina los valores de las variables locales, los
parámetros con los que se la llama, y la dirección de memoria de retorno que sería el límite
inferior de cada segmento representado en el ejemplo. El límite superior de la pila
representa la ubicación en memoria a la cual apunta el puntero de ejecución, es decir, el
tope de la pila. A medida que las rutinas se ejecutan se liberan de la pila para continuar
apilando las nuevas rutinas a ejecutar.

Se debe tener especial cuidado de no superar el límite de la pila de ejecución ya que llevaría
al error clásico de desborde (stack overflow). La condición más común en la cual se produce
este efecto se da con un mal diseño de la recursión, sea en casos de recursión infinita o muy
profunda, debido a que ante cada llamada de una subrutina recursiva se apila el entorno de
dicha llamada y nunca se libera de la pila el entorno previo, llevando así a completar la
estructura finita. Por otra parte, existe la posibilidad de cruzarnos con este error en
situaciones donde se definen variables globales o locales de gran tamaño, ya que ambos
tipos de variables se suelen asignar a la pila de ejecución.

Recordemos el concepto de alcance o scope de una variable: las variables globales tienen el
mismo tiempo de vida que el programa principal, mientras que las variables locales sólo
existen en memoria durante la ejecución de la rutina que la declara o utiliza. En el ejemplo

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 23

analizado se ve claramente la razón por la cual una variable local no puede continuar
existiendo al concluir la subrutina, ya que se elimina el entorno completo de la misma de la
memoria. Igualmente se debe considerar que algunas variables especiales como las
referencias o punteros, en realidad sólo guardan en la pila la dirección de memoria donde
se guarda el dato real. Entonces este tipo de variables, si bien sólo existen localmente,
permiten asignar un espacio en memoria dinámica (heap) donde se almacena el contenido
de la variable, el cual también es apuntado por otra variable ajena a la subrutina. Este
concepto es el utilizado cuando se habla del pasaje por referencia de un parámetro, donde
en realidad el parámetro es un puntero a la ubicación en memoria del valor real.

1.3.2. La Memoria Dinámica (heap)

Realizaremos una distinción entre variables estáticas y dinámicas, definida según cuándo
se efectúa la asignación de memoria requerida. Las variables estáticas tienen su
asignación de memoria en tiempo de compilación, ya que se conoce cuál es el tamaño de
memoria a reservar y el mismo no varía a lo largo del programa. Las variables estáticas
entonces existen durante toda la ejecución del programa, el caso más común siendo el de
las variables globales. Debido a la asignación previa a la ejecución, el compilador puede
optimizar dicha asignación para un acceso más eficiente.

Cuando un programa realiza la asignación de memoria en tiempo de ejecución, se dice que

es una asignación dinámica. Las variables locales son de asignación dinámica, o mejor dicho
automática, ya que se asignan a la pila al momento de la ejecución de la subrutina que las
define, pero en general la asignación dinámica de variables se refiere a la región de memoria
dinámica. Esta región de memoria no se estructura mediante una pila, sino que se compone
de un conjunto de segmentos que pueden se contiguos o no. La implementación de la
memoria dinámica será particular para cada lenguaje, por lo cual no profundizaremos el
modelo, pero es posible representar esta región de memoria como dos listas de segmentos.
Una lista contiene segmentos que están asignados a alguna variable dinámica, llamada lista
de utilizados, mientras que se encuentra la lista de segmentos libres que contiene el espacio
en memoria sin asignar.

La ventaja de disponer de una región dinámica de memoria es que podemos trabajar con
estructuras variables en el tiempo y recursivas, ya que se apoyan en variables de tipo
puntero, las cuales claramente son variables dinámicas. Recuerde que para comenzar a
utilizar una variable de tipo puntero es necesario realizar la asignación de memoria
mediante la instrucción nuevo. En ese momento del tiempo de ejecución, el sistema
selecciona uno o más segmentos de la lista de segmentos libres en la memoria dinámica, los
mueve a la lista de segmentos utilizados y finalmente asigna a la variable la dirección de
memoria correspondiente al primer segmento seleccionado.

Por otra parte, existe una desventaja que rara vez es contemplada. Luego de cierto tiempo
de ejecución, donde la memoria dinámica se ha consumido según la necesidad del programa,
suele ocurrir un efecto indeseado: la fragmentación. Los segmentos se asignan y liberan a
demanda y cada asignación requiere cantidades diferentes de segmentos. Entonces, existe
la posibilidad de que algunas variables se hayan liberado y dejen un hueco en la memoria

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 24

dinámica, la cual queda fragmentada. Los lenguajes más modernos se ocupan de este
problema mediante el recolector de basura (garbage collector), un módulo responsable de
mantener limpias las asignaciones en memoria dinámica. Aun así, es crucial que el
desarrollador implemente de forma responsable tanto la asignación como la liberación de
memoria dinámica. Es por ello, que debemos recordar siempre de ejecutar la instrucción
disponer para evitar problemas durante la ejecución.

1 p1: ↑Real

2 nuevo(p1) # se asigna memoria dinámica para p1

3 p1↑ <- 3.2 # almacena el valor 3.2 en memoria dinámica asignada
…
4 disponer(p1) # libera la memoria dinámica asignada a p1

1.4. INTRODUCCIÓN A TIPOS ABSTRACTOS DE DATOS

ABORDEMOS EL LOGRO DE LOS SIGUIENTES OBJETIVOS

✓ Modelar soluciones correctas de problemas del mundo real a través de Tipos

Abstractos de Datos

El concepto de Tipo Abstracto de Datos (TAD) ya ha sido abordado en cursos previos a

través de estructuras conocidas, como lo son la Lista, Cola y Pila, pero no necesariamente se
limitan a ellos. Es fundamental comprender cómo modelar diferentes problemas de la
realidad a través de TADs ya que nos servirá como punto de partida para el paradigma de
programación orientado a objetos (POO). Como hemos visto en esta unidad, los tipos de
datos incluidos en los lenguajes de programación proveen ciertas características como la
abstracción y encapsulamiento. A partir del modelado de problemas mediante TADs
nosotros estaremos introduciendo estas mismas propiedades en nuestras soluciones. Por
lo tanto, los sistemas diseñados serán capaces de modelar abstracciones complejas del
mundo real y proveer también tanto encapsulamiento como ocultamiento de
información.

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 25

 Un TAD define una clase de objetos abstractos caracterizados por
las operaciones disponibles sobre los mismos

1.4.1. Conceptos de Diseño

El diseño de un TAD se centra en definir la estructura de datos que modela la clase de objetos
que se pretende abstraer junto con el comportamiento asociado a los mismos. Este
comportamiento se manifiesta mediante las distintas operaciones que pueden realizarse
sobre la estructura. Esta combinación provee la abstracción deseada para representar la
clase de objetos mencionada. Puede observarse que los tipos de datos incluidos de forma
nativa como el Entero, Real, Cadena, etc, representan abstracciones similares con su
comportamiento asociado al igual que los TAD, sólo que son abstracciones realizadas en un
nivel inferior al que seguramente necesitaremos. Es más, los TADs que definiremos siempre
estarán apoyados en tipos preexistentes como así también en TADs predefinidos por
nosotros u otro implementador.

Encapsulamiento

El encapsulamiento es un concepto esencial ya que permite asociar y definir operaciones

que pueden aplicarse sobre el conjunto de elementos que componen un TAD. En el caso de
una Lista existían operaciones como insertar, listaVacia o ultimo que eran aplicables a ese
TAD particular. Si uno necesitara realizar una concatenación de listas, obviamente tendría
que implementar previamente el procedimiento concatenar para ese TAD Lista. Toda
operación que no hubiese estado implementada simplemente no formaría parte del TAD.
Dependiendo del lenguaje utilizado, existirán mecanismos para forzar dicho
encapsulamiento o no, pero al menos es necesario tenerlo presente como principio de
diseño al momento de implementarlo. Por ejemplo, en C es posible implementar un TAD en
un mismo archivo .c y luego exportar las operaciones para consumo externo mediante un
headerfile (.h). De esa forma C ofrece ese mecanismo para encapsular las operaciones al tipo
de datos definido.

Ocultamiento de Información

Continuando con el ejemplo previo, el uso de un headerfile no sólo permite encapsular

operaciones a un tipo de datos, sino que también oculta la información interna de cómo se
implementa el TAD. Entonces quien lo consume sólo necesita el headerfile con la firma de
las operaciones públicas, todo el resto se encuentra oculto en el archivo binario
previamente compilado.

Esta forma de exportar las operaciones públicas varía según el lenguaje utilizado, pero
representa siempre el mismo concepto: dichas operaciones componen la interfaz del TAD.
El consumidor de un TAD no necesita ni debe conocer en detalle la estructura que lo define,
si es estático o dinámico, si se apoya en otro TAD internamente, si requiere de operaciones

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 26

auxiliares propias, etc. Quien lo consume necesita saber cómo instanciarlo, es decir, cómo
inicializar una variable de ese TAD y qué operaciones pueden aplicarse sobre la misma. En
la POO encontraremos mecanismos claros que proveen tanto encapsulamiento como
ocultamiento de información, pero en algunos lenguajes imperativos clásicos puede que se
implementen con menos rigidez. Aun así, es importante comprender los conceptos para
implementar correctamente un TAD. Recordemos que toda operación que no deba
proveerse al usuario final del TAD será una operación privada y no formará parte de la
interfaz del mismo.

El siguiente ejemplo presenta una forma de implementar el TAD ListaEnteros en

pseudocódigo, pero sin especificar la interfaz, sólo incluye la estructura de datos interna y
algunas operaciones primitivas. La estructura de la lista se representa mediante punteros,
por lo cual en la operación insertar (línea 10) se debe realizar la reserva (alocación) de
memoria dinámica para el nuevo nodo insertado al comienzo de la lista. La operación
listaVacia (línea 7) construye una lista sin nodos y debería ser la operación que inicializa
siempre una variable de este tipo de datos. Ambas operaciones mencionadas se las puede
clasificar como operaciones constructoras del TAD, ya que permiten generar todos los
elementos del mismo (sea una lista vacía, o cualquier lista con nodos que almacenen un
valor Entero). Las operaciones esListaVacia y head se las conoce como proyectoras debido
a que presentan información de la estructura interna del TAD y no lo modifican, mientras
que la operación tail en este caso sí realiza una modificación sobre la variable dada
(devuelve la lista original, pero sin el elemento inicial) pero no elimina el nodo que
corresponde a la cabeza de la misma. Dado que nuestra implementación del TAD Lista está
optimizada para realizar la inserción de nuevos nodos en el inicio (cabeza) de la misma, los
conceptos de las operaciones de head y tail son adecuadas para descomponer la estructura
interna, es decir, resulta de utilidad obtener el elemento que se encuentra a la cabeza con
head y el resto de la lista sin dicho elemento con tail. Esta implementación tendrá sentido
más adelante al resolver problemas de recursión.

1 Tipo:
2 NodoEntero = registro
3 dato: Entero
4 sig: ListaEntero
5 finRegistro
6 ListaEntero = ↑NodoEntero

7 proced listaVacia(ref xs: ListaEntero)

8 xs <- NIL
9 finProced

10 proced insertar(x: Entero, ref xs: ListaEntero)

11 vars
12 ys: ListaEntero
13 nuevo(ys)
14 ys↑.dato <- x
15 ys↑.sig <- xs
16 xs <- ys
17 finProced

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 27

 18 funcion esListaVacia(xs: ListaEntero): Bool
19 devolver (xs = NIL)
20 finFuncion

21 proced head(xs: ListaEntero, ref x: Entero, ref error: Bool)

22 si (not esListaVacia(xs)) entonces
23 x <- xs↑.dato
24 error <- Falso
25 sino
26 error <- Verdadero
27 finSi
28 finProced

29 proced tail(ref xs: ListaEntero, ref error: Bool)

30 si (not esListaVacia(xs)) entonces
31 xs <- xs↑.sig
32 error <- Falso
33 sino
34 error <- Verdadero
35 finSi
36 finProced

1.4.2. Necesidad de definir un TAD

Analicemos una abstracción clásica y conocida que actualmente suele venir incorporada en
los lenguajes más modernos: la Fecha y Hora. El concepto de fecha y hora es interesante de
analizar porque, según el problema que se desee modelar, este concepto puede
representarse de diferentes formas. Por ejemplo, para diseñar un sistema que realiza
transacciones es necesario contar con una abstracción que modele el momento en el cual la
transacción ocurrió. Probablemente esta abstracción de tiempo tendrá su estructura
interna para representar día, mes, año, hora, minutos y segundos, junto con un
comportamiento asociado (crearFecha, obtenerDia, restarFechas, etc).

Un enfoque para implementar esta abstracción sería utilizar estructuras sueltas dentro del
programa, por ejemplo, definiendo variables de tipo Entero como día, mes, año, hora,
minutos, segundo, etc, y luego realizar algunas operaciones según se necesite en cada
momento (quizá modelándolas en funciones de visibilidad global). Recordemos que la idea
de implementar abstracciones mediante TADs persigue el objetivo de incorporar tres
conceptos de diseño: abstracción, encapsulamiento y ocultamiento de información. Por lo
tanto, el enfoque propuesto no sería el más apropiado para cumplir con estos principios, ya
que cada programador tendrá la libertad de definir el concepto de Fecha y Hora (y sus
operaciones) como le sea más conveniente y la implementación no podrá garantizar que se
represente siempre la misma abstracción para cada caso de uso.

Entonces, disponer de un mecanismo que permita combinar los tres principios

mencionados es muy importante para el modelado de abstracciones. Si optamos en cambio
por el enfoque de diseñar el TAD FechaHora, entonces podremos definir una estructura

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 28

interna no visible ni editable por el resto de los programadores, la cual sólo podrá ser
accedida o modificada mediante operaciones exportadas por el TAD, es decir, su interfaz
compuesta por operaciones públicas. El beneficio no sólo está en la reutilización de dicha
implementación en todo el programa (y por qué no en otros programas futuros), sino que
también permite utilizar una abstracción consistente entre los disintos casos de uso y
reducir errores relacionados con la operación sobre sus estructuras internas. A su vez, las
operaciones constructoras y modificadoras integran en su código toda acción de validación
que mantendrá la integridad del tipo especificado, por lo cual se reduce el riesgo de operar
con datos incoherentes.

1.4.3. Operaciones de un TAD

En el ejemplo del TAD ListaEntero hemos realizado una distinción sobre algunas
operaciones que forman parte del comportamiento del TAD. Recordemos que un TAD, al
igual que cualquier otro tipo de datos, se compone de una estructura interna que permite
representar todos los valores que dicho tipo soporta junto con un comportamiento que se
modela a partir de las operaciones que pueden realizarse sobre el mismo. Es la definición
propia del principio de encapsulamiento. Estas operaciones son las que nos permiten
acceder y modificar el estado de la estructura interna del TAD, siendo algunas de ellas de
visibilidad pública o exportadas para que pueda utilizarlas el usuario final.

Un TAD se compone de una estructura interna y un conjunto de

operaciones que permiten acceder y modificar dicha estructura

Veamos una posible implementación parcial del TAD FechaHora:

# TAD FechaHora

1 Tipo:
2 FechaHora = registro
3 dia: Entero
4 mes: Entero
5 año: Entero
6 hora: Entero
7 minuto: Entero
8 segundo: Entero
9 zona: Entero
10 finRegistro

11 proced crearFHCadena(str: Cadena, ref fh: FechaHora)

12 # Dada una cadena str, crear un FechaHora en la variable fh
13 si esFechaHoraValida(str) entonces
14 fh.dia <- (Entero) subcadena(str, 0, 2)
15 fh.mes <- (Entero) subcadena(str, 2, 2)
16 fh.año <- (Entero) subcadena(str, 4, 4)

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 29

 17 fh.hora <- (Entero) subcadena(str, 8, 2)
18 fh.minuto <- (Entero) subcadena(str, 10, 2)
19 fh.segundo <- (Entero) subcadena(str, 12, 2)
20 fh.zona <- 0 # asumo se inicializa en UTC
21 finSi
22 finProced

23 funcion dia(fh: FechaHora): Entero

24 devolver (fh.dia)
25 finFuncion

26 proced siguiente(ref fh: FechaHora)

27 # Modificar fh incrementando 1 segundo en la misma variable
28 si (fh.segundo = 59) entonces
29 fh.segundo = 0
30 si (fh.minuto = 59) entonces
31 fh.minuto = 0
32 si (fh.hora = 23) entonces
33 fh.hora = 0
34 siguienteDia(fh)
35 sino
36 fh.hora <- fh.hora + 1
37 finSi
38 sino
39 fh.minuto <- fh.minuto + 1
40 sino
41 fh.segundo <- fh.segundo + 1
42 finSi
43 finProced

44 proced restarFechas(fecha1, fecha2: FechaHora, ref resta:

FechaHora)

Las primeras 10 líneas definen la estructura interna del TAD. En este caso, nos hemos
apoyado en un tipo de dato compuesto conocido (registro). El registro es un tipo que
representa al producto cartesiano de distintos tipos, por ejemplo, nuestro TAD FechaHora
es el producto cartesiano de 7 tipos Entero (dia x mes x año x hora x minuto x segundo x
zona).

El procedimiento crearFHCadena tiene como objetivo validar cierta cadena con un formato
del estilo ‘dd/mm/aaaa hh:mm:ss’ y generar a partir de ella una nueva instancia del tipo
FechaHora, la cual se almacena en la variable fh. Obviamente la operación
esFechaHoraValida debería ser parte del TAD ya que se utiliza para generar nuevos
elementos del mismo, pero en este caso ha sido ignorada en la implementación por
cuestiones de espacio. Dado que crearFHCadena genera un elemento del TAD, se dice que es
una operación constructora. Un caso similar se vio en el ejemplo previo de listaVacia. Estas
operaciones generan expresiones básicas del tipo definido, es decir, pueden construir todos
los elementos que conforman la representación de valores posibles de ese tipo. Algunos
autores también hacen una distinción según los tipos de los parámetros que reciben las

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 30

operaciones ya que si alguno de ellos es del mismo tipo que el que se está construyendo las
denominan operaciones productoras, por ejemplo, es el caso del procedimiento
restarFechas del cual sólo se muestra su firma (línea 44).

Por otra parte, existen operaciones que no pretenden generar nuevas instancias de un cierto
tipo ni modificar su estado actual. En la línea 23 podemos observar que la función dia
simplemente devuelve información acerca del estado de la variable fh. En particular
devuelve una parte de su estructura interna, una expresión de un tipo distinto al del TAD
definido (en este caso, un Entero). A este tipo de operaciones se las llama proyectoras u
observadoras y son las que aseguran el ocultamiento de información durante el acceso de
lectura del tipo de dato.

Finalmente analicemos la operación siguiente (línea 26). Dado un elemento de tipo

FechaHora, este procedimiento aplica, a través de cierta lógica, diversas modificaciones a su
estructura interna para transformar el valor representado por el mismo elemento. El
objetivo es incrementar 1 segundo en el elemento pasado por referencia, lo cual resultará
en la modificación adecuada. Por lo tanto, diremos que es una operación modificadora.
Los tipos de datos que tienen este tipo de operaciones son tipos mutables, mientras que
aquellos tipos que no tienen definida una operación modificadora se los denomina tipos
inmutables.

Esta distinción es importante para comprender cómo producir nuevos elementos de cierto
tipo de datos. Por ejemplo, el tipo de datos primitivo Entero (int) es inmutable en Java, ya
que no posee operaciones modificadoras y sus constructores son todos los literales (-10, …,
0, 1, 2, …, 100, …). Si quisiera modificar el valor de una variable de tipo Entero, simplemente
se asigna un nuevo elemento que representa dicho valor deseado, pero esa expresión
(literal) es un elemento diferente al que tenía asignado antes la variable. No fue modificado
el elemento original, sino que se reemplazó la asignación de la variable que ahora apunta a
un nuevo elemento de tipo Entero. Es clave comprender correctamente esta diferenciación
para poder trabajar con lenguajes como Java que no permiten operar directamente con
punteros.

Los lenguajes más modernos incorporan mecanismos de limpieza de memoria, tal como es
el caso de Java con su Garbage Collector. Aun así, es necesario tener presente que siempre
que se asigna memoria durante la ejecución de un programa es considerada una buena
práctica la correcta liberación de la misma cuando ya no se la requiera. La operación
disponer que mencionamos para liberar la memoria asignada a los punteros es esencial para
mantener una memoria eficiente. Por ende, todo TAD debería implementar operaciones que
realizan dicha liberación y se las denomina operaciones destructoras. En el ejemplo dado,
se podría implementar un procedimiento destruirFechaHora(ref f: FechaHora) para tal
motivo, aunque en este caso particular no es necesario ya que el TAD no se construye de
forma dinámica (no utiliza punteros en su estructura interna).

1.4.4. Igualdad en el TAD

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 31

La igualdad en los tipos de datos es un concepto fundamental y puede darse a dos niveles
según su profundidad y se verán con más detalle en la POO, pero básicamente distinguimos
que la igualdad entre dos variables de un mismo tipo puede interpretarse de dos formas.
Una primera forma sería en determinar que dos variables son iguales si en realidad están a
apuntando a un mismo elemento en memoria. En el caso de variables estáticas, este tipo de
igualdad no tiene mucho sentido, pero sí lo tiene para variables de referencia y punteros.
Para analizar la igualdad en TADs nosotros trabajaremos con esta segunda forma de
igualdad, donde nos interesa el valor adoptado y su interpretación semántica. Por lo tanto,
definiremos la igualdad en un TAD según el criterio que deseemos. Veamos un ejemplo.

Si estuviera modelando un TAD Auto, ¿cómo podríamos definir su operación de igualdad?

En primer lugar, debemos pensar qué estamos modelando. La mayoría conocemos los
componentes de un auto, sus operaciones básicas posibles (avanzar, retroceder, doblar
derecha, cambiar marcha, etc), sus propiedades (marca, modelo, año de fabricación, color,
etc). Disponemos de una gran cantidad de información que determina a cada instancia de
Auto, entonces debemos preguntarnos dentro del problema a definir la razón por la cual yo
diría que un auto es igual a otro. Todo depende del contexto del problema… Por ejemplo, si
estuviera definiendo un sistema dentro de la cadena de producción de una automotriz,
probablemente establezca la igualdad entre dos autos cuando ambos sean de misma marca,
modelo, año y color. Pero si el sistema a modelar fuera uno destinado a la venta de autos,
quizá deba establecer mi igualdad por algo más preciso como la coincidencia del número de
motor y número de chasis. Ahora si estuviera modelando un sistema de multas, ¿me serviría
determinar la igualdad por estos parámetros? Seguramente no sea de valor, ya que mi
operación de igualdad sería mediante la coincidencia de los dominios (patentes) de los
autos.

Es por ello que la operación de igualdad en un TAD no es tan trivial, como sí lo puede ser en
un tipo de datos básico como el Entero. Y no debemos olvidar que, junto con operaciones
ordinales que definen un orden entre los elementos de un TAD (no siempre aplican, ya que
no todos los TADs tienen elementos que respetan una relación de orden), son muy
importantes ya que, al trabajar con varios elementos de ese tipo en un arreglo o lista, nos
permitirá realizar luego operaciones de búsqueda, comparaciones, establecer órdenes, etc.
La igualdad es determinante para ciertas condiciones lógicas de negocio, recordemos
que no es lo mismo que un sistema de multas identifique iguales a todos los autos de cierto
modelo, color y año, porque si tomara una foto y sólo comparara estos parámetros le
aplicaría la misma multa a todos aquellos autos de misma marca, modelo, color y año…

1.4.5. Creando un TAD

El diseño de un TAD requiere de conocimiento del dominio ya que intentamos modelar una
abstracción del mundo real. En ciertas situaciones surgirá de forma natural o trivial, como
es el caso del TAD FechaHora, aunque siempre surgirán detalles a lo largo del diseño:
¿Debemos contemplar la zona horaria? ¿Tendremos operaciones que devuelvan el día de la
semana? ¿En qué idiomas debería presentarse dicho día de la semana? ¿Utilizaremos
funciones para convertir el día de la semana a un Entero? Por ello deberemos utilizar un
proceso de razonamiento creativo para descubrir cómo modelar dicha abstracción o,

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 32

inclusive, cómo comprender en principio la abstracción en cuestión. Por lo tanto, no existe
una receta única o un procedimiento específico que nos permita diseñar TADs
correctamente. Dependerá del problema a resolver y la experiencia del diseñador.

En este último tramo de la unidad intentaremos definir una especie de formato para
construir TADs en pseudo-código, pero estará lejos de ser una guía universal o una
metodología de desarrollo. El objetivo será proponerle un ejemplo para que utilice como
punto de partida para sus próximas creaciones a lo largo de la materia. A modo de
simplificar el concepto, sólo presentaremos una implementación parcial de la abstracción
de un Edificio, con algunas operaciones desarrolladas y otras, en cambio, sólo definiendo
sus firmas.

1 # TAD Edificio

2 # Estructura interna
3 Tipo:
4 Edificio = registro
5 nombre: Cadena
6 direccion: Direccion
7 pisos: Lista(Piso)
8 cocheras: Lista(Cochera)
9 ascensores: Lista(Ascensor)
10 finRegistro

11 # Constructores
12 proced crearEdificio(nombre: Cadena, dir: Direccion, ref edificio:
13 Edificio)
14 edificio.nombre <- nombre
15 edificio.direccion <- dir
16 listaVacia(edificio.pisos)
17 listaVacia(edificio.cocheras)
18 listaVacia(edificio.ascensores)
finProced
19
20 # Modificadores
21 proced construirPiso(ref edificio: Edificio)
22 vars
23 piso: Piso
24 crearPiso(cantidadPisos(edificio) + 1, piso)
25 insertar(piso, edificio.pisos)
finProced
26
27 proced construirDepto(nro_piso: Entero, ref edificio: Edificio)
28 vars
29 depto: Departamento
30 piso: Piso
31 obtenerPiso(nro_piso, edificio, piso)
32 crearDepartamento(cantidadDeptos(piso) + 1, depto)
33 agregarDeptoPiso(depto, piso)
finProced
34
35 # Proyectores
36 funcion cantidadPisos(edificio: Edificio): Entero
37 funcion cantidadCocheras(edificio: Edificio): Entero
38 funcion cantidadAscensores(edificio: Edificio): Entero

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 33

 39 proced obtenerPisos(edificio: Edificio, ref pisos: Lista(Piso))
40 proced obtenerCocheras(edificio: Edificio, ref cocheras: Lista(Cochera))
proced obtenerAscensores(edificio: Edificio, ref ascensores:
Lista(Ascensor))
41
42 proced obtenerPiso(nro_piso: Entero, edificio: Edificio, ref piso: Piso)
43 vars
44 encontrado: Bool
45 aux: Piso
46 encontrado <- Falso
47 mientras not esListaVacia(edificio.pisos) and not encontrado
48 hacer
49 head(edificio.pisos, aux)
50 si pisoNumero(aux) = nro_piso entonces
51 piso <- aux
52 encontrado <- Verdadero
53 finSi
54 tail(edificio.pisos)
finMientras
55 finProced
56
57 # Destructores
58 proced destruirEdificio(ref edificio: Edificio)
59 para cada piso en edificio.pisos hacer
60 destruirPiso(piso)
61 finPara
62 destruirLista(edificio.pisos)
63 para cada cochera en edificio.cocheras hacer
64 destruirCochera(cochera)
65 finPara
66 destruirLista(edificio.cocheras)
67 para cada ascensor en edificio.ascensores hacer
68 destruirAscensor(ascensor)
69 finPara
destruirLista(edificio.ascensores)
finProced

En primer lugar, hemos intentado definir una aproximación a la abstracción de un Edificio,

donde identificamos algunas operaciones básicas que están agrupadas según la clasificación
mencionada previamente. No será necesario distinguir las operaciones mediante esta
clasificación, pero resulta de una guía intuitiva para comprender cuál es el rol de cada una.
Notemos algunas cuestiones relacionadas con las buenas prácticas de codificación:

• Los tipos de datos comienzan con mayúsculas: No confundir la variable edificio, con
el tipo de datos Edificio.
• El TAD Lista es un tipo paramétrico ya que puede contener nodos de cualquier tipo:
La estructura de Edificio tiene variables como pisos que es en realidad una Lista de
nodos de tipo Piso. Veremos otros tipos paramétricos más adelante.
• En general, las variables de tipo compuestos suelen pasarse por referencia: Se
intenta evitar el uso de funciones que retornen un tipo compuesto. Aunque es
posible realizarlo mediante punteros, es recomendable pasarla por referencia. Por
ejemplo, en los constructores uno podría hacer funciones en lugar de

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 34

 procedimientos y así devolver el tipo de dato que se construye, en cambio se observa
cómo se pasan por referencia como último parámetro.
• Los parámetros que no se modifican pasan por valor: Es cierto que en algunos
lenguajes es necesario pasar los arreglos por referencia por una cuestión de gestión
de la memoria, sin embargo, durante la materia intentaremos abstraernos de dichas
limitaciones de lenguajes específicos y hacer hincapié en el concepto de pasaje por
valor o referencia según su uso dentro del procedimiento o función.

La implementación es incompleta ya que podrían agregarse varias operaciones a este

concepto que modelamos, no incluimos ninguna validación en constructores y
modificadores, pero también se ve claramente que nos apoyamos en tipos de datos que no
especificamos. En general siempre tendremos abstracciones más simples que permiten
modelar una más compleja. En nuestro TAD Edificio podríamos haber definido la dirección
como campos dentro del registro de su estructura interna, pero dado que Dirección es una
abstracción de otro concepto que posiblemente pueda reutilizarse en otro diseño, he
decidido construirla por separado.

1 # TAD Direccion (inmutable)

2 # Estructura interna
3 Tipo:
4 Direccion = registro
5 calle: Cadena
6 numero: Entero
7 codigo_postal: Cadena
8 barrio: Cadena
9 provincia: Cadena
10 finRegistro

11 # Constructores
12 proced crearDireccion(calle: Cadena, numero: Entero, cod, barrio, prov:
Cadena, ref dir: Direccion)

13 # Proyectores
14 funcion dirCalle(dir: Direccion): Cadena
15 funcion dirNumero(dir: Direccion): Entero
16 funcion dirCodPostal(dir: Direccion): Cadena
17 funcion dirBarrio(dir: Direccion): Cadena
18 funcion dirProvincia(dir: Direccion): Cadena

La separación de abstracciones en otras más simples permite encarar el problema por

partes para luego integrarlas en una solución final. Al igual que el TAD Dirección, nos
quedaban pendientes otros TADs como Piso y Departamento. A continuación, se propone
una implementación parcial del TAD Piso.

1 # TAD Piso

2 # Estructura interna
3 Tipo:
4 Piso = registro
5 numero: Entero
6 departamentos: Lista(Departamento)

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 35

 7 finRegistro

8 # Constructores
9 proced crearPiso(num_piso: Entero, ref piso: Piso)
10 piso.numero <- num_piso
11 listaVacia(piso.departamentos)
12 finProced

13 # Modificadores
14 proced agregarDeptoPiso(depto: Departamento, ref piso: Piso)
15 insertar(depto, piso.departamentos)
16 finProced

17 # Proyectores
18 funcion pisoNumero(piso: Piso): Entero
19 funcion cantidadDeptos(piso: Piso): Entero

20 # Destructores
21 proced destruirPiso(ref piso: Piso)

Concluimos entonces con una primera creación parcial del TAD Edificio y sus TADs
asociados. Le proponemos ahora resolver la actividad final de la unidad, presentando para
su corrección la implementación completa del TAD Edificio.

ACTIVIDAD 2 (Tarea)

Le pedimos que realice la Actividad que le proponemos en el campus y la envíe al tutor para
su corrección.

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 36

SINTESIS DE LA UNIDAD

En esta unidad hemos recorrido brevemente los conceptos mínimos para embarcar temas
más complejos que se verán en las próximas unidades, recordando que los tipos de datos
nos permiten representar entidades abstractas a través de la asociación de un conjunto de
valores y operaciones aplicables sobre ellos. Su utilización nos provee mayor seguridad en
la programación ya que los lenguajes pueden detectar inconsistencias a través de sus
sistemas de tipos, los cuales pueden ser fuertes o débiles. También podremos aprovechar
mejoras de rendimiento en lenguajes compilados debido a la capacidad de gestionar su
almacenamiento según el tipo asignado.

Los lenguajes en general se dividen en compilados o interpretados, pero existen casos

híbridos como Java. En el caso de los primeros, existe un proceso previo a la ejecución del
programa que se lo denomina compilación, donde se transforma el código fuente en código
de programa. Los lenguajes interpretados simplemente ejecutan el código fuente,
otorgando mayor flexibilidad y portabilidad respecto a los compilados, pero sacrificando
probablemente rendimiento y seguridad.

Los sistemas se ejecutan utilizando dos tipos de memoria, una de rápido acceso y limitada
que se llama pila de ejecución y otra dinámica más amplia denominada heap. Dentro de los
tipos de datos conocidos tendremos el puntero que permite referenciar una dirección en
memoria dinámica, muy útil para definir estructuras recursivas.

Un tipo abstracto de datos (TAD) se apoya en la abstracción, encapsulamiento y el

ocultamiento de la información. A través de la abstracción podremos modelar problemas
complejos del mundo real, encapsulando una cierta estructura asociada a operaciones
aplicables a ella y logrando ocultar su implementación interna a través de una interfaz del
TAD.

Veamos el siguiente cuadro conceptual:

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 37

 Lenguajes 3ra
Fuerte
generación incorporan Sistema de
Tipos pueden ser

usan una Lenguajes

Compilados pueden ser
Débil
Pila de pueden tener
ejecución sistema de tipo
Estático proveen

Memoria Lenguajes
Dinámico
dinámica Interpretados
TIPO DE DATOS
se guarda en
es un

Puntero
es un

Estructurados
Básicos
es un

Abstracción
TAD
provee
Encapsulamiento

Ocultamiento

ALGORITMOS Y ESTRUCTURAS DE DATOS II – UNIDAD 1 Pág. 38