1

Me piden hacer una función que inserte un elemento entero en una lista enlazada ordenada de menor a mayor de forma recursiva en C++. Si el elemento ya pertenece a la lista, solamente se suma así mismo (da igual que luego de sumarse la lista quede desordenada).

Ejemplo: la lista dada es 1-3-4-8 y quiero insertar el 3, el resultado será 1-6-4-8.

Lo que hice fue lo siguiente:

struct nodo {
  int elem;
  nodo * sig;
}
typedef nodo * lista;

lista agregarAListaOrdenado(lista p, int x) {
  if (p == NULL || p->elem > x) {
    lista l = new nodo();
    l->elem = x;
    l->sig = p;
    p = l;
    return p;
  } else if (p->elem == x) {
    p->elem += x;
    return p;
  } else {
    return agregarAListaOrdenado(p->sig, x);
  }
}

Con algunos casos no funciona y no estaría viendo dónde está el error, por ejemplo: la lista dada es 1-2-3 y quiero insertar 4, da como resultado 4, cuando debería dar 1-2-3-4.

Gracias de antemano.

1 respuesta 1

2

Para saber si debes añadir un nuevo elemento tienes que actuar antes de llegar a un nodo nulo:

  if (p == NULL || p->elem > x) {
//    ~~~~~~~~~ <--- MAL

El motivo es que si p que es el puntero con el que iteras por la lista es NULL, ¿Cómo sabes dónde se encuentra el último nodo? Ya has perdido esa dirección de memoria y no la puedes recuperar. Sin este valor no puedes añadir elementos al final de la lista

lista agregarAListaOrdenado(lista p, int x) {
  if (p->elem > x) {
    lista l = new nodo();
    l->elem = x;
    l->sig = p;
    p = l;
    return p;
  } else if (p->elem == x) {
    p->elem += x;
    return p;
  } else if (p->sig == nullptr) {
    lista l = new nodo();
    l->elem = x;
    p->sig = l;
    return l;
  }
    return agregarAListaOrdenado(p->sig, x);
  }
}

Por otro lado, date cuenta que lista p es un concepto erróneo. Una cosa es una lista y otra un nodo. Una lista es una secuencia de nodos y esta función no está devolviendo tal cosa sino un nodo cualquiera de la lista.

No puedes perder de vista nunca el primer nodo de la lista porque si no es imposible que puedas gestionar correctamente la lista.

Así, por ejemplo, cuando quieres añadir un elemento a la lista haces lo siguiente:

lista l = new nodo();
l->elem = x;
l->sig = p;
p = l;
return p;

Al ejecutarse este código pueden pasar dos cosas:

  • Que no veas el nodo insertado en ningún sitio. Esto te sucederá siempre que se trate de un nodo intermedio. Efectivamente no estás modificando el nodo anterior, luego la lista no se entera de este cambio.

  • Que misteriosamente funcione. Si tienes la suerte de que estás trabajando sobre el primer nodo de la lista, entonces tendrás suerte y al lista reflejará el cambio.

Es más sencillo si separas conceptos:

struct Nodo {
  int elem;
  Nodo * sig;
};

struct Lista {
  Nodo * primero;
};

Ahora la función ya puede gestionar correctamente la lista sin perder elementos:

Lista agregarAListaOrdenado(Lista lista, int valor) {
    if (lista.primero == nullptr)
    {
        Nodo* nuevo = new Nodo;
        nuevo->elem = valor;
        nuevo->sig = nullptr;

        lista.primero = nuevo;
    }
    else if (lista.primero->elem == valor)
    {
        lista.primero->elem += valor;
    }
    else if (lista.primero->elem > valor)
    {
        Nodo* nuevo = new Nodo;
        nuevo->elem = valor;
        nuevo->sig = lista.primero;

        lista.primero = nuevo;
    }
    else
    {
        agregarAListaOrdenado(lista.primero, valor);
    }

    return lista;
}

void agregarAListaOrdenado(Nodo* nodo, int valor)
{
  if (nodo->sig == nullptr)
  {
    Nodo* nuevo = new Nodo;
    nuevo->elem = valor;
    nuevo->sig = nullptr;

    nodo->sig = nuevo;
  }
  else if (nodo->sig->elem > valor)
  {
    Nodo* nuevo = new Nodo;
    nuevo->elem = valor;
    nuevo->sig = nodo->sig;

    nodo->sig = nuevo;
  }
  else if (nodo->sig->elem == valor)
  {
    nodo->sig->elem += valor;
  }
  else
  {    
    agregarAListaOrdenado(nodo->sig, valor);
  }
}

Nota que ahora la función lo que hace es comprobar nodo->sig en vez de nodo. Trabajar desde el nodo anterior es la única forma de poder insertar elementos nuevos en cualquier parte de la lista. Esto tiene un efecto colateral, y es que tenemos que tratar de forma diferente al primer nodo de la lista. Esto se debe a que el primer nodo de la lista no tiene un nodo anterior sobre el que poder iterar.

También he quitado el alias. Lo he hecho por varias razones:

  • No es muy recomendable tener un alias de un puntero si no se indica claramente que es un puntero
  • Los nombres de las clases, estructuras, funciones y variables deben reflecjar el cometido de dicho elemento. Como te he comentado, un nodo no es una lista, luego ese alias puede llevar a cometer errores, como asumir que un nodo intermedio es una lista.
1
  • Ahí logré entenderlo, muchas gracias eferion. Commented el 23 oct. 2022 a las 1:22

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.