哈夫曼编码步骤Word格式.docx
- 文档编号:3416630
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:17
- 大小:19.18KB
哈夫曼编码步骤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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈夫曼 编码 步骤