// 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 =大约5百万个字节，但是在所有这些代码的结尾，我的根的权重= = 0。
如果您不知道该怎么办(我将花至少一个小时的时间在睡前寻找错误)，您能给我一些提高效率的提示吗？
编辑:问题是
if(freq[i]<min1)。首先，它应该是leaves [i]->与min1的权重比较，因为这是我实际上用来创建树的数组(freq []仅具有权重，而不是treenode指针)。因此，要解决此问题，我在该行及其后的if语句中进行了操作:if(leaves[i] && leaves[i]->weight<=min1)和if(leaves[i] && (leaves[i]->weight)<=min2 && i!=wheremin1)如果您有更多清理我的代码的建议(例如，在某些地方有更多注释，不同的比较方式等)，请提出建议。我不是一个优秀的编码人员，但我想成为一名优秀的编码人员，并且正在努力争取编写出良好的代码。
Edit2:我发布了新的/固定的代码。我的根的权重现在等于byteread。我仍然对清理此代码的建议持开放态度。
最佳答案
我几乎找不到:
if(freq[i]<min1){
应该
if(freq[i]<=min1){
正如您不能肯定地说的那样，您所有的频率都将小于INT_MAX。类似地:
if(freq[i]<min2 && i!=wheremin1){
应该:
if(freq[i]<=min2 && i!=wheremin1){
因为
min1和min2也可以相等。一旦开始组合节点，就需要通过更改
leaves数组来删除组合节点并插入组合的新节点。但是您并没有更改freq数组，该数组也需要更改，以使删除的节点的频率不再参与。关于c++ - 构建霍夫曼树后，当我读取5兆数据时，根的权重为700k，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2360771/