PDF de programación - Estructuras de Datos Avanzadas

Estructuras de Datos

Avanzadas

Contenido del Tema

6.1. Introducción
6.2. Pilas
6.3. Colas
6.4. Listas
6.5. Arboles Binarios.
Arboles Binarios de Búsqueda
6.6. Otras Estructuras.

T
T
E
E
M
M
A
A

6
6

Metodología de Programación

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 , Colas

y Listas

2) Datos organizados por Valor Arboles Binarios

Metodología de Programación

1

Introducción

• Estudio de las Estructuras de Datos:
Definición

Definición de la Estructura de Datos e
identificación de su Conjunto de
Conjunto de
Operaciones
Operaciones

Desarrollo de diversas Implementaciones
Implementaciones

Presentación de Aplicaciones
Aplicaciones

Metodología de Programación

Pilas

Añadir

Eliminar

Definición
Definición

•• Pila:Pila: Grupo Ordenado, (de
acuerdo al tiempo que llevan
en la pila) de Elementos
Homogéneos
del
mismo tipo).
Acceso a la Pila: añadir y
eliminar elementos, SÓLO a
través de la CABEZA de la
Pila

•• Acceso a la Pila:

(todos

• Estructura LIFOLIFO (LLast Input

First Output)

Metodología de Programación

2












Pilas. Operaciones

Conjunto de Operaciones
Conjunto de Operaciones

MÓDULO MPila
DEFINICIÓN
TIPOS
TElemento= // cualquier tipo de datos

TPila= // por definir

PROC MeterPila(fl
pila:TPila; fl elem: TElemento)
// Añade un elemento por la cabeza de la pila
PROC SacarPila(fl
pila:TPila;› elem:TElemento)
// Saca un elemento por la cabeza de la Pila

Metodología de Programación

Pilas. Operaciones

Conjunto de Operaciones
Conjunto de Operaciones

FUNC CrearPila():TPila
// Crea una pila vacía
FUNC PilaVacia (fl pila :TPila):LÓGICO
// Nos dice si una pila está vacía
FUNC PilaLlena(fl pila:TPila):LÓGICO
// Nos dice si una pila está llena.
PROC DestruirPila(fl
// Destruye una pila previamente creada
Fin

pila:TPila)

Metodología de Programación

3

›
›
›
Pilas. Implementación

Implementación
Implementación

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

CONSTANTES

MAXPILA ‹ 100

TIPOS
TElemento = ENTERO
TPila = ARRAY[1..MAXPILA]DE TElemento

Metodología de Programación

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

Metodología de Programación

4

Pilas. Implementación

CONSTANTES

CABEZA ‹ 0
MAXPILA ‹ 100

TIPOS

TPila = ARRAY[CABEZA..MAXPILA]DE TElemento

33

55

33

22

.......
.......

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

[99] [100]
[99] [100]

22
33
55

Metodología de Programación

Pilas.Implementación

•

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

• Solución: CONSTANTES

MAXPILA ‹ 100
TIPOS
TElemento= // cualquier tipo de datos
TPila=REGISTRO

Cabeza:NATURAL
Elementos: ARRAY[1..MAXPILA] DE

TElemento

kk

55
1 1 2

1313
2

.........
.........
k

88
k MAXPILA
MAXPILA

Metodología de Programación

5





















































!
"
#






!
"
#
Pilas.Implementación

IMPLEMENTACIÓN
FUNC CrearPila():TPila
VARIABLES
pila:TPila
INICIO

pila.Cabeza ‹ 0
RESULTADO ‹ pila

FIN
FUNC PilaVacia(fl pila:TPila

):LÓGICO

INICIO

RESULTADO‹ pila.Cabeza=0

FIN

FUNC PilaLlena(fl pila:TPila

):LÓGICO

INICIO

RESULTADO ‹ (pila.Cabeza

= MAXPILA)

FIN

PROC

DestruirPila(fl

› pila:TPila)

INICIO
// No hay que hacer nada.
FIN

Metodología de Programación

Pilas.Implementación

PROC SacarPila(fl

pila:TPila;

PROC MeterPila(fl

pila:TPila;

› elem:TElemento)

fl elem :TElemento)

INICIO

elem ‹ pila.Elementos
[pila.Cabeza]
pila.Cabeza‹ pila.Cabeza-1

INICIO

pila.Cabeza‹ pila.Cabeza+1
pila.Elementos
[pila.Cabeza] ‹ elem

la pila no ha de estar vacía

*/

*/

FIN

/* precondición:

FIN
/* precondición:

la pila no ha de estar llena

Metodología de Programación

6

›
›
Pilas.Implementación

PROC MeterPila (fl

fl elem:TElemento;
› llena : LÓGICO)

Inicio

pila:TPila;

PilaLlena(pila)

llena ‹
SI ( llena) ENTONCES


pila.Cabeza

pila.Cabeza + 1

pila.Elementos
[pila.Cabeza] ‹ elem

FINSI

Fin
/* Sin Prec ondición.Introduce
un elemento en la pila si
no está llena */

PROC SacarPila(fl

› elem:TElemento;
› vacia:LÓGICO)

pila:TPila ;

INICIO
vacia ‹ PilaVacia(pila)
SI

vacia ENTONCES
elem ‹ pila.Elementos
[pila.Cabeza]
pila.Cabeza ‹

pila.Cabeza-1

FINSI
FIN
/* Sin precondición. Saca un
elemento de la pila si no
está vacía*/

Metodología de Programación

Pilas.Implementación

2) Con una Lista Enlazada de Punteros
• Comienzo de una lista enlazada
TIPOS

