Discussion :

[naniate]

peut-on creer une liste des listes chainées et comment peut-on faire ?

[Sve@r]

peut-on creer une liste des listes chainées

On peut faire des listes de tout...

et comment peut-on faire ?

Déjà commencer par bien poser le truc parce que sinon ça peut vite partir en torche. Donc bien identifier ses différents éléments. Un élément pour manipuler une liste, un élément pour manipuler un membre de la liste etc.
Puis identifier ses différentes opérations. Une opération pour créer un membre, une opération pour insérer le membre dans la liste etc.
Plus on travaille modulaire et structuré en amont plus on a des chances d'écrire un code simple, sans bug et de l'écrire facilement. Mais j'ajouterais que c'est pas vraiment un truc à la portée du débutant...

PS: En dehors de l'exercice de style qu'on écrit pour se faire plaisir, le concept de liste chaînée ne se justifie que si il y a derrière une notion de tri et de conservation de l'ordonnancement. Ainsi, avec une liste chaînée, le nouvel élément pourra être facilement inséré à sa bonne place alors que c'est plus difficile (mais pas impossible) avec un tableau.
Mais si la notion d'ordre n'existe pas, alors la liste chaînée n'a plus de raison d'être et il est préférable de la remplacer par un tableau dynamique. Chaque nouvel élément viendra s'ajouter en fin de tableau qui sera réagrandi au besoin. On supprime ainsi les problèmes liés aux algorithmes de manipulation de liste et on peut utiliser en plus des outils de manipulation de tableau (comme le pointeur sur le premier élément qui s'incrémente par exemple).
Donc je conçois bien une liste chaînée pour manipuler des personnes (un carnet d'adresse), des mots (un dictionnaire), des fichiers (un répertoire) où on peut inclure une notion d'ordre relatif (tel mot est placé avant tel autre) mais je m'imagine mal d'utiliser des listes chaînées pour manipuler un ensemble de listes chaînées (comment dire que telle liste sera avant telle autre). Mais bon, je peu pas non plus tout savoir sur les besoins des uns et des autres. C'était juste une petite réflexion personnelle que je voulais faire partager...

[souviron34]

Mais si la notion d'ordre n'existe pas, alors la liste chaînée n'a plus de raison d'être et il est préférable de la remplacer par un tableau dynamique.

d'acccord avec le reste, mais pas avec ça...

A cause des non-libérations réelles de free, et si tu as une appli roulant 24/24, tu peux crasher ton système avec des realloc de tableaux, pour peu que tes tableaux varient beaucoup en taille...

(ça m'est arrivé, alors je connais le pbe )

[Sve@r]

d'acccord avec le reste, mais pas avec ça...
A cause des non-libérations réelles de free, et si tu as une appli roulant 24/24, tu peux crasher ton système avec des realloc de tableaux, pour peu que tes tableaux varient beaucoup en taille...

Effectivement, puisqu'il faut que le système recopie dans le nouveau tableau l'ensemble du précédent, le realloc peut entraîner parfois l'utilisation de 2 fois plus de mémoire qu'il n'est réellement demandé. J'avais pas pensé à ça.

(ça m'est arrivé, alors je connais le pbe )

C'est toujours bon d'avoir des retours d'expérience.

[souviron34]

Effectivement, puisqu'il faut que le système recopie dans le nouveau tableau l'ensemble du précédent, le realloc peut entraîner parfois l'utilisation de 2 fois plus de mémoire qu'il n'est réellement demandé. J'avais pas pensé à ça.

ben c'est surtout que c'est pas 2, c'est N....

Admettons que ton tableau puisse à certains moments contenir 5 données, puis 1000, puis 60, puis 100000, puis 40, etc...

Bien entendu () ce n'et pas la seulle allocation que tu fais.. Lorsque la réallocation est plus petite, pas de problèmes... Mais comme entre le moment où tu es passé de 1000 à 60 et celui où tu vas passer de 60 à 100000, tu as alloué et fais pleins d'autres choses, le tableau se mettra à la fin, et donc cela ne FAIT QUE CROITRE.... alors que la vraie plage mémoire de ton prog est remplie de trous....

Donc, en résumé :

• si tu connais la dimension max , tu l'assignes dès le départ
• si tu ne la connais pas, mais que il y a peu de données possibles, alloc dynamique
• si tu ne la connais pas, mais que le prog roulera peu de temps, (et que l'alloc est pas ds une boucle), alloc dynamique
• si tu ne la connais pas, mais que les variations seront faibles (sans autres allocs au milieu), alloc dynamique
• si tu ne la connais pas, mais variations importantes, runtime long, allocs mélangées, liste chainée..

(Et note bien que dans mon cas particulier, il y avait une notion d'ordre (qui pour moi était vitale et facile à utiliser avec un tableau (gràce aux indices)), et que j'ai dû remplacer par une "optimisation" un peu obscure, où pour garder mes indices je stockais l'adresse de certains éléments de la liste chaînée : totalement à déconseiller, mais la seule solution à mon problème.. : parcourir une liste de plus de 100 000 points, plusieurs fois par secondes, et avoir un temps de réponse correct, alors que ce qui m'intéresse est 6 petites plages d'"indices" dans ces 100000 points)