哈夫曼信源编码c语言程序代码.docVIP

哈夫曼编码的C语言实现 编码原理程序步骤的分析： 哈夫曼码是用概率匹配方法进行信源编码。编程时应该注意：1，概率大的符号对应于短码，概率小的对应于长码，充分利用短码；2缩减信源的最后二个码字，总是最后一位不同，保证了哈夫曼码是即时码。程序步骤：（见信息论课本p88页内容） （l）将信号源的符号按照出现概率递减的顺序排列。 （2）将两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率 （3）重排后的两个概率最小符号重复步骤(2)过程。 （4）不断继续上述过程，直到最后两个符号配以0和1为止 （5）从最后一级开始向前返回各个信源符号所对应的码元序列，及相应的码字。 根据以上规则编码可知：哈夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，到树根结束，最后得到一个横放的码树，所以编出的码是即时码。哈夫曼编码概率大的符号对应于短码，概率小的符号对应于长码，使平均码长最小。每次对概率最小的两个符号求概率之和形成缩减信源时，构造出两个树枝，由于给两个树枝赋码元时是任意的，因此编出的码字不惟一。 程序源代码如下; #include stdio.h #include malloc.h #include conio.h #include string.h #include stdlib.h #define HuffmanTree HF #define HuffmanCode HMC typedef struct {unsigned int weight; unsigned int parent,lchild,rchild; } HTNode,*HF; typedef char **HMC; typedef struct { unsigned int s1; unsigned int s2; } MinCode; void Error(char *message); HMC HuffmanCoding(HF HT,HMC HC,unsigned int *w,unsigned int n); MinCode Select(HF HT,unsigned int n); void Error(char *message) { fprintf(stderr,Error:%s\n,message); exit(1); } HMC HuffmanCoding(HF HT,HMC HC,unsigned int *w,unsigned int n) { unsigned int i,s1=0,s2=0; HF p; char *cd; unsigned int f,c,start,m; MinCode min; if(n=1) Error(Code too small!); m=2*n-1; HT=(HF)malloc((m+1)*sizeof(HTNode)); for(p=HT,i=0;i=n;i++,p++,w++) { p-weight=*w; p-parent=0; p-lchild=0; p-rchild=0; } for(;i=m;i++,p++) { p-weight=0; p-parent=0; p-lchild=0; p-rchild=0; } for(i=n+1;i=m;i++) { min=Select(HT,i-1); s1=min.s1; s2=min.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; } printf(HT List:\n); printf(Number\t\tweight\t\tparent\t\tlchild\t\trchild\n); for(i=1;i=m;i++) printf(%d\t\t%d\t\t%d\t\t%d\t\t%d\n, i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild); HC=(HMC)malloc((n+