inversion

Bonjour a tous,
j'ai un petit probleme.
J'ai une liste chainée et j'aimerai l'inverser completement.
Par exemple j'ai [1]->[2]->[3]->[4]->NULL et j'aimerai la transformer en [4]->[3]->[2]->[1]->NULL
Comment faire?
Merci pour votre aide !!!

C'est une question algorithmique pas directement lié au C...

Sauf si tu as un algorithme et que tu ne sais pas comment le traduire en C...

Jc

Une idée:

Code:

---

1 2 3 4 5 6 7 8

Soit l1 la liste que tu veux inverser Soit l2 une liste initialisé à NULL   Tant que l1 est non vide Ajouter la tête de l1 à la tête de l2 Enlever la tête de l1 Fin tant que

---

bien le bonjour,

une solution est de parcourir ta liste et d'en creer une copie en inserant a chaque fois l'element courant au debut de la liste de copie. Ainsi les elements a en queue se retrouveront en tete

vous nauriez pas un algo ou un exemple? parske la je rame..

Citation:

---

Envoyé par mdoerper

vous nauriez pas un algo ou un exemple? parske la je rame..

---

Hmmm, j'ai déjà donner un algo...

Par contre un exemple... Si [] est une liste vide:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

l1: 1 -> 2 -> 3 -> 4 l2: []   l1: 2 -> 3 -> 4 l2: 1   l1: 3 -> 4 l2: 2->1   l1: 4 l2: 3->2->1   l1: [] l2: 4->3->2->1

---

Si tu ne comprends pas, code déjà ta gestion de liste chaînée et tente de voir comment enlever la tête et comment ajouter en tête... Ensuite reposte pour poser des questions...

Jc

Ben en fait j'ai une liste de vehicule qui contient des vehicule.La liste comme les vehicule sont des pointeur.
Une structure pour un vehicule et une structure pour la liste, elle contient un poiteur vers un véhicule et un poiteur psuivant...
J'arrive a ajouter et retirer des elements de la liste mais je ne sais pas pourquoi je n'arrive pas a inverser.
Ma fonction est

Code:

---

liste_vehicule* inverse(liste_vehicule* L)

---

J'ai bien compris ton algo mais depuis ce matin je n'arrive pas a l'appliquer et le retranscrire en C.
Ca aurait été un tableau ça aurai été simple mais là j'ai du mal.
Desole

En principe si tu as bien fait ton travail tu devrais avoir ces fonctions de base:

Code:

---

1 2 3 4 5 6

liste_vehicule* nouvelle_liste(); //Rend une liste vide liste_vehicule* ajoute_elem(vehicule*, liste_vehicule*); //Ajoute un element en tete liste_vehicule* enleve_tete(liste_vehicule*); //Enleve la tete de la liste int liste_est_vide(liste_vehicule*); //Rend 1 si vide, 0 sinon vehicule* tete(liste_vehicule *); //Rend la tete de la liste

---

Si tu as ces fonctions, alors ta fonction inverse deviendrait:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

liste_vehicule* inverse(liste_vehicule * liste) { /*Creer une nouvelle liste*/ liste_vehicule *res = nouvelle_liste();   /* Tant que la liste de départ n'est pas vide */ while( liste_est_vide( liste) ) { /* On ajoute la tete sur la liste d'arrivee */ res = ajoute_elem_en_tete( tete(liste) ); /* On enleve la tete de la liste */ liste = enleve_tete(liste); } /* On rend l'inverse */ return res; }

---

Remarque que dépendant de l'implémentation des fonctions de bases, toute modification de l'inverse répercutera sur la liste de base...

Autre remarque, si tu regardes mon algo et finalement le code écrit, c'est la même chose... D'où l'importance d'avoir les fonctions de bases...

Jc

Pour creer la nouvelle liste je suis d'accord moi j'ai fais une fonction

Code:

---

init_liste()

---

(au debut je penser faire RES=L)
Pour le test je pensais a un

Code:

---

while(l->next!=NULL)

---

Pour enlever la tete je penseais a

Code:

---

l=l->next ...

---

Donc jusque là je pense que l'on parle de la meme chose mais il est vrai que je ne sais pas copier une tete vers une autre tete car moi je ne faisai mes ajout qu'a la fin de la liste (plus simple)

Citation:

---

Envoyé par mdoerper

(au debut je penser faire RES=L)

---

cela aurait été un problème puisque la liste res doit commencer vide...

Citation:

---

Envoyé par mdoerper

Pour le test je pensais a un

Code:

---

while(l->next!=NULL)

---

---

Je ferais

Code:

---

1 2	while(liste != NULL)

---

puisque rien ne prouve que tu as un élément dans ta liste...

Citation:

---

Envoyé par mdoerper

Pour enlever la tete je penseais a

Code:

---

l=l->next ...

---

---

C'est pareil...

Pour ajouter un élément en tête de liste le plus simple et de faire un dessin sur une feuille...

