Discussion :

[Yux]

Salut,

Je suis toujours sur mon programme de compression utilisant l'algorithme de Huffman (toujours au début, en fait). Je dois trier un tableau de structures, chaque structure contenant un int qui représente la valeur décimale d'un octet, et un unsigned long int qui représente le nombre d'occurences de cet octet dans le fichier à compresser.

La structure concernée est déclarée comme suit dans huffman.h :

Code :

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

1
2
3
4
typedef struct {
	unsigned long int freq;
	int index;
} s_freq_array_element;

J'ai essayé de réaliser mon tri à l'aide de la fonction qsort, l'objectif étant de trier sur la fréquence. Voici l'implémentation de ma fonction de comparaison :

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
int compare (const s_freq_array_element *a, const s_freq_array_element *b)
{
	int i;
	if (a->freq < b->freq)
	{
		i = -1;
	}
	if (a->freq == b->freq)
	{
		i = 0;
	}
	if (a->freq > b->freq)
	{
		i = 1;
	}
	return (i);
}

Dans la fonction main, j'écris ceci :

Code :

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

1
2
3
int (*p_compare)(const s_freq_array_element *a, const s_freq_array_element *b);
 
qsort (p_freq_array, freq_array_size, sizeof(s_freq_array_element), p_compare);

A la compilation, la ligne :

Code :

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

qsort (p_freq_array, freq_array_size, sizeof(s_freq_array_element), p_compare);

renvoie ce warning :

main.c: In function 'main':
main.c:24: warning: passing argument 4 of 'qsort' from incompatible pointer type

La page de man de qsort indique que la fonction de comparaison attend deux const void *. Je croyais que dans le cas de variables de type void, le cast était implicite. Si quelqu'un pouvait m'éclairer là-dessus...

Merci

[Yux]

Ben, c'est le cas non ?

Code :

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

int (*p_compare)(const s_freq_array_element *a, const s_freq_array_element *b);

Je pensais que cette ligne déclarait un pointeur p_compare sur une fonction renvoyant un int et prenant en argument deux pointeurs sur des structures s_freq_array_element. Cela dit, je débute en c. Je suis peut-être complètement à la masse...

[Skyounet]

Désolé j'ai supprimé mon post, en relisant le tien, j'ai remarque que j'avais mal lu.

Bref je suis en train de regarder des exemples avec qsort sur le net et pour la fonction de comparaison il l'utilisent void *.

Code :

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

1
2
 
int (*p_compare)(const void *a, const void*b);

[diogene]

Code :

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

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

qsort attend une fonction dont les deux arguments sont const void *. Tu dois construire une fonction de ce type sinon le type de l'argument est incorrect.

Code :

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

1
2
3
4
5
6
7
int compare (const void *aa, const void *bb) 
{
  const s_freq_array_element *a = aa;
  const s_freq_array_element *b = bb;
   int i; 
   if (a->freq < b->freq) 
   {....

et dans main

Code :

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

qsort (p_freq_array, freq_array_size, sizeof(s_freq_array_element), compare);

[Skyounet]

Code :

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

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

qsort attend une fonction dont les deux arguments sont const void *. Tu dois construire une fonction de ce type sinon le type de l'argument est incorrect.

Code :

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

1
2
3
4
5
6
7
int compare (const void *aa, const void *bb) 
{
  const s_freq_array_element *a = aa;
  const s_freq_array_element *b = bb;
   int i; 
   if (a->freq < b->freq) 
   {....

et dans main

Code :

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

qsort (p_freq_array, freq_array_size, sizeof(s_freq_array_element), compare);

Plutot comme ca

Code :

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

1
2
3
4
5
6
7
int (*compare) (const void *aa, const void *bb) 
{
  const s_freq_array_element *a = aa;
  const s_freq_array_element *b = bb;
   int i; 
   if (a->freq < b->freq) 
   {....

[Yux]

Merci pour vos réponses, j'ai testé celle de Diogène qui fonctionne parfaitement à l'exception du fait que le quatrième argument doit être un pointeur sur la fonction compare. Pour résumer, cela donne ça :

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
int compare (const void *p_a, const void *p_b)
{
	const s_freq_array_element *p_element1 = p_a;
	const s_freq_array_element *p_element2 = p_b;
	int i;
	if (p_element1->freq < p_element2->freq)
	{
		i = -1;
	}
	if (p_element1->freq == p_element2->freq)
	{
		i = 0;
	}
	if (p_element1->freq > p_element2->freq)
	{
		i = 1;
	}
	return (i);
}

Fichier main.c :

Code :

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

1
2
3
4
5
6
7
int (*p_compare)(const void *p_a, const void *p_b);
 
int main (int argc, char *argv[])
{
	p_compare = compare;
	qsort (p_freq_array, freq_array_size, sizeof(s_freq_array_element), p_compare);
}

Si j'affiche le contenu du tableau une fois trié (testé sur un petit fichier texte) :

Fréquence : 1, index : 51
Fréquence : 1, index : 52
Fréquence : 1, index : 60
Fréquence : 1, index : 71
Fréquence : 1, index : 122
Fréquence : 1, index : 233
Fréquence : 2, index : 38
Fréquence : 2, index : 56
Fréquence : 2, index : 67
Fréquence : 2, index : 95
Fréquence : 3, index : 54
Fréquence : 3, index : 58
Fréquence : 3, index : 61
Fréquence : 3, index : 62
Fréquence : 3, index : 103
Fréquence : 4, index : 49
Fréquence : 4, index : 53
Fréquence : 4, index : 102
Fréquence : 4, index : 119
Fréquence : 5, index : 48
Fréquence : 5, index : 104
Fréquence : 5, index : 107
Fréquence : 6, index : 46
Fréquence : 6, index : 50
Fréquence : 6, index : 120
Fréquence : 10, index : 98
Fréquence : 10, index : 113
Fréquence : 14, index : 116
Fréquence : 15, index : 112
Fréquence : 18, index : 118
Fréquence : 19, index : 97
Fréquence : 21, index : 99
Fréquence : 23, index : 105
Fréquence : 23, index : 110
Fréquence : 23, index : 114
Fréquence : 24, index : 115
Fréquence : 25, index : 45
Fréquence : 27, index : 108
Fréquence : 28, index : 10
Fréquence : 29, index : 100
Fréquence : 29, index : 117
Fréquence : 38, index : 109
Fréquence : 40, index : 101
Fréquence : 40, index : 111
Fréquence : 46, index : 47
Fréquence : 57, index : 32

Merci encore à tous les deux, j'attaque la construction de l'arbre. Je crois pouvoir dire que vous allez avoir de mes nouvelles dans un futur très proche

[diogene]

à l'exception du fait que le quatrième argument doit être un pointeur sur la fonction compare.

Mais l'identificateur d'une fonction seul (sans les ()) est un pointeur sur la fonction . La preuve est dans ton code :

Code :

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

1
2
int (*p_compare)(const void *p_a, const void *p_b);  
p_compare = compare;

p_compare est inutile dans qsort, compare suffit.

[Yux]

Ah oui, excuse-moi Diogène, vu comme ça c'est limpide effectivement. La première fois que j'avais testé, j'avais eu un warning sur un problème de pointeur mais j'avais du oublier de décommenter une ligne. Merci encore !