Création d'une queue

Bonjours, je désire créer une queue dont les valeurs sont des char*, mais j'ai quelque problème.

Voici le code

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

void Enqueue(Queue **f, char *value) { Queue *element = malloc(sizeof(Queue)); if(!element) exit(1); element->val = malloc(sizeof(value)+1); strcpy(element->val,value); element->next = *f; (*f) = element; } char *Dequeue(Queue **f) { Queue *save_Queue = *f; //Sauvegarde la Queue printf("Dequeue :\n"); char* Value; //Queue *tmp; if(!*f) return NULL; //Retourne NULL si la Queue est vide while((*f)->next) //Va à l'avant dernier de la Queue { printf("Value :%s\n",(*f)->val); (*f) = (*f)->next; } Value = malloc(sizeof((*f)->next->val)); strcpy(Value,(*f)->next->val); printf(Value); free((*f)->next); (*f)->next = NULL; //clo la Queue (*f) = save_Queue; return Value; } void Clear(Queue **f) { Queue *tmp; while(*f) { tmp = (*f)->next; free(*f); *f = tmp; } } void View(Queue *f) { while(f) { printf("Voici : %s\n",f->val); f = f->next; } }

---

Voici les problèmes :

Pour l'insertion, les éléments se mettent bien dans la liste, mais quand je les imprime (vie view), le premier et bon mais les autres, chaque fois sont rogner chaque fois le dernier éléments, donc le problème pour moi vient de l'insertion,mais je ne trouve pas.

Autre souci, quand je veux insérer un élément au début, j'ai un du mal à trouver comment arrêter la boucle.

Olivier

Déjà en général, on appelle ça une file, enfin pas grave.
Sinon pour une file on peut utiliser deux pointeurs pour travailler plus rapidement. Le premier pointeur pointe sur le premier élément ajouté et le deuxième pointe sur le dernier. Quand tu dois faire sortir un élément de la liste tu prends le premier pointeur, quand tu dois en faire rentrer un tu utilises le dernier pointeur...

Tu peux déjà essayer d'orienter tes cherches sur ce système.

Citation:

---

Envoyé par OlivierDotre

Bonjours, je désire créer une queue dont les valeurs sont des char*, mais j'ai quelque problème.
<...>
Voici les problèmes :

Pour l'insertion, les éléments se mettent bien dans la liste, mais quand je les imprime (vie view), le premier et bon mais les autres, chaque fois sont rogner chaque fois le dernier éléments, donc le problème pour moi vient de l'insertion,mais je ne trouve pas.

Autre souci, quand je veux insérer un élément au début, j'ai un du mal à trouver comment arrêter la boucle.

---

Code:

---

void Enqueue(Queue **f, char *value)

---

On va supposer qu'il s'agit de chaines de caractères. Il est donc nécessaire d'accepter les adresses des chaines invariantes :

Code:

---

void Enqueue(Queue **f, char const *value)

---

Pour pouvoir tester le code, j'ai ajouté ceci au début :

Code:

---

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

#include <stdio.h> #include <stdlib.h> #include <string.h>   typedef struct queue { /* donnees */ char *val;   /* chainage */ struct queue *next; } Queue;

---

et cela à la fin (provisoire):

Code:

---

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

int main (void) { Queue *f = NULL;   View (f);   Enqueue (&f, "Hello"); View (f);   Enqueue (&f, "Wild"); View (f);   Enqueue (&f, "World"); View (f);   Clear (&f); View (f);   return 0; }

---

et j'ai modifié View en

Code:

---

1 2 3 4 5 6 7 8 9 10

void View (Queue * f) { while (f) { printf ("'%s' -> ", f->val); f = f->next; } printf ("NIL\n"); }

---

Pour le moment, ça donne :

Code:

---

1 2 3 4 5 6 7 8

NIL 'Hello' -> NIL 'Wild' -> 'Hello' -> NIL 'World' -> 'Wild' -> 'Hello' -> NIL NIL   Press ENTER to continue.

---

Ce qui semble correct, mais je n'ai pas encore analysé tout le code...

Code:

---

if (!element)

---

est illisible. Préférer :

Code:

---

if (element == NULL)

---

Code:

---

exit (1);

---

est trop brutal et pas portable. (EXIT_FAILURE). Je recommande de tester la valeur afin de ne pas continier en cas d'echec. Idem avec tous les malloc()... Laisser la décision à la couche applicative.

Code:

---

element->val = malloc (sizeof (value) + 1);

---

Est horriblement faux. sizeof concerne un objet (ici, un pointeur). Rien à voir avec la taille de l'objet pointé (qui ne peut être déterminée ici). Ce qui nous intéresse, c'est la longueur de la chaine, soit strlen(). Pour simplifier, je recommande l'usage de strdup(), qui, bien que non standard C, est POSIX.1, donc très portable (et facile à reproduire).
Ceci devrait déjà résoudre les problèmes basiques :

Code:

---

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

void Enqueue (Queue ** f, char const *value) { Queue *element = malloc (sizeof (Queue)); if (element != NULL) { element->val = strdup (value); if (element->val != NULL) { element->next = *f; (*f) = element; } else { free (element); } } }

---

Dans Clear(), il manque la libération de la donnée :

Code:

---

free ((*f)->val);

---

Je n'ai pas vérifié le reste. DeQueue(), notamment, me parait étrange. Pourquoi des allocations ?

Super, merci

Je test ça dés que j'ai le temps et je vous dis quoi.

Un grand merci

Citation:

---

Envoyé par Emmanuel Delahaye

[
On va supposer qu'il s'agit de chaines de caractères. Il est donc nécessaire d'accepter les adresses des chaines invariantes :

Code:

---

void Enqueue(Queue **f, char const *value)

---

---

Petite question, const ne va rien changer au appel que je ferai de la méthode?


Sinon la fonction enqueue fonctionne à merveille, merci. Je teste la fonction dequeue

[edit]Je l'ai un peu changée mais j'ai une erreur de segmentation quand il ne reste que deux éléments dans la liste.

Code:

---

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

char *Dequeue(Queue **f) { Queue *save_Queue = *f; //Sauvegarde la Queue printf("Dequeue :\n"); char* Value; //Queue *tmp; if(!*f) return NULL; //Retourne NULL si la Queue est vide while((*f)->next) //Va à l'avant dernier de la Queue { printf("Value :%s\n",(*f)->val); View(*f); (*f) = (*f)->next; } Value = strdup ((*f)->next->val); printf(Value); free((*f)->next); (*f)->next = NULL; //clo la Queue (*f) = save_Queue; return Value; }

---

L'erreur se produit dans la boucle, c'est ma condition qui n'est pas bonne, mais je ne sais pas comment dire qu'il ne doit rester plus que deux éléments.

Merci

Salut

J'ai refait quelques avancées pour cette queue.

Code:

---

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

char *Dequeue(Queue **f) { Queue *save_Queue = *f; //Sauvegarde la Queue printf("Dequeue :\n"); char* Value; if(!*f) return NULL; //Retourne NULL si la Queue est vide while((*f)->next != NULL) //Va à l'avant dernier de la Queue { (*f) = (*f)->next; } Value = strdup ((*f)->val); (*f) = NULL; (*f) = save_Queue; return Value; }

---

Elle revoie la bonne valeur et bien le début de la file mais le problème c'est que ça ne supprime pas le noeud dont je viens de prendre la valeur.

Je pensais que (*f) = NULL; le fesais mais quand j'ai exécuté ce code ca fesait ca fesait comme si j'avais de nouveau ma liste de départ alors que je n'ai fait qu'une sauvegarde d'un pointeur au début.

Je ne sais pas comment faire.

Merci de votre aide

Olivier

Citation:

---

Envoyé par OlivierDotre

Code:

---

1 2	char *Dequeue(Queue **f) <...>

---

Je ne sais pas comment faire.

---

En fait, il y a 3 cas à traiter :

1. la file est vide
2. suppression du premier élément
3. suppression d'un autre élément.

Citation:

---

Envoyé par Emmanuel Delahaye

1. suppression d'un autre élément.

---

Dans le cas d'une file ce cas ne peut pas arriver, on supprime toujours en tete de file.

bah non justement, j'insère devant et je tire derrière, c'est un FIFO. Mais c'est vrai que je pourrais faire l'inverse, inséré au fond et retirer le premier. enfin ça change rien, c'est juste voir la file dans l'autre sens.

Je vais tester et faire pour ces cas. je vous dis quoi si j'ai un problème

merci pour vos réponse

Citation:

---

Envoyé par OlivierDotre

bah non justement, j'insère devant et je tire derrière, c'est un FIFO. Mais c'est vrai que je pourrais faire l'inverse, inséré au fond et retirer le premier. enfin ça change rien, c'est juste voir la file dans l'autre sens.

---

Oui, c'ezst une autre facon de voir les choses.
Le principe d'une FIFO (c'est vrai aussi pour une FILO d'ailleurs), c'est que l'on enleve toujours le meme element, ainsi il n'a a que deux cas a gerer :
* l'element est present ==> supression entete (ou en fin) de la liste.
* la liste est vide.