Estructuras de Datos en C/C++

Por Fulbia Torres

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.

• Idioma: Español
• Editorial: Fulbia Torres
• Fecha de lanzamiento: 14 dic 2019
• ISBN: 9780463174098

Fulbia Torres

Fulbia Josefina Torres de Delgado (1964) nació en Valera, estado Trujillo, Venezuela. Estudio en el Colegio María Rafols la básica y en el liceo Rafael Rangel el diversificado, en Valera. Se graduó de Ingeniero en Informática en la UCLA, Barquisimeto, estado Lara, Venezuela. Se graduó de Magister en Sistemas de Información en la UCLA, Barquisimeto, estado Lara, Venezuela. Cursa estudios de Doctorado en Ciencias de la Ingeniería: mención Productividad en la UNEXPO, Barquisimeto, estado Lara, Venezuela, por terminar.Trabajó como analista de PDE I (1991-1992), en la ULA, estado Mérida. En la Universidad Fermín Toro (1992-1995)(2000-2002) Docente Instructor. En la Universidad Yacambú (1994-1995) Docente Instructor, desde el año 1995 trabajo en la UNEXPO como Docente Agregado a dedicación exclusiva. Hoy jubilada. www.el.bqto.unexpo.edu.ve >ftorres.Trabajos de investigación realizados: Modelo Integral de Información de la Dirección de Investigación y Postgrado de la UNEXPO. Noviembre, 1999. Sistema de Información Presupuestario para la unidad de Contabilidad. ULA. 1991. Diseño Asistido por Computador de Libros Electrónicos en Computación. Noviembre 2001. Texto de Ejercitación de Problemas de Estructuras de Datos. Octubre 2006.Publicaciones: Estudios Comparativos de Datos Nítidos y Difusos en Estructuras de Datos. Publicado en Redip. UNEXPO. VRB. Venezuela (2011) y en el portal de Difusión de la Producción Científica Hispana revista Dialnet.

Vista previa del libro

Pilas

DEFINICIÓN

