by TorTukiTu » Sat Dec 01, 2012 9:30 am
XITRAM, une lsite chainée est une suite de composants qui pointent successivement les uns vers les autres. Typiquement, en C ces composants sont des structures, dans les langages objets, ces composants sont des objets.
Ci dessous une représentation schématique d'une liste chainée:
[img:cdf9d0f3f4]http://img16.imageshack.us/img16/5167/listechainee.png[/img:cdf9d0f3f4]
Le principe est de pouvoir facilement parcourir une liste (une chaine) d'éléments.
L'idée générale, c'est d'avoir entre autre donées, un pointeur qui enchaine vers l'élément suivant. Du coup, tu as juste à suivre tes pointeurs à chaque élément sur lequel tu bosses pour connaitre l'élément suivant et parcourir l'intégralité de la chaîne.
Les puissance des listes chainées est bien visible lorsqu'elles sont conjointement utilisés avec des fonctions récursives.
Par exemple, en imaginant que chacune des structures contient des informations sur un fichier, et que tu cherches à connaitre la taille totale des fichiers JPG, tu peux le faire très facilement:
[code:1:cdf9d0f3f4]
// Fonction qui parcours récursivement toute une liste chainée
fonction int calculTailleJPG(StructureFichier structure){
tailleCalculee = 0
// Si la structure courante représente un fichier JPG
SI( finiEnJPEG(structure->fileName) )
// Alors je récupère la taille de ce fichier
ALORS tailleCalculee = structure->size
// Si la structure courante pointe vers une structure suivante
SI (structure->pstruct NOT NULL)
// Alors j'éxécute cette foncion sur la structure suivante et je récupère le résultat, j'ajoute ce résultat à la taille que j'ai déjà récupéré
ALORS tailleCalculee = tailleCalculee + calculTailleJPG( structure->pstruct )
// Je renvoie la taille que j'ai calculé
return tailleCalculee
}
structure_initiale = {structureinstance}
tailleTotaleJPG = calculTailleJPG(structure_initiale)
[/code:1:cdf9d0f3f4]
Tortue 974.