Laboratorio 5

Descargar como docx, pdf o txt
Descargar como docx, pdf o txt
Está en la página 1de 11

Laboratorio

N°5

LA PAZ - BOLIVIA

FACULTAD DE INGENIERIA UMSA


Nombre: Rodrigo Valeriano Aruni

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

Intuitivamente, podemos visualizar árboles como una forma de organizar información


de forma jerárquica, con un único punto de entrada y una serie de caminos que van
abriéndose en cada punto hacia sus sucesores.

Se utilizan distintas notaciones gráficas para


representar árboles. Entre ellas la más usual es el
diagrama de árbol invertido, que consiste en utilizar
un "árbol invertido", representando la raíz en la parte
superior, y, debajo de ella, de izquierda a derecha,
cada uno de sus subárboles:

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

1.4 Procesamiento de árboles

Podemos estudiar el procesamiento de árboles desde dos puntos de vista: en amplitud,


y en profundidad.

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

2.1 Pilas reprentadas por listas

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.

Finalmente, el método para indicar si se trata de una pila vacía.

3. Colas
5
Todos sabemos lo que es una cola. Más aún, ¡estamos hartos de hacer colas!

El TAD cola modela precisamente ese comportamiento: el primero que llega es el


primero en ser atendido, los demás se van encolando hasta que les toque su turno.

Sus operaciones son:

3.1 Colas implementadas sobre listas

Al momento de realizar una implementación de una Cola, deberemos preguntarnos


¿C6mo representamos a las colas? Veamos, en primer lugar, si podemos implementar
colas usando listas de Python, como hicimos con la Pila.

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

El método encolar se implementará agregando el nuevo elemento al final de la lista:


6
¿Cuánto cuesta esta implementación? Dijimos en la sección anterior que usar listas
comunes para borrar elementos al principio da muy malos resultados. Como en este
caso necesitamos agregar elementos por un extremo y quitar por el otro extremo, esta
implementación será una buena alternativa sólo si nuestras listas son pequeñas, ya que
e medida que la cola crece, el método desencolar tardará cada vez más.

Pero si queremos hacer que tanto el encolar como el desencolar se ejecuten en tiempo
constante, debemos apelar a otra implementación.

4. Listas

Las listas en Python son contenedores de elementos no ordenados que permiten


almacenar valores de diferentes tipos y son de tamaño flexible, pueden expandirse y
reducirse cuando se añaden o eliminan elementos.

Hay dos formas para crear listas en Python:

- Usando un par de corchetes “[]” vacíos para crear listas vacías.


- Usando la clase list() para crear listas vacías.

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.

4.1 Creando listas usando corchetes “[]” vacíos


lista = []

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: 

[1, 2, "America", True, 5.0]


.

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.

- Creando lista en base a otra ya existente


Si ya tenemos una lista existente con anterioridad, podemos usarla para crear una
nueva, de la siguiente forma:

* Usando desempaquetado de tuplas:


tupla = (5, 90, 19, "0", True, "America")
lista = [*tupla]

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.

* Usando desempaquetado de listas:


lista = [1, "America", 2, True, 5.0]
lista2 = [*lista]

Creamos una lista con “n” cantidad de elementos y luego la pasamos como argumento


en el juego de corchetes “[]”, junto con el signo “*”, esto desempaca los elementos y
almacena una copia en el mismo orden en la nueva lista. Esta forma es muy similar a la
que veremos a continuación, conocida como copia superficial.

* 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 “[:]”.

- Creando listas usando List Comprehensions (Comprensión de Listas)

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.

* Crear una lista con un rango de números:


lista = [x for x in range(1, 21) if x % 2 == 0]

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.

El anterior fragmento de código es equivalente al siguiente:


lista = []
for x in range(1, 101):
if x % 2 == 0:
lista.append(x)

Un código menos compacto, además, la variable “x” queda viva en la memoria durante


todo el programa sin que se le llegue dar un uso realmente útil. Hagamos otro ejemplo,
pero esta vez con strings.

* Crear una lista de caracteres:


lista = [c if c != c.lower() else c.upper() for c in "Hola MundO, BiEnvenidos!!"]

En este ejemplo cambia todo, ya no trabajamos con números y aparecen las


sentencias if .. else. La idea es crear una lista con los caracteres del string en mayúscula
cada uno, ignorando los caracteres que ya están en mayúscula.
Hay dos casos en los cuales el uso de la sentencia if es válido:

Usar después del bucle for, solo cuando no hay sentencia else, como se ve en el


ejemplo anterior.

Usar antes del bucle for, solo cuando hay una sentencia else, como se ve en el ejemplo
actual del string.

El bucle for va a recorrer los caracteres del string, la sentencia if verifica si ya están en


mayúscula y solo los agrega a la lista; mientras que en la sentencia else se convierten a
mayúscula con el método .upper() y luego se añade a la lista.
9
El anterior fragmento de código es equivalente al siguiente:
for c in "Hola MundO, BiEnveNidos!!":
if c != c.lower():
lista.append(c)
else:
lista.append(c.upper())

La variable c que aparece al inicio de los corchetes “[]” corresponde a lista.append(c) en


la línea 3 de este fragmento de código, el método .append() añade el valor de c a la
lista. De nuevo se genera un código menos compacto.

* Crear una lista con dos bucles for:


anios = [1974, 1932, 1919, 2018, 2007, 1992]
anios2 = [1983, 1820, 1950, 2001, 2007, 1981]
lista = [x - y if x > y else y - x for x in anios for y in anios2]
print(lista)

En este ejemplo básicamente se muestra como usar 2 bucles for en la Comprensión de


Listas, aquí se comparan los elementos de cada lista y luego se realizan operaciones de
resta para determinar la diferencia de años que hay. Este fragmento de código es
equivalente al siguiente:

anios = [1974, 1932, 1919, 2018, 2007, 1992]


anios2 = [1983, 1820, 1950, 2001, 2007, 1981]
lista = []
for x in anios:
for y in anios2:
if x > y:
lista.append(x - y)
else:
lista.append(y - x)
print(lista)

Muy notable la diferencia, pasando de 6 a 13 líneas de código. Los ejemplos que se


muestran aquí solo son una pequeña parte de las diferentes formas en las que se
pueden hacer listas con Comprensión de Listas y parecen básicos, pero en realidad se
pueden hacer operaciones avanzadas con pocos limitantes.

10
5. Punteros

Un puntero es una variable que contiene la dirección de memoria de otra variable.

Los punteros permiten código más compacto y eficiente; utilizándolos en forma


ordenada dan gran flexibilidad a la programación.

La dirección de memoria de una variable se obtiene con el operador unario &. El


operador unario * permite la desreferencia de un variable puntero; es decir, permite el
acceso a lo apuntado por un puntero.

Dado el ejemplo

La sintaxis de la declaración de un puntero imita a las expresiones en que la variable


puede utilizarse; cada puntero apunta a un tipo específico de datos (con la excepción
del puntero genérico void).

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

También podría gustarte