Discussion :

[achta]

J'ai écrit une fonction qui inverse les éléments de la liste. Le prototype de la fonction est :

Code :

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

int rev_list(t_list **begin)

Je suis passée par la méthode des nouveaux éléments mais j'aimerai savoir comment appliquer rien qu'un jeu de pointeurs.

Merci d'avance.

[jabbounet]

Il ne serait pas plus simple d'utiliser une liste circulaire doublement chainée?


en fonction du sens de parcours tu as ta liste dans un sens ou dans l'autre.

[achta]

si mais comme je l ai dit je voudrais plutot une methode par pointeurs

[jabbounet]

euh ???

si je me souviens bien de mes cours de C/C++, une liste chainée et encore plus si elle l'est doublement référence les éléments (suivant et précédent) grâce a des pointeurs....

ou alors j'ai raté quelque chose....

Si tu veux vraiment passer par une fonction sans liste circulaire doublement chainée (cela sera peu être plus couteux)
l'algo est le suivant:
Tu crée une nouvelle liste (vide).
En boucle (ça va te couter très cher si la liste est longue): tu va chercher le dernier élément de ta liste (ça va couter cher si la liste est longue) tu le retire et tu l'insère dans la nouvelle.


Maintenant si ta liste est circulaire et doublement chainée et que tu veux l'inverse tu swap chacun des pointeur (prev et next) de ta liste en faisant gaffe quand tu parcours de ne pas t'emmêler les pinceaux.



tu as probablement moyen de le faire avec un algo recursif.

[achta]

merci

[diogene]

Avec une liste simplement chainée et en ne la parcourant qu'une seule fois, on peut utiliser la méthode suivante où invlist sera l'adresse du début de la liste inversée :

Code :

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

1
2
3
4
5
6
7
8
9
invlist = list
Si list n'est pas NULL et list->suivant n'est pas NULL :
Tant que list->suivant n'est pas NULL :
   1- Détacher list->suivant de la liste :
       p = list->suivant
       list->suivant = p->suivant
   2- Et l'insérer en tête de invlist :
       p->suivant = invlist
       invlist = p

Une dizaine de lignes de code suffisent pour implémenter cette méthode

Symboliquement, ce processus (pour le début)correspond au schéma ci-dessous

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
list----->1 ->2 ->3 ->4 ->NULL
          |
invlist---^

1 -Enlever list->suivant de la liste

list----->1 ->3 ->4 ->NULL
          |   |
invlist---^   |
p--------->2--^

2- Le placer en tête de invlist

list-------->1 ->3 ->4 ->NULL
             | 
invlist-->2--^

[jabbounet]

ah oui ,

je l'avais oublié celle là....

[Emmanuel Delahaye]

Si tu veux vraiment passer par une fonction sans liste circulaire doublement chainée (cela sera peu être plus couteux)
l'algo est le suivant:
Tu crée une nouvelle liste (vide).
En boucle (ça va te couter très cher si la liste est longue): tu va chercher le dernier élément de ta liste (ça va couter cher si la liste est longue) tu le retire et tu l'insère dans la nouvelle.

Mais non. Il suffit de la lire l'ancienne liste en séquence et de faire l'insertion en tête dans la nouvelle... La nouvelle liste sera alors inversée...

Il y a beaucoup à faire avant de sortir la grosse artillerie (liste doublement chainée).