Pro2324 Help

Tema 3 - Listas

TAD Lista

Una lista es por definición un conjunto de cero o más elementos.

Los elementos están ordenados de forma lineal, no por su contenido, sino simplemente por la posición que ocupan relativos unos a otros.

TAD Lista enlazada simple
NODO 3
NODO 2
NODO 1
INFORMACIÓN
SIGUIENTE
INFORMACIÓN
SIGUIENTE
INFORMACIÓN
SIGUIENTE
LISTA
NULL
TAD Lista enlazada simple

Por lo tanto, la lista está formada por nodos idénticos. Cada nodo está formado por dos elementos, la información del propio nodo y un puntero que apunta al siguiente. Además, el inicio de la lista está delimitado por un puntero Lista, y finaliza con el último nodo que apunta a NULL.

Operaciones

Siguiendo los pasos para la especificación de un TAD, definimos las operaciones del mismo clasificándolas en: constructoras, generadoras, modificadoras, observadoras y destructoras.

Generadoras


  • Objetivo: Crear una lista vacía y la inicializa
    Salida: Una lista vacía
    Poscondición: La lista sin datos

    LISTA
    NULL
    // SPDX-FileCopyrightText: 2024 Eliana Reigada // // SPDX-License-Identifier: GPL-3.0-only void createEmptyList(tList *lista) { lista->indice = LNULL; }

  • Objetivo: Si la posición es nula, añade un elemento al final de la lista. En caso contrario, el elemento quedará insertado justo antes del que actualmente ocupa la posición indicada.
    Entrada:
    - Item: Contenido del elemento a insertar
    - Position: Posición de referencia para la inserción
    - List: Lista donde vamos a insertar
    Salida: List: Lista con el elemento Item insertado y verdadero si se ha podido insertar, falso en caso contrario
    Precondición: Position es una posición válida de la lista o es una posición nula
    Postcondición: Las posiciones de los elementos de la lista posteriores a la del elemento insertado pueden haber variado

    NODO 2
    NODO 1
    INFORMACIÓN
    SIGUIENTE
    INFORMACIÓN
    SIGUIENTE
    LISTA
    NULL
    NODO 2
    NUEVO NODO
    NODO 1
    INFORMACIÓN
    SIGUIENTE
    INFORMACIÓN
    SIGUIENTE
    INFORMACIÓN
    SIGUIENTE
    LISTA
    NULL
    // SPDX-FileCopyrightText: 2023 Fernando Álvarez // // SPDX-License-Identifier: GPL-3.0-only bool insertItem(tItemL item, tPosL pos, tList *lista) { tPosL posAux; if (!createNode(&posAux)) { return false; } else { posAux->data = item; posAux->next = LNULL; //por si acaso } if (isEmptyList(*lista)) { *lista = posAux; } else if (pos == LNULL) { last(*lista)->next = posAux; } else if (pos == *lista) { posAux->next = pos; *lista = posAux; } else { posAux->next = pos->next; pos->next = posAux; posAux->data = pos->data; pos->data = item; } return true; }

