Salve a tutti, tra meno di un mese ho l'esame di Algoritmi e per quella data devo creare un programma in C++ che effettui la codifica di Huffman.
Il nostro prof ci ha dato delle limitazioni, infatti non possiamo utilizzare la STL per la coda di priorità ma dobbiamo crearla noi tramite un min-heap.
Il codice è molto semplice perchè ho appena iniziato. Per adesso il testo è richiesto in input, successivamente lo aprirò da file.
Preso il testo, verifico la frequenza di tutti i caratteri e creo un vector. Successivamente dovrei effettuare l'heapify per portarmi il minimo elemento al primo posto nel vector così da poter andare a costruire l'albero di huffman.
Il problema è ho scritto il codice e questo sembra funzionare perchè il programma parte ma non vengono effettuati gli scambi..
Ecco il codice:
classe.h
class ELEMENTO
{
private:
char carattere;
int frequenza;
ELEMENTO *left;
ELEMENTO *right;
public:
ELEMENTO()
{
frequenza=0;
left=NULL;
right=NULL;
}
ELEMENTO(char x, int y)
{
carattere=x;
frequenza=y;
}
ELEMENTO(const ELEMENTO &orig){carattere=orig.carattere; frequenza=orig.frequenza; left=orig.left; right=orig.right;};
~ELEMENTO(){};
void ins_char(char x)
{
carattere=x;
}
void aggiorna_freq()
{
frequenza++;
}
void ins_left(ELEMENTO x)
{
*left=x;
}
void ins_right(ELEMENTO x)
{
*right=x;
}
char visualizza_char()
{
return carattere;
}
int visualizza_freq()
{
return frequenza;
}
};
main.cpp
int main()
{
string testo;
cout<<"Inserisci il testo da codificare: "; //inserisco il testo
getline(cin,testo);
int size;
size=testo.size()*8; //calcolo lo spazio occupato in memoria
cout<<endl<<"Il testo occupa "<<size<<" bit di memoria.\n"<<endl<<endl;
vector <ELEMENTO> caratteri; //creo il vettore delle frequenze dei caratteri
caratteri.push_back(ELEMENTO(' ',0)); //il primo nodo in un heap mediate vettore deve essere nullo
for(int i=0; i<testo.size(); i++)
{
bool ver=false; //variabile di verifica
if(caratteri.size()==1) //se il vettore è vuoto inserisco l'elemento normalmente...
{
caratteri.push_back(ELEMENTO(testo[i],1));
}
else //altrimenti sono costretto a verificare prima se l'i-esimo carattere è già stato inserito nel vettore
{
for(int j=1; j<caratteri.size(); j++)
{
if(testo[i]==caratteri[j].visualizza_char()) //se l'i-esimo carattere è presente nel vettore..
{
caratteri[j].aggiorna_freq(); //aggiorno semplicemente il numero di frequenza
ver=true; //e assegno valore true alla variabile di verifica
}
}
if(ver==false) //se la variabile di verifica è falsa vuol dire che l'i-esimo elemento non è presente nel vettore
{
caratteri.push_back(ELEMENTO(testo[i],1)); //quindi lo inserisco normalmente
}
}
}
for(int i=1; i<caratteri.size(); i++)
{
cout<<"Carattere: "<<caratteri[i].visualizza_char()<<" - Frequenza: "<<caratteri[i].visualizza_freq()<<"\n";
}
for(int j=(caratteri.size())-1;j>1;j=j-2)
{//in questo modo ci permette di salire nell’ albero, evitando di attivare la
//funzione anche al fratello del nodo corrente già heap-izzato e
//quindi di passare ad un altro figlio avente padre diverso (in pratica utilizza la procedura heap su 3 nodi alla volta )
heapify(caratteri,j);
}
cout<<endl<<endl<<"Min-Heap:"<<endl;
for(int i=1; i<caratteri.size(); i++)
{
cout<<"Carattere: "<<caratteri[i].visualizza_char()<<" - Frequenza: "<<caratteri[i].visualizza_freq()<<"\n";
}
cout<<endl<<endl<<endl;
system("PAUSE");
return 0;
}
heapifu.cpp
void heapify(vector <ELEMENTO> a, int nodo)
{
int padre,fratello,min;
ELEMENTO scambia;
int i;
while(nodo<=(a.size())-1)
{// esce dal while quando raggiunge una foglia
padre=nodo/2; //assegnazione di padre
fratello=nodo%2;//assegnazione di frattelo relativamente a nodo
if(fratello==0)
{// se nodo è pari allora cerca il fratello destro
fratello=(padre*2)+1;
}
else
{// nodo dispari, cerchiamo fratello sinistro
fratello=padre*2;
}
if(fratello>(a.size())-1 || a[fratello].visualizza_freq()>a[nodo].visualizza_freq())
{// fratello non esiste o confronto tra i due fratelli o nodo > fratello
min=nodo; //assegnzione fratello
}
else
{
min=fratello; // se il fratello esiste o e’ maggiore allora max = fratello
}
if(a[min].visualizza_freq()<a[padre].visualizza_freq())
{// confronto tra padre e max nel caso caso dell’ if...scambio!!!
scambia=a[min];
a[min]=a[padre];
a[padre]=scambia;
}
nodo=min*2;
} // discende nell’ albero per confrontare max che ora è un nuovo nodo con i nuovi figli assegnategli
}
Credevo fosse un problema di costruttore, ma nella classe è presente il costruttore copia quindi la parte del codice dove vengono effettuati gli scambi dovrebbe funzionare..
Grazie per eventuali risposte