2024年哈夫曼编码实验报告.doc

试验汇报与總結

一、试验目的

掌握哈夫曼编码原理；

纯熟掌握哈夫曼树的生成措施；

3、理解数据编码压缩和译码输出编码的实現。

二、试验规定

实現哈夫曼编码和译码的生成算法。

三、试验内容

先记录要压缩编码的文献中的字符字母出現的次数，按字符字母和空格出現的概率對其進行哈夫曼编码，然後讀入要编码的文献，编码後存入另一种文献；接著再调出编码後的文献，并對其進行译码输出，最终存入另一种文献中。

五、试验原理

1、哈夫曼树的定义：假设有n個权值，试构造一颗有n個叶子节點的二叉树，每個叶子带权值為wi，其中树带权途径最小的二叉树成為哈夫曼树或者最优二叉树；

2、哈夫曼树的构造：

weight為输入的频率数组，把其中的值赋給依次建立的HTNode對象中的data属性，即每一种HTNode對应一种输入的频率。然後根据data属性按從小到大次序排序，每次從data取出两個最小和本次小的HTNode，将他們的data相加，构造出新的HTNode作為他們的父节點，指针parent，leftchild，rightchild赋對应值。在把這個新的节點插入最小堆。按此环节可以构造构造出一棵哈夫曼树。

通過已經构造出的哈夫曼树，自底向上，由频率节點開始向上寻找parent,直到parent為树的顶點為止。這样，根据每次向上有哪些信誉好的足球投注网站後，原节點為父节點的左孩子還是右孩子，来记录1或0，這样，每個频率都會有一种01编码与之唯一對应，并且任何编码没有前部分是同其他完整编码同样的。

六、试验流程

初始化，记录文本文献中各字符的個数作為权值,生成哈夫曼树；

根据符号概率的大小按由大到小次序對符号進行排序；

把概率最小的两個符号构成一种节點；

反复环节（2）（3），直到概率和為1；

從根节點開始到對应于每個符号的“树叶”，概率大的標“0”，概率小的標“1”；

從根节點開始，對符号進行编码；

译码時流程逆向進行，從文献中讀出哈夫曼树,并运用哈夫曼树将编码序列解码。

七、试验程序

#includeiostream

#includefstream

#includeiomanip

#includevector

usingnamespacestd;

typedefstruct//节點构造

{

chardata;//记录字符值

longintweight;//记录字符权重

unsignedintparent,lchild,rchild;

}HTNode,*HuffmanTree;//動态分派数组存储哈夫曼树

typedefchar**HuffmanCode;//動态分派数组存储哈夫曼编码表

voidSelect(HuffmanTreeHT,inti,ints1,ints2)//在HT[1...t]中选择parent不為0且权值最小的两個結點，其序号分别為s1和s2

{

s1=0;s2=0;

intn1=30000,n2=30000;

for(intk=1;k=i;k++)

{

if(HT[k].parent==0)

{

if(HT[k].weightn1)

{

n2=n1;n1=HT[k].weight;

s2=s1;s1=k;

}

else

if(HT[k].weightn2)

{

n2=HT[k].weight;

s2=k;

}

}

}

}

voidHuffmanCoding(HuffmanTreeHT,HuffmanCodeHC,intn)//将要编码的字符串存入空树中

{

ifstreamfin1(zifu.txt);

ifstreamfin2(weight.txt);

if(n=1)return;

intm=2*n-1;

inti;

HT=newHTNode[m+1];

char*zifu;

int*weight;

zifu=newchar[n+1];

weight=newint[n+1];

for(i=1;i=n;i++)//将待编码的字符放在zifu数组中

{

charch;

ch=fin1.get();

zifu[i]=ch;

}

for(i=1;i=n;i++)//将带编码字符對应的权值放在weight数组中

{

fin2weight[i];

}

for(i=1;i=n;i++)

{

HT[i].data=zifu[i];

HT[i].weight=weight[i];

}

for(i=n+1;i=m;i++)

{

HT[i].data=@;

}

for(i=1;i=m;i++)

{

HT[i].parent=HT[i].lchild=HT[i].rchild=0;

}

for(i=n+1;i=m;++i)

{

int