Création d'une queue

**OlivierDotre** · 11/08/2007, 02h56

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

Voici le code

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

**PsychoH13** · 11/08/2007, 03h22

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.

**Emmanuel Delahaye** · 11/08/2007, 09h31

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 :

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

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 :

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

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

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

Code :

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

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 :

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

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

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 :

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

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 :

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

   if (!element)

est illisible. Préférer :

Code :

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

   if (element == NULL)

Code :

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

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 :

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

   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 :

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

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

      free ((*f)->val);

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

**OlivierDotre** · 11/08/2007, 11h56

Super, merci

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

Un grand merci

**OlivierDotre** · 11/08/2007, 23h58

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 :

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

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 :

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

**OlivierDotre** · 15/08/2007, 02h26

Salut

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

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