哈夫曼编码实验报告.doc

赫夫曼编码实验报告一、实验内容实现赫夫曼编码的算法二、哈夫曼编码的实验步骤 1输入n个信源符号及其对应的权值2利用select()函数找出权值最小的两个信源，并各自分配一个码元“ 0”“ 1”，并将这两个信源合并为一个新的信源，其权值为这两个最小信源的权值之和，得到一个包n-1个信源符号的新信源，这一过程叫做信源的第一次缩减3. 重复步骤二，直到只剩下两个符号为止，此时从最后一级缩减信源开始，依编码路经向前返回，得到各信源符号所对应的码字4.输出信息熵，平均码长以及编码效率三、源代码#include#include using namespace std;#define MAX 100typedef structint weight;int parent,Lc,Rc;char data;HTNode,*HTree; /动态分配数组存储赫夫曼树typedef char * *HCode;void HuffmanCode(HTree &HT,HCode &HC,int *w,int n);void Select(HTree &HT,int n,int &s1,int &s2);void inputCode();void outputCode(HCode HC,char *data,int *w,int n);const int n=27;int flag=0;HTree Ht;HCode Hc;int num;void HuffmanCode(HTree &HT,HCode &HC,int *w,int n)/w存放n个字符权值(均0)，构造赫夫曼树HT，并求n个字符赫夫曼编码HC。int m,i,s1,s2;/s1,s2为在HT1.i-1中parent为0且weight最小的两个结点if(n=1) return;/如果结点小于或等于1个，则调用函数出错，退出函数m=2*n-1;/m为赫夫曼树的总结点数HT=(HTree)malloc(m+1)*sizeof(HTNode);/ 对赫夫曼树进行初始化for(i=1;i=n;i+) HTi.data=0;HTi.weight=wi-1;HTi.parent=0;HTi.Lc=0;HTi.Rc=0;for(;i=m;i+) HTi.data=0;HTi.weight=0;HTi.parent=0;HTi.Lc=0;HTi.Rc=0;/*创建HuffmanTree*char *cd;int start,c,f; for(i=n+1;i=m;+i) Select(HT,i-1,s1,s2);HTs1.parent=HTs2.parent=i;HTi.Lc=s1;HTi.Rc=s2;HTi.weight=HTs1.weight+HTs2.weight;/从叶子到根逆向求每个字符的赫夫曼编码 HC=(HCode)malloc(n+1)*sizeof(char*); /分配n个字符编码的头指针向量 cd=(char*)malloc(n*sizeof(char); /分配求编码的工作空间 cdn-1=0; / 编码结束符for(i=1;i=n;i+)/ 逐个字符求赫夫曼编码start=n-1;/ 编码结束符位置for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/ 从叶子到根逆向求编码if(HTf.Lc=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);/ 为第i个字符编码分配空间strcpy(HCi,&cdstart); /从cd复制编码(串)到HC free(cd);/HuffmanCode/s1为权值最小的根结点void Select(HTree &HT,int n,int &s1,int &s2)/在HT1.n选择parent为0且weight最小的两个结点，其序号分别为s1,s2。/其中s1 为weight最小值的结点，s2为weight第二小的值的结点int flag1=1,flag2=1; /s1,s2初始化后则置0；int i;for(i=1;i=n;i+)if(HTi.parent=0&(flag1|flag2)if(flag1)s1=i;flag1=0;else if(flag2)s2=i;flag2=0;for(i=s1+1;i=n;i+)if(HTi.parent=0)if(HTi.weightHTs1.weight)/当所比较的值比最小值小时，修改s1和s2s2=s1;s1=i;else if(HTi.weightHTs2.weight)/当所比较值大于s1且小于s2时，只修改s2s2=i;/Selectvoid inputCode()int n;int wMAX;int i;char dataMAX;float Hx=0; /信源的熵float al=0; /平均码长int l=0; /信源符号码长float p; /信源符号概率 cout请输入编码的个数: n;cout请输入各个编码及权值endl;coutendl;for(i=0;in;i+) cout请输入第i+1datai;cinwi;coutendl;HuffmanCode(Ht,Hc,w,n);cout*信源编码如下*endl;outputCode(Hc,data,w,n); for(i=0;in;i+)/计算信源的熵p=float(wi)/100;Hx=Hx-(p)*(log(p)/log(2);/计算信源的平均码长l=0;while(Hci+1l!=0)l+;al=al+p*l;cout信源的熵 H(X)=Hx比特/符号endl;cout信源的平均码长 l=al比特/符号endl;cout编码效率为: 100*Hx/al%endl;/inputCodevoid outputCode(HCode H