C++ lié Liste traversal et modification

Question

liste chaînée:

pointer2 -> [a] 
pointer ->[a] -> [b] -> [c] -> [d] -> null  
pointer = b; //makes it point one down so it will be pointer -> [b] ->[c] -> [d] -> null  
pointer = pointer 2; //makes pointer point back to where it was pointing to before, both pointers point to [a] 
pointer2 = pointer->next; //makes pointer 2 point to [b] 
pointer2->next = pointer->next; //makes [c] point to [b] 

Est-ce que je comprends bien? Les nœuds peuvent-ils pointer vers eux-mêmes comme pointeur-> suivant = pointeur-> suivant?

En gros:

• pointeur = pointer2 - faire le point de pointeur sur ce que le pointeur 2 pointait?
• LePointeur-> next = pointer2 - faire noeud de liaison qui pointe le pointeur pour pointer vers pointer2 noeud de liaison
• LePointeur-> next = pointer2-> prochain - faire noeud de liaison qui pointe le pointeur pour pointer vers l'un après pointeur pointeur2 pointer sur
• pointeur = pointeur2-> suivant - fait pointer le pointeur sur le nœud de lien un point après le pointeur 1.

Est-ce exact?

Answer 1

Les nœuds peuvent-ils pointer vers eux-mêmes?

Comme d'autres l'ont dit, c'est certainement possible. Mais peut-être que vous vouliez vraiment dire "est-ce valable?". La réponse à cela est que cela dépend du code qui manipule la liste chaînée. Si vous écrivez ce code, alors c'est à vous de décider si c'est valide. Par exemple, vous pouvez décider que lorsqu'un nœud pointe sur lui-même, alors cela indique la fin de la liste chaînée. Alors voici comment vous pouvez coder une fonction qui recherche une liste chaînée entier pour le nombre 3:

struct ListNode { 
    int value; 
    ListNode* next; 
}; 

bool containsThree(ListNode* list) { 
    for (; list->next != list; list = list->next) { 
     if (list->value == 3) { 
      return true; 
     } 
    } 
    // Also check final node 
    if (list->value == 3) { 
     return true; 
    } 
    return false; 
} 

vous pourriez décider que next == nullptr Sinon signifie la fin de la liste. Dans ce cas containsThree ressemblerait plus à ceci:

bool containsThree(ListNode* list) { 
    for (ListNode* node = list; node; node = node->next) { 
     if (node->value == 3) { 
      return true; 
     } 
    } 
    return false; 
} 

Avec cette nouvelle fonction, le cas échéant points de nœud à lui-même alors la fonction serait boucle pour toujours. Vous pouvez corriger cela, et même vérifier les grandes boucles dans la liste, comme ceci:

bool containsThree(ListNode* list) { 
    std::set<ListNode*> seenNodes; 
    for (ListNode* node = list; node; node = node->next) { 
     if (seenNodes.count(node)) { 
      break; 
     } 
     seenNodes.insert(node); 
     if (node->value == 3) { 
      return true; 
     } 
    } 
    return false; 
} 

Il y a un problème avec cette dernière fonction: il a une pénalité de performance significative par rapport à la précédente. C'est donc à vous de décider si les boucles de votre liste sont autorisées et si vous acceptez de les vérifier dans vos fonctions, ou si les boucles ne sont pas autorisées. L'un ou l'autre est correct, il suffit de prendre une décision et de s'y tenir.

(Edit: La première fonction d'exemple est un peu en désordre parce que la condition qui se termine la boucle le fait juste avant nous recherchons 3 dans le dernier nœud Il est également impossible de passer dans une liste vide les deux.. les problèmes sont corrigés dans les exemples nullptr, mais il est en fait possible de les corriger même en utilisant la règle "node == node->next signifie la fin de la liste" La clé consiste à ajouter un nœud factice à la fin de la liste chaînée Vous n'avez pas besoin de vérifier ce nœud pour trois-ness, et un tel nœud représente une liste vide.)

Answer 2

Vous avez raison exect pour la dernière affectation du pointeur:

... 
pointer2 = pointer->next; //makes pointer 2 point to [b]: Ok 
pointer2->next = pointer->next; //makes [c] point to [b]: Wrong 

pointer2 des points à [b], et pointer->next points b. La dernière affectation de pointeur faire des points b se conduisant à:

pointer2 -> b -> b ! 

et:

pointer -> a -> b -> b 

Vous malentendu peut provenir du fait que votre code pseudo n'est pas explicite sur ce que sont a, b, c et d, qu'est-ce qui représente la prochaine et où vous utilisez les adresses. Ecrire tout ceci est en C++ et ce sera plus clair.

Answer 3

Linked data structure a un pointeur pour les données actuelles, un pour le suivant (qui est le pointeur vers les données actuelles du suivant) et si doublement lié, puis un vers le précédent (qui est le pointeur vers les données actuelles du précédent).

Les nœuds peuvent-ils pointer vers eux-mêmes? comme pointeur-> suivant = pointeur-> suivant?

Oui. C'est la même chose que d'assigner un pointeur à lui-même. Pas très utile.

• LePointeur-> next = pointer2-> prochain - faire noeud de liaison qui pointe le pointeur pour pointer vers l'un après noeud de liaison qui pointer2 points
• pointeur = pointer2-> prochain - faire Pointeur pointant vers le noeud de liaison un après le pointeur pointé vers.

Après cela, cependant, le pointeur de données en cours et pointeur suivant de données sont les mêmes et le point de même. Cela signifie que si quelqu'un veut traverser cette liste chaînée, il peut se retrouver en boucle infinie s'il n'a pas de pointeur.