Discussion :

[m@tix]

Bonjour,

Je cherche à réaliser une procédure qui permettrait d'inverser les éléments d'une liste chaînée, c'est-à-dire que les éléments de tête deviendraient les éléments de queue. Je ne vois pas comment m'y prendre, pouvez-vous me montrer en m'expliquant svp?

Merci d'avance.

[PRomu@ld]

Tout dépend de la nature de ta liste, est-elle doublement/simplement chaînée ?

Sinon, l'idée de base c'est de faire appel à la récursivité.

[m@tix]

Elle est simplement chaînée. Comment ferais-tu alors?

[Hephaistos007]

L'inversion d'une liste revient à inverser le chainage entre les cellules prisent deux-à-deux. Pour cela, il faut disposer de trois pointeurs en permanence, et d'itérer en parcourant la liste du début à la fin (dans le sens du chainage d'origine).

Les trois pointeurs sont :

- current : le pointeur de la cellule courante
- previous : le pointeur de la cellule précédente
- next : le point de la cellule suivante

Dis autrement, tu as trois pointeurs qui pointent sur trois cellules successives de la liste (disons A, B et C). A quoi ca sert ? D'une part, current et next te permettent d'inverser le chainage entre deux cellules A et B. Le next te permet de pouvoir continuer le parcours de ta liste à partir de C, c-a-d dans le sens du chainage d'origine (important car tu viens d'inverser un chainage et donc de "briser" le sens de parcours de ta liste).

En répétant cette inversion sur toute la liste, c'est gagné. Il faut juste faire attention au cas particulier, lors de la première et de la dernière itération.

Bon courage.

[m@tix]

Bonsoir!

Tout d'abord, merci beaucoup pour ta réponse, je pense avoir compris le principe d'inversion que tu expliques. Il me semble que j'avais déjà vu une méthode d'inversion faisait intervenir la récursivité, mais pas moyen de remettre la main dessus..

Concernant ta méthode, même si je sens que j'ai compris les grandes lignes, j'ai du mal à la "mettre en forme"... Pourrais-tu stp me proposer (en m'expliquant si possible) un code?

Encore merci.

[Hephaistos007]

Grosso-modo, ca donne un truc comme ca :

Code pseudo-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
 
Procedure InverserListe(L: Liste) is
  Liste previous;
  Liste current;
  Liste next;
 
Début
 
  -- Situation de départ
  previous <- L;
  current <- previous ^.suivant;
  next <- current^.suivant;
 
  Tant que next <> Nil faire
      -- sauvegarde pour poursuivre le parcours de la liste     
      next <- current^.suivant;
      -- Inversion chainage
      current^suivant <- previous;
      -- On décale le tout pour recommencer
      previous <- current;
      current <- next;
  Fin Faire
 
Fin;

[m@tix]

Merci Hephaistos007! Je vais relire ton algo avec soin, pour essayer de comprendre.