哈夫曼编码步骤Word格式.docx
《哈夫曼编码步骤Word格式.docx》由会员分享，可在线阅读，更多相关《哈夫曼编码步骤Word格式.docx（17页珍藏版）》请在冰点文库上搜索。
inti,j,m1,m2,x1,x2;
/*初始化存放哈夫曼树数组HuffNode[]中的结点*/
for（i=0;
i<
2*n-1;
i++）
{
HuffNode[i].weight=0;
//权值
HuffNode[i].parent=-1;
HuffNode[i].lchild=-1;
HuffNode[i].rchild=-1;
HuffNode[i].value=i;
//实际值，可根据情况替换为字母
}/*endfor*/
/*输入n个叶子结点的权值*/
n;
{
printf（"
Pleaseinputweightofleafnode%d:
\n"
i）;
scanf（"
%d"
&
HuffNode[i].weight）;
/*循环构造Huffman树*/
n-1;
m1=m2=MAXVALUE;
/*m1、m2中存放两个无父结点且结点权值最小的两个结点*/
x1=x2=0;
/*找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树*/for（j=0;
j<
n+i;
j++）
if（HuffNode[j].weight<
m1&
&
HuffNode[j].parent==-1）{
m2=m1;
x2=x1;
m1=HuffNode[j].weight;
x1=j;
}
elseif（HuffNode[j].weight<
m2&
m2=HuffNode[j].weight;
x2=j;
/*设置找到的两个子结点x1、x2的父结点信息*/
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;
x1.weightandx2.weightinround%d:
%d,%d\n"
i+1,HuffNode[x1].weight,HuffNode[x2].weight）;
/*用于测试*/
\n"
）;
/*
for（i=0;
i<
n+2;
i++）
printf（"
Parents:
%d,lchild:
%d,rchild:
%d,value:
%d,weight:
%d\n"
HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight）;
}
*/
//测试
}
/*endHuffmanTree*/
//解码
voiddecodeing（charstring[],HNodeTypeBuf[],intNum）{
inti,tmp=0,code[1024];
intm=2*Num-1;
char*nump;
charnum[1024]
strlen（string）;
if（string[i]=='
0'
）
num[i]=0;
elsenum[i]=1;
i=0;
nump=&
num[0];
while（nump<
（&
num[strlen（string）]））
{tmp=m-1;
while（（Buf[tmp].lchild!
=-1）&
（Buf[tmp].rchild!
=-1））
if（*nump==0）
tmp=Buf[tmp].lchild;
elsetmp=Buf[tmp].rchild;
nump++;
Buf[tmp].value）;
intmain（void）{
HNodeTypeHuffNode[MAXNODE];
/*定义一个结点结构体数组*/HCodeTypeHuffCode[MAXLEAF],cd;
/*定义一个编码结构体数组，同时定义一个临时变量来存放求解编码时的信息*/inti,j,c,p,n;
charpp[100];
Pleaseinputn:
n）;
HuffmanTree（HuffNode,n）;
i<
n;
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;
/*设置下一循环条件*
}/*endwhile*/
/*保存求出的每个叶结点的哈夫曼编码和编码的起始位*/
for（j=cd.start+1;
{
HuffCode[i].bit[j]=cd.bit[j];
HuffCode[i].start=cd.start;
/*输出已保存好的所有存在编码的哈夫曼编码*/
%d'
sHuffmancodeis:
"
for（j=HuffCode[i].start+1;
j<
HuffCode[i].bit[j]）;
start:
HuffCode[i].start）;
}/*
for（i=0;
i++）{
for（j=0;
j<
j++）
}*/
Decoding?
PleaseEntercode:
scanf（"
%s"
&
pp）;
decodeing（pp,HuffNode,n）;
getch（）;
return0;
}
解码
#include"
string.h"
stdio.h"
#defineMAXVALUE1000/*定义最大权值*/
#defineMAXLEAF30/*定义哈夫曼树叶结点个数*/
#defineMAXNODEMAXLEAF*2-1
#defineMAXBIT30/*定义哈夫曼编码的最大长度*/
typedefstruct
{intbit[MAXBIT];
intstart;
}HCODETYPE;
{intweight;
intparent;
intlchild;
intrchild;
}HNODETYPE;
char*getcode1（char*s1,char*s2,char*s3）/*首先去掉电文中的空格*/
{chartemp[128]="
"
*p,*q;
p=s1;
while（（q=strstr（p,s2））!
=NULL）
{*q='
\0'
;
strcat（temp,p）;
strcat（temp,s3）;
p=q+strlen（s2）;
strcpy（s1,temp）;
returns1;
/*再去掉重复出现的字符（即压缩电文），提取哈夫曼树叶结点*/
char*getcode（char*s1）
{chars2[26],s5[26];
chartemp[200]="
*p,*q,*r,*s3="
intm,e,n=0;
m=strlen（s1）;
while（m>
0）
{p=s1;
s2[0]=s1[0];
s2[1]='
r=s2;
e=0;
while（（q=strstr（p,r））!
e++;
m-=e;
s5[n]=s2[0];
n++;
strcpy（temp,"
s5[n]='
strcpy（s1,s5）;
printf（"
压缩后的电文（即叶结点）:
%s\n"
s1）;
HNODETYPEhuffmantree（char*s2,chars3[]）
{HNODETYPEhuffnode[MAXNODE];
HCODETYPEhuffcode[MAXLEAF],cd;
intsum,i,j,n1,n2,x1,x2,p,k,c;
chars1[26]={'
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'
};
chars5[MAXLEAF];
intww[26]={0},n=0;
strcpy（s5,s2）;
sum=strlen（s2）;
26;
i++）/*统计所有字符出现的频度*/
for（j=0;
sum;
j++）
if（s2[j]==s1[i]）ww[i]++;
n=strlen（s3）;
for（i=0;
i++）
{huffnode[i].weight=0;
huffnode[i].parent=-1;
huffnode[i].lchild=-1;
huffnode[i].rchild=-1;
i++）/*分配给各叶结点权值*/
if（s3[i]==s1[j]）huffnode[i].weight=ww[j];
i++）/*构造哈夫曼树*/
{n1=n2=MAXVALUE;
x1=x2=0;
{if（huffnode[j].parent==-1&
huffnode[j].weight<
n1）
{n2=n1;
x2=x1;
n1=huffnode[j].weight;
x1=j;
else
if（huffnode[j].parent==-1&
n2）
{n2=huffnode[j].weight;
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;
i++）/*求每个叶结点的哈夫曼编码*/
{cd.start=n-1;
c=i;
p=huffnode[c].parent;
while（p!
=-1）
{if（huffnode[p].lchild==c）
cd.bit[cd.start]=0;
cd.bit[cd.start]=1;
cd.start--;
c=p;
for（j=cd.start+1;
huffcode[i].bit[j]=cd.bit[j];
huffcode[i].start=cd.start;
各叶结点对应哈夫曼编码:
/*输出每个叶结点的哈夫曼编码*/
{for（j=huffcode[i].start+1;
huffcode[i].bit[j]）;
\n电文的全部哈夫曼编码:
/*输出电文的全部哈夫曼编码*/
for（k=0;
k<
k++）
if（s2[k]==s3[i]）
main（）
{
chars1[MAXLEAF],s2[MAXLEAF];
\n请输入电文:
gets（s1）;
strcpy（s2,getcode1（s1,"
"
））;
huffmantree（s1,getcode（s2））;
nclude<
string.h>
intm,s1,s2;
typedefstruct{
unsignedintweight;
unsignedintparent,lchild,rchild;
}HTNode,*HuffmanTree;
//动态分配数组存储哈夫曼树
typedefchar*HuffmanCode;
//动态分配数组存储哈夫曼编码表
voidSelect（HuffmanTreeHT,intn）{
inti,j;
for（i=1;
i<
=n;
if（!
HT[i].parent）{s1=i;
break;
for（j=i+1;
j<
HT[j].parent）{s2=j;
if（（HT[s1].weight>
HT[i].weight）&
（!
HT[i].parent）&
（s2!
=i））s1=i;
for（j=1;
if（（HT[s2].weight>
HT[j].weight）&
HT[j].parent）&
（s1!
=j））s2=j;
voidHuffmanCoding（HuffmanTree&
HT,HuffmanCodeHC[],int*w,intn）{
//算法6.13
//w存放n个字符的权值（均>
0），构造哈夫曼树HT，
//并求出n个字符的哈夫曼编码HC
inti,j;
char*cd;
intp;
intcdlen;
if（n<
=1）return;
m=2*n-1;
HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;
//0号单元未用
for（i=1;
=n;
i++）{//初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
for（i=n+1;
=m;
HT[i].weight=0;
puts（"
\n哈夫曼树的构造过程如下所示：
HT初态:
\n结点weightparentlchildrchild"
i++）
\n%4d%8d%8d%8d%8d"
i,HT[i].weight,
HT[i].parent,HT[i].lchild,HT[i].rchild）;
按任意键，继续..."
getchar（）;
i++）{//建哈夫曼树
//在HT[1..i-1]中选择parent为0且weight最小的两个结点，
//其序号分别为s1和s2。
Select（HT,i-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;
\nselect:
s1=%ds2=%d\n"
s1,s2）;
结点weightparentlchildrchild"
for（j=1;
=i;
j++）
j,HT[j].weight,
HT[j].parent,HT[j].lchild,HT[j].rchild）;
//------无栈非递归遍历哈夫曼树，求哈夫曼编码
cd=（char*）malloc（n*sizeof（char））;
//分配求编码的工作空间
p=m;
cdlen=0;
++i）//遍历哈夫曼树时用作结点状态标志
HT[i].weight=0;
while（p）{
if（HT[p].weight==0）{//向左
HT[p].weight=1;
if（HT[p].lchild!
=0）{p=HT[p].lchild;
cd[cdlen++]='
elseif（HT[p].rchild==0）{//登记叶子结点的字符的编码
HC[p]=（char*）malloc（（cdlen+1）*sizeof（char））;
cd[cdlen]='
strcpy（HC[p],cd）;
//复制编码（串）
}elseif（HT[p].weight==1）{//向右
HT[p].weight=2;
if（HT[p].rchild!
=0）{p=HT[p].rchild;
1'
}else{//HT[p].weight==2，退回退到父结点，编码长度减1
HT[p].weight=0;
p=HT[p].parent;
--cdlen;
}//HuffmanCoding
voidmain（）{
HuffmanTreeHT;
HuffmanCode*HC;
int*w,n,i;
输入结点数:
scanf（"
HC=（HuffmanCode*）malloc（n*sizeof（HuffmanCode））;
w=（int*）malloc（n*sizeof（int））;
输入%d个结点的权值\n"
n）;
for（i=0;
w[i]）;
Huffman
升级会员 