Partage

Listes chainées

31 mars 2008 à 14:47:28

Bonjour à tous !

J'ai un petit soucis avec les listes chainées. J'ai définit une structure pour ma liste et créé deux fonctions, l'une pour ajouter des éléments et l'autre pour libérer la mémoire en fin d'exécution. Sauf que mon prog, lorsque je me contente de créer un élément, d'afficher une des variables membres et de supprimer l'élément me dit qu'il a rencontrer une erreur et doit fermer... Je n'ai pas d'erreur ou de warning à la compilation.
J'avoue n'avoir pas tant chercher tout seul, mais j'aime pas trop jouer avec ma mémoire quand je suis pas sur que je laisse pas trainer des morceaux de progs après exécution. Est-ce que quelqu'un pourrait m'aider pour rendre le code correct ?

Le header

#ifndef DEF_ELEMENTSERPENT
#define DEF_ELEMENTSERPENT
#include <iostream>
struct ElementSerpent
{
ElementSerpent *elementPrecedent;
int direction;
int x;
int y;
ElementSerpent *elementSuivant;
};
ElementSerpent* ajouterElementInFine(ElementSerpent *serpent, int x, int y, int direction);
void supprimerListe(ElementSerpent *serpent);
#endif

Les fonctions :

#include "ElementSerpent.h"
ElementSerpent* ajouterElementInFine(ElementSerpent *serpent, int x, int y, int direction)
{
ElementSerpent *element = new ElementSerpent;
element->x = x;
element->y = y;
element->direction = direction;
element->elementSuivant = NULL;
if(serpent == NULL)
{
return element;
}
else
{
ElementSerpent *temp = serpent;
while(temp->elementSuivant != NULL) //On parcourt la liste tant qu'il y a des éléments
{
temp = temp->elementSuivant;
}
temp->elementSuivant = element; //comme il n'y a pas d'élément en fin de liste, on peut ajouer le nouveau
return serpent;
}
}
void supprimerListe(ElementSerpent *serpent)
{
ElementSerpent *temp = serpent;
while(temp->elementSuivant != NULL)
{
temp = temp->elementSuivant;
delete temp->elementPrecedent;
}
delete temp;
}

le main :

#include <iostream>
#include "ElementSerpent.h"
using namespace std;
int main()
{
ElementSerpent *serpent;
serpent = ajouterElementInFine(serpent, 5, 5, 1);
cout << serpent->x;
supprimerListe(serpent);
return 0;
}

Merci d'avance !

MatteX

31 mars 2008 à 15:46:06

Pense RAII et encapsule les opérations sur la liste dans une classe, tu vas adorer!

Surtout le destructeur qui peut libérer la mémoire dès que la liste n'existe plus.

savais-tu que tu peux encapsuler une classe/struct dans une autre classe?

class MaListe
{
private:
struct Element
{
TYPE val;
Element * p_prec;
Element * p_suiv;
Element( TYPE v )
: val( v ), p_prec( 0 ), p_suiv( 0 )
{}
Element( TYPE v, Element * prec, Element * suiv )
: val( v ), p_prec( prec ), p_suiv( suiv )
{}
};
Element * tete_;
Element * pied_;
public:
//...
};

La structure Element appartient à MaListe en privé, donc n'est accessible qu'à l'intérieur de la classe.

Il ne te reste qu'à programmer les opérations d'ajout, d'insertion, de lecture, d'élimination et toute celle qui pourraient t'être utiles.

lmghs

31 mars 2008 à 16:07:26

Citation : MatteX

Pense RAII et encapsule les opérations sur la liste dans une classe, tu vas adorer!

Dans ce cas particulier, il y a un petit bémol. Les destructions se feront de façon récursive, et la pile d'appel a une taille max.

Sinon, entièrement d'accord à la séparation liste<->chainon.

MatteX

31 mars 2008 à 17:23:07

Citation : lmghs

Dans ce cas particulier, il y a un petit bémol. Les destructions se feront de façon récursive, et la pile d'appel a une taille max.

Je pense qu'on peut facilement faire la destruction de façon itérative pour éviter le dépassement de la pile!

lmghs

31 mars 2008 à 17:47:01

Oui. Surtout s'il y a la distinction liste/chainon.

Nataniel

31 mars 2008 à 19:28:28

Ok merci bien... mais y a un léger soucis... j'ai pas compris un traitre mot de tout ça passé encapsulation...

Je m'en va donc faire quelque recherche pour pile et destruction récursive ou itératives

chlablak

31 mars 2008 à 19:36:41

