哈夫曼编码和译码的算法设计与实现
- 格式：docx
- 大小：17.62 KB
- 文档页数：7
哈夫曼编码和译码的算法设计与实现
实验名称哈夫曼编码和译码的算法设计与实现实验方案实验成绩实验日期实验室信息系统设计与仿真室I 实验操作
实验台号班级姓名实验结果
一、实验目的
1、掌握哈夫曼编码的二叉树结构表示方法；
2、编程实现哈夫曼编码译码器；
3、掌握贪心算法的设计策略。
二、实验任务
①从文件中读取数据，构建哈夫曼树；
②利用哈夫曼树，对输入明文进行哈夫曼编码；
③利用哈夫曼树，对输入编码译码为明文。
三、实验设计方案
1、结构体设计
Huffman树：包括字符，权，父亲下标，左孩子下标，右孩子下标
#define N 29 //26个小写字母，逗号，句号和空格字符.
struct treenode{ //静态链表
char c; //char
int w; //weight
int f; //father
int l; //left child index
int r; //right child index
};
struct treenode htree[2*N-1];
2、自定义函数设计
①函数原型声明
void input(); //读取文件字符、权值数据
void huffman(); //建立huffman树 void getcode(int i, char *str); //得到单个字符的huffman编码
void encode(char ch); //将明文进行huffman编码
void decode(char *str); //将huffman编码译为明文
②读取文件字符、权值数据
void input()
{
int i;
char c;
int f;
freopen("in.txt","r",stdin);
for(i=0;i
{
c=getchar(); //接收字符
scanf("%d",&f); //接收权值
getchar(); //接收回车
ht[i].c=c;
ht[i].w=f;
ht[i].l=ht[i].f=ht[i].r=-1; //初始化父亲、左右孩子下标}
freopen( "CON", "r", stdin);
}
③建立huffman树
//使用贪心法建立huffman树,每次选择权值最小的根结点
void huffman()
{
void huffman()
{
int j,k,n;
input();
j=0;
k=N; for(n=N;n<2*N-1;n++){ //建立huffman树，共合并N-1次int
r=0,s=0;
ht[n].l=ht[n].f=ht[n].r=-1;
while(r<2){ //选择两个最小的权值结点
if((ht[k].w==0 || ht[k].w>ht[j].w) && j
s+=ht[j].w;
if(r==0) ht[n].l = j; //修改父亲、孩子下标
else ht[n].r=j;
ht[j].f=n;
j++;
}
else{
s+=ht[k].w;
if(r==0) ht[n].l = k; //修改父亲、孩子下标
else ht[n].r=k;
ht[k].f=n;
k++;
}
r++;
}
ht[n].w=s; //修改权值
}
}
④根据字符下标找到字符的huffman编码
//根据字符所在的下标，从叶子结点往上搜索到根节点，然后逆置得到该字符的huffman编码void getcode(int i, char *str){
int n,j,l=0;
for(n=i;ht[n].f!=-1;n=ht[n].f){ //沿着父亲往上搜索
int m=ht[n].f;
if(n==ht[m].l) str[l++]='0'; //左孩子记为0
else
str[l++]='1'; //右孩子记为1
}
for(j=0;j<=(l-1)/2;j++){ //将编码逆置
char t;
t=str[j];
str[j]=str[l-1-j];
str[l-1-j]=t;
}
str[l]=0; // str存放huffman编码，字符串结束标记
}
⑤读入明文生成huffman编码
void encode(char ch)
{
int i;
char str[N];
for(i=0;ht[i].c!=0;i++)
if(ht[i].c==ch) //找字符下标
break;
if (ht[i].c!=0)
{
getcode(i,str); //得到字符的huffman编码
printf("%s",str);
}
}
⑥将huffman编码串译码为明文
void decode(char *str){
while(*str!='\0'){
int i; for(i=2*N-2;ht[i].l!=-1;){
if(*str=='0')
i=ht[i].l;
else
i=ht[i].r;
str++;
}
printf("%c",ht[i].c);
}
}
3、主函数设计
思路：主函数实现实验任务的基本流程。
void main()
{
char ch;
int i;
char str[100];
huffman(); //建立huffman树
printf("请输入明文："); //输入明文
while((ch=getchar())!='\n')
encode(ch); //得到huffman编码printf("\n");
printf("\n请按字符编码对应表输入密文：\n");
for(i=0;i<="">
{
printf("%c:",ht[i].c);
encode(ht[i].c);
printf("\t");
}
scanf("%s",str); //输入编码串
decode(str); //翻译成明文 printf("\n");
}
四、测试
1、字符权值数据存放在in.txt文件中：
j 217
z 309
q 343
x 505
k 1183
w 1328
v 1531
f 1899
. 2058
y 2815
b 2918
g 3061
, 3069
h 3724
d 4186
m 4241
p 4283
u 4910
5005
c 6028
s 6859
l 6882
n 7948
o 8259
t 8929
r 9337 i 9364
a 10050
e 11991
2、测试
输入明文：you
输出编码：111011*********
输入编码：010001111111001000
输入解码：love
五、总结与讨论
1、问题与错误
2、经验与收获
3、改进与设想
六、源代码
