七：哈夫曼编码及应用

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

2、，画出哈夫曼树，并用算法continue333333.333333 .16666? .166667continue码码码码码码a0 0 0 0 为为为为 si n n2,2,1 ,1 ,曰沓沓沓疋nybtt数数数数46码码码码ac 1e ,jtjiat二 ,jtjia.ftjiro ty e0 10 1k 110 0250000250000125000125000125000125000-m- is si si si7z7z7z7z7z7z sii 林频频频频频频48btt2,2,b¥¥8ny fa数数皴皴皴皴>e/l-1d / / /z1dd ,i i ,ii i

3、,rn ,i i ,i i ,ii i ,rn ,i io ty0 10 16 0 10 0 11k 0 0 1111nc:usersgglo 47x47x47x47x47x47x47 t01 0101 孵cc频频频频频频频44:1000000101k 鬥ab2,2,3,22曰習習習習習習疋ny 炸fg数数数数数数数“码码码码码码码a 1 同同同同同同扁 s 4刖d / < 1纟纟纟纟纟纟纟 s v nd i 一 ,tt"r ,itur一 ,rr"t ,itur一 ,i 一 ,rr"t ,itur一 ,rr"t ,itur一 fiiii代码写在此处

4、#includenstdio.h"#include<malloc.h>#define maxnode 20#define maxleaf 30#define maxint 234567struct htnodeint ww;int parent,lchild, rchild;struct httreeint root; struct htnode ht maxnode;；typedef struct httree phttree;phttree *huffman (int m, int *w);void main 0 char s maxnode;int m=0;char

5、 w maxnode; int count=0;int t=0;int a maxnode;int *b;char *code;code= (char *) ma 1 loc (s izeof (char); b= (int *)malloc (sizeof (int); printf ("请输入字符窜：n");for (int i=0; i<maxn0de; i+) scanf ("%c n, &s i);+count;if (s i =' #')break;for (i=0; i<count-l; i+) a i =0; b

6、 m =0;for (int j=0; j<count-l; j+)if (s i =s j &&i<=j)a i=a i+l;if (si=sjoi>j) a i=a i+l;si =null;if (si !=null) bm =a i;w m =s i;m+;%d,频率printf (n%c的个数为 %fn", w m-1, b m-1, (float) a i / (count-1); phttree *pht;pht= (phttree *)malloc (sizeof (phttree); pht=huf fman (m, b);for

7、(i=0; i<2*m-l; i+)printf ("%du, pht->ht i. ww);printf (nn")；for (i=0; i<m; i+) int c; c=i; t=0;int p=pht->ht i.parent;whi1e (p!=-l)if (pht->ht p. lchild=c)icode t =' o't+；if (pht->ht p rchild=c) codet=/lz;t+； pht->root一一;c=p；p=pht->ht p parent;printf ("

8、%c 的编码是"，wi);for (int y=t-l; y>=0; y一)printf ("%c",code y);printf (nnn)；)phttree *huf fman (int m, int *w) /构造具有m各节点的哈弗曼树 phttree *pht;int i, j, xl, x2, ml, m2;pht=(phttree *)malloc (sizeof (phttree);if (pht=null) printf ("out of space!n")；return pht;for (i=0; i<2*m-l;

9、 i+) pht->hti. lchild=-l;pht->hti. rchild=-l;pht->hti parent=-l;if (i<m)pht->ht i. ww=w i;elsepht->hti. ww=-l;for (i=0;i+)ml=maxint;m2=maxint;xl=-l;x2=-l;for (j=0; j<m+i; j+)if(pht->htj. ww<ml&&pht->htj. parent=-l)im2=ml;x2=xl;ml=pht->htj. ww;xl=j；else if(pht->htj. ww<m2&&pht->htj. parent=-l) m2=pht->htj. ww;x2=j;pht->htxl. parent=m+i;pht->ht x2. p