Partage

Probleme liste chaine

valex
avatar
Le 11 septembre 2012 à 0:13:04

Bonjour tout le monde !

Je suis en train de coder une sorte de liste chainée, mais voila, je me trouve confronté a un soucis depuis quelques heures ... :(

Je dois avoir un soucis dans mes pointeurs ... =/

Voila les fichiers :

Noeud.h
#ifndef NOEUD_H_INCLUDED
#define NOEUD_H_INCLUDED

#include <stdio.h>
#include <stdlib.h>

typedef struct Coordonnee Coordonnee;
struct Coordonnee {
    int x;
    int y;
};

/*
 * decrit la coordonnee sous forme de chaine de caractere
 */
 void toStringCoord(Coordonnee* coord);

typedef struct Noeud Noeud;
struct Noeud {
    Coordonnee coord;
    Noeud* suivant;
};

/*
 * initialise le noeud
 */
void init_noeud(Noeud* noeudCourant, Noeud* suivant, Coordonnee* coordonnee);

/*
 * decrit le noeud sous forme de chaine de caractere
 */
 void toStringNoeud(Noeud* n);


#endif // NOEUD_H_INCLUDED


noeud.c
#include "Noeud.h"

/*
 * decrit la coordonnee sous forme de chaine de caractere
 */
void toStringCoord(Coordonnee* coord){
    printf("[%d,%d]", coord->x, coord->y);
}

/*
 * initialise le noeud
 */
void init_noeud(Noeud* noeudCourant, Noeud* noeudSuivant, Coordonnee* coordonnee){
    noeudCourant->coord = *coordonnee;
    noeudCourant->suivant = noeudSuivant;
}

/*
 * decrit le noeud sous forme de chaine de caractere
 */
 void toStringNoeud(Noeud* n){
    toStringCoord(&n->coord);
 }


listeChainee.h
#ifndef LISTECHAINE_H_INCLUDED
#define LISTECHAINE_H_INCLUDED

#include "Noeud.h"

typedef struct listeChainee listeChainee;

struct listeChainee {
    Noeud tete;
    int longueur;
};

/*
 * Initialise la liste chainee
 */
void init_listeChainee(listeChainee* listeCourante, Noeud* noeudTete);

/*
 * retourne la longueur de la liste
 */
 int getLongueur(listeChainee* liste);

/*
 * ajoute un noeud a la tete de la liste
 */
 void ajouterEnTete(listeChainee* liste, Noeud* nouvelleTete);

/*
 * decrit la liste sous forme de chaine de caractere
 */
 void toStringListeChainee(listeChainee* liste);


#endif // LISTECHAINE_H_INCLUDED


listeChainee.c
#include "ListeChaine.h"

/*
 * Initialise la liste chainee
 */
void init_listeChainee(listeChainee* listeCourante, Noeud* noeudTete){
    listeCourante->tete = *noeudTete;
    listeCourante->longueur = 1;
}

/*
 * retourne la longueur de la liste
 */
 int getLongueur(listeChainee* liste){
    return liste->longueur;
 }

/*
 * ajoute un noeud a la tete de la liste
 */
 void ajouterEnTete(listeChainee* liste, Noeud* nouvelleTete){
    toStringNoeud(&liste->tete);

    nouvelleTete->suivant = &liste->tete;

    toStringNoeud(nouvelleTete->suivant);

    liste->tete = *nouvelleTete;

    toStringNoeud(&liste->tete);
    toStringNoeud(nouvelleTete->suivant);

    printf("\n\n");
    liste->longueur += 1;
 }

/*
 * decrit la liste sous forme de chaine de caractere
 */
 void toStringListeChainee(listeChainee* liste){
    Noeud noeudCourant = liste->tete;
    int longueur = liste->longueur;
    int i;

    printf("[");
    for(i=1; i<=longueur; i++){

        toStringNoeud(&noeudCourant);

        if(i!=longueur){
            printf(",");
            noeudCourant = *noeudCourant.suivant;
        }

    }
    printf("]");
 }


main.c
#include <stdio.h>
#include <stdlib.h>

#include "Noeud.h"
#include "ListeChaine.h"

int main(){
    Coordonnee coordn = {0,0};
    Noeud n;
    init_noeud(&n, NULL, &coordn);

    Coordonnee coordm = {1,1};
    Noeud m;
    init_noeud(&m, &n, &coordm);

//    Coordonnee coordo = {2,2};
//    Noeud o;
//    init_noeud(&o, &m, &coordo);

    listeChainee liste;
    init_listeChainee(&liste, &n);

    ajouterEnTete(&liste, &m);
    //ajouterEnTete(&liste, &o);

    toStringListeChainee(&liste);

    printf("\n\n");
    return 0;
}


Je pense que le problème vient de la fonction ajouterEnTete(), plus particulièrement de la ligne 28 de listeChainee.c ...
L’échange de tête n'est pas bien effectué ...

Si quelqu'un a des idées, n’hésitez pas !! :D

Merci ! ;)
Publicité
Le 11 septembre 2012 à 0:13:04
sildre
avatar
Le 11 septembre 2012 à 1:21:19

