C++ Girl
  1. C++ Girl
  3. Échange d’éléments adjacents de la liste chaînée
Intereting Posts
Compilateurs GNU vs Visual Studio sur des tableaux alloués avec une constante de longueur avec une scope Définir l’affinité processeur pour le moteur MATLAB (Windows 7) L’initialisation de liste et la résolution de surcharge ayant échoué du constructeur initializer_list Comment appeler un pointeur sur une fonction membre lorsqu’il s’agit d’un membre de données de classe? OpenCV: comment visualiser une image de profondeur Qu’est-ce qu’une méthode ‘const’ peut changer? Interruption SNMP non reconnue par le gestionnaire Ordre de destruction des éléments d’un std :: vector Qt: signification de la valeur de retour de la fente? template template parameters et clang Détruire correctement les pointeurs dans un std :: map Avantages de l’utilisation de reference_wrapper au lieu du pointeur brut dans les conteneurs? Comment puis-je connaître la légèreté d’un tableau en C ++ Absence d’opérateur typeof en C ++ 03? Quelle est une bonne alternative aux espaces de noms au sein des classes?

Échange d’éléments adjacents de la liste chaînée

Ci-dessous se trouve mon code pour échanger de manière récursive les éléments adjacents d’une liste chaînée. Je perds le pointeur à chaque deuxième élément après l’échange. L’entrée est 1-> 2-> 3-> 4-> 5-> 6-> 7, je m’attendais à la sortie 2-> 1-> 4-> 3-> 6-> 5-> 7, mais ma sortie est 1-> 3-> 5-> 7. 

void nodelist::swap(node* head) { node* temp = head->next; if (head->next!= nullptr) { node* temp2 = temp->next; temp->next = head; head->next = temp2; head = head->next; temp = nullptr; temp2 = nullptr; swap(head); } }

Toute aide serait appréciée, merci d’avance.

En fait, il suffit d’échanger uniquement les données membres des nœuds. Il n’est pas nécessaire d’échanger les pointeurs eux-mêmes.

Néanmoins, si vous utilisez votre approche, la fonction peut ressembler à 

 void SwapList( node *head ) { if ( head != nullptr && head->next != nullptr ) { node *next = head->next; std::swap( *head, *next ); std::swap( head->next, next->next ); SwapList( head->next->next ); } }

Voici un programme démonstratif 

 #include  #include  struct node { int value; node *next; }; node * AddNode( node *head, int value ) { head = new node { value, head }; return head; } void PrintList( node *head ) { for ( ; head != nullptr; head = head->next ) { std::cout << head->value << ' '; } } void SwapList( node *head ) { if ( head != nullptr && head->next != nullptr ) { node *next = head->next; std::swap( *head, *next ); std::swap( head->next, next->next ); SwapList( head->next->next ); } } int main() { node *head = nullptr; for ( int i = 10; i != 0; ) { head = AddNode( head, --i ); } PrintList( head ); std::cout << std::endl; SwapList( head ); PrintList( head ); std::cout << std::endl; return 0; }

La sortie est 

 0 1 2 3 4 5 6 7 8 9 1 0 3 2 5 4 7 6 9 8

Vous pouvez utiliser la fonction affichée comme modèle (ou base) pour votre fonction.

Sans récursion: 

 void swap(node **head) { while (*head && (*head)->next) { node* tmp = *head; *head = tmp->next; tmp->next = (*head)->next; (*head)->next = tmp; head = &tmp->next; } }

Appelez swap( & list_head_ptr) .

Sinon, vous pouvez passer le pointeur principal par référence à un pointeur et utiliser un membre pointeur à pointeur local: 

 void swap(node*& head) { node **pp = &head; while (*pp && (*pp)->next) { node* tmp = *pp; *pp = tmp->next; tmp->next = (*pp)->next; (*pp)->next = tmp; pp = &tmp->next; } }

et invoquer comme swap(list_head_ptr) . Les deux méthodes fonctionnent.

Utiliser la récursion: 

 void nodelist::swap(node** head) { if (!*head || !(*head)->next) return; node* const sw = (*head)->next; (*head)->next = sw->next; sw->next = *head; *head = sw; swap(&(sw->next->next)); }

Si head est le pointeur qui stocke l’adresse de firstNode (value=1) , essayez alors la fonction suivante: 

 void nodelist::swap(node* head){ node* temp = head->next; //head->next is first-node which needs to switch with it's next node if (temp!= nullptr && temp->next!=nullptr){ head->next=temp->next; //move second node to first temp->next = head->next->next; //put second's next in first's head->next->next = temp; //and first will be second's next temp = nullptr; // swaping done swap(head->next->next); //do it for next couple } }

http://coliru.stacked-crooked.com/a/e1cc0d02b5599da4

OU

http://coliru.stacked-crooked.com/a/a1e200b687825d80

Si head est lui head même le premier firstNode (value=1) , alors passer head par valeur ne fonctionnera pas, vous devez soit le passer par adresse / référence, soit le faire comme dans le lien suivant:

http://coliru.stacked-crooked.com/a/a1e200b687825d80