Discussion :

[Community Management]

Chers membres,

Je vous présente ce tutoriel de CGi « Apprendre à programmer les listes chaînées en C » :

Une liste chaînée est un système informatique qui permet la sauvegarde dynamique de données en mémoire tout comme des variables ou tableaux, mais sans se préoccuper de leur nombre et en rendant leur allocation plus transparente.
Dans ce tutoriel, vous allez apprendre à programmer les listes chaînées en C.

Bonne lecture

[neuneutrinos]

Bon j'ai lu attentivement le contenu de ce tutoriel et certains points m'ont paru un peu étrange voir incomplet.
et ça commence dès la définition...

C'est un système informatique qui permet la sauvegarde dynamique de données en mémoire tout comme des variables ou tableaux, mais sans se préoccuper de leur nombre et en rendant leur allocation plus transparente.

On peut faire la même chose avec un tableau...
exemple simplifié:

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
//je zappe les test d'allocations ,etc...
 
typedef struct TableauSansLimite TableauSansLimite;
struct TableauSansLimite
{
 int* tab;
 int nbCase;
};
 
void init_TableauSansLimite(TableauSansLimite* tsl)//initialise proprement
{
 tsl->tab=NULL;
 tsl->nbCase=0;
}
 
void free_TableauSansLimite(TableauSansLimite* tsl)//vide proprement
{
 free(tsl->tab);
 init_TableauSansLimite(tsl);
}
 
 
void needRealloc_TableauSansLimite(TableauSansLimite* tsl,int newSize)//ré-alloue si nécessaire
{
 if(newSize>=tsl->nbCase)
 {
  tsl->tab=realloc (tsl->tab,newSize*sizeof(int));
  tsl->nbCase=newSize;
 }
}
 
int getCase_TableauSansLimite(TableauSansLimite* tsl,int indice)
{
 needRealloc_TableauSansLimite(tsl,indice+1);
 return tsl->tab[indice];
}
 
void setCase_TableauSansLimite(TableauSansLimite* tsl,int indice,int valeur)
{
 needRealloc_TableauSansLimite(tsl,indice+1);
 tsl->tab[indice]=valeur;
}
 
//utilisation
 
TableauSansLimite tab;
init_TableauSansLimite(&tab);
setCase_TableauSansLimite(&tsl,42,123);
printf("%d\n",getCase_TableauSansLimite(&tsl,42));//affichera 123

D'après la définition, cette structure est une liste chaînée...


Le tableau correspond à une architecture mémoire.
La liste chaînée en est une autre.
C'est sans tenir compte d'un nombre ou d'allocation mémoire...

un tableau

• Les éléments DOIVENT être contiguë en mémoire.
• Accès à n'importe quel élement avec un temps constant ( O(1) )
• insersion ou suppression de case aléatoire "longue" (peut demander de décaler les éléments pour garder un tableau) ( O(n) )

une liste

• Les éléments peuvent ne pas être contiguë en mémoire
• Insertion avec un temps constant ( O(1) )
• Accès séquentiel pour accéder aux éléments ( O(n) )

On dit liste chaînée, car les données sont chaînées les unes avec les autres. On accède aux données à l'aide d'un ou deux points d'entrée qui se situent la plupart du temps aux extrémités de la liste.

Dans la pratique ces points d'entrée seront des pointeurs soit sur le premier ou le dernier élément de la liste, voire sur les deux ou même mobile.

Les éléments de la liste sont chaînés entre eux à l'aide de pointeurs sur leur élément suivant ou précédent, voire sur les deux. Ces pointeurs doivent donc faire partie de l'élément. Ce qui nous orientera vers l'utilisation d'une structure du langage C (struct). Cette structure aura donc la particularité d'avoir au moins un pointeur sur des variables du même type qu'elle. Ce pointeur servira à relier les éléments de la liste entre eux. La structure contiendra bien sûr aussi les données que l'on veut mémoriser.

Très mal dit ou trop confus...
Cette parti peut être reformuler plus simplement (je propose "à froid" )

"
On dit chaînée car chaque élément possède au moins un lien vers un autre élément.

• On parle de liste simplement chaînée lorsqu'un élément ne possède qu'un lien vers l'élément suivant.
• On parle de liste doublement chaînée lorsqu'un élément possède un lien vers l'élément suivant ET précédant.

Dans la pratique, un élément sera représenté par une structure contenant la donnée ainsi qu'un pointeur vers l'élément suivant
et dans le cas d'une liste doublement chaînée, un pointeur vers l'élément précédant.

On mettra à NULL lorsque qu'u élément n'a plus de suivant (ou précédant).
[code exemple]

"

La pile n'est pas le meilleur exemple car elle ne fait pas intervenir LA propriété des listes à savoir l'insertion rapide.
Et se représente très bien avec un tableau ( exemple : la stack )
Un exemple visuel serait,par exemple, un maillon par ligne et faire une insertion et suppression de ligne.


Et pourquoi commencer de 0 à présenter les listes sans faire un comparatif avec les tableau ?

la "liste triée" aurait été un très bon endroit pour !
(comparaison avec le tri par insertion par exemple !)

Ensuite, pour donner le meilleur exemple, les "const" c'est pas pour les chiens

int Length(const pile *p)
void View(const pile *p)
//...

Là ou l'information serait utile au niveau des insertions/suppressions
pas un commentaire...

et au niveau des listes doublement chaînées, au moins un schémas de plus ne serait pas de trop ...


Ensuite classique... aucune optimisation sur les listes.

Parlera-t-on des liste chaînées circulaire ?
Parlera-t-on des liste chaînées avec sentinelle ? (un élément par défaut pour généraliser les insertions/suppressions ! )
Parlera-t-on de l'optimisation mémoire avec un chaînage XOR ? (bon celui là il est un peu à part)

Conclusion :

Bonne initiative à la base, mais incomplet...

(je ne veux pas être méchant, je dit ce que je pense être manquant ou à modifier )

voilà,voilà