TDA's

Tema 2
TDA’s Lineales: Listas, Colas, Pilas
Gabriel Navarro

Estructuras de Datos
Grado en Ingenier´ Inform´tica
ıa
a

Gabriel Navarro

Tema 2 TDA’s Lineales: Listas, Colas, Pilas

Resumen

Concepto de lista.
Implementaciones de listas.
Concepto de cola.
Implementaciones de colas.
Concepto de pila.
Implementaciones de pilas.
Aplicaciones.

Gabriel Navarro

Tema 2 TDA’sLineales: Listas, Colas, Pilas

LISTAS

Gabriel Navarro

Tema 2 TDA’s Lineales: Listas, Colas, Pilas

Listas
Definici´n
o
Una lista de elementos de un dominio D es una secuencia indexada
de elementos del dominio. Todo elemento cumple que tiene un
elemento siguiente (menos el elemento denominado ultimo), y un
´
elemento anterior (menos el primer elemento de la lista).
Denominaremos,a su vez, al final de la lista como a la posici´n
o
siguiente a la del ultimo elemento de la misma.
´
Formalmente, una lista de n elementos es una aplicaci´n de los
o
primeros n n´meros naturales en el dominio del problema:
u

L : {1, 2, 3, ..., n} − − > D
Denotaremos la lista como L =< l1 , l2 , ..., li , ..., ln >, donde li es
el elemento i-´simo de la lista.
e
Gabriel NavarroTema 2 TDA’s Lineales: Listas, Colas, Pilas

Listas: Operaciones
Un TDA lista debe permitir realizar las siguientes operaciones:
Construir la lista.
Saber si la lista est´ vac´
a
ıa.
Vaciar la lista.
Saber el n´mero de elementos de la lista.
u
Insertar un elemento en la lista.
Eliminar un elemento de la lista.
Conocer el elemento de una posici´n de la lista.
o
Conocer la posici´nsiguiente de un elemento de la lista.
o
Conocer la posici´n anterior de un elemento de la lista.
o
Conocer la posici´n del primer elemento y del final de la lista.
o
Copiar dos listas.
Gabriel Navarro

Tema 2 TDA’s Lineales: Listas, Colas, Pilas

Listas: Interfaz de la clase
template
class Lista {
public:
Lista();
Lista(const Lista &L);
˜Lista();
bool estaVacia();
void vaciar();int numElem();
void insertar(Posicion p, Elemento elm);
void borrar(Posicion p);
Elemento verElemento(Posicion p);
Posicion siguiente(Posicion p);
Posicion anterior(Posicion p);
Posicion primero();
Posicion final();
Lista & operator=(const Lista &L);
};
Gabriel Navarro

Tema 2 TDA’s Lineales: Listas, Colas, Pilas

Listas: Mejoras en la interfaz

En la especificaci´n de la interfazanterior, vemos que tanto Posicion
o
como Elemento son tipos de datos sin definir.
Elemento depender´ de la plantilla y de la instanciaci´n de la clase
a
o
al usarla.
Posicion depender´ de la implementaci´n de la clase.
a
o
Para facilitar el uso de listas, dado que conceptualmente es muy com´n
u
denotar una posici´n como un entero, se pueden incluir m´todos
o
e
adicionales que tratenla posici´n como tal:
o
void insertarEnIndice(int idx, Elemento elm);
void borrarDelIndice(int idx);
Elemento verElementoDelIndice(int p);

Gabriel Navarro

Tema 2 TDA’s Lineales: Listas, Colas, Pilas

Listas: Mejoras en la interfaz
Una soluci´n mas coherente con la abstracci´n es crear una clase
o
o
Posicion
Interfaz de Posicion
class Posicion {
.... // representaci´n de laclase
o
public:
Posicion();
Posicion( const Posicion & );
~Posicion();
Posicion & operator = (const Posicion & );
Posicion & operator ++ (); // no es necesaria ’siguiente’
Posicion & operator -- (); // no es necesaria ’anterior’
bool operator == (const Posicion & );
bool operator != (const Posicion & );
};

Gabriel Navarro

Tema 2 TDA’s Lineales: Listas, Colas, Pilas

Listas: Ejemplode uso
main(){
Lista l;
for (int i= 0 ; in:
6
Gabriel Navarro

min:
4
Tema 2 TDA’s Lineales: Listas, Colas, Pilas

Redimensionar: Ejemplo de funcionamiento
template
void Lista::RedimensionaLista(int n) {
Elemento *aux;
int min= (this->n < n)? this->n:n;
if ((nn)) return ;
aux = new (nothrow) Elemento [n];
if (!aux) return ;
for (int i=0 ; in= n;
}
RedimensionaLista(4);...