Je dois écrire une fonction qui ajoutera des éléments à C-struct, mais elle ne peut pas ajouter le même élément. Exemple:
Saisir:
1 2 1 3
Sortie:
bool add(Node*& head, int data){
Node *n = new Node;
n->data = data;
n->next = 0;
if(!head)
head = n;
else{
Node *tmp = head;
while(tmp->next)
tmp = tmp->next;
tmp->next = n;
}
};
Les éléments sont extraits d'un tableau, voici un morceau de code qui utilise la fonction dont j'ai besoin pour écrire:
struct Node {
int data;
Node* next;
};
C-struct Node ressemble à ça:
int tab[] = {1,4,1,3,5};
Node* head = 0;
for (size_t i = 0, e = std::size(tab); i != e; ++i) {
bool b = add(head,tab[i]);
cout << tab[i] << (b ? " " : " NOT ")
<< "added" << endl;
}
Voici ce que j'ai écrit, mais il ajoute tous les éléments du tableau. Je ne peux pas changer la boucle, seulement la fonction add :
ADDED 1 ADDED 2 NOT ADD 1 ADD 3
3 Réponses :
actuellement, vous ajoutez simplement l'élément sans chercher s'il est déjà présent ou non
La définition peut être quelque chose comme
Node::Node(int d) : next(0), data(d) {
}
// add should be a static method of Node, to be able to access next and data while they are private
bool add(Node*& head, int data){
if(!head) {
head = new Node(data);
return true;
}
Node *tmp = head;
while (tmp->next) {
if (tmp->data == data)
return false;
tmp = tmp->next;
}
if (tmp->data == data)
return false;
tmp->next = new Node(data);
return true;
}
Je vous encourage à ajouter un constructeur pour ne pas avoir à définir les données et les champs suivants à chaque fois après avoir créé une nouvelle instance
Exemple
bool add(Node*& head, int data){
if(!head) {
head = new Node;
n->data = data;
n->next = 0;
return true;
}
Node *tmp = head;
while (tmp->next) {
if (tmp->data == data)
return false;
tmp = tmp->next;
}
if (tmp->data == data)
return false;
tmp->next = new Node;
tmp->next->data = data;
tmp->next->next = 0;
return true;
}
Merci pour votre contribution, mais non, je ne peux pas ajouter les mêmes données
J'ai supposé que seul le résultat était pertinent, j'ai édité ma réponse pour ne pas l'ajouter si elle était déjà présente
Je ne suis pas le bownvoter, mais je dois dire: que ajoutez fonctionne trop de choses. Puisque nous faisons C-isms: il devrait y avoir un nœud * node_new (int) , un bool node_isnil (noeud *) , un nœud nœud_last ( Noeud *) et un bool node_find (int) .
Doit être while (tmp) pas while (tmp-> next) car il ne trouvera pas l'élément qui est le dernier dans la liste.
@john non, le while recherche le dernier élément pour ajouter le nouveau après lui, avec while (tmp) comment pouvez-vous ajouter le nouvel élément à la fin de la liste?
@bruno Vous avez raison, vous ne pouvez pas ajouter un nouvel élément avec une boucle comme while (tmp) mais vous ne pouvez pas rechercher toute la liste avec une boucle comme while (tmp-> next ) . Les deux opérations sont différentes.
@Bruno J'ai pris votre code, corrigé les erreurs de compilation (variable non déclarée n) changé l'entrée en int tab [] = {1,1}; la sortie était 1 ajouté 1 ajouté
oh oui quand j'ai changé la définition j'ai supprimé le test au bout d'un moment, je l'ai réintroduit
@bruno ok, vote vers le bas supprimé, la vôtre est la meilleure réponse
@PaulSanders que voulez-vous dire? new Node (..) renvoie une nouvelle instance de Node
@PaulSanders Je ne comprends pas, mon constructeur est juste Node :: Node (int d): next (0), data (d) {}
@PaulSanders J'ai ajouté une nouvelle ligne entre le '{' et le '}' au cas où il était moins lisible quand tout était sur la même ligne
Voici ma tentative. Recherchez les données existantes premier em> Ajoutez s'il n'est pas présent (pas de changement de code existant) bool add(Node*& head, int data) {
Node *tmp = head;
while (tmp) {
if (tmp->data == data)
return false; // data already present
tmp = tmp->next;
}
Node *n = new Node;
n->data = data;
n->next = 0;
if (!head) {
head = n;
}
else {
Node *tmp = head;
while(tmp->next)
tmp = tmp->next;
tmp->next = n;
}
return true; // data added
}
quelle mauvaise idée de parcourir la liste 2 fois!
@bruno, très vrai, je laisserai cette amélioration au PO
J'ai donc fait quelque chose comme ça et cela fonctionne avec les données dont je dispose. Je suppose que cela fonctionne en général
bool add(Node*& head, int data){
Node *n = new Node;
n->data = data;
n->next = 0;
if(!head)
head = n;
else{
Node *tmp = head;
while(tmp->next){
if(tmp->data == data)
return false;
else
tmp = tmp->next;
}
tmp->next = n;
}
};
Il alloue inutilement un nœud même s'il ne sera pas utilisé.
C'est vrai, mon mal. Merci de l'avoir remarqué
Il ne trouve pas non plus un élément égal lorsqu'il s'agit du dernier élément de la liste.
vous faites une fuite de mémoire
Ce que vous devez faire est de changer votre code
addde sorte que if recherche d'abord l'élément dans la liste, en utilisant une boucle, et ne l'ajoutez que s'il ne le trouve pas. Cela semble être une chose évidente à faire, sur quelle partie êtes-vous coincé?Je ne sais pas comment parcourir la liste pour trouver le même élément
Quelle est exactement votre question? Il n'y a aucune question dans votre message de question. Note latérale: il n'y a pas besoin de
ifdansadd, vous pouvez fairewhile (head) head = head-> next;.@Mrfk Vous parcourez déjà la liste dans le bloc
else. Dans le blocwhile, vérifiez simplement la valeur detmp-> dataet si c'est la même chose quedata, abandonnez l'opération.C'est une simple boucle,
Node * tmp = head; while (tmp) {if (tmp-> data == data) {trouvé} tmp = tmp-> next; }Cela semble plus facile que le code que vous avez déjà écrit mais je suppose que les pointeurs sont difficiles.Merci pour la note latérale, je vais changer cela. Ma question est la suivante: comment itération par des éléments de noeuds pour trouver s'il y a les mêmes éléments
Il vous manque les valeurs de retour de
add. Activez tous les avertissements pour votre compilateur, cela vous aidera à trouver ce genre d'erreurs.@WernerHenze Êtes-vous sûr?
Merci les gars, je sais quoi faire maintenant. Je vais réécrire la fonction pour qu'elle ait plus de sens
@Mrfk avertissement, ne vous trompez pas de réponse lol