Liste chainée
Résolu
taita1
Messages postés
9
Date d'inscription
dimanche 16 janvier 2005
Statut
Membre
Dernière intervention
17 novembre 2009
-
18 janv. 2005 à 14:26
taita1 Messages postés 9 Date d'inscription dimanche 16 janvier 2005 Statut Membre Dernière intervention 17 novembre 2009 - 25 janv. 2005 à 15:27
taita1 Messages postés 9 Date d'inscription dimanche 16 janvier 2005 Statut Membre Dernière intervention 17 novembre 2009 - 25 janv. 2005 à 15:27
A voir également:
- Inverser une liste chainée algorithme
- Inverser une image photoshop - Forum Graphisme/design
- Inverser couleur photoshop ✓ - Forum Visual Basic 6
- Inverser blanc et noir - Forum Visual Basic
- Inversion de couleur ✓ - Forum Visual Basic 6
- Parcourir une liste java ✓ - Forum Java
2 réponses
taita1
Messages postés
9
Date d'inscription
dimanche 16 janvier 2005
Statut
Membre
Dernière intervention
17 novembre 2009
25 janv. 2005 à 15:27
25 janv. 2005 à 15:27
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!
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!
cs_darktoto
Messages postés
14
Date d'inscription
jeudi 20 novembre 2003
Statut
Membre
Dernière intervention
29 août 2006
20 janv. 2005 à 22:47
20 janv. 2005 à 22:47
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.
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.
