Discussion :

[beegees]

Bonjour tout le monde,

J'aimerais me déplacer dans une liste simplement chaînée d'un élément à un autre.

Je vérifie si le premier élément est différent de NULL :

SI Premier == NULL
RETOURNER 0;

Par contre, je ne se sais pas comment passer d'un élément à un autre.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
SINON COMPTEUR++; 
  TANT QUE Premier->Suivant != NULL;

J'ai créé un début de code mais je suis un peu bloqué.

Qu'en pensez-vous ?

Merci d'avance.

beegees

[alex_pi]

Qu'est ce que tu entends par là ? Si c'est prendre la queue de la liste, il suffit d'échouer pour la liste vide, et de retourner la queue pour les listes non vides...

[beegees]

Qu'est ce que tu entends par là ? Si c'est prendre la queue de la liste, il suffit d'échouer pour la liste vide, et de retourner la queue pour les listes non vides...

Merci mais désolé mais je ne comprends pas bien ta réponse.

Si c'est prendre la queue de la liste

oui par exemple, ça me permettrait de connaître l'adresse du dernier élément.

il suffit d'échouer pour la liste vide

Je ne commais pas cette technique, peux-tu m'en dire plus stp ?

retourner la queue pour les listes non vides

Je n'ai pas de variable "queue" pour cet exerice (voir schéma mis en attachment).

Merci encore pour ton aide.

beegees

[pseudocode]

Par contre, je ne se sais pas comment passer d'un élément à un autre.

un truc comme ca ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
Courant = Premier; 
TANT QUE {condition} FAIRE
  Courant = Courant->Suivant;
FIN TANT QUE

[beegees]

un truc comme ca ?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
Courant = Premier; 
TANT QUE {condition} FAIRE
  Courant = Courant->Suivant;
FIN TANT QUE

Bonjour PseudoCode,

J'y avais pensé mais je pensais que s'était trop simple pour être correcte.

Je vois quand même que tu hésites :

un truc comme ca ?

Donc si quelqu'un pourrait confirmer ça serait sympa.

Autre chose, ne faut-il pas commencer au premier élément lorsque l'on veut lire le xième élément d'une liste simplement chaînée ?

Merci pour sincèrement pour l'aide.

beegees

[pseudocode]

Je vois quand même que tu hésites

J'hésite plus sur sur la compréhension de ton problème que sur mon algo.

[souviron34]

il n'hésite pas, c'est juste que c'est tellement évident...

Oui c'est bien :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
Courant = Premier; 
TANT QUE {condition} FAIRE
  Courant = Courant->Suivant;
FIN TANT QUE

qui peut être écrit comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
Courant = Premier; 
TANT QUE {COURANT non NULL} FAIRE
  Courant = Courant->Suivant;
FIN TANT QUE

là tu parcours toute la liste

Tu peux aussi faire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
Courant = Premier; 
TANT QUE {COURANT non NULL} FAIRE
         SI Element(COURANT) satisfait {condition}
              fait quelque chose
              sortie du tant que
         FIN SI
  Courant = Courant->Suivant;
FIN TANT QUE

pour chercher un élément particulier...

Autre chose, ne faut-il pas commencer au premier élément lorsque l'on veut lire le xième élément d'une liste simplement chaînée ?

Si TOUT le temps..

[beegees]

J'hésite plus sur sur la compréhension de ton problème que sur mon algo.

il n'hésite pas, c'est juste que c'est tellement évident...

Oui c'est bien :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
Courant = Premier; 
TANT QUE {condition} FAIRE
  Courant = Courant->Suivant;
FIN TANT QUE

qui peut être écrit comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
Courant = Premier; 
TANT QUE {COURANT non NULL} FAIRE
  Courant = Courant->Suivant;
FIN TANT QUE

là tu parcours toute la liste

Tu peux aussi faire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
Courant = Premier; 
TANT QUE {COURANT non NULL} FAIRE
         SI Element(COURANT) satisfait {condition}
              fait quelque chose
              sortie du tant que
         FIN SI
  Courant = Courant->Suivant;
FIN TANT QUE

pour chercher un élément particulier...




Si TOUT le temps..

Je vous remercie tous les deux pour vos réponses qui m'aident énormément.

Je vous souhaîte une bonne soirée et un bon fin de Week-End.

@ bientôt
beegees

[alex_pi]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
Courant = Premier; 
TANT QUE {COURANT non NULL} FAIRE
  Courant = Courant->Suivant;
FIN TANT QUE

A priori, vu le machin entouré, ce serait plus

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
Courant = Premier; 
SI Courant est NULL ALORS échouer
TANT QUE {COURANT->Suivant non NULL} FAIRE
  Courant = Courant->Suivant;
FIN TANT QUE
RETOURNER Courant

[souviron34]

