Fulbia Torres - Estructuras de Datos en C/C++

ESTRUCTURAS DE DATOS EN C/C++ EJERCITACIÓN Y PROBLEMAS RESUELTOS Smashwords 2019 Título de la obra: ESTRUCTURAS DE DATOS. Ejercitación y problemas resueltos Nombre del autor: FULBIA TORRES DE DELGADO © 2018 Fulbia Torres De Delgado Todos los derechos reservados. Fulbia Torres De Delgado fulbiato@gmail.com ISBN: Agradecimientos A nuestro padre Dios, Rey Celestial y Omnipotente, fuente de paz, fortaleza y alegría. De manera especial a la Dra.

Luisa Maibá Rodríguez, que con sus conocimientos, dedicando tiempo y esfuerzo, me orientó en la realización de este trabajo. A los estudiantes que han contribuido a mi actividad académica en la Universidad. Dedicatoria A mi esposo Manuel y a mis hijas Romina y Pierina mis grandes amores. A mí amada nieta Paulina con amor. A la memoria de tío Darío y tío Euclides amigos incondicionales. A Josefa y Pedro, mis amados padres, con amor.

A la memoria de GUARDIAN mi más fiel amigo. Prólogo Las estructuras de datos constituyen una de las principales áreas de estudio dentro del campo de la computación y éste incluye saber la forma en que se organiza la información, es decir el almacenamiento, manejo y recuperación de la misma. La eficiencia en el manejo de la información depende en gran medida de las estructuras diseñadas y de los métodos de manipulación que se implanten sobre ellas. El libro que a continuación se presenta está dirigido a estudiantes de ingeniería informática, computación, sistemas y carreras a fines, donde en su pensum de estudio contemplen la asignatura Estructuras de Datos como obligatoria o electiva. El objetivo del libro es servir como un texto de ejercitación en el cual se plantean una serie de ejercicios resueltos de estructuras de datos, tanto a nivel de diseño como a nivel de implementación, esto permite al estudiante ver la aplicación en problemas reales y practicar para obtener destrezas y desarrollar cualquier ejercicio planteado. También incluye una serie de ejercicios propuestos para que sean analizados y desarrollados por los estudiantes.

El lenguaje escogido para la implementación de los ejercicios es C++, dada su enorme difusión en el medio informático, su eficiencia, su estandarización. Cada ejercicio tiene una parte de análisis del problema planteado, la solución, una corrida grafica y la implementación(código fuente), esto permite al estudiante ver en el lenguaje de programación escogido cada uno de los ejercicios planteados, lo mismo que reutilizar el software para el desarrollo de sus propios proyectos. El libro está dividido en capítulos que corresponden a diferentes estructuras de datos. El capítulo I está dedicado a la estructura de datos PILA, restringido en almacenamiento secuencial. Contempla catorce (14) ejercicios resueltos y diez (10) propuestos. El capítulo II está dedicado a la RECURSIÓN, la cual es una técnica de programación muy potente que se utiliza en estructuras de datos.

Contempla quince (15) ejercicios resueltos y siete (7) propuestos. El capítulo III está dedicado a la estructura de datos COLA, restringido en almacenamiento secuencial. Contempla quince (15) ejercicios resueltos y siete (7) propuestos. El capítulo IV está dedicado a la estructura de datos LISTA, trabajadas en forma dinámica. Contempla quince (15) ejercicios resueltos y diez (10) propuestos. El capitulo V está dedicado a la estructura de datos ARBOL BINARIO DE BÚSQUEDA, trabajadas en forma dinámica.

Contempla quince (15) ejercicios resueltos y ocho (8) propuestos. Este libro es el producto de mi actividad docente, como profesora de la cátedra Estructuras de Datos, asignatura obligatoria de la carrera de Ingeniería Electrónica opción Computación, dictada en el Departamento de Ingeniería Electrónica, de la Universidad Nacional Experimental Politécnica “Antonio José de Sucre” UNEXPO, Barquisimeto Estado Lara Venezuela. Es importante resaltar que se ha enriquecido con aportes de estudiantes de dicha asignatura. Las estructuras de datos constituyen una de las principales áreas de estudio dentro del campo de la computación y éste incluye saber la forma en que se organiza la información, es decir el almacenamiento, manejo y recuperación de la misma. La eficiencia en el manejo de la información depende en gran medida de las estructuras diseñadas y de los métodos de manipulación que se implanten sobre ellas. El texto de ejercitación presentado a continuación es una selección de problemas resueltos y propuestos para la asignatura Estructuras de Datos que abarca los siguientes tópicos: pilas, recursividad, colas, listas (listas lineales simplemente enlazadas) y árboles binarios de búsqueda.

Cada capítulo del texto de ejercitación se ha estructurado en custro secciones:

