Discussion :

[Yux]

Désolé de poster un énième topic sur le sujet mais bien qu'ayant lu attentivement quelques uns des précédents, je n'arrive pas à mettre en oeuvre de solution élégante à mon problème (je débute en c).

J'essaye d'écrire un programme de compression utilisant l'algorithme de Huffman. En l'état actuel des choses, j'ai créé un tableau de 256 compteurs qui est correctement initialisé (fonction read_file). Je bute sur l'écriture de la fonction qui doit créer le tableau de fréquences. Le code complet :

huffman.h

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
#ifndef H_HUFFMAN
#define H_HUFFMAN
 
typedef struct {
	int value;
	unsigned long int frequency;
} s_frequency;
 
void read_file (const char *, unsigned long int []);
 
void create_frequencies_array (unsigned long int [], s_frequency []);
 
#endif /* guard */

huffman.c

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
#include<stdio.h>
#include<stdlib.h>
 
#include "huffman.h"
 
void read_file (const char *file, unsigned long int a_counters[])
{
	FILE *fp;
	int i;
 
	if ((fp = fopen (file, "rb")) == NULL)
	{
		fprintf (stderr, "Echec de l'ouverture du fichier %s", file);
		perror (" ");
		exit (1);
	}
	while ((i = fgetc (fp)) != EOF)
	{
		a_counters[i]++;
	}
	fclose (fp);
}
 
void create_frequencies_array (unsigned long int a_counters[], s_frequency a_frequencies[])
{
	int i = 0;
	int j = 0;
 
	for (i=0 ; i<256 ; i++)
	{
		if (a_counters[i] != 0)
		{
			j++;
		}
	}
	a_frequencies = malloc (j*sizeof(s_frequency));
	for (i=0 ; i<256 ; i++)
	{
		j = 0;
		if (a_counters[i] != 0)
		{
			a_frequencies[j].value = i;
			a_frequencies[j].frequency = a_counters[i];
		}
	}
}

main.c

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
#include<stdio.h>
 
#include "huffman.h"
 
const char *p_file;
unsigned long int a_counters[256] = {0};
s_frequency a_frequencies[];
 
int main (int argc, char *argv[])
{
	p_file = argv[1];
	read_file (p_file, a_counters);
	create_frequencies_array (a_counters, a_frequencies);
	return (0);
}

