Post on 11-Jul-2015
TADs Lista, Pilas y Colas.
Eliezer Beriguete Alcantara 12-0708
Estructura de Datos Prof. Rina Familia
La lista enlazada es un TDA que nos permite almacenar datos de una
forma organizada, al igual que los vectores pero, a diferencia de estos,
esta estructura es dinámica, por lo que no tenemos que saber "a priori"
los elementos que puede contener.
TAD Lista
Una lista consiste en una cantidad arbitraria de
elementos ordenados.
Una Lista es, a la vez, un TD (tipo de datos), un TAD (tipo
abstracto de datos) o una ED (estructura De datos).
TAD para modelar Listas
void imprimirLista( Lista lista ) { /*Imprime los elementos de la lista post: se imprimen todos los elementos de la lista l } Lista copiarLista( Lista lst ) { /*copia la lista {pre: lst es una lista} {post: copia la lista lst y crea otra igual} }
Lista ordenadaLista( Lista lst ) { /*ordena los datos de la lista
pre: lst = < x1,…, xn > post: ordenadaLista = ( xi, xi+1)
} Lista insertarDato (int dato ) { /*inserta un dato en la lista
Pre: dato es un entero post: insertarDato es una lista de enteros
}
Lista eliminarDato (int dato, Lista lista ) { /*Elimina un dato de la lista
Pre: dato es un entero post: eliminarDato es una lista de enteros
} int buscarDato (int dato, Lista lista ) { /*busca un dato en la lista
Pre: dato es un entero post: buscarDato es un entero igual a dato si existe en la lista, si no existe en nulo
}
Int localizarDato (int dato, Lista lista ) { /*busca la posicion del dato en la lista
Pre: dato es un entero post: localizarDato es la posicion del dato buscado en la lista
}
TAD Cola: conceptos y especificaciones
Secuencia de elementos de un cierto tipo, dispuestos en una dimensión (tipo lineal de datos)
– Nuevos elementos se añaden al final de la cola (añadir
encolar)
– Los elementos salen o se eliminan, de la cabeza de la cola (eliminar – desencolar)
– Operación de interés: observar el primero de los elementos de la cola (primero)
– Valor especial: cola vacía
– Estructura FIFO (First In, First Out): el orden de salida
debe corresponderse con el orden de llegada
Caracteristicas Los elementos se añaden por el extremo final, y se eliminan por el extremo opuesto: frente
El único elemento observable en todo momento es el primero que fue insertado
Se le suele denominar estructura FIFO (First Input First Output).
colaVacía: -----> cola
encolar: cola elemento -----> cola
parcial desencolar: cola -----> cola
parcial primero: cola -----> elem
esvacía: cola -----> bool
Operaciones
Funciones
creaVacía( sal c:cola) {Post: c=colaVacía} añadir(e/s c:cola; ent e:elemento) {Pre: c=c0} {Post: c=encolar(c0,e)} eliminar( e/s c:cola) {Pre: (c=c0)∧(c0≠colaVacía)} {Post: c=desencolar(c0)} primero(c:cola) devuelve elemento {Pre: (c=c0) ∧(c0≠colaVacía)} {Post: primero(c0)=primero(c0)} esVacía(c:cola) devuelve booleano {Post: esVacía(c)=vacía?(c)}
TAD pila: conceptos y especificaciones
Una pila (stack) es un conjunto de elementos del mismo tipo que solamente puede crecer o decrecer por uno de sus extremos.
– Valor especial: pila vacía
– Operaciones: apilar (añadir elemento), desapilar
(quitar elemento), cima (observar último elemento)
– Comportamiento:
• Cima de pila no vacía es el último elemento apilado
• Apilar añade un elemento “encima” del que estaba en la cima
• Desapilar de pila no vacía elimina el último elemento apilado
• Denominadas también estructuras LIFO (Last In, First Out)
El último elemento agregado se denomina tope (top) y el primero fondo (back).
Operaciones
InicializarPila
Apilar
Desapilar
pilaVacia
Cima
Decapitar
leerPila
imprimirPila
Eliminar
enumElemPila
crearPila: - →→→ Pila
apilar : Pila X Elemento →→→ Pila
desapilar : Pila →→→ Pila
recuperarTope: Pila →→→ Elemento
esVacia: Pila →→→ booleano
destruirPila : Pila →→→ -
Pila crearPila();
void apilar(Pila p, Elemento e);
void desapilar(Pila p);
Elemento recuperarTope(Pila p);
int esVacia(Pila p);
void destruirPila(Pila p);
Aplicaciones
Las pilas tienen muchas aplicaciones en informática. Por ejemplo se usan para: • evaluar expresiones aritméticas • analizar sintaxis • simular procesos recursivos
Referencias
http://www.buenastareas.com/ensayos/Tad-Lista/1996890.html http://webdiis.unizar.es/asignaturas/EDA-Tardes/leccion_10.pdf http://ocw.upm.es/lenguajes-y-sistemas-informaticos/estructuras-de-datos/contenidos/tema2/temaII2_presentacion.pdf http://cupi2.uniandes.edu.co/libros/estructuras_de_datos/index.php?option=com_content&view=article&id=88:23-ejemplos-de-utilizacion-del-tad&catid=59&Itemid=71 http://informatica.utem.cl/~mcast/ESDATOS/TADS/Ttema2.pdf http://www.calcifer.org/documentos/librognome/glib-lists-queues.html