Probleme de suppression d'un noeud dans une liste chaînée [Résolu]

Signaler
Messages postés
47
Date d'inscription
samedi 7 janvier 2006
Statut
Membre
Dernière intervention
13 décembre 2012
-
Messages postés
47
Date d'inscription
samedi 7 janvier 2006
Statut
Membre
Dernière intervention
13 décembre 2012
-
Hola hola !

J'ai un petit problème pour supprimer un un noeud dans une liste chaînée. Bien sur ce n'est pas si simple, mais je vais vous expliquer au mieux.

J'ai un gros tas de rectangle dans une image que je dois lier les uns aux autres suivant plusieurs critères. Afin de trouver le meilleur agencement possible, j'ai créer une classe Node (noeud de ma liste chaînée) me permettant de stocker un de ces liens.
J'ai donc un bel arbre doublement chaîné représentant tous les cas possibles.
Certain des critères s'applique une fois cet arbre créé et il me faut donc l'élaguer. C'est ici que situe mon problème.
Lorsque j'essaye de supprimer un noeud, une fois sur deux tout va bien et l'autre fois je reçois un "EXC_BAD_ACCESS, Could not access memory"…

ThinTree représente mon arbre, Node to delete et le noeud que je veux supprimer.

Si vous avez besoin de plus d'info n'hésitez pas !
Merci d'avance !!!!!!!

