Tema 3 - Listas

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.

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
  

  // 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
  

  // 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
  

  // 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
  

  // 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); } }

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
  

  // 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; }

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.

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 **.