Discussion :

[Invité]

Bonsoir,

Depuis plusieurs jours, je peine à réaliser une structure de liste chaînée basique en C++.
J'ai tout tenté, mais systématiquement j'obtiens une erreur de segmentation....
D'après gdb, elle se produirait à la ligne 25 ci-dessous mais je ne comprends pas pourquoi...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
#include <iostream>
 
 
struct Noeud {
 
	int valeur;
	Noeud *noeud_suivant;
 
};
 
struct Liste {
 
	Noeud *tete_de_liste;
 
};
 
 
int main() {
 
 
	Liste *liste;
	Noeud *noeud;
 
	noeud->valeur = 20;
	noeud->noeud_suivant = nullptr;
	liste->tete_de_liste = noeud;
 
}

Je suis sûr qu'il s'agit d'une erreur toute bête mais plusieurs jours de réflexion ne m'ont pas aidé à l'identifier...
Merci par avance pour votre aide

[Teaniel]

bonjour,

Dans main, lorsque tu effectues noeud->valeur=20, noeud n'est pas encore initialisé.
Du coup, l'opérateur de pointeur renvoie une valeur invalide, ce qui explique l'erreur de segmentation.
Même chose en ligne 26 : à ce moment là liste ne pointe sur aucun objet réel, et donc tu auras une erreur de segmentation
Correction immédiate :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
#include <iostream>
 
 
struct Noeud {
 
	int valeur;
	Noeud *noeud_suivant;
 
};
 
struct Liste {
 
	Noeud *tete_de_liste;
 
};
 
 
int main() {
 
 
	Liste liste; // Pas de pointeur ici comme ça ta liste est supprimée automatiqument
	auto *noeud = new Noeud; // ici
 
	noeud->valeur = 20;
	noeud->noeud_suivant = nullptr;
	liste->tete_de_liste = noeud;
        // .......
        // utilisation
        delete noeud; // Pour éviter les fuites mémoire
 
}

Ensuite, je suppose que ton code n'est pas fini, car il manque les procédures de création à ta liste. En utilisant les pointeurs intelligents on peut grandement simplifier cette gestion :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
#include <iostream>
 
 
struct Noeud {
 
	int valeur;
	shared_ptr<Noeud> noeud_suivant = nullptr;  // Lorsque l'instance contenante est supprimée, et que noeud_suivant est le dernier pointeur à référencer noeud_suivant, alors *noeud_suivant est aussi supprimé (delete) cetotomatix.
 
};
 
struct Liste {
 
	shared_ptr<Noeud> tete_de_liste = nullptr;  // pareil que ci-dessus.
 
};
 
 
int main() {
 
 
	Liste liste;
	auto *noeud = new Noeud; // ici
 
	noeud->valeur = 20;
	liste->tete_de_liste = noeud;
        // .......
        // utilisation
       
        // Ici, rien à faire pour nettoyer.
}

Ensuite, je pense que tu serais bien inspiré de regarder du côté de la STL (sauf si tu fais tout cela pour apprendre, auquel cas désolé de t'avoir spoilé), qui fournit déjà ce genre de service. Recherche std::list (ce site par exemple) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
#include <list>
 
int main()
{
    std::list<int> liste;
    liste.push_back(20);
    // ...  la suite
}

Ces deux lignes remplacent stricto-sensu l'intégralité de ton code...


Cordialement,
Marc

[Invité]

Hello Marc !

Tout d'abord, merci pour ta réponse et ton aide. Cette dernière m'a été d'une grande utilité ! J'ai en effet réussi à arriver là où je voulais en venir.
J'ai opté pour la première solution, c'est-à-dire l'allocation et les delete manuels. Bien entendu, mon code n'était pas complet. C'était pour l'exemple.
J'ai par la suite réalisé les méthodes d'ajout d'un élément et autres méthodes utiles à la gestion d'une liste chaînée.

Concernant l'import de l'en-tête list, j'étais au courant mais étant débutant en C++ (je viens du Python), réaliser sa structure soi-même est un bon exercice.
Bien entendu, par la suite je ne me refuserai certainement pas de l'utiliser. Comme on dit, inutile de réinventer la roue

Bonne soirée,
Bien à toi
Sacha

[koala01]

Salut,

Je suis un fervent adepte du concept du

Donnes un poisson à quelqu'un, il mangera un jour;

Apprends lui à pêcher, il mangera toute sa vie

Si bien que, au lieu de te donner une réponse "toute faite" (même si j'en viendrai peut-être à le faire à la fin de l'explication), je préfère t'expliquer le problème, de manière à ce que, si, dans deux jours, tu es de nouveau confronté à la même erreur, tu sois (j'espère, en tout cas) en mesure de la résoudre par toi-même.

