实验四哈夫曼编码的贪心算法设计

1、实验四哈夫曼编码的贪心算法设计（4学时）实验目的1. 根据算法设计需要，掌握哈夫曼编码的二叉树结构表示方法；2. 编程实现哈夫曼编译码器；3. 掌握贪心算法的一般设计方法。实验目的和要求（1）了解前缀编码的概念，理解数据压缩的基本方法；（2）掌握最优子结构性质的证明方法；（3）掌握贪心法的设计思想并能熟练运用（4）证明哈夫曼树满足最优子结构性质；（5）设计贪心算法求解哈夫曼编码方案；（6）设计测试数据，写出程序文档。实验内容j设需要编码的字符集为d1,d2,dn，它们出现的频率为kiakw1,w2,wn，应用哈夫曼树构造ki最短的不等长编码方案。核心源代码#include<stdio.h

2、>#include<stdlib.h>#include<string.h>typedefstructunsignedintweight；/用来存放各个结点的权值unsignedintparent，LChild，RChild；/指向双亲、孩子结点的指针HTNode，*HuffmanTree；/动态分配数组，存储哈夫曼树typedefchar*HuffmanCode；/动态分配数组，存储哈夫曼编码/选择两个parent为0，且weight最小的结点s1和s2voidSelect(HuffmanTree*ht，intn，int*s1，int*s2)inti，min；fo

3、r(i=1；i<=n；i+)if(*ht)i.parent=0)min=i；break；for(i=1；i<=n；i+)if(*ht)i.parent=0)if(*ht)i.weight<(*ht)min.weight)min=i;*s1=min;for(i=1;i<=n;i+)if(*ht)i.parent=0&&i!=(*s1)min=i;break;for(i=1;i<=n;i+)if(*ht)i.parent=0&&i!=(*s1)if(*ht)i.weight<(*ht)min.weight)min=i;*s2=mi

4、n;/构造哈夫曼树ht,w存放已知的n个权值voidCrtHuffmanTree(HuffmanTree*ht,int*w,intn)intm,i,s1,s2;m=2*n-1;/总共的结点数*ht=(HuffmanTree)malloc(m+1)*sizeof(HTNode);for(i=1;i<=n;i+)/1-n号存放叶子结点，初始化(*ht)i.weight=wi;(*ht)i.LChild=0;(*ht)i.parent=0;(*ht)i.RChild=0;for(i=n+1;i<=m;i+)/非叶子结点的初始化(*ht)i.weight=0;(*ht)i.LChild=0

5、;(*ht)i.parent=0;(*ht)i.RChild=0;printf("n哈夫曼树为:n");for(i=n+1;i<=m;i+)/创建非叶子结点，建哈夫曼树/在(*ht)1(*ht)i-1的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给si、s2Select(ht,i-1,&s1,&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;pr

6、intf("%d(%d,%d)n",(*ht)i.weight,(*ht)s1.weight,(*ht)s2.weight);printf("n");/从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码voidCrtHuffmanCode(HuffmanTree*ht,HuffmanCode*hc,intn)char*cd;/定义的存放编码的空间inta100;inti,start,p,w=0;unsignedintc;hc=(HuffmanCode*)malloc(n+1)*sizeof(char*);/分配n个编码的头指针cd=(char*)mall

7、oc(n*sizeof(char);/分配求当前编码的工作空间cdn-1='0'/从右向左逐位存放编码，首先存放编码结束符for(i=1;i<=n;i+)/求n个叶子结点对应的哈夫曼编码ai=0;start=n-1;/起始指针位置在最右边for(c=i,p=(*ht)i.parent;p!=0;c=p,p=(*ht)p.parent)/从叶子到根结点求编码if(*ht)p.LChild=c)cd-start='1'/左分支标1ai+;elsecd-start='0'/右分支标0ai+;hci=(char*)malloc(n-start)*s

8、izeof(char);/为第i个编码分配空间strcpy(hci,&cdstart);/将cd复制编码到hcfree(cd);for(i=1;i<=n;i+)printf(”权值为d的哈夫曼编码为：sn",(*ht)i.weight,hci);for(i=1;i<=n;i+)w+=(*ht)i.weight*ai;printf("带权路径为：%dn",w);voidmain()HuffmanTreeHT;HuffmanCodeHC;int*w,i,n,wei;printf("*哈夫曼编码*n");printf("

9、请输入结点个数：");scanf("%d",&n);w=(int*)malloc(n+1)*sizeof(int);printf("n输入这d个元素的权值:n",n);for(i=1;i<=n;i+)printf("%d:",i);fflush(stdin);scanf("%d",&wei);wi=wei;CrtHuffmanTree(&HT,w,n);CrtHuffmanCode(&HT,&HC,n);实验结果31'弓：P'-b"?rrp?.10100111110010101010310®eI*nV勺勺hiHIZrmnl-Tnrr-TUTXrzfpn扁帀帀帛=口帛帛T巾o譬£豪零囂-吐哈偎哈牌娜哈松ke?frH24&y29315214fcn刘刘为为为为为対路affiBfl渲渲E-值值权ssp哈夫曼树为:7<3.4>12(5,实验体会哈夫曼编码算法：每次将集合中两个权值