实验一哈夫曼编码.pptVIP

实验一 哈夫曼编码 实验目的 掌握哈夫曼编码原理 理解数据压缩的实现过程 实验要求 根据哈夫曼编码算法，对下列信源实现哈夫曼编码。求出编码后的平均码长。 实验内容与步骤 1、实验内容 对上面信源进行哈夫曼编码。 显示出每个符号的分配代码及平均码长 2、实验步骤 （1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。 （2）把概率最小的两个符号组成一个节点。 （3）重复步骤（1）（2），直到概率和为1 （4）从根节点开始到相应于每个符号的“树叶”，概率大的标“0”，概率小的标“1” （5）从根节点开始，对符号进行编码。 实验结果要求 1、哈夫曼编码程序。 2、实验报告(含流程图) 0.23 0.21 0.18 0.15 0.13 0.07 0.03 概率 1 0 0.10 1 0 0.23 1 0 0.33 1 0 0.44 1 0 0.56 0 1 1 编码 01 00 111 110 101 1001 1000 A1 A2 A3 A4 A5 A6 A7 符号 哈夫曼编码举例 #include stdio.h #include string.h #define N 15 #define M 2*N-1 typedef struct { float weight; int parent,lchild,rchild; }HTNode; typedef struct { char data; float weight; char code[N]; }HTCode; 参考程序 void Init(HTCode hc[],int *n) { int i; printf(\n input n=); scanf(%d,(*n)); fflush(stdin); /*修改的地方*/ printf(\n input %d character \n,*n); for(i=1;i=*n;i++) { printf(\n the %d charactor is:,i); scanf(%c,(hc[i].data)); fflush(stdin); /* 修改的地方*/ } for(i=1;i=*n;i++) { printf(\n the %d charactor weight is:,i); scanf(%f,(hc[i].weight)); } } 参考程序(续) void Select(HTNode ht[],int k,int *s1,int *s2) { int i; for(i=1;i=k;i++) { if(ht[i].parent==0) { *s1=i; break; } } for(i=1;i=k;i++) { if(ht[i].parent==0ht[i].weightht[*s1].weight) *s1=i; } 参考程序(续) for(i=1;i=k;i++) { if(ht[i].parent==0i!=*s1) { *s2=i; break; } } for(i=1;i=k;i++) { if(ht[i].parent==0i!=*s1ht[i].weightht[*s2].weight) *s2=i; } printf(\n this is *s1:%d\n,*s1); printf(\n this is *s2:%d\n,*s2); } 参考程序(续) void HuffmanCoding(HTNode ht[],HTCode hc[],int n) { char cd[N]; int i,j,m,c,f,s1,s2,start; m=2*n-1; for(i=1;i=m;i++) { if(i=n) ht[i].weight=hc[i].weight; else ht[i].weight=0.0; ht[i].parent=ht[i].lchild=ht[i].rchild=0; } for(i=n+1;i=m;i++) { Select(ht,i-1,s1,s2); 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; } 参考程序(续)