From 311f7855bfd0a11c40a239edf199c14c31f8025d Mon Sep 17 00:00:00 2001 From: Leandro Lucarella Date: Thu, 18 Sep 2003 05:54:28 +0000 Subject: [PATCH] Primera version de la DLList orientada a objetos. --- dllist.cpp | 197 ++++++++++++++++++++++++++++++++++++++++++++++++++ dllist.h | 207 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 404 insertions(+) create mode 100644 dllist.cpp create mode 100644 dllist.h diff --git a/dllist.cpp b/dllist.cpp new file mode 100644 index 0000000..a2994fd --- /dev/null +++ b/dllist.cpp @@ -0,0 +1,197 @@ +/* vim: set et sts=4 sw=4 fdm=indent fdl=1 fdn=0 fo+=t tw=80: + * + * Taller de Programación (75.42). + * + * Ejercicio Número 2: + * Programa calculadora. + * + * Copyleft 2003 - Leandro Lucarella + * Puede copiar, modificar y distribuir este programa bajo los términos de + * la licencia GPL (http://www.gnu.org/). + * + * Creado: sáb ago 30 20:34:45 ART 2003 + * + * $Id$ + */ + +// TODO metodos que devuelven NULL si la lista esta vacia. +// poner comentarios en línea simple? +#include "dllist.h" + +DLList::DLList(void): first(NULL), current(NULL), last(NULL) {} + +DLList::~DLList(void) { + /* Elimino los nodos. */ + while (!DLList_empty(list)) { + DLList_pop(list); + } +} + +bool DLList::empty(void) { + return this->first == NULL; +} + +void* DLList::begin(void) { + this->current = this->first; + /* Si hay un nodo, devulevo sus datos, si no NULL. */ + return this->current ? this->current->data : NULL; +} + +void* DLList::end(void) { + this->current = this->last; + /* Si hay un nodo, devulevo sus datos, si no NULL. */ + return this->current ? this->current->data : NULL; +} + +bool DLList::have_more(void) { + return this->current != NULL; +} + +void* DLList::current(void) { + return this->current ? this->current->data : NULL; +} + +void* DLList::next(void) { + DLListNode* cur = this->current; + /* Si no está vacía ni ya fue terminada de recorrer. */ + if (cur) { + /* Apuntamos el actual al próximo. */ + this->current = cur->next; + /* Devolvemos los datos del próximo o NULL si no había otro. */ + return this->current ? this->current->data : NULL; + /* Si está vacía o ya fue terminada de recorrer devolvemos NULL. */ + } else { + return NULL; + } +} + +void* DLList::prev(void) { + DLListNode* cur = this->current; + /* Si no está vacía ni ya fue terminada de recorrer. */ + if (cur) { + /* Apuntamos el actual al anterior. */ + this->current = cur->prev; + /* Devolvemos los datos del anterior o NULL si no había otro. */ + return this->current ? this->current->data : NULL; + /* Si está vacía o ya fue terminada de recorrer devolvemos NULL. */ + } else { + return NULL; + } +} + +bool DLList::unshift(void* data) { + DLListNode* node = new DLListNode(NULL, data, this->first); + /* Si obtenemos la memoria bien, actualizamos lo que sea necesario. */ + if (node) { + /* Apunto el nodo actual al nuevo nodo. */ + this->current = node; + /* Si la lista está vacía hay que hacer apuntar todo al nuevo nodo. */ + if (this->first == NULL) { + this->first = node; + this->last = node; + /* Si no está vacía. */ + } else { + /* Apunto el nodo anterior al primer nodo de la lista al nuevo. */ + this->first->prev = node; + /* Apunto el primer nodo de la lista al nuevo. */ + this->first = node; + } + return true; + } else { + return false; + } +} + +bool DLList::push(void* data) { + DLListNode* node = new DLListNode(this->last, data, NULL); + /* Si obtenemos la memoria bien, actualizamos lo que sea necesario. */ + if (node) { + /* Apunto el nodo actual al nuevo nodo. */ + this->current = node; + /* Si la lista está vacía hay que hacer apuntar todo al nuevo nodo. */ + if (this->first == NULL) { + this->first = node; + this->last = node; + /* Si no está vacía. */ + } else { + /* Apunto el próximo nodo del último nodo de la lista al nuevo. */ + this->last->next = node; + /* Apunto el último nodo de la lista al nuevo. */ + this->last = node; + } + return true; + } else { + return false; + } +} + +void* DLList::shift(void) { + /* Primer nodo */ + DLListNode* node = this->first; + /* Datos del primer nodo. */ + void* data = node->data; + /* Pongo como primer nodo al siguiente. */ + this->first = node->next; + /* Pongo al primero como nodo actual. */ + this->current = this->first; + /* Si era el único pongo el último en NULL. */ + if (!this->first) { + this->last = NULL; + /* Si no, pongo el anterior en NULL. */ + } else { + this->first->prev = NULL; + } + /* Libero memoria del nodo. */ + delete node; + return data; +} + +void* DLList::pop(void) { + /* Último nodo */ + DLListNode* node = this->last; + /* Datos del último nodo. */ + void* data = node->data; + /* Pongo como último nodo al anterior. */ + this->last = node->prev; + /* Pongo al último como nodo actual. */ + this->current = this->last; + /* Si era el único pongo el primero en NULL. */ + if (!this->last) { + this->first = NULL; + /* Si no, pongo el siguiente en NULL. */ + } else { + this->last->next = NULL; + } + /* Libero memoria del nodo. */ + delete node; + return data; +} + +void* DLList::remove_current(void) { + /* Nodo actual */ + DLListNode* current = this->current; + /* Datos del nodo actual. */ + void* data = current->data; + /* Si tiene siguiente. */ + if (current->next) { + /* Se pone como anterior del siguiente al anterior del actual. */ + current->next->prev = current->prev; + /* Si no tiene siguiente, se pone como último al anterior del actual. */ + } else { + this->last = current->prev; + } + /* Si tiene anterior. */ + if (current->prev) { + /* Se pone como siguiente del anterior al siguiente del actual. */ + current->prev->next = current->next; + /* Si no tiene anterior, se pone como primero al siguiente del actual. */ + } else { + this->first = current->next; + } + /* Pongo como elemento actual al próximo elemento. */ + this->current = current->next; + /* Libero memoria del nodo. */ + delete current; + return data; +} + diff --git a/dllist.h b/dllist.h new file mode 100644 index 0000000..94c7d54 --- /dev/null +++ b/dllist.h @@ -0,0 +1,207 @@ +/* vim: set et sts=4 sw=4 fdm=indent fdl=1 fdn=1 fo+=t tw=80: + * + * Taller de Programación (75.42). + * + * Ejercicio Número 3: + * TODO + * + * Copyleft 2003 - Leandro Lucarella + * Puede copiar, modificar y distribuir este programa bajo los términos de + * la licencia GPL (http://www.gnu.org/). + * + * Creado: Wed Sep 17 21:07:54 ART 2003 + * + * $Id$ + */ + +#ifndef DLLIST_H +#define DLLIST_H + +/** Nodo de la lista doblemente enlazada. */ +struct DLListNode { + /** Puntero al nodo anterior. */ + DLListNode* prev; + /** Datos almacenados en el nodo. */ + void* data; + /** Puntero al próximo nodo. */ + DLListNode* next; +}; + +/** + * Lista doblemente enlazada. + */ +class DLList { + + protected: + /** Puntero al primer nodo. */ + DLListNode* first; + /** Puntero al nodo actual. */ + DLListNode* current; + /** Puntero al último nodo. */ + DLListNode* last; + + public: + /** + * Crea una nueva lista. + */ + DLList(void); + + /** + * Libera la memoria ocupada por una lista. + */ + ~DLList(void); + + /** + * Indica si está vacía. + * + * \return true si está vacía, false si no. + */ + bool empty(void); + + /** + * Apunta al primer elemento, devolviendolo. + * Hace que el elemento actual sea el primero y devuelve su valor. + * Si está vacía, devuelve NULL. + * Siempre que se quiera recorrer la lista de izquierda a derecha + * debería usarse esta función primero. Por ejemplo: + * \code + * DLList list; + * char* data; + * ... + * for (data = list.begin(); list.have_more(); data = list.next()) { + * printf("El elemento actual es '%s'.\\n", data); + * } + * \endcode + * + * \return Primer elemento o NULL si está vacía. + * \see have_more(), next(), end(), prev() + */ + void* begin(void); + + /** + * Apunta al último elemento, devolviendolo. + * Hace que el elemento actual sea el último y devuelve su valor. + * Si está vacía, devuelve NULL. + * Siempre que se quiera recorrer la lista de derecha a izquierda + * debería usarse esta función primero. Por ejemplo: + * \code + * DLList list; + * char* data; + * ... + * for (data = list.end(); list.have_more(); data = list.prev()) { + * printf("El elemento actual es '%s'.\\n", data); + * } + * \endcode + * + * \return Último elemento o NULL si está vacía. + * \see DLList_have_more(), DLList_prev(), DLList_begin(), DLList_next() + * \pre La DLList debe estar \ref DLList_new "creada" correctamente. + */ + void* end(void); + + /** + * Indica si se puede obtener otro elemento de la lista. + * + * \return true si se puede obtener otro elemento, false si no. + * \see begin(), end(), prev(), next() + */ + bool have_more(void); + + /** + * Obtiene el elemento actual. + * + * \return Elemento actual o NULL si se terminó de recorrer o está vacía. + * \see prev(), next(), have_more() + */ + void* current(void); + + /** + * Obtiene el próximo elemento. + * + * \return Siguiente elemento o NULL si es el último. + * \see begin(), have_more(), current(), prev() + */ + void* next(void); + + /** + * Obtiene el elemento anterior. + * + * \return Elemento anterior o NULL si es el primero. + * \see begin(), have_more(), current(), next() + */ + void* prev(void); + + /** + * Agrega un elemento al inicio. + * + * \param data Elemento a agregar. + * + * \return true si se agregó, false si no hay más memoria. + * \see push(), pop(), unshift() + */ + bool unshift(void* data); + + /** + * Agrega un elemento al final. + * + * \param data Elemento a agregar. + * + * \return true si se agregó, false si no hay más memoria. + * \see pop(), shift(), unshift() + */ + bool push(void* data); + + /** + * Saca el primer elemento. + * Elimina el primer elemento devolviendo su contenido. + * Ejemplo: + * \code + * DLList list; + * char* data; + * ... + * while (!list.empty()) { + * data = list.shift(); + * printf("El elemento actual es '%s'.\\n", data); + * } + * \endcode + * + * \return Primer elemento o NULL si está vacía. + * \see empty(), pop(), remove_current() + * \warning Es necesario comprobar antes si está vacía, ya que puede + * devolver NULL también si el elemento de la lista es NULL. + */ + void* shift(void); + + /** + * Saca el último elemento. + * Elimina el último elemento devolviendo su contenido. + * Ejemplo: + * \code + * DLList list; + * char* data; + * ... + * while (!list.empty()) { + * data = list.pop(); + * printf("El elemento actual es '%s'.\\n", data); + * } + * \endcode + * + * \return Último elemento o NULL si está vacía. + * \see empty(), shift(), remove_current() + * \warning Es necesario comprobar antes si está vacía, ya que puede + * devolver NULL también si el elemento de la lista es NULL. + */ + void* pop(void); + + /** + * Elimina el elemento actual. + * Elimina el elemento actual devolviendo su contenido. + * + * \return Elemento actual o NULL si no hay más elementos. + * \see empty(), current(), have_more() + * \warning Es necesario comprobar antes si está vacía, ya que puede + * devolver NULL también si el elemento de la lista es NULL. + */ + void* remove_current(void); + +#endif /* DLLIST_H */ -- 2.43.0