A priori, vu le machin entouré, ce serait plus

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
Courant = Premier; 
SI Courant est NULL ALORS échouer
TANT QUE {COURANT->Suivant non NULL} FAIRE
  Courant = Courant->Suivant;
FIN TANT QUE
RETOURNER Courant

non non

sauf que :

• 1) Courant est assigné en fin de "boucle", donc si il est NULL courant->Suivant ne peut se calculer => crash
  
  
• 2) pour le dernier, courant->suivant est NULL, donc on ne passerait pas dans le dernier. Donc, si tu veux récupérer le dernier, c'est bon, mais si tu veux vérifier une condition ou faire un total ou n'importe quoi sur le contenu de la structure, ça marche pas....
  (tu t'arrêtes à l'avant-dernier)

[alex_pi]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
Courant = Premier; 
TANT QUE {COURANT non NULL} FAIRE
  Courant = Courant->Suivant;
FIN TANT QUE

Je persiste à penser qu'avec ce code, à la fin, Courant contient toujours NULL (puisque sinon on continue la boucle), ce qui n'est pas très intéressant. Et c'est pour éviter le crash dont tu parles que dans ma version j'ai ajouté au début du code un test pour vérifier que Courant n'est pas NULL.

[pseudocode]

je vote pour exp(i.PI)

[souviron34]

Je persiste à penser qu'avec ce code, à la fin, Courant contient toujours NULL (puisque sinon on continue la boucle), ce qui n'est pas très intéressant. Et c'est pour éviter le crash dont tu parles que dans ma version j'ai ajouté au début du code un test pour vérifier que Courant n'est pas NULL.

• non non..
• Oui bien sûr à la fin Courant ne contient toujours que NULL, si on n'a pas fait de break avant..

Résumons-nous...

Que voulons-nous faire ?

• a) soit récupérer le dernier élément
• b) passer à travers toute la liste pour faire quelque chose (vérifier une condition, faire une somme, etc etc..)

D'une part, ton test avant n'élimine que si le premier élément est NULL. Ton test n'est pas dans le TANT QUE. Donc il n'évite en aucun cas le crash, uniquement si la liste est vide.

D'autre part, ton algo ne marche que pour le problème a).

Si l'on veut faire le problème b), ou bien retourner un élément x, il faudra bien passer à travers tous les éléments...

Donc

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
Courant = Premier; 
TANT QUE {Courant non NULL} FAIRE
         SI Element(COURANT) satisfait {condition}
              (éventuellment fait quelque chose)
              (éventuellement sortie du tant que)
         FIN SI
  Courant = Courant->Suivant;
FIN TANT QUE

Est un code générique permettant de traverser toute la liste.

Si l'on veut faire une opération du style une moyenne, on fera juste

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
         SI Element(COURANT) satisfait {condition}
              moy = moy + valeur(Courant)
         FIN SI

Si on veut retourner le xième élément, on fera (en ajoutant un compteur) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
         n = n  + 1
         SI n égal x
              Sortie du TANT QUE
         FIN SI
...
retourner Courant

Il suffit de prendre un exemple pour s'en convaincre :

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
Structure TOTO
     int indice
     Structure TOTO *suivant
 
Structure TOTO Table egal NULL
 
/* Premier element */
Ajoute_Element ( Table )
 
/* Ici Table = Premier element
        Premier.indice = 0
        Premier.suivant = NULL */
 
/* Deuxième élément */
Ajoute_Element ( Table )
 
/* Ici : 
      Premier.indice = 0
      Premier.suivant = Second
      Second.suivant = NULL
      Second.indice = 1
 
/* Troisiième élément */
Ajoute_Element ( Table )
 
