ajout ou insertion enfin dans une liste doublement chaînée

Question

J'essaie d'insérer une valeur à la fin d'une liste doublement chaînée, je réussis à insérer la valeur en tête ou au premier nœud mais la deuxième valeur n'est pas insérée

Le problème ici est lors de la saisie de la deuxième valeur

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

Vous rencontrez un certain nombre de problèmes dans votre code :

• Ton node Les membres suivant et précédent ne sont jamais initialisés nulle part et, par conséquent, ne sont pas définis lorsqu'ils sont utilisés.Soit ajouter un constructeur à node ou assurez-vous qu’ils sont initialisés après l’attribution.
• L'ajout d'un nœud à une liste vide n'est pas correct. first->next n'est pas défini et pourquoi créez-vous deux nœuds, le premier et le dernier ?Dans une liste avec un élément alors first == last.Le réglage de suivant/précédent en premier/dernier n'a aucun sens non plus.
• Dans une liste double chaînée bien formée alors last->next devrait toujours être nul, tout comme first->previous.
• L'ajout d'un nœud dans une liste non vide est également incorrect.
• Bien que vous ne le montriez pas dans l'exemple, vous aurez éventuellement besoin d'un destructeur ainsi que d'un opérateur de copie et d'un constructeur de copie (la règle de trois).À l'heure actuelle, vous perdez de la mémoire et si vous essayez de supprimer des nœuds, vous entraînerez probablement une double libération et un crash.

Je suggérerais de prendre un peu de recul par rapport au code pour vous assurer de bien comprendre les concepts derrière une liste à double lien.Dessinez une liste sur papier avec les flèches suivant/précédent et voyez comment elles doivent être modifiées lors de l'ajout de nœuds à une liste vide/non vide ainsi que comment supprimer et déplacer des nœuds.Une fois que vous avez compris comment next/prev doit être défini, la traduction en code devrait être relativement simple.

Modifier pour répondre au commentaire :Pour ajouter un nouveau nœud, vous pouvez techniquement l'ajouter n'importe où, mais il est généralement ajouté à la fin (du moins d'après ce que j'ai vu).Voir les autres réponses pour un code complet et correct pour ajouter de nouveaux nœuds dans une liste vide et non vide.

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
  ...

Vous n'ajoutez pas votre nouveau nœud à la liste.

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

devrait être meilleur.Au fait: supprimez la mémoire allouée dans un destructeur!

Answer 3

J'écrirais votre liste double liée au code suivant:

    #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

Pourquoi avez-vous inséré les déclarations node *ptr; et node *toinsert; si vous ne les utilisez pas ?Il devrait également être évident que si vous insérez un seul nœud à la fin, un seul nouvel élément doit être créé (et vous appelez new deux fois si le premier est nul).

Answer 5

Essayez ce code ...

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;
 }