私は私のハフマンツリーを構築した後、私はデータの5megsて読んだとき、根の重量は700Kです

StackOverflow https://stackoverflow.com/questions/2360771

  •  23-09-2019
  •  | 
  •  

質問 

// 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)ました。それは私が実際に（FREQ []はただの重み、ないのTreeNodeポインタを持っている）ツリーを作成するために操作してるの配列だからMIN1へ>重量比較 - 最初に、[i]は葉でなければなりません。 if(leaves[i] && leaves[i]->weight<=min1)とif(leaves[i] && (leaves[i]->weight)<=min2 && i!=wheremin1)

：だから私はそれの後にその行とif文を作った、それを修正するには あなたは私のコードをクリーンアップするためのより多くの提案（すなわち、特定の場所でより多くのコメントが、比較するためのさまざまな方法、など）を持っている場合は、

、提案してください。私は偉大なコーダないんだけど、私はなりたいと私は良いコードを有する方に仕事にしようとしています。

EDIT2：私は新しい/固定コードを掲載しました。私の根の重量は今bytesreadに等しいです。私はまだ、このコードをクリーンアップするために提案を開いている。

役に立ちましたか？

解決

私は見つけることができる少数の事ます：

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配列を、変更されていません。

他のヒント

カップルのヒント：

1）coutに出力する（生成機能 "DumpStateを（）" 書く）おおよそ次のように探しています：

 ============START==================
 freq[0] = <some number>
 freq[1] = <some number>
 ...
 freq[255] = <some number>
 leaves[0] = null
 leaves[1] = { data = 'B', weight = 3 }
 ...
 leaves[255] = null
 ============= END ================

2回の反復などの後に、一回の反復の後、あなたのメインループの前に、この機能を入れています。

2）本当に、本当に簡単です入力ファイルを作成します。ような何かます：

aabc

あなたのプログラムを実行し、（上記1で作成した）ログファイルを保存します。 がが起こっは、実際にのあるものの、あなたのログファイルとその比較など、最初のループでは、最初のループの前に起こっすべきかを介して動作。あなたが（MIN1、MIN2、wheremin1、wheremin2）あまりにもいくつかの他の変数を印刷したい場合があります。

私はまだ解決策を持っていますが、いくつかのコメントがありません。これは、コードのかなり長い作品です。そして、正直少しの不器用されるように。私は、適切なメソッドにコードをリファクタリングすることをお勧め。 （多くの場合、問題リファクタリングしながら、ちょうど解決しましょう！）

例えば、BinaryTree :: InitializeFromFile（）の次の行

for(int i=0;i<256;i++){
    freq[i]=0;
    leaves[i] = new treenode;
}

BinaryTreeコンストラクタにおいてより適切であるかもしれません。また、以下の両方がBinaryTreeである

treenode * root;
treenode * leaves[256]
あなたは1つが何のためにある

をコメントすることができますか？マジック番号は256である複数の場所に存在しています。あなたはそのための適切な名前の変数を持つことができますか？

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top