Discussion :

[Matheux14]

Bonjour,

Ecrire un module qui permet de renverser une liste chainée.

Code Algorithme :

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
FONCTION Renverser(tete : liste) : liste
 
                  VARIABLE
 
                   r ; P : liste
 
 
DEBUT 
 
 
            r <-- Nil
 
         TANTQUE tete <> Nil FAIRE 
 
           P <-- tete
 
           tete <-- tete^.suivant
 
           P^.suivant <-- r
 
           r <-- P
 
        FINTANTQUE
 
          RETOURNER(r)
 
FIN

[Galet]

Bonjour Matheux14,
Je prends le relais de Tbc92 (que tu as un peu usé malgré sa bonne volonté).
Tes programmes sont emplis de problèmes de fond. Tu dois commencer par reprendre les bases (et tes cours) avant de poser une question. En réfléchissant, avant de poster, tu gagneras du temps...et de l'aide.
Bonne journée.

[Mat.M]

bonsoir pour inverser une liste chainée, une méthode simple un peu à l'arrachée c'est de positionner sur le dernier élément.
En prenant le dernier élément de la liste A,on recrée une nouvelle liste B et le premier élément de la liste B sera le dernier de la liste A et ainsi de suite

[Matheux14]

D'accord mais j'ai du mal à traduire cela en termes algorithmiques..
Pourriez vous m'aider s'il vous plait

[Galet]

D'accord mais j'ai du mal à traduire cela en termes algorithmiques..
Pourriez vous m'aider s'il vous plait

Bonjour,

Méthode 1 :
Dans une liste chainée, un élément N pointe vers l'élément suivant, c'est à dire N+1. Le dernier élément ne pointe plus sur rien.
A->B->C->D...
Tu peux donc penser à une boucle qui traite, en partant du premier, chaque élément tant que le pointeur vers N+1 (successeur) n'est pas nul.
Ce raisonnement, mis en forme, te permettra de scruter ta liste d'origine.

Le plus simple, dans un premier temps, est de construire une seconde liste (cible). Il te suffira ensuite de supprimer la première.

Pour la cible, à partir du premier, tu copies le N+1, et tu le fais pointer vers N (qui est donc le prédécesseur du N+1). Le premier élément copié se retrouvera ainsi en fin de liste puisqu'il ne pointera sur rien. Ta liste sera inversée.
A<-B<-C<-D...
N'oublies pas de mémoriser le dernier élément de la Cible qui devient donc le premier de ta liste.

Méthode 2 :
Tu ajoutes à chaque élément N, un pointeur qui indique l'élément qui le précède (N-1=prédécesseur).
En parcourant ta liste du premier jusqu'au dernier (Même principe que pour la méthode 1), tu initialises ce nouveau pointeur de N vers N-1. Tu as ainsi, une liste doublement chainée car chaque élément N connait son prédécesseur (N-1) et son successeur (N+1). Le premier n'ayant pas de prédécesseur et le dernier pas de successeur.
Tu pourras alors parcourir ta chaine dans l'un ou l'autre des sens (en remontant ou en descendant).
A<->B<->C<->D...

A toi de jouer...

[Matheux14]

Code Algorithme :

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
33
34
FONCTION Renverser(tete : liste) : liste
 
                  VARIABLE
 
                   L ; P1 ; P : liste
 
 
DEBUT 
 
          P1 <-- NIL
 
          P <-- tete
 
          L <-- P
 
          P^.suivant <-- P1
 
          DESALLOUER(P1)
 
          P1 >
 
         TANTQUE tete <> NIL FAIRE 
 
           tete <-- tete^.suivant
 
           P^.suivant <-- P
 
              ....
 
        FINTANTQUE
 
          RETOURNER(r)
 
FIN

Comme çà ?