Discussion :

[allezlolo]

Bonjour à tous,

Comme le titre l'indique je dois trier un tableau de pointeurs vers des éléments de type quelconques, la fonction de tri reçoit en argument un pointeur vers une fonction qui compare deux éléments et renvoi -1,0 ou 1 suivant le résultat de la comparaison.

Hélas, je ne trouve même pas l'entête de ma fonction.
Exemple, si je trie des doubles, il me suffit de mettre :

void tri (double tab[], etc...)

Mais sans connaître le type des éléments du tableau, comment puis je faire ???

Merci d'avance pour votre aide

[barbsbou]

Salut moi je verrais un truc du genre

Code :

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

1
2
 
void sort(void **tab, char (*cmp_element)(const void *elt_1, const void *elt_2));

void **tab car c'est un tableau de pointeur,
(*cmp_element) c'est le pointeur sur fonction qui a pour prototype (const void *elt_1, const void *elt_2)

A la bonne synthaxe pres ca doit etre qq chose comme ca...lol

Je sais pas si ca peut eclairer ton esprit....????


Je pense que l'idee est de mettre dans le prototype des void * pour ensuite les caster..... non??? dites le moi si je me trompe que je ne raconte pas trops de betise...

[allezlolo]

Oula, dur de comprendre ce que tu m'as mis lol mais je vais essayer...

pourquoi met tu char devant le (*cmp_element) ??
Je ne comprends pas non plus le const devant elt1 et elt2

[barbsbou]

J'ai mis le char car la fonction de comparaison te retourne -1, 0, 1 donc ca tient dans un octet donc je propose d'utiliser un char qui est suffisant!!

Les const dans le prototype ca permet juste de t'assurer que tu ne va pas modifier les arguments que tu passes... c'est pour constant!!


Est-ce un chouilla plus clair????
Est-ce que tu sais manipuler les pointeurs de fonctions..???

[barbsbou]

pour essayer d'illustrer voici un petit exemple pour les unsigned char

Code :

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

1
2
3
4
5
6
7
8
9
10
 
char cmp_unsigned_char(const void *elt_1, const void *elt_2)
{
    unsigned char *a, *b;
 
    a = (unsigned char *) elt_1;   /*cast*/
    b = (unsigned char *) elt_2;
 
..../*apres c'est facile de comparer 2 unsigned char*/
}

pour utiliser cette fonction tu feras qq chose comme :

Code :

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

1
2
3
4
5
 
void **tab;
 
/* allocation et initialisation de tab */
sort(tab, &cmp_unsigned_char)

et maintenant est ce un peu plus clair???

Par contre je n'ai pas teste avec un compilo donc je le fais de memoire desole d'avance si il y a qq coquille!!

[allezlolo]

D'accord je vois mieux,

Je cherche sur internet des tuto pour les pointeurs de fonctions mais hélas je ne trouve pas grand chose qui m'éclaircit.

Je fais un test simple :

Code :

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

1
2
3
int tri_quest2 (void **tab,int (*cmp_element)(void const *e1, void const *e2)) {
  return cmp_element(tab[0],tab[1]);;
}

SI je veux tester ma fonction avec strcmp, et deux chaines de caractères comment dois je appeler ma fonction ?
J'ai essayé ça mais sans réussite...

Code :

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

1
2
3
4
5
6
7
8
 
int main() {
  char* tab;
  tab = (int) malloc (sizeof(int)*2);
  tab[0] = "test";
  tab[1] = "test1";
  printf("%s %s %d \n", tab[0], tab[1],  tri_quest2 (tab,strcmp());
}

[allezlolo]

Ha je n'avais pas vu ta dernière réponse, je lis....

[allezlolo]

REbonjour,

avec ta manière comme la mienne, j'ai ce type d'erreur à la compilation :

Code :

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

 attention : passing argument 2 of «sort" from incompatible pointer type

[diogene]

Code :

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

1
2
3
4
  char* tab;
  tab = (int) malloc (sizeof(int)*2);
  tab[0] = "test";
  tab[1] = "test1";

Attention, ces 4 lignes sont incohérentes :
- Le malloc indique que tu veux allouer deux int. La valeur de retour devrait se stocker dans un int * or tab est un char *. Le cast du retour du malloc en int est une absurdité.
- Dans le tableau obtenu, tu ne mets pas des int mais des pointeurs sur char !
Si c'est le but recherché, alors tab devrait être du type char **, et le malloc devrait allouer deux char *.

Code :

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

1
2
3
4
  char** tab;
  tab =  malloc (sizeof(char*)*2);
  tab[0] = "test";
  tab[1] = "test1";

[allezlolo]

en effet, je me suis embrouillé en tapant, les ignes me permettant de tester la fonction.

J'ai toujours la mêm erreur à la compilation (passing argument 1 of «tri_quest2" from incompatible pointer type
), voici mon code :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
int tri_quest2 (void **tab,int (*cmp_element)(void const *e1, void const *e2)) {
  return cmp_element(tab[0],tab[1]);;
}
 
int main() {
  char** tab;
  tab =  malloc (sizeof(char*)*2);
  tab[0] = "test";
  tab[1] = "test1";
 
  tri_quest2(tab, &strcmp); 
}

[Emmanuel Delahaye]

Comme le titre l'indique je dois trier un tableau de pointeurs vers des éléments de type quelconques, la fonction de tri reçoit en argument un pointeur vers une fonction qui compare deux éléments et renvoi -1,0 ou 1 suivant le résultat de la comparaison.

Quelconque mais de même type, OK ? Sinon, il est absurde de vouloir trier autre chose qu'un tableau.

Mais sans connaître le type des éléments du tableau, comment puis je faire ???

Tu ne peux pas.

Explique ton problème réel, tu as sans doute une erreur de conception.

EDIT : Si j'ai bien compris, tu veux créer une fonction de tri générique ? Ca existe déjà en C standard : qsort().

Tu veux créer ton propre qsort(), c'est ça ?

C'est une technique assez avancée...

Il faut commencer par définir correctement l'interface. Les paramètres sont :

Code :

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

1
2
3
4
5
 
void * tab : adresse du premier élément du tableau à trier
size_t nb_elem : nombre d'éléments du tableau
size_t sz_elem : taille en bytes d'un élément du tableau
int (*fp_compare)(void const *a, void const *b) : adresse de la fonction de comparaison

Celle-ci est forcément externe, car il faut pourvoir comparer les éléments pour pouvoir trier.

Elle a donc la forme :

Code :

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

int compare (void const *a, void const *b)

Les 2 paramètres sont a et b, les adresses respectives des 2 élément en train d'être comparés.

Pour faire la comparaison, on a besoin de connaitre le type (qui doit être le même pour les deux):

Code :

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

1
2
T const *pa = a;
T const *pb = b;

ensuite, on compare de qui doit l'être... et on retour,e <0, 0 ou >0 selon le résutat. Par exemple :

Code :

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

   return *pa - *pb;

ou

Code :

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

   return strcmp (pa, pb);

etc.

Tu as un algo de tri qui fonctionne ?

[allezlolo]

Quelconque mais de même type, OK ? Sinon, il est absurde de vouloir trier autre chose qu'un tableau.

Tu ne peux pas.

Explique ton problème réel, tu as sans doute une erreur de conception.

Oui les éléments du tableau sont de même type et je passe en argument un pointeur vers une fonction qui compare deux éléments.

[allezlolo]

Merci pour ces précisions

Oui j'ai un algorithme pour le trie qui fonctionne.

Mon problème est surtout d'arriver à utiliser correctement ma fonction de comparaison dans ma fonction principale.

Comme je l'ai expliquer dans le message plus haut, je cherche tout simplement pour commencer à réussir à compiler et renvoyer quelque chose de correct avec ce code :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
int tri_quest2 (void **tab,int (*cmp_element)(void const *e1, void const *e2)) {
  return cmp_element(tab[0],tab[1]);;
}
 
int main() {
  char** tab;
  tab =  malloc (sizeof(char*)*2);
  tab[0] = "test";
  tab[1] = "test1";
 
  tri_quest2(tab, &strcmp); 
}

Je ne vois pas ce qui bloque sur ce petit bout de code...?

EDIT : oui je cherche à implenté une sorte de qshort sans utiliser forcément le tri rapide.

[barbsbou]

En regardant de plus pres ton erreur de compilation je me suis apercu que le prototype de strcmp est :

Code :

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

1
2
 
int strcmp(const char *s1, const char *s2);

or dans ta fonction de tri veut une fonction qui a comme prototype :

Code :

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

1
2
 
int cmp_element(void const *e1, void const *e2)

le probleme vient de la je pense

fait toi une fonction de comparaison ca se fait en 10 lignes et en 2 min si t'as pas trop l'habitude... test la une fois que t'es sure quelle fonctionne attaque toi a la faire passer un argument dune fonction.....

etape par etape... ;-)

[barbsbou]

okay on a poster en meme temps donc desole si jai dit des choses inutile...lol

mais strcmp veut des char et toi tu veu une fonction de comparaison qui prend des void.... la c'est un probleme...

donc utilise pas strcmp() ou pas directement

mais fait le d'abord avec des char ou un type tres simple a comparer, puis fait ta fonction de comparaison en qq ligne (qui prends des void) et je ne vois pas pkoi ca ne marchera pas.....

par acqui de conscience j'ai regarde des vieux sources et cété comme ca ke j'ai utiliser les pointeurs de fonction....

[allezlolo]