Tu as fait une erreur dans ta structure Liste. Tu ne dois pas stocker le nœud en tête de liste, juste un pointeur sur le nœud en tête de liste.
En corrigeant les répercussions de ce changement (et en faisant attention aux cas particuliers : liste nulle, etc.), ça marche, mais la manière d'utiliser ta liste sera difficile par rapport aux listes "habituelles".

En effet, on devrait ne pas avoir besoin de créer de nœud dans le main. C'est un élément interne à la structure liste, il ne doit pas apparaître lors de l'utilisation d'une liste. La liaison que tu fais grâce à init_noeud doit se faire automatiquement, ce n'est pas à l'utilisateur de ta structure liste de lier un par un chaque nœud.

En clair, ton main doit ressembler à ça (à toi de faire les fonctions nécessaires) :

int main(void)
{
    Coordonnee coordn = {0,0};
    Coordonnee coordm = {1,1};
    Coordonnee coordo = {2,2};

    ListeChainee *liste = NULL;
    ajouterEnTete(liste, coordn);
    ajouterEnTete(liste, coordm);
    ajouterEnTete(liste, coordo);

    // liste  ->  nœud_tete  ->  nœud  ->  nœud
    // taille      coordo       coordm    coordn
    //   3         (2,2)         (1,1)     (0,0)

    toStringListeChainee(liste);

    return 0;
}
valex
avatar
Le 11 septembre 2012 à 10:53:18

Ok je vais essayer de modifier tout ça et je repasse !

Par contre, en C il n'y a pas de type abstrait (comme en java) ? si je code une liste de coordonnée, je ne pourrais pas y mettre autre chose. C'est ça ?

Edit : J'ai bien avancé suivant tes conseils, mais un autre probleme se pose :


ListeChainee.c
#include "ListeChaine.h"

/*
 * Initialise la liste chainee
 */
void init_listeChainee(listeChainee* listeCourante, Coordonnee* coord){
    listeCourante->longueur = 1;

    Noeud noeudTete;
    init_noeud(&noeudTete, NULL, coord);

    listeCourante->tete = &noeudTete;
}

/*
 * retourne la longueur de la liste
 */
 int getLongueur(listeChainee* liste){
    return liste->longueur;
 }

/*
 * retourne 1 si la liste est vide
 */
 int estVide(listeChainee* liste){
    return liste == NULL;
 }

/*
 * ajoute un noeud a la tete de la liste
 */
 void ajouterEnTete(listeChainee* liste, Coordonnee* coord){

    Noeud nouvelleTete;

    if(estVide(liste)){
        init_noeud(&nouvelleTete, NULL, coord);
        *liste = {nouvelleTete, 1};
    }

    else{
        init_noeud(&nouvelleTete, liste->tete, coord);
        liste->tete = &nouvelleTete;
    }

    liste->longueur += 1;
 }

