// 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;
}
したがって、私の bytesread var = 約 5mil バイトですが、ルートの重みは、このすべてのコードの終わりまでに = 0 になります。
わからない場合は (就寝前にバグを探すのに少なくとももう 1 時間は費やすことになります)、効率を改善するためのヒントを教えていただけますか?
編集：問題はif(freq[i]<min1). まず、leas[i]-> min1 との重みの比較である必要があります。これは、ツリーを作成するために実際に操作している配列だからです (freq[] は、ツリーノード ポインターではなく、重みだけを持っています)。それを修正するために、その行とその後に if ステートメントを作成しましたif(leaves[i] && leaves[i]->weight<=min1)。if(leaves[i] && (leaves[i]->weight)<=min2 && i!=wheremin1)
コードをクリーンアップするための提案が他にもある場合 (つまり、特定の場所にコメントを追加する、比較するさまざまな方法など)、提案してください。私は優れたコーダーではありませんが、そうなりたいと思っており、優れたコードを作成できるように努力しています。
Edit2: 新しい/修正されたコードを投稿しました。私のルートの重みはバイトリードに等しくなりました。このコードをクリーンアップするための提案はまだ受け付けています。