Problème avec les listes chainées

Version imprimable

Salut tout le monde,

SVP, j'ai écrit un petit code qui me permet d'ajouter un nouvel élément dans une liste chainée,

Code:

1
2
3
4
5
6
7
8
9
void RA_Blocks::ajouter (RA_Page rap)
{
	liste *nouv;
	nouv=new liste;
	nouv->rapage=rap;
	nouv->suiv=Les_RA_Pages;
	Les_RA_Pages=nouv;
	nb_ra_pages++;
}

la définition de la classe est la suivante :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#if !defined(AFX_RA_BLOCKS_H__AF8B6C62_E94D_4F27_97BF_961318027A4F__INCLUDED_)
#define AFX_RA_BLOCKS_H__AF8B6C62_E94D_4F27_97BF_961318027A4F__INCLUDED_
 
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
 
#include "RA_Page.h"
 
struct liste{
	RA_Page rapage;
	liste *suiv;
};
 
class RA_Blocks 
{
 
  public:
	RA_Blocks();
	RA_Blocks(int n, liste *list);
	RA_Blocks(const RA_Blocks &right);
	~RA_Blocks();
	RA_Blocks & operator=(const RA_Blocks &right);
	int operator==(const RA_Blocks &right) const;
	int operator!=(const RA_Blocks &right) const;
	void ajouter (RA_Page rap);
	void afficher ();
	int nb_RA_Page ();
 
  private: 
      liste *Les_RA_Pages;
	  int nb_ra_pages;
 
};
 
#endif

Quand je compile, 0 Errors et 0 Warnings
Mais quand j'exécute, ca se bloque, ca passe pas 8O

je ne sais vraiment pas d'où ca vient.

merci d'avance
Bien cordialement

19/04/2008, 23h57
IrmatDen

Salut,

Ne crée pas ta propre structure, utilise l'officielle et correcte std::list (edit: surtout que là tu n'as même pas la notion de conteneur, tu as juste déclaré la composition d'un maillon de la liste ;))
20/04/2008, 01h17
reeda

Citation:

Envoyé par IrmatDen

Salut,

Ne crée pas ta propre structure, utilise l'officielle et correcte std::list (edit: surtout que là tu n'as même pas la notion de conteneur, tu as juste déclaré la composition d'un maillon de la liste ;))

salut,

je crois que je n'ai pas compri ta réponse,
un petit boue de code qui explique ca, m'aiderai à mieux comprendre votre réponse.:D

merci d'avance
Bien cordialement
20/04/2008, 02h37
coyotte507

Salut,

je crois que le meilleur moyen de trouver ce qui cloche dans un code est de le débugger. Peux-tu fournir un code assez complet pour être compilable?

La classe template std::list permet de créer des listes chainées d'éléments du même type, quelqu'il soit. Il suffit d'inclure <list>
20/04/2008, 15h40
HanLee

Petit tutorial : http://cpp.developpez.com/cours/stl/#LIII-A

Citation:

Envoyé par IrmatDen

Salut,

Ne crée pas ta propre structure, utilise l'officielle et correcte std::list (edit: surtout que là tu n'as même pas la notion de conteneur, tu as juste déclaré la composition d'un maillon de la liste ;))

La notion de conteneur est une notion qui "vient du C++", son "maillon" correspond très bien à la définition récursive d'une liste par contre.

Mais ne crois pas que je ne l'encourage pas à utiliser std::list hein.

Salut,

Je crains que le problème soit principalement algorithmique...

Déjà, il me semblerait utile de donner des noms plus explicite à tes types et à tes membres, et, sans doute, de rajouter un pointeur sur le dernier élément de la liste ;).

Ainsi, ta classe liste représente, en réalité, un maillon, et je te proposerais donc de la renommer en "Maillon", pour lui donner une forme proche de

Code:

1
2
3
4
5
6
7
8
9
10
11
12
struct Maillon
{
    RA_page page;
    Maillon * suivant;
    /* je rajoute un constructeur dont je m'assure qu'il ne servira pas
     * d'opérateur de conversion implicite
     */
    explicit Maillon(const RA_page& page, Maillon * suivant=NULL):page(page),
    suivant(suivant)
    {
    }
};

