PDF de programación - Estructuras de Datos en Java

Estructuras de Datos en Java






1. Antecedentes

Introducción a la Orientación a Objetos

La programación orientada a objetos (POO) es una nueva manera de
enfocar la programación. Desde sus comienzos, la programación ha estado
gobernada por varias metodologías. En cada punto crítico de la evolución de
la programación se creaba un nuevo enfoque para ayudar al programador a
manejar programas cada vez más complejos. Los primeros programas se
crearon mediante un proceso de cambio de los conmutadores del panel
frontal de la computadora. Obviamente, este enfoque solo es adecuado para
programas pequeños. A continuación se invento el lenguaje ensamblador que
permitió escribir programas más largos. El siguiente avance ocurrió en los
años 50 cuando se invento el primer lenguaje de alto nivel (FORTRAN).


Mediante un lenguaje de alto nivel, un programador estaba capacitado
para escribir programas que tuvieran una longitud de varios miles de líneas.
Sin embargo, el método de programación usado en el comienzo era un
enfoque adhoc que no solucionaba mucho. Mientras que esto esta bien para
programas relativamente cortos, se convierte en “código espagueti” ilegible y
difícil de tratar cuando se aplica a programas más largos. La eliminación del
código espagueti se consiguió con
los lenguajes de
programación estructurados en los años sesenta. Estos lenguajes incluyen
ALGOL y PASCAL. En definitiva, C es un lenguaje estructurado, y casi todos los
tipos de programas que se han estado haciendo se podrían llamar programas
estructurados.

la creación de


Los programas estructurados se basan en estructuras de control bien
definidas, bloques de código,
la ausencia del GOTO, y subrutinas
independientes que soportan recursividad y variables locales. La esencia de la
programación estructurada es la reducción de un programa a sus elementos
constitutivos. Mediante la programación estructurada un programador medio
puede crear y mantener programas de una longitud superior a 50,000 líneas.


Aunque la programación estructurada nos ha llevado a excelentes
resultados cuando se ha aplicado a programas moderadamente complejos,
llega a fallar en algún punto cuando el programa alcanza un cierto tamaño.
Para poder escribir programas de mayor complejidad se necesitaba de un
nuevo enfoque en la tarea de programación. A partir de este punto nace la
programación orientada a objetos (POO). La POO toma las mejores ideas
incorporadas en la programación estructurada y las combina con nuevos y
potentes conceptos que permiten organizar los programas de forma más
efectiva. La POO permite descomponer un problema en subgrupos
relacionados. Cada subgrupo pasa a ser un objeto autocontenido que contiene
sus propias instrucciones y datos que le relacionan con ese objeto. De esta

manera, la complejidad se reduce y el programador puede tratar programas
más largos.


Todos

los

lenguajes de POO comparten

tres características:

encapsulación, polimorfismo y herencia.


Encapsulación.


La encapsulación es el mecanismo que agrupa el código y los datos que
maneja y los mantiene protegidos frente a cualquier interferencia y mal uso.
En un lenguaje orientado a objetos, el código y los datos suelen empaquetarse
de la misma forma en que se crea una “caja negra” autocontenida. Dentro de
la caja son necesarios tanto el código como los datos. Cuando el código y los
datos están enlazados de esta manera, se ha creado un objeto. En otras
palabras, un objeto es el dispositivo que soporta encapsulación.


En un objeto, los datos y el código, o ambos, pueden ser privados para
ese objeto o públicos. Los datos o el código privado solo los conoce o son
accesibles por otra parte del objeto. Es decir, una parte del programa que
esta fuera del objeto no puede acceder al código o a los datos privados.
Cuando los datos o el código son públicos, otras partes del programa pueden
acceder a ellos, incluso aunque este definido dentro de un objeto.
Normalmente, las partes públicas de un objeto se utilizan para proporcionar
una interfaz controlada a las partes privadas del objeto.


Para todos los propósitos, un objeto es una variable de un tipo definido
por el usuario. Puede parecer extraño que un objeto que enlaza código y
datos se pueda contemplar como una variable. Sin embargo, en programación
orientada a objetos, este es precisamente el caso. Cada vez que se define un
nuevo objeto, se esta creando un nuevo tipo de dato. Cada instancia
específica de este tipo de dato es una variable compuesta.

Polimorfismo.


