estructuras de datos - lsc.fie.umich.mxlsc.fie.umich.mx/~pedro/ed/data_structuresp.pdf ·...

OutlineIntroduccion

ColaPila

Aplicaciones de colas y pilasEjemplo

Estructuras de Datos

Pedro Chavez Lugo

15 de marzo de 2010

Pedro Chavez Lugo Estructuras de Datos

OutlineIntroduccion

ColaPila


1 Introduccion

2 Cola

3 Pila

4 Aplicaciones de colas y pilas

5 Ejemplo


OutlineIntroduccion

ColaPila


Tipo de Dato Abstracto

Un tipo de dato abstracto (TDA), corresponde a un conjunto devalores y un conjunto de operaciones sobre tales valores.

Ejemplos de TDA

Enteros.

Reales.

Booleanos.

Listas.

etc.


OutlineIntroduccion

ColaPila



Tipos de datos primitivos

La gran mayorıa de los tipos de datos primitivos (int, float, double,etc.) estan definidos en los registros de las actuales arquitecturasde procesador.


OutlineIntroduccion

ColaPila






Los TDA son definidos por el programador.


OutlineIntroduccion

ColaPila






Los TDA son definidos por el programador.TAD = Datos + Operaciones


OutlineIntroduccion

ColaPila


Lista

Lista

La lista es un TDA, que consta de una secuencia de elementosllamados nodo.


OutlineIntroduccion

ColaPila


Lista

Lista


Nodo

Datos (Informacion)


OutlineIntroduccion

ColaPila


Lista

Lista


Nodo

Datos (Informacion)

Enlace o apuntador (Apunta al siguiente nodo)


OutlineIntroduccion

ColaPila


Lista

Lista


Nodo

Datos (Informacion)

Enlace o apuntador (Apunta al siguiente nodo)

Datos Enlace Teléfono Enlace

Nodo

Nombre

Ejemplo

Sexo


OutlineIntroduccion

ColaPila


Nodos enlazados

Los nodos forman una secuencia desde el primer elemento al ultimoelemento. El primer nodo se enlaza al segundo, este se enlaza al tercero,y ası sucesivamente hasta llegar al ultimo nodo, que debe serrepresentado de forma diferente para especificar que este nodo no seenlaza a ningun otro.

Primer nodo Ultimo nodo

Datos Datos nullDatos


OutlineIntroduccion

ColaPila


Nodo

public class Nodo {

int id;

Nodo siguiente;

Nodo()

{

id = 0;

siguiente = null;

}

Nodo(int id)

{

this.id = id;

siguiente = null;

}

}

public static void main(String args[])

{

Nodo cero = new Nodo ();

Nodo uno = new Nodo (1);

Nodo dos = new Nodo (2);

Nodo tres = new Nodo (3);

//enlazamiento

cero.siguiente = uno;

uno.siguiente = dos;

dos.siguiente = tres;

//recorrido de la lista

Nodo aux = cero;

while(aux != null)

{

System.out.println("dato: "+aux.id);

aux = aux.siguiente;

}

}


OutlineIntroduccion

ColaPila


Lista

Una lista consiste de un conjunto de nodos enlazados.


OutlineIntroduccion

ColaPila


Lista


Operaciones sobre listas

Crear una lista vacıa.


OutlineIntroduccion

ColaPila


Lista




Insertar nodo.


OutlineIntroduccion

ColaPila


Lista




Insertar nodo.

Eliminar nodo.


OutlineIntroduccion

ColaPila


Lista




Insertar nodo.

Eliminar nodo.

Buscar nodo.


OutlineIntroduccion

ColaPila


Lista




Insertar nodo.

Eliminar nodo.

Buscar nodo.

Imprimir lista.


OutlineIntroduccion

ColaPila


Lista




Insertar nodo.

Eliminar nodo.

Buscar nodo.

Imprimir lista.

Eliminar lista.


OutlineIntroduccion

ColaPila


Lista

Clasificacion de las listas

Lista simplemente enlazada.


OutlineIntroduccion

ColaPila


Lista



Lista doblemente enlazada.


OutlineIntroduccion

ColaPila


Lista




Lista circular simplemente enlazada.


OutlineIntroduccion

ColaPila


Lista





Lista circular doblemente enlazada.


OutlineIntroduccion

ColaPila


Lista






Lista FIFO (cola) - First-In-First-Out.


OutlineIntroduccion

ColaPila


Lista






Lista FIFO (cola) - First-In-First-Out.

Lista LIFO (pila) - Last-In-First-Out.


OutlineIntroduccion

ColaPila


Lista simplemente enlazada

Fin de listaInicio lista


OutlineIntroduccion

ColaPila


Lista doblemente enlazada


OutlineIntroduccion

ColaPila


Lista circular simplemente enlazada


OutlineIntroduccion

ColaPila


Lista circular doblemente enlazada


OutlineIntroduccion

ColaPila


Cola

Una cola es un tipo de lista FIFO (el primero en entrar es elprimero en salir), tal como la fila de un banco.Operaciones sobre el tipo cola:

Insertar - por la parte final de la cola.

Remover - por la parte inicial de la cola.

Es vacia - pregunta para saber si la cola es vacia.


OutlineIntroduccion

ColaPila


Inicio cola removerFin de cola insertar


OutlineIntroduccion

ColaPila


Pila

Una pila es un tipo de lista LIFO (el ultimo en entrar es el primeroen salir), tal como una pila de planos.Operaciones sobre el tipo pila:

Meter (push) - inserta por el tope.

Sacar (pop) - sacar por el tope.

Es vacia - pregunta para saber si la pila es vacia.


OutlineIntroduccion

ColaPila


tope 2

4

1

3

6

Meter Sacar

Fondo


OutlineIntroduccion

ColaPila


Aplicaciones de colas y pilas

Las pilas y colas son dos casos particulares de lista.

Ambas son empleadas en problemas bien definidos.

Aplicaciones:

Compiladores.

Administracion de memoria, procesos de S.O.

Comunicacion de redes.

etc.


OutlineIntroduccion

ColaPila


Ejemplo

Dada una lista que representa un texto (caracteres consecutivos),cifrar a dicha lista para que no sea legible.Solucion emplear al cifrario de Cesar:

Desplazamiento del alfabeto

Si se tiene una A, esta puede ser desplazada n veces. Si n = 3,entonces a la letra A, le corresponde la letra D.


OutlineIntroduccion

ColaPila


A B C X Y Z

n = 3

AD E F B C


estructuras de datos - lsc.fie.umich.mxlsc.fie.umich.mx/~pedro/ed/data_structuresp.pdf ·...

Documents