Version imprimable
J'ai écrit une fonction qui inverse les éléments de la liste. Le prototype de la fonction est :
Je suis passée par la méthode des nouveaux éléments mais j'aimerai savoir comment appliquer rien qu'un jeu de pointeurs.Code:int rev_list(t_list **begin)
Merci d'avance.
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.
si mais comme je l ai dit je voudrais plutot une methode par pointeurs
euh:calim2: ???
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.
merci:ccool:
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 :
Une dizaine de lignes de code suffisent pour implémenter cette méthodeCode:
2
3
4
5
6
7
8
9invlist = 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
Symboliquement, ce processus (pour le début)correspond au schéma ci-dessous
Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16list----->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--^
ah oui ,
je l'avais oublié celle là....
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...Citation:
Envoyé par jabbounet
Il y a beaucoup à faire avant de sortir la grosse artillerie (liste doublement chainée).