La fonction create_frequencies_array admet un tableau en argument, ce tableau étant modifié par la fonction. Est-ce une meilleure solution de ne pas déclarer le tableau dans la fonction main et de retourner un pointeur en sortie de la fonction create_frequencies_array ? La zone mémoire allouée sera-t-elle visible de la fonction main (j'ai vu que certains utilisaient des pointeurs de pointeurs)?


De plus, dans un cas ou dans l'autre, je ne vois pas de moyen simple pour connaître la taille du tableau une fois que l'on retourne à la fonction main.

Voilà, je vous serais vraiment reconnaissant d'éclairer ma lanterne...

[Trap D]

Pour connaitre la taille du tableau manipulé, il faut utiliser une variable supplémentaire qui la mémorise, tu peux d'ailleurs, pour ce faire, créer une structure :

Code :

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

1
2
3
4
5
typedef struct
{
  int taille;
  int *array;
} Str_Tab;

D'autre part, au sortir de la fonction create_frequencies_array, la nouvelle adresse a_frequencies est perdue, donc tu peux faire ainsi :

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
s_frequency *create_frequencies_array (unsigned long int a_counters[] )
{
   int i = 0;
   int j = 0;
   s_frequency *a_frequencies;   
   for (i=0 ; i<256 ; i++)
   {
      if (a_counters[i] != 0)
      {
         j++;
      }
   }
   a_frequencies = malloc (j*sizeof(s_frequency));
   if (a_frequencies != NULL)
   {
     for (i=0 ; i<256 ; i++)
     {
        j = 0; // pourquoi est-ce répété à chaque fois ??
        if (a_counters[i] != 0)
        {
           a_frequencies[j].value = i;
           a_frequencies[j].frequency = a_counters[i];
        }
     }
  }
  return a_frequencies; // il faudra faire attention au retour de tester la valeur NULL
}

[Yux]

Merci pour ta réponse Trap D, je voulais avoir une petite précision sur le pointeur retourné par la fonction create_frequencies_array : comment passe-t-on du pointeur au tableau ? Cette écriture par exemple est-elle valable ?

Code :

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

s_frequeny a_frequencies[] = create_frequencies (unsigned long int a_counters[]);

Sinon, bien vu pour le corps de la fonction. C'est ça que j'avais en tête :

Code :

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

1
2
3
4
5
6
7
8
9
10
for (i=0 ; i<256 ; i++)
	{
		j = 0;
		if (a_counters[i] != 0)
		{
			a_frequencies[j].value = i;
			a_frequencies[j].frequency = a_counters[i];
			j++;
		}
	}

[diogene]

Code :

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

s_frequeny a_frequencies[] = create_frequencies (unsigned long int a_counters[]);

La fonction renvoie une adresse, pas un tableau (même si cette adresse est celle du premier élément d'un tableau) donc, tu dois avoir,

Code :

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

 s_frequency * a_frequencies = create_frequencies (unsigned long int a_counters[]);

Ce qui ne t'empèches nullement de l'utiliser en écrivant

Code :

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

a_frequencies[i]

Code :

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

1
2
3
4
5
6
7
8
9
10
for (i=0 ; i<256 ; i++) 
   { 
      j = 0; 
      if (a_counters[i] != 0) 
      { 
         a_frequencies[j].value = i; 
         a_frequencies[j].frequency = a_counters[i]; 
         j++; 
      } 
   }

ne resoud pas l'objection de Trap D concernant j : Dans le if, j est toujours 0 et ceci est équivalent à

Code :

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

1
2
3
4
5
6
7
8
9
10
for (i=0 ; i<256 ; i++) 
   { 
      j = 0; 
      if (a_counters[i] != 0) 
      { 
         a_frequencies[0].value = i; 
         a_frequencies[0].frequency = a_counters[i]; 
         j++; 
      } 
   }

très probablement le code devrait être:

Code :

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

1
2
3
4
5
6
7
8
9
10
j = 0;
for (i=0 ; i<256 ; i++) 
   { 
      if (a_counters[i] != 0) 
      { 
         a_frequencies[j].value = i; 
         a_frequencies[j].frequency = a_counters[i]; 
         j++; 
      } 
   }

Enfin, la fonction ne permet pas de savoir combien d'éléments ont été alloués pour a_frequencies ce qui peut poser des problémes pour accéder aux éléments du tableau dans la fonction qui appelle create_frequencies

[Yux]

très probablement le code devrait être:

Code :

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

1
2
3
4
5
6
7
8
9
10
j = 0;
for (i=0 ; i<256 ; i++)
   {
      if (a_counters[i] != 0)
      {
         a_frequencies[j].value = i;
         a_frequencies[j].frequency = a_counters[i];
         j++;
      }
   }

Effectivement, au temps pour moi...

Enfin, la fonction ne permet pas de savoir combien d'éléments ont été alloués pour a_frequencies ce qui peut poser des problémes pour accéder aux éléments du tableau dans la fonction qui appelle create_frequencies

Trap D me conseillait justement d'utiliser une structure contenant cette information. Je ne sais pas si tu as une autre solution à me conseiller ? J'avais pensé à utiliser une liste chaînée mais je ne sais pas si ce mécanisme n'est pas trop lourd pour ce cas de figure...

[diogene]

Trap D me conseillait justement d'utiliser une structure contenant cette information. Je ne sais pas si tu as une autre solution à me conseiller ? J'avais pensé à utiliser une liste chaînée mais je ne sais pas si ce mécanisme n'est pas trop lourd pour ce cas de figure...

Dans la mesure où tu connais une limite supérieure à la taille du tableau et que cette limite est raisonnable, utiliser un tableau est plus léger à gérer qu'une liste et la solution de Trap D me semble répondre au problème et facile à mettre en oeuvre.

[Yux]

Salut Diogene, je me suis contenté au bout du compte de passer un pointeur sur int en argument de la fonction qui crée le tableau. En tout cas, merci pour tes éclaircissements. Je passe le topic en résolu.