PilaCeldaEnlazada.hpp
/*! \par Fichero: Pila.hpp \mainpage Pila a partir de Celdas Enlazadas \author Julio Camacho Cañamón */ #ifndef _Pila_HPP_ #define _Pila_HPP_ #include <cassert> // Facilita la entrada y salida #include <iostream> #include "pilainterfaz.hpp" /*!\brief Espacio de nombres para la asignatura Estructura de datos.*/ namespace ed { //! Estructura de los nodos de la Pila template <class G> //Pantilla de tipo genérico G struct NodoPila{ G elemento; //!< Campo informativo de la Pila NodoPila *siguiente; //!< Puntero al siguiente nodo de la Pila }; //! Definición de la clase Pila template<class G> class Pila :public PilaInterfaz<G> { private: int _l; //!< Almacena el número máximo de elementos que va a tener la Pila. int _n; //!< Número de elementos de la Pila NodoPila<G> *_cima; //!< Cima de la Pila public: //! \name Constructor de la clase Pila /*! \brief Constructor que crea una Pila vacía \pre Ninguna \post La Pila toma los siguientes valores por defecto _n = 0; _cima = NULL; _l=100; */ Pila(int l=100) { tamanyo(0); limite(l); _cima = NULL; } //! \name Desctructor de la clase Pila ~Pila() { liberarMemoria(); } //! \name Constructor de copia de la clase Pila /*! \brief Constructor que crea una Pila a partir de otra \param Pila pasada por referencia constante \pre Ninguna */ Pila(const Pila &p) { tamanyo(0);//No podemos copiar el tamaño, sino nos va a dejar apilar cuando tengamos los datos de la pila p limite(p.limite()); NodoPila<G> *cursor=p._cima; G vector[p.tamanyo()]; int i=0; for( i=0; i<p.tamanyo() ; i++) { vector[i]=cursor->elemento; cursor=cursor->siguiente; } for(i=p.tamanyo()-1; i>=0; i--) { apilar(vector[i]); } //Opción desechada que utilizaba una pila auxiliar para guardar el contenido de la pila. //Se desecha porque no se puede modificar la pila pasada como referencia constante. /* NodoPila<G> *cursor=p._cima; Pila PilaAux;//Se crea una Pila auxiliar con valores por defecto while(PilaAux.tamanyo()<p.tamanyo()) { PilaAux.apilar(cursor->elemento); cursor=cursor->siguiente; } cursor=PilaAux._cima; while(tamanyo()<PilaAux.tamanyo()) { apilar(cursor->elemento); cursor=cursor->siguiente; } */ /* Pila PilaAux;//Se crea una Pila auxiliar con valores por defecto while(not estaVacia()) //mientras nuestra Pila original NO esté vacia... { PilaAux.apilar(p.cima());//APilamos en la Pila auxiliar la cima de nuestra Pila original p.desapilar();//quitamos el elmento de la cima de nuestra Pila original } //cuando acabe el bucle, tendremos la Pila original (p) vacia, y en la Pila auxiliar, el contenido de la orginal, pero en orden inverso while(not PilaAux.estaVacia())//mientras la Pila auxiliar no esté vacia... { p.apilar(PilaAux.cima());//Devolvemos a nuestra Pila original, la cima de la auxiliar (es decir la base original) apilar(PilaAux.cima());//guardmos en la Pila nueva la cima de la auxiliar PilaAux.desapilar();//desaPilamos de la auxiliar } //cuando acabe este bucle, tendremos tanto en la original como en la nueva el conteido de la original */ } //! \name Funciones de observadores y modificadores de la clase Pila /*! \brief Indica cuantos elementos tiene la Pila \return Devuelve el numero de elementos de la Pila \pre Ninguna \post Ninguna \sa vacia */ inline int tamanyo() const throw() { return _n; } /*! \brief Modifica el número de elementos que tiene la Pila \param int n, número de elementos que va a tener la Pila \pre Ninguna \post Ninguna \sa vacia */ inline void tamanyo(const int & n) throw() { _n=n; } /*! \brief Indica el límite de elementos que tiene la Pila \return Devuelve el límite de elementos de la Pila \pre Ninguna \post Ninguna \sa apilar */ inline int limite() const throw() { return _l; } /*! \brief Modifica el límite de elementos que tiene la Pila \param int n, número máximo de elementos que puede tener la Pila \pre Ninguna \post Ninguna \sa vacia */ inline void limite(const int & l) throw() { _l=l; } //! \name Funciones de acceso de la clase Pila /*! \brief Comprueba si una Pila está vacía \return Devuelve true si la Pila está vacía; false, en caso contrario \pre Ninguna \post Ninguna \sa tamanyo */ bool estaVacia () const throw() { if (tamanyo()==0) return true; else return false; } /*! \brief Comprueba si una Pila está llena \return Devuelve true si la Pila está llena; false, en caso contrario \pre Ninguna \post Ninguna \sa limite, tamanyo */ bool estaLlena () const throw () { if (tamanyo() == limite()) return true; else return false; } /*! \brief Indica el elemento que hay en la cima \return Devuelve una referencia constante al elemento que hay en la cima \pre Ninguna \post Ninguna \sa tamanyo, vacia */ inline const G & cima () const throw() { //std::cout<<"\ncima(): "<<_cima->elemento; return (_cima->elemento); } //! \name Funciones de modificación de la clase Pila /*! \brief Libera la memoria ocupada por una Pila \return void \pre Ninguna \post Pila se queda vacía \sa vacia */ void liberarMemoria() { if (not estaVacia()) { NodoPila<G> *_borrar; while (_cima != NULL) { _borrar = _cima; _cima = _cima->siguiente; delete _borrar; //Va eliminando la Pila desde la cima hasta el final, mientras la cima no sea el último elmento } tamanyo(0); _cima=NULL; } } /*! \brief Elimina el nodo cima de la Pila \pre Que exista la Pila y no esté vacía \post La nueva cima será el nodo apuntado por la cima antigua \sa vacia */ void desapilar() throw() { //std::cout<<"\nSoy Desapilar() estaVacia()="<<estaVacia(); NodoPila<G> *cimaVieja=_cima; //Guardamos el puntero a la cima que va a ser borrada if(not estaVacia()) { //Actualizamos los cursores _cima=_cima->siguiente; //std::cout<<"\nTamaño preDesapilar: "<<tamanyo()<<" Tamaño postDesapilar: "<<tamanyo(); //Decrementamos el número de elementos en la Pila tamanyo(tamanyo()-1); } } /*! \brief Inserta un nuevo elemento en la Pila \param G elemto que se inserta en la Pila \return true si la operación ha tenido éxito o false en caso contrario \pre Que exista la Pila \post La cima queda modificada \sa vacia */ void apilar(G const &p) throw() { //std::cout<<"\nSoy Apilar("<<p<<") estaLlena()="<<estaLlena(); if(not estaLlena())//si NO se ha llegado al límite de elmentos... { //std::cout<<"\nSoy Apilar("<<p<<") y estoy dentro del if"; NodoPila<G> *nodo, *cimaVieja; nodo = new NodoPila<G>; // reservamos memoria para un nuevo nodo; //Guardando nodos viejos cimaVieja=_cima; //Inicializando valores de nodo nodo->elemento=p; //hacemos que el elemento del nuevo nodo tenga el valor pasado, p nodo->siguiente=_cima;//hacemos que el nuevo nodo sea el primero apuntando al que apunta ahora el cursor _cima //std::cout << "\nApilar: nodo->elemento: "; //std::cout <<nodo->elemento; //Actualizar cima _cima=nodo;//hacemos que _cima apunten al nuevo nodo //Añadir un nuevo elemento al contador propio de la clase Pila tamanyo(tamanyo()+1); //Si no se hiciese, siempre nos diría que la Pila está vacia //std::cout<<"\nApilar: Tamaño: "<<tamanyo(); //std::cout << "\nApilar: Cima: "<<cima(); } } //Sobrecarga del operador de asignación con una Pila Pila &operator=( const Pila &p) { if (estaVacia() == false)//en caso de que hubiese algo en la Pila a la que le queremos asignar el contenido de p... liberarMemoria();//eliminamos todo lo que tenga tamanyo(0);//No podemos copiar el tamaño, sino nos va a dejar apilar cuando tengamos los datos de la pila p limite(p.limite()); NodoPila<G> *cursor=p._cima; G vector[p.tamanyo()]; int i=0; for( i=0; i<p.tamanyo() ; i++) { vector[i]=cursor->elemento; cursor=cursor->siguiente; } for(i=p.tamanyo()-1; i>=0; i--) { apilar(vector[i]); } return *this; } }; } //namespace ed #endif //__Pila_HPP__
PilaInterfaz.hpp
#ifndef __PILA_INTERFAZ_HPP__ #define __PILA_INTERFAZ_HPP__ #include <string> #include <cassert> /*!\brief Espacio de nombres para la asignatura Estructura de datos.*/ namespace ed { /*! \brief Clase interfaz para definir una pila. Una pila es una colección de elementos de forma tal que el único elemento accesible para borrarlo o consultarlo, es el último elemento introducido, que se denomina cima. Una vez que se borra la cima, la nueva cima sería el elemento que se insertó previamente a la antigua cima, si existía, en caso contrario la pila queda vacía. En nuestro caso vamos a definir una pila de elemento genéricos G y de tamaño limitado. */ template<class G> class PilaInterfaz { public: /*!\name Operaciones. @{ */ /*!\brief Inserta un elemento de tipo G en la Pila. \arg[in] x indica el elemento de tipo G a insertar en la pila. \pre La pila no está llena. \post La pila no está vacía. */ virtual void apilar(const G &x) throw () = 0; /*!\brief elimina un elemento de la pila. Elimina el único elemento disponible de la pila que es la cima \pre La pila no está vacía. \post El elemento que hay en la cima ha quedado eliminado */ virtual void desapilar() throw () = 0; /*!\brief Muestra la cima de la pila. Muestra el elemento que está en la cima de la pila, dejando a ésta invariable. \return el elemento de tipo G que está en la cima de la pila \pre La pila no está vacía */ virtual const G & cima () const throw () = 0; /*!\brief Comprueba si la pila está vacía \return true si la pila está vacía y false en caso contrario */ virtual bool estaVacia () const throw () = 0; /*!\brief Comprueba si la pila está llena \return true si la pila está llena y false en caso contrario */ virtual bool estaLlena () const throw () = 0; /*!@}*/ }; } //namespace ed #endif //__PILA_HPP__
main.hpp
//#define NDEBUG #include <cassert> #include <iostream> #include "pilainterfaz.hpp" #include "pilaCeldaEnlazada.hpp" //#include "pila.hpp" using namespace ed; using namespace std; int main() { Pila<int> p; //Comprobación de la inserción for(int i = 1; i <= p.limite(); i++) p.apilar(i); cout<<"Apilar comprobada\n"; //Creamos una pila a partir del constructor de copia. Pila<int> p1(p); //Creamos otra pila a partir de la asignación. Pila<int> p2; p2 = p; //Comprobación de límite de la pila //p.apilar(100); cout<<"llena comprobada\n"; //Comprobación de desapilar for(int i = p1.tamanyo(); i > 0; i--) { assert(p.cima() == i); p.desapilar(); } cout<<"Desapilar comprobada\n"; //Comprobación de que está vacía assert(p.estaVacia() == true); cout<<"Vacia comprobada\n"; //Comprobaciones para la pila construída a partir del constructor de copia. //Comprobación de límite de la pila //p1.apilar(100); //Comprobación de desapilar for(int i = p1.tamanyo(); i > 0; i--) { assert(p1.cima() == i); p1.desapilar(); } cout<<"Desapilar comprobada en p1\n"; //Comprobación de que está vacía assert(p1.estaVacia() == true); cout<<"Vacia comprobada\n"; //Comprobaciones para la pila construída a partir de la asignación. //Comprobación de desapilar for(int i = p2.tamanyo(); i > 0; i--) { assert(p2.cima() == i); p2.desapilar(); } cout<<"Desapilar comprobada en p2\n"; //Comprobación de que está vacía assert(p2.estaVacia() == true); cout<<"Vacia comprobada\nFIN, Todo con ÉXITO\n\n"; return 0; }
Correcto. Deberías haber quitado los comentarios que has puesto cuando se usaba una pila auxiliar.
ResponderEliminarHas colocado la tarea de estructuras dinámicas en el módulo de ficheros.