Una PILA es una estructura ordenada y homogénea, en la que podemos añadir o quitar elementos en un extremo llamado TOPE siguiendo una política LIFO (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.

tipo_base InfoPila (struct tipopila *p)

{

if PilaVacia (p) { cout << Pila Underflow << endl;

exit (1); }

else return ((*p).elementos[(*p).tope]);

}

Devuelve verdadero si la pila está vacía y falso en caso contrario.

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. Implementar una función que calcule y retorne la suma de los elementos enteros de una pila.

Análisis:

Entradas: pila con elementos enteros.

Salidas: suma de los elementos.

Una implementación para esta función puede ser:

int SumaPila(struct tipopila *p)

{ declaración de variables a utilizar

int elem=0;

int suma=0;

// Ciclo donde se saca el elemento elem

// de la pila para sumarlo el resultado se guarda en la variable suma

while (!PilaVacia(p))

{ elem=ElimPila(p);

suma=suma+elem;

}

// Retorna el contenido de la variable suma

return suma;

}

Otra implementación para esta función puede ser:

int sumapila (struct tipopila *p)

{ int suma=0;

While (! PilaVacia(p))

suma = suma + ElimPila(p);

return (suma);

}

Corrida en frío:

suma=0

elem= 0 inicialmente la pila es:

2. Implementar una función que verifique que si dos pilas son iguales, sin destruir su contenido.

Análisis:

Entradas: pila1, pila2.

Salidas: valor booleano si son iguales o no.

Una implementación para esta función puede ser:

void PilasIguales( struct tipopila *p1, struct tipopila *p2)

{

int diferente=0;

while ((!PilaVacia(p1)) && (!diferente))

//Verifica si los elementos en el tope de la pila son diferentes

{ if (InfoPila (p1) != InfoPila (p2))

{ cout << Las pilas son diferentes;

diferente = 1; }

//Si los elementos son iguales los quita de la pila

ElimPila (p1);

ElimPila (p2);

}

// Si la pila llega a vacío, verificado todos sus elementos retorna 1

// indicando que las pilas son iguales

if (diferente == 0)

cout << Las pilas son iguales;

}

Corrida en frío: Primera corrida

primera iteración ( while ) segunda iteración (while)

inicialmente la pila es:

tercera iteración (while) cuarta iteración (while)

Salida: Las pilas son iguales.

Segunda corrida.

Primera iteración (while) segunda iteración

Salida; Las pilas son diferentes.

3. Implementar una función que cuente las ocurrencias del elemento elem en la pila

Análisis:

Entradas: pila, elem.

Salidas: número de ocurrencias del elemento elem.

Una implementación para esta función puede ser:

int CuentaOcurren(struct tipopila *p, int elem)

{

// variable cuenta almacena el número de ocurrencias del elemento

// elem en la pila

int cuenta=0;

while (!PilaVacia(p))

// verifica si el elemento que está en el tope de la pila es igual al

// elemento elem

if (InfoPila(p)==elem)

//va contando el número de ocurrencias de elem en la pila

{ cuenta+=1;

// y saca los elementos de la pila

ElimPila(p); }

else ElimPila(p);

return cuenta;

}

Corrida en frío:

primera iteración (while) segunda iteración (while)

cuenta = 0; elem = 6; cuenta = 0+1=1; cuenta = 1; elem = 6;

tercera iteración (while) cuarta iteración (while)

cuenta = 1; elem = 6; cuenta = 1+1=2; cuenta =2

Salida: cuenta = 2

4. Implementar una función reemplazar que tenga como argumentos una pila de elementos enteros y dos valores enteros nuevo y antiguo de forma que si el segundo valor aparece en algún lugar de la pila sea reemplazado por el nuevo.

Análisis:

Entradas: pila de enteros, valore enteros nuevo, antiguo.

Salidas: pila con el elemento nuevo ya reemplazado.

Una implementación para esta función puede ser:

struct tipopila Reemplazar (struct tipopila *p, int nuevo, int viejo)

{

struct tipopila q;

struct tipopila r;

int aux;;

CrearPila(&q);

CrearPila(&r);

// se van sacando elementos de p y los vamos metiendo en q

// excepto en el caso de sacar viejo, que insertamos nuevo

while (!PilaVacia(p))

{

aux=ElimPila(p);

if (aux == viejo)

AdicPila (&q,nuevo);

else AdicPila (&q,aux);

}

// ya tenemos en q el resultado pero al contrario

// por tanto sólo resta volcarla en r.

while (!PilaVacia(&q))

{

aux=ElimPila(&q);

AdicPila (&r,aux);

}

return r;

}

Corrida en frío:

Inicialmente la pila es: primera iteración (while)

nuevo = 1; viejo = 3; aux = 8;

segunda iteración (while) tercera iteración (while)

nuevo = 1; viejo = 3; aux = 5; nuevo = 1; viejo = 3; aux= 3

cuarta iteración (while) corrida siguiente (while)

nuevo = 1; viejo= 3; aux= 2 después de varias iteraciones la pila r queda

5. Implementar una función para insertar un elemento entero en una pila ordenada ascendentemente.

Análisis:

Entradas: pila con elementos enteros ordenada.

Salidas: pila con el elemento entero nuevo ordenada.

Una implementación para esta función puede ser:

struct tipopila PilaOrdenada( struct tipopila *pila, int valor)

{

struct tipopila paux;

int encontrado=1;

int elem;

CrearPila(&paux);

// se van sacando elementos de la pila y se verifica si es mayor que valor

while ( encontrado )

{

elem=ElimPila(pila);

// si elem es mayor al valor entrante, elem se mete en la pila auxiliar

if ( elem > valor )

AdicPila (&paux,elem);

else {encontrado=0;

// se agrega elem a la pila original, se agrega el valor entrante

// a la pila original quedando en orden

AdicPila (pila,elem);

AdicPila (pila,valor); }

}

// Ciclo externo para regresar los elementos de la pila auxiliar a la pila original

while ( !PilaVacia(&paux) )

{ elem=ElimPila(&paux);

AdicPila (pila,elem); }

return (*pila);

}

Corrida en frío:

primera iteración ( while )

encontrado=1

valor = 4 inicialmente la pila es:

segunda iteración ( while )

encontrado=1

valor = 4: elem = 6 6>4

tercera iteración ( while )

encontrado=0

valor = 4 elem = 2 2>4

Corrida ciclo externo: elem=6 elem=8

6. Implementar una función mezcla (p.q) que genere la pila resultante de ir apilando alternativamente los elementos de p y q desde sus respectivos fondos hacia las cimas.

Análisis:

Entradas: pilas p y q con elementos enteros.

Salidas: pila con la mezcla de las dos pilas de entrada.

Una implementación para esta función puede ser:

struct tipopila Mezcla(struct tipopila *p, struct tipopila *q)

{

struct tipopila r;

struct tipopila paux;

int valorp;

int valorq;

int valor;

CrearPila(&r);

CrearPila(&paux);

// se van sacando elementos de p y q y se van metiendo

// alternativamente en la pila auxiliar paux

while (!PilaVacia(p))

{

valorp=ElimPila(p);

valorq=ElimPila(q);

AdicPila(&paux,valorq);

AdicPila(&paux,valorp);

}

// se pasan los elementos de la pila auxiliar a la pila resultante r

while(!PilaVacia(&paux))

{

valor=ElimPila(&paux);

AdicPila(&r,valor);

}

// se retorna la pila resultante r

return r;

}

Corrida en frío:

Inicialmente las pilas p y q son: primera iteración ( primer while )

valor = 6 valor = 5

segunda iteración ( primer while) Segundo ciclo (while)

valor = 4 valor = 3 valor = 1

tercera iteración primer while)

