正文
哈夫曼算法java代码,求哈夫曼编码的算法
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
我需要一个程序设计的代码：设计一个利用哈夫曼算法的编码和译码系统
我的这个能实现编码与译码；
//huffman.h
const int Lengh=1000;
char coding[100]; //存储二进制字符串
int n; //定义全局变量
enum Child{none,lchild,rchild}; //采用枚举标记事左孩子还是右孩子
struct element
{
char letter,*code;
int weight; //权值域
int parent;
Child a;
};
void Select(element h[],int k,int *a,int *b);
void InitHuffmanTree(element huffTree[],char t[],int w[]) //哈夫曼树的初始化
{
int i,m=2*n-1,s1,s2;
for(i=0;in;i++) //初始前n个结点
{
huffTree[i].code='\0';
huffTree[i].parent=-1;
huffTree[i].a=none;
huffTree[i].letter=t[i];
huffTree[i].weight=w[i];
}
for(;i=m;i++) //后m-n个结点置空
{
huffTree[i].code='\0';
huffTree[i].letter=' ';
huffTree[i].parent=-1;
huffTree[i].a=none;
huffTree[i].weight=0;
}
for(i=n;im;i++) //建立哈夫曼树
{
Select(huffTree,i-1,s1,s2); //在huffTree中找权值最小的两个结点s1,s2
huffTree[s1].parent=i; //将s1,s2合并，则s1,s2的双亲是k
huffTree[s2].parent=i;
huffTree[s1].a=lchild;
huffTree[s2].a=rchild;
huffTree[i].weight=huffTree[s1].weight+huffTree[s2].weight;
}
}
void Select(element h[],int k,int *a,int *b) //寻找最小和次小节点的序号
{
int i;
int min1=1000;
int min2=1000;
for (i=0;i=k;i++)//找最小的结点序号
{
if (h[i].parent==-1h[i].weightmin1)
{
*a=i;
min1=h[i].weight;
}
}
for(i=0;i=k;i++)//找次小结点的序号
{
if(h[i].parent==-1(*a!=i)h[i].weightmin2)
{
*b=i;
min2=h[i].weight;
}
}
}
void HuffmanTreeCode(element HT[]) //单个字符编码
{
int i;
char *temp;
temp=(char *)malloc(n*sizeof(char)); //分配n个字符空间
temp[n-1]='\0';
int p;
int s;
for(i=0;in;i++)
{
p=i;
s=n-1;
while(HT[p].parent!=-1)//从结点回溯,左孩子为0,右孩子为1
{
if(HT[p].a==lchild)
temp[--s]='0';
else if(HT[p].a==rchild)
temp[--s]='1';
p=HT[p].parent;
}
HT[i].code=(char *)malloc((n-s)*sizeof(char));//分配结点码长度的内存空间
strcpy(HT[i].code,temp+s);
printf("%c",HT[i].letter);
printf(":"); printf(" ");
printf("%s\n",HT[i].code);
}
}
void HuffmanTreeYima(element huff[],char cod[],int b) //译码
{
char sen[100];
char temp[50];
char voidstr[]=" ";
int t=0; int s=0;
for(int i=0 ; ib; i++)
{
temp[t++]=cod[i];
temp[t] = '\0';
for(int j=0;jn;j++)
{
if (!strcmp(huff[j].code,temp)) //代码段吻合
{
sen[s]=huff[j].letter;
s++;
strcpy(temp,voidstr); //将TEMP置空
t=0;
break;
}
}
}
sen[s]='\0';
cout"译码为:"endl;
coutsenendl;
}
//h.cpp
#include iostream.h
#include string.h
#include malloc.h
#include stdio.h
#include "huffman.h"
void main()
{
element h[Lengh];
char c,a[Lengh],p;
int i,b[Lengh];
int symbol=1;
cout"!!!!欢迎来到哈夫曼编码与译码!!!!"endl;
cout"编码："endl;
cout"请输入要编码字符的个数：";
cinn;
for(i=0;in;i++)
{
cin.get();//跳过输入流中的一个字符(即获取上次输入的回车键)
cout"字符："; cin.get(c); a[i]=c;
cout"权值："; cinb[i];
}
InitHuffmanTree(h,a,b); //哈夫曼树的初始化
HuffmanTreeCode(h); //编码
cout"译码："endl;
cout"请输入要译码的二进制字符串,输入'#'结束：";
int k=0;
while(symbol)
{
cinp; coding[k]=p;
if(p=='#') symbol=0;
k++;
}
HuffmanTreeYima(h,coding,k-1); //进行译码
}
相关问答
Q1: 哈夫曼编码码长怎么算
设某信源产生有五种符号u1、u2、u3、u4和u5，对应概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。
霍夫曼编码是变长编码，思路：对概率大的编的码字短，概率小的编的码字长，这样一来所编的总码长就小，这样编码效率就高。上面那样求是不对的，除非你这6个码字是等概率的，各占1/6。应该用对应的概率*其对应得码长，再求和。
实际应用中
除采用定时清洗以消除误差扩散和采用缓冲存储以解决速率匹配以外，主要问题是解决小符号集合的统计匹配，例如黑（1）、白（0）传真信源的统计匹配，采用0和1不同长度游程组成扩大的符号集合信源。游程，指相同码元的长度（如二进码中连续的一串0或一串1的长度或个数）。
按照CCITT标准，需要统计2×1728种游程（长度），这样，实现时的存储量太大。事实上长游程的概率很小，故CCITT还规定：若l表示游程长度，则l=64q+r。
Q2: 设计程序以实现构造哈夫曼算法，并计算出所构造的哈夫曼树的带权路径长度
// c1.h (程序名)
#includestring.h
#includectype.h
#includemalloc.h // malloc()等
#includelimits.h // INT_MAX等
#includestdio.h // EOF(=^Z或F6),NULL
#includestdlib.h // atoi()
#includeio.h // eof()
#includemath.h // floor(),ceil(),abs()
#includeprocess.h // exit()
#includeiostream.h // cout,cin // 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
// #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE
// c6-7.h 赫夫曼树和赫夫曼编码的存储表示
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
char data;
}HTNode,*HuffmanTree; // 动态分配数组存储赫夫曼树 typedef char **HuffmanCode; // 动态分配数组存储赫夫曼编码表
#include "..\c1.h"
#include "c6-7.h" int min(HuffmanTree t, int i)
{ // 返回i个结点中权值最小的树的根结点序号，函数select()调用
int j,flag;
unsigned int k=UINT_MAX; // 取k为不小于可能的值(无符号整型最大值)
for(j=1;j=i;j++)
if(t[j].weightk t[j].parent==0) // t[j]是树的根结点
k=t[j].weight,flag=j;
t[flag].parent=1; // 给选中的根结点的双亲赋1，避免第2次查找该结点
return flag;
} void select(HuffmanTree t,int i,int s1, int s2)
{ // 在i个结点中选择2个权值最小的树的根结点序号，s1为其中序号小的那个
int j;
s1=min(t,i);
s2=min(t,i);
if(s1s2)
{
j=s1;
s1=s2;
s2=j;
}
}
// HuffmanCoding1求赫夫曼编码。实现算法6.12的程序
void HuffmanCoding1(HuffmanTree HT,HuffmanCode HC,int *w,int n) // 算法6.12
{ // w存放n个字符的权值(均0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC
int m,i,s1,s2,start;
unsigned c,f;
HuffmanTree p;
char *cd;
if(n=1)
return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用
for(p=HT+1,i=1;i=n;++i,++p,++w)
{
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
} //2. 生成HT数组的前n个元素
for(;i=m;++i,++p)
(*p).parent=0; //3. 将n+1到2n-1个元素的parent初始化为0
for(i=n+1;i=m;++i) // 建赫夫曼树
{ // 在HT[1～i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2
select(HT,i-1,s1,s2);
HT[s1].parent=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
} //4. 建立n+1到2n-1个元素
// 从叶子到根逆向求每个字符的赫夫曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
// 分配n个字符编码的头指针向量([0]不用)
cd=(char*)malloc(n*sizeof(char)); // 分配求编码的工作空间
cd[n-1]='\0'; // 编码结束符
for(i=1;i=n;i++)
{ // 逐个字符求赫夫曼编码
start=n-1; // 编码结束符位置
for(c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent)
// 从叶子到根逆向求编码
if(HT[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
HC[i]=(char*)malloc((n-start)*sizeof(char));
// 为第i个字符编码分配空间
strcpy(HC[i],cd); // 从cd复制编码(串)到HC
}
free(cd); // 释放工作空间
}
// 实现算法6.13的程序
void HuffmanCoding2(HuffmanTree HT,HuffmanCode HC,int *w,int n) // 前半部分为算法6.12
{ // w存放n个字符的权值(均0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC
int m,i,s1,s2; // 此句与algo6-1.cpp不同
unsigned c,cdlen; // 此句与algo6-1.cpp不同
HuffmanTree p;
char *cd;
if(n=1)
return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 0号单元未用
for(p=HT+1,i=1;i=n;++i,++p,++w)
{
(*p).weight=*w;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(;i=m;++i,++p)
(*p).parent=0;
for(i=n+1;i=m;++i) // 建赫夫曼树
{ // 在HT[1～i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2
select(HT,i-1,s1,s2);
HT[s1].parent=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
// 以下为算法6.13，无栈非递归遍历赫夫曼树，求赫夫曼编码，以上同算法6.12
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
// 分配n个字符编码的头指针向量([0]不用)
cd=(char*)malloc(n*sizeof(char)); // 分配求编码的工作空间
c=m;
cdlen=0;
for(i=1;i=m;++i)
HT[i].weight=0; // 遍历赫夫曼树时用作结点状态标志
while(c)
{
if(HT[c].weight==0)
{ // 向左
HT[c].weight=1;
if(HT[c].lchild!=0)
{
c=HT[c].lchild;
cd[cdlen++]='0';
}
else if(HT[c].rchild==0)
{ // 登记叶子结点的字符的编码
HC[c]=(char *)malloc((cdlen+1)*sizeof(char));
cd[cdlen]='\0';
strcpy(HC[c],cd); // 复制编码(串)
}
}
else if(HT[c].weight==1)
{ // 向右
HT[c].weight=2;
if(HT[c].rchild!=0)
{
c=HT[c].rchild;
cd[cdlen++]='1';
}
}
else
{ // HT[c].weight==2，退回
HT[c].weight=0;
c=HT[c].parent;
--cdlen; // 退到父结点，编码长度减1
}
}
free(cd);
}
void main()
{ // 主程序同algo6-1.cpp
HuffmanTree HT;
HuffmanCode HC;
int *w,n,i;
printf("请输入权值的个数(1): ");
scanf("%d",n);
w=(int *)malloc(n*sizeof(int));
printf("请依次输入%d个权值(整型):\n",n);
for(i=0;i=n-1;i++)
scanf("%d",w+i);
HuffmanCoding1(HT,HC,w,n);
for(i=1;i=n;i++)
puts(HC[i]); HuffmanCoding2(HT,HC,w,n);
for(i=1;i=n;i++)
puts(HC[i]); }
Q3: Java实现哈夫曼算法，运行出现问题，求帮助，在线等！！！
可以在Dog与Cat类中重写Animal中的animalDo方法，通过调用animalDo方法，
然后会自动根据不同的实例调用不同类中的方法（多态知识）。
Q4: 急！哈夫曼编码算法的实现！@！！明天上午就要要的！~~~结果给的正确，加积分！！！
手打的,你最好编译一下以免我哪里敲错了
(百度不能显示行首空格真是不爽)
//哈夫曼树和~编码的存储表示
typedef struct{
unsigned int weight;//权值
unsigned int parent,lchild,rchild;
}HTNode, *HuffmanTree;//动态分配数组存储哈夫曼树
typedef char * *HuffmanCode;//动态分配数组存储哈夫曼编码表
void HoffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n){
//w存放n个字符的权值(均0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC
if (n=1) return;
m=2*n-1;
HT=(HuffmanTree) malloc ((m+1)*sizeof(HTNode));//0号单元未采用
for (p=HT,i=1;i=n;++i,++p,++w) *p={*w,0,0,0};
for (;i=m;++i;++p) *p={0,0,0,0}
for (i=n+1;i=m;++i){//建哈夫曼树
//在HT[1..i-1]选择parent为0且weight最小的两个结点编号分别为s1,s2
Select(HT,i-1,s1,s2);
HT[s1].parent=i;HT[s2].parent=i;
HT[i].lchild=s1;Ht[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
//从叶子到根逆向求每个字符的哈夫曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));//分配n个字符编码的头指针向量
cd=(char *)malloc(n*sizeof(char));//分配求编码的工作空间
cd[n-1]="\0";//编码结束符
for (i=1;i=n;++i){//逐个字符求哈夫曼编码
start=n-1;//编码结束符位置
for (c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子逆向向根求编码
if (HT[f].lchild==c) cd[--start]="0";
else cd[--start]="1";
HC[i]=(char *)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间
strcpy(HC[i],cd);//从cd复制编码(串)到HC
}
free(cd);//释放工作空间
}//HuffmanCoding
Q5: 构造哈夫曼树和哈夫曼编码,用java解答。
真懒啊你真懒啊你真懒啊你真懒啊你真懒啊你真懒啊你真懒啊你真懒啊你真懒啊你真懒啊你
