Me gustaría insertar los datos de forma ordenada en una lista vinculada ordenada. Puedo insertar los datos pero no están ordenados. ¿Alguien puede ayudarme en lo que estoy haciendo mal? Aquí está mi función:

typename SortedList<T>::iterator SortedList<T>::insert(const T& data) {


if (data < front_->data_) {
    Node* n = new Node(data, front_, nullptr);

    //if empty
    if (front_ == nullptr) {
        //make back pt to node
        back_ = n;
    }
    else {
        //make front's previous point to node
        front_->prev_ = n;
    }
    //make front point at node
    front_ = n;
    return SortedList<T>::iterator(n);
}
else {
    Node* nn = new Node(data, nullptr, back_);

    //if empty
    if (front_ == nullptr) {
        //make front_ pt to node
        front_ = nn;
    }
    else {
        //make back's next point to node
        back_->next_ = nn;
    }
    //make back point at node
    back_ = nn;
    return SortedList<T>::iterator(nn);
}

Y aqui esta mi clase

class SortedList{

struct Node {
    T data_;
    Node* next_;
    Node* prev_;
    Node(const T& data = T{}, Node* nx = nullptr, Node* pr = nullptr) {
        data_ = data;
        next_ = nx;
        prev_ = pr;
    }
};

Node* front_;
Node* back_;
int sizelist;

}
0
Adi 18 oct. 2017 a las 23:30

3 respuestas

La mejor respuesta

No está comprobando front_ para nullptr antes de acceder a front_->data.

Pero lo más importante, no está tratando de insertar los datos en ningún tipo de posición ordenada. Está insertando solo al principio o al final de la lista. Para insertar en el medio, debe escanear la lista buscando el lugar correcto para insertar.

Pruebe algo más como esto en su lugar:

class SortedList{

    struct Node {
        T data_;
        Node* prev_;
        Node* next_;

        Node(const T& data = T{}, Node* pr = nullptr, Node* nx = nullptr)
            : data_(data), prev_(pr), next_(nx)
        {
        }
    };

    Node* front_;
    Node* back_;
    int size_;

    ...

    iterator insert(const T& data);
};

typename SortedList<T>::iterator SortedList<T>::insert(const T& data)
{
    Node *nn = front_;
    while ((nn) && (data >= nn->data_)) {
        nn = nn->next_;
    }

    Node *n = new Node(data);
    if (nn)
    {
        n->prev_ = nn->prev_;
        n->next_ = nn;
        if (nn->prev_) nn->prev_->next = n;
        nn->prev = n;
    }
    else
    {
        n->prev_ = back_;
        if (back_) back_->next_ = n;
        back_ = n;
    }

    if (front_ == nn) front_ = n;

    ++size_;

    return iterator(n);
}
0
Remy Lebeau 18 oct. 2017 a las 22:33

No vi ningún código que busque en la lista para encontrar dónde insertar el elemento. No ha especificado la cantidad de elementos que espera tener; el rendimiento de una inserción lineal en una lista ordenada es en promedio O (n / 2), lo que lleva a la conclusión de que en general tendrá O (n ^ 2/2) [que es n cuadrado sobre 2], lo cual es intolerable si n es, digamos, 10,000 e irrelevante si n <10. Hace 20 años enfrenté este problema con n> 200, en un 8088. Hay una solución que es aproximadamente O (log2 (n)), pero sin saber n I no quiero pasar el tiempo para explicarlo si no es relevante.

0
flounder 18 oct. 2017 a las 20:59

Su código apunta a la falta de claridad en su pensamiento.

Tienes que lidiar con los siguientes casos:

  1. La lista está vacía.
  2. Los nuevos datos son menores que los valores de todos los elementos de la lista.
  3. Los nuevos datos son mayores que los valores de todos los elementos de la lista.
  4. Los nuevos datos se encuentran entre los valores más bajos y más altos de los elementos de la lista.

Además, su uso de "prev" y "next" me parece un poco extraño. Cuando pienso en una lista doblemente vinculada, pienso en ella como:

          front -> next -> next -> next -> nullptr
nullptr <- prev <- prev <- prev <- back

Parece que estás usando:

          front -> prev -> prev -> prev -> nullptr
nullptr <- next <- next <- next <- back

Mi respuesta corresponde a lo que creo que estás usando, la segunda versión. Si eso es incorrecto, los usos de "siguiente" y "anterior" deben actualizarse en algunos lugares.

Caso 1

Agregue lo siguiente al comienzo de su función:

if ( front_ == nullptr )
{
   Node* n = new Node(data, nullptr, nullptr);
   front_ = n;
   back_ = n;
   return SortedList<T>::iterator(n);
}

Caso 2

Te hace falta:

if ( data < front_->data_ )
{
   Node* n = new Node(data, front_, nullptr);
   front_->prev_ = n;
   return SortedList<T>::iterator(n);
}

Caso 3

Te hace falta:

if ( data > back_->data_ )
{
   Node* n = new Node(data, nullptr, back_);
   back_->next_ = n;
   return SortedList<T>::iterator(n);
}

Caso 4

Te hace falta:

// Find the place where to insert the new Node.
Node* iter = front_;
for ( ; iter != nullptr && data < iter->data_; iter = iter->prev_ );

// Insert the new Node.
Node* prev = iter->prev_
Node* n = new Node(data, iter, prev);
prev->next_ = n;
iter->prev_ = n;
return SortedList<T>::iterator(n);

Poniendo todo junto:

typename SortedList<T>::iterator SortedList<T>::insert(const T& data)
{
   // Case 1
   if ( front_ == nullptr )
   {
      Node* n = new Node(data, nullptr, nullptr);
      front_ = n;
      back_ = n;
      return SortedList<T>::iterator(n);
   }

   // Case 2
   if ( data < front_->data_ )
   {
      Node* n = new Node(data, front_, nullptr);
      front_->prev_ = n;
      return SortedList<T>::iterator(n);
   }

   // Case 3
   if ( data > back_->data_ )
   {
      Node* n = new Node(data, nullptr, back_);
      back_->next_ = n;
      return SortedList<T>::iterator(n);
   }

   // Case 4

   // Find the place where to insert the new Node.
   Node* iter = front_;
   for ( ; iter != nullptr && data < iter->data_; iter = iter->prev_ );

   // Insert the new Node.
   Node* prev = iter->prev_
   Node* n = new Node(data, iter, prev);
   prev->next_ = n;
   iter->prev_ = n;
   return SortedList<T>::iterator(n);
}
0
R Sahu 19 oct. 2017 a las 15:33