2
// 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). 首先它应该是与 min1 的叶子 [i]-> 权重比较,因为这是我实际操作以创建树的数组(freq[] 仅具有权重,而不是树节点指针)。所以为了修复它,我做了那行和它后面的 if 语句:if(leaves[i] && leaves[i]->weight<=min1)if(leaves[i] && (leaves[i]->weight)<=min2 && i!=wheremin1)

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

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

4

3 回答 3

3

我能找到的东西很少:

if(freq[i]<min1){

应该

if(freq[i]<=min1){

正如你不能肯定地说你所有的频率都将小于 INT_MAX。相似地:

if(freq[i]<min2 && i!=wheremin1){

应该:

if(freq[i]<=min2 && i!=wheremin1){

asmin1min2也可以相等。

开始组合节点后,您需要注意删除组合节点并通过更改leaves数组来插入组合的新节点。但是您并没有更改freq阵列,阵列也需要更改,以便已删除节点的频率不再参与。

于 2010-03-02T03:59:07.413 回答
2

一些提示:

1) 编写一个函数“DumpState()”,它产生的输出(到 cout)大致如下所示:

 ============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) 创建一个非常非常简单的输入文件。就像是:

aabc

运行您的程序,并保存日志文件(使用上面的 1 创建)。处理在第一个循环之前、第一个循环中等应该发生的事情。将其与您的日志文件进行比较,了解实际发生情况。您可能还想打印一些其他变量(min1、min2、wheremin1、wheremin2)。

于 2010-03-02T07:11:15.953 回答
1

我还没有解决方案,但很少有评论。这是一段相当长的代码。老实说有点笨拙。我建议将您的代码重构为适当的方法。(很多时候,问题只是在重构时得到了解决!)

例如, BinaryTree::InitializeFromFile() 中的以下行

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

在 BinaryTree 构造函数中可能更合适。此外,BinaryTree 中有以下两个

treenode * root;
treenode * leaves[256]

你能评论一下哪个是做什么用的吗?幻数 256 出现在多个地方。你能有一个适当命名的变量吗?

于 2010-03-02T04:44:33.693 回答