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 ; } }

---

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

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.

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 :aie: ):mrgreen: ( 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; }

---

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

---