/*
 * decrit la liste sous forme de chaine de caractere
 */
 void toStringListeChainee(listeChainee* liste){
    Noeud* noeudCourant = liste->tete;
    int longueur = liste->longueur;
    int i;

    printf("[");
    for(i=1; i<=longueur; i++){

        toStringNoeud(noeudCourant);

        if(i!=longueur){
            printf(",");
            noeudCourant = noeudCourant->suivant;
        }

    }
    printf("]");
 }


J'ai ce message d'erreur de la part de mon IDE :

C:\Users\Val\Documents\Arduino\Snake\ListeChaine.c|38|error: expected expression before '{' token|

C'est lors du premier ajout, lorsque la liste est encore vide ... :euh:
simbilou
avatar
Le 11 septembre 2012 à 14:17:07

Citation : valex

Par contre, en C il n'y a pas de type abstrait (comme en java) ? si je code une liste de coordonnée, je ne pourrais pas y mettre autre chose. C'est ça ?



Et oui, c'est une grosse faiblesse du C. En fait il est possible de s'en sortir avec des pointeurs génériques (void*) mais c'est galère*.

Pour ton erreur, qu'essayes tu de faire exactement avec cette ligne *liste = {nouvelleTete, 1}; ?

*Mieux vaut utiliser le travail d'un autre déjà fait (utlist par exemple).
JSDZ @ Lyon — pc-bsd — bépo
valex
avatar
Le 11 septembre 2012 à 15:48:46

Bah en fait,
Quand j'arrive a cette ligne le pointeur ligne est NULL. Je voudrais donc qu'il pointe vers une structure de type listeChainee avec pour seul element le noeud que je viens de lui donner (longueur 1).

Le truc c'est que je suis en train de m'entrainer pour le fun :-° . C'est pour ca que je n'utilise pas de lib, mais je garde ton lien sous la main ! :p
simbilou
avatar
Le 11 septembre 2012 à 17:20:51

Citation : valex

Le truc c'est que je suis en train de m'entrainer pour le fun :-° . C'est pour ca que je n'utilise pas de lib



Je comprend bien, et c'est un très bon exercice. :)

J'ai regardé un petit peu ton code et ça ne marchera jamais comme ça. Tu ne fais aucune allocation de mémoire. Où sont stocké les maillons de ta chaine ?
JSDZ @ Lyon — pc-bsd — bépo
sildre
avatar
Le 11 septembre 2012 à 17:38:42

Citation : simbilou

Où sont stocké les maillons de ta chaine ?


Au départ ils étaient dans le main...
Maintenant, nul part.
valex
avatar
Le 11 septembre 2012 à 17:54:07

Je te remets tout les dossiers :

Noeud.h
#ifndef NOEUD_H_INCLUDED
#define NOEUD_H_INCLUDED

#include <stdio.h>
#include <stdlib.h>

typedef struct Coordonnee Coordonnee;
struct Coordonnee {
    int x;
    int y;
};

/*
 * decrit la coordonnee sous forme de chaine de caractere
 */
 void toStringCoord(Coordonnee* coord);

typedef struct Noeud Noeud;
struct Noeud {
    Coordonnee coord;
    Noeud* suivant;
};

/*
 * initialise le noeud
 */
void init_noeud(Noeud* noeudCourant, Noeud* suivant, Coordonnee* coordonnee);

/*
 * decrit le noeud sous forme de chaine de caractere
 */
 void toStringNoeud(Noeud* n);


#endif // NOEUD_H_INCLUDED


Noeud.c
#include "Noeud.h"

/*
 * decrit la coordonnee sous forme de chaine de caractere
 */
