标题:急求huffman编解码程序!!
只看楼主
bananact
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2005-5-16
 问题点数:0 回复次数:5 
急求huffman编解码程序!!
求助高手们水能给我提供一个 huffman 编码解码的程序啊
要求输入字符和出现频率后能输出二进制码
输入二进制串能输出字符
我马上就要交作业了
高手们帮帮忙!最好越简单越好!
谢谢了!
搜索更多相关主题的帖子: huffman 解码 
2005-05-16 21:59
qin
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2006-4-25
得分:0 

typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char * *HuffmanCode;

int HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n,void(*Select)(HuffmanTree HT,int i,int &s1,int &s2))
{
if(n<=1)return 1;
int m=2*n-1;
if((HT=new HTNode[m+1])==NULL)
return 0;
HuffmanTree p;
int i,s1,s2;
// p=HT+1;
for(i=1;i<=n;i++,p++,w++)
{
HT[i].weight=*w;
HT[i].parent=HT[i].lchild=HT[i].rchild=0;
}
// *p={*w,0,0,0};
for(i=n+1;i<=m;i++,p++)
{
HT[i].weight=HT[i].parent=HT[i].lchild=HT[i].rchild=0;
}
// *p={0,0,0,0};
for(i=n+1;i<=m;i++)
{
Select(HT,i-1,s1,s2);
cout<<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;
}

if((HC=new char* [n+1])==NULL)
return 0;
char * cd;
if((cd=new char[n])==NULL)
return 0;
cd[n-1]='\0';
int start,c,f;
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]=new char[n-start];
strcpy(HC[i],&cd[start]);
}
delete cd;
return 1;
}

2006-04-25 13:25
playboy_dmx
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2006-5-14
得分:0 

大哥
有没有C版本的啊?

2006-05-14 20:31
菜鸟上路
Rank: 4
等 级:贵宾
威 望:14
帖 子:1120
专家分:0
注 册:2006-3-21
得分:0 

/* 标准文档模板 */

#include "Stdio.h"
#include "Conio.h"

#define N 30

typedef struct Node
{
int flag;
int weight;
int lchild,rchild,parent;
}HTNode,*HuffmanTree;

typedef struct Code
{
int start;
int weight;
char * code;
}HuffCode,*Code;

HuffmanCoding(HuffmanTree HT,int *w,int n)
{
int i=1,j,s1=0,s2=0;
Code cc;

if (n<=0) return;

HT=(HuffmanTree)malloc((2*n-1) * sizeof(HTNode));

printf("Binary Tree:\n");
for (i=0;i<n;i++)
{
HT[i].flag=0;
HT[i].weight=w[i];
HT[i].lchild=0;
HT[i].rchild=0;
HT[i].parent=0;
printf("weight=%d ",HT[i].weight);
printf("lchild=%d ",HT[i].lchild);
printf("rchild=%d\n",HT[i].rchild);
}
for (i=n;i<2*n-1;i++)
{
HT[i].flag=0;
HT[i].weight=0;
HT[i].lchild=0;
HT[i].rchild=0;
HT[i].parent=0;
}
for (i=n;i<2*n-1;i++) /*建立赫夫曼树*/
{
Choose(HT,i,&s1,&s2);
HT[s1].flag=1;
HT[s2].flag=1;
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;
printf("weight=%d ",HT[i].weight);
printf("lchild=%d ",HT[i].lchild);
printf("rchild=%d\n",HT[i].rchild);

}
Encoding(HT,n,cc);
printf("Leave Code:\n");
for (i=0;i<n;i++)
{
printf("weight=:%d code=:",HT[i].weight);

for (j=cc[i].start+1;j<n;j++)
printf("%c",cc[i].code[j]);
printf("\n");
}
}

Choose(HuffmanTree HT,int leftnum,int *s1,int *s2)
{ /*选择最小weight的序号*/
int i,j,min1=10000,min2=10000,temp;

for (i=0;i<leftnum;i++)
{
if (HT[i].parent==0 && min1>HT[i].weight)
{
(*s1)=i;
min1=HT[i].weight;
}
}

for (j=0;j<leftnum;j++)
{
if (HT[j].parent==0 && min2>HT[j].weight && (*s1)!=j)
{
(*s2)=j;
min2=HT[j].weight;
}
}

if ((*s1)>(*s2))
{
temp=(*s1);
(*s1)=(*s2);
(*s2)=temp;
}
}

