Prog2: Ejercicio 2a

Hola, resolviendo este ejercicio llegue a dos implementaciones distintas y me surgieron estas dudas :

Cual de las dos implementaciones es preferible? Estan bien las implementaciones?

En la primera trate de evitar tener que buscar en cada llamada recursiva el final de la lista y entonces me hice la funcion auxiliar lista enOrdenRec (AB t, lista &l). La idea de l es poder guardarme siempre el final de la lista para no tener que buscarlo al momento de concatenar las listas.

En la segunda implementacion trate de hacerlo usando directamente append y las llamadas recursivas.

// Primera implementacion

lista enOrdenRec (AB t, lista &l) {
    if (t != NULL) {
        lista finalLeft, finalRight;
        lista principio = enOrdenRec(t->izq,finalLeft);
        lista nuevo = new nodoLista;
        nuevo->elem = t->elem;
        if (finalLeft != NULL)
            finalLeft->sig = nuevo;
        else
            finalLeft = nuevo;
        nuevo->sig = enOrdenRec(t->der, finalRight);
        l = finalRight;
        return principio;
    }
    else {
        l = NULL;
        return NULL;
    }
}

lista enOrden(AB t) {
    lista l = crearLista();
    return enOrdenRec(t, l);
}

// segunda implementacion

lista enOrdenAppend(AB t) {
    if (t == NULL)
        return NULL;
    else {
        lista nuevo = new nodoLista;
        nuevo->elem = t->elem;
        nuevo->sig = NULL;
        lista principio = enOrdenAppend(t->izq);
        principio = append(principio, nuevo);
        principio = append(principio, enOrdenAppend(t->der));
        return principio;
    }
}

lista append (lista &inicio,lista final)

Ademas, cuando intente escribir el return de la segunda implementacion como :

return append(append(enOrdenAppen(t->izq), nuevo), enOrdenAppen(t->der));

tuve el siguiente error del compilador:

cannot bind non-const lvalue reference of type nodoAB* to an rvalue of type nodoAB*

y no entiendo mucho que quiere decir, supuse que tiene que ver con pasar por referencia el inicio de la lista en

append y por eso me arme la variable principio.

Re: Ejercicio 2a

de Sofia Tito Virgilio Rodriguez - lunes, 20 de abril de 2020, 15:01

Hola Rafael,

Es muy interesante la solución que se te ocurrió para aprovechar el pasaje por referencia y no tener que recorrer la lista en cada iteración.

Aunque hay un detalle en la implementación respecto a eso, si te fijas, tu implementación le asigna algo a l en dos casos,

cuando el árbol no es vacío, le asigna el final retornado por la invocación con el subárbol derecho,
cuando el árbol es vacío le asgina NULL

¿Cuál es el problema con esto?. Que l siempre va a terminar valiendo NULL.

¿Por qué? Porque para obtener el valor de l usamos el valor almacenado en finalRight, que a su vez va a usar el valor de finalRight que se obtiene al llamar con su subárbol derecho, y así sucesivamente, hasta que se llegue al punto en que el subárbol derecho sea NULL, y ahí se frena la recursión y se devuelve por referencia NULL hasta volver al punto en el que empezamos.

Esto nos dice que necesitamos otro caso base en el que exista una lista cuyo final se le pueda asignar a l, es decir, hay que agregar el caso en el que el árbol tiene un solo elemento, se crea la lista de un solo nodo, y se devuelve en l una referencia a ese único nodo de la lista, que es el nodo final.

Teniendo ambos casos base, tu implementación funcionaría bien si el árbol es vacío de primera, pero también funcionaría bien cuando el árbol no es vacío, ya que al empezar a llamar recursivamente con el subárbol derecho para obtener el valor del final, ya no va a frenar cuando llegue a un subárbol vacío, sino que va a frenar cuando llegue a un subárbol con un solo elemento, y ese va a ser el final que se va a devolver por referencia hasta volver al punto en el que empezamos.

Luego hay otro detalle en la instrucción finalLeft = nuevo; ya que luego lo que retornas es principio, por lo que en caso de que el subárbol izquierdo sea vacío, lo que tiene que apuntar a nuevo es el puntero principio, ¿se ve eso?

Un último detalle es que en la función invocadora, en este caso al invocar a crearLista() no estás pidiendo memoria, pero podrías tener una representación de lista como la de la tarea 2 en la que si se pida memoria para crear una lista vacía, y luego esa memoria se perdería, por lo que en ese caso sería incorrecto crear una cadena vacía si luego se va a modificar el valor del puntero y se va a perder la referencia, y por lo tanto la memoria, asociada a esa lista vacía.

En cuanto a la segunda implementación, también es correcta, y el error que te dió el compilador básicamente dice que no puede transformar un lvalue (valor que puede ir a la izquierda de una asignación) en un rvalue (valor que puede ir a la derecha de una asignación).
Y este error sale del pasaje por referencia, ya que al pasar un elemento por referencia estamos dando a entender que se va a modificar, y por lo tanto, que va a ser tratado como un lvalue, sin embargo, lo retornado por append es un rvalue, ya que los resultados de las invocaciones a operaciones que retornan un valor pueden ir a la derecha de las asignaciones.

Entonces es por esto no te deja pasar el resultado de invocar a append como primer parámetro de la función.

En cuanto a cuál es preferible, hay muchas formas de evaluar qué solución es preferible frente a otra, ésta semana se va a empezar con el tema de introducción al análisis de algoritmos que se centra en evaluar y comparar la eficiencia de los algoritmos en base al tiempo de ejecución, y eso te va a dar herramientas para poder evaluar qué solución conviene más al menos en ese aspecto.

Cualquier duda que haya quedado no dudes en consultar nuevamente,

Saludos!