Arboles

FUNDAMENTOS DE
PROGRAMACIÓN
Datos recursivos II
Ángela Villota Gómez
Escuela de Ingeniería de Sistemas y Computación
Facultad de Ingeniería
Universidad del Valle

Primera parte:
Repaso de funciones con listas
Soluciones a algunos problemas de la tarea en clase

Problema 1: función que toma una lista como
entrada y retorna un elemento.
función elemento-n, que
toma como entradasuna
lista y un natural n. La
función retorna el n-esimo
elemento en la lista.
 Ejemplo:






(elemento-n 2 (list 1 2
3))debe retornar 2

Análisis de datos:
 Si la lista está vacía:
Puede ser por dos razones:





Importante: la cuenta de los
elementos arranca en 1


Se pasó una lista vacía como entrada
El índice es mayor que el tamaño de la lista

En amboscasos hay un error en la
entrada.
Si n es igual a 1:
Quiere decir que ya se encontró el
elemento buscado y se retorna el
primero de la lista
En el caso contrario:
Es necesario seguir buscando en el
resto de la lista y con n-1 por medio de
un llamado recursivo.

Problema 1: función que toma una lista como
entrada y retorna una lista.


función insertar-en-n que tiene
Análisis dedatos:
como entradas: un elemento, una  Si la lista está vacía:
lista y un natural n. La función
Puede ser por dos razones:
retorna una lista en la que se ha
 Se pasó una lista vacía como entrada
insertado el elemento en la n El índice es mayor que el tamaño de la lista
esima posición.



Ejemplo:

(insertar-en-n 5 (list 1 2 3 4) 2 )
debe retornar (list 1 5 2 3 4)


En el primercaso no hay error, pero en el
segundo si


Quiere decir que ya se encontró la
posición en la que se quiere ubicar el
elemento, así que se hace cons del
elemento y la lista

Importante:


Si n es igual a 1:

la cuenta de los elementos
arranca en 1


En el caso contrario:
Es necesario seguir contando posiciones,
pero también conservando los elementos
de la lista

Problema1: función que toma una lista como
entrada y retorna una lista.




función insertar-ultimo que tiene Análisis de datos:
como entradas: un elemento y
 Si la lista está vacía:
una lista. La función retorna una
Puede ser por dos razones:
lista en la que se ha insertado el
 Se pasó una lista vacía como entrada
elemento en la última posición.


Ejemplo:
(insertar-ultimo 3 (list 21))
debe retornar (list 2 1 3)
La clave en este ejercicio es
encontrar el fin de la lista
(empty) para poder insertar el
elemento




Se recorrió la lista y llegamos a
empty

En ambos casos hacemos (cons
elemento lista)


En el caso contrario:
Es necesario seguir buscando el
fin de la lista haciendo un
llamado recursivo con el resto.

Segunda parte: Datos recursivosEstructuras en estructuras y Listas en listas,
ejemplos: árboles

Listas con estructuras
 Definición

de datos:

(define-struct toy (nom pre))
; La estructura toy repesenta
un juguete
; nom es el nombre, de tipo
símbolo
; pre es el precio, de tipo
número
Un ejemplo de lista de juguetes :

(list
(make-toy
(make-toy
(make-toy
(make-toy
)

‘car 20)
‘doll 15)
‘xbox 300)
‘ipod150)

(list
‘car

20

‘doll

15

‘xbox

300

‘ipod

150

)

Ejemplo de funciones con listas que contienen
estructuras


Análisis de datos:
 Si la lista está vacía:
Puede ser por dos razones:

función quitar-caro que
saca de una lista los
juguetes que son
considerados caros. La
función tiene dos entradas,
una lista de juguetes y un
límite.




Se pasóuna lista vacía como entrada



Se llegó al final de la lista

Dado que esta función retorna una lista se debe
retornar empty
En el caso contrario:
Si el precio del juguete es menor o igual al
límite: se incluye en juguete en la lista y se sigue
comparando con los elementos del resto de la
lista por medio de un llamado recursivo.
 Si es mayor: no se incluye en la lista y se sigue...