Fusion de 2 listes chaînées et ajout à la fin des listes chaînées c ++

Je n’ai pas grand chose pour l’instant mais j’essaie de comprendre comment utiliser des listes chaînées.

Struct:

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

Comment puis-je append un nœud à la fin de la liste? J’essaie simplement de prendre un pointeur pour le début d’une liste et une valeur int à append en tant que nouveau nœud. Lorsque j’essaie d’exécuter ce que j’ai actuellement, je reçois une exception.

 void addNode(Node* head, int x) { Node* temp = new Node; temp->data = x; temp->next = NULL; if(!head) { head = temp; return; } else { Node* last = head; while(last->next) last=last->next; last->next = temp; } } 

Je n’ai pas vraiment commencé à fusionner les deux listes. Je sais juste que je dois prendre 2 listes chaînées (ou des pointeurs vers la tête de 2 listes chaînées?), Puis parcourir les listes pour tous les nœuds.

EG: La liste liée 1 comprend 3 nœuds: 4, 10, 20. La liste chaînée 2 comprend 4 nœuds: 2, 5, 15, 60.

La fonction de liste de fusion créerait une nouvelle liste chaînée avec 2,4,5,10,15,20,60 en tant que nœuds.

EDIT: J’appelle la fonction addNode de la manière suivante:

 Node *head = new Node; insertAtEnd(head,20); 

Est-ce correct ou cela pourrait-il être la cause de l’exception?

En faisant cela:

 void addNode(Node* head, int x) // here ---------^ 

et puis plus tard ceci:

  head = temp; // here 

vous modifiez simplement le pointeur d’en- head local, qui prend la valeur d’adresse transmise par l’appelant. Puisque head n’est pas une référence réelle à un pointeur (il s’agit simplement d’un pointeur), le pointeur de l’appelant est passé, car head rest inchangé. Vous n’ajoutez jamais le nœud alloué à votre liste, vous perdez de la mémoire, cela devient un jour sortingste …

Passez le pointeur par référence à la place. En corrigeant cela, puis en fixant le membre de data invalide, qui devrait en réalité être une value et un pointeur à pointeur permettant de parcourir la liste pour trouver la fin, le résultat pourrait ressembler à ceci:

 #include  struct Node { int value; Node *next; }; void addNode(Node*& head, int x) { Node **pp = &head; while (*pp) pp = &(*pp)->next; *pp = new Node; (*pp)->value = x; (*pp)->next = nullptr; } void printList(const Node *head) { for (; head; head = head->next) std::cout << head->value << ' '; std::cout << '\n'; } void freeList(Node *&head) { while (head) { Node *p = head; head = p->next; delete p; } } int main() { Node *head = nullptr; for (int i=1; i<=5; ++i) addNode(head, i); printList(head); freeList(head); } 

Sortie

 1 2 3 4 5 

Je vous laisse la tâche de mettre en œuvre une fusion réelle, mais cela devrait suffire à vous fournir une liste gérable et opérationnelle.


Mise à jour: à partir de la question modifiée du PO:

 Node *head = new Node; insertAtEnd(head,20); 

En plus d'être une fonction nommée complètement différente, votre nœud est initialisé par défaut. Dans votre cas, cela signifie le Node résultant du new Node; a des valeurs indéterminées pour la value et la next . Vous transmettez ensuite cela à votre fonction, qui suppose une valeur déterminée (null) pour terminer votre boucle.

Cela peut être corrigé de plusieurs façons. la mécanique du code ci-dessus en est un exemple. Il n'est pas nécessaire de pré-allouer un nœud principal en premier lieu si le code de gestion de liste comprend que NULL signifie "non-liste". Votre post original addNode semblait au moins essayer de suivre ce mantra.

Déclarez la fonction de la manière suivante

 void addNode( Node* &head, int x) ; 

Et au lieu de cet extrait de code

 Node *head = new Node; insertAtEnd(head,20); 

Vous devez appeler la fonction la première fois de la manière suivante

 Node *head = nullptr; // or NULL addNode(head,20); 

Notez qu’il n’y a pas de fonction avec le nom insertAtEnd dans votre message. Il y a la fonction addNode . 🙂

Si vous avez besoin de fusionner deux listes, vous pouvez utiliser ce programme de démonstration comme exemple. Bien sûr, vous devrez append d’autres fonctions, par exemple supprimer des listes pour obtenir un projet complet.

 #include  struct Node { int value; Node *next; }; Node * insert( Node *current, int value ) { Node *tmp; if ( current == nullptr ) { tmp = new Node { value, nullptr }; } else { tmp = new Node { value, current->next }; current->next = tmp; } return tmp; } std::ostream & display( Node *head, std::ostream &os = std::cout, const char *delimiter = " " ) { for ( ; head; head = head->next ) os << head->value << delimiter; return os; } Node * merge( Node * &head1, Node * &head2 ) { Node *new_head = nullptr; Node *current = nullptr; while ( head1 != nullptr && head2 != nullptr ) { Node *tmp; if ( head2->value < head1->value ) { tmp = head2; head2 = head2->next; } else { tmp = head1; head1 = head1->next; } tmp->next = nullptr; if ( new_head == nullptr ) { new_head = tmp; current = new_head; } else { current->next = tmp; current = current->next; } } if ( head1 != nullptr ) new_head == nullptr ? new_head : current->next = head1; if ( head2 != nullptr ) new_head == nullptr ? new_head : current->next = head2; head2 = nullptr; head1 = new_head; return new_head; } int main() { Node *list1 = nullptr; Node *list2 = nullptr; list1 = insert( list1, 4 ); insert( insert( list1, 10 ), 20 ); display( list1, std::cout << "List1: " ) << std::endl; list2 = insert( list2, 2 ); insert( insert( insert( list2, 5 ), 15 ), 60 ); display( list2, std::cout << "List2: " ) << std::endl; std::cout << std::endl; merge( list1, list2 ); display( list1, std::cout << "List1: " ) << std::endl; display( list2, std::cout << "List2: " ) << std::endl; return 0; } 

La sortie du programme est

 List1: 4 10 20 List2: 2 5 15 60 List1: 2 4 5 10 15 20 60 List2: 

cela peut être une cause d’exception:

 struct Node { int value; <----- Node structure has value property Node *next; }; Node* temp = new Node; temp->data = x; <------ Assigning to data property of Node which does not exists temp->next = NULL; 

Pour append une liste, vous pouvez utiliser la même approche

 void addNode(Node* head, Node* head2) { Node* last = head; while(last->next) last=last->next; last->next = head2; } 

EDIT: Dans ma partie principale, j’appelle la fonction addNode de la manière suivante:

 Node *head = new Node; insertAtEnd(head,20); 

C’est faux. Vous n’avez pas initialisé head->next , donc dans insertAtEnd le code while(last->next) last=last->next; tentera de comparer le pointeur non initialisé et, s’il n’est pas nul, le déréférencera. Cela va probablement bloquer votre programme plutôt que de lancer une exception. Là encore, c’est un comportement indéfini, donc tout peut arriver.

Puisque votre fonction d’insertion couvre déjà le cas de l’insertion dans une liste vide, j’appellerais simplement

 head = nullptr; insertAtEnd(head,20)`; 

De plus, il y a le problème de ne jamais mettre à jour le pointeur principal en dehors de la fonction, ce qui a déjà été couvert dans d’autres réponses.