Par contre, la classe RA_Blocks est... la liste en elle-même, et je t'encouragerais donc à renommer en... Liste, en lui donnant la forme de

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Liste
{
    public:
        Liste();
	Liste(int n, Maillon*list);/* j'ai laissé n, mais il n'est pas forcément nécessaire ;) */
	Liste(const Liste &right);
	~Liste();
	Liste & operator=(const RA_Blocks &right);
	int operator==(const Liste &right) const;
	int operator!=(const Liste &right) const;
	void ajouter (RA_Page rap);
	void afficher ();
        /*Autant rester "const correct" ;) */
	size_ nb_RA_Page () const; /* voir plus bas pour "size_t" */
   private:
        /* en ayant le premier et le dernier élément de la liste, tu te
         * donne l'occasion de rajouter un élément en fin de liste en 
         * temps constant
         * en plus, cela te facilitera le travail si tu décide un jour de 
         * permettre l'insertion en début de liste ;)
         */
        Maillon * premier; /* le premier élément de la liste */
        Maillon * derenier;/* le dernier élément de la liste */
        /* comme il n'y aura jamais... -1 éléments, autant utiliser une valeur
         * non signée, dont on est sur qu'elle permettra de représenter
         * l'ensemble des valeurs "potentielles" ;)
         */
        size_t nb_maillon; /* le nombre d'éléments dans la liste */
};

L'implémentation des méthodes prendrait la forme de

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
/*création d'une liste vide */
Liste::Liste():premier(NULL),dernier(NULL),nb_maillon(0)
{
}
/* n ne sera pas utilisé ;) */
Liste::Liste(int n, Maillon *list):premier(NULL),dernier(NULL)
{
    /* nous allons créer une boucle qui va copier chacun des maillons 
     * reçu par le constructeur
     */
    while(liste!=NULL)
    {
        /* on copie le maillon */
        Maillon * temp=new Maillon(list->page);
        /* C'est peut être le premier maillon */
        if(!premier)
        {
            /* dans ce cas, temp est tout à la fois premier et dernier maillon */
            premier=temp;
         }
         else
         {
             /* sinon, on lie le dernier maillon à temp */
             dernier->suivant=temp;
             /* et temp devient le dernier maillon */
         }
         /* et, bien sur, on incrémente le nombre de maillon */
         dernier=temp;
         ++nb_maillon;
    }
}
/* Le constructeur par copie travaille exactement de la meme manière:
 * En effet, on  ne peut pas se permettre de faire partager les maillons par
 * plusieurs listes
 */
Liste::Liste(const Liste &right):premier(NULL),dernier(NULL),nb_maillon(0)
{
    /* nous allons créer une boucle qui va copier chacun des maillons 
     * reçu par le constructeur
     */
    Maillon list=right->premier;
    while(list!=NULL)
    {
        /* on copie le maillon */
        Maillon * temp=new Maillon(list->page);
        /* C'est peut être le premier maillon */
        if(!premier)
        {
            /* dans ce cas, temp est tout à la fois premier et dernier maillon */
            premier=temp;
         }
         else
         {
             /* sinon, on lie le dernier maillon à temp */
             dernier->suivant=temp;
         }
         /* et temp devient le dernier maillon */
         dernier=temp;
         /* et, bien sur, on incrémente le nombre de maillon */
         ++nb_maillon;
    }
}
/* le destructeur s'occupe de détruire tous les maillons */
Liste::~Liste()
{
 
    while(premier!=NULL)
    {
        /* on garde une trace de l'élément qui suit le premier maillon */
        Maillon * temp=premier->suivant;
        /* on libère la mémoire du premier maillon */
        delete premier;
        /* l'élément qui suivait le premier maillon devient premier maillon */
        premier = temp;
    }
}
/* Je te laisse du travail pour les opérateurs d'affectation et 
 * de comparaison, ainsi que les accesseurs simples ;)
 */