Je veux ajouter C dans la liste res=A -> B... quels pointeurs dois-je mettre à jour?

Citation:

---

Envoyé par mdoerper

car moi je ne faisai mes ajout qu'a la fin de la liste (plus simple)

---

Du tout, c'est plus compliqué... il faut arriver jusqu'à la fin... Le début, on l'a tout de suite...

Jc

Citation:

---

Envoyé par fearyourself

Je veux ajouter C dans la liste res=A -> B... quels pointeurs dois-je mettre à jour?

---

Il faut que C pointe vers res (donc A) et ensuite res pointe vers C
C'est ça?

Citation:

---

Envoyé par mdoerper

j'ai un petit probleme.
J'ai une liste chainée et j'aimerai l'inverser completement.
Par exemple j'ai [1]->[2]->[3]->[4]->NULL et j'aimerai la transformer en [4]->[3]->[2]->[1]->NULL

---

Dommage que tu n'ais pas une liste doublement chainée !

Sinon, c'est simple. Il faut déplacer les éléments dans une deuxième liste en insérant en tête...

C'est de l'algorithmique de base... Rien à voir avec le langage C...

L'inversion d'une liste est un algo assez simple : le principe est :
Ta liste est consituée d'une tête et d'un suivant, donc pour l'inverser il suffit de travailler avec le suivant

Code:

---

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

entrée : la tete de la liste à inversée retour : la tete de la nouvelle liste inversée   fonction inverse(Liste tete) retour : Liste   Variable cur type Liste : pointeur courant sur la liste Variable p type Liste : pointeur sur le suivant de cur suivant Variable q type Liste : pointeur temporaire pour mémorisation   debut commentaire : si la tete de liste est NULL, on n'a rien à faire si tete <> NULL alors commentaire initialisation du parcours de liste cur <= tete Commentaire : on a accès au suivant p <= cur->suivant Commentaire : on peut maintenant faire que tete soit le dernier noeud cur->suivant <= NULL Commentaire : on parcourt maintenant la liste en inversant les liens tant que p <> NULL faire commentaire : on mémorise le suivant de p pour conserver l'ancien lien q <= p->suivant commentaire : on connecte maintenant le suivant de p à son précédent mémorisé dans tete p->suivant <= cur commentaire : on avance d'un cran cur <= p fin tant que commentaire ! la tete de la liste est maintenant cur tete <= cur fin si renvoyer tete fin

---

Citation:

---

Envoyé par Trap D

Code:

---

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

entrée : la tete de la liste à inversée retour : la tete de la nouvelle liste inversée   fonction inverse(Liste tete) retour : Liste   Variable cur type Liste : pointeur courant sur la liste Variable p type Liste : pointeur sur le suivant de cur suivant Variable q type Liste : pointeur temporaire pour mémorisation   debut commentaire : si la tete de liste est NULL, on n'a rien à faire si tete <> NULL alors commentaire initialisation du parcours de liste cur <= tete Commentaire : on a accès au suivant p <= cur->suivant Commentaire : on peut maintenant faire que tete soit le dernier noeud cur->suivant <= NULL Commentaire : on parcourt maintenant la liste en inversant les liens tant que p <> NULL faire commentaire : on mémorise le suivant de p pour conserver l'ancien lien q <= p->suivant commentaire : on connecte maintenant le suivant de p à son précédent mémorisé dans tete p->suivant <= cur commentaire : on avance d'un cran cur <= p fin tant que commentaire ! la tete de la liste est maintenant cur tete <= cur fin si renvoyer tete fin

---

---

Je ne suis qu'un débutant mais a premiere vu ton code est erroné car tu sauvegarde une valeur dans la variable temporaire Q mais tu ne la réutilise pas? Erreur?
Du coup je reste bloqué dans la boucle while

