From: Leandro Lucarella Date: Sun, 31 Aug 2003 07:02:48 +0000 (+0000) Subject: Se agrega la primera versión que compila de la lista doblemente enlazada. X-Git-Tag: svn_import~29 X-Git-Url: https://git.llucax.com/z.facultad/75.42/calculadora.git/commitdiff_plain/f74ef52ac13755f7680dbad22168b8d8e8b98e63 Se agrega la primera versión que compila de la lista doblemente enlazada. --- diff --git a/dllist.c b/dllist.c new file mode 100644 index 0000000..ed2b62c --- /dev/null +++ b/dllist.c @@ -0,0 +1,134 @@ +/* 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 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$ + */ + +#include "dllist.h" +#include + +bool DLList_init(DLList* list) { + list = (DLList*)malloc(sizeof(DLList)); + if (list) { + list->first = NULL; + list->current = NULL; + list->last = NULL; + } + return list ? TRUE : FALSE; +} + +bool DLList_empty(DLList* list) { + return list->first == NULL; +} + +void* DLList_reset(DLList* list) { + list->current = list->first; + return list->current ? list->current->data : NULL; +} + +void* DLList_current(DLList* list) { + return list->current ? list->current->data : NULL; +} + +void* DLList_next(DLList* list) { + DLNode* ret; + ret = list->current; + if (ret) { + list->current = ret->next; + return list->current ? list->current->data : NULL; + } + return NULL; +} + +bool DLList_unshift(DLList* list, void* data) { + DLNode* node = (DLNode*)malloc(sizeof(DLNode)); + /* Si obtenemos la memoria bien, actualizamos lo que sea necesario. */ + if (node) { + /* Inicializamos el nuevo nodo. */ + node->prev = NULL; + node->data = data; + node->next = list->first; + /* Si la lista está vacía hay que hacer apuntar todo al nuevo nodo. */ + if (DLList_empty(list)) { + list->first = node; + list->current = node; + list->last = node; + /* Si no está vacía. */ + } else { + /* Apunto el nodo anterior al primer nodo de la lista al nuevo. */ + list->first->prev = node; + /* Apunto el primer nodo de la lista al nuevo. */ + list->first = node; + } + } + return node ? TRUE : FALSE; +} + +bool DLList_push(DLList* list, void* data) { + DLNode* node = (DLNode*)malloc(sizeof(DLNode)); + /* Si obtenemos la memoria bien, actualizamos lo que sea necesario. */ + if (node) { + /* Inicializamos el nuevo nodo. */ + node->prev = list->last; + node->data = data; + node->next = NULL; + /* Si la lista está vacía hay que hacer apuntar todo al nuevo nodo. */ + if (DLList_empty(list)) { + list->first = node; + list->current = node; + list->last = node; + /* Si no está vacía. */ + } else { + /* Apunto el próximo nodo del último nodo de la lista al nuevo. */ + list->last->next = node; + /* Apunto el último nodo de la lista al nuevo. */ + list->last = node; + } + } + return node ? TRUE : FALSE; +} + +void* DLList_shift(DLList* list) { + /* Primer nodo */ + DLNode* node = list->first; + /* Datos del primer nodo. */ + void* data = node->data; + /* Pongo como primer nodo al siguiente. */ + list->first = node->next; + /* Si era el único actualizo los otros punteros. */ + if (!list->first) { + list->last = NULL; + list->current = NULL; + } + /* Libero memoria del nodo. */ + free(node); + return data; +} + +void* DLList_pop(DLList* list) { + /* Último nodo */ + DLNode* node = list->last; + /* Datos del último nodo. */ + void* data = node->data; + /* Pongo como último nodo al anterior. */ + list->last = node->prev; + /* Si era el único actualizo los otros punteros. */ + if (!list->last) { + list->first = NULL; + list->current = NULL; + } + /* Libero memoria del nodo. */ + free(node); + return data; +} + diff --git a/dllist.h b/dllist.h new file mode 100644 index 0000000..dc26214 --- /dev/null +++ b/dllist.h @@ -0,0 +1,179 @@ +/* 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 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 19:59:12 ART 2003 + * + * $Id$ + */ + +#ifndef DLLIST_H +#define DLLIST_H + + +/** Tipo de dato booleano. */ +typedef enum { + FALSE, /**< Falso. */ + TRUE /**< Verdadero. */ +} bool; + +/** Nodo de la lista doblemente enlazada. */ +typedef struct DLNodeStruct DLNode; + +/** Nodo de la lista doblemente enlazada. */ +struct DLNodeStruct { + /** Puntero al nodo anterior. */ + DLNode* prev; + /** Datos almacenados en el nodo. */ + void* data; + /** Puntero al próximo nodo. */ + DLNode* next; +}; + +/** Lista doblemente enlazada. */ +typedef struct DLListStruct DLList; + +/** Lista doblemente enlazada. */ +struct DLListStruct { + /** Puntero al primer nodo. */ + DLNode* first; + /** Puntero al nodo actual. */ + DLNode* current; + /** Puntero al último nodo. */ + DLNode* last; +}; + +/** + * Inicializa la DLList. + * Se crea (alocando memoria) e inicializa la DLList. + * + * \param list DLList a inicializar. + * + * \return TRUE si se inicializó bien, FALSE si hay error. + * \post Se crea una nueva DLList, reservando una porción de memoria. + */ +bool DLList_init(DLList* list); + +/** + * Indica si la DLList está vacía. + * + * \param list DLList a verificar. + * + * \return TRUE si está vacía, FALSE si no. + * \pre La DLList debe estar \ref DLList_init "inicializada". + */ +bool DLList_empty(DLList* list); + +/** + * Reinicia la DLList devolviendo el primer elemento. + * Hace que el elemento actual de la DLList vuelva a ser el primero. + * Siempre que se quiera recorrer la DLList debería usarse esta función + * primero. Por ejemplo: + * \code + * DLList* list; + * NodeType* node; + * ... + * for (node = DLList_reset(list); node; node = DLList_next(list)) { + * printf("Uso el elemento actual aquí.\\n"); + * } + * \endcode + * + * \param list DLList de la cual obtener el siguiente elemento. + * + * \return Puntero al primer elemento o NULL si está vacía. + * \see DLList_current() + * \see DLList_next() + * \pre La DLList debe estar \ref DLList_init "inicializada". + */ +void* DLList_reset(DLList* list); + +/** + * Obtiene el elemento actual de la DLList. + * + * \param list DLList de la cual obtener el elemento actual. + * + * \return Elemento actual o NULL si se terminó de recorrer o está vacía. + * \see DLList_reset() + * \see DLList_next() + * \pre La DLList debe estar \ref DLList_init "inicializada". + */ +void* DLList_current(DLList* list); + +/** + * Obtiene el próximo elemento de la DLList. + * + * \param list DLList de la cual obtener el siguiente elemento. + * + * \return Puntero al próximo elemento o NULL si es el último. + * \see DLList_reset() + * \see DLList_current() + * \pre La DLList debe estar \ref DLList_init "inicializada". + */ +void* DLList_next(DLList* list); + +/** + * Agrega un elemento al inicio de la DLList. + * + * \param list DLList a la cual agregar el elemento. + * \param data Elemento a agregar. + * + * \return TRUE si se agregó, FALSE si no hay más memoria. + * \see DLList_push() + * \see DLList_pop() + * \see DLList_unshift() + * \pre La DLList debe estar \ref DLList_init "inicializada". + */ +bool DLList_unshift(DLList* list, void* data); + +/** + * Agrega un elemento al final de la DLList. + * + * \param list DLList a la cual agregar el elemento. + * \param data Elemento a agregar. + * + * \return TRUE si se agregó, FALSE si no hay más memoria. + * \see DLList_pop() + * \see DLList_shift() + * \see DLList_unshift() + * \pre La DLList debe estar \ref DLList_init "inicializada". + */ +bool DLList_push(DLList* list, void* data); + +/** + * Saca el primer elemento de la DLList. + * Elimina el primer elemento de la DLList devolviendo su contenido. + * + * \param list DLList de la cual sacar el elemento. + * + * \return Primer elemento de la DLList. + * \see DLList_push() + * \see DLList_shift() + * \see DLList_unshift() + * \pre La DLList debe estar \ref DLList_init "inicializada" y no + * \ref DLList_empty "vacía". + */ +void* DLList_shift(DLList* list); + +/** + * Saca el último elemento de la DLList. + * Elimina el último elemento de la DLList devolviendo su contenido. + * + * \param list DLList de la cual sacar el elemento. + * + * \return último elemento de la DLList. + * \see DLList_push() + * \see DLList_shift() + * \see DLList_unshift() + * \pre La DLList debe estar \ref DLList_init "inicializada" y no + * \ref DLList_empty "vacía". + */ +void* DLList_pop(DLList* list); + +#endif /* DLLIST_H */