Discussion:Liste chaînée

Ancien contenu

Ancien contenu

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 Suppression

 

Titre

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

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

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++

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ébut et fin qui 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 sur supprimer_dernier dans le cas vide, bug introduit par le faux sentiment de sécurité vu fin ne plante pas... J'y mis un assert du coup, mais il faudrait harmoniser...

• J'aurai trouvé un while (index->suivant) plus expressif qu'un while (index->suivant != nullptr) ou encore if (not index->suivant) bien plus parlant que if (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.

--Luc Hermitte (discuter) 14 juillet 2021 à 11:34 (CEST)