Cabeza de la Pila

TElemento= // cualquier tipo de datos
TPila = PUNTERO A TNodoPila
TNodoPila =

REGISTRO



FINREGISTRO

dato:TElemento
sig: TPila

Metodología de Programación

7

›
‹
›
$
%
$
%
&
&
'
(
)
*
+
(
'
(
)
*
+
(
,
-
,
-
.
.
Pilas.Implementación

PROC MeterPila(fl

› pila:TPila;

› elem: TElemento;
› llena: LÓGICO)

VARIABLES

nuevonodo : TPila

INICIO

llena ‹ FALSO
nuevonodo ‹

NUEVO(TNodoPila)

nuevonodo^.dato ‹ elem
nuevonodo^.sig ‹ pila
pila ‹ nuevonodo

FIN

PROC SacarPila(fl

› pila:TPila;

› elem
› vacía: LÓGICO)

:TElemento;

VARIABLES

ptr: TPila

INICIO

vacía ‹ PilaVacía(pila)

SI vacía ENTONCES

elem ‹ pila^.dato
ptr ‹ pila
pila ‹ pila^.sig
ELIMINAR(ptr)

FINSI
FIN

Metodología de Programación

Pilas.Implementación

PROC CrearPila():TPila

PROC DestruirPila(fl

› pila:TPila)

INICIO

RESULTADO ‹ NULO

Fin

FUNC PilaVacia(pila :TPila

):LÓGICO

INICIO

RESULTADO ‹ (pila= NULO)

FIN

Variables

ptr: TPila

Inicio

MIENTRAS(pila„ NULO)HACER

ptr ‹ pila
pila ‹ pila^.sig
ELIMINAR(ptr)

FINMIENTRAS

FIN

Metodología de Programación

8

Pilas. Aplicaciones

Aplicaciones
Aplicaciones

•• Ejemplo1

•• Ejemplo2

Ejemplo1: Leer una secuencia de caracteres desde teclado
: Leer una secuencia de caracteres desde teclado
e imprimirla al revés
e imprimirla al revés
Ejemplo2: Verificar si una cadena de caracteres está
: Verificar si una cadena de caracteres está
balanceada en paréntesis o no
balanceada en paréntesis o no
))(l(mnmn))opop))qrqr



