ejercicio 4 insOrd

ejercicio 4 insOrd

de Rafael Agustin Castelli Ottati -
Número de respuestas: 9

Hola, llegue a la siguiente resolucion del ejercicio, pero me parece que separe demasiado en casos y es engorrosa. Como podria solucionarla en menos casos y de forma mas clara?

// Precond : lista l ordenada
void insOrd (int x, lista &l) {
    lista nuevo = new nodo_doble;
    nuevo->elem = x;
    lista dummy = new nodo_doble;
    dummy->sig = l;
    lista buscador = dummy;
    bool listo = false;
    while (buscador->sig != NULL && !listo) {
        buscador = buscador->sig;
        if (buscador->elem > x) {
            listo = true;
            nuevo->sig = buscador;
            nuevo->ant = buscador->ant;
            if (buscador->ant != NULL)
                buscador->ant->sig = nuevo;
            else
                l = nuevo;
            buscador->ant = nuevo;
        }
    }
//  Llegue al final sin encontrar posicion para insertar o la lista era vacia
    if (l == NULL) {
        l = nuevo;
        nuevo->ant = NULL;
        nuevo->sig = NULL;
    }
    else if (!listo && buscador->sig == NULL) {
        buscador->sig = nuevo;
        nuevo->ant = buscador;
        nuevo->sig = NULL;
    }
    delete dummy;
}

En respuesta a Rafael Agustin Castelli Ottati

Re: ejercicio 4 insOrd

de Sofia Tito Virgilio Rodriguez -

Hola Rafael,

Te cuento la manera en la que yo lo resolví. 

Yo lo separé en 2 casos, que son esencialmente:

  • insertar al inicio (ya sea porque la lista es vacía, o porque el primer elemento de la lista es mayor al elemento que estoy insertando)
  • insertar en el medio o al final 
El primer caso se considera simplemente con un if que verifique si corresponde insertar al inicio (si la lista es vacía o si l->elem > x).

Luego, para el segundo caso, en lugar de ir recorriendo y frenar en el elemento posterior, que es lo que haces vos, yo fui recorriendo con el propósito de frenar en el elemento anterior.
Esto lo puedo hacer porque ya tengo la certeza de que la lista no es vacía y de que no voy a insertar al inicio de la lista, entonces lo que hago es definirme un iterador iter que inicializo al comienzo de la lista, e ir recorriendo la lista mientras queden elementos (iter->sig != NULL) y mientras el próximo elemento sea menor o igual a x (iter->sig->elem <= x).
Cuando una de estas dos condiciones da false, es porque iter está posicionado en el elemento anterior al que quiero insertar (que puede ser el último o no).
Entonces, realizo la inserción de manera tal que en iter->sig quede insertado el nuevo elemento, teniendo el cuidado de actualizar iter->sig->ant solamente si iter->sig != NULL se puede lograr que el bloque de código de este caso funcione tanto para el medio de la lista como para el final.

Si no quedó claro o te surge alguna duda volvé a consultar,

Saludos!
En respuesta a Rafael Agustin Castelli Ottati

Re: ejercicio 4 insOrd

de Carlos Eduardo Colmenares Chirinos -

Yo lo hice de esta manera, a ver que les parece


4vbi

En respuesta a Carlos Eduardo Colmenares Chirinos

Re: ejercicio 4 insOrd

de Sofia Tito Virgilio Rodriguez -

Hola Carlos, 

¿Qué pasaría al ejecutar ese código si la lista l es vacía o si el primer elemento de l es mayor que x y por lo tanto x debe insertarse al inicio?

Saludos!

En respuesta a Sofia Tito Virgilio Rodriguez

Re: ejercicio 4 insOrd

de Carlos Eduardo Colmenares Chirinos -
No tome en cuenta ese caso pero debo modificar el codigo para que lo envalue tambie, gracias por avisar.
En respuesta a Carlos Eduardo Colmenares Chirinos

Re: ejercicio 4 insOrd

de Sofia Tito Virgilio Rodriguez -

Carlos,

Hay un detalle más que me dí cuenta ahora, en el segundo if, el que evalúa si el siguiente es mayor que x, fijate que en este caso el orden en el que actualizas las referencias puede alterar el resultado.

Si ejecutas la instrucción

lpos->sig = nuevo  (instr 1)

antes de ejecutar la instrucción

lpos->sig->ant = nuevo (instr 2)

entonces al ejecutar instr 2 tenemos que lpos->sig ahora es igual a nuevo y por lo tanto instr 2 es equivalente a nuevo->ant = nuevo, que no es realmente lo que queremos lograr, por lo que también hay que tener en cuenta el orden de las instrucciones para que las referencias se actualicen correctamente.

No sé si se entendió bien, cualquier cosa volvé a consultar,

Saludos!

En respuesta a Sofia Tito Virgilio Rodriguez

Re: ejercicio 4 insOrd

de Maria Alejandra Galetta Paz -

Buenas tardes, 

A mi el código me quedo de la siguiente forma 

void insOrd(int x, lista & l) {   

    lista p= new nodo_doble;

          p->=x;

     if (l==NULL|| l->elem>=x) {

          p->sig=l;

          p->ant=NULL;

          if (l!=NULL) {

                 p->ant=P;

                 l=p;

              }

           else 

                l=p;

         }

     else {

         lista cursor=l;

         while (cursor->sig!=NULL && cursor->sig->elem<x)

             cursor=cursor->sig;

         p->sig=cursor->sig;

         p->ant=cursor;

         if (cursor->sig!=NULL)

              cursor->sig->ant=p;

         cursor->sig=p;

         };

};

Quería saber si había hecho bien las conexiones, con los nodos anterior y posterior. Muchas gracias.


En respuesta a Maria Alejandra Galetta Paz

Re: ejercicio 4 insOrd

de Sofia Tito Virgilio Rodriguez -

Hola,

El código que mostras parece ser correcto exceptuando por la primer instrucción dentro del if(l != NULL), te das cuenta por qué?

Luego, un detalle, cuidado con los ";", no van luego de las llaves "}" a no ser, por ejemplo, que estés definiendo un struct como sucede en el caso del laboratorio.

Saludos!

En respuesta a Sofia Tito Virgilio Rodriguez

Re: ejercicio 4 insOrd

de Maria Alejandra Galetta Paz -
Hola, muchas gracias, si me equivoque al pasarlo, la primera instrucción de ese if debería ser :

l->ant=p 

no?