void Liste::ajouter(RA_Page rap)
{
    /* je considère que, ici, on ajoute d'office en fin de liste ;) 
     * L'idéal serait toute fois d'avoir
     *    -AjouterDebut
     *    -AjouterFin
     *    -AjouterApres(element, a_ajouter)
     *    -éventuellement, pouvoir passer des Maillons directement comme
     *     surcharge de ces trois méthodes ;)
     */
    /* on crée le nouveau maillon */
    Maillon * temp=new Maillon(rap);
    /*c'est peut etre le premier maillon de la liste */
    if(!premier)
    {
        premier = temp;
    }   
    else
    {
        dernier->suivant=temp;
    }
    dernier=temp;
    ++nb_maillon;
}

Maintenant, il faut savoir que le C++ fournit une classe qui permet de travailler de manière bien plus simple, même si, pour l'instant, il ne s'agit que d'une liste "doublement chainée" (la prochaine norme devrait fournir une classe de liste "simplement chainée): la classe list, disponible dans l'espace de noms std en incluant le fichier d'en-tête <list>

20/04/2008, 21h02
IrmatDen

Citation:

Envoyé par HanLee

La notion de conteneur est une notion qui "vient du C++", son "maillon" correspond très bien à la définition récursive d'une liste par contre.

Mais ne crois pas que je ne l'encourage pas à utiliser std::list hein.

Non non :) Merci de la précision au contraire.
21/04/2008, 12h45
reeda

salut les amis,

je vous remerci beaucoup pour toutes vos réponses, elles sont toutes trés interessantes.

Mais je crois que le problème que j'ai viens du fait que mon projet est un peu lourd car j'implémente une structure de données un peu complexe, il y a en tout 7 classes, chacune contient des pointeurs, des objets d'autres classes, ...

Quand j'ai voulu faire un grand exemple même d'autres fonctions que j'utilisais sans problème sur des exemples plus petits ne marchent plus maintenant.

Ca donne le truc de :
http://5oufich.ifrance.com/upload/nepaenvoyer.bmp

Donc je ne pense pas que c'est un problème qui vient du code mais plutot de la mémoire, et la liste chainnée que je veux créer se bloque parce que celle ci contient des objets d'un type qui rassemble toutes les classes créés dans mon projet.

Et j'ai remarqué aussi que ce problème survient quand je crée un pointeur sur un objet des classes de mon projet.

Et maintenant, je ne sais plus quoi faire.

P.S. : j'utilise VC++ 6.0 comme EDI

Merci beaucoup
Bien cordialement
22/04/2008, 09h30
Médinoc

Compile le projet en mode Debug, lance-le dans le debugger de Visual, et lors du plantage, regarde où ça plante...
La fenêtre "call stack" peut t'être utile...
23/04/2008, 12h42
reeda

Citation:

Envoyé par Médinoc

Compile le projet en mode Debug, lance-le dans le debugger de Visual, et lors du plantage, regarde où ça plante...
La fenêtre "call stack" peut t'être utile...

oké merci, je vais essayer votre proposition.
J'ai remarqué aussi que ce problème se manifest quand j'oubli d'initialiser un pointeur.

Bien cordialement
23/04/2008, 16h21
koala01

Citation:

Envoyé par reeda

oké merci, je vais essayer votre proposition.
J'ai remarqué aussi que ce problème se manifest quand j'oubli d'initialiser un pointeur.

Bien cordialement

C'est peut etre tout simplement là, le problème :D

En mode "debug", tu peux, parfois, trouver des pointeur initialisés d'office à NULL (ou à 0), mais, en mode release, si tu n'initialise pas un pointeur, sa valeur d'origine est... tout et n'importe quoi (la valeur qui se trouve en mémoire de la dernière fois qu'elle a été utilisée... y compris par d'autres applications... autrement dit: des crasses :D)

C'est l'une raisons principales pour lesquelles on déconseille toujours très fortement l'utilisation des pointeurs, à moins qu'il n'y ai pas moyen de faire autrement, et que l'on conseille toujours d'utiliser des classes dont on soit sur qu'elles ont été triturées et testées dans tous les sens...

La bibliothèque standard est l'une des bibliothèques fournissant des classes entrant dans cette catégorie ;):D