Discussion :

[takout]

Bonjour à tous,

j'ai implémenté une fonction qui ajoute un élément dans une file, j'aimerais optimiser cette fonction mais je ne sais pas comment le faire.
Pouvez vous m'aidez s'il vous plaît ?

voici ma fonction :

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
 
typedef int bool;
#define False 0
#define True  1
 
typedef struct Fifo
{
    int *donnee;
    struct Fifo *suivant;
} Fifo;
 
void fifo_add( Fifo **p_fifo, int *val)
{
  Fifo *new_fifo, *p_courant;
 
  /* on créer un nouvel élément de la file */
  new_fifo=Malloc(1,Fifo);
  assert(new_fifo != NULL); 
 
  /* on fait pointer l'élément vers null */
  new_fifo->suivant=NULL;
 
  /* on assigne aà l'élément la donné que l'on veut ajouter*/
  new_fifo->donnee=val;
  /* si la file est vide, alors on fait pointer la file vers l'élément que l'on vient de créer */
  if(fifo_isempty(*p_fifo))
  { 
   *p_fifo=new_fifo;
  }
  else
  {
     p_courant=*p_fifo;
    while(p_courant->suivant!=NULL)
    {
      p_courant=p_courant->suivant;
    }
     p_courant->suivant=new_fifo;
  }
return;  
}

Cordialement,
Takout

[Bousk]

Bonjour,

si tu ne vois pas comment le faire, peut-être est-ce parce que tu ne peux pas.
Une liste, si tu ne possèdes que son élément de tête à manipuler, tu n'as pas grand choix : tu parcours chaque élément jusqu'à arriver en fin de file et ajouter le nouveau.
Soit ce que tu fais.

Par contre, pourquoi utiliser un int* en données ? Fourni par l'utilisateur qui plus est : risque de passer un pointeur qui causera un crash parce que libéré entre temps.
Et le return à la fin est inutile.

[Neckara]

Pour ta file, tu peux avoir deux pointeur : l'un sur le début de la file et l'autre sur la fin pour éviter de devoir parcours l'ensemble de ta file à chaque insertion.

Si tu n'as qu'un seul pointeur tu peux remplacer :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
  if(fifo_isempty(*p_fifo))
  { 
   *p_fifo=new_fifo;
  }
  else
  {
     p_courant=*p_fifo;
    while(p_courant->suivant!=NULL)
    {
      p_courant=p_courant->suivant;
    }
     p_courant->suivant=new_fifo;
  }

Par :

Code :

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

1
2
3
4
5
6
7
 
        Fifo ** p_courant= p_fifo;
        while(fifo_isempty(*p_courant))
        {
                  p_courant = &(*p_courant)->suivant;
         }
         *p_courant = new_fifo;

En gros tu fait un parcours indirect, ainsi tu parcours toute ta liste indépendamment du fait que le maillon soit premier ou non.
Par contre je me suis peut-être trompé dans l'écriture à vérifier tout de même.

[takout]

Le int * c'est parce que j'utilise des tableaux en valeur dans ma file.
Le reurn c'est par habitude on m'a toujours appris qu'une fonction doit retourner quelques choses.

Neckara je pense que ta solution peut me faire gagner du temps.

[Neckara]

Disons qu'avec 2 pointeurs, tu ne rajoute qu'une affectation lors de l'insertion et pour toutes les autres opérations, tu n'as aucune ou pratiquement aucune modification.

Avec 1 seul pointeur tu as un parcours complet de la liste (donc plusieurs affectations etc...). Si ta liste est grande on va dire 10 000 maillons, la différence va se faire sentir.


Après, tu peux utiliser une liste simplement chaînée ou doublement chaînée.
La liste doublement chaînée simplifiera l’algorithme des insertions suppressions et te permettra aussi de parcourir ta liste en sens inverse.
Mais si tu utilise une file, je suppose que tu ne fait que des insertions en queue et suppression en tête, dans ce cas là avoir des maillons doublement chaîné ne sert pas trop.


J'y pense que maintenant mais tu peux aussi avoir qu'un seul pointeur et utiliser une file circulaire.
Ton pointeur (= ta liste) pointerais sur le dernier élément et le dernier élément pointe sur le premier élément.

[Bousk]

Le reurn c'est par habitude on m'a toujours appris qu'une fonction doit retourner quelques choses.

Une fonction qui retourne void ne retourne.. rien.
return sert à sortir de la fonction.
Quand le programme rencontre l'accolade fermante, il sort de la fonction.

[Neckara]

On met le return si un jour on veut éventuellement changer le type de retour de la fonction (mettre un booléen par exemple) pour voir très rapidement où mettre la valeur de retour et pour ne pas a avoir à réécrire le 'return' ?

De toute façon mettre return; ne coûte rien et ce n'est en soit pas faux, je pense que c'est plus une raison de lisibilité du code qu'autre chose, même si je ne vois pas vraiment l'utilité d'écrire le return.

[takout]

Voilà j'ai fais ajout d'un élément avec deux pointeurs :

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
 
 
void fifo_add( Fifo **p_fifo,Fifo **fin,int *val)
{
  Fifo *new_fifo;
 
  /* on créer un nouvel élément de la file */
  new_fifo=Malloc(1,Fifo);
  assert(new_fifo != NULL); 
 
  /* on fait pointer l'élément vers null */
  new_fifo->suivant=NULL;
 
  /* on assigne aà l'élément la donné que l'on veut ajouter*/
  new_fifo->donnee=val;
  /* si la file est vide, alors on fait pointer la file vers l'élément que l'on vient de créer */
  if(fifo_isempty(*p_fifo))
  { 
   *p_fifo=new_fifo;
   *fin=new_fifo; 
  }
  else
  {
     (*fin)->suivant=new_fifo;
     *fin=new_fifo;
  }
return;  
}

[olivier_u]

De toute façon mettre return; ne coûte rien et ce n'est en soit pas faux, je pense que c'est plus une raison de lisibilité du code qu'autre chose, même si je ne vois pas vraiment l'utilité d'écrire le return.

Dans certains projets, c'est demandé explicitement en tant que règle de codage.