中科新闻网工厂厨师招聘:悬赏50！关于Huffman编码树！在线等！
来源：百度文库 编辑：中科新闻网 时间：2024/04/20 15:59:10
通过编程序计算，给出编码表
通过编程序和手工计算两种方式，得到压缩编码后得到的二进制比特序列
计算平均码字长度，与未经压缩的ASCII比较，说明压缩的效果
上面这是题目，有回的吗？在考试阿，快交卷了。快啊！！！
题目中给的文件如下：
Could you drop me off at the airport?
是个文本文件。
兄弟考试过了吗？ 我希望答案是肯定的。
如果现在还是不懂的话，希望看一下这个程序。
//本程序根据26个英文字母出现的频度，得到了它们的一种哈夫曼编码方案
//by jirgal 2005.4.18
#include<iostream.h>
#include<iomanip.h>
#define NUM 26 //字母数
#define TNUM 51 //
#define LTH 15 //编码最大长度
class Node
{
public:
char data;
int weight;
int parent;
int lchild;
int rchild;
};
void main()
{
char ch[NUM]={'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'};//26个字母
int weit[NUM]={856,139,279,378,1304,289,199,528,627,13,42,
339,249,707,797,199,12,677,607,1045,249,92,149,17,199,8};//出现频率
Node nodes[TNUM]; //用对象数组存储哈夫曼树
int i,j,one,two,a,b;
int hc[NUM][LTH]; //用于存储编码
int m,n;
//初始化数组
for(i=0;i<NUM;i++)
{
nodes[i].data=ch[i];
nodes[i].weight=weit[i];
nodes[i].parent=-1;
nodes[i].lchild=-1;
nodes[i].rchild=-1;
}
for(i=NUM;i<TNUM;i++)
{
nodes[i].data='@';
nodes[i].weight=-1;
nodes[i].parent=-1;
nodes[i].lchild=-1;
nodes[i].rchild=-1;
}
//建立哈夫曼树
for(i=NUM;i<TNUM;i++)
{
a=b=-1;
one=two=10000; //最大权数
for(j=0;j<i;j++)
{
if(nodes[j].parent==-1)
{
if(nodes[j].weight<=two)
{
one=two;
two=nodes[j].weight;
a=b;
b=j;
}
else if(nodes[j].weight>two&&nodes[j].weight<=one)
{
one=nodes[j].weight;
a=j;
}
}
}//for语句得到 parent=-1(即尚没有父结点)且weight最小的两个结点
nodes[a].parent=i;
nodes[b].parent=i;
nodes[i].lchild=a;
nodes[i].rchild=b;
nodes[i].weight=nodes[a].weight+nodes[b].weight;
}
//初始化hc
for(i=0;i<LTH;i++)
{
for(j=0;j<NUM;j++)
{
hc[j][i]=7;
}
}
//编码
for(i=0;i<NUM;i++)
{
j=LTH-1;
for(m=i,n=nodes[i].parent;m!=-1;m=n,n=nodes[n].parent)
{
if(nodes[n].lchild==m)
{
hc[i][j]=0;
}
else
{
hc[i][j]=1;
}
j--;
}
}
//输出 nodes
cout<<"HuffmanTree:"<<endl;
cout<<setw(4)<<"NO."<<setw(6)<<"data"<<setw(8)<<"weight"<<setw(6)
<<"parnt"<<setw(6)<<"lchd"<<setw(6)<<"rchd"<<endl;
for(i=0;i<TNUM;i++)
{
cout<<setw(4)<<i<<setw(6)<<nodes[i].data<<setw(8)<<nodes[i].weight<<setw(6)
<<nodes[i].parent<<setw(6)<<nodes[i].lchild<<setw(6)<<nodes[i].rchild<<endl;
}
//输出编码
cout<<endl<<"Result:"<<endl;
cout<<setw(6)<<"char"<<setw(10)<<"frequency"<<setw(16)<<"huffmancode\n";
for(i=0;i<NUM;i++)
{
cout<<setw(6)<<ch[i]<<setw(8)<<weit[i];
cout<<" ";
for(j=0;j<LTH;j++)
{
if(hc[i][j]!=7)
{
cout<<hc[i][j];
}
}
cout<<endl;
}
cout<<"\nDone.\n"<<endl;
}
//本程序根据26个英文字母出现的频度，得到了它们的一种哈夫曼编码方案
//by jirgal 2005.4.18
#include<iostream.h>
#include<iomanip.h>
#define NUM 26 //字母数
#define TNUM 51 //
#define LTH 15 //编码最大长度
class Node
{
public:
char data;
int weight;
int parent;
int lchild;
int rchild;
};
void main()
{
char ch[NUM]={'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'};//26个字母
int weit[NUM]={856,139,279,378,1304,289,199,528,627,13,42,
339,249,707,797,199,12,677,607,1045,249,92,149,17,199,8};//出现频率
Node nodes[TNUM]; //用对象数组存储哈夫曼树
int i,j,one,two,a,b;
int hc[NUM][LTH]; //用于存储编码
int m,n;
//初始化数组
for(i=0;i<NUM;i++)
{
nodes[i].data=ch[i];
nodes[i].weight=weit[i];
nodes[i].parent=-1;
nodes[i].lchild=-1;
nodes[i].rchild=-1;
}
for(i=NUM;i<TNUM;i++)
{
nodes[i].data='@';
nodes[i].weight=-1;
nodes[i].parent=-1;
nodes[i].lchild=-1;
nodes[i].rchild=-1;
}
//建立哈夫曼树
for(i=NUM;i<TNUM;i++)
{
a=b=-1;
one=two=10000; //最大权数
for(j=0;j<i;j++)
{
if(nodes[j].parent==-1)
{
if(nodes[j].weight<=two)
{
one=two;
two=nodes[j].weight;
a=b;
b=j;
}
else if(nodes[j].weight>two&&nodes[j].weight<=one)
{
one=nodes[j].weight;
a=j;
}
}
}//for语句得到 parent=-1(即尚没有父结点)且weight最小的两个结点
nodes[a].parent=i;
nodes[b].parent=i;
nodes[i].lchild=a;
nodes[i].rchild=b;
nodes[i].weight=nodes[a].weight+nodes[b].weight;
}
//初始化hc
for(i=0;i<LTH;i++)
{
for(j=0;j<NUM;j++)
{
hc[j][i]=7;
}
}
//编码
for(i=0;i<NUM;i++)
{
j=LTH-1;
for(m=i,n=nodes[i].parent;m!=-1;m=n,n=nodes[n].parent)
{
if(nodes[n].lchild==m)
{
hc[i][j]=0;
}
else
{
hc[i][j]=1;
}
j--;
}
}
//输出 nodes
cout<<"HuffmanTree:"<<endl;
cout<<setw(4)<<"NO."<<setw(6)<<"data"<<setw(8)<<"weight"<<setw(6)
<<"parnt"<<setw(6)<<"lchd"<<setw(6)<<"rchd"<<endl;
for(i=0;i<TNUM;i++)
{
cout<<setw(4)<<i<<setw(6)<<nodes[i].data<<setw(8)<<nodes[i].weight<<setw(6)
<<nodes[i].parent<<setw(6)<<nodes[i].lchild<<setw(6)<<nodes[i].rchild<<endl;
}
//输出编码
cout<<endl<<"Result:"<<endl;
cout<<setw(6)<<"char"<<setw(10)<<"frequency"<<setw(16)<<"huffmancode\n";
for(i=0;i<NUM;i++)
{
cout<<setw(6)<<ch[i]<<setw(8)<<weit[i];
cout<<" ";
for(j=0;j<LTH;j++)
{
if(hc[i][j]!=7)
{
cout<<hc[i][j];
}
}
cout<<endl;
}
cout<<"\nDone.\n"<<endl;
很理解你的心情,顶,安慰以下,呵呵
I'm so sorry I didn't see it on time to save you:)
But Huffman Code is not so hard,isn't it?