Discussion :

[exhortae]

Bonjour,

voilà j'ai implémenter une FIFO suivant le modèle suivant :

Code :

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

1
2
3
4
5
6
7
typedef struct noeud_file s_noeud_file;
 
struct noeud_file
{
   s_noeud_arbre *p_noeud_arbre;
   s_noeud_file *p_suivant;
};

dans cette file je sauvegarde les adresses des noeuds d'un arbre binaire de recherche (pour pouvoir faire ensuite un parcours en largeur)

Ma file ce présente comme suit:

j'ajoute à partir de la gauche, et je retire à partir de la droite. Le point d'entre de ma file est un pointeur sur le dernier element qui lui même pointe sur le premier élément.

Je voudrais faire une fonction dequeue minimaliste, et voilà comment j'ai implémenté l'histoire, lorsque je déroule le code à la main sa fonctionne, quelqu'un pourrait t'il juste confirmer que c'est bon(j'ai tjs un peu de mal quand il s'agit de pointeur sur pointeur).

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
/* --------------------------------------------------------------------------
   retirer_dans_file ()
   --------------------------------------------------------------------------
   Role : retourne l'information utile du premier noeud
   --------------------------------------------------------------------------
   Condition : la file n'est pas vide
   -------------------------------------------------------------------------- */
s_noeud_arbre *retirer_dans_file (s_noeud_file **p_pdernier)
{
   /* on utilise un pointeur temporaire pour memoriser une adresse */
   s_noeud_file **p_ptmp = &(*p_pdernier)->p_suivant;
 
   /* on sauvegarde l'information utile a revoyer */
   s_noeud_arbre *p_noeud_arbre = (*p_ptmp)->p_noeud_arbre;
 
   /* on doit libere le noeud lu */
   (*p_pdernier)->p_suivant = (*p_ptmp)->p_suivant;
   free (*p_ptmp), *p_ptmp = NULL;
 
   return p_noeud_arbre;
}

Merci

[Médinoc]

D'ici, je ne vois rien qui me choque.

Simplement, en chaînage simple j'ai tendance à "enfiler" en queue de liste, car je trouve plus facile de retirer la tête...

[exhortae]

D'ici, je ne vois rien qui me choque.

Simplement, en chaînage simple j'ai tendance à "enfiler" en queue de liste, car je trouve plus facile de retirer la tête...

Je viens de tester et à l'exécution ça foire

[fearyourself]

Je viens de tester et à l'exécution ça foire

Il faudrait le code complet pour comprendre pourquoi cela plante.

Jc

[exhortae]

J'ai mis le code du projet dans un zip (voir fichier file.c)

[diogene]

Il faut remettre le pointeur de liste à NULL si un seul élément était 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
s_noeud_arbre *retirer_dans_file (s_noeud_file **p_pdernier)
{
   /* on utilise un pointeur temporaire pour memoriser une adresse */
   s_noeud_file *p_ptmp = (*p_pdernier)->p_suivant;
 
   /* on sauvegarde l'information utile a revoyer */
   s_noeud_arbre *p_noeud_arbre = p_ptmp->p_noeud_arbre;
 
 
   (*p_pdernier)->p_suivant = p_ptmp->p_suivant;
   /* Un seul élément dans la liste ? */
   if(p_ptmp == *p_pdernier) *p_pdernier = NULL;
   /* on doit libere le noeud lu */
   free (p_ptmp);
   return p_noeud_arbre;
}

[exhortae]

En faite c'est ce que j'avais fais dans la première version

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
 
/* --------------------------------------------------------------------------
   retirer_dans_file ()
   --------------------------------------------------------------------------
   Role : retourne l'information utile du premier noeud
   --------------------------------------------------------------------------
   Condition : la file n'est pas vide
   -------------------------------------------------------------------------- */
s_noeud_arbre *retirer_dans_file (s_noeud_file **p_pdernier)
{
   /* on sauvegarde le pointeur sur la structure de donnee a renvoye */
   s_noeud_arbre *p_noeud_arbre = (*p_pdernier)->p_suivant->p_noeud_arbre;
 
   /* il faut libere le noeud */
 
   if (*p_pdernier == (*p_pdernier)->p_suivant)
   {
      /* Si il ne reste qu'un seul noeud dans la file */
      free (*p_pdernier), *p_pdernier = NULL;
   }
   else
   {
      /* on sauvegarde l'adresse du premier noeud dans un pointeur
         temporaire */
      s_noeud_file *p_tmp = (*p_pdernier)->p_suivant;
 
      (*p_pdernier)->p_suivant = p_tmp->p_suivant;
 
      free (p_tmp), p_tmp = NULL;
   }
 
   return p_noeud_arbre;
}

mais j'avais voulu trouver une version qui regroupe tous les cas en 1. Je sais pas si c'est possible.

[diogene]

Je ne pense pas qu'avec ta liste bouclée sur elle même tu puisses faire l'économie du test genre

Code :

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

if(p_ptmp == *p_pdernier) *p_pdernier = NULL;

[exhortae]

Oui effectivement y'avait un souci, dans le cas où il y a qu'un seul noeud, la dernière instruction

Code :

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

*p_ptmp = NULL;

ne mettait pas à nul le noeud en entier, mais seulement le champ p_suivant du noeud

Merci