PILA DINAMICA VTJE

Vista previa del material en texto

Centro Universitario de Ciencias
Exactas e Ingenierías
Ingeniería informática
SEMINARIO DE SOLUCIÓN DE PROBLEMAS DE ESTRUCTURAS DE DATOS I
Nombre del Alumno:
Valenciano Tadeo Jeremy Esau
PILA DINÁMICA
Declaración de la clase Disk
Empezaremos con la declaración de una clase llamada Disk esta clase será la
encargada de definir los atributos y métodos con los que contara nuestro objeto, esta
clase contara con el atributo de tipo entero llamado sizeOfDisk.
Por otra parte, los getters se encargaran de obtener y retornar los datos que el
objeto tenga, además contara de otros métodos como lo son imprimir. El método
imprimir se encargara de concatenar todos los atributos del objeto y los retornara.
A cada método setter se le pasara por referencia los valores que el usuario ingrese,
estos se deben mantener de manera constante debido a que no se modificara su
valor a lo largo de la ejecución del método.
1
Después encontraremos la respectiva sobrecarga de operadores, estos se
encargarán de modificar el comportamiento de dichos operadores para poder
manipular los objetos de la manera que se desea. Dichas recargas de los operadores
nos ayudarán a retornar el tamaño del disco y así comparar discos o igualar.
Implementación de la clase Disk.
2
3
En la implementación de la clase Disk, el método set será el encargado de asignar el
valor que se pase por referencia al atributo de la clase.
Posteriormente, el método get retornara el valor del atributo sizeofDisk, el método to
string concatenara los valores de la clase y la retornara en un string.
La sobrecarga de los operadores de asignacion y de igualacion retornaran el tamaño
de los discos, dicho atributo se llama sizeofDisk.
Main cpp
Empezamos incluyendo las librerías que necesitaremos, la librería stack la cual incluye
la implementación de una pila dinámica con Templetes, la librería disk que es la
encargada de ejemplificar un disco de la torre, la librería de excepciones, la de iostream
que es la encargada de las operaciones de entrada/salida. Ademas de la libreria string
para el manejo de cadenas de caracteres y de math para calcular la formula de los
movimientos de las torres de hanoi.
Declaración de variables.
Despues crearemos 3 pilas para asi simular las torres de Hanoi, nuestra pilas son
4
dinamicas, por lo cual nuestras templates no tendran un tamaño definido. Tambien
tendremos una variable la cual contara el numero de movimientos y los movimientos
minimos.
Función resultado
Esta funcion se encargara de verificar si las pilas se encuentran vacias, en caso de ser
asi se imprimira solo la base de la pila, si la pila no se encuentra vacia se ejecutara el
metodo toString de la pila.
5
Función cambió
Esta funcion verificara si tanto la torre 1 y la torre 2 esta vacia, se llamara a la funcion
resultado la cual imprimira las torres, si las dos torres estan vacias quiere decir que el
juego se ha terminado, posteriormente imprimira los movimientos y calculara los
movimientos mimimos y tambien los imprimira.
En caso de que ninguno de los casos anteriores pasen se imprimran las torres y se
crearan las variables de origen y destino que se encargaran de guadar el numero de
las torres que el usuario desea desapilar y apilar.
En caso de que tanto el origen como el destino sea el mismo imprimira un error. Si no
sucede esto incrementaremos la variable de movimientos.
Utilizaremos un case anidado donde primero se evaluara la torre de origen y después
en el otro case la torre de destino. Se generará una disco auxiliar el cual obtendrá el
tope de la torre 1 y después obtendremos su tamaño y lo guardaremos en el auxiliar 1.
En el segundo switch se evaluara la torre de destino, primero se evaluara si está vacía,
Se generara una disco auxiliar el cual obtendrá el tope de la torre 2 y después
obtendremos su tamaño y lo guardaremos en el auxiliar 2.
En caso de que el tamaño del disco 1 sea menor al de disco 2 se imprimirá un mensaje
de error y se decrementara el movimiento que se realizó, finalmente volveremos a
llamar a la función cambio.
6
Después de desa pilar el elemento de la torre 1, se le asignará el tamaño del disco al
disco auxiliar. Se intentara apilar dicho disco en la torre 2 y en caso de que no se pueda
apilar se lanzara una excepción.
En el Tercer switch se evaluara la torre de destino, primero se evaluara si está vacía,
Se generara una disco auxiliar el cual obtendrá el tope de la torre 3 y después
obtendremos su tamaño y lo guardaremos en el auxiliar 2.
En caso de que el tamaño del disco 1 sea menor al de disco 2 se imprimirá un mensaje
de error y se decrementara el movimiento que se realizó, finalmente volveremos a
llamar a la función cambio.
Después de desa pilar el elemento de la torre 1, se le asignará el tamaño del disco al
disco auxiliar. Se intentará apilar dicho disco en la torre 3 y en caso de que no se pueda
7
apilar se lanzará una excepción. En caso de que el usuario no digite alguna opción
válida, se imprimirá un error con el default del switch
Utilizaremos un case anidado donde primero se evaluara la torre de origen y después
en el otro case la torre de destino. Se generará una disco auxiliar el cual obtendrá el
tope de la torre 1 y después obtendremos su tamaño y lo guardaremos en el auxiliar 1.
En el segundo switch se evaluara la torre de destino, primero se evaluara si está vacía,
Se generara una disco auxiliar el cual obtendrá el tope de la torre 2 y después
obtendremos su tamaño y lo guardaremos en el auxiliar 2.
En caso de que el tamaño del disco 1 sea menor al de disco 2 se imprimirá un mensaje
de error y se decrementara el movimiento que se realizó, finalmente volveremos a
llamar a la función cambio.
Después de desa pilar el elemento de la torre 1, se le asignará el tamaño del disco al
disco auxiliar. Se intentará apilar dicho disco en la torre 2 y en caso de que no se pueda
8
apilar se lanzará una excepción.
Función main
Dentro de nuestra función main se creara una variable que guarde el número de discos
con los que iniciara la torre número 1, después igualaremos los movimientos mínimos
al número de discos, con ayuda de un bucle for haremos una iteración hasta que
nuestro auxiliar sea menor al número de discos.
Dentro de nuestro bucle a nuestro disco auxiliar le asignaremos el número de discos
menos el auxiliar, después intentaremos apilar dicho disco en la torre 1, en caso de que
no se pueda apilar correctamente se imprimirá y lanzara una excepción.
Al finalizar nuestro bucle invocaremos la función cambio.
9
Código
Disk.H
#ifndef DISK_H_INCLUDED
#define DISK_H_INCLUDED
#include <string>
using namespace std;
10
class Disk {
private:
int sizeOfDisk;
public:
void setSizeOfDisk(const int&);
int getSizeOfDisk();
string toString();
Disk& operator = (const Disk&);
bool operator == (const Disk&);
};
11
#endif // DISK_H_INCLUDED
Disk.cpp
#include "disk.h"
void Disk::setSizeOfDisk(const int& a)
{
sizeOfDisk = a;
}
int Disk::getSizeOfDisk()
{
return sizeOfDisk;
}
string Disk::toString()
{
string result;
result = "\t| ";
if(sizeOfDisk <= 9) { result += " "; }
result += to_string(sizeOfDisk);
12
result += " |";
return result;
}
Disk& Disk::operator=(const Disk& a)
{
sizeOfDisk = a.sizeOfDisk;
return *this;
}
bool Disk::operator==(const Disk& a)
{
return sizeOfDisk = a.sizeOfDisk;
}
Stack.H
#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED
#include <exception>
#include <string>
13
template <class T>
class Stack
{
private:
class Node
{
private:
T data;
Node* next;
public:
Node();
Node(const T&);
T getData() const;
Node* getNext() const;
void setData(const T&);
void setNext(Node*);
14
friend class Stack;
};
Node* anchor;
void copyAll(const Stack<T>&);
bool isValidPos(Node*) const;
void deleteAll();
public:
typedef Node* Position;
class Exception : public std::exception
{
private:
std::string msg;
public:
15
explicit Exception(const char* message) :
msg(message) { }
explicit Exception(conststd::string& message) :
msg(message) { }
virtual ~Exception() throw () { }
virtual const char* what() const throw ()
{
return msg.c_str();
}
};
Stack();
Stack(const Stack<T>&);
bool isEmpty() const;
void push(const T&);
16
T pop();
T getTop() const;
std::string toString() const;
Stack<T>& operator = (const Stack<T>&);
~Stack(); ///Dildre El destructor solo se usa cuando
es memoria dinamica
};
///Implementaciones
///Nodo
template <class T>
Stack<T>::Node::Node() : next(nullptr) {}
template <class T>
Stack<T>::Node::Node(const T& e) : data(e), next(nullptr)
{}
17
template <class T>
T Stack<T>::Node::getData() const
{
return data;
}
template <class T>
typename Stack<T>::Node* Stack<T>::Node::getNext() const
{
return next;
}
template <class T>
void Stack<T>::Node::setData(const T& e)
{
data = e;
}
template <class T>
18
void Stack<T>::Node::setNext(Node* p)
{
next = p;
}
/// Pila
template <class T>
void Stack<T>::copyAll(const Stack<T>& pila1)
{
Node* aux(pila1.anchor);
Node* ultimoIngresado(nullptr);
Node* nuevoNodo;
while(aux != nullptr)
{
nuevoNodo = new Node(aux->getData());
if(ultimoIngresado == nullptr)
{
anchor = nuevoNodo;
19
}
else
{
ultimoIngresado->setNext(nuevoNodo);
}
ultimoIngresado = nuevoNodo;
aux = aux->getNext();
}
}
template <class T>
bool Stack<T>::isValidPos(Node* posi) const
{
Node* aux(anchor);
while(aux != nullptr)
{
if(aux == posi)
{
return true;
20
}
aux = aux->getNext();
}
return false;
}
template <class T>
Stack<T>::Stack() : anchor(nullptr) {}
template <class T>
Stack<T>::Stack(const Stack<T>& pila1) : anchor(nullptr)
{
copyAll(pila1);
}
template <class T>
bool Stack<T>::isEmpty() const
{
return anchor == nullptr;
21
}
template <class T>
void Stack<T>::push(const T& ele)
{
Node* aux(new Node(ele));
if(aux == nullptr)
{
throw Exception("Memoria no disponible, tratando
de crear new Node, push");
}
aux->setNext(anchor);
anchor = aux;
}
template <class T>
T Stack<T>::pop()
22
{
if(anchor == nullptr)
{
throw("Insuficiencia de datos, pop");
}
T result(anchor->getData());
Node* aux(anchor);
anchor = anchor->getNext();
delete aux;
return result;
}
template <class T>
T Stack<T>::getTop() const
{
if(anchor == nullptr)
23
{
throw Exception("Insuficiencia de datos,
getTop");
}
return anchor->getData();
}
template <class T>
std::string Stack<T>::toString() const
{
std::string resultado;
Node* aux(anchor);
while(aux != nullptr)
{
resultado += aux->getData().toString() + "\n";
aux = aux->getNext();
}
24
return resultado;
}
template <class T>
void Stack<T>::deleteAll()
{
Node* aux;
while(anchor != nullptr)
{
aux = anchor;
anchor = anchor->getNext();
/// Liberamos memoria
delete aux;
}
}
template <class T>
25
Stack<T>& Stack<T>::operator=(const Stack<T>& pila1)
{
deleteAll();
copyAll(pila1);
return *this;
}
template <class T>
Stack<T>::~Stack()
{
deleteAll();
}
#endif // LIST_H_INCLUDED
Main.cpp
#include "stack.h"
#include "disk.h"
26
#include <exception>
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
// declaracion de las 3 pilas
Stack<Disk> torre1;
Stack<Disk> torre2;
Stack<Disk> torre3;
Disk diskAux;
int movimientos = 0;
int movimientosMin = 0;
void result()
{
if (torre1.isEmpty())
{
cout << "\n\n\n\n\t TORRE #1\n\n\n\t|
27
|\n\t|______|";
}
else
{
cout << "\n\n\n\n\t TORRE #1\n\n\n";
cout << torre1.toString();
cout << "\t|______|";
}
if (torre2.isEmpty())
{
cout << "\n\n\n\n\t TORRE #2\n\n\n\t|
|\n\t|______|";
}
else
{
cout << "\n\n\n\n\t TORRE #2\n\n\n";
cout << torre2.toString();
cout << "\t|______|";
}
28
if (torre3.isEmpty())
{
cout << "\n\n\n\n\t TORRE #3\n\n\n\t|
|\n\t|______|";
}
else
{
cout << "\n\n\n\n\t TORRE #3\n\n\n";
cout << torre3.toString();
cout << "\t|______|";
}
cout << "\n\n";
}
void cambio()
{
if (torre1.isEmpty())
{
if (torre2.isEmpty())
{
29
result();
cout << "\n\tJUEGO TERMINADO \t Total de
movimientos: " << movimientos << "\n\n\tMovimientos
minimos: " << pow(2, movimientosMin) - 1 << "\n\n\n\n";
exit(0);
}
}
result();
int origenT = 0;
int destinoT = 0;
int myAux1, myAux2;
cout << "\n\tDigite el # de la torre de origen: ";
cin >> origenT;
cout << "\n\tDigite el # de la torre de destio: ";
cin >> destinoT;
if (origenT == destinoT)
30
{
cout << "\n\n\t ERROR Misma posicion de origen y
Destino \n";
system("pause");
cambio();
}
movimientos++;
switch (origenT)
{
case 1:
{
Disk myAuxDisk = torre1.getTop();
myAux1 = myAuxDisk.getSizeOfDisk();
switch (destinoT)
{
31
case 2:
if (torre2.isEmpty())
{
}
else
{
Disk auxDisk2 = torre2.getTop();
myAux2 = auxDisk2.getSizeOfDisk();
if (myAux1 > myAux2)
{
cout << "\n\n\t ERROR Disco de ORIGEN
es mas GRANDE que el de destino" << endl;
system("pause");
movimientos--;
cambio();
}
}
32
torre1.pop();
diskAux.setSizeOfDisk(myAux1);
try
{
torre2.push(diskAux);
}
catch (Stack<Disk>::Exception ex)
{
cout << "ERROR AL INSERTAR" << endl;
cout << ex.what() << endl;
}
cambio();
break;
case 3:
if (torre3.isEmpty())
{
33
}
else
{
Disk auxDisk2 = torre3.getTop();
myAux2 = auxDisk2.getSizeOfDisk();
if (myAux1 > myAux2)
{
cout << "\n\n\tERROR Disco de ORIGEN
es mas GRANDE que el de destino" << endl;
system("pause");
movimientos--;
cambio();
}
}
torre1.pop();
diskAux.setSizeOfDisk(myAux1);
try
34
{
torre3.push(diskAux);
}
catch (Stack<Disk>::Exception ex)
{
cout << "ERROR AL INSERTAR" << endl;
cout << ex.what() << endl;
}
cambio();
break;
default:
cout << "\n\n\tERROR El destino es INVALIDO"
<< endl;
system("pause");
exit(0);
break;
}
}
break;
35
case 2:
{
if (torre2.isEmpty())
{
cout << "\n\n\tERROR El origen no tiene
discos" << endl;
system("pause");
movimientos--;
cambio();
}
Disk auxDisk = torre2.getTop();
myAux1 = auxDisk.getSizeOfDisk();
switch (destinoT)
{
case 1:
36
if (torre1.isEmpty())
{
}
else
{
Disk auxDisk2 = torre1.getTop();
myAux2 = auxDisk2.getSizeOfDisk();
if (myAux1 > myAux2)
{
cout << "\n\n\t ERROR Disco de ORIGEN
es mas GRANDE que el de destino" << endl;
system("pause");
movimientos--;
cambio();
}
}
torre2.pop();
37
diskAux.setSizeOfDisk(myAux1);
try
{
torre1.push(diskAux);
}
catch (Stack<Disk>::Exception ex)
{
cout << "ERROR AL INSERTAR" << endl;
cout << ex.what() << endl;
}
cambio();
break;
case 3:
if (torre3.isEmpty())
{
}
else
{
38
Disk auxDisk2 = torre3.getTop();
myAux2 = auxDisk2.getSizeOfDisk();
if (myAux1 > myAux2)
{
cout << "\n\n\t ERROR Disco de ORIGEN
es mas GRANDE que el de destino" << endl;
system("pause");
movimientos--;
cambio();
}
}
torre2.pop();
diskAux.setSizeOfDisk(myAux1);
try
{
torre3.push(diskAux);
}
39
catch (Stack<Disk>::Exception ex)
{
cout << "ERROR AL INSERTAR" << endl;
cout << ex.what() << endl;
}
cambio();
break;
default:
cout << "\n\n\t ERROR Destino de disco
invalido, seleccione otra opcion" << endl;
system("pause");
exit(0);
break;
}
}
break;
case 3:
{
40
if (torre3.isEmpty())
{
cout << "\n\n\t ERROR, El ORIGEN seleccionado
NO tiene DISCOS disponibles" << endl;
system("pause");
movimientos--;
cambio();
}
Disk auxDisk = torre3.getTop();
myAux1 = auxDisk.getSizeOfDisk();
switch (destinoT)
{
case 1:
if (torre1.isEmpty())
{
}
41
else
{
Disk auxDisk2 = torre1.getTop();
myAux2 = auxDisk2.getSizeOfDisk();
if (myAux1 > myAux2)
{
cout << "\n\n\t ERROR Disco de ORIGEN
es mas GRANDE que el de destino" << endl;
system("pause");
movimientos--;
cambio();
}
}
torre3.pop();
diskAux.setSizeOfDisk(myAux1);
try
42
{
torre1.push(diskAux);
}
catch (Stack<Disk>::Exception ex)
{
cout << "ERROR AL INSERTAR" << endl;
cout << ex.what() << endl;
}
cambio();
break;
case 2:
if (torre2.isEmpty())
{
}
else
{
Disk auxDisk2 = torre2.getTop();
myAux2 = auxDisk2.getSizeOfDisk();43
if (myAux1 > myAux2)
{
cout << "\n\n\t ERROR Disco de ORIGEN
es mas GRANDE que el de destino" << endl;
system("pause");
movimientos--;
cambio();
}
}
torre3.pop();
diskAux.setSizeOfDisk(myAux1);
try
{
torre2.push(diskAux);
}
catch (Stack<Disk>::Exception ex)
{
cout << "ERROR AL INSERTAR" << endl;
44
cout << ex.what() << endl;
}
cambio();
break;
default:
cout << "\n\n\t ERROR Destino de disco
invalido, seleccione otra opcion" << endl;
system("pause");
exit(0);
break;
}
}
break;
default:
cout << "\n\n\t ERROR Destino de disco invalido,
seleccione otra opcion" << endl;
system("pause");
exit(0);
45
break;
}
}
int main()
{
system("color 09");
int numDisks = 0;
system("cls");
cout << "\n\t PRACTICA TORRES DE HANOI " << endl;
cout << "\n\tIngrese la cantidad de discos que desea
para su torre: ";
cin >> numDisks;
movimientosMin = numDisks;
for (int aux = 0; aux < numDisks; aux++)
{
diskAux.setSizeOfDisk(numDisks - aux);
46
try
{
torre1.push(diskAux);
}
catch (Stack<Disk>::Exception ex)
{
cout << "ERROR AL INSERTAR" << endl;
cout << ex.what() << endl;
}
}
cambio();
return 0;
}
47