abcabc((defgdefg((ijkijk))(l(
abc((defdef))))ghijghij((klkl)m)m
abc

SISI
NONO

•• Ejemplo3
Ejemplo3: Reconocimiento del Lenguaje,
: Reconocimiento del Lenguaje,
L={W$W´ / W es una cadena de caracteres y Wés su
L={W$W´ / W es una cadena de caracteres y Wés su

inversa} (Suponemos que $ no está ni en W ni en W´)
inversa}
(Suponemos que $ no está ni en W ni en W´)

Metodología de Programación

Pilas. Ejemplo1

ALGORITMO Inverso
DESDE MPila IMPORTA

TPila,
MeterPila,
Pilavacia, DestruirPila

CrearPila,
SacarPila,

CONSTANTES

ENTER ‹ CHR(13)

TIPOS

TElemento = CARÁCTER

VARIABLES

c : TElemento
pila : TPila
ll,v:LÓGICO

INICIO

pila ‹ CrearPila()
LEER(c)

MIENTRAS (c„ ENTER)
( ll) HACER

MeterPila(pila,c,ll)
Leer(c)

FINMIENTRAS

SacarPila(pila,c,v)

MIENTRAS
( PilaVacia(pila))HACER
SacarPila(pila,c,v)
Escribir(c)

FINMIENTRAS
DestruirPila(pila)

FIN

Metodología de Programación

9

Pilas. Ejemplo2

ALGORITMO Balanceo
DESDE MPila IMPORTA CrearPila, TPila,
MeterPila, SacarPila, PilaVacia,
DestruirPila

CONSTANTES

ENTER ‹ CHR(13)

Tipos

TElemento = CARÁCTER

VARIABLES

c : TElemento
pila : TPila
bien,ll, v : LÓGICO

Inicio

pila ‹ CrearPila()
bien ‹ CIERTO
LEER(c)

MIENTRAS(bien

(c„ ENTER)HACER

SI c= ‘(’ ENTONCES

MeterPila(pila,c,ll)
bien ‹ ll

EN OTRO CASO

SI c = ‘)’ ENTONCES

SacarPila(pila,c,v)
bien ‹ v

FINSI

FINSI
LEER(c)
FINMIENTRAS
SI bien PilaVacia(pila) ENTONCES
Escribir(“cadena balanceada “)

EN OTRO CASO

Escribir(“cadena no balanceada”)

FINSI
DestruirPila(pila)
FIN

Metodología de Programación

Pilas. Ejemplo3

Algoritmo Lenguaje_L
DESDE MPila IMPORTA TPila,

CrearPila, MeterPila,
SacarPila, DestruirPila

CONSTANTES

ENTER ‹ CHR(13)

TIPOS

TElemento = CARÁCTER



VARIABLES

c1, c2 : TElemento
pila : TPila
bien, ll, v : LÓGICO

Leer(c1)
bien ‹ TRUE
MIENTRAS (bien (c1 „ ENTER))

HACER

SacarPila(pila,c2,v)
bien ‹ ( v) (c1=c2)
/* He podido sacar el
elemnto y conicide
*/
SI (bien) ENTONCES
Leer(c1)
FINSI

Inicio

pila ‹ CrearPila()

ll ‹ FALSO

LEER(c1)
MIENTRAS (c1 „ ‘$’) ( ll) HACER

MeterPila(pila,c1,ll)
LEER(c1)

FINMIENTRAS

FINMIENTRAS
SI (bien

PilaVacia(pila))ENTONCES
Escribir(“ Si pertenece”)

EN OTRO CASO

Escribir (“No pertenece”)

FINSI
DestruirPila(pila)

FIN

Metodología de Programación

10

Pilas. Aplicaciones

• Aplicaciones complejas que se pueden solucionar con

pilas:

Expresiones Algebraicas
Expresiones Algebraicas

Operadores: +, -, *, /
Operandos: Letras mayúsculas
Notación Infija
Infija::

•• Notación
• 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

Metodología de Programación

Pilas. Aplicaciones

Notación Prefija
Notación Prefija

Notación Postfija
Postfija
Notación

antes

• El operador binario esta situado
dos

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

de

sus
+AB

• El operador binario está situado