void toStringCoord(Coordonnee* coord){
    printf("[%d,%d]", coord->x, coord->y);
}

/*
 * initialise le noeud
 */
void init_noeud(Noeud* noeudCourant, Noeud* noeudSuivant, Coordonnee* coordonnee){
    noeudCourant->coord = *coordonnee;
    noeudCourant->suivant = noeudSuivant;
}

/*
 * decrit le noeud sous forme de chaine de caractere
 */
 void toStringNoeud(Noeud* n){
    toStringCoord(&n->coord);
 }


ListeChainee.h
#ifndef LISTECHAINE_H_INCLUDED
#define LISTECHAINE_H_INCLUDED

#include "Noeud.h"

typedef struct listeChainee listeChainee;

struct listeChainee {
    Noeud* tete;
    int longueur;
};

/*
 * Initialise la liste chainee
 */
void init_listeChainee(listeChainee* listeCourante, Coordonnee* coord);

/*
 * retourne la longueur de la liste
 */
 int getLongueur(listeChainee* liste);

/*
 * retourne 1 si la liste est vide
 */
 int estVide(listeChainee* liste);

/*
 * ajoute un noeud a la tete de la liste
 */
 void ajouterEnTete(listeChainee* liste, Coordonnee* coord);

/*
 * decrit la liste sous forme de chaine de caractere
 */
 void toStringListeChainee(listeChainee* liste);


#endif // LISTECHAINE_H_INCLUDED


ListeChainee.c
#include "ListeChaine.h"

/*
 * Initialise la liste chainee
 */
void init_listeChainee(listeChainee* listeCourante, Coordonnee* coord){
    listeCourante->longueur = 1;

    Noeud noeudTete;
    init_noeud(&noeudTete, NULL, coord);

    listeCourante->tete = &noeudTete;
}

/*
 * retourne la longueur de la liste
 */
 int getLongueur(listeChainee* liste){
    return liste->longueur;
 }

/*
 * retourne 1 si la liste est vide
 */
 int estVide(listeChainee* liste){
    return liste == NULL;
 }

/*
 * ajoute un noeud a la tete de la liste
 */
 void ajouterEnTete(listeChainee* liste, Coordonnee* coord){

    Noeud nouvelleTete;

    if(estVide(liste)){
        init_noeud(&nouvelleTete, NULL, coord);
        liste = malloc(sizeof(listeChainee));

        init_listeChainee(liste, coord);
//        liste->tete = &nouvelleTete;
//        liste->longueur = 1;
    }

    else{
        init_noeud(&nouvelleTete, liste->tete, coord);
        liste->tete = &nouvelleTete;
    }

    liste->longueur += 1;
 }

/*
 * decrit la liste sous forme de chaine de caractere
 */
 void toStringListeChainee(listeChainee* liste){
    Noeud* noeudCourant = liste->tete;
    int longueur = liste->longueur;
    int i;

    printf("[");
    for(i=1; i<=longueur; i++){

        toStringNoeud(noeudCourant);

        if(i!=longueur){
            printf(",");
            noeudCourant = noeudCourant->suivant;
        }

    }
    printf("]");
 }


main.c
#include <stdio.h>
#include <stdlib.h>

#include "Noeud.h"
#include "ListeChaine.h"

int main(){
    Coordonnee coordn = {0,0};
    Coordonnee coordm = {1,1};
    Coordonnee coordo = {2,2};


    listeChainee* liste = NULL;

    ajouterEnTete(liste, &coordn);
    ajouterEnTete(liste, &coordm);
    ajouterEnTete(liste, &coordo);

    toStringListeChainee(liste);
    printf("\n\n");
    
    free(liste);

    
    return 0;
}


J'ai pris en compte les remarques de sildre.
Et j'ai essayé de passer par l'allocation mémoire, la ça compile, mais le programme plante.

J'ai fait (dans ma fonction ajouterEnTete) :
printf("%d", estVide(liste));