Modificadores


  • Objetivo: Copia una lista en otra
    Entrada: List_1: Lista que vamos a copiar
    Salida: List_2: Copia de la lista original y verdadero si se ha podido copiar, falso en caso contrario
    Precondición: La lista origen está inicializada

    LISTA 1
    NODO1
    NODO2
    NULL
    LISTA 2
    X
    LISTA 1
    NODO 1
    NODO 2
    NULL
    LISTA 2
    NUEVO NODO
    copiar
    LISTA 1
    NODO 1
    NODO 2
    NULL
    LISTA 2
    NODO 1
    copiar
    LISTA 1
    NODO 1
    NODO 2
    NULL
    LISTA 2
    NODO 1
    NUEVO NODO
    LISTA 1
    NODO 1
    NODO 2
    NULL
    LISTA 2
    NODO 1
    NODO 2
    // SPDX-FileCopyrightText: 2024 Eliana Reigada // // SPDX-License-Identifier: GPL-3.0-only bool copyList(tlist listaDest, tList *listaOrig) { tPosl p, q, r; bool ret = true; createEmptyList(listaOrig); if (!isEmptyList(listaDest)) { p = listaDest; while ((p != LNULL) && createNode(&r)) { r->data = p->data; r->next = LNULL; if (p == listaDest) { *listaOrig = r; q = r; } else { q->next = r; q = r; } p = p->next; } if (p != LNULL) { deleteList(listaOrig); ret = false; } } return ret; }

  • Objetivo: Modifica el contenido de un elemento de la lista
    Entrada:
    - Item: Nuevo contenido a asignar al elemento en Position
    - Position: Posición del elemento que queremos modificar
    - List: Lista a modificar
    Salida: List: Lista con el contenido del elemento modificado
    Precondición: Position es una posición válida de la lista

    _
    NODO 2
    NODO A MODIFICAR
    NODO 1
    NUEVA INFORMACIÓN
    POSICIÓN A MODIFICAR
    INFORMACIÓN
    SIGUIENTE
    INFORMACIÓN ANTIGUA
    SIGUIENTE
    INFORMACIÓN
    SIGUIENTE
    LISTA
    NULL
    // SPDX-FileCopyrightText: 2024 Eliana Reigada // // SPDX-License-Identifier: GPL-3.0-only void updateItem(tItem item, tPosL pos, tList *lista) { pos->data = item; }

Destructoras


  • Objetivo: Elimina de la lista un elemento con cierta posición
    Entrada: Position: Posición del elemento a eliminar List: Lista a modificar Salida: List: Lista sin el elemento correspondiente a Position
    Precondición: Position es una posición válida de la lista
    Postcondición: Las posiciones de los elementos de la lista posteriores a la de la posición eliminada pueden haber variado

    NODO 2
    NODO A ELIMINAR
    NODO 1
    INFORMACIÓN
    SIGUIENTE
    INFORMACIÓN
    SIGUIENTE
    INFORMACIÓN
    SIGUIENTE
    LISTA
    NULL
    NODO 2
    NODO 1
    INFORMACIÓN
    SIGUIENTE
    INFORMACIÓN
    SIGUIENTE
    LISTA
    NULL
    // SPDX-FileCopyrightText: 2024 Eliana Reigada // // SPDX-License-Identifier: GPL-3.0-only void deleteAtPosition(tPosL pos, tList *lista) { tPosl posAux; if (pos == *lista) *lista = (*lista)->next; else { for (posAux = *lista; posAux->next != pos; posAux = posAux->next); posAux->next = pos->next; } free(pos); }

  • Objetivo: Elimina todos los elementos de la lista
    Entrada: List: Lista a borrar
    Salida: Lista vacía

    NODO 3
    NODO 2
    NODO 1
    INFORMACIÓN
    SIGUIENTE
    INFORMACIÓN
    SIGUIENTE
    INFORMACIÓN
    SIGUIENTE
    LISTA
    NULL
    FREE ()
    NODO 2
    NODO 1
    INFORMACIÓN
    SIGUIENTE
    INFORMACIÓN
    SIGUIENTE
    LISTA
    ANTIGUA DIRECCIÓN DE NODO 3
    NULL
    FREE ()
    NODO 1
    INFORMACIÓN
    SIGUIENTE
    LISTA
    ANTIGUA DIRECCIÓN DE NODO 2
    NULL
    FREE ()
    LISTA
    NULL
    // SPDX-FileCopyrightText: 2024 Eliana Reigada // // SPDX-License-Identifier: GPL-3.0-only void deleteList(tList *lista) { tPosL posAux; while (*lista != LNULL) { while (posAux->next != NULL) posAux = posAux->next; free(posAux); } }

