Supprimer le nœud de liste chaînée (de manière récursive)

!=Je suis actuellement en train de travailler sur d'effacement récursif de la fonction bool qui thakes liste et int comme arguments et retourne true si l'int a donc été trouvé et supprimé et false si elle n'a pas été trouvé dans la liste. Il semble fonctionner, mais le problème est qu'il supprime les la prochaine int nombre dans la liste, et pas le courant:

 typedef struct E_Type * List;

 struct E_Type
 {
        int data;
        List next = 0;
 };

bool erase(const List & l, int data){
List current = l;   
if (current == 0)
{
   return false;
 }
else if (current->data == data)
{
      List deleteNode = new E_Type;
     deleteNode = current->next;//probably this causes the error, but how can I point it to the current without crashing the program
     current->next = deleteNode->next;
     delete deleteNode;
     return true;
}

else if (current->data != data)
{
      return erase(current->next, data);
}


}

Éventuellement sans rapport avec: List deleteNode = new E_Type; deleteNode = current->next;? C'est une fuite de mémoire là.
Un plus sans lien de parenté commentaire: quel est le but de else if (current->data > data)? L'instruction return est la même de toute façon.
La déclaration if (current == 0) ne fonctionnera pas, à moins que List est la définition de type d'un pointeur de type ou de la classe surchargé == opérateur qui prend un pointeur d'entier.
oui la Liste est typedef avec poiner à E_Type / R. Martinho vous avez raison, je vais corriger cette fuite, merci
Il y a même plus d'erreurs possibles et les problèmes avec votre code, pourquoi ne pas simplement utiliser les std::list (ou encore mieux, std::vector)?
Je peux, mais ma tâche est d'utiliser la structure suivante Nœud typedef struct E_Type * Liste; struct E_Type { int data; Liste = 0; };
Votre tâche de préciser que la méthode doit être récursive?

InformationsquelleAutor EmilDo | 2012-12-06

c++linked-list

1

Le seul nœud que vous envisagez de courant, de sorte que vous devez avoir une disposition pour la modification de l:
```
if (current->data == data)
{
  l = current->next;
  delete current;
  return true;
}
```
- alors qu'il avait besoin de le pointeur à l', pas la référence, mais qui devrait fonctionner ensuite.
- Non, l est un pointeur, ce qui est passé par référence.
- argh, vous avez raison. Toutes ces années et je continue de se confondre par ce genre de choses o_O
- vous n'êtes pas seul. Pointeurs de fonction encore faire mes oreilles saignent.
- Ouais, il est vraiment déroutant et les renseignements sur les fonctions plus complexes comme c'est rare. Vos suggestions travaillé, merci @Bêta
InformationsquelleAutor Beta
2

Il y a deux type de base de listes:
- unique-les listes chaînées (chaque nœud connaît son prochain nœud) et
- double-listes chaînées (chaque nœud connaît son prochain ainsi que son nœud précédent).
Si, comme dans votre cas, on a une seule liste liée, vous ne devez pas vérifier le nœud COURANT pour que l'égalité de 'données', parce qu'à ce moment, il est trop tard pour changer l'aiguille suivante du dernier nœud. Donc, vous devez toujours vérifier la PROCHAINE pointeur pour l'égalité, comme ceci:
```
bool erase(const List & l, int data)
{
    List current = l;   
    if (current == 0)
        return false;

    //special case: node to be deleted is the first one
    if (current->data == data)
    {
        delete current;
        return true;
    }

    if (current->next && current->next->data == data) //next exists and must be erased
    {
        List deleteNode = current->next;   //Step 1: save ptr to next
        current->next = deleteNode->next;  //Step 2: reassign current->next ptr
        delete deleteNode;                 //Step 3: delete the node
        return true;
    }

    return erase(current->next, data);
}
```
Note: j'ai épargné votre dernier "else if" la condition. Le 'else' parce que la précédente si eu un retour en elle, et le "si", car son état était tout simplement la négation de la précédente "si", ce qui - si le programme est livré ce serait toujours valable.

Ce qui concerne

InformationsquelleAutor euphrat
1

Voici quelques pointeurs.

Une approche itérative

Lorsque vous êtes à l'itération sur votre liste, le maintien d'un pointeur vers la actuel élément n'est pas suffisant. Vous avez également besoin de maintenir un pointeur vers le précédente élément, car vous en aurez besoin pour fixer previous->next si vous supprimez l'élément courant.

En plus de cela, la suppression du premier élément de la liste nécessitent un traitement spécial.

Une approche récursive

Écrire une fonction récursive qui prendra un pointeur vers la tête de la liste, rechercher & supprimer l'élément requis, et retourne un pointeur sur la nouvelle tête de la liste. Pour ce faire, vous devez:
1. Définir et mettre en œuvre le cas de base. La manipulation d'un élément listes semble comme un candidat naturel.
2. Définir la récursivité. Il y a deux cas: soit la tête de liste est l'élément que vous recherchez, ou il ne l'est pas. Comprendre ce que vous devez faire dans les deux cas, et à partir de là.
InformationsquelleAutor NPE
1

Si vous avez une liste:

Un --> B - > C --> D

Et vous voulez supprimer C, vous devez:

Magasin C dans une variable temp

Changement B->next=C->suivant

supprimer C.

Si vous avez besoin de trouver B pour être en mesure de le modifier.

Vous devriez certainement pas de créer une nouvelle instance de E_type.

InformationsquelleAutor Benoit Thiery
1

Votre condition
```
else if (current->data == data)
```
va s'arrêter sur le nœud qui a la données de la valeur. Vous passez ensuite à supprimer le nœud après nœud dans votre code.

Si vous voulez garder le reste du code de même, alors que la ligne doit être :
```
else if ((current->next)->data == data)
```
avec un supplément de vérifier, dans le cas où le premier élément est le seul élément dans la liste.

Un moyen plus simple serait de garder un pointeur qui pointe sur l'élément avant de l'élément en cours, puis de supprimer le nœud qui est référencé par le pointeur.
- c'est une bonne suggestion, merci je vais la mettre en œuvre.
InformationsquelleAutor asheeshr
0

Vous aurez besoin de changer la next pointeur de la précédent entrée. Donc, tout est de trouver, mais vous devez vérifier actuel->next->données contre des données, pas de courant->data.

Assurez-vous de vérifier pour les NULS-les pointeurs dans le cas actuel est la dernière entrée dans la liste!
- Que faire si le premier entrée de la liste est celui qui doit être supprimé?
- Me il, trop 😉 Comme AshRJ écrit, vous auriez besoin de vérifier que, comme bien comme la dernière fois.
InformationsquelleAutor SvenS
0

Lorsque vous supprimez un nœud à partir d'une liste, vous devez pointer le nœud précédent à la suivante. Puisque vous avez une seule liste liée, il y a 2 options:
1. Maintenir un pointeur vers précédente nœud dans votre erase fonction. Lors de la rencontre souhaitée nœud, lien nœud précédent à current->next et supprimer le nœud actuel. Besoin d'un traitement spécial pour le premier noeud de la liste.
2. Lorsque vous rencontrez souhaité nœud, copier le contenu de la current->next en current, puis de les supprimer current->next. De cette façon, vous n'avez pas besoin d'un paramètre supplémentaire dans votre fonction. Besoin d'un traitement spécial pour le dernier nœud de la liste.
- Vous pouvez également copier les données de la prochaine nœud au nœud courant & supprimer le nœud suivant
- N'y a pas pensé, désolé.
- Édité pour ajouter de la deuxième approche.
InformationsquelleAutor prazuber

Vous devez vous connecter pour publier un commentaire.