Estructuras de Datos con C++
César Liza Avila
PRESENTACION
Las Estructuras de Datos son un tema fundamental en la formación de los estudiantes de Ingeniería de Sistemas, Computación e Informática, y afines, pues nos dan un conocimiento técnico para elegir la mejor y más eficiente forma de organizar nuestros datos para la solución de problemas de uso común en programación.
A pesar de haberse escrito muchos libros sobre el tema, ninguno de ellos contiene la cantidad y diversidad de ejemplos debidamente explicados que trae esta obra. Los estudiantes pueden ver ejemplos concretos de programación usando las estructuras de datos, cubriendo el vacío existente entre la descripción teórica, abundante en otros libros, y las implementaciones reales. Estos ejemplos han sido codificados en el Lenguaje C/C++ pues sigue siendo el líder por excelencia y es el padre de lenguajes más recientes como Java, PHP y C#, facilitándonos su aprendizaje si más adelante decidimos programar en ellos. Sistemas Operativos, manejadores de base de datos, procesadores de texto, juegos, compiladores, calculadoras electrónicas, compresores de archivos, simuladores, utilitarios en general, etc., tienen prácticamente todo su código escrito en C/C++. Las estructuras de datos son la base de este tipo de aplicaciones y aprenderlas con C/C++ resulta ser una gran decisión.
En este libro encontrará más de 85 ejemplos completos de programas sobre recursividad, ordenamiento, búsqueda, listas enlazadas, pilas, colas y árboles. Asimismo, encontrará más de 140 ejercicios propuestos que sin duda, serán de valiosa ayuda, tanto para los estudiantes como de los docentes, y constituirán fuente inagotable para la elaboración de prácticas y exámenes.
La recursividad, es una importante técnica para resolver problemas complejos dividiéndolo en otros idénticos pero más pequeños. También incluimos ejemplos de un tipo particular de recursión, los llamados algoritmos de retroceso o backtracking, muy utilizados en aplicaciones de inteligencia artificial como en la solución de rompecabezas y juegos. Los métodos de ordenamiento, son indispensable en todo software que necesite la clasificación, localización y visualización organizada de datos. Se describen ejemplos de uso de métodos como burbuja, selección, inserción, Shell, ordenación rápida, y algunas mejoras a los mismos. Los métodos de búsqueda, permiten localizar un dato particular dentro de un gran conjunto de datos. Aquí mostramos la utilización de los métodos de búsqueda secuencial, binaria, y por interpolación. En una lista enlazada, cada elemento indica donde buscar el siguiente; los procesadores de texto, hojas de cálculo, manejadores de bases de datos, los mensajes de correo electrónico y todo tipo de software que trate de manera optimizada la memoria, utiliza listas enlazadas gestionadas con punteros. En una pila, los elementos recientemente ingresados se retiran primero. El sistema operativo utiliza las pilas en la invocación de funciones. Las pilas también sirven para eliminar la recursión, así como para implementar las opciones deshacer y rehacer muy comunes en la mayoría de software, asimismo en las calculadoras electrónicas, en compiladores e intérpretes para la evaluación y análisis de expresiones. En una cola, los elementos que ingresaron primero se retiran primero. Las colas forman parte de nuestra vida diaria y también son de uso muy común en las computadoras puesto que muchas rutinas al requerir la atención del procesador o de algún otro dispositivo, tienen que esperar un tiempo para ser atendidos. Finalmente, tratamos los árboles binarios de búsqueda (ABB) que permiten almacenar elementos ordenadamente para su rápida recuperación. Muchas aplicaciones como manejadores de bases de datos, software de inteligencia artificial utilizan esta estructura debido a su eficiencia.
En suma, todas aquellas opciones de software que usted como programador, siempre quiso implementar son puestas a su alcance y de manera sencilla en esta obra.
Le rogamos que cualquier crítica, sugerencia, o inquietud, la dirija a la siguiente dirección electrónica: creadores@hotmail.com, que gustosos la responderemos con el ánimo de mejorar cada día. Asimismo, le invitamos a visitar nuestra página web www.geocities.com/cesar_liza.
César Liza Avila.
CONTENIDO
Presentación..................................................................................11
CAPITULO 1: Recursividad……………………….…………………13
1.1 Suma de los n primeros números naturales
1.2 Obtenga el producto de dos enteros a y b
1.3 Factorial de un número
1.4 Convertir un número en base 10 a base 2
1.5 Máximo común divisor (MCD) de dos números por Euclides
1.6 Cálculo del enésimo número Fibonacci
1.7 Determine si un número es par o impar
1.8 Suma de los elementos de un arreglo
1.9 Máximo elemento de un arreglo
1.10 Clave de una cerradura de n dígitos
1.11 Prerrequisitos de un curso y prerrequisitos de prerrequisitos
1.12 La Función de Ackermman
1.13 Invierta las letras de una frase
1.14 Permutaciones que se obtienen con las letras A, B y C
1.15 Triángulo mágico de 3 círculos por lado que suman 10
1.16 La Leyenda Hindú del fin del mundo: Las Torres de Hanoi
1.17 Resolver un laberinto
1.18 La Vuelta del Caballo
CAPITULO 2: Ordenamiento……..………………………………….39
2.1 Ordenar por Burbuja (Buble Sort)
2.2 Ordenar por Selección
2.3 Ordenar por Inserción
2.4 Ordenar por Shell
2.5 Ordenar por Quick Sort
2.6 Ordenar por Burbuja Mejorado
2.7 Ordenar por Burbuja en dos direcciones
2.8 Inserción en arreglo ordenado manteniéndolo ordenado
2.9 Lea n nombres y ordénelos alfabéticamente
2.10 Lea un arreglo de estructuras y ordénelos alfabéticamente
2.11 Ordene un polinomio según el grado de sus términos
2.12 Ordene según monto de inversión
2.13 Ordenar por fecha de nacimiento
CAPITULO 3: Búsqueda……………………………………...……...67
3.1 Encuentre el menor elemento de un arreglo
3.2 Encuentre el grado de un polinomio
3.3 Búsqueda Secuencial en un arreglo
3.4 Búsqueda Lineal Recursiva en un arreglo
3.5 Lea un monomio y diga si forma parte del polinomio
3.6 Búsqueda Binaria dentro de un arreglo
3.7 Búsqueda Binaria dentro de un intervalo
3.8 Resuelva y = f (x), por partición binaria o bisección
3.9 Búsqueda Binaria por fecha de nacimiento
3.10 Búsqueda por Interpolación Lineal en un arreglo
3.11 Resuelva por Interpolación Lineal ecuación no lineal y=f(x)
CAPITULO 4: Listas Enlazadas……………………………………..93
4.1 Lista Enlazada, método nodo cabecera
4.2 Lista Enlazada, puntero al primero, inserción al inicio
4.3 Lista Enlazada, puntero al primero, inserción al final
4.4 Lista Enlazada, puntero al primero, inserta en posición dada
4.5 Lista enlazada, menú eliminar
4.6 Elimine elementos repetidos en lista enlazada
4.7 Diga si un monomio forma parte del polinomio
4.8 Invierta los elementos de una lista enlazada
4.9 Desplazamiento o rotación a la izquierda de un elemento
4.10 Junte dos listas enlazadas hacia una tercera
4.11 Ordene una lista enlazada por el Método de la Burbuja
4.12 Inserte elementos manteniendo ordenada la lista enlazada
4.13 Lea dos números gigantes y súmelos
CAPITULO 5: Pilas…………………………………………………..127
5.1. Menú para gestionar pila: apilar, desapilar, ver, destruir
5.2. Diga si un número es capicúa
5.3. Convierta un número en base 10 a una base menor que 26
5.4. Indique el movimiento a realizar en las Torres de Hanoi
5.5. Venta de n tipos de periódicos
5.6. Diga si los paréntesis están correctamente balanceados
5.7. Lea una expresión en infija y transfórmela a postfija
5.8. Lea una expresión en postfija y calcule su valor numérico
5.9. Costee los artículos de un almacén según la política LIFO
5.10. Programa para deshacer y rehacer una operación
CAPITULO 6: Colas………………………………………………….159
6.1 Menú gestiona una cola: encolar, desencolar, ver, destruir
6.2 Dividir cola en una de hombres y otra de mujeres
6.3 Personas que desean pasar un río en barca de capacidad m
6.4 Intercale los elementos de dos colas
6.5 Con una pila y una cola, diga si una palabra es palíndromo
6.6 Costee artículos de un almacén según la política FIFO
6.7 Gestione una Cola con Prioridad
6.8 Gestione una Cola Doble
6.9 Arribos Poisson, servicio exponencial, avance fijo de tiempo
6.10 Arribos Poisson, servicio exponencial, eventos discretos
CAPITULO 7: Arboles Binarios de Búsqueda………………….205
7.1 Recorrido de un ABB en preorden, enorden y postorden
7.2 Recorrido por nivel en un ABB
7.3 Búsqueda recursiva e iterativa en un ABB
7.4 Elimina elemento de un árbol binario de búsqueda (ABB)
7.5 Elimina elemento de ABB y luego una sus dos subárboles
7.6 Realice la tala de un ABB.
7.7 Realice la poda de un árbol
7.8 Genere aleatoriamente ABB, recórralo acumulando puntos
7.9 Calcule la altura de un ABB
7.10 Dado un ABB construya su árbol espejo.
7.11 Muestre las palabras que se forman en un ABB de letras
7.12 Genere un árbol binario equilibrado.