allelben
2012-05-25, 11:33
bonjour
svp aide moi
exercice:
1-implémenter une fonction permattant de calculer les fréquences contenus dans une chaine de caracteres
2-implémenter une fonction permattant de calculer les fréquences contenus dans un fichier texte (nom de fichier fich1.txt et adrresse d://fich1.txt).
3-implementer l'algorithme de hoffman pour calculer les codes des caracteres selon un tableau de frequences
4-implimenter l'algorithme de hoffman permattant le decodage
5-rediger un rapport concernant votre implimentation
et voila mon essaye
ou es l erreur
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct noeud
{
unsigned char lettre;
int nb_occ;
struct noeud * f_g, * f_d;
} Noeud;
Noeud * nouveau_noeud(unsigned char lettre, int nb_occ,
Noeud * gauche, Noeud * droite);
void initialiser(Noeud * table[256]);
int compter(char * nom_sortie, Noeud * table[256]);
int trier_eliminer(Noeud * table[256]);
void inserer(Noeud * table[256], Noeud * cle, int taille);
Noeud * calculer_arbre(Noeud * table[256], int nb_non_nul);
int profondeur(Noeud * arbre);
void remplir_table(Noeud * arbre, char ** table_code, char * chaine, int hauteur);
void afficher(FILE * sortie, char ** table_code);
int nb_0_1(Noeud * arbre, int hauteur);
int main(int argc, char ** argv)
{
Noeud * table[256];
Noeud * arbre;
char * table_code[256];
char * chaine;
int max, i, nb_non_nul;
int longueur_non_code;
int longueur_code;
int nb;
FILE * sortie;
initialiser(table);
longueur_non_code = compter(argv[1], table);
nb_non_nul = trier_eliminer(table);
arbre = calculer_arbre(table, nb_non_nul);
max = profondeur(arbre);
printf("max = %d\n", max);
for (i = 0; i < 256; i++) table_code[i] = NULL;
chaine = (char *) malloc((max + 1) * sizeof(char));
if (chaine == NULL)
{
printf("plus de place pour chaine\n");
exit(1);
}
remplir_table(arbre, table_code, chaine, 0);
sortie = fopen(argv[2], "w");
if (sortie == NULL)
{
printf("fichier inexistant\n");
exit(1);
}
afficher(stdout, table_code);
afficher(sortie, table_code);
fclose(sortie);
printf("longueur du texte non code = %d\n", longueur_non_code);
nb = longueur_code = nb_0_1(arbre, 0);
longueur_code = nb / 8 + (nb % 8 != 0 ? 1 : 0);
printf("longueur du texte code = %d\n", longueur_code);
return 0;
}
Noeud * nouveau_noeud(unsigned char lettre, int nb_occ,
Noeud * gauche, Noeud * droite)
{
Noeud * nouveau;
nouveau = (Noeud *) malloc(sizeof(Noeud));
if (nouveau == NULL)
{
printf("plus de place dans nouveau_noeud\n");
exit(1);
}
nouveau -> lettre = lettre;
nouveau -> nb_occ = nb_occ;
nouveau -> f_g = gauche;
nouveau -> f_d = droite;
return nouveau;
}
void initialiser(Noeud * table[256])
{
int i;
for (i = 0; i < 256; i++) table[i] = nouveau_noeud(i, 0, NULL, NULL);
}
/* Compte les nombres d'occurrences de chaque lettre
et renvoie le nombre total de lettres du texte */
int compter(char * D://fich1.txt, Noeud * table[256])
{
unsigned char caractere;
int nb = 0;
FILE * fichier;
fichier = fopen(D://fich1.txt, "r");
if (fichier == NULL)
{
printf("fichier inexistant\n");
exit(1);
}
while (fscanf(fichier, "%c", &caractere) != EOF)
{
table[caractere] -> nb_occ++;
nb++;
}
fclose(fichier);
return nb;
}
/* insere le noeud cle dans le tableau de noeuds table trié par ordre
décroissant entre les indices 0 à taille - 1
en respectant l'ordre décroissant
*/
void inserer(Noeud * table[256], Noeud * cle, int taille)
{
int i = taille;
while ((i >= 1) && (table[i - 1] -> nb_occ < cle -> nb_occ))
{
table[i] = table[i - 1];
i = i - 1;
}
table[i] = cle;
}
int trier_eliminer(Noeud * table[256])
{
int i;
int nb_non_nul = 0;
for (i = 1; i < 256; i++)
if (table[i] -> nb_occ > 0)
{
inserer(table, table[i], nb_non_nul);
nb_non_nul++;
}
else free(table[i]);
return nb_non_nul;
}
Noeud * calculer_arbre(Noeud * table[256], int nb_non_nul)
{
int nb;
Noeud * n1, * n2, * nouveau;;
for (nb = nb_non_nul; nb > 1; nb--)
{
n1 = table[nb - 2];
n2 = table[nb - 1];
nouveau = nouveau_noeud('_', n1 -> nb_occ + n2 -> nb_occ, n1, n2);
inserer(table, nouveau, nb - 2);
}
return table[0];
}
int profondeur(Noeud * arbre)
{
int g, d;
if (arbre == NULL) return -1;
g = profondeur(arbre -> f_g);
d = profondeur(arbre -> f_d);
if (g >= d) return g + 1;
return d + 1;
}
void remplir_table(Noeud * arbre, char ** table_code, char * chaine, int hauteur)
{
unsigned char lettre;
if (arbre -> f_g == NULL)
{
lettre = arbre -> lettre;
chaine[hauteur] = '\0';
table_code[lettre] = (char *) malloc((hauteur + 1) * sizeof(char));
if (table_code[lettre] == NULL)
{
printf("plus de place dans remplir_table\n");
exit(1);
}
strcpy(table_code[lettre], chaine);
}
else
{
chaine[hauteur] = '0';
remplir_table(arbre -> f_g, table_code, chaine, hauteur + 1);
chaine[hauteur] = '1';
remplir_table(arbre -> f_d, table_code, chaine, hauteur + 1);
}
}
void afficher(FILE * sortie, char ** table_code)
{
int i;
for (i = 0; i < 256; i++)
if (table_code[i] != NULL) fprintf(sortie, "%c (%d) : %s\n", i, i, table_code[i]);
}
/* Retourne le nombre de 0 et de 1 correspondant au codage dans le texte codé
des lettres contenus dans arbre */
int nb_0_1(Noeud * arbre, int hauteur)
{
if (arbre -> f_g == NULL) return hauteur * arbre -> nb_occ;
return nb_0_1(arbre -> f_g, hauteur + 1) + nb_0_1(arbre -> f_d, hauteur + 1);
}
svp aide moi
exercice:
1-implémenter une fonction permattant de calculer les fréquences contenus dans une chaine de caracteres
2-implémenter une fonction permattant de calculer les fréquences contenus dans un fichier texte (nom de fichier fich1.txt et adrresse d://fich1.txt).
3-implementer l'algorithme de hoffman pour calculer les codes des caracteres selon un tableau de frequences
4-implimenter l'algorithme de hoffman permattant le decodage
5-rediger un rapport concernant votre implimentation
et voila mon essaye
ou es l erreur
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct noeud
{
unsigned char lettre;
int nb_occ;
struct noeud * f_g, * f_d;
} Noeud;
Noeud * nouveau_noeud(unsigned char lettre, int nb_occ,
Noeud * gauche, Noeud * droite);
void initialiser(Noeud * table[256]);
int compter(char * nom_sortie, Noeud * table[256]);
int trier_eliminer(Noeud * table[256]);
void inserer(Noeud * table[256], Noeud * cle, int taille);
Noeud * calculer_arbre(Noeud * table[256], int nb_non_nul);
int profondeur(Noeud * arbre);
void remplir_table(Noeud * arbre, char ** table_code, char * chaine, int hauteur);
void afficher(FILE * sortie, char ** table_code);
int nb_0_1(Noeud * arbre, int hauteur);
int main(int argc, char ** argv)
{
Noeud * table[256];
Noeud * arbre;
char * table_code[256];
char * chaine;
int max, i, nb_non_nul;
int longueur_non_code;
int longueur_code;
int nb;
FILE * sortie;
initialiser(table);
longueur_non_code = compter(argv[1], table);
nb_non_nul = trier_eliminer(table);
arbre = calculer_arbre(table, nb_non_nul);
max = profondeur(arbre);
printf("max = %d\n", max);
for (i = 0; i < 256; i++) table_code[i] = NULL;
chaine = (char *) malloc((max + 1) * sizeof(char));
if (chaine == NULL)
{
printf("plus de place pour chaine\n");
exit(1);
}
remplir_table(arbre, table_code, chaine, 0);
sortie = fopen(argv[2], "w");
if (sortie == NULL)
{
printf("fichier inexistant\n");
exit(1);
}
afficher(stdout, table_code);
afficher(sortie, table_code);
fclose(sortie);
printf("longueur du texte non code = %d\n", longueur_non_code);
nb = longueur_code = nb_0_1(arbre, 0);
longueur_code = nb / 8 + (nb % 8 != 0 ? 1 : 0);
printf("longueur du texte code = %d\n", longueur_code);
return 0;
}
Noeud * nouveau_noeud(unsigned char lettre, int nb_occ,
Noeud * gauche, Noeud * droite)
{
Noeud * nouveau;
nouveau = (Noeud *) malloc(sizeof(Noeud));
if (nouveau == NULL)
{
printf("plus de place dans nouveau_noeud\n");
exit(1);
}
nouveau -> lettre = lettre;
nouveau -> nb_occ = nb_occ;
nouveau -> f_g = gauche;
nouveau -> f_d = droite;
return nouveau;
}
void initialiser(Noeud * table[256])
{
int i;
for (i = 0; i < 256; i++) table[i] = nouveau_noeud(i, 0, NULL, NULL);
}
/* Compte les nombres d'occurrences de chaque lettre
et renvoie le nombre total de lettres du texte */
int compter(char * D://fich1.txt, Noeud * table[256])
{
unsigned char caractere;
int nb = 0;
FILE * fichier;
fichier = fopen(D://fich1.txt, "r");
if (fichier == NULL)
{
printf("fichier inexistant\n");
exit(1);
}
while (fscanf(fichier, "%c", &caractere) != EOF)
{
table[caractere] -> nb_occ++;
nb++;
}
fclose(fichier);
return nb;
}
/* insere le noeud cle dans le tableau de noeuds table trié par ordre
décroissant entre les indices 0 à taille - 1
en respectant l'ordre décroissant
*/
void inserer(Noeud * table[256], Noeud * cle, int taille)
{
int i = taille;
while ((i >= 1) && (table[i - 1] -> nb_occ < cle -> nb_occ))
{
table[i] = table[i - 1];
i = i - 1;
}
table[i] = cle;
}
int trier_eliminer(Noeud * table[256])
{
int i;
int nb_non_nul = 0;
for (i = 1; i < 256; i++)
if (table[i] -> nb_occ > 0)
{
inserer(table, table[i], nb_non_nul);
nb_non_nul++;
}
else free(table[i]);
return nb_non_nul;
}
Noeud * calculer_arbre(Noeud * table[256], int nb_non_nul)
{
int nb;
Noeud * n1, * n2, * nouveau;;
for (nb = nb_non_nul; nb > 1; nb--)
{
n1 = table[nb - 2];
n2 = table[nb - 1];
nouveau = nouveau_noeud('_', n1 -> nb_occ + n2 -> nb_occ, n1, n2);
inserer(table, nouveau, nb - 2);
}
return table[0];
}
int profondeur(Noeud * arbre)
{
int g, d;
if (arbre == NULL) return -1;
g = profondeur(arbre -> f_g);
d = profondeur(arbre -> f_d);
if (g >= d) return g + 1;
return d + 1;
}
void remplir_table(Noeud * arbre, char ** table_code, char * chaine, int hauteur)
{
unsigned char lettre;
if (arbre -> f_g == NULL)
{
lettre = arbre -> lettre;
chaine[hauteur] = '\0';
table_code[lettre] = (char *) malloc((hauteur + 1) * sizeof(char));
if (table_code[lettre] == NULL)
{
printf("plus de place dans remplir_table\n");
exit(1);
}
strcpy(table_code[lettre], chaine);
}
else
{
chaine[hauteur] = '0';
remplir_table(arbre -> f_g, table_code, chaine, hauteur + 1);
chaine[hauteur] = '1';
remplir_table(arbre -> f_d, table_code, chaine, hauteur + 1);
}
}
void afficher(FILE * sortie, char ** table_code)
{
int i;
for (i = 0; i < 256; i++)
if (table_code[i] != NULL) fprintf(sortie, "%c (%d) : %s\n", i, i, table_code[i]);
}
/* Retourne le nombre de 0 et de 1 correspondant au codage dans le texte codé
des lettres contenus dans arbre */
int nb_0_1(Noeud * arbre, int hauteur)
{
if (arbre -> f_g == NULL) return hauteur * arbre -> nb_occ;
return nb_0_1(arbre -> f_g, hauteur + 1) + nb_0_1(arbre -> f_d, hauteur + 1);
}