Discussion :

[takout]

Bonjour à tous,

Je souhaiterai supprimer les doublons d'un tableau. Pour se faire, j'ai utilisé une méthode empirique. Je parcoure le tableau trié en comptant son nombre d'éléments n sans les doublons. Je crée un autre tableau de taille n et je range les valeurs du tableau trié sans les doublons dans ce tableau.

Voici le code que j'ai utilisé :

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
 
int nombre_doublon(double *tab, int size)
{ 
  register int i;
   int k=1;
   for(i=0;i<size-1;++i)
   {  
     if(tab[i]!=tab[i+1])
     { ++k;}
   }
   return(k);
}
 
int suprime_doublon(double **res,double *tab,int size)
{  
   double *t;
   int i,j,n_nondoublon;
   j=0;
 
    n_nondoublon=nombre_doublon(tab,size);
    t=Malloc(n_nondoublon,double);
 
   t[j]=tab[0];
   for(i=0;i<size;++i)
   {
      if(t[j]!=tab[i])
      { ++j;
      	t[j]=tab[i]; 
      }
 
   }  
   *res=t; 
   return(n_nondoublon);    
 }

j'aimerai savoir si mon code peut être optimisé, s'il n'existe pas en C des méthodes plus rapides. Car dans le cas d'un tableau trié de très grande taille ma méthode peut être très lente.

[diogene]

Pourquoi ne pas le faire sur place dans le même tableau ? C'est plus simple et plus rapide. Par exemple :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
size_t suprime_doublon(double * tab , size_t dim)
{
  double *read = tab+1;
  double *write = tab;
  while( read <tab+dim)
  {
       if(*read != *write) *++write = *read;
       read++;
  }
  return write-tab+1;
}

qui renvoie le nombre d'éléments du tableau différents et élimine les doublons.

Note : Attention à la comparaison entre double qui peut poser problèmes dans certains cas : on peut avoir à préférer une comparaison plus souple du genre la différence entre les deux double est supérieure à un seuil donné.

[takout]

Ah ok d'accord !
Donc si j'appelle la fonction de cette façon sur mon tableau trié (n= suprime_doublon(tab , dim) ) il me faut parcourir tab de 0 à n-1 pour avoir tous les éléments sans doublons du tableau (c'est bien ça ?).
Mais qu'est ce qui ce passe pour tous les éléments de tab qui se situent après le n ième élément ?

Cordialement,
Takout

[diogene]

Ah ok d'accord !
Donc si j'appelle la fonction de cette façon sur mon tableau trié (n= suprime_doublon(tab , dim) ) il me faut parcourir tab de 0 à n-1 pour avoir tous les éléments sans doublons du tableau (c'est bien ça ?).

Oui

Mais qu'est ce qui ce passe pour tous les éléments de tab qui se situent après le n ième élément ?

Ils restent à leur place. Il suffit de les ignorer. Le tableau final est du coup surdimensionné, c'est tout. Ce n'est pas génant en soi.