实验一哈夫曼编码

实验一 哈夫曼编码n实验目的n掌握哈夫曼编码原理n理解数据压缩的实现过程 实验要求根据哈夫曼编码算法，对下列信源实现哈夫曼编码。求出编码后的平均码长。 05.0,10.0,15.0,20.0,25.0,25.0 6,5,4,3,2,1 XXXXXXX 实验内容与步骤1、实验内容n 对上面信源进行哈夫曼编码。n 显示出每个符号的分配代码及平均码长2、实验步骤（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。 （2）把概率最小的两个符号组成一个节点。（3）重复步骤（1）（2），直到概率和为1（4）从根节点开始到相应于每个符号的“树叶”，概率大的标“0”，概率小的标“1”（5）从根节点开始，对符号进行编码。 实验结果要求1、哈夫曼编码程序。2、实验报告(含流程图) #include #include #define N 15#define M 2*N-1typedef struct float weight;int parent,lchild,rchild;HTNode;typedef struct char data;float weight; char codeN;HTCode; 参考程序 void Init(HTCode hc,int *n) int i;printf(n input n=);scanf(%d,fflush(stdin); /*修改的地方*/printf(n input %d character n,*n);for(i=1;i=*n;i+) printf(n the %d charactor is:,i);scanf(%c,fflush(stdin); /* 修改的地方*/for(i=1;i=*n;i+) printf(n the %d charactor weight is:,i);scanf(%f, 参考程序(续) void Select(HTNode ht,int k,int *s1,int *s2) int i;for(i=1;i=k;i+) if(hti.parent=0) *s1=i;break;for(i=1;i=k;i+) if(hti.parent=0参考程序(续) for(i=1;i=k;i+) if(hti.parent=0break;for(i=1;i=k;i+)if(hti.parent=0printf(n this is *s1:%dn,*s1); printf(n this is *s2:%dn,*s2); 参考程序(续) void HuffmanCoding(HTNode ht,HTCode hc,int n) char cdN;int i,j,m,c,f,s1,s2,start;m=2*n-1;for(i=1;i=m;i+) if(i=n) hti.weight=hci.weight;else hti.weight=0.0;hti.parent=hti.lchild=hti.rchild=0;for(i=n+1;i=m;i+) Select(ht,i-1,hts1.parent=i;hts2.parent=i; hti.lchild=s1;hti.rchild=s2;hti.weight=hts1.weight+hts2.weight; 参考程序(续) for(i=1;i=m;i+) printf(n the %d charactor weight is %f:,i,hti.weight);printf(n the %d charactor lchild is %d:,i,hti.lchild);printf(n the %d charactor rchild is %d:,i,hti.rchild);printf(n the %d charactor parent is %d:,i,hti.parent);for(i=0;iN;i+) cdi= ;cdn-1=0;for(i=1;i=n;i+) start=n-1;for(c=i,f=hti.parent;f;c=f,f=htf.parent) if(htf.lchild=c) cd-start=0; else cd-start=1;strcpy(hci.code, 参考程序(续) void main() int i,m,n,wN+1;float l=0.0;float arg,*point=HTNode htM+1;HTCode hcN+1;Init(hc,HuffmanCoding(ht,hc,n);for(i=1;i=n;i+)printf(n the code of %c is :%s,hci.data,hci.code);for(i=1;i=n;i+) l+=strlen(hci.code)*hci.weight; /* 修改的地方*/* l+=strlen(hci.code); */ /* l=l/n; 修改的地方*/printf(n the average length of the huffman coding is %f,l); 参考程序(续)