PDF de programación - Estructuras de Datos Avanzadas

Imágen de pdf Estructuras de Datos Avanzadas

Estructuras de Datos Avanzadasgráfica de visualizaciones

Publicado el 16 de Enero del 2021
63 visualizaciones desde el 16 de Enero del 2021
319,7 KB
31 paginas
Creado hace 16a (26/04/2004)
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
  • Links de descarga
http://lwp-l.com/pdf18706

Comentarios de: Estructuras de Datos Avanzadas (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad