2. Estructuras de Datos en C++

Metodología

Resuelva los ejercicios y preséntelos al profesor.

Ejercicio para Resolver No. 1

Principales estructuras de datos en C y C++

Para definir una estructura de datos normalmente se crea un objeto que maneja la cabeza de la estructura y a través de los métodos miembro se realizan las funciones propias de un TAD. 

La estructura más sencilla es una pila, vamos a crear una pila que maneje valores enteros. Esta estructura puede implementarse de dos maneras, una es usando un vector otra usando nodos unidos a través de apuntadores. 

Vamos a realizar primero una pila hecha con un arreglo estático (sin apuntadores) y luego un ejemplo con apuntadores. 
 
 

Uso de Clases con Arreglos

Las clases nos pueden ayudar a mejorar el manejo de un arreglo. De la siguiente forma. 
 

prog1

#include "iostream.h"

class Vector {
 int vector[50];
public:
 Vector();
 void entrarDato (int valor, int posicion) {
  vector[posicion] = valor;
 }
 int verDato (int posicion) {
  return vector[posicion];
 }
 void mostrarVector();
};

Vector::Vector() {
 for (int i=0; i<50; i++)
  vector[i] = -1;
}

void Vector::mostrarVector() {
 for (int i=0; i<50; i++)
  cout << "vector [" << i << "] = " << vector[i] << endl;
 cout << endl;
}

main() {
 Vector mivector;
 mivector.entrarDato(345,43);
 mivector.entrarDato(23,47);
 mivector.entrarDato(5,35);
 mivector.entrarDato(8,38);
 mivector.entrarDato(10,39);
 mivector.entrarDato(23,40);
 mivector.mostrarVector();
 cout << "********************" << endl;
 cout << "Posicion 23 : " << mivector.verDato(23) << endl;
}

Se puede observar que el manejo desde el main se hace mucho más sencillo. Se crea la variable que en este caso se llama mivector y luego se usan sus métodos de entrarDato, verDato y mostrarVector, de manera muy sencilla. 

Ejercicio Resuelto A

Elabore la clase y el programa que permita probar su funcionamiento. 

Solución

#include "iostream.h"

class Factorial {
 int vector[10];
public:
 Factorial ();
 int verFactorial(int dato) {
  if (dato < 10)
   return vector[dato];
  else {
   cout << "El valor de " << dato << " no esta presente" << endl;
   return -1;
  }
 }
};

Factorial::Factorial() {
 int i,prodacumulado=1;
 for (i = 0; i<10; i++)
  if (i == 0)
   vector[i] = 1;
  else {
   prodacumulado *= i;
   vector[i] = prodacumulado;
  }
}

main () {
 cout << "Bienvenido al programa factorial" << endl;
 Factorial miFactorial;
 cout << "5! = "<< miFactorial.verFactorial(5) << endl;
 cout << "9! = "<< miFactorial.verFactorial(9) << endl;
 cout << "2! = "<< miFactorial.verFactorial(2) << endl;
 cout << "1! = "<< miFactorial.verFactorial(1) << endl;
 cout << "15! = "<< miFactorial.verFactorial(15) << endl;
}
 

Pila con Arreglo de enteros

#include "iostream.h"

class Pila {
 int vector[50];
public:
 Pila() { }
}

Pero en este caso al crear este objeto no hace nada porque el constructor está vacío y no hay forma de llegar a su vector interno. 

Las estructuras tienen funciones que se agrupan funcionalmente de la siguiente forma. 

• Constructores
• Destructores
• Funciones analizadoras: que permiten observar los datos
• Funciones modificadoras: que modifican la estructura

Es necesario recordar que en la pila el dato que sale fue el último que se metio en la estructura. 

Para la pila se usará un vector estático de 50 posiciones y un índice que se encargará de indicar donde está la cabeza de la pila. Cuando indicePila sea -1, la pila estará vacía. Cuando sea 0, indicará que en la pila hay un dato en la posición 0, y así sucesivamente. 

