Ajouter une fonction dans une liste doublement liée entraîne une boucle infinie

Question

J'ai eu des problèmes pour programmer une liste doublement chaînée. Le problème est que ma fonction Add aboutit à une boucle infinie quand je vérifie si les liens sont nullptr. Quand je ne le fais pas, cela me donne une erreur. J'ai essayé de régler cela et pour la vie de moi ne peux pas le comprendre. Voici la méthode d'addition:

void Add(string n, int w) //Method to add a node to the Linked List and maintain the order. 
{ 

    node * nd = new node(n, w, nullptr, nullptr); 

    if (nHead == nullptr && wHead == nullptr) //If there is nothing in the Linked List 
    { 
     nHead = nd; //Add a node 
     wHead = nd; 
    } 

    else //If there is something in the linked List 
    { 
     node * ntraverse = nHead; //variable to traverse down the name links 

     while (nd->name > ntraverse->name && ntraverse->wLink != nullptr) 
     { 
      ntraverse = ntraverse->nLink; // Traverses down the name links until nd's name is smaller than a links 
     } 

     nd->nLink = ntraverse; // Here, the namelink for nd is set to ntraverse, since ntraverse is less than or equal to nlink 
     ntraverse->nLink = nd; // So here, since nd is the new value appended to the rest of the list, we set ntraverse = nlink. 

           // note at this point, we have not handled weight 

     node * wtraverse = wHead; //variable to traverse down the weight links 

     while (nd->weight > wtraverse->weight && wtraverse->wLink != nullptr) 
     { 
      wtraverse = wtraverse->wLink; // Traverses down the weight links until nd's weight is smaller than a links 
     } 

     nd->wLink = wtraverse; // Here, the namelink for nd is set to ntraverse, since ntraverse is less than or equal to nlink 
     wtraverse->wLink = nd; // So here, since nd is the new value appended to the rest of the list, we set ntraverse = nlink. 

     //at this point, nd holds both the correct nlink and wlink 

    } 

    cout << "Added: " << nd->name << " " << nd->weight << "\n"; 
    cout << "Current nlist:\n"; 
    nPrint(); 
    cout << "Current wlist:\n"; 
    wPrint(); 

    size++; //increment size 

} 

Toute aide serait grandement appréciée. Si vous avez besoin de moi pour répondre à quelque chose, s'il vous plaît faites le moi savoir. Le nœud fonctionne correctement, il stocke 4 valeurs: nom, poids, nLink et wLink, où nLink conserve la liste ordonnée par nom et wLink conserve la liste ordonnée au poids. Pour LinkedList, nHead est la tête de nom et wHead est la tête de poids.

Encore une fois, merci pour votre aide.

Answer 1

Vous vous mixer wLink et nlink ensemble

node * ntraverse = nHead; //variable to traverse down the name links 

while (nd->name > ntraverse->name && ntraverse->wLink != nullptr) 

Dans ce qui précède, vous traversons les liens de nom et de test pour voir si vous êtes à la fin de la liste de poids.

Ceci n'est pas une liste doublement chaînée, il s'agit de deux listes simples et vous devez traiter chaque liste séparément.

En d'autres termes, votre code devrait ressembler à ceci:

void Add(string n, int w) //Method to add a node to the Linked List and maintain the order. 
{ 

    node * nd = new node(n, w, nullptr, nullptr); 

    if (nHead == nullptr) //If there is nothing in the Linked List 
    { 
     nHead = nd; //Add a node 
    } 


    else //If there is something in the linked List 
    { 
     /* Code to handle nLink with no mention of wLink */ 
    } 

    if (wHead == nullptr) //If there is nothing in the Linked List 
    { 
     wHead = nd; //Add a node 
    } 


    else //If there is something in the linked List 
    { 
     /* Code to handle wLink with no mention of nLink */ 
    } 

} 

Bien sûr, la solution idéale serait d'écrire une classe de liste chaînée ....

Answer 2

Alors je me suis ce que le problème était. À la fin de chaque boucle, j'avais

nd->wLink = wtraverse; // Here, the namelink for nd is set to ntraverse, since ntraverse is less than or equal to nlink 
    wtraverse->wLink = nd; // So here, since nd is the new value appended to the rest of the list, we set ntraverse = nlink. 

Cela créait une boucle circulaire. Le lien de nd stocke wtraverse, et le lien de wtraverse est stocké nd, ce qui signifie que l'un des liens pointe vers une autre partie de la liste. En ce qui concerne l'argument sémantique sur la terminologie de la liste à liaison double, mon professeur en structures de données fait référence à une structure de données dans laquelle le nœud a deux liens sous la forme d'une liste à double liaison. Qu'elle soit correcte ou non, argumenter sémantique était de peu d'aide et n'a rien fait pour résoudre le problème.