Polimorfismo (del Griego, cuyo significado es “muchas formas”) es la
cualidad que permite que un nombre se utilice para dos o más propósitos
relacionados pero técnicamente diferentes. El propósito del polimorfismo
aplicado a la POO es permitir poder usar un nombre para especificar una clase
general de acciones. Dentro de una clase general de acciones, la acción
específica a aplicar está determinada por el tipo de dato. Por ejemplo, en C,
que no se basa significativamente en el polimorfismo, la acción de valor
absoluto requiere tres funciones distintas: abs(), labs() y fabs(). Estas tres
funciones calculan y devuelven el valor absoluto de un entero, un entero largo
y un valor real, respectivamente. Sin embargo, en C++, que incorpora
polimorfismo, a cada función se puede llamar abs().


El tipo de datos utilizado para llamar a la función determina que
versión específica de la función se esta usando, es decir, es posible usar un

nombre de función para propósitos muy diferentes. Esto se llama sobrecarga
de funciones.


De manera general, el concepto de polimorfismo es la idea de “una
interfaz, múltiples métodos”. Esto significa que es posible diseñar una
interfaz genérica para un grupo de actividades relacionadas. Sin embargo, la
acción específica ejecutada depende de
los datos. La ventaja del
polimorfismo es que ayuda a reducir la complejidad permitiendo que la misma
interfaz se utilice para especificar una clase general de acción. Es trabajo del
compilador seleccionar la acción específica que se aplica a cada situación. El
programador no necesita hacer esta selección manualmente, solo necesita
recordar y utilizar la interfaz general.


El polimorfismo se puede aplicar tanto a funciones como a operadores,
prácticamente todos los lenguajes de programación contienen una aplicación
limitada de polimorfismo cuando se relaciona con los operadores aritméticos,
por ejemplo, en C, el signo + se utiliza par añadir enteros, enteros largos,
caracteres y valores reales. En estos casos, el compilador automáticamente
sabe que tipo de aritmética debe aplicar, en C++, se puede ampliar este
concepto a otros tipos de datos que se definan, este tipo de polimorfismo se
llama sobrecarga de operadores.



Herencia.


La herencia es el proceso mediante el cual un objeto puede adquirir las
propiedades de otro. Mas en concreto, un objeto puede heredar un conjunto
general de propiedades a alas que puede añadir aquellas características que
son específicamente suyas. La herencia es importante porque permite que un
objeto soporte el concepto de clasificación jerárquica. Mucha información se
hace manejable gracias a esta clasificación, por ejemplo, la descripción de
una casa. Una casa es parte de una clase general llamada edificio, a su vez,
edificio es una parte de la clase mas general estructura, que es parte de la
clase aun más general de objetos que se puede llamar obra-hombre.


En cualquier caso, la clase hija hereda todas las cualidades asociadas con
la clase padre y le añade sus propias características definitorias. Sin el uso de
clasificaciones ordenadas, cada objeto tendría que definir todas
las
características que se relacionan con él explícitamente.


Sin embargo, mediante el uso de la herencia, es posible describir un
objeto estableciendo la clase general (o clases) a las que pertenece, junto
con aquellas características específicas que le hacen único.



Tipos de Datos Abstractos


Abstracción: consiste en ignorar los detalles de la manera particular en
que está hecha una cosa, quedándonos solamente con su visión general. Tipo
de Dato Abstracto (TDA) se define como un conjunto de valores que pueden
tomar los datos de ese tipo, junto a las operaciones que los manipulan.

Un TDA es un modelo matemático de estructuras de datos que especifican los
tipos de datos almacenados, las operaciones definidas sobre esos datos y los
tipos de parámetros de esas operaciones.


TAD = Valores (tipo de dato) + operaciones



Un TDA define lo que cada operación debe hacer, más no como la debe
hacer. En un lenguaje de programación como Java un TDA puede ser
expresado como una interface, que es una simple lista de declaraciones de
métodos.


Un TDA es materializado por una estructura de datos concreta, en Java,
es modelada por una clase. Una clase define los datos que serán almacenados
y las operaciones soportadas por los objetos que son instancia de la clase. Al
contrario de las interfaces, las clases especifican como las operaciones son
ejecutadas (implementación).

Ejemplos de tipos de datos abstractos son las Listas, Pilas, Colas, etc., que se
discutirán más adelante.



Estructu