// Huffman Tree.cpp
#include "stdafx.h"
#include <iostream>
#include <string>//Necessary to do any string comparisons
#include <fstream>
#include <iomanip>
#include <cstdlib>//for exit() function
using namespace std;
class BinaryTree{
private:
struct treenode{
char data;
int weight;
treenode *LChild;
treenode *RChild;
};
treenode * root;
int freq[256];
treenode* leaves[256];
string path[256];
string longestpath;
void BuildHuffmanStrings(treenode *p, string path);
public:
void InitializeFromFile(string FileName);
void EncodeFile(string InFile, string OutFile);
void DecodeFile(string InFile, string OutFile);
BinaryTree()
{
for(int i=0;i<256;i++){
freq[i]=0;
leaves[i] = new treenode;
}
root=NULL;
}
};//Class end
/*Takes supplied filename and builds Huffman tree, table of encoding strings, etc.
Should print number of bytes read.*/
void BinaryTree::InitializeFromFile(string Filename){
int CHAR_RANGE = 256;
ifstream inFile;
inFile.open(Filename.c_str(), fstream::binary);
if(inFile.fail()){
cout<<"Error in opening file "<<Filename;
return;
}
char c;
inFile.get(c);
int bytesread = 0;
while(!inFile.eof()){
bytesread++;
freq[(int)c] ++;
inFile.get(c);
}
for(int i=0;i<CHAR_RANGE;i++){//makes a leafnode for each char
leaves[i]->weight=freq[i];
leaves[i]->data=(char)i;
}
int wheremin1, wheremin2, min1, min2;
/*Builds the Huffman Tree by finding the first two minimum values and makes a parent
node linking to both*/
for(int k=0;k<256;k++){
wheremin1=0; wheremin2=0;
min1 = INT_MAX; min2 = INT_MAX;
//Finding the smallest values to make the branches/tree
for(int i=0;i<CHAR_RANGE;i++){
if(leaves[i] && freq[i]<min1){
min1=leaves[i]->weight; wheremin1=i;
}
}for(int i=0;i<CHAR_RANGE;i++){
if(leaves[i] && freq[i]<min2 && i!=wheremin1){
min2=leaves[i]->weight; wheremin2=i;
}
}
if(leaves[wheremin1] && leaves[wheremin2]){
treenode* p= new treenode;
p->LChild=leaves[wheremin1]; p->RChild=leaves[wheremin2];//Setting p to point at the two min nodes
p->weight=min1 + min2;
leaves[wheremin2]=NULL;
leaves[wheremin1]=p;
root=p;
}
}//end for(build tree)
cout<<" Bytes read: "<<bytesread;
cout<<" Weight of the root: "<<root->weight;
}
/*Takes supplied file names and encodes the InFile, placing the result in OutFile. Also
checks to make sure InitializeFromFile ran properly. Prints in/out byte counts. Also
computes the size of the encoded file as a % of the original.*/
void BinaryTree::EncodeFile(string InFile, string OutFile){
}
/*Takes supplied file names and decodes the InFile, placing the result in OutFile. Also
checks to make sure InitializeFromFile ran properly. Prints in/out byte counts.*/
void BinaryTree::DecodeFile(string InFile, string OutFile){
}
int main(array<System::String ^> ^args){
BinaryTree BT;
BT.InitializeFromFile(filename);
return 0;
}
donc mon bytesRead var = environ 5 mil octets, mais le poids de ma racine est = à 0 à la fin de tout ce code .Après avoir construit mon arbre de Huffman poids de la racine est 700k quand je l'ai lu 5megs de données
Si vous ne pouvez pas le comprendre (je vais passer au moins une heure de plus à chercher le bug avant de me coucher) pourriez-vous me donner quelques conseils pour améliorer l'efficacité?
Modifier: Le problème était if(freq[i]<min1). Tout d'abord, il faut laisser la comparaison de poids [i] -> à min1 parce que c'est le tableau que je manipule pour créer l'arbre (freq [] a juste les poids, pas les pointeurs de treenode). Donc, pour le fixer, je fis cette ligne et l'instruction if après: if(leaves[i] && leaves[i]->weight<=min1) et if(leaves[i] && (leaves[i]->weight)<=min2 && i!=wheremin1)
Si vous avez d'autres suggestions pour le nettoyage de mon code, (plus de commentaires dans certains endroits, différentes façons de comparer, etc.). veuillez suggérer. Je ne suis pas un excellent codeur, mais j'aimerais être et j'essaie de travailler pour avoir du bon code.
Édition2: J'ai posté le nouveau/code fixe. Le poids de ma racine est maintenant égal à bytesread. Je suis toujours ouvert aux suggestions pour nettoyer ce code.
Je travaille littéralement exactement la même chose pour l'école. Comment gérez-vous les cas où le poids est 0? Vous devriez pouvoir ignorer 0 valeurs lors de la construction de l'arbre. – Maynza
Je ne fais que les jeter dans l'arbre. Pas trop inquiet pour l'efficacité en ce moment. – Azreal