valor = 2 valor = 1 valor = 2

Y así sucesivamente hasta completar la pila m la cual se imprime en el siguiente ciclo.

7. Implementar una función que multiplique los elementos de las pilas p y q y los resultados apilarlos en una tercera pila r. Imprimir las pilas originales y la pila resultante.

Análisis:

Entradas: pilas p y q con elementos enteros.

Salidas: pila r con el resultado de multiplicar los elementos de las dos pilas.

Una implementación para esta función puede ser:

struct tipopila Multiplicar (struct tipopila *p, struct tipopila *q)

{

tipopila r, paux;

int valor, valorp, valorq;

CrearPila(&r);

CrearPila(&paux);

// se van sacando elementos de p y q y se van multiplicando

// el resultado se va guardando en la pila auxiliar paux

while (!PilaVacia(p))

{ valorp=ElimPila (p);

valorq=ElimPila (q);

AdicPila(&paux,valorp * valorq);

}

// se pasan los elementos de la pila auxiliar a la pila resultante r

while (!PilaVacia(&paux))

{ valor=ElimPila (&paux);

AdicPila(&r,valor); }

return r;

}

Corrida en frío:

Inicialmente las pilas p y q son: primera iteración ( primer while )

valorp = 3 valorq = 4

segunda iteración (primer while) segundo ciclo (while)

valorp = 8 valorq = 6 primera iteración. valor=45

segunda iteración (primer while) segunda iteración. valor=48

valorp = 5 valorq = 9

8. Implementar una función que dada una pila y un valor umbral, crea otras dos pilas, en una de las cuales se han introducido los valores menores que el umbral, y en la otra los valores mayores o iguales que el umbral. La pila inicial no desaparece.

Análisis:

Entradas: pilas p con elementos enteros.

Salidas: pila1 con los valores menores que el umbral y pila2 con los valores mayores e iguales al umbral.

Una implementación para esta función puede ser:

void DividirPila (struct tipopila *p; int valorum)

{

tipopila p1, p2;

int valor;

CrearPila(&p1);

CrearPila(&p2);

// se van sacando elementos de p y se compara con el valor umbral

// si es menor se mete en la pila p1 y si es mayor o igual se meta en

// la pila p2

while (!PilaVacia(p))

{ valor=ElimPila (p);

if (valor