La clase que podrá manejar la estructura de pila es la siguiente:

prog3

#include "iostream.h"

  // Pila hecha con un vector fijo de 50 posiciones
class Pila {
 int vector[50];
  // indicePila:  -1 -> pila vacia     0 -> posicion del dato
 int indicePila;
public:
 Pila() {   indicePila = -1; }; // constructor
  // funciones analizadoras
 void mostrarDatos();
 int cuantosDatos();
  // funciones modificadoras
 void entrarDato(int dato);
 int sacarDato();
};

 // Esta función sale del cuerpo de la clase porque usa un ciclo. 
void Pila::mostrarDatos() {
 cout << endl << "DATOS EN LA PILA" << endl;
 for (int i=0; i<=indicePila; i++)
  cout << "Dato No. " << i << " : " << vector[i] << endl;
 cout << endl;
}

int Pila::cuantosDatos() {
 return indicePila + 1;
}

void Pila::entrarDato(int dato) {
 if (indicePila < 49) {
  indicePila ++;
  vector[indicePila] = dato;
 } else
  cout << "Pila desbordada: no se añadio valor" << endl;
}

int Pila::sacarDato() {
 if (indicePila > -1) {
  indicePila --;
  return vector[indicePila + 1];
 }
 return -1;
}

Hay que notar que todas las funciones con excepción del constructor se sacaron del cuerpo de la clase y su nombre se resolvió usando los dos pares de dos puntos ::. Esto permite implementar una función miembro por fuera del cuerpo de la clase. 

De esta forma por ejemplo, la función que dentro del cuerpo de la clase se llama:

void entrarDato(int dato);

Afuera del cuerpo de la clase se llama

