Clase 10 de prácticas: Estructuras de datos mutables

Tenemos el siguiente procedimiento para añadir listas:

(define (append x y)
    (if (null? x)
         y
        (cons (car x) (append (cdr x) y))))

append forma una lista nueva formando sucesivamente nuevas parejas de elementos de x con elementos de y. El procedimiento append! es similar a append, pero es un mutador, no un constructor. Añade las listas modificando el final de la última pareja de x para que su cdr sea ahora y. (Sería un error llamar a append! con un x vacío.)

(define (append! x y)
    (set-cdr! (last-pair x) y)
        x)

Donde last-pair es un procedimiento que devuelve la última pareja de su argumento:

(define (last-pair x)
    (if (null? (cdr x))
        x
        (last-pair (cdr x))))

Considera las siguientes instrucciones:

(define x (list 'a 'b))
(define y (list 'c 'd))
(define z (append x y))
z -> (a b c d)
(cdr x) -> ________________________
define w (append! x y))
w -> (a b c d)
(cdr x) -> ________________________

Rellena los huecos y a continuación dibuja diagramas de caja y puntero para explicar las respuestas.

¿Qué argumentos de las dos llamadas a set-cdr! que vemos abajo producen los efectos indicados en list1 y list2? No debes crear nuevas parejas, sólo modificar los punteros a las ya existentes. Rellena los espacios en blanco y dibuja los diagramas de caja y puntero asociados a las listas (list1 y list2) antes y después de haber ejecutado las dos llamadas a set-cdr!.

(define list1 (list (list 'a) 'b))
(define list2 (list (list 'x) 'y))
(set-cdr! ___________________  ___________________)
(set-cdr! ___________________  ___________________)
list1
((a x b) b)
list2
((x b) y)

A continuación dibuja un diagrama de caja y puntero que explique el efecto de evaluar la expresión:

(set-car! (cdr list1) (cadr list2))

Escribe un procedimiento filter-olist! que tome una lista con cabecera y un predicado como argumento, y elimine los elementos de la lista que no satisfagan el predicado.

(define lista (list '*list* 1 2 3 5 6 7 8 9 10 11 12))
(filter-olist! lista odd?)
l1
(*list* 1 3 5 7 9 11)

Escribe el procedimiento (subst-btree! tree old new) que tome un árbol binario y dos elementos como argumento, y mute el árbol binario de forma que cada ocurrencia de old se sustituya por new.

Escribe el procedimiento (reverse-olist! ols) que tome una lista con cabecera como argumento, y mute la lista de forma que quede invertida.

lista
(*list* 1 2 3 4 5 6 7 8)
(reverse-list! lista)
lista
(*list* 8 7 6 5 4 3 2 1)

Define el procedimiento (reverse-tree! tree) que mute el árbol genérico tree y lo devuelva invertido.

tree
(1 (2) (3 (5) (6)) (4))
(reverse-tree! tree)
tree
(1 (4) (3 (6) (5)) (2))

Fecha de entrega: durante la semana del 18 al 22 de mayo, en la sesión correspondiente a tu turno de prácticas.

Material a entregar para conseguir hasta 1,5 puntos (0,25 puntos cada ejercicio):

• Papel con las soluciones de los ejercicios 1, 2, 3, 4, 5 y 6
• Soluciones a los ejercicios 1, 2, 3, 4, 5 y 6 cargadas en el ordenador, para que el profesor de prácticas pueda evaluarlas