七：哈夫曼编码及应用

1、广州中医药大学医学信息工程学院时间 2021.03. 10创作：欧阳治实验报告数据结构与算法 计算机科学与技术（）级课程名称专业班级学生学号学生姓名实验名称实验成绩课程类别：必 回限选口公选口其它口 修哈夫曼编码及应用实验目的：了解哈夫曼树的应用，掌握哈夫曼树的 构造方法及前缀码的应用。实验性质：设计性，应 用性。实验步骤：（1）输入一串宇符，统计其中所有的不同宇符及 其个数，得出每个不同字符在文中出现的频 欧阳治创编2021.03.10欧阳治创编 2021.03.10率。根据每个宇符频率建立哈夫曼树，输出字符 对应的编码。实验要求1、实验要求独立完成。2、迟交或不交的或源代码雷同者一律不做作

2、业登 记评分。作业提交（实验报告写在此处）给出含有6, 8, 11个字符的实例，统计他们的频率，画出哈夫曼树，并用算法验证结果。#includenstdio.hM#include < malloc. h >#deflnc MAXNODE 20#deflnc MAXLEAF 30 #dcfinc MAXINT 234567struct HtNodcint ww;int parcntjchild.rchild;struct HtTrecint root;struct HtNodc htMAXN()DE;；typcdcf struct HtTrec PHtTrec;PHtTrce *hu

3、ffman(int mint *w);void main() char sMAXNODE;int m=();char wMAXN()DEJ; int countO;int t=();int aMAXN()DE;int *b;char *codc;c()ck=(char *)malloc(sizcof(char);b二(int *)malloc(sizeof(int);printfC请输入字符窜:n");for(int i=0;i<MAXNODE;i+) scanf(”c ”,&si);+count;if(s|i=#)break;fbr(i=();i< count-

4、1 ;汁+) ai=0;bm=0;for(int j=();j<count-l ;j+)iF(si二二 sj &&iv 二 j)ai=ai + l；iF(si二二 sj &&i>j)ai=ai+l;si=NULL;if(si!=NULL)欧阳治创编2021.03.10欧阳治创编 2021.03.10bm=ai;wm=si;m+;printf("%c 的个数 %d,频率为 %fn",wm-l,bm-1 , (float) af/ (count-1);PHtTree *pht;pht=(PHtTrce *)malloc(sizeof(

5、PHtTree);pht=huffman(m,b);for(i=0;i<2*m-l ;i+)printf("%d",pht->hti.ww);printfCn");for(i=();i<m;i-F4-) int c;c=i;t=0;intp=pht->hti.parent;while(p!=-l)欧阳治创编2021.03.10欧阳治创编 2021.03.10if(pht->htp.lchild=c)code t='()'计+；if(pht->htp.rchild=c)codcftjr；t+；pht->roo

6、t;C=p；p=pht->htp.parent;printf("%c 的编码是”,vi);for(int y=t-l;y>=();y)printF(”c",codty);prin 呎、n”)；PHtTree *huffman(int m,int *w)/构造具有 m 各节点的哈弗曼树PHtTrcc *pht;intpht= (PHtTrcc *)malloc(sizeof(PHtTree);if(pht=NULL)printf(Hout of spacc!nn);return pht;fbr(i=0<2*m-U4-F)pht->hti.lchild=

7、-l;pht->hti .rchild=-l;pht->hti.parcnt=-l;pht->hti xvw 二 w i;elsepht>hti.ww二 1;for(i=();i<m-l;i+)欧阳治创编2021.03.10欧阳治创编 2021.03.10ml=MAXINT;m2 二 MAXINT;xl=-l;x2二 1;for(j=0;jvm+i;j+)if(pht->htj .ww<m 1&&pht->htj.parcnt=-l)m2 二 ml;x2=xl;ml 二pht>>ht(j.yvw;xl=j；else if(pht->ht:jww<m2&&pht->htj.parcnt=-l)m2 二 pht>>ht(jvw；x2=j;pht->htxl.parcnt=m+i;pht->htx2.parcnt=m+i;pht->htm+i ww二ml +m2;欧阳治创编2021.03.10欧阳治创编 2021.03.10pht->ht