哈夫曼编码源程序与运行结果.doc

源程序：#include#include#include#include/* Huffman 树的存储结构*/#define n 4/*叶子数目根据需要设定*/#define m 2*n-1/* Huffman 树中结点总数 */typedef struct float weight;/*结点的权值*/int lchild,rchild,parent;/*左、右孩子及双亲的下标*/htnode;typedef htnode huffmantreem+1;/* huffmantree是结构数组类型,其0号单元不用，存储哈夫曼树 */typedef structchar ch;/*存储字符*/ char coden+1;/*存放编码位串*/codenode;typedef codenode huffmancoden+1;/*huffmancode是结构数组类型,其0号单元不用,存储哈夫曼编码*/void inithuffmantree(huffmantree ht) /*初始化哈夫曼树函数inithuffmantree()*/int i; for(i=0;i=m;i+)hti.weight=0;hti.lchild=hti.rchild=hti.parent=0;void inputweight(huffmantree ht)/*输入权值函数 */int i; printf(请输入概率n);for(i=1;i=n;i+) scanf(%f,&hti.weight);for(i=1;i=n;i+) hti.weight=hti.weight*100;void selectmin(huffmantree ht, int i, int *p1, int *p2)/* 在ht1.i中选两个权值最小的根结点，其序号为*p1和*p2，*p1中放权值最小的根结点的序号，*p2中放权值次小的根结点的序号*/int j,min1,min2;/* min1,min2分别是最小权值和次小权值*/min1=min2=32767;*p1=*p2=0;for(j=1;j=i;j+)if(htj.parent=0)/* j 为根结点*/if(htj.weightmin1|min1=32767)if(min1!=32767)min2=min1; *p2=*p1; min1=htj.weight; *p1=j;elseif(htj.weightmin2|min2=32767)min2=htj.weight; *p2=j;void createhuffmantree(huffmantree ht)/*构造huffman树，htm为其根结点*/int i,p1,p2;inithuffmantree(ht);/* 将ht初始化*/inputweight(ht);/* 输入叶子权值至ht 1.n的weight域*/for(i=n+1;i=m;i+)/* 共进行n-1次合并，新结点依次存于hti中*/selectmin(ht,i-1,&p1,&p2); /*在ht 1. i-1中选择两个权值最小的根结点，其序号分别为p1和p2*/ htp1.parent=htp2.parent=i; hti.lchild=p1;/* 最小权值的根结点是新结点的左孩子*/ hti.rchild=p2; /* 次小权值的根结点是新结点的右孩子*/ hti.weight=htp1.weight+htp2.weight;void huffmancodes(huffmantree ht,huffmancode hcd) /*根据huffman树ht求huffman编码*/int c,p,i,numn+1,j;/* c和p分别指示 ht中孩子和双亲的位置 */char cdn+1;/* 临时存放编码*/int start; /* 指示编码在cd 中的起始位置*/float l=0;cdn=0;/* 编码结束符*/printf(请输入字符n); for(i=0;i=n;i+)/* 依次求叶子ht i的编码*/ hcdi.ch=getchar();/* 读入叶子ht i对应的字符*/ start=n;/* 编码起始位置的初值*/ c=i;/* 从叶子ht i开始上溯*/while(p=htc.parent)!=0)/* 直至上溯到ht c是树根为止*/ cd-start=(htp.lchild=c)?0:1; /*若ht c是htp的左孩子，则生成代码0，否则生成代码1*/ c=p;/* 继续上溯*/strcpy(hcdi.code,&cdstart);/* 复制编码位串*/printf(n);printf(序号 信源字母 码字 码字长 n);for(i=1;i=n;i+)printf( %d %c %s %dn,i,hcdi.ch,hcdi.code,strlen(hcdi.code);for(i=1;i=n;i+)l=l+strlen(hcdi.code)*(hti.weight/100);printf(平均码长=%f比特n,l);vo