• Una sección inicial de teoría en la cual se define la estructura a utilizar, la definición de las operaciones básicas que se realizan sobre la estructura y la implementación de las mismas.
• Una sección de ejercicios resueltos donde se hace un análisis del enunciado y luego se plasma una solución al problema en un lenguaje de programación de alto nivel ( C++)
• Una sección de ejercicios dejados planteados para el estudiante.
• Una sección donde aparece el código fuente de cada uno de los ejercicios desarrollados en el capitulo.

Esto es importante, ya que permite al estudiante comprender las estructuras de datos y adquirir habilidades y destrezas en el dominio de implementación de las mismas. Indice Definición Tad Pila Operaciones: Constructoras Modificadoras Analizadoras Destructora Implementación Estática De Pilas (Utilizando Struct) Ejercicios Resueltos Implementación Estática De Pilas Utilizando Clases Ejercicios Propuestos Codigo Fuente Ejercicios Resueltos Definición Ejercicios Resueltos Ejercicios Propuestos Codigo Fuente Ejercicios Resueltos Definición Tad Cola Operaciones: Constructora Modificadoras Analizadoras Destructora Implementación Estática De Colas Implementación Circular Ejercicios Resueltos Implementación Estática De Colas Utilizando Clases Ejercicios Propuestos Codigo Fuente Ejercicios Resueltos Definición Tad Listas Operaciones Constructora Modificadoras Analizadoras Destructora Implementación Dinámica De Lista Utilizando Struct Ejercicios Resueltos Implementación Dinamica De Lista. Utilizando Clases Ejercicios Propuestos Codigo Fuente Ejercicios Resueltos Definición Tad Abb Operaciones: Constructora Modificadoras Analizadoras Destructora Implementación Dinámica Del Árbol Binario De Búsqueda Utilizando Struct Ejercicios Resueltos Ejercicios Propuestos Codigo Fuente Ejercicios Resueltos Pilas DEFINICIÓN UnaPILAes una estructura ordenada y homogénea, en la que podemos añadir o quitar elementos en un extremo llamadoTOPEsiguiendo una políticaLIFO(Last In, First Out). Se dice que es una estructura ordenada, porque sus elementos se sitúan siguiendo un cierto orden, no que estén ordenados en función de su valor.

Se dice que se trata de una estructura homogénea, porque todos sus elementos son del mismo tipo, pueden ser tanto simples (enteros, reales,…) como compuestos (registros, vectores,.....). TAD PILA Veamos cual es la especificación formal del tipo de datos abstracto pila: TAD: pila Operaciones: CONSTRUCTORAS Crea una pila vacía. CrearPila: -----  Pila MODIFICADORAS Dada una pila p y un valor e, del tipo base, modifica la pila al apilar en p el nuevo elemento sobre la posición indicada por el valor del tope. AdicPila: Pila x tipo_base -----  Pila Dada una pila p, elimina el elemento indicado por el valor del tope y modifica la pila. ElimPila: Pila -----  Pila ANALIZADORAS Devuelve el valor del elemento que está apuntado por el tope. InfoPila: Pila -----  tipo_base Devuelve verdadero si la pila está vacía y falso en caso contrario.

PilaVacia: Pila -----  lógico Devuelve verdadero si la pila está llena y falso en caso contrario. PilaLlena: Pila -----  lógico DESTRUCTORA Destruye la pila retornando toda la memoria ocupada. No Aplica IMPLEMENTACIÓN ESTÁTICA DE PILAS (Utilizando struct) Definición # define MAXELEM número máximo de elementos struct tipopila { int tope; tipo_base elementos [MAXELEM]; } struct tipopila p; Con esta definición de Pila las operaciones asociadas especificadas en el TAD quedarían del siguiente modo: Crea una pila vacía int CrearPila (struct tipopila *p) { return (*p).tope = -1; } Dada una pila p y un valor del tipo base, modifica la pila al apilar en p el nuevo elemento sobre la posición indicada por el valor del tope. void AdicPila (struct tipopila *p, tipo_base valor) { if PilaLlena (p) { cout << "Pila Overflow" << endl; exit (1); } else (*p).elementos[++ ((*p).tope)] = valor; } Dada una pila p, elimina el elemento indicado por el valor del tope, la pila se modifica. tipo_base ElimPila (struct tipopila *p) { if PilaVacia (p) { cout << "Pila Underflow" << endl; exit (1); } return ((*p).elementos[((*p).tope)--]); } Devuelve el valor del elemento que está apuntado por el tope. int PilaVacia (struct tipopila *p) { if ( (*p).tope == -1) return (1); else return (0); } Devuelve verdadero si la pila está llena y falso en caso contrario. int PilaLlena (struct tipopila *p) { if ( (*p).tope == MAXELEM-1) return (1); else return (0); } EJERCICIOS RESUELTOS Los ejercicios que a continuación se presentan están codificados en el lenguaje de alto nivel C++ utilizando struct. 1. 1.