ESTRUCTURAS DE DATOS
Semana 07
Colas
LOGRO DE LA SESIÓN
Al finalizar la sesión, el estudiante realiza operaciones sobre una Cola, utilizando el
lenguaje de programación C#, con entorno gráfico, demostrando lógica y coherencia.
CONTENIDO
✓ Definición y características
✓ Representación gráfica y operaciones
✓ Implementación en un Vector
DEFINICIÓN Y CARACTERÍSTICAS
DEFINICIÓN
Es una Estructura en la cual los elementos se adicionan por un extremo y son atendidos por
el otro extremo. El primer elemento agregado en una Cola es el primero en ser eliminado.
Por ello, a las Colas también se les conoce como Estructuras FIFO (First In, First Out).
Ing. Wilbe Cerdán
CARACTERÍSTICAS
✓ Los elementos sólo pueden ser agregados por el extremo llamado final.
✓ Los elementos sólo pueden ser atendidos por el extremo llamado frente.
✓ Un elemento ubicado a la mitad de la Cola no podrá ser atendido sin haber atendido
antes a los elementos ubicados delante de éste.
Ing. Wilbe Cerdán
OPERACIONES Y REPRESENTACIÓN GRÁFICA
ADICIONAR
Consiste en colocar un elemento en la Cola, por el extremo derecho (final).
frente final
Ing. Wilbe Cerdán
ATENDER
Consiste en retirar un elemento de la Cola, por el extremo izquierdo (frente).
frente final
Ing. Wilbe Cerdán
IMPLEMENTACIÓN EN UN VECTOR
IMPLEMENTACIÓN EN UN VECTOR
Procedimiento
1. Se crea un Vector, de tamaño n, para almacenar los elementos de la Cola.
2. Se declaran dos variables, llamadas frente y final, para guardar las posiciones del primer
y del último elemento de la Cola respectivamente.
Ejemplo de representación
frente = 0
10 15 12 18
final = 3 0 1 2 3 4
Ing. Wilbe Cerdán
IMPLEMENTACIÓN EN UN VECTOR
Ejemplos
Dada la siguiente Cola:
frente = 0 10 15 12 18
final = 3 0 1 2 3 4
1. Adiciona el canal 16
frente = 0 10 15 12 18 16
final = 4 0 1 2 3 4
2. Atiende un elemento
frente = 1 15 12 18 16
final = 4 0 1 2 3 4
Ing. Wilbe Cerdán
IMPLEMENTACIÓN EN UN VECTOR
Ejemplos
Dada la siguiente Cola:
frente = 2 12 18 16
final = 4 0 1 2 3 4
3. Adiciona el canal 20
frente = 2 20 12 18 16
final = 0 0 1 2 3 4
4. Adiciona el canal 50
frente = 2 20 50 12 18 16
final = 1 0 1 2 3 4
Ing. Wilbe Cerdán
IMPLEMENTACIÓN EN UN VECTOR
Ejemplos
Dada la siguiente Cola:
frente = 2 20 50 12 18 16
final = 1 0 1 2 3 4
5. Atiende 2 elementos
frente = 4 20 50 16
final = 1 0 1 2 3 4
6. Atiende un elemento
frente = 0 20 50
final = 1 0 1 2 3 4
Ing. Wilbe Cerdán
IMPLEMENTACIÓN EN UN VECTOR
Verificaciones
▪ Si la Cola está vacía: frente = -1 y final = -1
▪ Si la Cola tiene un elemento: frente = final ≠ -1
▪ Si la Cola está llena: frente = 0 y final = n – 1 ó
frente = final + 1
Ing. Wilbe Cerdán
¡¡ GRACIAS POR SU ATENCIÓN !!
ESTRUCTURAS DE DATOS
Semana 08
Colas
LOGRO DE LA SESIÓN
Al finalizar la sesión, el estudiante realiza operaciones sobre una Cola, utilizando el
lenguaje de programación C#, con entorno gráfico, demostrando lógica y coherencia.
CONTENIDO
✓ Definición y características
✓ Representación gráfica y operaciones
✓ Implementación en una Lista enlazada
DEFINICIÓN Y CARACTERÍSTICAS
DEFINICIÓN
Es una Estructura en la cual los elementos se adicionan por un extremo y son atendidos por
el otro extremo. El primer elemento agregado en una Cola es el primero en ser eliminado.
Por ello, a las Colas también se les conoce como Estructuras FIFO (First In, First Out).
Ing. Wilbe Cerdán
CARACTERÍSTICAS
✓ Los elementos sólo pueden ser agregados por el extremo llamado final.
✓ Los elementos sólo pueden ser atendidos por el extremo llamado frente.
✓ Un elemento ubicado a la mitad de la Cola no podrá ser atendido sin haber atendido
antes a los elementos ubicados delante de éste.
Ing. Wilbe Cerdán
OPERACIONES Y REPRESENTACIÓN GRÁFICA
ADICIONAR
Consiste en colocar un elemento en la Cola, por el extremo derecho (final).
frente final
Ing. Wilbe Cerdán
ATENDER
Consiste en retirar un elemento de la Cola, por el extremo izquierdo (frente).
frente final
Ing. Wilbe Cerdán
IMPLEMENTACIÓN EN UNA LISTA ENLAZADA
IMPLEMENTACIÓN EN UNA LISTA ENLAZADA SIMPLE
Procedimiento
1. Se crea una Lista enlazada simple, para almacenar los elementos de la Cola.
2. Se declaran dos variables, llamadas frente y final, para guardar las direcciones de memoria del primer y del último
elemento de la Cola respectivamente.
Ejemplo
Adiciona los siguientes canales en una Cola: 10, 15, 12 y 18
Asígnales las siguientes direcciones de memoria: F05, F08, F03 y F06 respectivamente.
Ing. Wilbe Cerdán
IMPLEMENTACIÓN EN UNA LISTA ENLAZADA SIMPLE
Procedimiento
1. Se crea una Lista enlazada simple, para almacenar los elementos de la Cola.
2. Se declaran dos variables, llamadas frente y final, para guardar las direcciones de memoria del primer y del último
elemento de la Cola respectivamente.
Ejemplo
Adiciona los siguientes canales en una Cola: 10, 15, 12 y 18
Asígnales las siguientes direcciones de memoria: F05, F08, F03 y F06 respectivamente.
frente = F05 F05 F08 F03 F06
10 15 12 18
final = F06
Ing. Wilbe Cerdán
IMPLEMENTACIÓN EN UNA LISTA ENLAZADA SIMPLE
Operaciones
1. Adicionar un elemento en una Cola es igual que adicionar en una Lista enlazada simple.
2. Atender un elemento de la Cola es igual a eliminar al inicio en una Lista enlazada simple.
3. Recorrer una Cola es igual a recorrer una Lista enlazada simple.
Ing. Wilbe Cerdán
IMPLEMENTACIÓN EN UNA LISTA ENLAZADA SIMPLE
Verificaciones
▪ Si la Cola está vacía: frente = null y final = null
▪ Si la Cola tiene un elemento: frente = final ≠ null
Ing. Wilbe Cerdán
¡¡ GRACIAS POR SU ATENCIÓN !!
ESTRUCTURAS DE DATOS
Semana 09
Arboles
LOGRO DE LA SESIÓN
Al finalizar la sesión, el estudiante realiza operaciones de recorrido sobre un Árbol
binario, utilizando el lenguaje de programación C#, con entorno gráfico, demostrando
lógica y coherencia.
CONTENIDO
✓ Definición y representación
✓ Características y terminología
✓ Arboles binarios
DEFINICIÓN Y REPRESENTACIÓN
DEFINICIÓN
Es una Estructura de Datos no lineal, representa una relación jerárquica entre sus elementos.
Ing. Wilbe Cerdán
REPRESENTACIÓN
Ing. Wilbe Cerdán
CARACTERÍSTICAS Y TERMINOLOGÍA
CARACTERÍSTICAS
▪ Cada elemento del árbol se denomina nodo.
▪ El nodo de la parte superior se denomina raíz.
▪ Los nodos se conectan entre sí, a través de ramas.
▪ Cada nodo puede tener 0, 1 ó más nodos hijos.
▪ Cada nodo sólo tiene un nodo padre, a excepción de la raíz.
Ing. Wilbe Cerdán
TERMINOLOGÍA
▪ Sub árbol
Es un árbol que se encuentra
dentro de un árbol más grande.
▪ Hoja
Es aquel nodo que no tiene
sucesores (hijos).
▪ Altura
Es la distancia (ramas) desde
la raíz al nodo más lejano.
Ing. Wilbe Cerdán
ARBOL BINARIO
ARBOL BINARIO
DEFINICIÓN
Es un tipo específico de árbol en el cual cada nodo puede tener como máximo 2 sucesores.
Ing. Wilbe Cerdán
ARBOL BINARIO
FORMAS DE RECORRIDO
▪ Pre-Orden
▪ In-Orden
▪ Post-Orden
Ing. Wilbe Cerdán
ARBOL BINARIO
RECORRIDO PRE-ORDEN
▪ Visitar la raíz
A
▪ Recorrer sub árbol izquierdo
▪ Recorrer sub árbol derecho
B C
D E F
ABDECF
Ing. Wilbe Cerdán
ARBOL BINARIO
RECORRIDO IN-ORDEN
▪ Recorrer sub árbol izquierdo
A
▪ Visitar la raíz
▪ Recorrer sub árbol derecho
B C
D E F
D B EAC F
Ing. Wilbe Cerdán
ARBOL BINARIO
RECORRIDO POS-ORDEN
▪ Recorrer sub árbol izquierdo
A
▪ Recorrer sub árbol derecho
▪ Visitar la raíz
B C
D E F
D E B F CA
Ing. Wilbe Cerdán
¡¡ GRACIAS POR SU ATENCIÓN !!
Arboles Binarios
Ejemplo 1 Argentina
Dado el siguiente Arbol Binario,
muestra las 3 formas de recorrido: Uruguay Francia
Brasil Alemania
Italia
Pre-Orden:
In-Orden:
Post-Orden:
Ing. Wilbe Cerdán 1
Arboles Binarios
Ejemplo 1 Argentina
Dado el siguiente Arbol Binario,
muestra las 3 formas de recorrido: Uruguay Francia
Brasil Alemania
Italia
Pre-Orden: Argentina, Uruguay, Brasil, Francia, Alemania, Italia
In-Orden: Brasil, Uruguay, Argentina, Alemania, Italia, Francia
Post-Orden: Brasil, Uruguay, Italia, Alemania, Francia, Argentina
Ing. Wilbe Cerdán 2
Arboles Binarios
Ejemplo 2
Dado el siguiente Arbol Binario, A
muestra las 3 formas de recorrido:
B C
D E F
G H
Pre-Orden:
In-Orden:
Post-Orden:
Ing. Wilbe Cerdán 3
Arboles Binarios
Ejemplo 2
Dado el siguiente Arbol Binario, A
muestra las 3 formas de recorrido:
B C
D E F
G H
Pre-Orden: A, B, D, G, C, E, F, H, J
In-Orden: B, G, D, A, E, C, H, J, F
Post-Orden: G, D, B, E, J, H, F, C, A
Ing. Wilbe Cerdán 4
Arboles Binarios
Ejemplo 3
Dada la siguiente expresión aritmética: [A + (B – C)] x (D / E)
Dibuja el árbol correspondiente
y muestra sus recorridos
Pre-Orden:
In-Orden:
Post-Orden:
Ing. Wilbe Cerdán 5
Arboles Binarios
Ejemplo 3
Dada la siguiente expresión aritmética: [A + (B – C)] x (D / E)
Dibuja el árbol correspondiente x
y muestra sus recorridos + /
A – D E
B C
Pre-Orden:
In-Orden:
Post-Orden:
Ing. Wilbe Cerdán 6
Arboles Binarios
Ejemplo 3
Dada la siguiente expresión aritmética: [A + (B – C)] x (D / E)
Dibuja el árbol correspondiente x
y muestra sus recorridos + /
A – D E
B C
Pre-Orden: *, +, a, –, b, c, /, d, e
In-Orden: a, +, b, –, c, *, d, /, e
Post-Orden: a, b, c, –, +, d, e, /, *
Ing. Wilbe Cerdán 7
Arboles Binarios
Ejemplo 3
Dada la siguiente expresión aritmética: [A + (B – C)] x (D / E)
Dibuja el árbol correspondiente x
y muestra sus recorridos + /
A – D E
B C
Pre-Orden: *, +, a, –, b, c, /, d, e Notación pre-fija
In-Orden: a, +, b, –, c, *, d, /, e
Post-Orden: a, b, c, –, +, d, e, /, * Notación post-fija
Ing. Wilbe Cerdán 8
Arboles Binarios
Ejemplo 4
Dado los siguientes recorridos, dibuja el árbol correspondiente:
Pre-Orden: L, B, D, E, P, X, Y, Z
In-Orden: D, B, E, L, P, Y, X, Z
Ing. Wilbe Cerdán 9
Arboles Binarios
Ejemplo 4
Dado los siguientes recorridos, dibuja el árbol correspondiente:
Pre-Orden: L, B, D, E, P, X, Y, Z
In-Orden: D, B, E, L, P, Y, X, Z L
B P
D E X
Y Z
Ing. Wilbe Cerdán 10
Arboles Binarios
Ejemplo 5
Dado los siguientes recorridos, dibuja el árbol correspondiente:
Post-Orden: 70, 4, 29, 39, 13, 14, 11
In-Orden: 29, 70, 4, 11, 39, 14, 13
Ing. Wilbe Cerdán 11
Arboles Binarios
Ejemplo 5
Dado los siguientes recorridos, dibuja el árbol correspondiente:
Post-Orden: 70, 4, 29, 39, 13, 14, 11
In-Orden: 29, 70, 4, 11, 39, 14, 13 11
29 14
4 39 13
70
Ing. Wilbe Cerdán 12