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

发布时间：2022-05-29 发布人：admin 分类：说明书资料大小：0.03M 资料格式：doc 举报版权申诉

zxmleehom-1980351-4744302543428519039.doc.pdf-第1页.png

第1页 / 共7页

zxmleehom-1980351-4744302543428519039.doc.pdf-第2页.png

第2页 / 共7页

zxmleehom-1980351-4744302543428519039.doc.pdf-第3页.png

第3页 / 共7页

zxmleehom-1980351-4744302543428519039.doc.pdf-第4页.png

第4页 / 共7页

zxmleehom-1980351-4744302543428519039.doc.pdf-第5页.png

第5页 / 共7页

zxmleehom-1980351-4744302543428519039.doc.pdf-第6页.png

第6页 / 共7页

zxmleehom-1980351-4744302543428519039.doc.pdf-第7页.png

第7页 / 共7页

文本预览

哈夫曼编码的 C 语言实现编码原理程序步骤的分析：哈夫曼码是用概率匹配方法进行信源编码。编程时应该注意：1，概率大的符号对应于短码，概率小的对应于长码，充分利用短码；2 缩减信源的最后二个码字，总是最后一位不同，保证了哈夫曼码是即时码。程序步骤：（见信息论课本 p88 页内容）（l）将信号源的符号按照出现概率递减的顺序排列。（2）将两个概率最小的字母分别配以 0 和 1 两个码元，并将这两个概率相加作为一个新字母的概率（3）重排后的两个概率最小符号重复步骤(2)过程。（4）不断继续上述过程，直到最后两个符号配以 0 和 1 为止（5）从最后一级开始向前返回各个信源符号所对应的码元序列，及相应的码字。根据以上规则编码可知：哈夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，到树根结束，最后得到一个横放的码树，所以编出的码是即时码。哈夫曼编码概率大的符号对应于短码，概率小的符号对应于长码，使平均码长最小。每次对概率最小的两个符号求概率之和形成缩减信源时，构造出两个树枝，由于给两个树枝赋码元时是任意的，因此编出的码字不惟一。程序源代码如下; #include

#include #include #include #include #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+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char *)); cd[n-1]='\0'; for(i=1;i<=n;i++) { start=n-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; HC[i]=(char *)malloc((n-start)*sizeof(char *)); strcpy(HC[i],&cd[start]); } free(cd); return HC; } void main() {

MinCode Select(HF HT,unsigned int n); HF HT=NULL; HuffmanCode HC=NULL; unsigned int *w=NULL; unsigned int i,n; printf("请输入节点个数 n:"); scanf("%d",&n); w=(unsigned int *)malloc((n+1)*sizeof(unsigned int *)); w[0]=0; printf("请输入权重:\n"); for(i=1;i<=n;i++) { printf("w[%d]=",i); scanf("%d",&w[i]); } HC=HuffmanCoding(HT,HC,w,n); printf("HMC:\n"); printf("Number\t\tWeight\t\tCode\n"); for(i=1;i<=n;i++) printf("%d\t\t%d\t\t%s\n",i,w[i],HC[i]); } MinCode Select(HF HT,unsigned int n) { unsigned int min,secmin; unsigned int temp; unsigned int i,s1,s2,tempi; MinCode code;

s1=1;s2=1; for(i=1;i<=n;i++) if(HT[i].parent==0) { min=HT[i].weight; s1=i; break; } tempi=i++; for(;i<=n;i++) if(HT[i].weights2)

{ temp=s1; s1=s2; s2=temp; } code.s1=s1; code.s2=s2; return code; } 运行结果如下：请输入节点个数 n:5 请输入权重: w[1]=2 w[2]=3 w[3]=1 w[4]=1 w[5]=3 Number 1 2 3 4 5 Press any key to continue Weight 2 3 1 1 3 Code 00 10 010 011 11 编程感想及总结：正如事物均具有两面性，哈夫曼编码也具有优点和缺点，比如哈夫曼编码可以取得较好的荣誉压缩效果，使得输出码元概率均匀化。但是由于编码不唯一，硬件实现可能会有一定难度，压缩与还原也相对费时，尤其在概率相同的情况下，编码效率较低。

分享到：

赞收藏

资料库

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

相关推荐

开发技术

热门标签

最新资料