Alors, si tu veux alller pisser, fumer une clope ou boire quelque chose avant de commencer, c'est le moment, c'est l'instant, car, après, tu risques de passer quelques temps "ardus"

D'abord, il faut savoir que, dans la très grosse majorité des cas, une erreur de segmentation est, le plus souvent, due à un pointeur "dans les choux"; ou, pour être plus précis, parce que tu essaye de déréférencer (comprends : parce que tu essaye d'accéder à l'élément pointé par) un pointeur invalide.

Cela m'amène tout naturellement à expliquer ce qu'est cette notion de pointeur, et donc, à en donner une définition (sans doute un peu adaptée de manière personnelle par rapport à ce que tu en as appris ).

Un pointeur est une donnée (on pourrait dire une variable) de type numérique entier (généralement non signé) qui correspond à l'adresse mémoire à laquelle on devrait (à laquelle on espère!!!) trouver une donnée du type indiqué.

Si on observe ton code, on trouve "assez faciltement" quatre déclarations de pointeurs :

1. à la ligne 7, lorsque tu déclares (au niveau de ta structure Noeud une donnée nommée noeud_suivant comme étant "une donnée numérique entière représentant l'adresse mémoire à laquelle on devrait trouver une donnée de type Noeud"
2. à la ligne 13 lorsque tu déclares (au niveau de ta structure Liste ) une donnée nommée tete_de_liste comme étant "une donnée numérique entière représentant l'adresse mémoire à laquelle on devrait trouver une donnée de type Noeud"
3. à la ligne 21 lorsque tu déclares (au niveau de la fonction principale main ) une donnée nommée liste comme étant "une donnée numérique entière représentant l'adresse mémoire à laquelle on devrait trouver une donnée de type Liste" et
4. à la ligne 22 lorsque tu déclares (au niveau de la fonction principale main ) une donnée nommée noeud comme étant "une donnée numérique entière représentant l'adresse mémoire à laquelle on devrait trouver une donnée de type Noeud"

A partir de maintenant, il va falloir faire un gros effort pour arriver à se faire "aussi bête qu'un ordinateur", et se poser, pour chacun de ces éléments une question toute bête :

à quoi correspond cette adresse mémoire

Pour t'aider à répondre à cette question, il faut savoir une chose à propos du compilateur : lorsqu'il analyse une ligne bien particulière de ton code, il n'a absolument aucune idée de ce qui se passe au niveau des lignes suivantes!

Si bien que la réponse à cette question est la même pour chacune des quatre lignes que j'ai indiqué : on n'en a absolument aucune idée. Et on n'a d'ailleurs absolument aucun moyen de le savoir.

Avec un peu de chance, la valeur numérique représentée par ces quatre donnée effectivement correspondre à l'adresse mémoire à laquelle nous trouverions une donnée qui puisse être considérée comme étant du type Noeud (pour les lignes 7, 13 et 22) ou du type Liste (pour la ligne 21).

Il faut donc être "un tout petit peu" réaliste sur ce coup:

• Déjà, les chances qu'il traîne "par miracle" en mémoire des données qui puissent "être considérées" comme étant de type Noeud ou de type Liste sont particulièrement faibles.
• En plus, quand on pense qu'un ordinateur dispose de quoi? 2? 4 ? ... 64Gb de RAM? la probabilité que l'adresse mémoire représentée par ces pointeurs corresponde à l'adresse mémoire à laquelle se trouveraient ces "données miraculeuse" est ... quasi inexistante.
• Enfin même les deux premiers points arrivaient à faire quelque chose de correct (mais nous sommes au delà du miracle sur ce coup là ) , il faut savoir que le système d'exploitation te mettra des battons dans les roues, car il refusera forcément que ton application n'aille chipoter à de la mémoire qui n'a pas été désignée comme... étant rendue disponible à ton application (re )

Arrivés à ce point, nous n'en sommes encore qu'à avoir déterminé s'il y avait "la moindre chance" que les pointeurs correspondent à une adresse mémoire "cohérente". Et tu seras sans doute d'accord avec moi pour dire que ce n'est décidément pas le cas

Et pourtant, si ton code s'arrêtait à la ligne 23, ton application ne ferait sans doute rien d'intéressant, mais, au moins, elle ne planterait pas magistralement en se plaignant d'une erreur de segmentation, simplement, parce que l'on n'essaye pas de déréférencer (comprends : d'accéder au contenu de l'adresse mémoire représentée par) les différents pointeurs.

Si ton programme plante, c'est, très clairement, à cause des lignes 24 à 26 car:

• à la ligne 24, il n'y a aucune chance que noeud->valeur te permette d'accéder à une donnée qui puisse être considéré comme la donnée "valeur" de ton noeud (vu qu'il n'y a déjà aucune chance que noeud corresponde effectivement à l'adresse à laquelle on trouvera effectivement une donnée de type Noeud)
• A la ligne 25, rebelote : comment veux tu que noeud->noeud_suivant puisse correspondre à une donnée (qui devrait être un pointeur sur une donnée de type Noeud) valide
• Enfin, à la ligne 26, les mêmes causes ayant toujours les mêmes effets, tu auras compris que toute tentative d'accéder à liste->tete_de_liste n'a absolument aucune chance de réussir

La solution à ce problème est donc "toute simple" (du moins, en théorie) : il faut s'assurer que les pointeurs appelés liste et noeud ... correspondent à une adresse mémoire à laquelle nous trouverons effectivement une donnée de type Liste et une autre de type Noeud.

A ceci près que, tu connais la différence entre la théorie et la pratique En théorie, il n'y a aucune différence. En pratique il y en a une

Et je peux t'assurer que c'est surtout vrai dans un langage comme le C++

Car il faut bien se dire que chaque "fonctionnalité" (et je parle au sens le plus large possible du terme, à savoir des données, des fonctions et des différents types de donnée) que tu pourras développer ne vaut que ... par l'usage qui en sera fait.

Or, il faut rester un minimum cohérent par rapport aux besoins qui ont été exprimés : si tu pars sur l'idée de créer la notion de "liste" (et, du coup, de l'idée de créer la notion sous-jacente de "noeud"), c'est -- très clairement -- parce que tu veux pouvoir profiter d'une "collection" dont le nombre d'éléments évolue de manière dynamique (comprends : que la collection puisse aussi bien contenir cinq éléments si cela te suffit ou ... 10 000 si tu devais en avoir besoin).

Lorsque je te dis que la solution est simple en théorie, parce qu'il "suffit" de s'assurer que l'adresse représentée par différents pointeurs correspondent effectivement à l'adresse à laquelle on s'attend à trouver une donnée du type adéquat, c'est parfaitement juste, car, si l'on s'en tient au code que tu nous présente, nous pourrions le modifier très rapidement pour lui donner une forme proche de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
int main() {
    Liste liste_temp; // on crée une donnée de type Liste 
    Liste *liste = & liste_temp; // on déclare un pointeur de type Liste, auquel on associe l'adresse mémoire de liste_temp
    Noeud noeud_temp; // pareil avec une donnée de type Noeud
    Noeud *noeud = &noeud_temp; toujours pareil
 
	noeud->valeur = 20;
	noeud->noeud_suivant = nullptr;
	liste->tete_de_liste = noeud;
 
}

De là, nous pourrions même le simplifier énormément, vu que la seule adresse mémoire dont nous ayons besoin est celle correspondant à ton pointeur noeud lorsque l'on décide de définir la valeur de liste->tete_de_liste.

Nous pourrions donc -- en effet -- nous contenter de prendre l'adresse mémoire de noeud_temp lorsque nous avons réellement besoin d'avoir une adresse mémoire (qui correspond à l'endroit où l'on trouveras un élément de type NoeudLe même code pourrait donc parfaitement ressembler à

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
int main(){
    Liste liste; // on crée une donnée de type Liste
    Noeud noeud; // on crée une donnée de type Noeud
    noeud.noeud_suivant =nullptr; // on indique que le pointeur noeud_suivant représente une adresse mémoire invalide
    noeud.valeur = 20; // on fournit une valeur cohérente pour la partie "valeur" de notre donnée de type Noeud
    liste.tete_de_liste = & noeud; // on fournit l'adresse mémoire à laquelle se trouve notre noeud comme "premier élément de la liste"
}

Sauf que, hehe ... Ce serait trop facile!

Car il faut considérer comme un principe immuable le fait que chaque fonctionnalité (et je parle vraiment au sens le plus large, qu'il s'agisse d'une donnée, d'une fonction ou d'un type de donnée) que tu peux développer ne vaudra quelque chose que par l'usage qui en sera fait!

Il arrive donc un moment où il faut être un tout petit peu consistant par rapport à ce que l'on fait, car il ne sert à rien de "perdre son temps" à créer une structure si ce n'est pas pour l'utiliser de manière "pleine et entière" à l'usage auquel elle est destinée.

Or, le fait que tu aies pris la peine de créer la structure Liste et, plus encore, le fait que tu aies pris la peine de créer la structure Noeud nous indique très clairement que tu souhaites mettre en place le concept de "liste (simplement) chaînée".

On peut discuter sans fin sur l'utilité qu'il y a à vouloir mettre un tel concept en oeuvre, parce qu'il se fait -- comme l'a si bien fait remarquer Teaniel -- que la bibliothèque standard le fournit effectivement déjà. Mais ce n'est pas une raison pour ignorer l'aspect pédagogique qu'il pourrait y avoir à "mettre les mains dans le cambouis" pour le mettre soi-même en oeuvre, quitte à ce que ce soit la seule fois que nous le fassions nous-même

Voyons donc en vitesse à quoi correspond ce concept : une liste (simplement chaînée) est une collection d'éléments (des valeurs entières, dans le cas présent) capable d'adapter le nombre d'éléments qu'elle contient de manière dynamique. C'est à dire que nous attendons de sa part qu'elle soit en mesure de contenir 5 élément si cela suffit tout comme nous voulons qu'elle soit en mesure d'en contenir ... 100 000 si le besoin venait à s'en faire sentir

Or, les corrections que j'ai apportées jusqu'à présent au code ne fonctionneront que pour ... un seul élément. Ce qui est, il faut bien le dire, très loin de représenter l'usage "classique" que l'on s'attend à pouvoir faire de ce concept

Car le terme est lancé : le nombre d'éléments doit pouvoir évoluer de manière dynamique.

Et ce simple terme nous fait entrer dans une toute nouvelle dimension, pleine de pièges, de chausses trappes et de subtilités en tout genre, nommée "la gestion dynamique de la mémoire".

Cette dimension est composée d'un matériaux très particulier, tiré de la constatation "toute simple" qui est que nous ne pouvons pas déterminer, au moment d'écrire le code, le nombre d'éléments que la liste chaînée, et de sa conséquence logique: il ne sert absolument à rien d'essayer de faire en sorte de réserver "suffisamment de mémoire" pour représenter "l'ensemble de tous les éléments qui seront placés dans la liste", vu que, dans le "meilleur des cas" nous en aurions "beaucoup trop" et que toute la mémoire "inutilisée" risquerait de faire défaut aux "autres processus" lancés par l'ordinateur, et parce que, dans le pire des cas, nous risquerions quand même de ne pas en avoir assez

Et surtout, elle est régie par quatre règles simples:

1. Seul le système d'exploitation est en mesure de fournir de la mémoire supplémentaire à l'application
2. La mémoire fournie par le système d'exploitation n'est que "prêtée" à l'application
3. l'application a obligation de rendre toute la mémoire prêtée au système d'exploitation et
4. le système d'exploitation peut décider à tout moment, pour n'importe quelle raison et sans avoir à justifier sa décision de ne pas fournir la mémoire demandée par l'application

Mais avant de t'aider à entrer dans cette dimension, je dois te mettre en garde:

Elle est peuplée par énormément de personnes, et par de nombreux cadavres que tu risques de trouver dans des états de décomposition plus ou moins avancés Toutes ces personnes et tous ces cadavres sont (ou ont jadis été) des développeurs C++. Tous te paraîtront en pleine possession de leurs moyens mentaux, et tous risquent de te donner quelques conseils destinés -- selon eux -- à t'aider à survire dans cet environnement hostile.

Mais le nombre de cadavres que tu va croiser devrait t'inciter à considérer ces conseils avec la plus grande prudence, car ils sont la preuve tangible d'un fait indéniable : de nombreux développeurs C++ ont laissé leur santé mentale ou physique dans cette dimension

Si tu décides de partir explorer cette dimension, ce doit être de ton plein gré, en sachant que tu risques, toi aussi, d'y laisser ta santé mentale (dans le meilleure des cas), et peut-être même ta santé physique.

Je vais donc te laisser réfléchir quelques instants avant de te demander si tu souhaites que nous entreprenions l'exploration de cette dimension parallèle ensemble, au moins, jusqu'à ce que tu te sentes capable d'y survire seul