PDF de programación - Estructuras de datos en Java

Estructuras de datos en Java

Estructuras de datos en Java

Luis Joyanes Aguilar

Ignacio Zahonero Martínez

madrid • bogotá • buenos aires • caracas • guatemala • lisboa • méxico

nueva york • panamá • santiago • sÃo paulo

AucklAnd • hAmburgo • londres • milán • montreAl • nuevA delhi • pArís

sAn frAncisco • sidney • singApur • st. louis • tokio • toronto

ESTRUCTURAS DE DATOS EN JAVA.

No está permitida la reproducción total o parcial de este libro, ni su tratamiento informático,
ni la transmisión de ninguna forma o por cualquier medio, ya sea electrónico, mecánico,
por fotocopia, por registro u otros métodos, sin el permiso previo y por escrito de los
titulares del Copyright.

DERECHOS RESERVADOS © 2008, respecto a la primera edición en español, por

MCGRAW-HILL/INTERAMERICANA DE ESPAÑA, S. A. U.
Edificio Valrealty, 1. ª Planta
Basauri, 17
28023 Aravaca (Madrid)

ISBN: 978-84-481-5631-2
Depósito legal:

Editor: José Luis García
Técnico Editorial: Blanca Pecharromán
Compuesto en: Gesbiblo, S. L.
Diseño de cubierta: Gesbiblo, S. L.
Impreso por:

IMPRESO EN ESPAÑA – PRINTED IN SPAIN

A Luis y Paloma.

PRÓLOGO

Dos de las disciplinas clásicas en todas las carreras relacionadas con la Informática y las Ciencias
de la Computación son Estructuras de Datos y Algoritmos, o bien una sola disciplina si ambas
se estudian integradas: “Algoritmos y Estructuras de Datos”. El estudio de estructuras de datos
y de algoritmos es tan antiguo como el nacimiento de la programación y se ha convertido en
estudio obligatorio en todos los currículos desde finales de los años 70 y sobre todo en esa
misma década cuando apareció el lenguaje Pascal de la mano del profesor Niklaus Wirtz, y
posteriormente en la década de los ochenta con la aparición de su obra —ya clásica— Algorithms
and Data Structures (1986).

Muchas facultades y escuelas de Ingeniería, así como institutos tecnológicos, comienzan sus
cursos de Estructuras de Datos con el soporte de Java. Existen muchas razones por las cuales
pensamos que Java es apropiado para la formación en estructuras de datos. Una de ellas es que
Java, es un lenguaje más moderno que C o C++, con mejores funcionalidades, orientado a obje-
tos, a la programación en Web,… Además, a partir de Java 1.5 permite diseñar clases genéricas,
de forma similar a las plantillas (templates) de C++.

El primer problema que se suele presentar al estudiante de Estructura de Datos que, probable-
mente, procederá de un curso de nivel básico, medio o avanzado de introducción o fundamentos
de programación o bien de iniciación en algoritmos, es precisamente el modo de afrontar infor-
mación compleja desde el principio. Aunque es verdad que Java1 tiene muchas ventajas sobre un
lenguaje procedimental, por ejemplo C, muchas de estas ventajas no se hacen evidentes hasta que
un programa se “vuelve” o “hace” más complejo. En este caso el paradigma orientado a objetos
es una herramienta de programación y organización muy poderosa y con grandes ventajas para
la enseñanza y posterior tarea profesional.

A primera vista, Java es más interesante que un lenguaje procedimental por su enfoque orien-
tado a objetos, aunque puede parecer, en el caso del análisis y diseño de algoritmos y estructuras
de datos, que esta propiedad añade una complejidad inherente y no es así, la implementación en
clases y objetos puede darle una nueva potencialidad. Pensando en esta transición se ha incluido
un capítulo dedicado a conceptos teórico-prácticos de orientación a objetos. En cualquier caso, el
curso está soportando la comprensión del tipo abstracto de datos (TAD) de modo que el estilo de
programación empleado en el texto se basa en el estudio de tipos abstractos de datos como base
para la formación en orientación a objetos.

Se estudian estructuras de datos con un objetivo fundamental: aprender a escribir programas más
eficientes. También cabe aquí hacerse la pregunta: ¿Por qué se necesitan programas más eficientes
cuando las nuevas computadoras son más rápidas cada año? La razón tal vez resida en el hecho de
que nuestras metas no se amplían a medida que se aumentan las características de las computadoras.
La potencia de cálculo y las capacidades de almacenamiento aumentan la eficacia y ello conlleva un
aumento de los resultados de las máquinas y de los programas desarrollados por ellas.

 Véanse otras obras de los autores, publicadas también en McGraw-Hill, tales como Programación en C++,
Programación en Java 2 o Programación en C.

vii

viii

Prólogo

