2 deadwood Deadwood_ 于 2017.01.01 20:55 提问

哈弗曼树的问题,代码如下,求详细解释。答辩需要,但我一点也不懂,急求

int Count(int cou[]) //计算输入的字母的个数
{
char word;
char letter[27]={' ','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o', 'p','q','r','s','t','u','v','w','x','y','z'};
fstream SourceFile;
SourceFile.open("SourceFile.txt",ios::in); //从SourceFile.txt读取
if (!SourceFile)
{
cout<<"Can't open this file"<<endl;
}
while (!SourceFile.eof())//循环直到文件结束

    {
        SourceFile.get(word);
        if (word>='A'&&word<='Z')//如果是大写字母,统一转换为小写
        {
            word=word+32;//32是 'a' - 'A' ascii差
        }
        int i=word-96;// 96是'a'的ascii
        cou[i]++; // cou保存你对应字母的统计数字,+1
    }
    SourceFile.close();//关闭文件
    cout<<"letter"<<'\t'<<'\t'<<"频率为"<<endl;//输出
        for (int j=1;j<=26;j++)//依次输出a~z字符的出现频率
        {
            if (cou[j]!=0)//如果没有这个字母出现,就不输出
            {
                cout<<letter[j]<<'\t'<<'\t'<<cou[j]<<endl; //letter[j]可以用 (char)('A' + i) 代替
            }
        }
        cout<<"读入完事儿!"<<endl;

return 0;

}

/*-----------选择HT中双亲域为0的权值最小的两个结点--------------*/
void Select(HuffmanTree HT,int i,int &s1,int &s2) //自定义函数
{
//选择两个最小值,将他们的位序输出到s1,s2
int m=0,k=0;

for(k=1;k<=n;++k)            //得到第一个父节点为零的节点,++k先自加,再运算
{
    if(0==HT[k].parent)
    {
        m=HT[k].weight;
        s1=k;
        break;
    }
}

for(;k<=n;++k)                    //得到最小值
{
    if(0==HT[k].parent && HT[k].weight<m)    //权<m
    {
        m=HT[k].weight;
        s1=k;
    }
}

for(k=1;k<=n;++k)                //得到第二个父节点为零的节点
{
    if(k!=s1 && 0==HT[k].parent)
    {
        m=HT[k].weight;
        s2=k;
        break;
    }
}

for(;k<=n;++k)                    //求得次小元
{
    if(0==HT[k].parent && k!=s1 && HT[k].weight<m)
    {
        m=HT[k].weight;
        s2=k;
    }
}

}//Select

/*---------算法5.10 根据统计结果建立Huffman树-----------*/
void CreatHuffmanTree(HuffmanTree &HT,int cou[])
{ if(n<=1) return;
int m=2*n-1;
HT=new HTNode[m+1]; //0 号单元未用,所以需要动态分配m+1个单元,HT[m]表示根节点
int s1=0,s2=0; //

for(int i=1;i<=m;i++)           //初始化HuffmanTree 将1~m单元中的双亲,左右孩子的下标初始化为0
{
    HT[i].lchild=0;
    HT[i].rchild=0;
    HT[i].parent=0;
}

for(i=1;i<=n;i++)               //输入叶节点的权值
    HT[i].weight=cou[i-1];      
for(i=n+1;i<=m;i++)             
{
    Select(HT,i,s1,s2);         //选择HT中两个双亲域为0且权值最小的两个节点的序号s1和s2
    HT[s1].parent=i;    HT[s2].parent=i;       //标记其双亲结点为HT[i]
    HT[i].lchild=s1;    HT[i].rchild=s2;       //HT[s1]和HT[s2]作为HT[i]的左右孩子
    HT[i].weight=HT[s1].weight+HT[s2].weight;   //HT[i]的权值为左右孩子权值之和
}
cout<<"huffmantree构造完成"<<endl;

}

/*--------------------算法5.11 根据统计结果对各字符进行编码,并保存在Code.txt中------------------*/
void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC)
{ int start;
char cd;
HC=new char
[n+1];
cd=new char[n];
cd[n-1]='\0';
int i,c,f;
for (i=1;i<=n;++i)
{
start=n-1;
c=i;f=HT[i].parent;
while(f!=0){
--start;
if (HT[f].lchild==c)
cd[start]='0';
else cd[start]='1';
c=f;
f=HT[f].parent;
}
HC[i]=new char[n-start];
strcpy(HC[i],&cd[start]);
}
delete cd;
cout<<"HuffmanCode创建完毕"<<endl;
}

/*----------对SourceFile.txt进行编码,并保存在ResultFile.txt中-----------*/
void Code(HuffmanTree &HT,HuffmanCode &HC)
{
string alph;
ifstream infile("SourceFile.txt");
if(!infile){
cout<<"Cannot open this file!"< exit(1);
}
infile>>alph;
infile.close();
ofstream outfile;
outfile.open("ResultFile.txt");
if(!outfile)
cout<<"cannot open the file!"<<endl;
else{
for(int i=0;i<alph.length();i++){
int j=alph[i]-97;
for(int k=1;k<=n;k++){
if(HT[k].weight==cou[j])
outfile<<HC[k];
}
}
}
cout<<"huffman编码完成"<<endl;
outfile.close();
}

2个回答

caozhy
caozhy   Ds   Rxr 2017.01.01 20:57

之前的问题如果满意,请先采纳。然后帮你看剩余的部分。

Deadwood_
Deadwood_ 谢谢你,我这是要答辩的题目,但不懂这些代码什么意思,能再详细一些吗,再不懂的我可以百度
12 个月之前 回复
caozhy
caozhy   Ds   Rxr 2017.01.02 21:25
 /*--------------------算法5.11 根据统计结果对各字符进行编码,并保存在Code.txt中------------------*/
void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC)
{ int start;
char cd;
HC=new char[n+1]; //生成长度为n+1个字符的哈夫曼编码表
cd=new char[n]; //这里写错了吧,是char * cd
cd[n-1]='\0'; //最后一个字符设置为\0,也就是字符串结束
int i,c,f;
for (i=1;i<=n;++i) //遍历整个哈夫曼编码表
{
start=n-1;
c=i;f=HT[i].parent; //子节点的值等于它父节点的值的和
while(f!=0){
--start;
if (HT[f].lchild==c) //如果左子节点没有
cd[start]='0'; //添加前缀码
else cd[start]='1'; 。。输出1
c=f;
f=HT[f].parent; .//获取上一层节点
}
HC[i]=new char[n-start]; //构造哈夫曼编码
strcpy(HC[i],&cd[start]); //复制到参数中作为结果输出
}
delete cd;
cout<<"HuffmanCode创建完毕"<<endl;
}
/*----------对SourceFile.txt进行编码,并保存在ResultFile.txt中-----------*/
void Code(HuffmanTree &HT,HuffmanCode &HC)
{
string alph; //子母表
ifstream infile("SourceFile.txt"); //读取文件
if(!infile){
cout<<"Cannot open this file!"< exit(1);
}
infile>>alph;
infile.close();
ofstream outfile;
outfile.open("ResultFile.txt");
if(!outfile)
cout<<"cannot open the file!"<<endl;
else{
for(int i=0;i<alph.length();i++){
int j=alph[i]-97; //当前字符下标
for(int k=1;k<=n;k++){
if(HT[k].weight==cou[j]) //设置哈夫曼树的权重
outfile<<HC[k]; //输出到文件
}
}
}
cout<<"huffman编码完成"<<endl;
outfile.close();
}
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!