/* Ici : 
      Premier.indice = 0
      Premier.suivant = Second
      Second.suivant = Troisième
      Second.indice = 1
      Troisième.suivant = NULL
      Troisième.indice = 2

Donc, bien sûr si l'on veut le dernier, on va partir de Table, qui est premier,
et tester sur element->suivant.

Mais cet algo n'est pas général, et ne permet pas de faire tout ce qu'on veut.
Si par exemple je veux faire la moyenne des indices, crac boum hue... Si je veux trouver les nombres pairs, ça marche pas non plus.. Bref, dès que je veux passer dans la totalité de la liste, ça ne marche pas. Le seul moyen dans ce cas-là est de parcourir TOUTE la liste, et donc de s'arrêter quand element est NULL. Et dans ce cas, lorsqu'on a atteint le dernier, et que l'on fait Courant = Courant->suivant, Courant devient NULL, et donc la condition du "TANT QUE" devient "si Courant non NULL", et non "si Courrant->suivant non NULL", car cela générerait un crash, car adresse inconnue...

Et encore une fois, si je veux en sortir un, et pas forcément le dernier, ton argument que c'est toujours NULL tombe.

En bref, ton code est bon UNIQUEMENT si on veut retourner le dernier element.
Pour toute autre opération sur une liste simplement chaînée, ça marche pas..

[alex_pi]

D'une part, ton test avant n'élimine que si le premier élément est NULL. Ton test n'est pas dans le TANT QUE. Donc il n'évite en aucun cas le crash, uniquement si la liste est vide.

Alors là j'aimerais beaucoup un exemple de liste sur lequel il crache puisqu'avant d'acceder à Courant->Suivant je vérifie qu'il est non NULL et qu'en conséquence je ne déréférence jamais de pointeur NULL...

D'autre part, ton algo ne marche que pour le problème a).

Oui, mon algo a l'avantage de répondre à la question initialement posé alors que le votre a la propriété de juste mettre Courant à NULL après avoir parcouru une liste... A la rigueur, on pourrait le décrire comme un algo de semi-décidabilité de la finitiude de la liste...

[souviron34]

Bon cool..

D'habitude je m'incline devant vos qualités respectives, à toi et pseudocode..
surtout en maths théoriques, où je suis d'une part pas forcément très fort, mais où en plus ça remonte à loin... C'est pour ça que je m'étonne de cette discussion...

Cependant, là, la question originale était :

Bonjour tout le monde,

J'aimerais me déplacer dans une liste simplement chaînée d'un élément à un autre.

Ce n'est qu'après qu'il y a eu :

oui par exemple, ça me permettrait de connaître l'adresse du dernier élément.

Je ne répondrais pas aux insultes, mais oui ton algo marche, MAIS on ne passe pas dans toute la liste...

C'est pour ça que je citais un exemple qui passe dans toute la liste, c'est tout..

[beegees]

Salut les gars,

ça fait toujours plaisir de voir qu'un de nos posts donne autant de réactions

No panic, ce soir si Dieu le veut, j'aurai la solution et je la posterai demain matin.

Merci à tout ceux qui ont participés à cette discution.

beegees

[pseudocode]

Vu qu'il y a eu 2 questions de posées (post #1 et post #3), il y a 2 réponses.

- La question "générale" sur le parcours de liste chainée.
- La question "spécifique" sur la recherche du dernier élément.

Restons courtois... ça n'est que du code.

[alex_pi]

Bon cool..

J'ai supprimé la dernière phrase de mon post qui n'avait pas sa place ici, et je m'en excuse.

[...], mais oui ton algo marche, MAIS on ne passe pas dans toute la liste...

Euh, si on passe dans toute la liste puisqu'on ne s'arrête qu'au dernier élément, c'est à dire celui dont la queue de liste est la liste vide.

Bon, pour récapituler (je sais que c'est mal de faire les devoirs des gens, mais là ça devient confu...)

Une liste est soit la liste vide (représenté ici par le "pointeur" NULL), soit un couple, constitué d'un élément (la tête) et d'un pointeur vers le reste de la liste (la queue), qui peut être éventuellement la liste vide : (t, q) ou avec une syntaxe peut être plus claire, t::q, ou dans une notation "structure" ou "objet", lst->element et lst->suivant

Pour retourner l'adresse de la liste constitué uniquement du dernier élément, on peut appliquer l'algo (non générique et adapté uniquement à ce but):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
SI courant = NULL ALORS échouer 
SINON(
  TANTQUE courant->suivant != NULL FAIRE
    courant := courant-> suivant
  FINTANTQUE
  RETOURNER courant
)

Où échouer est l'équivalent d'une exception


Si on recherche le premier élément vérifiant une condition particulière

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
TANTQUE courant != NULL FAIRE
  SI condition(courant->element) ALORS retourner courant->element
  SINON courant := courant->suivant
FINTANTQUE
échouer

On peut évidement modifier légèrement le code pour faire porter condition sur la liste commençant à l'élément courant plutôt que simplement sur l'élément ou pour retourner l'adresse de la sous liste commençant par l'élément courant plutôt que de renvoyer l'élément

Finalement, pour répondre à la question "faut-il commencer au premier élément", la réponse est "oui" puisque dans le cas d'une liste simplement chaîné, on n'a de toutes façons accès qu'au premier élément !

--
alex_pi,
qui persiste à penser que le pseudo-code (le "langage", pas le modérateur ;-)) est particulièrement douloureux et qu'utiliser un "vrai" langage (OCaml, par exemple :-D) serait quand même bien plus sympathique...

[souviron34]

nous sommes d'accord

[beegees]

Bonjour,

Je suis au cours, je profite d'une pause pour répondre à ton message.

Cette phrase m'inquiète :

[QUOTE]Finalement, pour répondre à la question "faut-il commencer au premier élément", la réponse est "oui" puisque dans le cas d'une liste simplement chaîné, on n'a de toutes façons accès qu'au premier élément ![/QUOTE]

ça veut dire qu'il faut détruire l'élément 1 et 2 pour lire le 3 ?

Merci pour l'aide et pour votre dévouement.

beegees