Apprendimento o inserimento finalmente in un elenco doppiamente collegato

Question

Sto cercando di inserire un valore alla fine di un elenco doppiamente collegato, ho successo nell'inserire il valore alla testa o al primo nodo, ma il secondo valore non viene inserito

Il problema qui è immettere il secondo valore

class d_list
{
private:

    struct node
    {
        double data;
        node *next;
        node *previous;
    };

    node *first;
    node *last ;
public:
    d_list(void)
    {
        first = nullptr;
        last = nullptr;
    };
    void append(double);

};

void d_list::append(double num)
{
    node *ptr;
    node *toinsert;
    if(!first)
    {
        first = new node;
        first->previous= nullptr;
        first->data = num;
        last= new node;
        first->next= last->previous;
        last->previous = first->next;
        last->next= nullptr;

    }
    else
    {
        if(last->next == nullptr)
        {
            ptr = new node;
            ptr->next =last->previous;
            ptr->data=num;
            last->previous = ptr->next  ;
        }


        last->next= nullptr;
    }

}


int _tmain(int argc, _TCHAR* argv[])
{
    d_list aa;
    cout<<"going to append first"<<endl;
    aa.append(44);
    cout<<"going to append second"<<endl;
    aa.append(50.5);

    return 0;
}

Answer 1

Hai una serie di problemi nel tuo codice:

• Tuo node I membri successivi e precedenti non vengono mai inizializzati da nessuna parte e di conseguenza non sono definiti quando usati. O aggiungere un costruttore a node o assicurarsi che siano inizializzati dopo l'allocazione.
• L'aggiunta di un nodo a un elenco vuoto non è corretta. first->next È rimasto indefinito e perché stai creando due nodi, entrambi i primi e gli ultimi? In un elenco con un elemento allora first == last. L'impostazione del prossimo/precedente in primo/ultimo non ha alcun senso.
• In un elenco a doppio legame ben formato quindi last->next dovrebbe sempre essere nullo, come dovrebbe first->previous.
• Anche l'aggiunta di un nodo in un elenco non vuoto è errata.
• Sebbene non lo mostri nell'esempio, alla fine avrai bisogno di un distruttore e di un operatore di copia e di un costruttore di copie (la regola di tre). Al momento stai perdendo la memoria e se provi a eliminare i nodi probabilmente si tradurrai in un doppio e si arrestano in crash.

Suggerirei di fare un passo indietro dal codice per assicurarti di comprendere correttamente i concetti alla base di una lista doppiamente collegata. Disegna un elenco su carta con frecce Next/Prev e vedere come devono essere modificati quando si aggiungono nodi a un elenco vuoto/non vuoto e come eliminare e spostare i nodi. Una volta capito come dovrebbe essere impostato il prossimo/Prev, tradurlo in codice dovrebbe essere relativamente semplice.

Modifica per rispondere al commento: per aggiungere un nuovo nodo puoi aggiungerlo tecnicamente ovunque, ma di solito viene aggiunto alla fine (almeno da quello che ho visto). Vedi le altre risposte per un codice completo e corretto per l'aggiunta di nuovi nodi in un elenco vuoto e non vuoto.

Answer 2

...
if(last->next == nullptr)
{
  ptr = new node;
  ptr->next =last->previous; // <- is not correct
  ptr->data=num;
  last->previous = ptr->next  ; // <- does not do anything useful
  ...

Non aggiungi il tuo nuovo nodo all'elenco.

...
if(!last->next)
{
  ptr = new node;
  ptr->previous=last->previous;
  ptr->next =last;
  ptr->data=num;
  last->previous = ptr  ;
  ...

dovrebbe essere migliore. A proposito: elimina la memoria assegnata in un distruttore!

Answer 3

Scriverei il tuo doppio elenco collegato nel seguente codice:

    #include <iostream>
    using namespace std;
    class d_list
    {
    private:

        struct node
        {
            double data;
            node *next;
            node *previous;
        };

        node *first;
        // node *last ; no need for bidirectional list
    public:
        d_list(void)
        {
            first = nullptr;
            //last = nullptr;
        };
        void append(double);

    };

    void d_list::append(double num)
    {
        node *ptr = new node;
        ptr->data = num;
        node *toinsert;
        if(!first)
        {
            first = ptr;
            first->previous=first->next=first;
        }
        else
        {
            if(first->next == first)
            {
                ptr->next = ptr->previous = first;
                first->next = first->previous = ptr;
            }
            else{
                node *last = first->previous;
                ptr->next = first;
                ptr->previous = last;
                last->next = ptr;
                first->previous = ptr;
            }
        }
    }


    int _tmain(int argc, _TCHAR* argv[])
    {
        d_list aa;
        cout<<"going to append first"<<endl;
        aa.append(44);
        cout<<"going to append second"<<endl;
        aa.append(50.5);

        return 0;
    }

Answer 4

Perché hai inserito le dichiarazioni node *ptr; e node *toinsert; Se non li usi? Inoltre, dovrebbe essere ovvio che se si inserisce un singolo nodo alla fine, dovrebbe essere creato solo un nuovo elemento (e si chiama nuovo due volte se il primo è null).

Answer 5

Prova questo codice ...

class d_list 
{


private:
      struct node
      {
         double data;
         node *next;
         node *previous;
     };
      node *first;
     node *last ;

 public:
     d_list(void)
     {
         first = nullptr;
         last = nullptr;
     };

     void append(double);
  }; 

 void d_list::append(double num)
 {
     node *ptr;
     node *toinsert;
     if(!first)
     {
         first = last = new node;
         first->previous= nullptr;
         first->next = nullptr;
         first->data = num;
     }
     else
     {
             ptr = new node;
             ptr->next =last->previous;
             ptr->data=num;
             last->previous = ptr->next  ;
     }
  }


 int _tmain(int argc, _TCHAR* argv[])
 {
     d_list aa;
     cout<<"going to append first"<<endl;
     aa.append(44);
     cout<<"going to append second"<<endl;
     aa.append(50.5);
      return 0;
 }