si jamais il y a la STL (meme si c'est interessant de savoir comment ca marche): cf FAQ de developpez pour un bon point de depart

C++ Références | Idiomes | FAQ

Nataniel

31 mars 2008 à 19:40:41

J'ai maté le tuto du site sur les piles et les files... ça m'amène à me demander si c'est bien celle dont vous parlez. parce que je vois pas très bien pourquoi elle serait plus limitée que ce que j'ai de mémoire. Et puis, c'est pas vraiment une pile que j'ai créé. Enfin, c'était pas le but en tout cas. Je vais voir ce que je peux faire avec des objets mais pour ce qui est de mon code actuel, quelqu'un voit-il le problème ?

chlablak

31 mars 2008 à 19:53:23

la pile (memoire automatique) c'est la ou sont mise les variables locales de la fonction, a l'opposé avec le tas (memoire dynamique) ou sont placer les variables allouée dynamiquement

et pour la STL, je te conseille de nouveau la FAQ de developpez, tu veras mieux se que c'est

C++ Références | Idiomes | FAQ

Nataniel

31 mars 2008 à 19:55:44

J'ai consulté à l'instant la FAQ en question. ça a l'air intéressant et faudra que je m'y plonge. Mais c'est pas obligatoire pour le cas présent.
J'ai dans l'idée qu'apprendre à m'en servir correctement sera aussi long que de faire fonctionner mes listes chainées...

chlablak

31 mars 2008 à 20:06:13

au contraire, la STL a été crée pour etre utilisée, et elle est tres simple (a part quelques concepts comme les traits, les foncteurs, les iterateurs, ...)

d'apres se que j'ai vu, tu fais un snake, donc une liste (std::list) est adaptée:

#include <list> // pour std::list
struct Bout // ton type
{
int x_, y_, direction_;
Bout(int x, int y, int direction) :
x_(x),
y_(y),
direction_(direction)
{}
};
std::list<Bout> Serpent; // on créé une liste de "Bout" (un serpent)
Serpent.push_back(Bout(23, 52, LEFT)); // on ajoute un bout
std::list<Bout>::const_iterator It; // on créé un iterateur constant (qui ne pouras modifier le contenu) pour _itéré_ la liste
for(It = Serpent.begin(); It != Serpent.end(); ++It)
{
std::cout << It->x_ << It->y_ << It->direction_ << std::endl;
}

C++ Références | Idiomes | FAQ

Nataniel

31 mars 2008 à 20:08:42

Bon bah en route pour lire attentivement cette FAQ et creuser la question merci...

Pour le code, ça n'intéresse personne ?? Même pas un tout petit peu ?

chlablak

31 mars 2008 à 20:15:21

c'est peut-etre tout simplement parce que tu as oublié d'initaliser serpent

ElementSerpent *serpent = 0; // ou NULL si tu prefere

C++ Références | Idiomes | FAQ

Nataniel

31 mars 2008 à 20:19:05

C'est bête mais ça fonctionne...

Code compilé et fonctionnant.

J'espère simplement que ma libération de mémoire est correcte (le compilateur collerait un warning sinon ?). Et ça, je peux utiliser des objets/class, des struct ou la STL, ça changera pas le prob, il faut que je gère la libération correctement.

Merci à tous en tout cas.

lmghs

31 mars 2008 à 20:19:17

Ton but est juste d'utiliser une liste chainée, ou juste d'en définir une ?

Sinon pour le code, quand il s'agit du C déguisé en C++, j'ai du mal -- cerveau pas disponible pour faire ça en loisir ^^' . Quand c'est du C++ avec les responsabilités bien réparties, même pas besoin d'intervenir tellement c'est tout de suite tout plus simple (regarde le squelette que t'as fourni MatteX)

chlablak

31 mars 2008 à 20:25:25

Citation : Nataniel

J'espère simplement que ma libération de mémoire est correcte

elle me semble

Citation : Nataniel

(le compilateur collerait un warning sinon ?)

non, ce genre d'erreurs arrive à l'execution, et sont plus dur à resoudre

mais bon moi je dis vive la STL

C++ Références | Idiomes | FAQ

Nataniel

31 mars 2008 à 20:28:38

Bon, oui j'avoue, c'est du C déguisé en C++.

Je peux vous l'expliquer, c'est pour une raison qui me dépasse moi-même. Il se trouve que je code ce projet de serpent avec un amis qui malheureusement à appris le C++ comme si c'était du C (en tout cas pour l'instant). En gros, class et objet, il sait pas encore ce que c'est et il vient à peine de toucher aux références. Par contre, il refuse catégoriquement de faire du C... Donc moi je fais du C mais je compile en C++ (en essayant quand même d'utiliser les bonnes biblio, ce qui est un peu dur vu qu'on va utiliser la SDL...)

Remarquez quand même, je ne m'amuse pas à utiliser stdlib stdio du C...

Et oui je compte bien utiliser cette chaîne. Elle va représenter le serpent en mémoire et je vais utiliser x et y pour positionner chaque élément du serpent sur int carte[][]

Inki

31 mars 2008 à 21:40:23

Pour en revenir au code de départ, le fameux C déguisé en C++, il y a un truc qui me choque :

dans ta fonction "ajouterElementInFine()" je ne vois jamais aucune référence à "elementPrecedent", ni pour lui affecter NULL s'il n'y en a pas ni pour lui affecter le maillon approprié.

Le pire c'est qu'après lors de ta libération mémoire tu essaye de "delete elementPrecedent" o_O

Si tu delete un pointeur non initialisé je comprend que ça crash, tu essaye de delete "quelque part en mémoire"... le système d'exploitation doit prendre ca comme un viol je penses

Sinon pour la discussion sur le C++ et le C, pour avoir appris comme ça je trouve que c'est vraiment pas mal d'apprendre a faire un code modulaire propre en C et de programmer des Piles, listes chainées et autres... après quand on passe au C++ entre les classes et la STL on se crois dans un rêve =)

Nataniel

1 avril 2008 à 11:08:47

Je pensais bien à un truc comme ça, j'ai rajouté :
element->elementPrecedent = temp; juste avant le retrun... ça m'a l'air pas mal...

Edit : j'ai reconverti mon code en C et posté sur le forum approprié. Il semble que la libération se fasse correctement.
Est-ce que si ça marche avec malloc et free, ça marchera automatiquement avec delete et new ?

lmghs

1 avril 2008 à 11:46:00

Tu auras des petites conversions et calculs en moins. => tout bénef.

Sinon que le côté C++ (fortement conseillé en C), c'est d'avoir une fonction d'initialisation qui s'occupe de tout : allouer, plus initialiser absolument tous les membres de ta structure. La différence, est qu'en C++ le constructeur ne fera pas l'allocation.

Sépare également les responsabilités liste/chainon, et tu verras, les choses s'éclairciront d'elles même.