Merci à tous pour vos réponses,
Je me replonge bien dedans, je fais les quelques fonctions pour tester et je vous tiens au courant si tout marche.

En tout cas, merci pour tout

[allezlolo]

Rebonsoir,

Voilà je ne dois plus être très loin du but, le tout compile mais mes éléments ne me semblent pas triés :

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
 
tri_quest2 (void **tab,int (*cmp_element)(void const *e1, void const *e2),int nombreEl) {
  int j=0;
  int i=0;
  void* aux;
 
  for (i; i < nombreEl; i++) {
    for (j = i + 1; j < (nombreEl); j++){
      if (cmp_element(tab[i],tab[j])) {
        aux = tab[i];
        tab[i] = tab[j];
        tab[j] = aux;
      }
    }         
  }
}
 
static int compare (void const *a, void const *b)
{
   return strcmp (a,b);
}
 
int main() {
  void** tab;
  tab =  malloc (sizeof(char*)*2);
  tab[0] = "c";
  tab[1] = "d";
  tab[2] = "a";
  tab[3] = "b"; 
  tri_quest2(tab, &compare,4); 
  printf("%s %s %s %s", tab[0],tab[1],tab[2],tab[3]);
}

Cela me donne comme ordre b a d c au lieu de abcd...

[allezlolo]

C'est bon ça marche

Il me fallait en fait mettre

if (cmp_element(tab[i],tab[j])==1)

ça me parait un peu bizarre car je croyais que 1 était équivalent à true...

Enfin bon ça marche c'est le principal

[Vincent Rogier]

Pourquoi ne pas utiliser qsort ??

[Emmanuel Delahaye]

Voilà je ne dois plus être très loin du but, le tout compile mais mes éléments ne me semblent pas triés

Code :

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

1
2
3
4
5
6
7
8
 
int main() {
  void** tab;
  tab =  malloc (sizeof(char*)*2);
  tab[0] = "c";
  tab[1] = "d";
  tab[2] = "a";
  tab[3] = "b";

Déjà, tu alloues 2 pointeurs et tu en utilises 4. Le comportement est indéterminé...

Ensuite,

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
 
Project   : Forums
Compiler  : GNU GCC Compiler (called directly)
Directory : D:\dev\forums\
--------------------------------------------------------------------------------
Switching to target: default
Compiling: main.c
main.c:1: warning: return type defaults to `int'
main.c: In function `tri_quest2':
main.c:6: warning: statement with no effect
main.c:15: warning: control reaches end of non-void function
main.c: In function `compare':
main.c:19: warning: implicit declaration of function `strcmp'
main.c: At top level:
main.c:22: warning: function declaration isn't a prototype
main.c: In function `main':
main.c:24: warning: implicit declaration of function `malloc'
main.c:25: warning: assignment discards qualifiers from pointer target type
main.c:26: warning: assignment discards qualifiers from pointer target type
main.c:27: warning: assignment discards qualifiers from pointer target type
main.c:28: warning: assignment discards qualifiers from pointer target type
main.c:30: warning: implicit declaration of function `printf'
main.c:30: warning: char format, void arg (arg 2)
main.c:30: warning: char format, void arg (arg 3)
main.c:30: warning: char format, void arg (arg 4)
main.c:30: warning: char format, void arg (arg 5)
main.c:31: warning: control reaches end of non-void function
Linking console executable: console.exe
Process terminated with status 0 (0 minutes, 5 seconds)
0 errors, 16 warnings

y'a encore du boulot...

Ceci fonctionne :

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
49
50
51
52
53
54
55
56
 
#include <stdio.h>
#include <string.h>
 
void aff (void const **tab, int n)
{
   int i;
   for (i = 0; i < n; i++)
   {
      printf ("%s ", (char *) tab[i]);
   }
   printf ("\n");
}
 
void tri_quest2 (void const **tab, int n,
                 int (*cmp_element) (void const *e1, void const *e2))
{
   int sorted;
   do
   {
      int j;
      sorted = 1;
 
      for (j = 0; j < n - 1; j++)
      {
         if (cmp_element (tab[j], tab[j + 1]) > 0)
         {
            /* swap */
            {
               void const *aux = tab[j + 1];
               tab[j + 1] = tab[j];
               tab[j] = aux;
            }
            sorted = 0;
            aff (tab, n);
         }
      }
   }
   while (!sorted);
}
 
static int compare (void const *a, void const *b)
{
   return strcmp (a, b);
}
 
int main (void)
{
   void const *tab[] = { "d", "c", "b", "a" };
   tri_quest2 (tab, 4, &compare);
   puts ("");
 
   aff (tab, 4);
 
   return 0;
}

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
c d b a
c b d a
c b a d
b c a d
b a c d
a b c d
 
a b c d
 
Press ENTER to continue.