Discussion:Liste chaînée
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Cet article est indexé par les projets Informatique et Mathématiques.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Bon début | Moyenne |  | Informatique (discussion • critères • liste • stats • hist. • comité • stats vues) |
| À évaluer |  | Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues) | |
Cet article ne comporte pas de liste de tâches suggérées. Vous pouvez saisir une liste de tâches à accomplir (par exemple sous forme d'une liste à puces), puis sauvegarder. Vous pouvez aussi consulter la page d'aide.
Ancien contenu[modifier le code]
A. Listes chaînées simples 1. Définition
La liste chaînée organise l’information séquentiellement comme dans la structure de tableau que l’on a pu voir précédemment. Chaque maillon/nœud de la chaîne contient une information et un lien sur le nœud suivant. On représentera la liste de la façon suivante :
[schemas non disponible]
L’avantage de cette structure par rapport à la structure tableau est qu’elle est dynamique, on peut ajouter et retirer des éléments de la liste à notre guise, en ayant une gestion mémoire optimale. Il n’est donc pas nécessaire de connaître à l’avance la taille maximale de la liste. 2. Mise en oeuvre
Une liste chaînée est une suite de pointeurs sur des objets contenant l’information. La structure de base d’une liste chaînée est la suivante :
En programmation procédurale , il faut utiliser les pointeurs explicites:
typedef struct LC { int info ; structLC *suivant }myLC
En POO (Java), la liste fera l’objet d’une classe :
Classe Nœud
Variables :
info Nœud nœud_suivant Fin Classe
On peut remarquer que les déclarations ne sont pas très éloignées l’une de l’autre, cependant, il y a des différences à l’utilisation (plus besoin de pointeur pour la POO) :
Pour appeler le nœud suivant dans le premier cas :
Nœud *tete tete->noeud_suivant
La déclaration d’une liste simplement chaînée se fera de la manière suivante :
#include <stdio.h>
int main(int argc, char *argv[]) {
myLC *tete ; tete = NULL ;
tete = (myLC *)malloc(sizeof(myLC)) ; // création de la tête
if (tete == NULL) printf(« Erreur d’allocation de la mémoire ») ;
.. }
Tous les algorithmes qui suivront sont des fonctions qui doivent être contenues dans l’algorithme précédent.
3. Primitives
a) Déplacement
[schemas non disponible]
Comme on peut le voir sur le schéma précédent, déplacer un nœud dans une liste consiste à changer 3 liens, quelque soit l’endroit où se trouve ce nœud. L’algorithme qui permet cette modification est le suivant : Début Modification(tete,nœud_depart,nœud_fin) // on suppose que nœud_depart est le nœud juste avant celui qu’on veut déplacer, et nœud_fin, le nœud derrière lequel on veut mettre le nœud choisi. Si le nœud fin est vide, on déplace devant la tête de la liste Variables locales : Nœud nœud_choisi Si nœud_depart est vide Alors nœud_choisi tete tete suivant(nœud_choisi) Sinon nœud_choisi suivant(nœud_depart) suivant(nœud_depart) suivant(nœud_choisi) FinSi Si nœud_fin est vide Alors suivant(nœud_choisi) tete tete nœud_choisi Sinon suivant(nœud_choisi) suivant(nœud_fin) suivant(nœud_fin ) nœud_choisi FinSi
Fin Modification
b) Suppression
[schemas non disponible]
Comme on peut le voir sur le schéma précédent, supprimer un nœud dans une liste consiste modifier 1 lien (il faudra supprimer de la mémoire le nœud supprimer si on n’utilise pas Java). L’algorithme qui permet cette modification est le suivant : Début Suppression(tete,noeud) // on suppose que « nœud » est le nœud juste avant celui qu’on veut supprimer Variables locales : Nœud pointeur Nœud aEffacer
Si nœud est vide Alors aEffacer tete tete suivant(aEffacer) Libere(aEffacer) Sinon aEffacer suivant(noeud) suivant(noeud) suivant(aEffacer) Libere(aEffacer) FinSi Fin Suppression
c) Insertion
[schemas non disponible]
Comme on peut le voir sur le schéma ci-dessus, insérer un nœud dans une liste consiste modifier 2 liens.
L’algorithme qui permet cette modification est le suivant :
Début InsérerAprès(tete,nœud,noeudAInsérer) // si nœud est vide, on insère avant la tete Si nœud est vide Alors suivant(noeudAInserer) tete tete noeudAInserer Sinon suivant(noeudAInsérer) suivant(nœud) suivant(nœud) noeudAInsérer FinSi
Fin SuppressionTitre[modifier le code]
J'aimerais faire remarquer que la nouvelle orthographe de chaînée est chainée (réforme 1990). Quelqu'un sait-il si l'orthographe adoptée sur Wikipédia est standard ou réformée ?
- Il semblerait que cela ne soit pas obligatoire (Catégorie:Graphie de 1990) : « comme Wikipédia ne favorise pas cette norme graphique qui n'est pas encore largement utilisée, les articles concernés sont donc tous des redirections sauf exceptions ». Et la redirection existe. Sanao 12 novembre 2006 à 16:59 (CET)
Exemple concret d'un liste[modifier le code]
Est-il intéressant de proposer une version complète d'une liste ? Par exemple, on peut montrer le code source des fonctions nécessaires à une insertion ou à une suppression. Je suis capable de faire cela en C/C++ mais je ne sais pas si cela est judicieux (cela pourrait surcharger l'article).MGK (discuter) 18 juillet 2014 à 18:22 (CEST)
- Pour l'instant, je vais commencer par proposer une classe en C++ basique avec une méthode pour ajouter un élément au début et en supprimer un à la fin. Il réutilisera la structure proposée en C.MGK (discuter) 18 juillet 2014 à 18:31 (CEST)
Pertinence du langage C++ dans l'exemple complet[modifier le code]
Le langage C++ disposant dans la STL de la classe list, qui permet de faire des listes doublement chaînées (ce que n'indique pas l'article qui pourrait renvoyer à Sequence container (C++)#List (en) pour ne pas induire en erreur le lecteur sur ce point), il me semble plus pertinent de proposer un exemple en C. --Treebeard (discuter) 21 octobre 2014 à 11:40 (CEST)
Amélioration du code C++[modifier le code]
J'ai procédé à une correction et amélioration du code C++.
Entre autres choses dans la fonction membre d'ajout, le new est réalisé en tout premier pour offrir une garantie forte de résistance aux exceptions: si le new échoue, l'instance n'est pas altérée.
Je suis resté sage dans mes modifications.
- Idéalement, il faudrait séparer itération et point d'entrée vers les chaînons. Cela permettrait d'éviter les opérations
débutetfinqui moulinent systématiquement alors que l'on pourrait stocker ces 2 pointeurs dans la liste. AMA, on n'est plus àsizeof T*sur les machines où nous faisons de l'allocation dynamique. Cependant cela nécessiterait l'introduction d'une notion d'itérateur indépendante.
- Je n'ai pas touché à la programmation défensive en place, alors que l'on pourrait avoir des préconditions fortes à base d'
assert()-- en attendant le support de la programmation par contrat dans une version future du langage. Note que cela aurait évité le bug sursupprimer_dernierdans le cas vide, bug introduit par le faux sentiment de sécurité vufinne plante pas... J'y mis un assert du coup, mais il faudrait harmoniser...
- J'aurai trouvé un
while (index->suivant)plus expressif qu'unwhile (index->suivant != nullptr)ou encoreif (not index->suivant)bien plus parlant queif (index->suivant == nullptr).
Bref, +1 aux autres remarques pour utiliser une formulation plus algorithmique (comme sur la page anglaise) plutôt que d'ouvrir la porte à des subtilités sur chaque choix de langage.