inversion [Sources]

**mdoerper** · 01/02/2006, 11h47

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 !!!

**fearyourself** · 01/02/2006, 11h56

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 :

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

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

**khayyam90** · 01/02/2006, 11h56

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

**mdoerper** · 01/02/2006, 14h22

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

**fearyourself** · 01/02/2006, 14h27

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 :

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

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

**mdoerper** · 01/02/2006, 14h43

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 :

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

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

**fearyourself** · 01/02/2006, 14h56

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

Code :

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

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 :

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
 
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

**mdoerper** · 01/02/2006, 15h09

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

Code :

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

init_liste()

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

Code :

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

while(l->next!=NULL)

Pour enlever la tete je penseais a

Code :

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

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)

**fearyourself** · 01/02/2006, 15h20

Envoyé par mdoerper

(au debut je penser faire RES=L)

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

Envoyé par mdoerper

Pour le test je pensais a un

Code :

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

while(l->next!=NULL)

Je ferais

Code :

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

1
2
 
while(liste != NULL)

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

Envoyé par mdoerper

Pour enlever la tete je penseais a

Code :

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

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?

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

**mdoerper** · 01/02/2006, 15h25

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?

**Emmanuel Delahaye** · 01/02/2006, 16h21

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...

**Trap D** · 01/02/2006, 16h21

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 :

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
 
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

**mdoerper** · 01/02/2006, 17h11

Envoyé par Trap D

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
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

**Trap D** · 01/02/2006, 17h28

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

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
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

**HanLee** · 01/02/2006, 17h58

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.

**mdoerper** · 01/02/2006, 20h04

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

**DreadNum** · 23/02/2006, 22h39

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...

**fearyourself** · 24/02/2006, 09h14

Cela devrait se trouver dans un nouveau thread...

Mais bon,

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

Code :

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

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 :

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

SListe *inverse(SListe *liste);

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

Code :

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

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 :

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

void inverse(SListe **liste);

Jc

**DreadNum** · 24/02/2006, 09h55

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

**fearyourself** · 24/02/2006, 09h59

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

inversion [Sources]

C

Discussions similaires

Partager

Partager