PDF de programación - Estructuras de Datos Avanzadas

Estructuras de Datos

Avanzadas

Contenido del Tema

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

T
E
M
A

5

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

y Listas

Pilas , Colas

2) Datos organizados por Valor

Arboles Binarios

Programación Modular 2

1

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

Añadir

Eliminar

Cabeza

Pila

Programación Modular 4

Definición

• Pila: Grupo Ordenado, (de
acuerdo al tiempo que llevan
en la pila) de Elementos
Homogéneos
del
mismo tipo).

(todos

• 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)

2

Pilas. Operaciones

INTERFAZ CLASE CPila

TipoElemento ... // cualquier tipo de datos

TIPOS

METODOS

// Añade un elemento por la cabeza de 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

3

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
abc(def))ghij(kl)m

SI
NO

• Ejemplo3: Reconocimiento del Lenguaje,

L={W$W´ / W es una cadena de caracteres y Wés su
inversa} (Suponemos que $ no está ni en W ni en W´)

Programación Modular 7

Pilas. Ejemplo1

Algoritmo Inverso
Tipos

TipoElemento = C

Variables

Inicio

TipoElemento c
CPila pila // Se llama automáticamente al constructor

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

4

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

pila.Apilar(c)

SINO

SI c = = ‘)’ ENTONCES

SI (!pila.EstáVacía()) ENTONCES

pila.Desapilar()

SINO

bien = FALSO

FINSI

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

Programación Modular 9

Pilas. Ejemplo3

Algoritmo Lenguaje_L
Tipos

TipoElemento = $

Variables

TipoElemento c1, c2
CPila pila
B bien

Inicio

Leer(c1)
MIENTRAS (c1 != ‘$’) HACER

pila.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

FINSI

Leer(c1)

FINSI

FINMIENTRAS
SI (bien AND pila.EstáVacía())ENTONCES

Escribir (“ Si pertenece”)

Escribir (“No pertenece”)

SINO

FINSI
pila Destruir()
Fin

Programación Modular 10

5

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. Aplicaciones

Notación Prefija

Notación Postfija

antes

de

• El operador binario esta situado
dos

justo
operandos
• Gramática:
<expr_pref>::=<letra>|<operador>

sus
+AB

• El operador binario está situado
sus dos

justo después de
operandos
• Gramática:
<exp_post>::=<letra>|<expr_post>

AB+

<expr_pref><expr_pref>

<exp_post><operador>

<letra> ::=
A| B ....|Z
<operador> ::= + | - | * | /
• Ejemplos:
A+(B*C)
(A+B)*C

+A*BC
*+ABC

<letra> ::=A| B ....|Z
<operador> ::= + | - | * | /
• Ejemplos:
A+(B*C)
(A+B)*C

ABC*+
AB+C*

Programación Modular 12

6

Pilas. Aplicaciones

• Ventaja: Usando expresiones prefijas y postfijas no son

necesarias reglas de precedencia, ni uso de paréntesis.
Las gramáticas que las generan son muy simples, y los
algoritmos que las reconocen y evalúan muy fáciles

• Ejemplo 4: Algoritmo que evalúa una expresión en notación

Postfija
1)Usaremos una pila
2)La expresión postfija se almacenará en un array y será
correcta
3)Los operandores serán: +, -, * y /
4)Los operandos serán letras mayúsculas (a cada una le
podemos asignar un valor)

Programación Modular 13

Pilas. Ejemplo4

Algoritmo B Operando(C c)
Inicio

DEVOLVER (c=='+' O c=='*' O c=='/' O c=='-');

Tipos
C TipoArray[1..20]
Z TipoElemento

Fin Operando
Algoritmo Operador(c:$):Z
Inicio

CASO c SEA

'A' : DEVOLVER(5)
'B' : DEVOLVER(7)
'C' : DEVOLVER(-1)
'D' : DEVOLVER(11)
SINO

DEVOLVER 0

FINCASO

Fin Operando

Programación Modular 14

7

Pilas. Ejemplo4

Algoritmo Z Postfija(E TipoArray exp,

E Z ultimo)

Variables

CPila pila
Z i, op1, op2, result
C c
Inicio

PARA i = 1 HASTA ultimo HACER

c = exp[i]
SI Operador(c) ENTONCES

op2 = pila.Cima()

pila.Desapilar()
op1 = pila.Cima()
pila.Desapilar()

CASO c SEA
‘+’ : pila.Apilar(op1+op2)
‘-’ : pila.Apilar(op1-op2)
‘*’ : pila.Apilar(op1*op2)
‘/’ : pila.Apilar(op1/op2)
FINCASO

SINO

pila.Apilar(Operando(c))

FINSI
FINPARA
result = pila.Cima()
pila.Destruir()
DEVOLVER result

Fin

Programación Modular 15

Pilas. Implementación

