Discussion :

[kronos85]

Bien le bonjour !

Alors pour faire court, je faisait une petite classe permettant de coder un texte (en fait de le compresser) par la méthode d'Huffman, rien de bien compliqué.

Je ne suis pas sûr de mon algo, mais là n'est pas le problème.
En effet, je compile et tout se passe à merveilles, sauf que arrivé à un point du prog, ça plante (j'ai un beau message windaube ^^ : xxxx.exe a rencontré un problème et doit fermer...) systématiquement au même endroit.

J'ai pensé à un souci de pointeur ou qqchose dans le genre, mais le compilo ne bronche pourtant pas...

Précisions :
IDE -> Dev-C++ 4.9.9.2
OS -> WinXP
APP -> Appli DOS (donc pas de Framework)


Voilà les codes de mon main, mon code_huffman.h et .cpp :

main.cpp

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
#include <iostream>
#include <string>
 
#include "code_huffman.h"
#include "decode_huffman.h"
 
using namespace std;
 
 
int main()
{
	string phrase;
	Code code;
 
	cout << "***** Entrer la phrase a coder *****" << endl << endl;
	getline(cin, phrase);
 
	code.coder(phrase);
 
	system("PAUSE");	
	return EXIT_SUCCESS;
}

code_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 CODE_HUFF
#define CODE_HUFF
 
class Code
{
      public:
             Code();
             void coder(std::string phrase);
 
      private:
              char m_phrase_base[];
};
#endif

code_huffman.cpp

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <iostream>
#include <string>
#include <vector>
#include "code_huffman.h"
 
using namespace std;
 
Code:: Code()
{    
}
 
void Code:: coder(string phrase)
{
       strcpy(m_phrase_base, phrase.c_str());
 
       cout << "Vous avez saisi : \"" <<m_phrase_base <<"\"" << endl;
       cout << "Codage en cours..." <<endl;
 
       int  taille=strlen(m_phrase_base); // on récupère la taille de la chaine
       char tab_char[]= "";               // pour stocker les lettre "noeuds" de l'arbre d'Huffman
       vector <int>  tab_occur;           // nombre d'occurences des noeuds
       int  pos_tabs=0;                   // position dans tab_char et dans le vecteur
 
 
       for(int i=0; i<taille; i++)        // parcours de la chaine de caractères
       {
        if(i==0)    // premier caractère
        {
           tab_char[pos_tabs]=       m_phrase_base[i];
           tab_occur[pos_tabs]=      1;
        }
 
        else
        {
            int j=i-1;                    // indice de parcours du tableau de noeuds
            bool ajouter_char= true;      // permet de savoir si on a un nouveau noeud à ajouter ou pas
 
            do
            {
             if(m_phrase_base[i]!=tab_char[j]) // teste si l'on a pas encore rencontré le caractère
                                               // en comparant au tableau de noeuds
             {
               j--;                            // si c'est le cas on compare avec le reste du tableau
             }     
 
             else
             {
                 j=0;                          // sinon on arrête de comparer
                 ajouter_char= false;
                 tab_occur[j]+= 1;             // et on rajoute une occurence au noeud en question
             }
            }
            while(j>0);
 
            if(ajouter_char)                   // ajout d'un noeud
            {
                pos_tabs++;
 
                tab_char[pos_tabs]=   m_phrase_base[i];
                tab_occur[pos_tabs]+= 1;
            }
        }
       }
 
// affichage du tableau de noeuds       
       for(int i=0; i<pos_tabs; i++)
              cout << tab_char[i] << " | ";
 
       cout << endl;
 
// affichage du vecteur d'occurences       
       for(int i=0; i<pos_tabs; i++)
              cout << tab_occur[i] << " | ";
}

une idée sur le pourquoi du comment ?

[Lucien63]

Code :

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

char tab_char[]= "";

tab_char est un tableau de char vide (un seul caractère \0)

Et toi tu va écrire en dehors de ses limites, c'est normal que ça plante.

[kronos85]

Oui en effet c'est pas très malin d'avoir fait ça...

Cependant j'ai remplacé ça par un vecteur :

Code :

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

vector <char> tab_char;

et le problème reste le même... :/

[Lucien63]

Code :

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

char m_phrase_base[];

m_phrase_base est un pointeur non initialisé et toi tu t'en sert pour écrire en mémoire.

Code :

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

strcpy(m_phrase_base, phrase.c_str());

ça fait forcement des étincelles.

[kronos85]

Eh bien non ! J'ai parlé trop vite car en fait l'erreur ne vient pas de là !

Si je ne laisse que le code suivant dans mon 'code_huffman.cpp'

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
#include <iostream>
#include <string>
#include <vector>
#include "code_huffman.h"
 
using namespace std;
 
Code:: Code()
{    
}
 
void Code:: coder(string phrase)
{
       strcpy(m_phrase_base, phrase.c_str());
 
       cout << "Vous avez saisi : \"" <<m_phrase_base <<"\"" << endl;
       cout << "Codage en cours..." <<endl;
}

Et sans modifier quoi que ce soit ailleurs, le programme s'execute jusque au bout sans aucune erreur...

Le problème vient donc apparament d'ailleurs...

[edit] Erf ! en effet il vient simplement de là (enfin depuis que je suis passé en vecteur du moins) :

Code :

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

1
2
3
4
5
6
7
for(int i=0; i<taille; i++)        // parcours de la chaine de caractères
       {
        if(i==0)    // premier caractère
        {
           tab_char[pos_tabs]=       m_phrase_base[i];
           tab_occur[pos_tabs]=      1;
        }

l'assignation d'une valeur se fait comme ça :

Code :

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

1
2
           tab_char.push_back(m_phrase_base[i]);
           tab_occur.push_back(1);

Je pensais qu'on pouvait assigner comme pour un tableau 'normal' mais apparament non...

[kronos85]

Décidément...

Bon mon algo avait lui aussi quelques soucis, je l'ai donc modifié (le .h et le main n'ont pas été modifiés par rapport au 1er post):

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
57
58
59
60
61
void Code:: coder(string phrase)
{
       strcpy(m_phrase_base, phrase.c_str());
 
       cout << "Vous avez saisi : \"" <<m_phrase_base <<"\"" << endl;
       cout << "Codage en cours..." <<endl;
 
       int  taille=strlen(m_phrase_base); // on récupère la taille de la chaine
       vector <char> tab_char;            // pour stocker les lettre "noeuds" de l'arbre d'Huffman
       vector <int>  tab_occur;           // nombre d'occurences des noeuds
       int  pos_tabs=0;                   // position dans tab_char et dans le vecteur
 
 
       for(int i=0; i<taille; i++)        // parcours de la chaine de caractères
       {
        if(i==0)    // premier caractère
        {
           tab_char.push_back(m_phrase_base[i]);
           tab_occur.push_back(1);
        }
        else
        {
            int j=i-1;                    // indice de parcours du tableau de noeuds
            bool ajouter_char= true;      // permet de savoir si on a un nouveau noeud à ajouter ou pas
 
            do
            {
             if(m_phrase_base[i]!=tab_char[j]) // teste si l'on a pas encore rencontré le caractère
                                               // en comparant au tableau de noeuds
             {
               j--;                            // si c'est le cas on compare avec le reste du tableau
             }
 
             else
             {
                 ajouter_char= false;
                 tab_occur.at(j)+= 1;          // et on rajoute une occurence au noeud en question
                 j=-1;                          // sinon on arrête de comparer
             }
            }
            while(j>=0);
 
            if(ajouter_char== true)            // ajout d'un noeud
            {
                pos_tabs++;
 
                tab_char.push_back(m_phrase_base[i]);
                tab_occur.push_back(1);
            }
        }
       }
 
// affichage du tableau de noeuds
       for(int i=0; i<tab_char.size(); i++)
              cout << tab_char.at(i) << " | ";
 
       cout << endl;
 
// affichage du vecteur d'occurences
       for(int i=0; i<tab_occur.size(); i++)
              cout << tab_occur.at(i) << " | ";

Le code marche impeccablement... sauf... si la phrase saisie par l'utilisateur dépasse 17 caractères !

Si on saisit ça : 012345678901234567
C'est nickel le prog fait ce qu'on lui demande et sans broncher.
Si on saisit ça : 0123456789012345678
C'est nickel le prog fait ce qu'on lui demande mais là il bronche à la sortie du programme ! (c'est à dire après le system("PAUSE") => "Appuyez sur une touche pour continuer")

Je pense que j'ai dû oublier quelque chose qui ne plait pas à la mémoire, mais quoi... et surtout pourquoi seulement après 17 caractères !?

[Lucien63]

m_phrase_base c'est quoi ?

Car s'il est toujours déclaré comme avant :

Code :

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

char m_phrase_base[];

C'est sur que ça va planter quand tu fait la copie de chaîne :

Code :

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

strcpy(m_phrase_base, phrase.c_str());

[kronos85]

Eh bien c'est un simple tableau de caractères dynamique qui me sert à enregistrer la phrase de départ que donne l'utilisateur.

Ceci dit, il est bien déclaré comme ça, mais ça ne plante pas ! enfin ça plante SEULEMENT si la phrase de l'utilisateur dépasse les 17 caractères !

Ce qu'il se passe c'est que ça ne plante QUE lorsque le programme se ferme, pas avant !
Le programme se déroule correctement : la phrase est copié et les deux vecteurs (d'enumération des caractères et d'occurences) sont ok !

[Lucien63]

Pour créer un tableau de char dynamique on crée une variable pointeur et on alloue de la mémoire.
ex:

Code :

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

1
2
char *m_phrase_base;
m = new char[255];

[kronos85]

Ben le souci c'est que là, la taille de mon tableau n'est pas dynamique dans ce cas, elle est fixée à 255. Or j'aimerais pouvoir taper autant de texte que je veux...

Ceci dit, cette solution règle effectivement le problème si on décide de limiter l'entrée utilisateur (j'en déduit que la valeur de 17 est... arbitraire ? aléatoire ?)

Et au passage, merci pour ton aide et ta patience

[droggo]

Fie,

Ceci dit, cette solution règle effectivement le problème si on décide de limiter l'entrée utilisateur (j'en déduit que la valeur de 17 est... arbitraire ? aléatoire ?)

c'est un comportement indéfini. Tu as seulement la malchance que ça passe pour certaines valeurs (malchance, car ça semble marcher alors qu'il y a un bug).

Et puisque tu fais du C++, pourquoi utilises-tu des char[] au lieu de string ?

[kronos85]

j'utilise des tableaux de char pour pouvoir les parcourir caractère par caractère (pour pouvoir appliquer l'algorithme de Huffman) mais peut-être y a-t-il une méthode pour cela avec les string ?!

[Davidbrcz]

Bien sur que oui ! Ou serait l'intérêt sinon ?
Exemple :

Code :

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

1
2
std::string s("abc");
char c = s[0] ; //c=a

[kronos85]

cool ^.^

Je me coucherait encore moins bête ce soir

Merci tout le monde

[Davidbrcz]

Une très bonne doc sur la STL : ici

[kronos85]

Ah cool c'est exactement ce que je cherchais !

(erf pourtant c'était en gros dans ta signature !!! /me court chercher une 2e paire de lunettes... ^^)

[Davidbrcz]

HS: Je viens de l'ajouter, ya encore 1H le lien n'y était pas