七：哈夫曼编码及应用

1、广州中医药大学医学信息工程学院实验报告课程名称：数据结构与算法专业班级：计算机科学与技术（）级学生学号:学生姓名: 实验名称: 实验成绩:课程类别：限选口公选口其它口必修哈夫曼编码及应用实验目的：了解哈夫曼树的应用，掌握哈夫曼树的构造方法及前缀码的应用。实验性 质：设计性，应用性。实验步骤：(1)输入一串字符，统计其中所有的不同字符及其个数，得出每个不同字符 在文中出现的频率。(2)根据每个字符频率建立哈夫曼树，输出字符对应的编码。实验要求1、实验要求独立完成。2、迟交或不交的或源代码雷同者一律不做作业登记评分。作业提交(实验报告写在此处)给出含有6，8，11个字符的实例，统计他们的频率，画出

2、哈夫曼树，并用 算法验证结果。8211246的编码的推码2566601250001256SS125000125600cont in0 0000Hi 01 0 1 e n频频频频频顼48SS11B1K11“ k B2,2,24S香香習習習疋nuFR数数数数数数12码码码码码码. KDDnKKVr 1. AR.SSPffl S.S s c內內囱内囱內1內內询內疗巾eBJBIBJB.BIfilB 2 B.B .B ,g 日，日* i tj 、亠 J- r-wai? lbi -jj J -1-. j-T* FT;C:UsersggM代码写在此处0 8- _H- _M-00 R- o 邓曲 0 丄 0

3、10 1 筛cc毂频芻频频44LiLil000000lH1k 朋2,2,3,疋ny VFGll码码！ 码码码阳 a as rn二-ifh二n二Isl JTr .nI 一；二ISL I二 J J-HI.J!r I I -J : J r-ll FT ! kfl 3 IfJJ ft-ift-in#i nclude#in clude#defi ne MAXNODE 20#defi ne MAXLEAF 30#defi ne MAXINT 234567 struct HtNodeint ww;int pare nt,lchild,rchild;struct HtTreeint root;struct H

4、tNode htMAXNODE;typedef struct HtTree PHtTree;PHtTree *huffma n(i nt m,i nt *w);void mai n() char sMAXNODE;int m=0;char wMAXNODE; i nt cou nt=O;int t=0;int aMAXNODE;int *b;char *code;code=(char *)malloc(sizeof(char); b=(int *)malloc(sizeof(int); printf( 请输入字符窜： n); for(int i=0;iMAXNODE;i+) scanf(%c

5、,&si);+count;if(si=#)break;for(i=0;icount-1;i+) ai=0;bm=0;for(int j=0;jcount-1;j+)if(si=sj&ij)ai=ai+1;si=NULL;if(si!=NULL)bm=ai;wm=si;m+;频率printf(%c 的 个 数 %d, 为 fn,wm-1,bm-1,(float)ai/(cou nt-1);PHtTree *pht;pht=(PHtTree *)malloc(sizeof(PHtTree);pht=huffman(m,b);for(i=0;ihti.ww);printf(n);for(i=0;ih

6、ti.parent;while(p!=-1)if(pht-htp.lchild=c) codet=0; t+; if(pht-htp.rchild=c) codet=1; t+; pht-root-;c=p; p=pht-htp.parent; printf(%c 的编码是 ,wi); for(int y=t-1;y=0;y-) printf(%c,codey); printf(n); PHtTree *huffman(int m,int *w)child=-1; pht-hti.rchild=-1;pht-hti.parent=-1; if(ihti.ww=wi;else pht-hti.ww=-1; for(i=0;im-1;i+) m1=MAXINT; m2=MAXINT; x1=-1; x2=-1;for(j=0;jhtj.wwhtj.parent=-1) m2=m1; x2=x1; m1=pht-htj.ww; x1=j;else if(pht-htj.wwhtj.parent=-1) m2=pht-htj.ww;x2=j;pht-htx1.parent=m+i;pht-htx2.parent=m+i;pht-htm+i.ww=m1+m