La búsqueda de la eficiencia de un programa no debe chocar con un buen diseño y una codi-
ficación clara y legible. La creación de programas eficientes tiene poco que ver con “trucos de
programación” sino, al contrario, se basan en una buena organización de la información y buenos
algoritmos. Un programador que no domine los principios básicos de diseños claros y limpios
probablemente no escribirá programas eficientes. A la inversa, programas claros requieren orga-
nizaciones de datos claras y algoritmos claros, precisos y transparentes.

La mayoría de los departamentos informáticos reconocen que las destrezas de buena pro-
gramación requieren un fuerte énfasis en los principios básicos de ingeniería de software. Por
consiguiente, una vez que un programador ha aprendido los principios para diseñar e implemen-
tar programas claros y precisos, el paso siguiente es estudiar los efectos de las organizaciones de
datos y los algoritmos en la eficiencia de un programa.

EL EnfOquE dEL LibRO
En esta obra se muestran numerosas técnicas de representación de datos. En su contexto las
mismas se engloban en los siguientes principios:

1. Cada estructura de datos tiene sus costes y sus beneficios. Los programadores y dise-
ñadores necesitan una comprensión rigurosa y completa de cómo evaluar los costes y
beneficios para adaptarse a los nuevos retos que afronta la construcción de la aplicación.
Estas propiedades requieren un conocimiento o comprensión de los principios del análisis
de algoritmos y también una consideración práctica de los efectos significativos del medio
físico empleado (p.e. datos almacenados en un disco frente a memoria principal).

2. Los temas relativos a costes y beneficios se consideran dentro del concepto de elemento
de compensación. Por ejemplo, es bastante frecuente reducir los requisitos de tiempo en
beneficio de un incremento de requisitos de espacio en memoria, o viceversa.

3. Los programadores no deben reinventar la rueda continuamente. Por consiguiente, los
estudiantes necesitan aprender las estructuras de datos utilizadas junto con los algorit-
mos correspondientes.

4. Los datos estructurados siguen a las necesidades. Los estudiantes deben aprender a eva-
luar primero las necesidades de la aplicación y, a continuación, encontrar una estructura
de datos en correspondencia con sus funcionalidades.

Esta edición describe, fundamentalmente, estructuras de datos, métodos de organización
de grandes cantidades de datos y algoritmos junto con el análisis de los mismos, en esencia
estimación del tiempo de ejecución de algoritmos. A medida que las computadoras se vuelven
más y más rápidas, la necesidad de programas que pueden manejar grandes cantidades de
entradas se vuelve más críticas y su eficiencia aumenta a medida que estos programas pueden
manipular más y mejores organizaciones de datos. Analizando un algoritmo antes de que se
codifique realmente, los estudiantes pueden decidir si una determinada solución será factible
y rigurosa. Por ejemplo, se pueden ver cómo diseños e implementaciones cuidadas pueden
reducir los costes en tiempo y memoria. Por esta razón, se dedican dos capítulos, en exclusiva
a tratar los conceptos fundamentales de análisis de algoritmos, y en un gran número de algo-
ritmos se incluyen explicaciones de tiempos de ejecución para poder medir la complejidad y
eficiencia de los mismos.

Prólogo



ix

El método didáctico que sigue nuestro libro ya lo hemos seguido en otras obras nuestras y
busca preferentemente enseñar al lector a pensar en la resolución de un problema siguiendo un
determinado método ya conocido o bien creado por el propio lector. Una vez esbozado el método,
se estudia el algoritmo correspondiente junto con las etapas que pueden resolver el problema. A
continuación, se escribe el algoritmo, en la mayoría de las veces en lenguaje Java. Para que el
lector pueda verificar su programa en la computadora, se incluyen los códigos fuente en la página
web del libro.

Uno de los objetivos fundamentales es enseñar al estudiante, simultáneamente, buenas reglas
de programación y análisis de algoritmos de modo que puedan desarrollar los programas con la
mayor eficiencia posible.

Aunque se ha tratado de que el material de este texto sea lo menos dependiente del lenguaje,
la programación, como el lector sabe, requiere el uso de un lenguaje específico. En nuestro caso
se ha elegido Java como espina dorsal de programación

Java ya es un lenguaje de programación muy extendido en el mundo de la programación y de
la ingeniería de software, tal vez el más utilizado por su gran vinculación con Internet y la web,
y también en comparación con el otro gran lenguaje de programación C++. Java ofrece muchos
beneficios y los programadores suelen verlo como más seguro, más portable y más fácil de utili-
zar que C++. Por estas propiedades, es un lenguaje idóneo para el examen e implementación de
estructuras de datos fundamentales. Otras características importantes de Java, tales como hilos
(threads) y sus GUIs (Interfaces gráficas de usuario), aunque importantes, no se suelen necesitar
en este texto y, por consiguiente, no se han examinado.

Java es un lenguaje de programación sencillo, orientado a objetos, distribuido, inter-
pretado, robusto, seguro, neutro ante la arquitectura, portable, altas prestaciones,
m