Tout à fait, erreur de recopie (je l'ai fait à partir d'un prog C

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

debut commentaire : si la tete de liste est NULL, on n'a rien à faire si tete <> NULL alors commentaire initialisation du parcours de liste cur <= tete Commentaire : on a accès au suivant p <= cur->suivant Commentaire : on peut maintenant faire que tete soit le dernier noeud cur->suivant <= NULL Commentaire : on parcourt maintenant la liste en inversant les liens tant que p <> NULL faire commentaire : on mémorise le suivant de p pour conserver l'ancien lien q <= p->suivant commentaire : on connecte maintenant le suivant de p à son précédent mémorisé dans tete p->suivant <= cur commentaire : on avance d'un cran cur <= p p <= q <=== manque cette ligne fin tant que commentaire ! la tete de la liste est maintenant cur tete <= cur fin si renvoyer tete fin

---

Les listes c'est profondément récursif comme définition, alors les algorithmes sont naturellement récursifs.

Donc au début, code en récursif, et convertis-le en itératif à la fin si besoin est.

Merci beaucoup a tous pour votre aide.
J'ai enfin (et pour la premiere fois) réussi a inverser une liste chainée..

Bonjour à Tous

Je viens pour ajouter une petite contrainte, la même chose mais sans retour de pointeur c'est à dire que le pointeur sur liste en paramètre pointe sur la liste inversée en sortie. C'est une des colles que j'ai eu à un entretien pour un stage, qui s'est terminé par un echec d'ailleurs....!

Merci pour votre aide...

Cela devrait se trouver dans un nouveau thread...

Mais bon,

En supposant que ta liste chaînée soit définie comme ceci:

Code:

---

1 2 3 4 5 6

typedef struct sListe { int v; struct sListe *next; }SListe;

---

Nous avons montré qu'il est possible d'avoir comme prototype de la fonction inverse:

Code:

---

SListe *inverse(SListe *liste);

---

Par contre, il est impossible en C de faire le travail avec ce genre de prototype:

Code:

---

void inverse(SListe *liste);

---

A moins que la liste est un premier élément qui ne sert à rien à part être le début de la liste, ie ce 1er élément restera 1er après l'inversion.

Par contre, ceci est possible:

Code:

---

void inverse(SListe **liste);

---

Jc

Le truc c'est justement de le faire sans double pointeur....

Citation:

---

Envoyé par DreadNum

Le truc c'est justement de le faire sans double pointeur....

---

Sans double pointeur, sans retour et sans le premier élément qui est là comme sentinelle, il est impossible (à mon avis) en C d'inverser une liste. Je parle bien sûr de liste simplement chaînée...

Cela devait être une question piège...

Jc

En fait ça donnerait ça

void reverseString( struct elem* parFirst);
{
elem *tmp1,*tmp2;
char c;

tmp1 = reverString( parFirst->suivant); // même fonction ms avec retour
tmp2 = tmp1->suivant;
tmp1->suivant = NULL;
parFirst->suivant -> suivant = tmp1;
parFirst->suivant = tmp2;
c = parFirst->caractere;
parFirst->caractere = tmp1->caractere;
tmp1->caractere = c;
}
on part de parFirst->s->a->l->u->t->NULL
et on obtient

result->t->u->l->a->NULL

et tjs parFirst->s


on dit que la première cellule devient la dernière de facon à avoir

u->l->a->t->NULL

ensuite on dit que parFirst->suivant->suivant (s pointe tjs sur a) est égale à u et on se retrouve avec

parFirst->s->u->l->a->t->NULL

et il suffit d'inverser les valeurs des deux cellules aux extremités.

et en fin parFirst->t->u->l->a->s->NULL


Et la chaine est inversée

J'ai pas lu toute la réponse mais je cite ta question:

Citation:

---

la même chose mais sans retour de pointeur

---

Et après ta solution appelle:

Code:

---

tmp1 = reverString( parFirst->suivant); // même fonction ms avec retour

---

Je trouve qu'utiliser une fonction qui retourne quelque chose est une façon de tricher. Masi bon, il y aurait à ce moment là plus simple:

Code:

---

1 2 3 4 5 6 7 8 9 10 11

void inverse(SListe *liste) { SListe *inv; if(liste!=NULL) { inv = superinversequifaittoutleboulot(liste); liste->val = inv->val; liste->next = inv->next; } }

---

Mais je suppose généralement lorsqu'on applique des modification de la liste chaînée que ce qui nous intéresse est modifié l'ordre du chaînage et non pas la valeur dans les éléments. Une solution comme tu (ou ma version) fonctionne bien sûr mais cela ne sert pas à grand chose lorsqu'on a une liste chaînée où chaque élément contient un millers d'éléments...

C'est pour cela que je dis que ce n'est pas possible. Echanger le contenu des éléments d'une liste chaînée ne me vient pas à l'esprit...

Jc

Nan mais je suis d'accord avec toi que c'est la question con, juste pr l'exo. Après ds la pratique, c'est clair que tu fais pas ce genre de chose...;-)

@+

Je repars sur Paris pour d'autres entretiens....

Citation:

---

Envoyé par fearyourself

Citation:

---

Envoyé par DreadNum

Le truc c'est justement de le faire sans double pointeur....

---

Sans double pointeur, sans retour et sans le premier élément qui est là comme sentinelle, il est impossible (à mon avis) en C d'inverser une liste. Je parle bien sûr de liste simplement chaînée...

Cela devait être une question piège...

---

Pas forcément.

On peut aussi passer l'adresse d'une structure contenant le pointeur. C'est certes une une façon déquisée (mais élégante) de passer un 'double pointeur', tout en conservant une syntaxe claire (p->x) et une approche 'objet'.

Il n'est pas rare de faire comme ceci :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

struct node { struct node *p_next; struct node *p_prev; long id; /* identificateur de donnees generiques */ void *p_data; /* adresse des donnees generiques */ };   struct dlist { struct node * p_head; struct node * p_tail; struct node * p_curr; };

---

etc.