Ho le seguenti classi
codice:
#ifndef HUFFMAN_H#define HUFFMAN_H
#include "Nodo.h"
#include "Priority_queue.h"
#include <iostream> //libreria per l'i/o
#include <vector> //libreria per gestire i vettori
#include <fstream> //libreria per gestire i files
#include <cmath> //libreria che permette di usare funzioni matematiche (nel mio caso la pow())
#include <cstdlib> //libreria che permette di usare le funzioni system
#include <string> //libreria che permette di usare e gestire le stringhe
#include <bitset> //libreria che permette l'uso di array di bit
using namespace std;
class Huffman //classe con i metodi per la codifica e decodifica di Huffman
{
public:
Huffman();
void encoding(string p);
void decompression();
~Huffman();
private:
void compression(string p);
vector<char>read_file(string name);
void build_tree();
void build_tree_decompression();
void rate_compression();
void coding(Nodo*,char character,bool &);
vector <int> v;
vector <int> occurrences;
vector <char> input;
Nodo* root;
};
#endif // HUFFMAN_H
codice:
#include "Huffman.h"#include "Nodo.h"
#include "Priority_queue.h"
using namespace std;
vector<char>Huffman::read_file(string name)
{
ifstream fileread;
fileread.open("name",ifstream::in);
if(fileread.is_open())
cout<<"Il file e' stato aperto con successo!"<<endl;
else{
cout<<"Il file non esiste!"<<endl;
system("pause");
exit(1);
}
vector<char> buffer;
char character;
while(fileread.get(character))
buffer.push_back(character);
fileread.close();
return buffer;
}
void Huffman::build_tree(){
for(int j=0;j<256;j++) //inizializzo il vettore con '0' in tutte le posizioni
occurrences.push_back(0);
for(int i=0;i<input.size();i++) //conto le occorrenze dei caratteri nel file e li memorizzo nel vettore
occurrences[static_cast<int> (input[i])]++;
vector <Nodo*> nodi;
for(int i=0;i<occurrences.size();i++) //inserisco le occorrenze nel vettore nodi
if(occurrences[i]>0)
nodi.push_back(new Nodo(occurrences[i],i));
Priority_queue *queue = new Priority_queue(nodi); //creo la queue di priorità con i nodi
while((queue->get_size())>1){
Nodo *nodo=new Nodo; //nodo allocato ed inizializzato
Nodo *left,*right; //nodi dichiarati
left=queue->extract_min();
right=queue->extract_min();
nodo->set_frequency(left->get_frequency()+right->get_frequency());
nodo->set_left(left);
nodo->set_right(right);
queue->insert_(nodo);
}
root=queue->extract_min();
}
void Huffman::coding(Nodo *n,char character,bool &check){
if(n->get_left()!=0){
v.push_back(0);
coding(n->get_left(),character,check);
}
if(check==false){
if(n->get_right()!=0){
v.push_back(1);
coding(n->get_right(),character,check);
}
}
if ((n->get_left() && n->get_right()) == 0) {
if(character == n->get_value()){
check=true;
return;
}
else {
v.pop_back();
return;
}
}
if (check==false){
v.pop_back();
return;
}
}
void Huffman::compression(string route){
ofstream filewrite;
string way;
way=route+".aa";
route.erase(route.end() -4,route.end());
filewrite.open(way.c_str(),ios::binary);
if(filewrite.is_open())
cout<<"*sto effettuando la compressione...*"<<endl;
for(int i=0;i<occurrences.size();i++)
filewrite.write((const char*)&occurrences[i],4);
int counter=0;
int size=v.size();
for(int i=0;i<size;i++){
counter++;
if(counter==8){
counter =0;
char character=0;
int j=7;
for(int i=0;i<=7;i++){
character+=pow(2,j--)*v[i];
}
filewrite.write(&character,sizeof(char));
v.erase(v.begin(),v.begin()+8); //inseriti 8 caratteri nel file, li cancello dal vettore
}
}
if(counter!=0){
while(v.size()<8){
v.push_back(0);
}
char character=0;
int j=7;
for(int i=0;i<=7;i++){
character+=pow(2,j--)*v[i];
}
filewrite.write(&character,sizeof(char));
}
filewrite.write((char*)&counter,4);
filewrite.close();
cout<<"codifica terminata!"<<endl;
}
void Huffman::rate_compression(){
cout<<"inserisci il percorso del file originale:\t"<<endl;
string route;
cin>>route;
ifstream filenoncompresso;
filenoncompresso.open("route",ifstream::in);
filenoncompresso.seekg(0,filenoncompresso.end);
int lunghezza1=filenoncompresso.tellg();
filenoncompresso.seekg(0,filenoncompresso.beg);
filenoncompresso.close();
ifstream filecompresso;
string way;
way=route+".aa";
route.erase(route.end()-4,route.end());
filecompresso.open(way.c_str());
filecompresso.seekg(0,filecompresso.end);
int lunghezza2=filecompresso.tellg();
lunghezza2=lunghezza2-1028;
filecompresso.seekg(0,filecompresso.beg);
cout<<"La differenza in byte tra il file non compresso e il file compresso e':"<<lunghezza1-lunghezza2<<endl;
}
void Huffman::encoding(string p){
input=read_file(p);
build_tree();
for(int i=0;i<input.size();i++){
bool check=false;
coding(root,input[i],check);
}
compression(p);
rate_compression();
}
void Huffman::build_tree_decompression(){
vector<Nodo*>nodi;
for(int i=0;i<occurrences.size();i++) //inserisco le occorrenze nel vettore nodi
if(occurrences[i]>0)
nodi.push_back(new Nodo(occurrences[i],i));
Priority_queue *queue= new Priority_queue(nodi); //creo la coda di priorità con i nodi
while((queue->get_size())>1){
Nodo *nodo=new Nodo; //nodo allocato ed inizializzato
Nodo *left,*right; //nodi dichiarati
left=queue->extract_min();
right=queue->extract_min();
nodo->set_frequency(left->get_frequency()+right->get_frequency());
nodo->set_left(left);
nodo->set_right(right);
queue->insert_(nodo);
}
root=queue->extract_min();
}
void Huffman::decompression(){
ofstream filewrite;
cout<<"Inserire il percorso del file da decomprimere:"<<endl;
string route;
cin>>route;
string way=route+"dc.txt";
route.erase(route.end()-3,route.end());
filewrite.open(way.c_str());
if(filewrite.is_open())
cout<<"File decompresso creato..."<<endl;
ifstream fileread;
string way_2;
way_2=route+".aa";
fileread.open(way_2.c_str(),ios::binary);
for(int i=0;i<256;i++) //inizializzo il vettore con '0' in tutte le posizioni
occurrences.push_back(0);
for(int j=0;j<256;j++)
fileread.read((char*)&occurrences[j],4);
build_tree_decompression();
fileread.seekg(-4,fileread.end);
int bit_clean;
fileread.read((char*)&bit_clean,4);
fileread.seekg(0,fileread.beg);
string buffer((std::istreambuf_iterator<char>(fileread)),std::istreambuf_iterator<char>());
fileread.close();
int bit_dirty=8-bit_clean;
buffer.erase(buffer.begin(),buffer.begin()+1024);
string sequence; //usata per esplorare l'albero
bitset<8>*bit;
for(int i=0;i<buffer.size()-4;i++){
bit=new bitset<8>(buffer[i]); //inizializzo bit con i bit del carattere i-esimo
sequence=sequence+bit->to_string(); //trasformo ogni bit in un carattere
delete bit;
}
int i=0;
Nodo* nodo;
while(i<sequence.size()-bit_dirty){
nodo=root;
while(!(nodo->get_left()==0 && nodo->get_right()==0)){ //fino a quando non trovo una foglia (ovvero ad un carattere)
nodo=sequence[i]==0 ? nodo->get_left() : nodo->get_right(); //operatore ternario
i++;
}
char character=nodo->get_value();
filewrite.write(&character,1);
}
filewrite.close();
}
codice:
#ifndef NODO_H#define NODO_H
using namespace std;
class Nodo
{
Nodo* left; // puntatore al nodo sinistro
Nodo* right; // puntatore al nodo destro
int frequency;
char value;
public:
Nodo() {}; // costruttore di default
Nodo (int freq, char val); //costruttore che prende in input frequency e value
Nodo* get_left();
Nodo* get_right();
char get_value();
int get_frequency();
void set_frequency(int frequen);
void set_value(char valu);
void set_right(Nodo*right);
void set_left(Nodo*left);
~Nodo() {delete left; delete right;}; //distruttore
};
#endif // NODO_H
codice:
#include "Nodo.h"
using namespace std;
Nodo::Nodo(int freq, char val) //implementazione del costruttore con parametri
{
this->frequency=freq;
this->value=val;
this->right=NULL;
this->left=NULL;
}
Nodo* Nodo::get_left(){
return this->left;
}
Nodo* Nodo::get_right(){
return this->right;
}
int Nodo::get_frequency(){
return this->frequency;
}
char Nodo::get_value(){
return this->value;
}
void Nodo::set_left(Nodo* left){
this->left=left;
}
void Nodo::set_right(Nodo* right){
this->right=right;
}
void Nodo::set_frequency(int frequen){
this->frequency=frequen;
}
void Nodo::set_value(char valu){
this->value=valu;
}
codice:
#include "Priority_queue.h"#include "Nodo.h"
using namespace std;
Priority_queue::Priority_queue(vector<Nodo*>&nodo){
for (int i = 0;i<nodo.size();i++)
this->n.push_back(nodo[i]);
build_heap();
}
int Priority_queue::get_size(){
return n.size();
}
int Priority_queue::get_left(int i){
return 2*i+1;
}
int Priority_queue::get_right(int i){
return 2*i+2;
}
Nodo* Priority_queue::get_root(){
return n[0];
}
Nodo* Priority_queue::extract_min(){
Nodo* temp;
temp = this->n[0];
this->n[0] = this->n[n.size() - 1];
this->n[n.size() - 1] = temp;
n.pop_back();
heapify(0);
return temp;
}
void Priority_queue::swap_nodo(int i,int j){
Nodo *temp = new Nodo();
temp = this->n[i];
this->n[i] = this->n[j];
this->n[j] = temp;
}
void Priority_queue::heapify(int i){
int minimum = i;
int r = get_right(i);
int l = get_left(i);
if (l<this->n.size() && n[minimum]->get_frequency()>n[l]->get_frequency())
minimum = l;
if (r<this->n.size() && n[minimum]->get_frequency()>n[r]->get_frequency())
minimum = r;
if (minimum != i) {
swap_nodo(minimum,i);
heapify(minimum);
}
}
void Priority_queue::build_heap(){
for (int i = ((this->n.size()) - 1); i >= 0; i--)
heapify(i);
}
void Priority_queue::insert_(Nodo*x){
this->n.push_back(x);
build_heap();
}
codice:
#ifndef Priority_queue_H#define Priority_queue_H
#include "Nodo.h"
using namespace std;
class Priority_queue
{
public:
Priority_queue();
Priority_queue(vector<Nodo*>&nodo); //costruttore con parametri
void insert_(Nodo*);
Nodo* extract_min();
Nodo* get_root();
int get_size();
~Priority_queue(); //distruttore
private:
vector <Nodo*> n;
void heapify(int);
void build_heap();
int get_left(int);
int get_right(int);
void swap_nodo(int, int);
};
#endif // Priority_queue_H
main
codice:
#include "Huffman.h"#include "Nodo.h"
#include "Priority_queue.h"
using namespace std;
int main() {
cout << endl << endl << " BENVENUTO NEL PROGRAMMA DI COMPRESSIONE E DECOMPRESSIONE DI LUIGI PICCOLO" << endl << endl << endl << endl << endl;
system("pause");
system("CLS");
cout << endl << endl << "\tInserire 1 per comprimere, 2 per decomprimere, 3 per uscire: ";
int choice;
cin >> choice;
Huffman *h = new Huffman();
string route;
if (choice == 1) {
cout << endl << endl << "\t\tInserire il percorso del file da comprimere: " << endl;
cout << "\t\t";
cin >> route;
system("pause");
system("CLS");
h->encoding(route);
}else if(choice == 2)
h->decompression();
cout << endl << endl << "\t\tUSCITA IN CORSO..." << endl << endl;
system("pause");
exit(1);
return 0;
}
Ho dovuto togliere le librerie perchè superavo i limiti del messaggio
L'errore undefined reference mi appare alla riga Huffman *h = new Huffman(); e non capisco il motivo
Come risolvo?