From 745520d79002f4380743f3a063202a387cc465fc Mon Sep 17 00:00:00 2001 From: Leandro Lucarella Date: Sun, 31 Aug 2003 19:27:53 +0000 Subject: [PATCH] =?utf8?q?Primera=20versi=C3=B3n=20moderadamente=20probada?= =?utf8?q?=20de=20la=20lista.?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- dllist.c | 66 ++++++++++++++++++++++++++++------ dllist.h | 108 ++++++++++++++++++++++++++++++++++++------------------- 2 files changed, 126 insertions(+), 48 deletions(-) diff --git a/dllist.c b/dllist.c index ed2b62c..629f7f5 100644 --- a/dllist.c +++ b/dllist.c @@ -1,4 +1,4 @@ -/* vim: set et sts=4 sw=4 fdm=indent fdl=1 fdn=1 fo+=t tw=80: +/* vim: set et sts=4 sw=4 fdm=indent fdl=1 fdn=0 fo+=t tw=80: * * Taller de Programación (75.42). * @@ -18,36 +18,70 @@ #include bool DLList_init(DLList* list) { - list = (DLList*)malloc(sizeof(DLList)); + /* Aloco memoria para la lista. */ + /*list = (DLList*)malloc(sizeof(DLList));*/ + /* Si la obtuve, inicializo todo a NULL y devuelvo TRUE. */ if (list) { list->first = NULL; list->current = NULL; list->last = NULL; + return TRUE; + /* Si no hay más memoria devuelvo FALSE. */ + } else { + return FALSE; } - return list ? TRUE : FALSE; } bool DLList_empty(DLList* list) { return list->first == NULL; } -void* DLList_reset(DLList* list) { +void* DLList_begin(DLList* list) { list->current = list->first; + /* Si hay un nodo, devulevo sus datos, si no NULL. */ return list->current ? list->current->data : NULL; } +void* DLList_end(DLList* list) { + list->current = list->last; + /* Si hay un nodo, devulevo sus datos, si no NULL. */ + return list->current ? list->current->data : NULL; +} + +bool DLList_have_more(DLList* list) { + return list->current != 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; + DLNode* current = list->current; + /* Si no está vacía ni ya fue terminada de recorrer. */ + if (current) { + /* Apuntamos el actual al próximo. */ + list->current = current->next; + /* Devolvemos los datos del próximo o NULL si no había otro. */ return list->current ? list->current->data : NULL; + /* Si está vacía o ya fue terminada de recorrer devolvemos NULL. */ + } else { + return NULL; + } +} + +void* DLList_prev(DLList* list) { + DLNode* current = list->current; + /* Si no está vacía ni ya fue terminada de recorrer. */ + if (current) { + /* Apuntamos el actual al anterior. */ + list->current = current->prev; + /* Devolvemos los datos del anterior o NULL si no había otro. */ + return list->current ? list->current->data : NULL; + /* Si está vacía o ya fue terminada de recorrer devolvemos NULL. */ + } else { + return NULL; } - return NULL; } bool DLList_unshift(DLList* list, void* data) { @@ -58,10 +92,11 @@ bool DLList_unshift(DLList* list, void* data) { node->prev = NULL; node->data = data; node->next = list->first; + /* Apunto el nodo actual al nuevo nodo. */ + list->current = node; /* 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 { @@ -82,10 +117,11 @@ bool DLList_push(DLList* list, void* data) { node->prev = list->last; node->data = data; node->next = NULL; + /* Apunto el nodo actual al nuevo nodo. */ + list->current = node; /* 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 { @@ -105,6 +141,10 @@ void* DLList_shift(DLList* list) { void* data = node->data; /* Pongo como primer nodo al siguiente. */ list->first = node->next; + /* Pongo el nodo anterior al primero como NULL. */ + list->first->prev = NULL; + /* Lo pongo como nodo actual. */ + list->current = list->first; /* Si era el único actualizo los otros punteros. */ if (!list->first) { list->last = NULL; @@ -122,6 +162,10 @@ void* DLList_pop(DLList* list) { void* data = node->data; /* Pongo como último nodo al anterior. */ list->last = node->prev; + /* Pongo el nodo siguiente al último como NULL. */ + list->last->next = NULL; + /* Lo pongo como nodo actual. */ + list->current = list->last; /* Si era el único actualizo los otros punteros. */ if (!list->last) { list->first = NULL; diff --git a/dllist.h b/dllist.h index dc26214..d9ad1f7 100644 --- a/dllist.h +++ b/dllist.h @@ -38,26 +38,21 @@ struct DLNodeStruct { }; /** Lista doblemente enlazada. */ -typedef struct DLListStruct DLList; - -/** Lista doblemente enlazada. */ -struct DLListStruct { +typedef struct { /** Puntero al primer nodo. */ DLNode* first; /** Puntero al nodo actual. */ DLNode* current; /** Puntero al último nodo. */ DLNode* last; -}; +} DLList; /** * 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); @@ -72,27 +67,61 @@ bool DLList_init(DLList* list); 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: + * Apunta al primer elemento de la DLList devolviendolo. + * Hace que el elemento actual de la DLList sea el primero y devuelve su valor. + * Si está vacía, devuelve NULL. + * Siempre que se quiera recorrer la DLList de izquierda a derecha debería + * usarse esta función primero. Por ejemplo: * \code - * DLList* list; - * NodeType* node; + * DLList* l; + * char* data; * ... - * for (node = DLList_reset(list); node; node = DLList_next(list)) { - * printf("Uso el elemento actual aquí.\\n"); + * for (data = DLList_begin(l); DLList_have_more(l); data = DLList_next(l)) { + * printf("El elemento actual es '%s'.\\n", data); * } * \endcode * - * \param list DLList de la cual obtener el siguiente elemento. + * \param list DLList de la cual obtener el primer elemento. + * + * \return Primer elemento o NULL si está vacía. + * \see DLList_have_more(), DLList_next(), DLList_end(), DLList_prev() + * \pre La DLList debe estar \ref DLList_init "inicializada". + */ +void* DLList_begin(DLList* list); + +/** + * Apunta al último elemento de la DLList devolviendolo. + * Hace que el elemento actual de la DLList sea el último y devuelve su valor. + * Si está vacía, devuelve NULL. + * Siempre que se quiera recorrer la DLList de derecha a izquierda debería + * usarse esta función primero. Por ejemplo: + * \code + * DLList* l; + * char* data; + * ... + * for (data = DLList_end(l); DLList_have_more(l); data = DLList_prev(l)) { + * printf("El elemento actual es '%s'.\\n", data); + * } + * \endcode + * + * \param list DLList de la cual obtener el último elemento. * - * \return Puntero al primer elemento o NULL si está vacía. - * \see DLList_current() - * \see DLList_next() + * \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_init "inicializada". */ -void* DLList_reset(DLList* list); +void* DLList_end(DLList* list); + +/** + * Indica si se puede obtener otro elemento de la lista en una iteración. + * + * \param list DLList a verificar. + * + * \return TRUE si se puede obtener otro elemento, FALSE si no. + * \see DLList_begin(), DLList_end(), DLList_prev(), DLList_next() + * \pre La DLList debe estar \ref DLList_init "inicializada". + */ +bool DLList_have_more(DLList* list); /** * Obtiene el elemento actual de la DLList. @@ -100,8 +129,7 @@ void* DLList_reset(DLList* list); * \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() + * \see DLList_prev(), DLList_next(), DLList_have_more() * \pre La DLList debe estar \ref DLList_init "inicializada". */ void* DLList_current(DLList* list); @@ -111,13 +139,23 @@ void* DLList_current(DLList* list); * * \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() + * \return Siguiente elemento o NULL si es el último. + * \see DLList_begin(), DLList_have_more(), DLList_current(), DLList_prev() * \pre La DLList debe estar \ref DLList_init "inicializada". */ void* DLList_next(DLList* list); +/** + * Obtiene el elemento anterior de la DLList. + * + * \param list DLList de la cual obtener el elemento anterior. + * + * \return Elemento anterior o NULL si es el primero. + * \see DLList_begin(), DLList_have_more(), DLList_current(), DLList_next() + * \pre La DLList debe estar \ref DLList_init "inicializada". + */ +void* DLList_prev(DLList* list); + /** * Agrega un elemento al inicio de la DLList. * @@ -125,10 +163,9 @@ void* DLList_next(DLList* list); * \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() + * \see DLList_push(), DLList_pop(), DLList_unshift() * \pre La DLList debe estar \ref DLList_init "inicializada". + * \post El puntero interno de la DLList apunta al nuevo elemento. */ bool DLList_unshift(DLList* list, void* data); @@ -139,10 +176,9 @@ bool DLList_unshift(DLList* list, void* data); * \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() + * \see DLList_pop(), DLList_shift(), DLList_unshift() * \pre La DLList debe estar \ref DLList_init "inicializada". + * \post El puntero interno de la DLList apunta al nuevo elemento. */ bool DLList_push(DLList* list, void* data); @@ -153,11 +189,10 @@ bool DLList_push(DLList* list, void* data); * \param list DLList de la cual sacar el elemento. * * \return Primer elemento de la DLList. - * \see DLList_push() - * \see DLList_shift() - * \see DLList_unshift() + * \see DLList_push(), DLList_shift(), DLList_unshift() * \pre La DLList debe estar \ref DLList_init "inicializada" y no * \ref DLList_empty "vacía". + * \post El puntero interno de la DLList apunta primer elemento. */ void* DLList_shift(DLList* list); @@ -168,11 +203,10 @@ void* DLList_shift(DLList* list); * \param list DLList de la cual sacar el elemento. * * \return último elemento de la DLList. - * \see DLList_push() - * \see DLList_shift() - * \see DLList_unshift() + * \see DLList_push(), DLList_shift(), DLList_unshift() * \pre La DLList debe estar \ref DLList_init "inicializada" y no * \ref DLList_empty "vacía". + * \post El puntero interno de la DLList apunta último elemento. */ void* DLList_pop(DLList* list); -- 2.43.0