chainage maillon fonction insertion [Résolu]

[tsuka]

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

[Bousk]

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

[leternel]

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.

[tsuka]

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

[Trademark]

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