Liste chainée

Résolu
Signaler
Messages postés
9
Date d'inscription
dimanche 16 janvier 2005
Statut
Membre
Dernière intervention
17 novembre 2009
-
Messages postés
9
Date d'inscription
dimanche 16 janvier 2005
Statut
Membre
Dernière intervention
17 novembre 2009
-
salut je suis toute nouvelle,ma question se pose sur les listes chainées
programmées en langage c++,j'aimerai bien avoir un exemple d'exécution
et merci d'avance!

2 réponses

Messages postés
9
Date d'inscription
dimanche 16 janvier 2005
Statut
Membre
Dernière intervention
17 novembre 2009

je vous remercie d'avoir répondu à ma question bien que je me suis trompé de forum!
c'est vrai je fais des études en informatique appliquée à la gestion mais mon problème c'est que je veux savoir la syntaxe de c++ par l'exemple de manipulation des listes chainées ou autrement dits, des pointeurs.De toute façon, j'irai au forum convenant et merci encore!
3
Merci

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

Codes Sources 109 internautes nous ont dit merci ce mois-ci

Messages postés
14
Date d'inscription
jeudi 20 novembre 2003
Statut
Membre
Dernière intervention
29 août 2006

En C++? Tu t'est trompée de forum?
Et qu'entends tu exactement par exemple d'exécution? ce n'est pas très précis....
Enfin bref, si tu parlais de VB, l'espace de nom System.Collections contient les classes de
tes rêves. L'implémentation de liste figée ou chainée est faite, tu n'as qu'a utiliser.
Mais si tu veux connaître un exemple d'exécution, mon imagination peut te fournir ceci:
> A= {0,1,2,3}
{0,1,2,3}
> Push A,4
{0,1,2,3,4}
> Pop A
4
Certes cela sous entends la présence d'un interpréteur, ou d'un testeur malin...
Non je plaisante.

Peut être ne sais tu pas ce que c'est qu'une liste chainée?
Plusieurs notions te sont indispensables à la compréhension de ce qui suit:
ce que c'est qu'un tableau
la représentation d'un tableau en mémoire
un soupçon de représentation shématisé (très très simple)
une base de programmation

Définition
Une liste est composée d'élèments.
Dans une liste chainée simple, chaque élèment est relié à un autre, différent de lui même.
ex: A->B->C
les élèments A, B, et C forment une liste chainée.
Le dernier élèment d'une liste chainée n'est relié à aucun autre, et
aucun élèment n'est lié à son premier élément.
ex: C n'est lié à aucun autre
aucun élèment n'est lié à A
On dit que C est la queue, et que A est la tête.
Dans une liste chainée double, chaque élèment est relié à deux autres, différents entre eux,
et différent à lui même.
ex: A<->B<->C
Dans une liste chainée cyclique, le dernier élément est relié au premier.
ex: A->B->C->A
Une liste chainée cyclique n'a alors ni queue ni tête.
Je te laisse deviner la double liste chainée cyclique.
NB: Evidemment il existe d'autres dénomination pour liste chainée. Ce qui est important
c'est le concept.

Comment manipuler une liste chainée
A partir de la tête, d'une liste chainée tu peux obtenir tous ses élèments.
En effet, le premier est lié au deuxième, qui est lié au troisième, etc...
ex: A->B->C
de A tu va vers B
de B tu va vers C

Pour enlever un élèment d'une liste chainée, il faut lier son élèment précédent à son élèment suivant, et le tour est joué
ex: A->B->C
tu enlève B: A-> ->C
il faut lier A (le prédédent de B) à C (le suivant de B) pour obtenir: A->C
Si l'élèment à enlever est A ou C, tu devine l'exception qu'il faut gérer

Pour ajouter un élèment dans une liste chainée, il faut briser un lien. ce lien comport un élèment précédent et un élèment suivant. le précédent est à lier avec l'élèment à ajouter, et
l'élèment à ajouter à lier avec le suivant
ex: A->B->C
tu ajoute D avant C, donc tu brise le lien entre B et C:
A->B C
tu lie B à D: A->B->D C
puis D à C: A->B->D->C
Si l'élement à ajouter est avant A ou après C, tu devines encore une fois ce qui peux se passer.

L'utilité d'une liste chainée
Si tu compare un tableau à une liste chainée, d'un point de vue programmatoire
uniquement, tu te rends compte de plusieurs choses:
1. avec un tableau, tu peux accéder directement à un élèment du tableau par son index
ex: [a,b,c,d,e] est un tableau
son élement 1 est b.
2. si tu veux insérer ou supprimer un élément dans un tableau il faut toucher aux autres
ex: [a,b,c,d,e] est un tableau
si tu veux supprimer l'élèment d'index 1, c'est à dire b, il faut mettre c à la place de
b, d à la place de c, et e à la place de d, pour obtenir [a,c,d,e]
3. avec une liste, pour accéder à un élément il faut parcourir en moyenne la moitié des élèments
4. avec une liste, pour ajouter un élèment, il suffit de briser un lien et de raccommoder.

La liste chainée et le tableau ont donc des utilités complémentaires: le tableau est pratique pour les recherches et les mises à jour, la liste est pratique pour les ajouts/suppressions.
ex: pour représenter une pile d'assiette, dans laquelle tu peux ajouter une assiette ou la supprimer:
[1,1,0,0,0] = il y a 2 assiettes
[1,1,1,0,0] = on a ajouté une assiette, il y a 3 assiettes
avec un tableau c'est très simple, le nombre d'assiette te précise la position de
l'élèment à modifier pour représenter la pile d'assiettes après la modification.
[1,1,0,0,0] il y a 2 assiettes, tu dois en ajouter une, la position a modifier est
2+1=3.
ce qui devient [1,1,1,0,0].
maintenant le nombre d'assiettes est 3, si tu veux supprimer une assiette, tu dois
modifier la position 3, ce qui donne [1,1,0,0,0]

ex: pour représenter une de ces anciennes machines à distribuer les bonbons, avec une poignée à tourner, on les charge en haut, et on se fournit en bas:
B0->B1->B2 B0, B1 et B2 sont des bonbons dans la machine
lorsque l'on en rajoute, on les ajoute à la queue
si on ajoute B3: B0->B1->B2->B3
lorsque l'on se sert, on prend à la tête
si on se sert, il reste: B1->B2->B3

On choisis donc la liste chainée ou le tableau en fonction de la situation, de l'opération demandée. Le choix entre les deux se fait souvent naturellement. Parfois les deux solutions peuvent être intéressantes. Il faut alors faire appel à des structures plus complexes telles
que des tables de hashage.

Bon voila. Je n'irais pas plus loin.
Euh... sinon, tu fais des études en informatique, ou tu posais cette question juste comme
ca?
P.S.: Si tu cherchais vraiment un exemple en C++ excuse moi pour le baratin, je ne sais
pas ce qu'il m'a pris.