Trav

Estructuras de Datos Avanzadas
Contenido del Tema

T E M A 5

5.1. Introducción 5.2. Pilas 5.3. Colas 5.4. Listas 5.5. Arboles Binarios Arboles Binarios de Búsqueda

Programación Modular

Introducción
Objetivos
• Especificación e Implementación de nuevas estructuras de datos Técnica: Abstracción de Datos • Tipos de Estructuras de Datos: 1) Datos organizados por Posición Pilas , Colasy Listas 2) Datos organizados por Valor Arboles Binarios
Programación Modular
2

Introducción
• Estudio de las Estructuras de Datos: Definición de la Estructura de Datos e identificación de su Conjunto de Operaciones Presentación de Aplicaciones Desarrollo de diversas Implementaciones

Programación Modular

3

Pilas
Definición • Pila: Grupo Ordenado, (de acuerdo al tiempo que llevanen la pila) de Elementos Homogéneos (todos del mismo tipo). • Acceso a la Pila: añadir y eliminar elementos, SÓLO a través de la CABEZA de la Pila • Estructura LIFO (Last Input First Output)

Añadir

Eliminar

Cabeza

Pila

Programación Modular

4

Pilas. Operaciones

INTERFAZ CLASE CPila TIPOS TipoElemento ... // cualquier tipo de datos METODOS // Añade un elemento por la cabezade la pila Apilar( E TipoElemento elem) // Saca un elemento por la cabeza de la Pila Desapilar() // Devuelve el elemento de la cabeza de la Pila TipoElemento Cima()
...

Programación Modular

5

Pilas. Operaciones 2
... // Crea una pila vacía Crear() //Operación lógica que nos dice si una pila está vacía o no B EstáVacía () //Operación lógica que nos dice si una pila está llena o no.//Necesaria en determinadas implementaciones B EstáLlena() // Destruye una pila previamente creada Destruir() FIN CPila

Programación Modular

6

Pilas. Aplicaciones
Aplicaciones • Ejemplo1: Leer una secuencia de caracteres desde teclado e imprimirla al revés • Ejemplo2: Verificar si una cadena de caracteres está balanceada en paréntesis o no abc(defg(ijk))(l(mn)op)qr SI abc(def))ghij(kl)mNO • Ejemplo3: Reconocimiento del Lenguaje, L={W$W´ / W es una cadena de caracteres y W´es su inversa} (Suponemos que $ no está ni en W ni en W´)
Programación Modular
7

Pilas. Ejemplo1
Algoritmo Inverso Tipos TipoElemento = C Variables TipoElemento c CPila pila // Se llama automáticamente al constructor Inicio Leer(c) MIENTRAS c != CHR(13)HACER pila.Apilar(c) Leer(c) FINMIENTRAS MIENTRAS NO(pila.EstáVacía()) HACER c = pila.Cima() pila.Desapilar() Escribir(c) FINMIENTRAS pila.Destruir() Fin

Programación Modular

8

Pilas. Ejemplo2
Algoritmo Balanceo Tipos TipoElemento = C Variables TipoElemento c CPila pila B bien Inicio bien = VERDADERO Leer(c) MIENTRAS HACER (bien Y (c!=CHR(13))) SI c = = ‘)’ ENTONCES SI (!pila.EstáVacía()) ENTONCES pila.Desapilar () SINO bien = FALSOFINSI FINSI FINSI Leer(c) FINMIENTRAS SI bien Y pila .EstáVacía() ENTONCES Escribir(“cadena balanceada “) SINO Escribir(“cadena no balanceada”) FINSI pila.Destruir() Fin

SI c== ‘(’ ENTONCES pila.Apilar(c) SINO

Programación Modular

9

Pilas. Ejemplo3
Algoritmo Lenguaje_L Tipos TipoElemento = $ Variables TipoElemento c1, c2 CPila pila B bien Inicio Leer(c1) MIENTRAS (c1 != ‘$’) HACERpila.Apilar(c1) Leer(c1) FINMIENTRAS Leer(c1) bien = VERDADERO MIENTRAS (bien AND (c1 CHR(13))) HACER SI pila .EstáVacía()ENTONCES bien= FALSO SINO c2 = pila .Cima() pila.Desapilar () SI (c1 != c2) ENTONCES bien = FALSE SINO Leer(c1) FINSI FINSI FINMIENTRAS SI (bien AND pila.EstáVacía())ENTONCES Escribir (“ Si pertenece”) SINO Escribir (“No pertenece”) FINSI pila Destruir() Fin

ProgramaciónModular

10

Pilas. Aplicaciones
• Aplicaciones complejas que se pueden solucionar con pilas: Expresiones Algebraicas Operadores: +, -, *, / Operandos: Letras mayúsculas • Notación Infija: • El operador binario está situado entre sus dos operandos A+ B • Inconveniente: Son necesarias reglas de precedencia y uso de paréntesis para evitar ambigüedades A+B*C

Programación Modular

11

Pilas....