Observadoras


  • Objetivo: Busca el primer elemento con cierto contenido en la lista
    Entrada:
    - Item: Contenido del elemento buscado
    - List: Lista donde realizar la búsqueda
    Salida: Position: Posición del elemento encontrado o nulo si no se encuentra

    NODO 3
    NODO 2
    NODO 1
    NO
    USUARIO 3
    SIGUIENTE
    USUARIO 2
    SIGUIENTE
    USUARIO 1
    SIGUIENTE
    LISTA
    NULL
    ¿ERES EL USUARIO3?
    NODO 3
    NODO 2
    NODO 1
    NO
    USUARIO 3
    SIGUIENTE
    USUARIO 2
    SIGUIENTE
    USUARIO 1
    SIGUIENTE
    LISTA
    NULL
    ¿ERES EL USUARIO3?
    NODO 3
    NODO 2
    NODO 1
    SI
    USUARIO 3
    SIGUIENTE
    USUARIO 2
    SIGUIENTE
    USUARIO 1
    SIGUIENTE
    LISTA
    NULL
    ¿ERES EL USUARIO3?
    // SPDX-FileCopyrightText: 2024 Eliana Reigada // // SPDX-License-Identifier: GPL-3.0-only tPosL findItem(tItem item, tList lista) { tPosL posAux; for (posAux = lista; (posAux != LNULL) && (posAux->data != item); posAux = posAux->next); return posAux; }

  • Objetivo: Determina si la lista está vacía
    Entrada: List: Lista a comprobar
    Salida: Verdadero si la lista está vacía, falso en caso contrario

    // SPDX-FileCopyrightText: 2024 Eliana Reigada // // SPDX-License-Identifier: GPL-3.0-only bool isEmptyList(tLIst lista) { return lista == LNULL; }

  • Objetivo: Recupera el contenido de un elemento de la lista
    Entrada: Position: Posición del elemento buscado
    List: Lista donde realizar la búsqueda
    Salida: Item: Contenido del elemento que está en Position
    Precondición: Position es una posición válida en la lista

    // SPDX-FileCopyrightText: 2024 Eliana Reigada // // SPDX-License-Identifier: GPL-3.0-only tItem getItem(tPosL pos, tList lista) { return pos->data; }

  • Objetivo: Devuelve la posición del primer elemento de la lista
    Entrada: List: Lista a manipular
    Salida: Position: Posición del primer elemento
    Precondición: La lista no está vacía

    // SPDX-FileCopyrightText: 2024 Eliana Reigada // // SPDX-License-Identifier: GPL-3.0-only tPosL first(tList lista) { return lista; }

  • Objetivo: Devuelve la posición del último elemento de la lista
    Entrada: List: Lista a manipular
    Salida: Position: Posición del último elemento
    Precondición: La lista no está vacía

    // SPDX-FileCopyrightText: 2024 Eliana Reigada // // SPDX-License-Identifier: GPL-3.0-only tPosL last(tList lista) { tPosL posAux; for (posAux = lista; posAux->next != LNULL; posAux->next); return posAux; }

  • Objetivo: Devuelve la posición del elemento anterior al actual
    Entrada: Position: Posición del elemento actual
    List: Lista a manipular
    Salida: Posición del elemento anterior o nulo si es el primero
    Precondición: Position es una posición válida de la lista

    // SPDX-FileCopyrightText: 2024 Eliana Reigada // // SPDX-License-Identifier: GPL-3.0-only tPosL previous(tPosL pos, tList L) { tPosL posAux; for (posAux = L; posAux->next != pos; posAux = posAux->next); return posAux; }

  • Objetivo: Devuelve la posición del elemento siguiente al actual
    Entrada:
    - Position: Posición del elemento actual
    - List: Lista a manipular
    Salida: Position: Posición del elemento siguiente o nulo si es el último
    Precondición: Position es una posición válida de la lista

    // SPDX-FileCopyrightText: 2024 Eliana Reigada // // SPDX-License-Identifier: GPL-3.0-only tPosL next(tPosL pos, tList lista) { return pos->next; }

TAD Lista ordenada

Los elementos están ordenados de forma lineal por su contenido.

En caso de ordenación alfabética:

