Source: http://www.slideshare.net/DebateInformaticaMaterias/estructuras-de-datos-codeqwrr
Timestamp: 2015-09-03 08:02:39+00:00

Document:
Estructuras de datos (codeqwrr)
11. programación gráfica en c
programar en java 7ed(code 1232342...
10. programacion c
12. el lenguaje de programacion c++
5. la cara oculta de c++ builder by Jose Alberto Noh Noh
Claudia Mayeli Cantero Otalora
COMPARTIDO POR . SAN JUAN
COMPARTE TUS EBOOKS
nueva york • panamá • santiago • sÃo paulo
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
Edificio Valrealty, 1. ª Planta
ISBN: 978-84-481-5631-2
Editor: José Luis García
Técnico Editorial: Blanca Pecharromán
Compuesto en: Gesbiblo, S. L.
Diseño de cubierta: Gesbiblo, S. L.
A Luis y Paloma.
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 objetos, 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, probablemente, 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 información compleja desde el principio. Aunque es verdad que Java 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 orientado 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.
viii Prólogo
La búsqueda de la eficiencia de un programa no debe chocar con un buen diseño y una codificació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 organizaciones de datos claras y algoritmos claros, precisos y transparentes.
La mayoría de los departamentos informáticos reconocen que las destrezas de buena programació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 implementar 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.
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 algoritmos correspondientes.
4.	Los datos estructurados siguen a las necesidades. Los estudiantes deben aprender a evaluar 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 algoritmos se incluyen explicaciones de tiempos de ejecución para poder medir la complejidad y
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
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
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 utilizar 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, interpretado, robusto, seguro, neutro ante la arquitectura, portable, altas prestaciones,
multihilo y dinámico
Por el contrario, Java tiene pocas pero algunas desventajas comparado con C++: no soporta
bien programación genérica, características de E/S menos potentes, … Pensando en aquellos
lectores que deseen conocer las características del lenguaje C++, en la página oficial del libro, el
lector, el profesor y el maestro, podrán encontrar amplia información de C++ y también en obras
nuestras, “hermanas” de este texto, tales como Programación en Java y Estructuras de datos en
C++, que se encuentran en dicha página.
Los programas han sido compilados en diversos entornos tales como JCreator y NetBeans
utilizando la plataforma J2SE5 conocida popularmente como versión 5. La reciente aparición
de Java SE 6, también conocida como Java 6 puede ser utilizada también para el desarrollo de
programas. Para consultar las nuevas características de la versión 6 de Java, presentada a finales
del 2006, visite la página de Sun:
//java.sun.com/javase/6
//java.sun.com/javase/downloads/index.jsp
El estudio de Algoritmos y de Estructuras de Datos son disciplinas académicas que se incorporan a todos los planes de estudios universitarios de Ingeniería e Ingeniería Técnica en
Informática, Ingeniería de Sistemas Computacionales y Licenciatura en Informática, así como
a los planes de estudio de Formación Profesional e institutos politécnicos. Suele considerarse
también a estas disciplinas como ampliaciones de las asignaturas de Programación, en cualquiera de sus niveles.
En el caso de España, los actuales planes de estudios de Ingeniería Técnica en Informática
e Ingeniería Informática, y los futuros, contemplados en la Declaración de Bolonia, tienen
materias troncales relativas tanto a Algoritmos como a Estructuras de Datos. Igual sucede en
los países iberoamericanos donde también es común incluir estas disciplinas en los currículos
de carreras de Ingeniería de Sistemas y Licenciaturas en Informática. ACM, la organización
profesional norteamericana más prestigiosa a nivel mundial, incluye en las recomendaciones
de sus diferentes currículos de carreras relacionadas con informática el estudio de materias de
algoritmos y estructuras de datos. En el conocido Computing Curricula de 1992 se incluyen
descriptores recomendados de Programación y Estructura de Datos, y en los últimos currículos
publicados, Computing Curricula 2001 y 2005, se incluyen en las áreas PF de Fundamentos de
Programación (Programming Fundamentals, PF1 a PF4) y AL de Algoritmos y Complejidad
(Algorithms and Complexity, AL1 a AL3). En este libro se han incluido los descriptores más
importantes tales como Algoritmos y Resolución de Problemas, Estructuras de datos fundamentales, Recursión, Análisis de algoritmos básicos y estrategias de algoritmos. Además se incluye
un estudio de algoritmos de estructuras discretas tan importantes como Árboles y Grafos. Por
último, se desarrolla y se ponen ejemplos de todas las colecciones presentes en Java.
Esta obra está concebida como un libro didáctico y eminentemente práctico. Se pretende
enseñar los principios básicos requeridos para seleccionar o diseñar las estructuras de datos
que ayudarán a resolver mejor los problemas y a no a memorizar una gran cantidad de implementaciones. Por esta razón, se presentan numerosos ejercicios y problemas resueltos en su
totalidad, siempre organizados sobre la base del análisis del problema y el algoritmo correspondiente en Java. Los lectores deben tener conocimientos a nivel de iniciación o nivel medio
en programación. Es deseable haber cursado al menos un curso de un semestre de introducción a los algoritmos y a la programación, con ayuda de alguna herramienta de programación,
preferentemente, y se obtendrá el mayor rendimiento si además se tiene conocimiento de un
lenguaje estructurado como C.
El libro busca de modo prioritario enseñar al lector técnicas de programación de algoritmos y
estructuras de datos. Se pretende aprender a programar practicando el análisis de los problemas
y su codificación en Java.
Está pensado para un curso completo anual o bien dos semestres, para ser estudiado de modo
independiente —por esta razón se incluyen las explicaciones y conceptos básicos de la teoría
de algoritmos y estructuras de datos— o bien de modo complementario, exclusivamente como
apoyo de libros de teoría o simplemente del curso impartido por el maestro o profesor en su aula
de clase. Pensando en su uso totalmente práctico se ha optado por seguir una estructura similar
al libro Algoritmos y Estructura de Datos publicado por McGraw-Hill por los profesores Joyanes
y Zahonero de modo que incluye muchos de los problemas y ejercicios propuestos en esta obra.
En caso de realizar su estudio conjunto, uno actuaría como libro de texto, fundamentalmente, y
el otro como libro de prácticas para el laboratorio y el estudio en casa o en un curso profesional.
El contenido del libro sigue los programas clásicos de las disciplinas Estructura de Datos y/o
Estructuras de Datos y de la Información respetando las directrices emanadas de los Currícula
de 1991 y las actualizadas del 2001 y 2005 de ACM/IEEE, así como de los planes de estudio
de Ingeniero Informático e Ingeniero Técnico en Informática de España y los de Ingeniero de
Sistemas y Licenciado en Informática de muchas universidades latinoamericanas.
La Parte I, Análisis de algoritmos y estructuras de datos básicas describe el importante
concepto de análisis de un algoritmo y las diferentes formas de medir su complejidad y eficiencia; asimismo se describen las estructuras de datos más simples tales como arrays, cadenas o
estructuras. La Parte II, Diseño de algoritmos (Recursividad, ordenación y búsqueda) examina
los algoritmos más utilizados en la construcción de cualquier programa tales como los relativos
a búsqueda y ordenación, así como las potentes técnicas de manipulación de la recursividad.
La Parte III, Estructuras de datos lineales (Abstracción de datos, listas, pilas, colas y tablas
hash) constituye una de las partes avanzadas del libro y suele formar parte de cursos de nivel
medio/alto en organización de datos. Por último, la Parte IV, Estructuras de datos no lineales
(Árboles, grafos y sus algoritmos) constituye también una de las partes avanzadas del libro; su
conocimiento y manipulación permitirán al programador obtener el máximo aprovechamiento
en el diseño y construcción de sus programas. La descripción más detallada de los capítulos
correspondientes se reseñan a continuación.
Capítulo 1. Algoritmos y estructuras de datos. Los tipos de datos y la necesidad de su organización en estructuras de datos es la parte central de este capítulo. El estudio de los conceptos
de algoritmos y programas y su herramienta de representación más característica, el pseudocódigo, son uno de los objetivos más ambiciosos de esta obra. El capítulo hace una revisión
de sus propiedades más importantes: representación, eficiencia y exactitud. Se describe la
notación O grande utilizada preferentemente en el análisis de algoritmos.
Capítulo 2. Tipos de datos: Clases y objetos. La programación orientada a objetos es, hoy
en día, el eje fundamental de la programación de computadoras. Su núcleo esencial son los
conceptos de clases y objetos. En el capítulo se consideran los conceptos teóricos de encapsulación de datos y tipos abstractos de datos como soporte de una clase y de un objeto; también
se analiza el modo de construcción de objetos, así como conceptos tan importantes como la
visibilidad de los miembros de una clase. Constructores, paquetes y recolección de objetos
junto con la definición de tipos abstractos de datos en Java completan el capítulo.
Capítulo 3. Arrays (arreglos) y cadenas. Los diferentes tipos de arrays (arreglos) se describen
y detallan junto con la introducción a las cadenas (strings). La importante clase String se
describe con detalle, así como la especificación de la clase Vector.
Capítulo 4. Clases derivadas y polimorfismo. Uno de los conceptos más empleados en programación orientada a objetos y que ayudará al programador de un modo eficiente al diseño
de estructura de datos son las clases derivadas. La propiedad de herencia, junto con el polimorfismo ayudan a definir con toda eficacia las clases derivadas. Otro término fundamental
xii Prólogo
en POO son las clases abstractas que permitirán la construcción de clases derivadas. Java,
soporta herencia simple y, por razones de simplicidad, no soporta herencia múltiple, como
C++, al objeto de no añadir problemas al diseño. Los conceptos de interfaces también se
describen en el capítulo.
Capítulo 5. Algoritmos recursivos. La recursividad es una de las características más sobresalientes en cualquier tipo de programación, Los algoritmos recursivos abundan en la vida
ordinaria y el proceso de abstracción que identifica estos algoritmos debe conducir a un buen
diseño de algoritmos recursivos. Los algoritmos más sobresalientes y de mayor difusión en el
mundo de la programación se explican con detalle en el capítulo. Así, se describen algoritmos
como mergesort (ordenación por mezclas), backtracking (vuelta atrás) y otros.
Capítulo 6. Algoritmos de ordenación y búsqueda. Las operaciones más frecuentes en el proceso de estructura de datos, son: ordenación y búsqueda de datos específicos. Los algoritmos
más populares y eficientes de proceso de estructuras de datos internas se describen en el
capítulo junto con un análisis de su complejidad. Así, se analizan algoritmos de ordenación
básicos y algoritmos avanzados como Shell, QuickSort, BinSort o RadixSort; en lo relativo a
métodos de búsqueda se describen los dos métodos más utilizados: secuencial y binaria.
Capítulo 7. Algoritmos de ordenación de archivos. Los archivos (ficheros) de datos son, posiblemente, las estructuras de datos más diseñadas y utilizadas por los programadores de
aplicaciones y programadores de sistemas. Los conceptos de flujos y archivos de Java junto
con los métodos clásicos y eficientes de ordenación de archivos se describen en profundidad
Capítulo 8. Listas enlazadas. Una lista enlazada es una estructura de datos lineal de gran uso
en la vida diaria de las personas y de las organizaciones. Su implementación mediante listas
enlazadas es el objetivo central de este capítulo. Variantes de las listas enlazadas simples
como doblemente enlazadas y circulares, son también, motivo de estudio en el capítulo.
Capítulo 9. Pilas. La pila es una estructura de datos simple cuyo concepto forma también parte,
en un elevado porcentaje de la vida diaria de las personas y organizaciones, como las listas. El
tipo de dato Pila se puede implementar con arrays o con listas enlazadas y describe ambos
algoritmos y sus correspondientes implementaciones en Java.
Capítulo 10. Colas. Al igual que las pilas, las colas conforman otra estructura que abunda en la
vida ordinaria. La implementación del TAD Cola se puede hacer con arrays (arreglos), listas
enlazadas e incluso listas circulares. Asimismo, se analiza también en el capítulo el concepto
de la bicola o cola de doble entrada.
Capítulo 11. Colas de prioridades y montículos. Un tipo especial de cola, la cola de prioridades, utilizada en situaciones especiales para la resolución de problemas, y el concepto de
montículo (heap, en inglés) se analizan detalladamente, junto con un método de ordenación
por montículos muy eficiente, sobre todo en situaciones complejas y difíciles.
Capítulo 12. Tablas de dispersión, funciones hash. Las tablas aleatorias hash junto con los
problemas de resolución de colisiones y los diferentes tipos de direccionamiento conforman
Capítulo 13. Árboles. Árboles binarios y árboles ordenados. Los árboles son estructuras de
datos no lineales y jerárquicas muy importantes. Estas estructuras son notables en programación avanzada. Los árboles binarios y los árboles binarios de búsqueda se describen con rigor
y profundidad por su importancia en el mundo actual de la programación tanto tradicional
(fuera de línea) como en la Web (en línea).
Capítulo 14. Árboles de búsqueda equilibrados. Este capítulo se dedica a la programación
avanzada de árboles de búsqueda equilibrada. Estas estructuras de datos son complejas y su
diseño y construcción requiere de estrategias y métodos eficientes para su implementación;
sin embargo, su uso puede producir grandes mejoras al diseño y construcción de programas
que sería muy difícil y por otros métodos.
Capítulo 15. Grafos, representación y operaciones. Los grafos son una de las herramientas más
empleadas en matemáticas, estadística, investigación operativa y numerosos campos científicos. El estudio de la teoría de grafos se realiza fundamentalmente como elemento importante
de matemática discreta o matemática aplicada. El conocimiento profundo de la teoría de grafos
junto con los algoritmos de implementación es fundamental para conseguir el mayor rendimiento de las operaciones con datos, sobre todo si éstos son complejos en su organización.
Capítulo 16. Grafos, algoritmos fundamentales. Un programador de alto nivel no puede dejar de
conocer en toda su profundidad la teoría de grafos y sus aplicaciones en el diseño de redes; por
estas razones se analizan los algoritmos de Warshall, Dijkstra y Floid que estudian los caminos mínimos y más cortos. Se termina el capítulo con la descripción del árbol de expansión de
coste mínimo y los algoritmos de Prin y Kruskal que resuelven su diseño e implementación.
Capítulo 17. Colecciones. El importante concepto de colección se estudia en este capítulo. En particular, los contenedores e iteradores son dos términos imprescindibles para la programación
genérica; su conocimiento y diseño son muy importantes en la formación del programador.
El lector puede encontrar en la página web oficial del libro el Anexo con el estudio de árboles B y otros temas avanzados.
Código Java disponible
Los códigos en Java de todos los programas de este libro están disponibles en la web (Internet)
http://www.mhe.es/joyanes —en formato Word para que puedan ser utilizados directamente
y evitar su “tecleado” en el caso de los programas largos, o bien simplemente, para seleccionar,
recortar, modificar… por el lector a su conveniencia, a medida que avanza en su formación.
Muchos profesores y colegas españoles y latinoamericanos nos han alentado a escribir esta obra,
continuación/complemento de nuestra antigua y todavía disponible en librerías, Estructura de
Datos cuyo enfoque era en el clásico lenguaje Pascal. A todos ellos queremos mostrarles nuestro
agradecimiento y, como siempre, brindarles nuestra colaboración si así lo desean.
A los muchos instructores, maestros y profesores, tanto amigos como anónimos, de universidades e institutos tecnológicos y politécnicos de España y Latinoamérica que siempre apoyan
nuestras obras y a los que desgraciadamente nunca podremos agradecer individualmente ese
apoyo; al menos que conste en este humilde homenaje, nuestro eterno agradecimiento y reconocimiento por ese cariño que siempre prestan a nuestras obras. Como saben aquellos que nos
conocen siempre estamos a su disposición en la medida que, físicamente, nos es posible. Gracias
a todos, esta obra es posible, en un porcentaje muy alto, por vuestra ayuda y colaboración.
xiv Prólogo
Y como no, a los estudiantes, a los lectores autodidactas y no autodidactas, que siguen
nuestras obras. Su apoyo es un gran acicate para seguir nuestra tarea. También, gracias queridos lectores.
Pero si importantes son en esta obra nuestros colegas y lectores españoles y latinoamericanos, no podemos dejar de citar al equipo humano que desde la editorial siempre cuida nuestras
obras y sobre todo nos dan consejos, sugerencias, propuestas, nos “soportan” nuestros retrasos,
nuestros “cambios” en la redacción, etc. A Carmelo Sánchez, nuestro editor —y, sin embargo,
amigo— de McGraw-Hill, que en esta ocasión, para no ser menos, nos ha vuelto a asesorar tanto
en la primera fase de realización como en todo el proceso editorial y a nuestro nuevo editor José
Luis García que nos ha seguido apoyando y alentando en nuestro trabajo.
Prólogo................................................................................................................................ vii
Capítulo 1.	Algoritmos y estructuras de datos............................................................ Introducción........................................................................................................... .
1.1.	Tipos de datos............................................................................................... 1.1.1.	Tipos primitivos de datos................................................................ .
1.1.2.	Tipos de datos compuestos y agregados.......................................... 1.2.	La necesidad de las estructuras de datos...................................................... 1.2.1.	Etapas en la selección de una estructura de datos........................... 1.3.	Algoritmos y programas............................................................................... 1.3.1.	Propiedades de los algoritmos......................................................... 1.3.2.	Programas........................................................................................ 1.4.	Eficiencia y exactitud................................................................................... .
1.4.1.	Eficiencia de un algoritmo............................................................... 1.4.2.	Formato general de la eficiencia...................................................... 1.4.3.	Análisis de rendimiento................................................................... 1.5.	Notación O-grande....................................................................................... .
1.5.1.	Descripción de tiempos de ejecución con la notación o................. 1.5.2.	Determinar la notación o................................................................ 1.5.3.	Propiedades de la notación o-grande.............................................. 1.6.	Complejidad de las sentencias básicas de java............................................. RESUMEN............................................................................................................. EJERCICIOS.......................................................................................................... 1
capítulo 2.	Tipos de datos: clases y objetos................................................................. .
Introducción........................................................................................................... .
2.1.	Abstracción en lenguajes de programación.................................................. 2.1.1.	Abstracciones de control................................................................. .
2.1.2.	Abstracciones de datos.................................................................... 2.2.	Tipos abstractos de datos.............................................................................. 2.2.1.	Ventajas de los tipos abstractos de datos......................................... 2.2.2.	Implementación de los tad............................................................ 2.3.	Especificación de los tad........................................................................... 2.3.1.	Especificación informal de un tad. .............................................. .
2.3.2.	Especificación formal de un tad................................................... 2.4.	Clases y objetos. ........................................................................................... .
2.4.1.	¿Qué son objetos?. ........................................................................... .
2.4.2.	¿Qué son clases?.............................................................................. .
2.5.	Declaración de una clase.............................................................................. .
2.5.1.	Objetos............................................................................................. 2.5.2.	Visibilidad de los miembros de la clase.......................................... .
2.5.3.	Métodos de una clase....................................................................... 23
2.5.4.	Implementación de las clases. ......................................................... .
2.5.5.	Clases públicas................................................................................. 2.6.	Paquetes........................................................................................................ 2.6.1.	Sentencia package............................................................................ 2.6.2.	Import.............................................................................................. .
2.7.	Constructores................................................................................................ 2.7.1.	Constructor por defecto................................................................... 2.7.2.	Constructores sobrecargados........................................................... 2.8.	Recolección de objetos. ................................................................................ .
2.8.1.	Método finalize()....................................................................... 2.9.	Objeto que envia el mensaje: this.............................................................. 2.10.	Miembros static de una clase.................................................................... 2.10.1.	Variables static. ........................................................................... 2.10.2.	Métodos static.............................................................................. 2.11.	Clase object................................................................................................ 2.11.1.	Operador instanceof. .................................................................. 2.12.	Tipos abstractos de datos en Java................................................................. 2.12.1.	Implementación del tad Conjunto................................................ .
RESUMEN............................................................................................................. EJERCICIOS.......................................................................................................... PROBLEMAS........................................................................................................ .
Capítulo 3.	Arrays (arreglos) y cadenas........................................................................ Introducción........................................................................................................... .
3.1.	Arrays (arreglos)........................................................................................... 3.1.1.	Declaración de un array.................................................................. 3.1.2.	Creación de un array....................................................................... 3.1.3.	Subíndices de un array.................................................................... 3.1.4.	Tamaño de los arrays. Atributo length............................................. 3.1.5.	Verificación del índice de un array................................................. 3.1.6.	Inicialización de un array............................................................... .
3.1.7.	Copia de arrays. .............................................................................. .
3.2.	Arrays multidimensionales........................................................................... 3.2.1.	Inicialización de arrays multidimensionales.................................. 3.2.2.	Acceso a los elementos de arrays bidimensionales........................ 3.2.3.	Arrays de más de dos dimensiones. ................................................ .
3.3.	Utilización de arrays como parámetros....................................................... 3.3.1.	Precauciones.................................................................................... 3.4.	Cadenas. Clase String................................................................................ 3.4.1.	Declaración de variables Cadena. ................................................... .
3.4.2.	Inicialización de variables Cadena.................................................. 3.4.3.	Inicialización con un constructor de String.................................... 3.4.4.	Asignación de cadenas. ................................................................... .
3.4.5.	Métodos de String......................................................................... 3.4.6.	Operador + con cadenas.................................................................. 3.5.	Clase Vector................................................................................................ 3.5.1.	Creación de un Vector. .................................................................... .
3.5.2.	Insertar elementos............................................................................ 61
Contenido xvii
3.5.3.	Acceso a un elemento...................................................................... 3.5.4.	Eliminar un elemento...................................................................... .
3.5.5.	Búsqueda.......................................................................................... RESUMEN............................................................................................................. EJERCICIOS.......................................................................................................... PROBLEMAS........................................................................................................ .
Capítulo 4.	Clases derivadas y polimorfismo.............................................................. Introducción........................................................................................................... .
4.1.	Clases derivadas........................................................................................... .
4.1.1.	Declaración de una clase derivada.................................................. 4.1.2.	Diseño de clases derivadas.............................................................. 4.1.3.	Sobrecarga de métodos en la clase derivada................................... 4.2.	Herencia pública........................................................................................... .
4.3.	Constructores en herencia............................................................................ .
4.3.1.	Sintaxis............................................................................................ .
4.3.2.	Referencia a la clase base: super................................................... 4.4.	Métodos y clases no derivables: atributo final.......................................... 4.5.	Conversiones entre objetos de clase derivada y clase base............................. 4.6.	Métodos abstractos....................................................................................... 4.6.1.	Clases abstractas.............................................................................. 4.7.	Polimorfismo................................................................................................ .
4.7.1.	Uso del polimorfismo...................................................................... 4.7.2.	Ventajas del polimorfismo............................................................... 4.8.	Interfaces. ..................................................................................................... .
4.8.1.	Implementación de una interfaz...................................................... 4.8.2.	Jerarquía de interfaz........................................................................ 4.8.3.	Herencia de clases e implementación de interfaz............................ 4.8.4.	Variables interfaz............................................................................. RESUMEN............................................................................................................. EJERCICIOS.......................................................................................................... PROBLEMAS........................................................................................................ .
Capítulo 5.	Algoritmos recursivos. ............................................................................... .
5.1.	La naturaleza de la recursividad................................................................... 5.2.	Métodos recursivos....................................................................................... 5.2.1.	Recursividad indirecta: métodos mutuamente recursivos.............. 5.2.2.	Condición de terminación de la recursión....................................... 5.3.	Recursión versus iteración............................................................................ 5.3.1.	Directrices en la toma de decisión iteración/recursión................... 5.3.2.	Recursión infinita............................................................................ 5.4.	Algoritmos divide y vencerás....................................................................... 5.4.1.	Torres de Hanoi................................................................................ 5.4.2.	Búsqueda binaria............................................................................. 5.5.	Backtracking, algoritmos de vuelta atrás..................................................... 5.5.1.	Problema del Salto del caballo......................................................... 5.5.2.	Problema de las ocho reinas............................................................ 125
xviii Contenido
5.6.	Selección óptima........................................................................................... 5.6.1.	Problema del viajante....................................................................... RESUMEN............................................................................................................. EJERCICIOS.......................................................................................................... PROBLEMAS........................................................................................................ .
Capítulo 6.	Algoritmos de ordenación y búsqueda...................................................... Introducción........................................................................................................... .
6.1.	Ordenación.................................................................................................... 6.2.	Algoritmos de ordenación básicos. ........................................................ 6.3.	Ordenación por intercambio......................................................................... 6.3.1.	Codificación del algoritmo de ordenación por intercambio............ 6.3.2.	Complejidad del algoritmo de ordenación por intercambio............ 6.4.	Ordenación por selección. ............................................................................ .
6.4.1.	Codificación del algoritmo de selección......................................... 6.4.2.	Complejidad del algoritmo de selección.......................................... 6.5.	Ordenación por inserción. ............................................................................ .
6.5.1.	Algoritmo de ordenación por inserción........................................... 6.5.2.	Codificación del algoritmo de ordenación por inserción................ 6.5.3.	Complejidad del algoritmo de inserción.......................................... 6.6.	Ordenación Shell........................................................................................... 6.6.1.	Algoritmo de ordenación shell........................................................ 6.6.2.	Codificación del algoritmo de ordenación shell............................. 6.6.3.	Análisis del algoritmo de ordenación shell..................................... 6.7.	Ordenación rapida (Quicksort)..................................................................... 6.7.1.	Algoritmo Quicksort........................................................................ 6.7.2.	Codificación del algoritmo Quicksort............................................. 6.7.3.	Análisis del algoritmo Quicksort. ................................................... .
6.8.	Ordenación de objetos.................................................................................. .
6.9.	Búsqueda en listas: búsqueda secuencial y binaria...................................... 6.9.1.	Búsqueda secuencial........................................................................ 6.9.2.	Búsqueda binaria............................................................................. 6.9.3.	Algoritmo y codificación de la búsqueda binaria........................... 6.9.4.	Análisis de los algoritmos de búsqueda.......................................... .
Capítulo 7.	Algoritmos de ordenación de archivos...................................................... Introducción........................................................................................................... .
7.1.	Flujos y archivos........................................................................................... 7.2.	Clase File................................................................................................... .
7.3.	Flujos y jerarquía de clases........................................................................... 7.3.1.	rchivos de bajo nivel: Fileinputstream y Fileoutputstream.... A
7.4.	Ordenación de un archivo. Métodos de ordenación externa........................ 7.5.	Mezcla directa............................................................................................... 7.5.1.	Codificación del algoritmo de mezcla directa................................. 193
Contenido xix
7.6.	Fusión natural............................................................................................... 7.6.1.	Algoritmo de la fusión natural........................................................ .
7.7.	Mezcla equilibrada múltiple......................................................................... 7.7.1.	Algoritmo de la mezcla equilibrada múltiple.................................. 7.7.2.	Declaración de archivos para la mezcla equilibrada múltiple......... 7.7.3.	Cambio de finalidad de un archivo: entrada ↔ salida................... 7.7.4.	Control del número de tramos......................................................... 7.7.5.	Codificación del algoritmo de mezcla equilibrada múltiple........... 7.8.	Método polifásico de ordenación externa.................................................... .
7.8.1.	Mezcla polifásica con m = 3 archivos........................................... 7.8.2.	Distribución inicial de tramos......................................................... 7.8.3.	Algoritmo de la mezcla.................................................................... 7.7.4.	Mezcla polifásica versus mezcla múltiple....................................... RESUMEN............................................................................................................. EJERCICIOS.......................................................................................................... PROBLEMAS........................................................................................................ .
Capítulo 8.	Listas enlazadas.......................................................................................... Introducción........................................................................................................... .
8.1.	Fundamentos teóricos de listas enlazadas.................................................... 8.2.	Clasificación de listas enlazadas.................................................................. 8.3.	Tipo abstracto de datos (tad) lista............................................................. .
8.3.1.	Especificación formal del tad Lista.............................................. 8.4.	Operaciones de listas enlazadas................................................................... 8.4.1.	Declaración de un nodo................................................................... 8.4.2.	Acceso a la lista: cabecera y cola.................................................... 8.4.3.	Construcción de una lista................................................................ 8.5.	Inserción de un elemento en una lista.......................................................... 8.5.1.	Insertar un nuevo elemento en la cabeza de la lista........................ 8.5.2.	Inserción al final de la lista............................................................. .
8.5.3.	Insertar entre dos nodos de la lista.................................................. 8.6.	Búsqueda en listas enlazadas....................................................................... 8.7.	Eliminación de un nodo de una lista............................................................ 8.8.	Lista ordenada............................................................................................... 8.8.1.	Clase ListaOrdenada................................................................... 8.9.	Lista doblemente enlazada........................................................................... .
8.9.1.	Nodo de una lista doblemente enlazada.......................................... 8.9.2.	Insertar un elemento en una lista doblemente enlazada................. 8.9.3.	Eliminar un elemento de una lista doblemente enlazada................ 8.10.	Listas circulares............................................................................................ 8.10.1.	Insertar un elemento en una lista circular....................................... 8.10.2.	Eliminar un elemento en una lista circular..................................... 8.10.3.	Recorrer una lista circular............................................................... 8.11.	Listas enlazadas genéricas............................................................................ 8.11.1.	Declaración de la clase lista genérica.............................................. 8.11.2.	Iterador de lista................................................................................ RESUMEN............................................................................................................. EJERCICIOS.......................................................................................................... PROBLEMAS........................................................................................................ .
xx Contenido
Capítulo 9.	Pilas.............................................................................................................. Introducción........................................................................................................... .
9.1.	Concepto de pila........................................................................................... .
9.1.1.	Especificaciones de una pila............................................................ 9.2.	Tipo de dato pila implementado con arrays................................................. 9.2.1.	Clase PilaLineal.......................................................................... 9.2.2.	Implementación de las operaciones sobre pilas.............................. .
9.2.3.	Operaciones de verificación del estado de la pila........................... 9.3.	Pila dinámica implementada con un vector................................................. .
9.4.	tipo pila implementado como una lista enlazada. ................................... El
9.4.1.	Clase Pila y Nodopila.................................................................. 9.4.2.	Implementación de las operaciones del tad Pila
con listas enlazadas.......................................................................... 9.5.	Evaluación de expresiones aritméticas con pilas......................................... .
9.5.1.	Notación prefija y notación postfija
de una expresiones aritmética. ........................................................ .
9.5.2.	Evaluación de una expresión aritmética.......................................... 9.5.3.	Transformación de una expresión infija a postfija.......................... 9.5.4.	Evaluación de la expresión en notación postfija............................. .
Capítulo 10.	Colas............................................................................................................. Introducción........................................................................................................... .
10.1.	Concepto de Cola.......................................................................................... 10.1.1.	Especificaciones del tipo abstracto de datos Cola.......................... .
10.2.	Colas implementadas con arrays................................................................. 10.2.1.	Declaración de la clase Cola............................................................ 10.3.	Cola con un array circular. .......................................................................... .
10.3.1.	Clase Cola con array circular.......................................................... 10.4.	Cola con una lista enlazada.......................................................................... 10.4.1.	Declaración de Nodo y Cola............................................................ 10.5.	Bicolas: colas de doble entrada..................................................................... 10.5.1.	Bicola con listas enlazadas.............................................................. RESUMEN............................................................................................................. EJERCICIOS.......................................................................................................... PROBLEMAS........................................................................................................ .
Capítulo 11.	Colas de prioridades y montículos............................................................ Introducción........................................................................................................... .
11.1.	Colas de prioridades..................................................................................... 11.1.1.	Declaración del tad cola de prioridad.......................................... 11.1.2.	Implementación............................................................................... .
11.2.	Tabla de prioridades...................................................................................... 11.2.1.	Implementación............................................................................... .
11.2.2.	Insertar............................................................................................. 315
Contenido xxi
11.2.3.	Elemento de máxima prioridad....................................................... 11.2.4.	Cola de prioridad vacía.................................................................... 11.3.	Vector de prioridades.................................................................................... 11.3.1.	Insertar............................................................................................. 11.3.2.	Elemento de máxima prioridad....................................................... 11.3.3.	Cola de prioridad vacía.................................................................... 11.4.	Montículos.................................................................................................... .
11.4.1.	Definición de montículo.................................................................. 11.4.2.	Representación de un montículo..................................................... .
11.4.3.	Propiedad de ordenación: condición de montículo......................... .
11.4.4.	Operaciones en un montículo.......................................................... 11.4.5.	Operación insertar...................................................................... 11.4.6.	Operación buscar mínimo........................................................... 11.4.7.	Eliminar mínimo............................................................................. .
11.5.	Ordenación por montículos (Heapsort)........................................................ 11.5.1.	Algoritmo......................................................................................... 11.5.2.	Codificación..................................................................................... 11.5.3.	Análisis del algoritmo de ordenación por montículos..................... 11.6.	Cola de prioridades en un montículo............................................................ 11.6.1.	Ejemplo de cola de prioridades. ..................................................... .
Capitulo 12.	Tablas de dispersión, funciones hash........................................................ Introducción........................................................................................................... .
12.1.	Tablas de dispersión...................................................................................... 12.1.1.	Definición de una tablas de dispersión............................................ 12.1.2.	Operaciones de tablas de dispersión................................................ 12.2.	Funciones de dispersión................................................................................ 12.2.1.	Aritmética modular.......................................................................... 12.2.2.	Plegamiento. .................................................................................... .
12.2.3.	Mitad del cuadrado.......................................................................... 12.2.4.	Método de la multiplicación............................................................ 12.3.	Colisiones y resolución de colisiones........................................................... 12.4.	Exploración de direcciones........................................................................... 12.4.1.	Exploración lineal............................................................................ 12.4.2.	Exploración cuadrática.................................................................... 12.4.3.	Doble dirección dispersa................................................................. .
12.5.	Realizacion de una tabla dispersa. ............................................................... .
12.5.1.	Declaración de la clase TablaDispersa............................................ 12.5.2.	Inicialización de la tabla dispersa. .................................................. .
12.5.3.	Posición de un elemento.................................................................. .
12.5.4.	Insertar un elemento en la tabla...................................................... .
12.5.5.	Búsqueda de un elemento................................................................ 12.5.6.	Dar de baja un elemento.................................................................. 12.6.	Direccionamiento enlazado.......................................................................... 12.6.1.	Operaciones de la tabla dispersa enlazada...................................... 12.6.2.	Análisis del direccionamiento enlazado.......................................... 341
xxii Contenido
12.7.	Realizacion de una tabla dispersa encadenada. ........................................... .
12.7.1.	Dar de alta un elemento................................................................... 12.7.2.	Eliminar un elemento...................................................................... .
12.7.3.	Buscar un elemento. ........................................................................ .
Capítulo 13.	Árboles. Árboles binarios y árboles ordenados....................................... Introducción........................................................................................................... .
13.1.	Árboles generales y terminología................................................................. 13.1.1.	Terminología.................................................................................... 13.1.2.	Representación gráfica de un árbol................................................. 13.2.	Arboles binarios............................................................................................ 13.2.1.	Equilibrio......................................................................................... 13.2.2.	Árboles binarios completos............................................................. 13.2.3.	Tad Árbol binario........................................................................... 13.2.4.	Operaciones en árboles binarios...................................................... 13.3.	Estructura de un árbol binario...................................................................... 13.3.1.	Representación de un nodo.............................................................. 13.3.2.	Creación de un árbol binario........................................................... 13.4.	Árbol de expresión........................................................................................ 13.4.1.	Reglas para la construcción de árboles de expresiones................... 13.5.	Recorrido de un árbol................................................................................... 13.5.1.	Recorrido preorden......................................................................... .
13.5.2.	Recorrido en orden.......................................................................... 13.5.3.	Recorrido postorden........................................................................ 13.5.4.	Implementación............................................................................... .
13.6.	Árbol binario de búsqueda........................................................................... .
13.6.1.	Creación de un árbol binario de búsqueda...................................... 13.6.2.	Nodo de un árbol binario de búsqueda............................................ 13.7.	Operaciones en árboles binarios de búsqueda. ............................................ .
13.7.1.	Búsqueda.......................................................................................... 13.7.2.	Insertar un nodo............................................................................... 13.7.3.	Eliminar un nodo............................................................................. RESUMEN............................................................................................................. EJERCICIOS.......................................................................................................... PROBLEMAS........................................................................................................ .
Capítulo 14.	Árboles de búsqueda equilibrados............................................................ Introducción........................................................................................................... .
14.1.	Eficiencia de la búsqueda en un árbol ordenado.......................................... 14.2.	Árbol binario equilibrado, árboles avl. ..................................................... .
14.2.1.	Altura de un árbol equilibrado, árbol avl..................................... 14.3.	nserción en árboles de busqueda equilibrados: rotaciones......................... I
14.3.1.	Proceso de inserción de un nuevo nodo.......................................... .
14.3.2.	Rotación simple............................................................................... .
14.3.3.	Movimiento de enlaces en la rotación simple................................. 14.3.4.	Rotación doble................................................................................. 403
Contenido xxiii
14.3.5.	Movimiento de enlaces en la rotación doble................................... 14.4.	mplementación de la inserción con balanceo y rotaciones........................ I
14.5.	Borrado de un nodo en un árbol equilibrado............................................... .
14.5.1.	Algoritmo de borrado...................................................................... 14.5.2.	Implementación de la operación borrado........................................ RESUMEN............................................................................................................. EJERCICIOS.......................................................................................................... PROBLEMAS........................................................................................................ .
Capítulo 15.	Grafos, representación y operaciones....................................................... Introducción........................................................................................................... .
15.1.	Conceptos y definiciones.............................................................................. 15.1.1.	Grado de entrada, grado de salida de un nodo................................ 15.1.2.	Camino............................................................................................. 15.1.3.	Tipo Abstracto de Datos grafo........................................................ .
15.2.	Representacion de los grafos........................................................................ 15.2.1.	Matriz de adyacencia....................................................................... 15.2.2.	Matriz de adyacencia: Clase GrafoMatriz................................... 15.3.	Listas de adyacencia..................................................................................... 15.3.1.	Clase grafoAdcia.......................................................................... 15.3.2.	ealización de las operaciones con listas de adyacencia................ R
15.4.	Recorrido de un grafo................................................................................... 15.4.1.	Recorrido en anchura....................................................................... 15.4.2.	Recorrido en profundidad. .............................................................. .
15.4.3.	Implementación: Clase recorregrafo......................................... 15.5.	Conexiones en un grafo................................................................................ 15.5.1.	Componentes conexas de un grafo.................................................. 15.5.2.	Componentes fuertemente conexas de un grafo............................. 15.6.	Matriz de caminos. Cierre transitivo............................................................ 15.6.1.	Matriz de caminos y cierre transitivo. ............................................ .
15.7.	Puntos de articulación de un grafo............................................................... 15.7.1.	Búsqueda de los puntos de articulación.......................................... 15.7.2.	Implementación............................................................................... .
Capítulo 16.	Grafos, algoritmos fundamentales............................................................ Introducción........................................................................................................... .
16.1.	Ordenación topológica.................................................................................. 16.1.1.	Algoritmo de una ordenación topológica............................................	16.1.2.	Implementación del algoritmo de ordenación topológica............... 16.2.	Matriz de caminos: algoritmo de Warshall.................................................. 16.2.1.	Implementación del algoritmo de warshall..................................... 16.3.	aminos más cortos con un solo origen: agoritmo de dijkstra................... C
16.3.1.	Algoritmo de dijkstra...................................................................... 16.3.2.	Codificación del algoritmo de dijkstra........................................... 16.4.	odos los caminos mínimos: algoritmo de floyd......................................... T
16.4.1.	Codificación del algoritmo de floyd............................................... 463
xxiv Contenido
16.5.	Árbol de expansión de coste mínimo........................................................... 16.5.1.	Algoritmo de prim........................................................................... 16.5.2.	Codificación del algoritmo de prim................................................ 16.5.3.	Algoritmo de kruscal...................................................................... RESUMEN............................................................................................................. EJERCICIOS.......................................................................................................... PROBLEMAS........................................................................................................ .
Capítulo 17.	Colecciones................................................................................................... Introducción........................................................................................................... .
17.1.	Colecciones en Java...................................................................................... 17.1.1.	Tipos de Colecciones....................................................................... 17.2.	Clases de utilidades: Arrays y collections......................................... 17.2.1.	Clase Arrays. ................................................................................. 17.2.2.	Clase Collections........................................................................ 17.3.	omparación de objetos: comparable y comparator.............................. C
17.3.1.	Comparable. .................................................................................. 17.3.2.	Comparator.................................................................................... 17.4.	Vector y stack........................................................................................... 17.4.1.	Vector............................................................................................. 17.4.2.	Stack............................................................................................... 17.5.	Iteradores de una colección.......................................................................... .
17.5.1.	Enumeration..................................................................................... 17.5.2.	Iterator.............................................................................................. 17.5.3.	ListIterator....................................................................................... .
17.6.	Interfaz Collection. .................................................................................. 17.7.	Listas............................................................................................................. 17.7.1.	Arraylist.......................................................................................... 17.7.2.	Linkedlist........................................................................................ 17.8.	Conjuntos...................................................................................................... 17.8.1.	AbstractSet....................................................................................... 17.8.2.	Hashset............................................................................................. 17.8.3.	TreeSet............................................................................................. 17.9.	Mapas y diccionarios.................................................................................... 17.9.1.	Dictionary.................................................................................... 17.9.2.	Hashtable...................................................................................... 17.9.3.	Map................................................................................................... 17.9.4.	HashMap.......................................................................................... 17.9.5	TreeMap.......................................................................................... 17.10.	Colecciones parametrizadas......................................................................... 17.10.1.	Declaración de un tipo parametrizado............................................ RESUMEN............................................................................................................. EJERCICIOS.......................................................................................................... PROBLEMAS........................................................................................................ .
Bibliografía........................................................................................................................ .
Prólogo................................................................................................................................ 533
Con el estudio de este capítulo, usted podrá:
•	Revisar los conceptos básicos de tipos de datos.
•	Introducirse en las ideas fundamentales de estructuras de datos.
•	Revisar el concepto de algoritmo y programa.
•	Conocer y entender la utilización de la herramienta de programación conocida
por “pseudocódigo”.
•	Entender los conceptos de análisis, verificación y eficiencia de un algoritmo.
•	Conocer las propiedades matemáticas de la notación O.
•	Conocer la complejidad de las sentencias básicas de todo programa Java.
1.1.	Tipos de datos.
1.2.	La necesidad de las estructuras de datos.
1.3.	Algoritmos y programas.
1.4.	Eficiencia y exactitud.
1.5.	Notación O-grande.
1.6.	Complejidad de las sentencias básicas de Java.
♦	Algoritmo.
♦	Complejidad.
♦	Eficiencia.
♦	Estructura de datos.
♦	Notación asintótica.
♦	Pseudocódigo.
♦	Rendimiento de un programa.
♦	Tipo de dato.
La representación de la información es fundamental en ciencias de la computación y en informática.
El propósito principal de la mayoría de los programas de computadoras es almacenar y recuperar
información, además de realizar cálculos. De modo práctico, los requisitos de almacenamiento
y tiempo de ejecución exigen que tales programas deban organizar su información de un modo
que soporte procesamiento eficiente. Por estas razones, el estudio de estructuras de datos y de los
algoritmos que las manipulan constituye el núcleo central de la informática y de la computación.
Se revisan en este capítulo los conceptos básicos de dato, abstracción, algoritmos y programas,
así como los criterios relativos a análisis y eficiencia de algoritmos.
1.1. TIPOS DE DATOS
Los lenguajes de programación tradicionales, como Pascal y C, proporcionan tipos de datos
para clasificar diversas clases de datos. La ventajas de utilizar tipos en el desarrollo de software
[TREMBLAY 2003] son:
•	Apoyo y ayuda en la prevención y en la detección de errores.
•	Apoyo y ayuda a los desarrolladores de software, y a la comprensión y organización de
ideas acerca de sus objetos.
•	Ayuda en la identificación y descripción de propiedades únicas de ciertos tipos.
Detección y prevención de errores mediante lenguajes tipificados (tipeados), como Pascal y
ALGOL, en determinadas situaciones.
La expresión aritmética
6 + 5 + Ana la niña limeña
contiene un uso inapropiado del literal cadena. Es decir, se ha utilizado un objeto de un cierto
tipo (datos enteros) en un contexto inapropiado (datos tipo cadena de caracteres) y se producirá
un error con toda seguridad en el momento de la compilación, en consecuencia, en la ejecución
del programa del cual forme parte.
Los tipos son un enlace importante entre el mundo exterior y los elementos datos que manipulan los programas. Su uso permite a los desarrolladores limitar su atención a tipos específicos
de datos, que tienen propiedades únicas. Por ejemplo, el tamaño es una propiedad determinante
en los arrays y en las cadenas; sin embargo, no es una propiedad esencial en los valores lógicos,
Definición 1: Un tipo de dato es un conjunto de valores y operaciones asociadas a esos
Definición 2: n tipo de dato consta de dos partes: un conjunto de datos y las operacioU
nes que se pueden realizar sobre esos datos.
Algoritmos y estructuras de datos En los lenguajes de programación hay disponible un gran número de tipos de datos. Entre ellos se
pueden destacar los tipos primitivos de datos, los tipos compuestos y los tipos agregados.
1.1.1. Tipos primitivos de datos
Los tipos de datos más simples son los tipos de datos primitivos, también denominados datos
atómicos porque no se construyen a partir de otros tipos y son entidades únicas no descomponibles en otros.
Un tipo de dato atómico es un conjunto de datos atómicos con propiedades idénticas. Estas
propiedades diferencian un tipo de dato atómico de otro. Los tipos de datos atómicos se definen
por un conjunto de valores y un conjunto de operaciones que actúan sobre esos valores.
Tipo de dato atómico
1.	Un conjunto de valores.
2.	Un conjunto de operaciones sobre esos valores.
Diferentes tipos de datos atómicos
valores	operaciones	-∞ , …, -3, -2, -1, 0, 1, 2, 3, …, +∞
*, +, -, /, %, ++, --, …
valores	operaciones	- , …, 0.0, …,
*, +, -, %, /, …
valores	operaciones	0, …, 'A', 'B', …, 'a', 'b', …
valores	operaciones	verdadero, falso
and, or, not, …
Los tipos numéricos son, probablemente, los tipos primitivos más fáciles de entender, debido a
que las personas están familiarizadas con los números. Sin embargo, los números pueden también ser
difíciles de comprender por los diferentes métodos en que son representados en las computadoras.
Por ejemplo, los números decimales y binarios tienen representaciones diferentes en las máquinas.
Debido a que el número de bits que representa los números es finito, sólo los subconjuntos de enteros
y reales se pueden representar. A consecuencia de ello, se pueden presentar situaciones de desbordamiento (underflow y overflow ) positivo y negativo al realizar operaciones aritméticas. Normalmente,
los rangos numéricos y la precisión varía de una máquina a otra. Para eliminar estas inconsistencias,
algunos lenguajes modernos, como Java y C#, tienen especificaciones precisas para el número de bits,
el rango y la precisión numérica de cada operación para cada tipo numérico.
0	23	786	456	999
7.56	4.34	0.897	1.23456	99.999
El tipo de dato boolean (lógico) suele considerarse como el más simple debido a que sólo
tiene dos valores posibles: verdadero (true) y falso (false). El formato sintáctico de estas
constantes lógicas puede variar de un lenguaje de programación a otro. Algunos lenguajes ofrecen
un conjunto rico de operaciones lógicas. Por ejemplo, algunos lenguajes tienen construcciones
que permiten a los programadores especificar operaciones condicionales o en cortocircuito. Por
ejemplo, en Java, en los operadores lógicos y || sólo se evalúa el segundo operando si su valor
se necesita para determinar el valor de la expresión global.
El tipo carácter consta del conjunto de caracteres disponible para un lenguaje específico en
una computadora específica. En algunos lenguajes de programación, un carácter es un símbolo
indivisible, mientras que una cadena es una secuencia de cero o más caracteres. Las cadenas se
pueden manipular de muchas formas, pero los caracteres implican pocas manipulaciones. Los
tipos carácter, normalmente, son dependientes de la máquina.
'Q'	'a'	'8'	'9'	'k'
Los códigos de carácter más utilizados son EBCDIC (utilizado por las primeras máquinas de
IBM) y ASCII (el código universal más extendido). La aparición del lenguaje Java trajo consigo
la representación de caracteres en Unicode, un conjunto internacional de caracteres que unifica
a muchos conjuntos de caracteres, incluyendo inglés, español, italiano, griego, alemán, latín,
hebreo o indio. En Java, el tipo char se representa como un valor de 16 bits. Por consiguiente, el
rango de char está entre 0 y 65.536, lo que permite representar prácticamente la totalidad de los
alfabetos y formatos numéricos y de puntuación universales.
1.1.2. Tipos de datos compuestos y agregados
Los datos compuestos son el tipo opuesto a los tipos de datos atómicos. Los datos compuestos
se pueden romper en subcampos que tengan significado. Un ejemplo sencillo es el número de su
teléfono celular 51199110101. Realmente, este número consta de varios campos, el código del
país (51, Perú), el código del área (1, Lima) y el número propiamente dicho, que corresponde a
un celular porque empieza con 9.
En algunas ocasiones los datos compuestos se conocen también como datos o tipos agregados. Los tipos agregados son tipos de datos cuyos valores constan de colecciones de elementos
de datos. Un tipo agregado se compone de tipos de datos previamente definitivos. Existen tres
tipos agregados básicos: arrays (arreglos), secuencias y registros.
Un array o arreglo es, normalmente, una colección de datos de tamaño o longitud fija, cada
uno de cuyos datos es accesible en tiempo de ejecución mediante la evaluación de las expresiones
que representan a los subíndices o índices correspondientes. Todos los elementos de un array
deben ser del mismo tipo.
array de enteros:
[4, 6, 8, 35, 46, 0810]
Una secuencia o cadena es, en esencia, un array cuyo tamaño puede variar en tiempo de
ejecución. Por consiguiente, las secuencias son similares a arrays dinámicos o flexibles.
= Aceite picual de Carchelejo
El término inglés array se traduce en casi toda Latinoamérica por arreglo, mientras que en España
se ha optado por utilizar el término en inglés o bien su traducción por “lista” , “tabla” o “matriz”.
Algoritmos y estructuras de datos Un registro puede contener elementos datos agregados y primitivos. Cada elemento agregado, eventualmente, se descompone en campos formados por elementos primitivos. Un registro
se puede considerar como un tipo o colección de datos de tamaño fijo. Al contrario que en los
arrays, en los que todos sus elementos deben ser del mismo tipo de datos, los campos de los registros pueden ser de diferentes tipos de datos. A los campos de los registros se accede mediante
El registro es el tipo de dato más próximo a la idea de objeto. En realidad, el concepto de
objeto en un desarrollo orientado a objetos es una generalización del tipo registro.
Registro	{
1.2. LA NECESIDAD DE LAS ESTRUCTURAS DE DATOS
A pesar de la gran potencia de las computadoras actuales, la eficiencia de los programas sigue
siendo una de las características más importantes a considerar. Los problemas complejos que
procesan las computadoras cada vez más obligan, sobre todo, a pensar en su eficiencia dado el
elevado tamaño que suelen alcanzar. Hoy, más que nunca, los profesionales deben formarse en
técnicas de construcción de programas eficientes.
En sentido general, una estructura de datos es cualquier representación de datos y sus operaciones asociadas. Bajo esta óptica, cualquier representación de datos, incluso un número entero o
un número de coma flotante almacenado en la computadora, es una sencilla estructura de datos.
En un sentido más específico, una estructura de datos es una organización o estructuración de
una colección de elementos dato. Así, una lista ordenada de enteros almacenados en un array es
un ejemplo de dicha estructuración.
Una estructura de datos es una agregación de tipos de datos compuestos y atómicos
en un conjunto con relaciones bien definidas. Una estructura significa un conjunto de
reglas que contienen los datos juntos.
Las estructuras de datos pueden estar anidadas: se puede tener una estructura de datos que
conste de otras.
1.	Una combinación de elementos en la que cada uno es o bien un tipo de dato u otra
2.	conjuntos de asociaciones o relaciones (estructura) que implica a los elementos
La Tabla 1.1 recoge las definiciones de dos estructuras de datos clásicas: arrays y registros.
Tabla 1.1 Ejemplos de estructura de datos
Secuencias homogéneas de datos o tipos
de datos conocidos como elementos.
Combinación de datos heterogéneos en una
estructura única con una clave identificada.
Asociación de posición entre los elementos.
Ninguna asociación entre los elementos.
La mayoría de los lenguajes de programación soporta diferentes estructuras de datos. Además,
esos mismos lenguajes suelen permitir a los programadores crear sus propias nuevas estructuras
de datos con el objetivo fundamental de resolver del modo más eficiente posible una aplicación.
Será necesario que la elección de una estructura de datos adecuada requiera también la posibilidad de poder realizar operaciones sobre dichas estructuras. La elección de la estructura
de datos adecuada redundará en una mayor eficiencia del programa y, sobre todo, en una mejor
resolución del problema en cuestión. Una elección inadecuada de la estructura de datos puede
conducir a programas lentos, largos y poco eficientes.
Una solución se denomina eficiente si resuelve el problema dentro de las restricciones de recursos requeridas. Restricciones de recursos pueden ser el espacio total disponible para almacenar los datos (considerando la memoria principal independiente de las restricciones de espacio de
discos, fijos, CD, DVD, flash…) o el tiempo permitido para ejecutar cada subtarea. Se suele decir
que una solución es eficiente cuando requiere menos recursos que las alternativas conocidas.
El costo de una solución es la cantidad de recursos que la solución consume. Normalmente,
el coste se mide en término de recursos clave, especialmente el tiempo.
1.2.1. Etapas en la selección de una estructura de datos
Los pasos a seguir para seleccionar una estructura de datos que resuelva un problema son
[SHAFFER 97]:
1.	Analizar el problema para determinar las restricciones de recursos que debe cumplir cada
2.	Determinar las operaciones básicas que se deben soportar y cuantificar las restricciones
de recursos para cada una. Ejemplos de operaciones básicas son la inserción de un dato en
la estructura de datos, suprimir un dato de la estructura o encontrar un dato determinado
en dicha estructura.
3.	Seleccionar la estructura de datos que cumple mejor los requisitos o requerimientos.
Este método de tres etapas para la selección de una estructura de datos es una aproximación
centrada en los datos. Primero se diseñan los datos y las operaciones que se realizan sobre ellos,
a continuación viene la representación de esos datos y, por último, viene la implementación de
Las restricciones de recursos sobre ciertas operaciones clave, como búsqueda, inserción de
registros de datos y eliminación de registros de datos, normalmente conducen el proceso de
selección de las estructuras de datos.
Algoritmos y estructuras de datos Algunas consideraciones importantes para la elección de la estructura de datos adecuada son:
•	¿Todos los datos se insertan en la estructura de datos al principio o se entremezclan con
•	¿Se pueden eliminar los datos?
•	¿Los datos se procesan en un orden bien definido o se permite el acceso aleatorio?
Un tipo es una colección de valores. Por ejemplo, el tipo boolean consta de los valores
true y false. Los enteros también forman un tipo.
Un tipo de dato es un tipo con una colección de operaciones que manipulan el tipo.
Por ejemplo, una variable entera es un miembro del tipo de dato entero. La suma es un
ejemplo de una operación sobre tipos de datos enteros.
Un elemento dato es una pieza de información o un registro cuyos valores se especifican
a partir de un tipo. Un elemento dato se considera que es un miembro de un tipo de dato.
El entero es un elemento de datos simple ya que no contiene subpartes.
Un registro de una cuenta corriente de un banco puede contener varios campos o piezas
de información como nombre, número de la cuenta, saldo y dirección. Dicho registro es
un dato agregado.
1.3. ALGORITMOS Y PROGRAMAS
Un algoritmo es un método, un proceso, un conjunto de instrucciones utilizadas para resolver un
problema específico. Un problema puede ser resuelto mediante muchos algoritmos. Un algoritmo
dado correcto, resuelve un problema definido y determinado (por ejemplo, calcula una función
determinada). En este libro se explican muchos algoritmos y, para algunos problemas, se proponen diferentes algoritmos, como es el caso del problema típico de ordenación de listas.
La ventaja de conocer varias soluciones a un problema es que las diferentes soluciones pueden
ser más eficientes para variaciones específicas del problema o para diferentes entradas del mismo problema. Por ejemplo, un algoritmo de ordenación puede ser el mejor para ordenar conjuntos
pequeños de números, otro puede ser el mejor para ordenar conjuntos grandes de números y un
tercero puede ser el mejor para ordenar cadenas de caracteres de longitud variable.
Desde un punto de vista más formal y riguroso, un algoritmo es “un conjunto ordenado de pasos
o instrucciones ejecutables y no ambiguas”. Obsérvese en la definición que las etapas o pasos que
sigue el algoritmo deben tener una estructura bien establecida en términos del orden en que se ejecutan las etapas. Esto no significa que las etapas se deban ejecutar en secuencia: una primera etapa,
después una segunda, etc. Algunos algoritmos, conocidos como algoritmos paralelos, por ejemplo,
contienen más de una secuencia de etapas, cada una diseñada para ser ejecutada por procesadores
diferentes en una máquina multiprocesador. En tales casos, los algoritmos globales no poseen un
único hilo conductor de etapas que conforman el escenario de primera etapa, segunda etapa, etc.
En su lugar, la estructura del algoritmo es el de múltiples hilos conductores que se bifurcan y se reconectan a medida que los diferentes procesadores ejecutan las diferentes partes de la tarea global.
Durante el diseño de un algoritmo, los detalles de un lenguaje de programación específico se
pueden obviar frente a la simplicidad de una solución. Generalmente, el diseño se escribe en español
(o en inglés, o en otro idioma hablado). También se utiliza un tipo de lenguaje mixto entre el español
y un lenguaje de programación universal que se conoce como pseudocódigo (o seudocódigo).
1.3.1. Propiedades de los algoritmos
Un algoritmo debe cumplir diferentes propiedades :
1.	Especificación precisa de la entrada. La forma más común del algoritmo es una transformación que toma un conjunto de valores de entrada y ejecuta algunas manipulaciones
para producir un conjunto de valores de salida. Un algoritmo debe dejar claros el número y tipo de valores de entrada y las condiciones iniciales que deben cumplir esos valores de
entrada para conseguir que las operaciones tengan éxito.
2.	Especificación precisa de cada instrucción. Cada etapa de un algoritmo debe ser definida
con precisión. Esto significa que no puede haber ambigüedad sobre las acciones que se
deban ejecutar en cada momento.
3.	Exactitud, corrección. Un algoritmo debe ser exacto, correcto. Se debe poder demostrar
que el algoritmo resuelve el problema. Con frecuencia, esto se plasma en el formato de un
argumento, lógico o matemático, al efecto de que si las condiciones de entrada se cumplen
y se ejecutan los pasos del algoritmo, entonces se producirá la salida deseada. En otras
palabras, se debe calcular la función deseada y convertir cada entrada a la salida correcta.
Un algoritmo se espera que resuelva un problema.
4.	Etapas bien definidas y concretas. Un algoritmo se compone de una serie de etapas concretas, lo que significa que la acción descrita por esa etapa está totalmente comprendida
por la persona o máquina que debe ejecutar el algoritmo. Cada etapa debe ser ejecutable
en una cantidad finita de tiempo. Por consiguiente, el algoritmo nos proporciona una
“receta” para resolver el problema en etapas y tiempos concretos.
5.	Número finito de pasos. Un algoritmo se debe componer de un número finito de pasos. Si la
descripción del algoritmo consta de un número infinito de etapas, nunca se podrá implementar como un programa de computador. La mayoría de los lenguajes que describen algoritmos
(español, inglés o pseudocógio) proporciona un método para ejecutar acciones repetidas,
conocidas como iteraciones, que controlan las salidas de bucles o secuencias repetitivas.
6.	Un algoritmo debe terminar. En otras palabras, no puede entrar en un bucle infinito.
7.	Descripción del resultado o efecto. Por último, debe estar claro cuál es la tarea que el
algoritmo debe ejecutar. La mayoría de las veces, esta condición se expresa con la producción de un valor como resultado que tenga ciertas propiedades. Con menor frecuencia, los
algoritmos se ejecutan para un efecto lateral, como imprimir un valor en un dispositivo
de salida. En cualquier caso, la salida esperada debe estar especificada completamente.
¿Es un algoritmo la instrucción siguiente?
Escribir una lista de todos los enteros positivos
Es imposible ejecutar la instrucción anterior dado que hay infinitos enteros positivos. Por consiguiente, cualquier conjunto de instrucciones que implique esta instrucción no es un algoritmo.
En [BUDD 1998], [JOYANES 2003], [BROOKSHEAR 2003] y [TREMBLAY 2003], además de en
las referencias incluidas al final del libro en la bibliografía, puede encontrar información ampliada sobre
teoría y práctica de algoritmos.
programar en java 7ed(code 1232342334) , libro similar al 9 edicion
5. la cara oculta de c++ builder Jose Alberto Noh Noh
P4tr0n3s de d1s3ñ0 1ra 3dic10n er1ch g4mm4
(code 12412) Introduccion a la programacion con java 1edi dean
S1st3m4s operativos (7ed_2005)_galvin_silberschatz_gagne
Matemáticas discretas (code 12312y)
Diseno de algoritmos y su codificacion en lenguaje c
Swokowski earl algebra y trigonometria con geometria(code 1132t)
R3d3s de c0mput4d0r4s 5ta 3d .kur0s3 , j y r0ss
Int3l1g3nc1a 4rtific14l. un 3nf0qu3 m0d3rn0, 2da 3d1ci0n stu4rt russ3l y p3t3……
1ng3n13r1a de s0ftw4r3 p4r4 4pl1c4c10n3s de 1nt3rn3t Debate Utpl
S0ftw4r3 3ng1neer1ng for 1nt3rn3t 4pplic4t10ns
R3d3s d3 c0mput4d0r4s-5ed1c10n
E2tad1st1c4 Apl1c4d4 a l0s n3g0c10s y Ec0n0mi4 15va edicion
246469719 antr0p0l0gia
S1stem4s op3r4tiv0s (7ed_2005)_g4lvin_s1lb3rsch4tz_g4gne
Gu14 ing3n1er1a de r3quisitos 2014 2014
1ng3n13r14 de s0ftwar3 pr3ssman 7 ed

References: resolución 
 Resolución 
 resolución 
 resolución 
 resolución 

resolución