哈夫曼树译码的算法思路,语言描述即可
发布网友
发布时间：2022-04-27 00:32
共3个回答
热心网友
时间：2022-06-21 18:28
你讲的是实现时的语言注释，还是他的实现过程追问实现过程
追答假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为： (1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)； (2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； (3)从森林中删除选取的两棵树，并将新树加入森林； (4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树
参考资料：http://ke.baidu.com/view/127820.html?wtp=tt
热心网友
时间：2022-06-21 18:29
程序先给你，语言描述我找找看：
C++的
#include<stdlib.h>
#include<fstream.h>
#include<iomanip.h>
#include<windows.h>
ofstream outstuf;
#define MAXBIT 50 // 哈夫曼编码的最大长度
#define MAXVALUE 50 // 最大权值
#define MAXLEAF 50 // 哈夫曼树中叶子结点个数
#define MAXNODE MAXLEAF*2-1 //树中结点总数
//哈夫曼树结点结构
typedef struct
{
char data ; //结点值
int weight; //权值
int parent; //双亲结点
int lchild; //左孩子结点
int rchild; //右孩子结点
}HNodeType;
HNodeType HuffNode[MAXNODE];
//存放哈夫曼编码的数据元素结构
typedef struct
{
int bit [MAXBIT]; //存放哈夫曼码
int start; //编码的起始下标
}HCodeType;
void Haffmanfile(int n); //保存文件
HNodeType *HaffmanTree(int n) ; //构造哈夫曼树
void Haffmancode(int n); //构造哈夫曼编码
HNodeType *HaffmanTree(int n) //构造哈夫曼树
{
int i,j,m1,m2,x1,x2;
for(i=0;i<2*n-1;i++) //所有结点的初始化
{
HuffNode[i].weight=0;
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
}
cout<<"\t________________________________________"<<endl;
cout<<"\t输入叶子结点的值和权值"<<endl;
cout<<"\t________________________________________"<<endl;
for(i=0;i<n;i++)
{
cout<<"\t______________________"<<endl;
cout<<"\t输入第"<<i+1<<"个叶子节点的值: ";
cin>>HuffNode[i].data;
cout<<"\t输入第"<<i+1<<"个叶子节点的权值: ";
cin>>HuffNode[i].weight;
}
for(i=0;i<n-1;i++) //构造哈夫曼树
{ m1=m2=MAXVALUE; x1=x2=0;
for(j=0;j<n+i;j++)
{
if(HuffNode[j].parent==-1&&HuffNode[j].weight<m1) //只在尚未构造二叉树的结点中查找
{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
else if(HuffNode[j].parent==-1&&HuffNode[j].weight<m2)
{
m2=HuffNode[j].weight;
x2=j;
}
}
//将找出的两棵权值最小的子树合并为一棵子树
HuffNode[x1].parent=n+i;
HuffNode[x2].parent=n+i;
HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
HuffNode[n+i].lchild=x1;
HuffNode[n+i].rchild=x2;
}
return HuffNode;
}
//构造哈夫曼编码
void Haffmancode(int n)
{
int i,j,c,p;
HNodeType *HuffNode=new HNodeType[MAXNODE];
HCodeType *HuffCode=new HCodeType[MAXLEAF];
HCodeType *cd=new HCodeType;
HuffNode=HaffmanTree(n); //建立哈夫曼树
for(i=0;i<n;i++)
{
cd->start=n-1;
c=i;
p=HuffNode[c].parent;
while(p!=-1) //循环直到树根结点
{
if(HuffNode[p].lchild==c)
cd->bit[cd->start]=0; //处理左孩子结点
else
cd->bit[cd->start]=1; //处理右孩子结点
cd->start--;
c=p;
p=HuffNode[c].parent;
}
for(j=cd->start+1;j<n;j++)
HuffCode[i].bit[j]=cd->bit[j];
HuffCode[i].start=cd->start; //指向哈夫曼编码最开始字符
}
cout<<"\n\t每个叶子结点的值及对应的哈夫曼编码"<<endl;
for(i=0;i<n;i++)
{ cout<<"\t****************************************"<<endl;
cout<<"\t第"<<i+1<<"个叶子结点的值和哈夫曼编码为:";
cout<<HuffNode[i].data<<" ";
for(j=HuffCode[i].start+1;j<n;j++)
cout<<HuffCode[i].bit[j];
cout<<endl;
}
outstuf.open("bianma.txt",ios::out);
outstuf<<"____________\n哈夫曼编码:\n____________ "<<endl;
for(i=0;i<n;i++)
{
for(j=HuffCode[i].start+1;j<n;j++)
outstuf<<HuffCode[i].bit[j]<<" ";
outstuf<<endl;
}
cout<<"\t\t*******************"<<endl;
cout<<"\t\t哈夫曼编码保存成功!"<<endl;
cout<<"\t\t*******************"<<endl;
outstuf.close();
Haffmanfile(n);
}
void Haffmanfile(int n)
{
char s[80];
int a[20],i=0,r;
ifstream instuf("bianma.txt",ios::in);
if(!instuf)
{
cout<<"文件不能打开!"<<endl;
abort();
}
instuf.getline(s,80);
while(instuf>>a[i])
i++;
for(r=0;r<i;r++) cout<<a[r]<<" ";
if(a[0]!=0&&a[0]!=1)
{
cout<<"此文件无内容!"<<endl;
abort();
}
instuf.close();
int p=0,j=0,k=0; char zu[10],ch;
system("pause");system("cls");
cout<<"\n\t\t*************************************"<<endl;
cout<<"\t\t是否要对原编码进行译码操作 (Y or N)?:\t";
cin>>ch;
if(ch=='N'||ch=='n') return;
for(r=0;r<n;r++)
{
p=2*n-2;
while(HuffNode[p].lchild!=-1&&HuffNode[p].rchild!=-1)
{
if(a[j]==0) p=HuffNode[p].lchild;
if(a[j]==1) p=HuffNode[p].rchild;
j++;
}
zu[k]=HuffNode[p].data;
k++;
}
outstuf.open("yima.txt",ios::out);
outstuf<<"译码为: "<<endl;
for(j=0;j<n;j++) outstuf<<HuffNode[j].data<<" ";
outstuf<<endl;
cout<<"\t\t**************\n\t\t译码保存成功!\n\t\t**************"<<endl;
outstuf.close();
instuf.open("yima.txt",ios::in);
if(!instuf)
{
cout<<"文件不能打开!"<<endl;
abort();
}
instuf.getline(s,80);
i=0;
cout<<"\n\t\t哈夫曼编码的译码为: ";
while(instuf>>zu[i])
{cout<<zu[i]<<" ";
i++;
}
cout<<endl;
instuf.close();
}
void main()
{
int n,i;char choice;system("cls");system("color 80");
cout<<"\t _______________________________________________________"<<endl;
cout<<"\t 本演示系统可以良好的演示哈夫曼编码和译码的产生,"<<endl;
cout<<"\t 但本程序有一定的不完善，用户可以随时到CSDN社区关注更新!"<<endl;
cout<<"\t _______________________________________________________"<<endl;
loop:
cout<<"\t\t _________________________________\n\n";
cout<<"\t\t 1.哈夫曼演示系统 0.退出演示系统\n";
cout<<"\t\t _________________________________\n\n\t请选择\t";
cin>>choice;
switch(choice)
{case '1': system("cls");
cout<<"\t\t _____________________________\n\n";
cout<<"\t\t\t请输入叶子结点个数:\t";
cin>>n;
Haffmancode(n);
cout<<"\n\t*********输出哈夫曼树!**********"<<endl;
cout<<"\t字符 "<<"权值 "<<"左孩子指针 "<<"右孩子指针"<<endl;
for( i=0;i<2*n-1;i++)
{cout<<"\t";
cout<<setw(5)<<HuffNode[i].data<<setw(5)<<HuffNode[i].weight<<setw(5)<<
HuffNode[i].lchild<<setw(5)<<HuffNode[i].rchild<<setw(5)<<
HuffNode[i].parent<<endl;
}
system("pause");system("cls");goto loop;break;
case '0':break;
}
}
热心网友
时间：2022-06-21 18:29
等一下给你
