Codage d’une fonction pour copier une liste liée en C ++

La première question que vous devez vous poser est de savoir quelle est la sémantique de la copie. En particulier, vous utilisez Student* comme contenu de nœud. Que signifie copier le contenu d’un nœud? Devrions-nous copier le pointeur de manière à ce que les deux listes pointent vers (partager) les mêmes instances d’étudiant, ou devez-vous effectuer une copie en profondeur ?

 struct Listnode { Student *student; // a pointer? shouldn't this be a `Student` object? Listnode *next; }; 

La prochaine question que vous devriez vous poser est de savoir comment vous allez affecter les nœuds pour la deuxième liste. Actuellement, vous n’allouez qu’un seul noeud dans la copie.

Je pense que votre code devrait ressembler davantage à:

 Listnode *SortedList::copyList(Listnode *L) { Listnode *current = L; // Assume the list contains at least 1 student. Listnode *copy = new Listnode; copy->student = new Student(*current->student); copy->next = NULL; // Keep track of first element of the copy. Listnode *const head = copy; // 1st element already copied. current = current->next; while (current != NULL) { // Allocate the next node and advance `copy` to the element being copied. copy = copy->next = new Listnode; // Copy the node contents; don't share references to students. copy->student = new Student(*current->student); // No next element (yet). copy->next = NULL; // Advance 'current' to the next element current = current->next; } // Return pointer to first (not last) element. return head; } 

Si vous préférez partager des instances d’étudiant entre les deux listes, vous pouvez utiliser

 copy->student = current->student; 

au lieu de

 copy->student = new Student(*current->student); 

C’est une excellente question puisque vous avez fait le gros du travail vous-même, bien mieux que la plupart des questions “S’il vous plaît, faites mes devoirs à ma place”.

Quelques points.

Tout d’abord, qu’advient-il si vous passez dans une liste vide? Vous voulez probablement rattraper votre retard et renvoyer une liste vide à l’appelant.

Deuxièmement, vous n’allouez que le premier noeud de la liste de copie, vous devez en effectuer un par noeud dans la liste d’origine.

Quelque chose comme (pseudo-code (mais semblable à C ++) pour les devoirs, désolé):

 # Detect empty list early. if current == NULL: return NULL; # Do first node as special case, maintain pointer to last element # for appending, and start with second original node. copy = new node() last = copy copy->payload = current->payload current = current->next # While more nodes to copy. while current != NULL: # Create a new node, tracking last. last->next = new node() last = last->next # Transfer payload and advance pointer in original list. last->payload = current->payload current = current->next # Need to terminate new list and return address of its first node last->next = NULL return copy 

Et, bien que vous ayez raison de ne pas renvoyer de pointeur sur une variable de stack locale, ce n’est pas ce que vous faites. La variable que vous renvoyez pointe vers la mémoire allouée au tas , qui survivra à la sortie de la fonction.

J’ai essayé de faire la même chose. Mes exigences étaient:

1. Chaque nœud est une classe très basique et simple (je me suis éloigné du modèle struct).
2. Je souhaite créer une copie complète, et pas seulement un pointeur sur l’ancienne liste chaînée.

La façon dont j’ai choisi de faire cela est avec le code C ++ suivant:

 template  Node  * copy(Node  * rhs) { Node  * current = new Node(); Node  * pHead = current; for (Node  * p = rhs; p; p = p->pNext) { Node  * prev = current; prev->data = p->data; if (p->pNext != NULL) { Node  * next = new Node(); prev->pNext = next; current = next; } else { prev->pNext = NULL; } } return pHead; } 

Cela fonctionne bien, sans erreur. Parce que la “tête” est un cas particulier, il est nécessaire que je mette en œuvre un pointeur “actuel”.

L’instruction copy->next = current->next est fausse. Tu devrais faire

 Create the first node copy here copy->student = current->student; copy->next = NULL; while(current->next!=NULL) { Create new node TEMP here copy->next = TEMP; TEMP->student = current->student; TEMP->next = NULL; copy = TEMP; } 

Étant donné que vous avez besoin d’une copie de la liste liée, vous devez créer un nouveau nœud dans la boucle tout en parcourant la liste d’origine.

 Listnode *startCopyNode = copy; while (current != NULL) { *(copy->student) = *(current->student); copy->next = new Listnode; copy = copy->next; current = current->next; } copy->next = NULL; return startCopyNode; 

N’oubliez pas de delete les nœuds de la liste liée.

@pat, je suppose que vous obtiendrez un seg_fault, car vous créez la mémoire une seule fois. Vous devez créer de la mémoire (en gros, appeler «nouveau») pour chaque noeud. Découvrez où vous devez utiliser le mot-clé “nouveau” pour créer de la mémoire pour tous les nœuds.

Une fois que vous avez terminé, vous devez le lier au nœud précédent, car il s’agit d’une liste à liaison unique, vous devez conserver un pointeur sur le nœud précédent. Si vous voulez apprendre et devriez être capable de vous souvenir de toute la vie, ne voyez aucun des codes mentionnés ci-dessus. Essayez de penser aux facteurs mentionnés ci-dessus et essayez de créer votre propre code.

Comme d’autres l’ont fait remarquer, vous devez appeler new pour chaque nœud de la liste d’origine pour allouer de l’espace pour une copie, puis copier l’ancien nœud sur le nouveau et mettre à jour le pointeur dans le nœud copié.

Un autre facteur que je rencontre avec cette fonction est l’idée de retourner un pointeur sur une variable locale.

Vous ne renvoyez pas de pointeur sur une variable locale; lorsque vous avez appelé new , vous avez alloué de la mémoire sur le tas et y avez renvoyé un pointeur (ce qui signifie bien sûr que vous devez vous rappeler d’appeler delete pour le libérer lorsque vous avez terminé avec la nouvelle liste, en dehors de la fonction).