Implementación

1) Con un Array
• Array estructura adecuada Elementos Homogéneos
• Elementos almacenados de forma Secuencial

Constantes

MaxPila=100

Tipos
Z TipoElemento
TipoElemento TDatos[1..MaxPila]

Programación Modular 16

8

Pilas. Implementación

Sólo es posible acceder a la Cabeza de la Pila

¿ Cómo es posible conocer la posición de la cabeza?

1) Variable entera “cabeza”

Inconveniente: se ha de pasar
como parámetro adicional a todas las operaciones sobre la
pila

2) Extender el array, en pila[0] almacenaremos el índice del

elemento que ocupa la cabeza actual

Programación Modular 17

Pilas. Implementación

CONSTANTES

Cabeza=0; MaxPila=100;

TIPOS

TipoElemento TDatos[Cabeza..MaxPila]

3

5

3

2

.......

[0] [1] [2] [3]

[99] [100]

Cabeza

Basura

Cabeza

2
3
5

Programación Modular 18

9

Pilas. Implementación

•

Inconveniente: Solo es posible implementar una pila de
ordinales (no de cualquier otro tipo de datos)

• 3) Solución: Registro = cabeza + array de datos

k

Cabeza

5 13
Elementos
1 2

.........

8
k MaxPila

Programación Modular 19

Pilas.Implementación

IMPLEMENTACION CLASE CPila

CONSTANTES

MAXPILA = // Valor adecuado

ATRIBUTOS

Z cabeza
TipoElemento datos[1..MAXPILA]

MÉTODOS

Crear ()
INICIO

cabeza = 0

FIN Crear
Destruir()
INICIO

cabeza=0
FIN Destruir

Programación Modular 20

10

Pilas.Implementación

B EstáVacia ()
INICIO

DEVOLVER (cabeza == 0)

FIN

EstáVacia

B EstáLlena()
INICIO

FIN EstáLlena

DEVOLVER (cabeza == MAXPILA)

Programación Modular 21

Pilas.Implementación

Apilar(E TipoElemento elem)
INICIO // precondición: la pila no ha de estar
llena

cabeza = cabeza + 1
datos[cabeza] = elem

FIN Apilar

Desapilar()
INICIO // precondición: la pila no ha de estar
vacía

cabeza = cabeza - 1

FIN Desapilar

FIN Cima

FIN CPila

TipoElemento Cima()
INICIO // precondición: la pila no ha de estar
vacía

DEVOLVER datos[cabeza]

Programación Modular 22

11

Pilas.Implementación

// Sin precondición. Mete un elemento de la pila si no
está llena
Apilar(E TipoElemento elem;S B llena)
INICIO

llena = EstáLlena()
SI NOT llena ENTONCES
cabeza = cabeza + 1
datos[cabeza] =

elem

FINSI

FIN Apilar

Programación Modular 23

Pilas.Implementación

// Sin precondición. Saca un elemento de la pila si no
está vacía
Desapilar(S B vacia)
INICIO

vacia = EstáVacia()
SI NOT vacia ENTONCES
cabeza = cabeza – 1

FINSI

FIN Desapilar

Programación Modular 24

12

Pilas. Implementación

// Sin precondición. Mira el 1er elemento de la pila si no
está vacía
TipoElemento Cima(S B vacia)
VAR

TipoElemento elem

INICIO

vacia = PilaVacia()
SI NOT vacia ENTONCES
elem=datos[cabeza]

FINSI

// Sin precondición. Devuelve el elemento de la cima de la
// pila si no está vacía. Si está vacía devuelve un valor
// basura

devolver elem;

FIN Cima

Programación Modular 25

Pilas.Implementación

2) Con una Lista Enlazada de Punteros

• Comienzo de una lista enlazada
• Se inserta y se extrae por el inicio de la lista

Cabeza de la Pila

cabeza

10

8

10
8

Programación Modular 26

13

Pilas. Implementación

IMPLEMENTACION CLASE CPila

TIPOS

REGISTRO NodoPila

TipoElemento dato
NodoPila *sig

FINREGISTRO

ATRIBUTOS

NodoPila *cabeza

METODOS

Crear ()
INICIO

cabeza = NULO

FIN Crear
B EstáVacia ()
INICIO

DEVOLVER (cabeza == NULO)

Fin EstáVacía

Programación Modular 27

Pilas.Implementación

Apilar (E TipoElemento elem)
VAR

NodoPila *nuevonodo

INICIO

Asignar(nuevonodo)
nuevonodo->dato = elem
nuevonodo->sig = cabeza
cabeza = nuevonodo

FIN Apilar

Programación Modular 28

14

Pilas.Implementación

Suponiendo que
la pila tiene al

menos un
elemento

Desapilar ()
VAR

NodoPila *ptr

INICIO

ptr = cabeza