c++ - 在我构建我的霍夫曼树之后，当我阅读了 5 兆数据时，根的权重为 700k

Question

// 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 = 大约 500 万字节，但到所有这些代码结束时，我的根的权重 = 为 0。

如果你想不通(我将在睡前至少再花一个小时寻找错误)你能给我一些提高效率的提示吗？

编辑:问题是 if(freq[i]<min1) .首先，它应该是 leaves[i]->weight 与 min1 的比较，因为这是我实际上正在操纵以创建树的数组(freq[] 仅具有权重，而不是树节点指针)。所以为了修复它，我做了那一行和它后面的 if 语句:if(leaves[i] && leaves[i]->weight<=min1)和 if(leaves[i] && (leaves[i]->weight)<=min2 && i!=wheremin1)

如果您有更多关于清理我的代码的建议(即在某些地方增加评论，不同的比较方式等)，请提出。我不是一个伟大的编码员，但我想成为并且我正在努力编写好的代码。

Edit2:我发布了新的/固定的代码。我的根的权重现在等于 bytesread。我仍然愿意接受清理此代码的建议。

Answer 1

我能找到的东西很少:

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 数组，它也需要更改，以便删除的节点的频率不会再次参与。