void Pila::entrarDato(int dato) {

Esa es la misma función solo que el primero es el prototipo que se le pasa a la clase para que sepa que hay una función con ese nombre que será implementada más adelante. 

Ahora hace falta un cuerpo del programa o main que sepa como manejar esta estructura. Para eso implementaremos una función menú que se encargará de pedir al usuario que indique cual función desea ejecutar, usando una estructura while. 

Se ha creado una función adicional que maneja el menú:

prog3 (2a parte)

int menu() {
 cout << endl << endl;
 cout << "Bienvenido al programa manejador de Pila de enteros" << endl;
 cout << "Escoja una opción" << endl;
 cout << "**************************************" << endl;
 cout << "0. Salir del Programa" << endl;
 cout << "1. Adicionar entero" << endl;
 cout << "2. Sacar entero" << endl;
 cout << "3. Ver cuantos datos tiene la pila" << endl;
 cout << "4. Mostrar datos en la pila" << endl;
 cout << "**************************************" << endl;
 int opcion;
 cin >> opcion;
 return opcion;
}

main () {
 Pila pila1;
 int respuesta,opcion;
 opcion = -1;
 while (opcion != 0) {
  opcion = menu();
  switch (opcion) {
  case 0:
   cout << "Gracias por usar nuestro software" << endl;
   break;
  case 1:
   cout << "indique valor a entrar:"; 
   cin >> respuesta;
   pila1.entrarDato(respuesta);
   break;
  case 2: 
   cout << "Dato obtenido:" << pila1.sacarDato() << endl;
   break;
  case 3: 
   cout << "Hay " << pila1.cuantosDatos() << " en la pila" << endl;
   break;
  case 4:
   pila1.mostrarDatos();
  }
 }
 return 0;
}

El programa completo será obviamente la parte que define e implementa la clase con la segunda que usa la función menú y el main. 

El switch es usado para atender cada una de las opciones que son ofrecidas al usuario en el menú. 

Estudie el anterior programa hasta entenderlo completamente. 
 

Ejercicio para Resolver No. 2

int vector [50];

Sino que sea 

int *vector;

Modifique el programa para que al entrar pida el tamaño de la pila que el usuario desea. Es decir, ya no será de 50 posiciones fijas sino del tamaño que el usuario escoja al inicio del programa

Pila con apuntadores

Tendremos una lista que usa dos apuntadores iniciales que son inicio y final que manejarán la lista enlazada y permitirán tener una pila implementada con apuntadores. Este programa desde el punto de vista del usuario es completamente igual al anterior. Sin embargo, no tiene la restricción de las 50 posiciones. 

prog3

#include "iostream.h"

struct nodo {
 int campo;
 struct nodo *anterior, *siguiente;
};
 

 // Pila hecha con apuntadores
class Pila {
 struct nodo *inicio, *final;
  // indicePila:  -1 -> pila vacia     0 -> posicion del dato
 int indicePila;
public:
 Pila() { 
  indicePila = -1; 
  inicio = NULL;
  final = NULL; 
 }; // constructor
  // funciones analizadoras
 void mostrarDatos();
 int cuantosDatos();
  // funciones modificadoras
 void entrarDato(int dato);
 int sacarDato();
 ~Pila();
};

 // Esta función sale del cuerpo de la clase porque usa un ciclo. 
void Pila::mostrarDatos() {
 cout << endl << "DATOS EN LA PILA" << endl;
 struct nodo *aux = inicio;
 int i = 0;
 while (aux != NULL) {
  cout << "Dato No. " << i << " : " << aux->campo << endl;
  i ++;
  aux = aux->siguiente;
 }
 cout << endl;
}

int Pila::cuantosDatos() {
 return indicePila + 1;
}

void Pila::entrarDato(int dato) {
 struct nodo *nuevo = new struct nodo;
 nuevo->campo = dato;
 nuevo->siguiente = NULL;
 nuevo->anterior = NULL;
 if (final != NULL) {
  final->siguiente = nuevo;
  nuevo ->anterior = final;
 } else
  inicio = nuevo;
 final = nuevo;
 indicePila ++;
}

int Pila::sacarDato() {
 struct nodo *aux = final;
 cout << "valor ";
 int valor;
 if (aux != NULL) {
  valor = aux->campo;
  if (final != NULL) 
      final = final->anterior;
  if (final != NULL) 
   final->siguiente = NULL;
  else 
   inicio = NULL;
  delete aux;
  indicePila --;
  return valor;
 } 
 return -1;
}

Pila::~Pila() {
 struct nodo *aux = inicio;
 while (aux != NULL) {
  inicio = inicio->siguiente;
  delete aux;
  aux = inicio;
 }
}

int menu() {
 cout << endl << endl;
 cout << "Bienvenido al programa manejador de Pila de enteros" << endl;
 cout << "Escoja una opción" << endl;
 cout << "**************************************" << endl;
 cout << "0. Salir del Programa" << endl;
 cout << "1. Adicionar entero" << endl;
 cout << "2. Sacar entero" << endl;
 cout << "3. Ver cuantos datos tiene la pila" << endl;
 cout << "4. Mostrar datos en la pila" << endl;
 cout << "**************************************" << endl;
 int opcion;
 cin >> opcion;
 return opcion;
}

main () {
 Pila pila1;
 int respuesta,opcion;
 opcion = -1;
 while (opcion != 0) {
  opcion = menu();
  switch (opcion) {
  case 0:
   cout << "Gracias por usar nuestro software" << endl;
   break;
  case 1:
   cout << "indique valor a entrar:"; 
   cin >> respuesta;
   pila1.entrarDato(respuesta);
   break;
  case 2: 
   cout << "Dato obtenido:" << pila1.sacarDato() << endl;
   break;
  case 3: 
   cout << "Hay " << pila1.cuantosDatos() << " en la pila" << endl;
   break;
  case 4:
   pila1.mostrarDatos();
  }
 }
 return 0;
}

Ejercicio para Resolver No. 3