Discussion :

[ecnirp]

Bonjour
je veux ecrire une fonction

Code :

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

  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

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

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

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.

[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

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

[ecnirp]

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

[Emmanuel Delahaye]

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 :

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

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

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

[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

[Emmanuel Delahaye]

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.

[ecnirp]

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

[PRomu@ld]

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

[busy999]

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

[busy999]

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 :

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

[Emmanuel Delahaye]

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

[Emmanuel Delahaye]

Code :

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

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.

[Emmanuel Delahaye]

Une autre solution consiste à utiliser une pile

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

[busy999]

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

Code :

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

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

[ecnirp]

Bonjouir
je comprend pas cette ligne dans ton code

Code :

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

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

[HanLee]

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 ?

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

[ecnirp]

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

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