Inverser une file

Version imprimable

20/05/2006, 01h25
ecnirp

Inverser une file

Bonjour
je veux ecrire une fonction

Code:

void permut(void)

qui inverser une file par exemple si ma file est A Z E R T Y ou tete =A et Queue = Y apres appel de la fonction permut() la file devient Y T R E Z A
merci de tous ce que vous pouvez me dire algo programme lien idée
20/05/2006, 01h45
busy999
Deja le prototype de la fonction m'etonne... Elle ne prend pas de file en parametre : je suppose que la file est declaree en global (les globals c'est mal :))

Ensuite vous pouvez faire une algo en recursif qui fasse genre :
Code:

1 2 3 4 5 6 7 8 9 10 parcour(node) { if (node->next) { parcour(node->next)->next = node; return node->next; } else return node; }
Il y a juste le probleme qu'il faut connaitre a l'avance la queue de la liste avant inversion, sinon vous perdrez votre liste dans la memoire.
20/05/2006, 01h58
ecnirp

oui la file la tete et la queue sont defini d une maniére global
pourqoui c mauvais excuse mon ignorance mais je suis novice en c
Merci
20/05/2006, 08h06
PRomu@ld

L'utilisation de variables globale est à proscrire pour plusieurs raisons :

- Accessibilité de tes variables partout dans le programme, donc modification possible par toute partie de ton programme (problème de sécurité)
- Les variables globales sont crées au début de ton programme et détruites à la fin, ce qui peut poser des problèmes d'occupation mémoire. Il est plus fréquent d'avoir une variable dont on a besoin qu'une partie du temps de notre programme.
- Mauvaise conception du programme le fait que tout soit global implique une mauvaise séparation des données (aucune séparation d'ailleurs)
- Code non réutilisable car dépendant de tes variables globales.

Le seul cas ou j'ai rencontré des cas ou on ne pouvait quasiment pas se passer de variables globales est le cas de la programmation système.
Si on te dis qu'il es plus performant d'utiliser des variables globales, n'écoute pas ce qu'on te dis, personnellement j'attend encore preuve à l'appui cette affirmation.
20/05/2006, 12h30
ecnirp

Oui vous avez raison en ce qui concerne les variables globals Merci c plus claire maintenenant ,
et pour la file???

Citation:

Envoyé par ecnirp

Oui vous avez raison en ce qui concerne les variables globals Merci c plus claire maintenenant ,
et pour la file???

C'est quoi une file pour toi ? Si c'est une liste chainée, ceci peut aider :

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
 
#include <stdio.h>
 
struct node
{
   struct node *p_next;
   int data;
};
 
static void display(struct node *p)
{
   if (p != NULL)
   {
      printf ("'%c' ", p->data);
      display(p->p_next);
   }
   else
   {
      printf ("NIL\n");
   }
}
 
static struct node *reverse(struct node *p)
{
   struct node *p_rev = NULL;
 
   while (p != NULL)
   {
      struct node *p_next = p->p_next;
      if (p_rev == NULL)
      {
         p->p_next = NULL;
      }
      else
      {
         p->p_next = p_rev;
      }
      p_rev = p;
      p = p_next;
   }
   return p_rev;
}
 
int main ()
{
   struct node a[] =
      {
         {
            a + 1, 'A'
         },
         {
            a + 2, 'Z'
         },
         {
            a + 3, 'E'
         },
         {
            a + 4, 'R'
         },
         {
            a + 5, 'T'
         },
         {
            NULL, 'Y'
         },
      };
   struct node *p = a;
 
   display(p);
   p = reverse(p);
   display(p);
   return 0;
}

Code:

1
2
3
4
 
'A' 'Z' 'E' 'R' 'T' 'Y' NIL
'Y' 'T' 'R' 'E' 'Z' 'A' NIL
Press ENTER to continue.

20/05/2006, 14h21
ecnirp

Bonjour
Merci bcp de ton code j ai piqué la fontion dispaly la mienne n 'etai pas recurssive alors pour inversion la file est une liste chainé ou on specfier la queue et la tete ( queue->next=NULL)
j ai pas bien compris ton algo pour l adopter pour mon cas
Merc une autre fois
20/05/2006, 14h27
Emmanuel Delahaye

Citation:

Envoyé par ecnirp

Bonjour
Merci bcp de ton code j ai piqué la fontion dispaly la mienne n 'etai pas recurssive alors pour inversion la file est une liste chainé ou on specfier la queue et la tete ( queue->next=NULL)
j ai pas bien compris ton algo pour l adopter pour mon cas
Merc une autre fois

[Tu pourrais le refaire en français ? J'ai du mal à comprendre ce que tu écris...]

Le principe est de déplacer les éléments dans une liste annexe en modifiant le chainage. On lit l'original en séquence :
a, b, c, d
et tout ce qu'on lit, on le place en tête de la nouvelle file :
a, NIL
b, a, NIL
c, b, a, NIL
d, c, b, a, NIL
Il n'a plus qu'a retourner l'adresse de la tête de la nouvelle file.
20/05/2006, 16h30
ecnirp

Citation:

Envoyé par Emmanuel Delahaye

Le principe est de déplacer les éléments dans une liste annexe en modifiant le chainage. On lit l'original en séquence :
a, b, c, d
et tout ce qu'on lit, on le place en tête de la nouvelle file :
a, NIL
b, a, NIL
c, b, a, NIL
d, c, b, a, NIL
Il n'a plus qu'a retourner l'adresse de la tête de la nouvelle file.

Oui, oui mais si on veut le faire sans utiliser une deuxieme file??
20/05/2006, 17h06
PRomu@ld

Citation:

Oui, oui mais si on veut le faire sans utiliser une deuxieme file??

Algorithmiquement parlant et sans toucher à la structure interne de la file, j'avoue (sans y avoir trop réflechir tout de même) ne pas voir de solution pour faire celà sur place.

Une autre solution consiste à utiliser une pile :mrgreen:
20/05/2006, 17h08
busy999

Essaye de regarder mon premier algo, il me semble qu'il puisse fonctionner correctement sans avoir besoin de deux files.

Bon j'ai fini par decider de le coucher sur emacs pour en etre sur :p Ca fonctionne sur ce test, il faut juste pousser les tests mais je trouve ca plutot pas mal. (J'ai utilise l'hypothese que l'on connais la tete de liste. Pour que l'algo soit universel il suffit juste de rajouter une fonction qui cherche la tete de liste)
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 34 35 36 37 38 39 40 #include <stdlib.h> #include <stdio.h> struct s_node { int val; struct s_node *next; }; void display(struct s_node *node) { for (; node; node = node->next) printf("[%d]", node->val); printf("\n"); } struct s_node *revert(struct s_node *node) { if (node && node->next) { revert(node->next)->next = node; node->next = NULL; } return node; } int main(void) { struct s_node test[] = { {1, test + 1}, {2, test + 2}, {3, NULL} }; display(test); revert(test); display(&test[2]); return 0; }

20/05/2006, 17h30
Emmanuel Delahaye
Citation:

Envoyé par ecnirp

Oui, oui mais si on veut le faire sans utiliser une deuxieme file??

Sur le plan de l'occupation mémoire, il n'y a pas de 'deuxième file'. C'est juste qu'au fur et à mesure qu'on démonte la première, on construit la seconde.

Les données (node) ne sont pas recopiée, on a juste modifié les liens, c'est tout. Ni allocation , ni libération... (en plus, j'aurais bien été embété avec mon exemple qui est statique...)

Ceci dit, je te trouve un peu gonflé :
- tu demandes tout pour rien
- tu n'as pas publié une ligne de code
- tu ne reflechis pas sur les solutions proposées
- les solutions proposées sont efficaces et solides et tu fais la fine bouche
Tu es trop gaté. Tu devrais te confronter un peu à la vrai vie...
20/05/2006, 17h34
Emmanuel Delahaye
Citation:
Envoyé par busy999

Code:

1 2 3 4 5 6 7 8 9 struct s_node *revert(struct s_node *node) { if (node && node->next) { revert(node->next)->next = node; node->next = NULL; } return node; }
Les solutions récursives utilisent de la mémoire incontrôlable... C'est joli, mais c'est dangereux... J'aime pas...

D'ailleurs pour display() tu es revenu à une solution itérative, et tu as eu raison.
20/05/2006, 17h36
Emmanuel Delahaye

Citation:

Envoyé par PRomu@ld

Une autre solution consiste à utiliser une pile :mrgreen:

C'est mieux que la récursion qui fait ça toute seule, mais de manière incontrôlable.

Je m'en suis apercut apres (j'ai code a taton). Il ne reste maintenant qu'un return et un seul test.
Code:

1 2 3 4 5 6 7 8 9 struct s_node *revert(struct s_node *node) { if (node && node->next) { revert(node->next)->next = node; node->next = NULL; } return node; }
Enjoy

20/05/2006, 17h48
ecnirp

Bonjouir
je comprend pas cette ligne dans ton code

Code:

revert(node->next)->next = node;

ton code c 'est pour inverser une liste chainée normal et non pas une file car faut changer la tete et la queue pour dans une file (FIFO)
Merci pour ton aide
20/05/2006, 17h53
HanLee

Citation:

Envoyé par Emmanuel Delahaye

C'est mieux que la récursion qui fait ça toute seule, mais de manière incontrôlable.

Pourquoi tu dis que c'est incontrôlable ?
20/05/2006, 17h54
busy999

Une file est une liste chainee specialisee. Donc inverser une liste chainee reviens a inverser la file. Dans mon algo, on imprime les deux listes (avant et apres inversion) ce qui signifie que l'on a perdu ni la tete ni la queue ^^

bon voila le code que je suis entrain de modifier ( d'apres les explications du prof du TD

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
 
typedef struct FIFO {
    int valeur;
  struct FIFO *next;
}fifo;
typedef fifo* pfifo;
pfifo tete,queue;
 
void inverser_f()
   { pfifo p=tete, q=queue,precedent=tete;
  while(p->next !=queue)
  {
   while(precedent->next !=q)
   {
   precedent=precedent->next;
   }
  queue->next=precedent;
  queue=queue->next;
   }
   tete=q;
queue->next=NULL;

)

Mais ca ne marche pas:cry:

20/05/2006, 17h56
busy999

Citation:

Envoyé par HanLee

Pourquoi tu dis que c'est incontrôlable ?

Le probleme du recursif c'est qu'a chaque appel de la fonction, le code est pose sur la pile. Ce qui fait que pour une recursion trop profonde, on peux exploser la pile. Seulement etant donner les ordinateurs actuels, je pense que l'on pourrais s'inquieter de mon algo pour une file depassant les 11000000[...]0000 elements ^^
20/05/2006, 17h58
HanLee

Citation:

Envoyé par busy999

Le probleme du recursif c'est qu'a chaque appel de la fonction, le code est pose sur la pile. Ce qui fait que pour une recursion trop profonde, on peux exploser la pile. Seulement etant donner les ordinateurs actuels, je pense que l'on pourrais s'inquieter de mon algo pour une file depassant les 11000000[...]0000 elements ^^

Ca je sais, mais si tu le fais en récursif terminal, le compilateur s'il fait un minimum son boulot, transforme le code de manière à ce que la pile ne déborde jamais, et là je ne vois pas où est ce que c'est incontrôlable en fait.
20/05/2006, 18h36
Emmanuel Delahaye

Citation:

Envoyé par busy999

Le probleme du recursif c'est qu'a chaque appel de la fonction, le code est pose sur la pile.

Gné ? Pas le code. L'adresse de retour, les données locales et les paramètres...

Citation:

Ce qui fait que pour une recursion trop profonde, on peux exploser la pile. Seulement etant donner les ordinateurs actuels, je pense que l'on pourrais s'inquieter de mon algo pour une file depassant les 11000000[...]0000 elements ^^

Faut voir... Quelle est la pile de ton processus ? 2 Mo ?

Une adresse de retour : 4 octets
Un paramètre : 4 octets

: OK pour 268435456 éléments. C'est pas l'infini...

En embarqué, il est courant d'avoir des piles de 64k (voire moins...)... On tombe à 8192. C'est pas le pérou...
20/05/2006, 18h39
Emmanuel Delahaye

Citation:

Envoyé par HanLee

Ca je sais, mais si tu le fais en récursif terminal, le compilateur s'il fait un minimum son boulot, transforme le code de manière à ce que la pile ne déborde jamais, et là je ne vois pas où est ce que c'est incontrôlable en fait.

Tu comptes sur le compilateur pour 'itériser' la fonction. Et si il ne le fait pas ? Tu vas vérifier le code généré à chaque compilation? Nos projets font de 100 klignes à 1Mlignes. Je prefère le faire moi même...
20/05/2006, 19h15
HanLee

Citation:

Envoyé par Emmanuel Delahaye

Tu comptes sur le compilateur pour 'itériser' la fonction. Et si il ne le fait pas ? Tu vas vérifier le code généré à chaque compilation? Nos projets font de 100 klignes à 1Mlignes. Je prefère le faire moi même...

Bah ça dépend du contexte.

Tu fais des projets embarqués je crois non ? Là je ne compterais pas sur leurs compilateurs c'est sûr parce que j'ai des a priori.

Mais sur les compilateurs pour PC, ils le font tous depuis longtemps.
Pour le vérifier, il faut et il suffit que le seul appel récursif de la fonction lors de son déroulement soit la valeur de retour.

Sinon, encore une autre question :

Quand on a des algorithmes récursifs impossibles à rendre terminaux, qui ne peuvent être simulés qu'avec une pile, à part les appels de fonctions en plus (qui ne peuvent pas être supprimés dans ce cas), où est le danger ?

Parce que si on se fabrique notre propre pile, c'est comme si on utilisait la pile d'appels.

Peut-être que si l'on fabrique notre propre pile on pourrait avoir plus de mémoire parce qu'on utiliserait le tas, plutôt que d'encombrer la pile d'appels ?
20/05/2006, 19h35
Emmanuel Delahaye

Citation:

Envoyé par HanLee

Quand on a des algorithmes récursifs impossibles à rendre terminaux, qui ne peuvent être simulés qu'avec une pile, à part les appels de fonctions en plus (qui ne peuvent pas être supprimés dans ce cas), où est le danger ?

Parce que si on se fabrique notre propre pile, c'est comme si on utilisait la pile d'appels.

Ben non. on utilise la tas et on laisse la pile tranquille... et surtout, en cas d'erreur, on est prévenu, et on est pas obligé que ça se termine en crash majeur...

Citation:

Peut-être que si l'on fabrique notre propre pile on pourrait avoir plus de mémoire parce qu'on utiliserait le tas, plutôt que d'encombrer la pile d'appels ?

Exactement.
20/05/2006, 19h41
HanLee

OK ! J'en étais sûr.
21/05/2006, 00h54
ecnirp

je vois que vous avez changer le sujet et vous etes entrain de regler le probleme de la gestion de la pile c 'est tres important mais moi je ne sais meme pas comment ca marche ( pour moi une pile est une liste chainée qui suit le principe LIFO)
alors SVp quelqu'un peut m aider a resoudre mon probleme
merci

Fuseau horaire GMT +2. Il est actuellement 03h51.