/*
Choose2(HuffmanTree HT,int leftnum,int *s1,int *s2)
{
int i,j,min1,min2,temp;
min1=min2=10000;

for (i=0;i<leftnum;i++)
{
if (HT[i].flag==0 && min1>HT[i].weight)
{
(*s1)=i;
min2=min1;
min1=HT[i].weight;
(*s2)=(*s1);
}
else
if (HT[i].flag==0 && min2>HT[i].weight)
{
(*s2)=i;
min2=HT[i].weight;
}
}
if ((*s1)>(*s2))
{
temp=(*s1);
(*s1)=(*s2);
(*s2)=temp;
}
}

Choose1(HuffmanTree HT,int leftnum,int *s1,int *s2)
{
int i,j,min1,min2,temp;
min1=min2=10000;

for (i=0;i<leftnum;i++)
{
if (HT[i].flag==0未访问过 && min1>HT[i].weight)
{
min2=min1;
min1=HT[i].weight;
(*s2)=(*s1);
(*s1)=i;
}
}
for (j=0;j<leftnum;j++)
{
if (HT[j].flag==0 && min2>HT[j].weight && (*s1)!=j)
{
min2=HT[i].weight;
(*s2)=j;
}
}
if ((*s1)>(*s2))
{
temp=(*s1);
(*s1)=(*s2);
(*s2)=temp;
}

}
*/

Encoding(HuffmanTree HT,int n,Code HuffmanCode)
{ /*赫夫曼树中叶子编码*/
Code cd;
int i,j,child,parent;
cd=(Code)malloc((n+1)*sizeof(HuffCode));

for (i=0;i<n;i++)
{
cd->start=n-1;
cd->weight=HT[i].weight;
child=i;
parent=HT[i].parent;

while (parent!=0)
{
if (HT[parent].lchild==child)
cd->code[cd->start]='1';
else
cd->code[cd->start]='0';
cd->start--;
child=parent;
parent=HT[child].parent;
}
for (j=cd->start+1;j<n;j++)
HuffmanCode[i].code[j]=cd->code[j];

HuffmanCode[i].start=cd->start;
HuffmanCode[i].weight=cd->weight;
}
}


main()
{
int n=8;
int w[]={7,19,2,6,32,3,21,10};

HuffmanTree HTree;
HuffmanCoding(HTree,w,n);

getch();

}


2006-05-19 11:51
墨斗鱼
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2006-4-10
得分:0 

C语言的
#include <stdio.h>
#define max 500
typedef struct
{
char data;
int weight;
int parent;
int left;
int right;
}huffnode;
typedef struct
{
char cd[max];
int start;
}huffcode;
char elem[1000];
char input[1000];
int weight[1000]={0};
int m=0;
int find_char(char a[],char c,int n)
{
int i;
for(i=0;i<=n;i++)
{
if(a[i]==c) return i;
}
return -1;
}
int get_elem_weight()
{
int i,n=-1;
for(i=0;i<100;i++)
elem[i]=' ';
char c;
while(1)
{
c=getchar();
input[m++]=c;
if(c==10) break;
else if(c!=' ')
{
if(find_char(elem,c,n)==-1)
{ n++;
elem[n]=c;
weight[n]=1;
}
else weight[find_char(elem,c,n)]+=1;
}
}
printf("除空格和回车之外各字符的出现频率如下:\n");
for(i=0;i<=n;i++)
{
printf("%c %d",elem[i],weight[i]);
printf("\n");
}
return n+1;
}
main()
{
huffnode ht[2*max];
huffcode htd[max],d;
int i,k,f,l,r,n,c,m1,m2,j;
printf("请输入一个字符串,以回车结束\n");
n=get_elem_weight();
for(i=1;i<=n;i++)
{
ht[i].data =elem[i-1];
ht[i].weight =weight[i-1];
}
for(i=1;i<=2*n-1;i++)
ht[i].parent =ht[i].left =ht[i].right =0;
for(i=n+1;i<=2*n-1;i++)
{
m1=m2=32767;
l=r=0;
for(k=1;k<=i-1;k++)
if(ht[k].parent ==0)
if(ht[k].weight <m1)
{
m2=m1;
r=l;
m1=ht[k].weight ;
l=k;
}
else if(ht[k].weight <m2)
{
m2=ht[k].weight ;
r=k;
}
ht[l].parent =i;
ht[r].parent =i;
ht[i].weight =ht[l].weight +ht[r].weight ;
ht[i].left =l;
ht[i].right =r;
}
for(i=1;i<=n;i++)
{
d.start =n+1;
c=i;
f=ht[i].parent ;
while(f!=0)
{
if(ht[f].left ==c)
d.cd[--d.start ]='0';
else
d.cd [--d.start ]='1';
c=f;
f=ht[f].parent ;
}
htd[i]=d;
}
printf("输出编码\n");
for(i=1;i<=n;i++)
{
printf("%c:",ht[i].data );
for(k=htd[i].start ;k<=n;k++)
printf("%c",htd[i].cd[k]);
printf("\n");
}
printf("你所输入的字符串为\n");
for(i=0;i<m-1;i++) printf("%c",input[i]);
printf("\n");
printf("经过编码之后\n");
for(i=0;i<m-1;i++)
{
if(input[i]!=' ')
{
for(k=1;k<=n;k++)
if(ht[k].data ==input[i]) break;
for(j=htd[k].start ;j<=n;j++)
printf("%c",htd[k].cd [j]);

}
else printf("%c",input[i]);
}
printf("\n");
}


2006-05-22 20:06
大头儿子
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2006-5-22
得分:0 
谢谢!因为我也急着要交作业,谢谢共享!
2006-05-23 12:14



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-18417-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.025687 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved