Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 5 sur 5
  1. #1
    Invité de passage
    Femme Profil pro
    Inscrit en
    mai 2011
    Messages
    12
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France

    Informations forums :
    Inscription : mai 2011
    Messages : 12
    Points : 1
    Points
    1

    Par défaut chainage maillon fonction insertion

    Bonjour à tous,
    j'ai besoin d'aide pour mon code c++, je dois grâce aux enregistrements de maillonT et chainageT, créer une fonction insertion permettant d'insérer un élément de type T EN TETE du chainage .
    Je n'arrive pas à compiler, il y a surement un problème avec mon pointeur, je pensais pourtant que à la base il fallait dire que ch.tete devient mem(pm).succ et que pm devient du coup la tete du maillon
    Merci d'avance pour votre aide

    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
     
    #include<stdio.h>
    #include<malloc.h>
     
     
    typedef int T;
     
    // enregistrement du maillon
    typedef struct maillonT {
                   T elt;
                   maillonT *succ;
            } maillonT;
     
    /enregistrement du chainage
    typedef struct chainageT {
                   maillonT *tete;
                   maillonT *queue;
                   int nb_elt;
            } chainageT;
     
     
    // ajout d'un nouvel élément en tête du chainage ch
     
     
    void insertionT(chainageT & ch,T e){
       //variable, pointeur vers maillonT 
       ch.nb_elt=0;
     
       maillonT *pm; 
       pm = new maillonT;
     
       pm->succ = ch.tete;
       ch.tete = pm;
       pm->elt = e;
       nb_elt=nb_elt+1; //incrémentation du nombre d'élément du chainage
     
       // si la liste est vide 
     
       if (ch.tete==NULL){
           ch.tete = pm ;
       }
    }

  2. #2
    Modérateur

    Homme Profil pro Cyrille
    Network programmer
    Inscrit en
    juin 2010
    Messages
    2 176
    Détails du profil
    Informations personnelles :
    Nom : Homme Cyrille
    Âge : 27
    Localisation : France

    Informations professionnelles :
    Activité : Network programmer

    Informations forums :
    Inscription : juin 2010
    Messages : 2 176
    Points : 5 641
    Points
    5 641

    Par défaut

    Bonjour,

    difficile de comprendre ce que tu espères faire, le code est flou.

    Quelle est l'erreur de compilation dont tu parles ?

    S'agit-il d'insérer un élément en tête d'une liste chaînée ? Si oui, il te faut d'abord revoir ton algo calmement avant de l'implémenter. C'est un cas d'école.

    Tu écris ch.tete = pm; et un peu plus loin
    if (ch.tete==NULL){
    ch.tete = pm ;
    }
    Euh...? pourquoi ? A priori ça devrait jamais être vérifié comme test.


    Pour rappel, le principe d'une liste chaînée en gros c'est
    structure type
    struct Element { T value; struct Element* next; };- ne pas hésiter à profiter d'être C++ pour ajouter un constructeur et initialiser enxtà NULL
    - un élément de tête de liste

    pour ajouter un élément à la fin
    - on parcourt la liste jusqu'au bout
    - on ajoute le nouvel élément

    pour ajouter un élément au milieu
    - on parcourt la liste jusqu'à l'élément précédent l'insertion
    - on met à jour les next du précédent et du nouvel élément pour garder la structure de la liste cohérente

    pour ajouter un élément au début
    - voir l'ajout d'élément au milieu en considérant la tete comme élément précédent l'insertion

  3. #3
    Expert Confirmé Sénior

    Homme Profil pro Pierre
    Ingénieur développement logiciels
    Inscrit en
    juin 2007
    Messages
    2 182
    Détails du profil
    Informations personnelles :
    Nom : Homme Pierre
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : juin 2007
    Messages : 2 182
    Points : 5 060
    Points
    5 060

    Par défaut

    Tu es en C++, donc, utilise ce qui va bien:

    Les en-têtes c++: cstdio et cmalloc, qui d'ailleurs ne servent ni l'un ni l'autre dans ton code. De plus cstdio est avantageusement remplace par iostream

    Les types réels.
    struct bidule {}; déclare un type nommé bidule.
    typedef T U; associe un alias U à un type T.
    En C++, il est inutile de faire typedef struct T {} T; parce que tu donnes l'alias T au type T.

    Tu obtiens ainsi:
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    typedef int T;
     
    // enregistrement du maillon
    struct maillonT {
       T elt;
       maillonT *succ;
    };
     
    //enregistrement du chainage
    struct chainageT {
       maillonT *tete;
       maillonT *queue;
       int nb_elt;
    };
    Cependant, en C++, on utiliserait des templates, mais c'est peut-être tôt dans ton cours (vu la nature de l'exercice)
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
     
    // enregistrement du maillon
    template <typename T> struct maillon {
       T elt;
       maillon *succ;
    };
     
    //enregistrement du chainage
    template <typename T> struct chainage {
       maillon<T> *tete;
       maillon<T> *queue;
       int nb_elt;
    };
    ce qui donnerait des définitions de variables telles que
    maillon<int> maillon={1, std::nullptr}; en C++11 et maillon<int> maillon={1, NULL}; en C++ moins récent

    Pour ta fonction, il y a plusieurs erreur:
    ta première instruction modifie le chainage reçu en référence, pour définir le nombre d'élément à 0, c'est une erreur, tu perds cette information

    nb_elt=nb_elt+1; ne peut pas compiler, nb_elt n'est pas une variable (tu pensais à ch.nb_elt)

    Ton test est faux, c'est la queue qu'il faut définir et mieux vaut vérifier la taille de la liste en te reposant sur la logique interne.

    Tu devrais définir le chainon intégralement avant de l'utiliser, et donc faire pm->elt = e; juste avant le pm->succ = ch.tete;Sinon, la logique du code est bonne.

    voici ton code, dûment commenté pour que tu comprennes
    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
    typedef int T;
     
    // enregistrement du maillon
    struct maillonT {
       T elt;
       maillonT *succ;
    };
     
    // enregistrement du chainage
    struct chainageT {
       maillonT *tete;
       maillonT *queue;
       int nb_elt;
    };
     
     
    // ajout d'un nouvel élément en tête du chainage ch
     
     
    void insertionT(chainageT & ch,T e){
    	//variable, pointeur vers maillonT 
     
    	ch.nb_elt=0;//ch pense à présent n'avoir aucun chainon
     
    	maillonT *pm; 
    	pm = new maillonT;
    	// soit un nouveau maillon, pointé par pm.
     
    	pm->succ = ch.tete;
    	//le successeur du chainon pointé par pm est celui pointé par la tete de la chaine.
     
    	ch.tete = pm; //la tete de la chaine contient dorénabent l'adresse du nouveau chainon
     
    	pm->elt = e;//on définit (enfin) la valeur du nouveau chainon
     
    	nb_elt=nb_elt+1; //incrémentation du nombre d'élément du chainage (0 devient 1)
     
    	// si la liste est vide 
     
    	if (nb_elt == 1){ // comme on a déjà fait ch.tete = pm, ce test est faux si pm n'est pas null
    		ch.queue = pm ;//si pm était null, on remet encore une fois null dans tete
    	}
    }
    voici à présent une version corrigée pour tenir compte des remarques
    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
    typedef int T;
     
    // enregistrement du maillon
    struct maillonT {
       T elt;
       maillonT *succ;
    };
     
    // enregistrement du chainage
    struct chainageT {
       maillonT *tete;
       maillonT *queue;
       int nb_elt;
    };
     
    // ajout d'un nouvel élément en tête du chainage ch
    void insertionT(chainageT & ch,T e) {
    	// soit un nouveau maillon, pointé par pm.
    	maillonT *pm = new maillonT;
    	pm->elt = e;//on définit (enfin) la valeur du nouveau chainon
    	pm->succ = ch.tete;	//le successeur du chainon pointé par pm est celui pointé par la tete de la chaine.
     
    	ch.tete = pm; //la tete de la chaine contient dorénavent l'adresse du nouveau chainon
     
    	if (nb_elt ==0) {
    		ch.queue = ch.tete;
    	}
    	++nb_elt;
    }
    en bonus, voici une version bien meilleure, parce que codée en respectant la logique des objets. (si tu ne peux pas utiliser le C++11, utilise 0 ou NULL à la place de std::nullptr)
    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
     
    // enregistrement du chainage.
    /*
    	n'ayant qu'une tete nulle initialement, le dernier chainon du chainage à forcément nullptr pour suivant.
    */
    template <typename T>
    struct chainage {
    	private:
    		using pointeur = maillon<T>*;
    		using size_t = int;
     
    		/*
    			nul n'a besoin de connaitre l'existence du maillon, c'est un outil de travail interne.
    			Donc le schéma du maillon est une propriété privée du chainage
    		*/
    		class maillon {
    			private:
    				T elt;
    				maillon *succ;
    			public:
    				maillon(const T& valeur) : elt(valeur), succ(std::nullptr) {}
    				maillon(const T& valeur, maillon *suivant) : elt(valeur), succ(suivant) {}
    				/*
    				destructeur vide
    				maillon n'allouant pas suivant, il ne le désalloue pas non plus.
    				*/
    				~maillon(){}
     
    				maillon* definirSuivant(maillon* m) {
    					maillon *ancien = succ;
    					succ = &m;
    					return ancien;
    				}
     
    				maillon* suivant() const {return succ;}
     
    				T valeur() const {return elt;}
    				T& valeur() {return elt;}
    		};
     
    		pointeur tete;
    		size_t nb_elt;
    	public:
    		//le seul constructeur est un chainage vide.
    		chainage() : tete(std::nullptr), nb_elt(0) {}
     
    		//j'interdis de construire un chainage par copie.
    		chainage(const chainage&) = delete;
    		//ainsi que de copier un chainage dans un autre
    		chainage& operator=(const chainage&) = delete;
     
    		/*
    		le destructeur libère tous les maillons, parce que le chainage alloue ses propres maillons
    		*/
    		~chainage() {
    			while (tete!=std::nullptr) {
    				pointeur temp = tete;
    				tete = temp.suivant();
    				delete temp;
    			}
    		}
     
    		//retourner le chainage lui-même permet l'enchainement d'appel
    		chainage& ajouterEnTete(const T& valeur) {
    			tete = new maillon(valeur, tete);
    			++nb_elt;
    			return *this;
    		}
     
    		size_t taille() const {return nb_elt;}
    };
     
    // ajout d'un nouvel élément en tête du chainage ch
    template <typename T>
    void insertion(chainage<T>& ch, const T& e){
    	ch.ajouterEnTete(e);
    }
    Pour pouvoir parcourir le chainage, on définirait une autre classe interne, un itérateur, tel qu'on puisse écrire :
    • ch.begin() pour avoir un iterateur au début du chainage.
    • ch.end() pour avoir un itérateur au bout. iterateur == ch.end() signifierait qu'il n'y a plus de valeur
    • *iterateur pour avoir la valeur actuellement désignée par l'itérateur
    • ++iterateur pour déplacer l'itérateur sur l'élément suivant.

    Cet itérateur se comporterait un peu comme un maillon, mais s'utiliserait avec la meme syntaxe qu'un pointeur si chainage avait été un tableau.

    ainsi, afficher le contenu du chainage s'écrirait:
    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
    template <typename T>
    void afficher1(const chainage<T>& ch){
    	std::cout<<"le chainage contient:";
    	chainage<T>::iterateur it = ch.begin();
    	while(it != ch.end()) {
    		std::cout<<' '<<*it;
    		++it
    	}
    	std::cout<<std::endl;
    }
     
    template <typename T>
    void afficher2(const chainage<T>& ch){
    	std::cout<<"le chainage contient:";
    	for(chainage<T>::iterateur it = ch.begin(); it != ch.end(); ++it) {
    		std::cout<<' '<<*it;
    	}
    	std::cout<<std::endl;
    }
     
    //et si le C++11 est autorisé, tu peux meme ecrire
    template <typename T>
    void afficher3(const chainage<T>& ch){
    	std::cout<<"le chainage contient:";
    	for(const T& valeur : ch) std::cout<<' '<<t;
    	std::cout<<std::endl;
    }
    et ultime bonus, voici ce qui existe dans la bibliothèque standard du langage.
    Code :
    1
    2
    3
    4
    5
    6
    #include <list>
    typedef int T;
    typedef list<T> chainageT;
    void insertionT(chainageT & ch, T e){
    	ch.push_front(e);
    }
    Dernier détail, pour utiliser le C++11 avec g++-4.7, il faut rajouter l'option -std=c++11, avec g++-4.6 c'est -std=c++0x, et dans les EDI, il y a quasiment toujours une option à cocher, ou alors, le moyen d'ajouter ses propres options.
    Mes principes de bases du codeur qui veut pouvoir dormir:
    • Une variable de moins est une source d'erreur en moins.
    • Un pointeur de moins est une montagne d'erreurs en moins.
    • Un copier-coller, ça doit se justifier... Deux, c'est un de trop.
    • La plus sotte des questions est celle qu'on ne pose pas.

    Pour faire des graphes, essayez yEd.

  4. #4
    Invité de passage
    Femme Profil pro
    Inscrit en
    mai 2011
    Messages
    12
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France

    Informations forums :
    Inscription : mai 2011
    Messages : 12
    Points : 1
    Points
    1

    Par défaut merci

    Merci beaucoup à vous pour vos indications,

    j'ai fais la fonction de suppression : elle ne fonctionne pas en effet au niveau du delete je pense pas vraiment comprendre comment retirer le maillon.
    Merci d'avance ! ( je vais me coucher ) ( par contre éviter e mettre des templates car nous n'avons pas appris cela )

    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
    //-----------------------------------------------------
    // Fonction Suppression:
    // Fonction qui permet de supprimer un élément T d'un chainage passé en paramètre
     
    void SuppressionT(chainageT & ch, T e){
         if (ch.nb_elt != 0 ) { /* si la liste n'est pas vide on pourra retirer un élément */
            int i = 0;
             maillonT *  courant;
             maillonT * supp_element;
     
             courant = ch.tete;
     
         for (i = 1; i < PositionElement(ch,e) ;i++) {   /* appel de la fonction PositionElement */
     
         courant = courant -> succ;
     
         supp_element = courant -> succ;
     
         courant -> succ = courant -> succ -> succ;
     
         if (courant -> succ == NULL) {
             ch.queue = courant;
     
             delete (supp_element); /* au départ je pensais mettre free (supp_element -> elt); free (supp_element); */
     
             ch.nb_elt=ch.nb_elt-1;
         }
         }
         }
    }
     
     
     
     
     
    int PositionElement(chainageT & ch, T e){
        maillonT * pm;
        int pos;
     
        pos = 0;
     
        pm = ch.tete;
     
        if ( pm -> elt == e) {
            pos = 1;
        }
        else {
            while ( pm -> elt != e ){
                pm = pm -> succ;
                pos = pos + 1;
            }
        }
            return pos;
    }

  5. #5
    Membre Expert Avatar de Trademark
    Inscrit en
    février 2009
    Messages
    763
    Détails du profil
    Informations forums :
    Inscription : février 2009
    Messages : 763
    Points : 1 351
    Points
    1 351

    Par défaut

    Salut,

    Plusieurs choses :

    * Renvois un booléen, true si l'élément a bien été supprimé, false si l'élément n'a pas été trouvé. Il n'est pas trouvé si la liste est vide mais encore si il n'est simplement pas dans la liste.

    * Tu dois pouvoir te passer de la fonction PositionElement qui ne fait qu'ajouter inutilement de la complexité. Et puis :

    Code :
    for (i = 1; i < PositionElement(ch,e) ;i++)
    Ce code signifie que pour chaque i tu reparcours toute ta liste avec PositionElement, sort le de ta boucle.

    * Ensuite pour en venir à ce qui t'intéresse, ta suppression ne marche pas car tu supprimes le dernier élément, en effet :

    Code :
    if (courant -> succ == NULL)
    ne sera vrai que quand courant sera le dernier maillon.


    Pour te donner un pseudo-code, voici ce que tu pourrais faire :

    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    trouve = faux
    tant que pas trouve ET que courant n'est pas la fin de la liste
      si courant->data == T
        trouve = vrai
      sinon
        avancer courant
     
    Si trouve
      alors on supprime courant
      retourne vrai
    Sinon
      retourne faux

+ Répondre à la discussion
Cette discussion est résolue.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •