Podemos acceder a cualquier posición dentro de la lista.
Podemos insertar y borrar elementos de cualquier posición.
Pueden ser concatenadas o divididas (sublistas ).
Una lista se suele representar como una sucesión de elementos
separados por comas: a1,a2,...,an:n>=0.
Listas
Matemáticamente una lista es una secuencia de cero o más
elementos.
Si tiene 0 elementos se llama lista vacía.
a1 es el primer elemento (cabeza ) y an el último (cola
).
Decimos que ai precede a ai+1 y ai sucede a ai−1 y
que ai ocupa la posición i-ésima.
Listas. Operaciones básicas
Insert (L, x, i) : añade el elemento x a la lista L en la
posición i. Implica reorganizar los elementos de la lista.
Append (L, x) : añade el elemento x al final de la lista
L. Si se ha podido hacer devuelve el valor booleano true y si
no false.
Retrieve (L, i) : Devuelve el elemento en la posición iésima o
null si no existe.
Listas. Operaciones básicas
Delete (L, i) : Elimina el elemento de la posición iésima. Si
se ha podido hacer devuelve el valor booleano true y si no
false. Implica reorganizar los elementos de la lista.
Length (L) : Devuelve |L|, la longitud de L.
Reset (L) : Hace que la posición actual sea igual la cabeza de
la lista y devuelve el valor 1, si la lista está vacía devuelve 0.
Listas. Operaciones básicas
Current (L) : Devuelve la posición actual en la lista L.
Next (L) : Incrementa y devuelve la posición actual en la lista
L.
Listas. Implementación
Aprovechamos el uso de un LOO como es C++.
Usaremos todos los términos en inglés.
Listas. Implementación
Cada TAD será una clase, p.e.:
typedefcharElement; // Hasta que veamos genericidad// usaremos estos typedef.typedefintPosition;
classList {
public:
voidinsert (Elementx, Positioni); // Dónde está el primer// parámetro 'L'?
...
};
Listl;
l.insert ('a', 1);
Listas. Implementación
Diversas opciones para la representación interna.
Puede ser un vector (array ).
Puede ser una serie de elementos en la cual cada uno sabe sólo
cuál es su siguiente (simplemente enlazada ):
Figura 1: Lista simplemente enlazada.
Listas. Implementación
O también su anterior (doblemente enlazada ):
Figura 2: Lista doblemente enlazada.
Pilas
Una pila es un tipo especial de lista.
Sigue unas normas estrictas en lo referente a la inserción y
extracción de elementos.
Es una estructura LIFO (Last In, First Out ).
Pilas. Operaciones básicas
Push (S, x) : Inserta x en S.
Top (S) : Devuelve el último dato insertado en S
(cabeza). Aplicada sobre una pila vacía lanzará una excepción de
tipo EmptyStackException.
Pilas. Operaciones básicas
Pop (S) : Elimina el último dato insertado en S (cabeza). En la
práctica lo devuelve antes de eliminarlo. Aplicada sobre una pila
vacía lanzará una excepción de tipo EmptyStackException.
Empty (S) : Devuelve true si la pila no tiene elementos.
Ejemplo, apilamos A, B, C y desapilamos.
Figura 3: Apilar.
Pilas. Implementación
Hemos dicho que son una Lista pero con ciertas restricciones.
Podemos aprovechar el concepto de herencia de la POO.
¿Sería válida esta implementación de la clase Pila?:
Este contenido no es la bibliografía completa de la asignatura, por lo tanto debes estudiar, aclarar y ampliar los conceptos que en ellas encuentres empleando los enlaces web y bibliografía recomendada que puedes consultar en la página web de la ficha de la asignatura y en la web propia de la asignatura.