J'obtiens toujours 1 ... o_O
sildre
avatar
Le 11 septembre 2012 à 18:14:40

Dans ListeChainee.c, lignes 9 et 34, tu dois faire de l'allocation dynamique. D'ailleurs il y a une incompatibilité entre la ligne 7 et la 50.

Ligne 38, tu fais liste = malloc(…). Mais je ne vois aucun free(liste) ?
Si tu alloues une portion mémoire, à un moment ou un autre il faudra que tu libères cette portion mémoire.
gregl
avatar
Le 11 septembre 2012 à 19:11:50

Citation : sildre

En clair, ton main doit ressembler à ça (à toi de faire les fonctions nécessaires) :

int main(void)
{
    Coordonnee coordn = {0,0};
    Coordonnee coordm = {1,1};
    Coordonnee coordo = {2,2};

    ListeChainee *liste = NULL;
    ajouterEnTete(liste, coordn);
    ajouterEnTete(liste, coordm);
    ajouterEnTete(liste, coordo);

    // liste  ->  nœud_tete  ->  nœud  ->  nœud
    // taille      coordo       coordm    coordn
    //   3         (2,2)         (1,1)     (0,0)

    toStringListeChainee(liste);

    return 0;
}


Ca ne peut pas marcher. liste sera toujours NULL dans le main même si tu le modifies dans ajouterEnTete (en C les paramètres, y compris les pointeurs, sont passés par valeur donc toute modification d'un paramètre est "perdue" lors du retour à l'appelant. Donc si tu passes un pointeur comme ici, tu peux modifier ce qui est pointé sans souci mais la modification du pointeur - i.e. un liste=... dans une des fonctions - sera sans effet lorsque tu reviens au main).

Il y a plusieurs façon de résoudre se problème, ma préférence va à la création d'une fonction de création d'une liste qui servira ) initialiser liste :
ListeChainee *liste = CreerListe();


valex, c'est la cause de ton problème, tu passes toujours NULL à tes fonctions et donc estVide() retour 1 et toStringListeChainee() plante puisque tu ne gères pas le cas où liste est NULL.
sildre
avatar
Le 11 septembre 2012 à 19:20:26

Citation : gregl

Ca ne peut pas marcher. liste sera toujours NULL dans le main même si tu le modifies dans ajouterEnTete (en C les paramètres, y compris les pointeurs, sont passés par valeur donc toute modification d'un paramètre est "perdue" lors du retour à l'appelant. Donc si tu passes un pointeur comme ici, tu peux modifier ce qui est pointé sans souci mais la modification du pointeur - i.e. un liste=... dans une des fonctions - sera sans effet lorsque tu reviens au main).


En même temps j'allais pas tout dévoiler. Je sais très bien tout cela. valex ne gérait pas encore l'allocation dynamique, je pensais que c'était à lui de trouver qu'il fallait faire :
ListeChainee *liste = CreerListe();
/*...*/
SupprimerListe(liste);
et je pense qu'il l'aurait trouvé de lui-même lorsqu'il aurait fait les allocations dynamiques.
valex
avatar
Le 12 septembre 2012 à 0:12:39

Ok merci les gars ! Mine de rien ça avance !

Mais je suppose que le problème doit aussi se poser lors de l'initialisation de mes noeuds ! non ?! :oo_O
sildre
avatar
Le 12 septembre 2012 à 0:15:20

Citation : sildre

Dans ListeChainee.c, lignes 9 et 34, tu dois faire de l'allocation dynamique. D'ailleurs il y a une incompatibilité entre la ligne 7 et la 50.

valex
avatar
Le 12 septembre 2012 à 12:08:57

Ha c'est la fameuse phrase que je n'avais pas totalement saisi (je n'avais pas encore appris l'alloc dynamique). Je regarde tout ca ! merci en tout cas !

Probleme liste chaine

× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
  • Editeur ●
  • Markdown