Laboratorio 5
Laboratorio 5
Laboratorio 5
N°5
LA PAZ - BOLIVIA
1
Estructura de datos
1. Arboles
Un árbol impone una estructura jerárquica sobre una colección de objetos. Ejemplos
claros de utilización de árboles se presentan tanto dentro como fuera del área de
computación (índices de libros, árboles genealógicos, etc.); en Informática constituyen
una de las estructuras más utilizadas, con aplicaciones que van desde los árboles
sintácticos utilizados para la representación y/o interpretación de términos de un
lenguaje o expresiones aritméticas, pasando por los árboles de activación de
procedimientos recursivos, hasta la representación de datos que se desea mantener
ordenados con un tiempo de acceso relativamente bajo. En general, se usarán árboles
siempre que se quiera representar información jerarquizada, cuando esta converja en
un solo punto.
1.2 Propiedades
Los hijos de un nodo de orden N pueden estar ordenados o desordenados. Los árboles
resultantes son ordenados y desordenados
respectivamente. Los siguientes árboles
ordenados no son equivalentes: O sea,
podemos ordenar o no a los hijos de un nodo,
lo cual dará lugar a diferentes conceptos de
igualdad.
2
1.3 Especificaciones algebraicas
- Procesamiento en amplitud
- Procesamiento de profundidad
3
2. Pilas
Una pila es un TAD que tiene las siguientes operaciones (se describe también la acción
que lleva adelante cada operación):
El comportamiento de una pila se puede describir mediante la frase "Lo último que se
apiló es lo primero que se usa", que es exactamente lo que uno hace con una pila (de
platos por ejemplo): en una pila de platos uno sólo puede ver la apariencia completa del
plato de arriba, y sólo puede tomar el plato de arriba (si se intenta tomar un plato del
medio de la pila lo más probable es que alguno de sus vecinos, o él mismo, se arruine).
Como ya se dijo, al crear un tipo abstracto de datos, es importante decidir cuál será la
representación a utilizar. En el caso de la pila, si bien puede haber más de una
representación, por ahora veremos la más sencilla: representaremos una pila mediante
una lista de Python.
Definiremos una clase Pila con un atributo, items, de tipo lista, que contendrá los ele-
mentos de la pila. El tope de la pila se encontrará en la última posición de la lista, y cada
vez que se apile un nuevo elemento, se lo agregará al final.
El método __init__ no recibirá parámetros adicionales, ya que deberá crear una pila
vacía (que representaremos por una lista vacía):
Advertencia
Al usar esa pila dentro de un programa, deberemos ignorar que se está trabajando sobre
una lista: solamente podremos usar los métodos de pila.
Si alguien viola este principio, y usa la representación dentro del programa usuario, termina
por recibir el peor castigo imaginable para un/a programador/a: sus programas pueden
dejar de funcionar el cualquier momento, tan pronto como quien produce del TAD decida
cambiar, aunque sea sutilmente, dicha representación.
4
El método apilar se implementará agregando el nuevo elemento al final de la lista:
Para implementar desapilar, se usará el método pop de lista que hace exactamente lo
requerido: elimina el último elemento de la lista y devuelve el valor del elemento
eliminado. Si la lista está vacía levanta una excepción, haremos lo mismo, pero
cambiaremos el tipo de excepción, para no revelar la implementación.
3. Colas
5
Todos sabemos lo que es una cola. Más aún, ¡estamos hartos de hacer colas!
Definiremos una clase Cola con un atributo, items, de tipo lista, que contendrá los
elementos de la cola. El primero de la cola se encontrará en la primera posición de la
lista, y cada vez que encole un nuevo elemento, se lo agregará al final.
El método __init__ no recibirá parámetros adicionales, ya que deberá crear una cola
vacía (que representaremos por una lista vacía):
Pero si queremos hacer que tanto el encolar como el desencolar se ejecuten en tiempo
constante, debemos apelar a otra implementación.
4. Listas
Con ambas formas podemos crear listas vacías o llenarlas con elementos de forma
predeterminada. Veremos ambas formas y como usar todos sus métodos para trabajar
sobre ellas.
Esta es la forma más común y sencilla de crear una lista vacía en Python, declaramos la
variable y después del signo “=” ponemos un par de corchetes “[]” vacíos. Si queremos
crear una lista con elementos predeterminados, solo hay agregarlos separados con una
coma “,”; por ejemplo:
7
Existen más formas de crear listas con elementos predeterminados usando el juego de
corchetes “[]”, que pueden ser o no ser más eficientes, dependiendo del contexto en el
que se usen. Veremos varias de ellas.
Creamos una tupla con “n” cantidad de valores y luego la pasamos como argumento en
los corchetes “[]”, junto con el signo “*”, esto toma los elementos de la tupla y los
desempaca como una copia en el mismo orden en la nueva lista.
* Copia superficial:
lista = [1, "America", 2, True, 5.0, False, 3.1415]
lista2 = lista[:]
En la copia superficial creamos una lista asignando una lista a una variable como se
observa en el fragmento de código, con la ventaja que podemos indicar el rango de
elementos que deseamos que tenga nuestra nueva lista usando Slicing o rebanadas
(que veremos más adelante). Al momento de asignar la lista debemos indicar que
deseamos que todos los elementos de la lista sean copiados, esto se hace usando la
sintaxis “[:]”.
8
La Comprensión de Listas es una forma compacta de crear listas, en la cual cada
elemento de la lista es el resultado de una operación previa sobre algún tipo de datos;
por ejemplo, crear una lista con los números pares de un rango.
Esta es la forma más básica de crear una lista usando Comprensión de Listas. En este
ejemplo generamos una lista con un rango de números que van desde 1 hasta 100, la
función range() no tiene en cuenta el último valor de los rangos.
Usar antes del bucle for, solo cuando hay una sentencia else, como se ve en el ejemplo
actual del string.
10
5. Punteros
Dado el ejemplo
La dirección especial NULL (o cero) indica que un puntero apunta a “nada” y es usada
como centinela para establecer el fin de estructuras autoreferenciadas. Además, esta es
retornada por la función de asignación de memoria, malloc, en el caso de no haber
suficiente memoria. El operador new, en cambio, aborta el programa cuando no tiene
más memoria que dar.
11