El TAD Lista
Las listas
aparecen muchos en la solución computacional de muchos problemas, ya sea para
almacenar objetos de determinada clase y calcular el máximo, mínimo, contar las
ocurrencias de un elemento, etc. La lista será el primer TAD que estudiaremos.
Una
lista se define como una n-tupla de
elementos (donde li es el i-esímo elemento de la lista) ordenados de
forma consecutiva, o sea, el elemento li precede al elemento li+1:
L= ( l1, l2,
… , ln ).
Si
la lista contiene 0 elementos se denomina lista vacía.
El
valor de i representa la posición del elemento en la lista, el orden no
significa que el elemento li sea mayor que el li-1, el
orden lo da la posición en la lista.
Ejemplos:
L = ( 5, 4, 3, 2, 1)
M = ( “María”, “Juan”, “Pedro” )
N = ( (1,2,3), (4,5,6), (7,8,9,10) )
O = ( 5.10, 4.99, 3, 2, “1”, (3,6,9) )
La primera de estas listas esta
formada por números enteros, la lista M por nombres, la tercera esta formada
por otras listas, y la cuarta y última esta formada por elementos de diferentes
tipos (números enteros y reales, cadenas, etc.).
La
cantidad de elementos de una lista se denota como |L|.
Ejemplo:
L = ( 5, 4, 3, 2, 1) |L| = 5
M = ( “María”, “Juan”, “Pedro” ) |M|
= 3
N = ( (1,2,3), (4,5,6), (7,8,9,10) ) |N|
= 3
O = ( 5.10, 4.99, 3, 2, “1”, (3,6,9) ) |O|
= 6
La
expresión () representa a la lista vacía,
La
longitud de la lista vacía es 0.
Ejemplo:
L = ()
|L| = 0
En
muchos problemas se imponen restricciones a los elementos que se pueden
almacenar en una lista, cuando una lista tiene todos sus elementos de un mismo
tipo se dice que ella es homogénea, en caso contrario es heterogénea, lo que significa que en la lista puede haber elementos de diferentes
tipos.
Ejemplo:
L = ( 5, 4, 3, 2, 1)
L es Homogénea, todos los elementos
son
del mismo tipo
O = ( 5.10, 4.99, 3, 2, “1”, (3,6,9) )
O es Heterogénea, se mezclan elementos
de diferentes
Tipos, L1 es real y L5 es una cadena.
Analicemos
ahora una definición formal del TAD
Lista con todas sus operaciones, para ello tomemos en cuenta que la lista
es homogénea:
TDA Lista es
Datos
Una colección ordenada de
elementos del mismo tipo. La llamaremos: l
Operaciones
Constructor
Crea una nueva lista, la crea vacía.
Insertar( Tipo x, Entero i)
Inserta un nuevo elemento x,
en la posición i
de la lista
Adicionar( Tipo x)
Adiciona un elemento
al final de la lista.
Tipo Obtener( Entero i)
Devuelve el elemento
que está en la posición i
de la lista
Eliminar( Entero i)
Elimina el elemento que está
en la posición i de la lista. Los elementos posteriores a partir de la posición
i + 1 pasan a tener la posición anterior inmediata es decir i.
Entero
Longitud( )
Devuelve la cantidad de
elementos de la lista. Si la lista es vacía devuelve el valor cero.
Lógico
Vacía()
Devuelve un valor lógico
verdadero si la lista tiene longitud cero, falso en caso contrario.
FIN
Figura 4: El TAD Lista.
Analicemos
cada una de las operaciones por separado.
Operaciones
del TAD Lista
Insertar(x,i)
Inserta el elemento
x en la posición i, haciendo que los elementos li, li+1, …, ln
pasen a ser los elementos li+1, li+2, …, ln+1;
incrementándose en uno la longitud de la lista. Si la operación no tiene éxito,
se dispara una excepción.
Precondiciones: 1 £ i £
|L| , el valor de i tiene que estar entre 1 y la longitud de la lista,
incluyendo ambos valores.
Poscondiciones: |L| = |Lo|+1[1], al finalizar la longitud de la lista tiene
que haberse
incrementado en 1.
x = Obtener(i), el elemento de la posición
i tiene que ser x
Ejemplo:
L = (1,2,5,7,9,13) |L|
= 6
L.Insertar(3,4)
L = (1,2,5,3,7,9,13) |L|
= 7
L4=3
Adicionar(x)
Adiciona el elemento x en la
cola de la lista, haciendo que la longitud de la lista se incremente en 1. Si
la operación no tiene éxito, se dispara
una excepción.
Precondiciones: No tiene, se puede ejecutar siempre.
Poscondiciones: |L| = |Lo|+1, al finalizar la longitud de la lista tiene
que haberse incrementado en 1.
x = Obtener(Longitud()), el último elemento tiene
que ser x
Ejemplo:
L = (1,2,5,3,7,9,13) |L|
= 7
L.Adicionar(4)
L = (1,2,5,3,7,9,13,4) |L|
= 8
x = L.Obtener(L.Longitud()) x = 4
Obtener(i)
Devuelve el i-ésimo elemento
de la lista (el que se encuentra en la posición i), si la posición i no existe
se dispara una excepción. No se modifica la lista.
Precondiciones: 1 £ i £
|L| , el valor de i tiene que estar entre 1 y la longitud de la lista, incluyendo ambos valores.
Poscondiciones: Lo = L
Ejemplo:
L = (1,2,5,3,7,9,13,4)
x = L.Obtener(7)
x = 13
Eliminar(i)
Elimina el elemento
almacenado en la posición i de la lista, haciendo que los elementos li+1,
li+2,…, ln pasen a ser los elementos li,
li+1, …, ln-1, esta operación disminuye en uno la
longitud de la lista, si la posición no existe se dispara una excepción.
Precondiciones: 1 £ i £
|L| , el valor de i tiene que estar entre 1 y la longitud de la lista,
incluyendo a ambos valores.
Poscondiciones: |L| = |Lo|-1 al finalizar
la longitud de la lista tiene que haberse
incrementado en 1.
Ejemplo:
L = (1,2,5,3,7,9,13,4) |L|
= 8
L.Eliminar(6)
L = (1,2,5,3,7,13,4) |L|
= 7
Longitud()
Devuelve |L|, la longitud de la lista
(cantidad de elementos). No se modifica la lista.
Ejemplo:
L = (1,2,5,3,7,9,13,4)
x = L.Longitud()
x = 8
Vacía()
Devuelve verdadero si la longitud de
la lista es 0. No se modifica la lista.
Ejemplo:
L = (1,2,5,3,7,9,13,4)
vacia = L.Vacia()
vacia = false
L = ()
vacia = L.Vacia()
vacia = true
Otras operaciones
Para la lista pudiéramos pensar en
otras operaciones como:
Cabeza() AdicionarCabeza() AdicionarCola()
Cola() EliminarCabeza() EliminarCola()
Nota: Todas estas
operaciones pueden ser obtenidas combinando la operaciones (llamémosles
básicas) enunciadas anteriormente.
Ejemplo:
L.Cola( ) ≡ L.Obtener(
L.longitud( ) )
Ejercicio
propuesto
Indique cuales son las expresiones para obtener el resto de las
operaciones propuestas del TAD Lista. Comente cada operación y defina las
precondiciones y postcondiciones de ella.
En la Figura 5 se muestra una clase abstracta diseñada
siguiendo la definición de TAD Lista.
El método Vacia() no lo declaramos
abstracto, porque aún sin escoger una estructura de datos podemos ofrecer una
implementación del mismo.
No hay comentarios.:
Publicar un comentario