TAD Lista ordenada enlazada simple
NODO 3
NODO 2
NODO 1
CCCC
SIGUIENTE
BBBB
SIGUIENTE
AAAA
SIGUIENTE
LISTA
NULL
TAD Lista ordenada enlazada simple

Operación a cambiar

Las operaciones del TAD lista ordenada es idéntico al TAD anterior, la única a modificar es la operación de inserción:


  • Objetivo: Inserta un elemento en la lista según el criterio de ordenación sobre el campo Item
    Entrada:
    - Item: Contenido del elemento a insertar
    - List: Lista donde vamos a insertar
    Salida: List: Lista con el elemento Item insertado en la posición correspondiente según su contenido y verdadero si se ha podido insertar, falso en caso contrario
    Precondición: La lista está inicializada
    Postcondición: Las posiciones de los elementos de la lista posteriores a la del elemento insertado pueden haber variado

    NODO 3
    NUEVO 2
    NODO 1
    NUEVO NODO
    CCC
    SIGUIENTE
    DDD
    SIGUIENTE
    BBB
    SIGUIENTE
    AAA
    SIGUIENTE
    LISTA
    NULL
    NUEVO NODO
    NODO 3
    NUEVO 2
    NODO 1
    CCC
    SIGUIENTE
    DDD
    SIGUIENTE
    BBB
    SIGUIENTE
    AAA
    SIGUIENTE
    LISTA
    NULL
    // SPDX-FileCopyrightText: 2023 Fernando Álvarez // // SPDX-License-Identifier: GPL-3.0-only bool insertItem(tItemL item, tList *lista) { tPosL q,p; if (!createNode(&q)) { return false; } else { q->data = item; q->next = LNULL; //por si acaso } if (isEmptyList(*lista)) { *lista = q; } else if(item < (*lista)->data){ q->next = *lista; *lista = q; } else{ p = findPosition(*lista,item); q->next = p->next; p->next = q; } return true; }

Comparación entre TADs

Estática

Simple Enlace

Doble Enlace

Necesidad de memoria

Mucha

Menos en promedio

Menos en promedio (+ que simple enlace)

Memoria contigua

Acceso directo

Ampliable

Operaciones más costosas

insertItem, deleteAtPosition (excepto al final)

insertItem (final), deleteAtPosition (final), previous, last, deleteList, copyList

insertItem (final), last, deleteList, copyList

Seguridad

⚔️😡🛡️

😴🛡️

😴🛡️

Archivo de Cabecera TAD

#include <stdbool.h> #define LNULL ...; //Constante que representa posiciones nulas // Se define en funcion del problema typedef ... tItemL; typedef ... tPosL; typedef ... tList; // Generadoras void createEmptyList(tList* L); bool insertItem(tItemL d, tPosL p, tList* L); // Modificadoras bool copyList(tList L, tList* M); void updateItem(tItemL d , tPosL p, tList* L); // Destructoras void deleteAtPosition(tPosL p, tList* L); void deleteList(tList* L); // Observadoras tPosL findItem(tItemL d, tList L); bool isEmptyList(tList L); tItemL getItem(tPosL p, tList L); tPosL first(tList L) ; tPosL last(tList L); tPosL previous(tPosL p, tList L); tPosL next(tPosL p, tList L);

Multilistas

En problemas de programación reales hacen falta soluciones complejas. Es habitual combinar múltiples TAD simples para construir un TAD complejo.

En este caso el TAD multilistas es un ejemplo de combinación de TADs, en este caso, listas.

TAD Multilistas

La multilista consiste, en crear sublistas enlazadas a los nodos de una lista principal.

A una lista de usuarios podríamos enlazar, por ejemplo, una playlist para cada uno.

Multilista.png

TAD Multiordenadas

Esta lista multiordenada consta de dos punteros, uno apunta al primer nodo ordenada por nombre, y el otro al primer DNI.

Los están enlazados entre ellos doblemente. Marcando el nodo anterior y siguiente, en dos categorías: Nombre y **DNI **.

Multiordenada.png
Last modified: 12 May 2024