(Je suis sous mac et les traces que vous verrez viennent de gdb. J'utilise openCV)

#ifndef __NODE_HPP__
#define __NODE_HPP__


#include <opencv2/opencv.hpp>
#include <vector> 
#include <list>


namespace myNamespace
{
class Node
{
public:
Node();
Node(std::vector<cv::Rect*>* iLine, cv::Rect* iBlock, Node* iPrev, bool iToAvoid=false);

const std::list<Node*>& getNext() const;
std::list<Node*>& getNextInstance();
const std::vector<cv::Rect*>* getLine() const;
std::vector<cv::Rect*>* getLineInstance();
const cv::Rect* getBlock() const;
cv::Rect* getBlockInstance();

void addNext(Node* aNode);

void thinOut(cv::Rect** lastAimedBlock);
void contains(std::vector<cv::Rect*>* myLine, cv::Rect *myBlock, bool& verif);
void deleteNode(std::vector<cv::Rect*>* myLine, cv::Rect *myBlock);
void setToAvoidFlag(bool flagValue);
bool getAValidCase();
void clean();

void display(std::string str);

private:
std::vector<cv::Rect*>* _line;
cv::Rect* _block;
std::list<Node*> _next;
Node* _prev;
bool _toAvoid;

void thinOut (Node *currentNode, std::map<cv::Rect*, int>& scoresMap, cv::Rect** lastAimedBlock);
void avoidSonsNodes (Node* currentNode);
void avoidParentsNodesUntil(Node* currentNode, cv::Rect* aimedBlock, std::map<cv::Rect*, int>& scoresMap, bool flag);
bool getNonToAvoidNextNode(Node *currentNode);
void contains(Node *currentNode, std::vector<cv::Rect*>* myLine, cv::Rect *myBlock, bool& verif);
void deleteNode(Node *currentNode, std::vector<cv::Rect*>* myLine, cv::Rect *myBlock, bool& verif);
void setToAvoidFlag(Node *currentNode, bool flagValue);
void clean(Node *currentNode);

void display(Node* currentNode, int cpt);

};
}

#endif 



Je vous épargne lecture de l'ensemble du .cpp et je vous montre simplement le vilain petit canard


void Node::deleteNode(Node *currentNode, std::vector<cv::Rect*>* myLine, cv::Rect *myBlock, bool& verif)
{
if(currentNode->_prev != NULL)   //to avoid the root (the root just gets nexts and NULL for other var
LOG("   line(" << currentNode->_line->back()->x << "," << currentNode->_line->back()->y << ")  block (" << currentNode->_block->x << "," << currentNode->_block->y << ")", 3);
if (currentNode->_line myLine && currentNode->_block myBlock)
{
// Erases currentNode from prev->next
currentNode->_prev->_next.remove(currentNode);

// Pushing currentNode->next into ->prev->next
for (std::list<Node*>::iterator nextIt=currentNode->_next.begin(); nextIt!=currentNode->_next.end(); ++nextIt)
{
currentNode->_prev->_next.push_back(*nextIt);
}

delete currentNode;
verif = true;

return;
}
else
{
for (std::list<Node*>::iterator nextIt=currentNode->_next.begin(); nextIt!=currentNode->_next.end(); ++nextIt)
{
deleteNode(*nextIt, myLine, myBlock, verif);

if (verif == true)
{
return;
}
}
}
}



Les traces d'executions :


20120628-2100-4036-3442 : <node.cpp:84> --------------- ThinTree ---------------
20120628-2100-4036-3442 : <node.cpp:85>  Node level 0 :  Root  nbNext = 1
20120628-2100-4036-3442 : <node.cpp:97>  Node level 1 :  line(126,64)   block(237,46)   nbNext 1   toAvoid 1   ptr = 0x1011aa980
20120628-2100-4036-3442 : <node.cpp:97>  Node level 2 :  line(125,48)   block(237,46)   nbNext 1   toAvoid 1   ptr = 0x1011aa9d0
20120628-2100-4036-3442 : <node.cpp:97>  Node level 3 :  line(199,76)   block(237,46)   nbNext 0   toAvoid 1   ptr = 0x1011aaa70
20120628-2100-4036-3442 : <node.cpp:90> ----------------------------------------

20120628-2100-4036-3442 : <cmdCreateLines.cpp:435> Node to delete : line (199,76)   block (237,46)

Program received signal EXC_BAD_ACCESS, Could not access memory.
Reason: 13 at address: 0x0000000000000000
0x000000010009c71b in std::_List_iterator<skerou::Node*>::operator++ (this=0x7fff5fbf5ee0) at stl_list.h:142
142		_M_node = _M_node->_M_next;
(gdb) bt
#0  0x000000010009c71b in std::_List_iterator<skerou::Node*>::operator++ (this=0x7fff5fbf5ee0) at stl_list.h:142
#1  0x00000001000b0f24 in std::list<myNamespace::Node*, std::allocator<myNamespace::Node*> >::remove (this=0x1011aaa30, __value=@0x7fff5fbf72c0) at list.tcc:182
#2  0x00000001000acdc0 in myNamespace::Node::deleteNode (this=0x1011aa950, currentNode=0x1011aaa70, myLine=0x1011aa6f0, myBlock=0x1011aa0b0, verif=@0x7fff5fbfae07) at node.cpp:262
#3  0x00000001000ad596 in myNamespace::Node::deleteNode (this=0x1011aa950, currentNode=0x1011aa9d0, myLine=0x1011aa6f0, myBlock=0x1011aa0b0, verif=@0x7fff5fbfae07) at node.cpp:280
#4  0x00000001000ad596 in myNamespace::Node::deleteNode (this=0x1011aa950, currentNode=0x1011aa980, myLine=0x1011aa6f0, myBlock=0x1011aa0b0, verif=@0x7fff5fbfae07) at node.cpp:280
#5  0x00000001000ad596 in myNamespace::Node::deleteNode (this=0x1011aa950, currentNode=0x1011aa950, myLine=0x1011aa6f0, myBlock=0x1011aa0b0, verif=@0x7fff5fbfae07) at node.cpp:280
#6  0x00000001000adf09 in myNamespace::Node::deleteNode (this=0x1011aa950, myLine=0x1011aa6f0, myBlock=0x1011aa0b0) at node.cpp:248
#7  0x0000000100097b49 in myNamespace::CmdCreateLines::linkBlocksWithLines (this=0x7fff5fbfd998) at cmdCreateLines.cpp:442
#8  0x000000010009b5be in myNamespace::CmdCreateLines::execute (this=0x7fff5fbfd998, lines=@0x7fff5fbfdb30) at cmdCreateLines.cpp:104
#9  0x0000000100016c14 in myNamespace::ReceiptSection::createLinesFromContours (this=0x10115e360) at receiptSection.cpp:292
#10 0x00000001000182fa in myNamespace::ReceiptSection::analyse (this=0x10115e360) at receiptSection.cpp:129
#11 0x0000000100006a07 in myNamespace::Receipt::buildStructure (this=0x10115b320) at receipt.cpp:138
#12 0x0000000100006de0 in myNamespace::Receipt::analyse (this=0x10115b320) at receipt.cpp:116
#13 0x00000001000b2ae1 in main (argc=-1, argv=0x7fff5fbff698) at main.cpp:83
#14 0x0000000100000d64 in start ()

6 réponses

Messages postés
47
Date d'inscription
samedi 7 janvier 2006
Statut
Membre
Dernière intervention
13 décembre 2012

Problem solved !

Un oeil extérieur m'a fait remarquer que je ne modifiais pas la valeur de prev pour les fils du noeud détruit. Ils gardaient donc un pointeur vers un objet inexistant...
Messages postés
47
Date d'inscription
samedi 7 janvier 2006
Statut
Membre
Dernière intervention
13 décembre 2012

Je viens de voir que les traces ne sont pas complètes, voici les bonnes :

20120628-2100-4036-3442 : <node.cpp:84> --------------- ThinTree ---------------
20120628-2100-4036-3442 : <node.cpp:85>  Node level 0 :  Root  nbNext = 1
20120628-2100-4036-3442 : <node.cpp:97>  Node level 1 :  line(126,64)   block(237,46)   nbNext 1   toAvoid 1   ptr = 0x1011aa980
20120628-2100-4036-3442 : <node.cpp:97>  Node level 2 :  line(125,48)   block(237,46)   nbNext 1   toAvoid 1   ptr = 0x1011aa9d0
20120628-2100-4036-3442 : <node.cpp:97>  Node level 3 :  line(199,76)   block(237,46)   nbNext 0   toAvoid 1   ptr = 0x1011aaa70
20120628-2100-4036-3442 : <node.cpp:90> ----------------------------------------

20120628-2100-4036-3442 : <cmdCreateLines.cpp:403> Last aimed block : (237,46)

20120628-2100-4036-3442 : <cmdCreateLines.cpp:435> Node to delete : line (199,76)   block (237,46)

20120628-2100-4036-3442 : <node.cpp:257>    line(126,64)  block (237,46)
20120628-2100-4036-3442 : <node.cpp:257>    line(125,48)  block (237,46)
20120628-2100-4036-3442 : <node.cpp:257>    line(199,76)  block (237,46)

Program received signal EXC_BAD_ACCESS, Could not access memory.
Reason: 13 at address: 0x0000000000000000
0x000000010009c71b in std::_List_iterator<myNamespace::Node*>::operator++ (this=0x7fff5fbf5ee0) at stl_list.h:142
142		_M_node = _M_node->_M_next;
(gdb) bt
#0  0x000000010009c71b in std::_List_iterator<myNamespace::Node*>::operator++ (this=0x7fff5fbf5ee0) at stl_list.h:142
#1  0x00000001000b0f24 in std::list<myNamespace::Node*, std::allocator<myNamespace::Node*> >::remove (this=0x1011aaa30, __value=@0x7fff5fbf72c0) at list.tcc:182
#2  0x00000001000acdc0 in myNamespace::Node::deleteNode (this=0x1011aa950, currentNode=0x1011aaa70, myLine=0x1011aa6f0, myBlock=0x1011aa0b0, verif=@0x7fff5fbfae07) at node.cpp:262
#3  0x00000001000ad596 in myNamespace::Node::deleteNode (this=0x1011aa950, currentNode=0x1011aa9d0, myLine=0x1011aa6f0, myBlock=0x1011aa0b0, verif=@0x7fff5fbfae07) at node.cpp:280
#4  0x00000001000ad596 in myNamespace::Node::deleteNode (this=0x1011aa950, currentNode=0x1011aa980, myLine=0x1011aa6f0, myBlock=0x1011aa0b0, verif=@0x7fff5fbfae07) at node.cpp:280
#5  0x00000001000ad596 in myNamespace::Node::deleteNode (this=0x1011aa950, currentNode=0x1011aa950, myLine=0x1011aa6f0, myBlock=0x1011aa0b0, verif=@0x7fff5fbfae07) at node.cpp:280
#6  0x00000001000adf09 in myNamespace::Node::deleteNode (this=0x1011aa950, myLine=0x1011aa6f0, myBlock=0x1011aa0b0) at node.cpp:248
#7  0x0000000100097b49 in myNamespace::CmdCreateLines::linkBlocksWithLines (this=0x7fff5fbfd998) at cmdCreateLines.cpp:442
#8  0x000000010009b5be in myNamespace::CmdCreateLines::execute (this=0x7fff5fbfd998, lines=@0x7fff5fbfdb30) at cmdCreateLines.cpp:104
#9  0x0000000100016c14 in myNamespace::ReceiptSection::createLinesFromContours (this=0x10115e360) at receiptSection.cpp:292
#10 0x00000001000182fa in myNamespace::ReceiptSection::analyse (this=0x10115e360) at receiptSection.cpp:129
#11 0x0000000100006a07 in myNamespace::Receipt::buildStructure (this=0x10115b320) at receipt.cpp:138
#12 0x0000000100006de0 in myNamespace::Receipt::analyse (this=0x10115b320) at receipt.cpp:116
#13 0x00000001000b2ae1 in main (argc=-1, argv=0x7fff5fbff698) at main.cpp:83
#14 0x0000000100000d64 in start ()




Je vous donne aussi la fonction suivante qui est indispensable pour lire la trace


void Node::deleteNode(std::vector<cv::Rect*>* myLine, cv::Rect *myBlock)
{
bool verif = false;
deleteNode(this, myLine, myBlock, verif);
}
Messages postés
3813
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
12 juin 2020
107
Bonjour.

Tu as résolu ton problème avant qu'on est eu le temps de t'aider, félicitation :D !

J'ai tout de même quelques remarques, qui ne sont pas directement liées à ta question, mais plus à la vue de ton code:
- void display(std::string str); => void display(const std::string& str); éviterait une copie.
- Dès le moment ou tu as un "return", pas besoin de "else" juste après.
- Un booléen se vérifie naturellement et non envers une valeur (c'est le principe du booléen). Donc on écrirait plutôt dans ce style: "if (verif)" et "if (!verif)". À noter que c'est une inélégance, mais pas une erreur technique de faire "verif == true".
- Évite l'emploi de "NULL", c'est parfois trompeur. Il préférable d'utiliser "0" ou mieux encore "nullptr" si tu as accès au C++0x. (Voir ici pour l'explication du problème: http://0217021.free.fr/portfolio/axel.berardino/articles/null-en-cpp).
- Préfère "erase" à "remove". Remove essaie de détruire *tous* les éléments qui sont identiques à celui que tu donnes, tandis que erase efface un élément en particulier. (currentNode étant un pointeur dont l'adresse est unique, tu as de la chance et ça fonctionne. Mais attention à ce petit détail qui pourrait être la source de bug si tu l'utilisais sur une liste dont les éléments ne seraient pas uniques). Niveau performance, remove parcourt toute ta liste...
- Si une méthode n'utilise pas les membres de ta classe, et n'a pas vocation à être vu de l'extérieur, alors ça devrait être une fonction visible uniquement dans ton fichier de code de la classe dans un namespace anonyme. Si elle a vocation à être visible, une méthode statique est à envisager.

Ces remarques étaient mineures, ce qui me choque un peu c'est plus que tu (re)codes une liste chaînée. En effet, dans la STL tu as déjà des listes chaînées !
- std::list => liste doublement chaînée.
- std::forward_list => liste simplement chaînée. (À partir de C++0x).

C'est d'autant plus étrange que tu utilises une liste doublement chaînées à l'intérieur de ta liste chaînée (_next).
N'ayant pas l'intégralité du code sous les yeux, il m'est difficile de te dire si l'emploi d'une liste chaînée est ici judicieuse. Je vais me contenter d'en rappeler les cas d'usages.
Une liste chaînées est toujours moins intéressante qu'un tableau sauf:
- Si on doit insérer souvent au milieu de la liste.
- Si on doit supprimer souvent au milieu de la liste.
- Si on doit échanger souvent des éléments.
- Si on doit fusionner des listes entre elles.

Si tu n'es pas dans ce cas, alors un tableau (std::vector) sera bien plus adapté (surtout si tu te contentes de faire des ajouts en queue).
En espérant que ces quelques remarques t'aideront.



________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question
Messages postés
47
Date d'inscription
samedi 7 janvier 2006
Statut
Membre
Dernière intervention
13 décembre 2012

Merci de tes remarques ! Je viens d'en appliquer certaine mais j'ai des questions sur d'autres.

- Dès le moment ou tu as un "return", pas besoin de "else" juste après.

Je vois pas trop quoi changer. Pour moi le else est là pour gérer les 2 cas :
-on est sur le noeud, on le supprime
-on est ailleurs, on continue de parcourir l'arbre


- Si une méthode n'utilise pas les membres de ta classe, et n'a pas vocation à être vu de l'extérieur, alors ça devrait être une fonction visible uniquement dans ton fichier de code de la classe dans un namespace anonyme. Si elle a vocation à être visible, une méthode statique est à envisager.

Tu parles des 2 fonctions delete? L'une est appelée depuis l'extérieur, l'autre est private car elle n'a pas à être visible.


- Évite l'emploi de "NULL", c'est parfois trompeur. Il préférable d'utiliser "0" ou mieux encore "nullptr" si tu as accès au C++0x. (Voir ici pour l'explication du problème: http://0217021.free.fr/portfolio/axel.berardino/articles/null-en-cpp).

Ca je suis fan !! Mais je n'ai pas la possibilité d'intégrer la norme C++0x au projet


Pour ce qui est de l'utilisation d'une std::list pour créer une liste chaînée, je pense effectivement qu'il y a quelque chose à faire. Je n'ai pas poussez assez loin mon apprentissage de la stl et c'est bien dommage.. L'utilisation d'un liste est par contre indispensable pour l'ensemble de mon algo. J'ai essayé au départ d'utiliser un tableau mais je ne m'y retrouvais pas.
Messages postés
3813
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
12 juin 2020
107
Je vois pas trop quoi changer. Pour moi le else est là [...]


void Node::deleteNode(Node *currentNode, std::vector<cv::Rect*>* myLine, cv::Rect *myBlock, bool& verif)
{
  //...
  if (currentNode->_line myLine && currentNode->_block myBlock)
  {
    //...
    verif = true;
    return;
  }

  for (std::list<Node*>::iterator nextIt=currentNode->_next.begin(); nextIt!=currentNode->_next.end(); ++nextIt)
  {
   deleteNode(*nextIt, myLine, myBlock, verif);
   if (verif)
     return;
  }


Tu parles des 2 fonctions delete? L'une est appelée depuis l'extérieur, l'autre est private car elle n'a pas à être visible.

Ta fonction "deleteNode" par exemple, n'utilise aucun membre de ta classe. Elle pourrait donc être une fonction plutôt qu'une méthode.
De plus, étant privée, on peut alors la transformer:
- Tu la retires du header.
- Tu la mets en haut de ton fichier de code, comme ceci:
namespace
{
  void deleteNode(Node *currentNode, std::vector<cv::Rect*>* myLine, cv::Rect *myBlock, bool& verif)
  {
    //...
  }
} // namespace


D'une manière générale, si une méthode n'utilise aucun membre de classe, c'est qu'elle devrait être une fonction anonyme privée ou une fonction publique statique.

L'utilisation d'un liste est par contre indispensable pour l'ensemble de mon algo. J'ai essayé au départ d'utiliser un tableau mais je ne m'y retrouvais pas.

Attention, en théorie, le choix d'une structure de donnée doit se faire en fonction de la contrainte de performance et/ou d'algorithme, et non de la facilité d'utilisation. Dans la pratique, si tu es plus à l'aise avec ceci, pourquoi pas. Note juste qu'il y a un point perfectible dans ton code (ce qui te servira si on te demande plus tard d'améliorer les performances ou la stabilité de celui-ci).

________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question
Messages postés
47
Date d'inscription
samedi 7 janvier 2006
Statut
Membre
Dernière intervention
13 décembre 2012

Parfait, c'était une bonne leçon !

Merci