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_ 谢谢你,我这是要答辩的题目,但不懂这些代码什么意思,能再详细一些吗,再不懂的我可以百度
一年多之前 回复
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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
哈弗曼树与哈弗曼树编码
哈弗曼(Huffman)树,也称最优树,是一类带全路径长度最短的树,在实际中有广泛的应用,也是二叉树的一个具体应用。 在哈夫曼树的定义中,涉及到了路径、路径长度、权等概念,下面先给出概念的定义。 一、概念与定义 路径:从树的一个结点到另一个结点的分支构成这两个结点之间的路径,对于哈夫曼树特指从根节点到某节点的路径。 路径长度:路径上的分支数目叫做路径长度。 树的路径长度:从树根到每一结点
javaOOP编写
自己写的一点代码求解释求更正,不懂的很多希望大家一起探讨探讨
【数据结构】求节点的哈夫曼的带权路径长度
题目来源:北航14级6系数据结构作业 【问题描述】  已知输入一串正整数,正整数之间用空格键分开,请建立一个哈夫曼树,以输入的数字为叶节点,求这棵哈夫曼树的带权路径长度。 【输入形式】  首先输入正整数的个数,然后接下来为接下来的正整数,正整数个数不超过10个 【输出形式】  输出相应的权值 【样例输入】  5 4 5 6 7 8 【样例输出】  69
hafuman的C++求解
哈弗曼树是数据结构的求最优树的方法。需要的可以下载哈。。
1172 哈夫曼树 求最小路径长度
题目描述:  哈夫曼树,第一行输入一个数n,表示叶结点的个数。需要用这些叶结点生成哈夫曼树,根据哈夫曼树的概念,这些结点有权值,即weight,题目需要输出所有结点的值与权值的乘积之和。 输入:  输入有多组数据。  每组第一行输入一个数n,接着输入n个叶节点(叶节点权值不超过100,2 输出:  输出权值。 样例输入: 5   1 2 2 5 9 样例输出: 37 算法实
【树】哈弗曼树和哈弗曼编码
#include #include using namespace std; const int max_size = 50; struct HuffmanNode{ int weight;//weight表示权值数据域 int parent;//par=0表明结点是独立的,par>0为它的双亲下标 int lchild, rchild;//lchild, rchild为左
javabean求解旧错
javabean+jsp问题,求纠错。急/
哈夫曼树相关知识点总结
1.哈夫曼树:给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。 2.哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 3.构造 1.权值最小的两个结点,构造成一棵二叉树,该二叉树的权值为两个结点之和,并把该二叉树看成结点。 2.重复1步骤。 3.哈夫曼编码:字符出现次数等同于权值,是变长
矩估计
:::   矩估计就是  用样本的矩(即期望)去估计随机变量的矩(数学期望)。 故而 矩估计的求法如下: 1.利用给定的概率密度函数或分布函数,列出求总体矩的等式,从而得到,未知参数和总体矩的关系式。 2.则,样本矩与矩估计量(即:未知参数的估计量)同样也满足这样的关系式 3.代入样本矩和矩估计量 4.求出矩估计量 摘要如下: 在实际问题当中
哈弗曼树和哈弗曼编码
最近总有人问我哈夫曼编码的问题,因此博主决定写一篇文章为大家捋一捋。 我们直接通过一个例子来了解一下哈夫曼编码,如下: 已知一个文件中各个字符及其对应的频率如下所示: 字符  a      b     c      d       e       f 频率 45    13   12   16     9        5 若采用哈夫曼编码,则字符序列“face”对应的编码为: 要求得