资源预览内容
第1页 / 共5页
第2页 / 共5页
第3页 / 共5页
第4页 / 共5页
第5页 / 共5页
亲,该文档总共5页全部预览完了,如果喜欢就下载吧!
资源描述
实验四 哈夫曼编码的贪心算法设计(4学时)实验目的. 根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法;. 编程实现哈夫曼编译码器;. 掌握贪心算法的一般设计方法。实验目的和要求(1)了解前缀编码的概念,理解数据压缩的基本方法;(2)掌握最优子结构性质的证明方法;(3)掌握贪心法的设计思想并能熟练运用(4)证明哈夫曼树满足最优子结构性质;(5)设计贪心算法求解哈夫曼编码方案;(6)设计测试数据,写出程序文档。 实验内容设需要编码的字符集为d1, d2, , dn,它们出现的频率为 w1, w2, , wn,应用哈夫曼树构造最短的不等长编码方案。 核心源代码#include #include #include typedef struct unsigned int weight; /用来存放各个结点的权值 unsigned int parent,LChild,RChild; /指向双亲、孩子结点的指针 HTNode, *HuffmanTree; /动态分配数组,存储哈夫曼树typedef char *HuffmanCode; /动态分配数组,存储哈夫曼编码/选择两个parent为0,且weight最小的结点s1和s2void Select(HuffmanTree *ht,int n,int *s1,int *s2) int i,min; for(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=min;/构造哈夫曼树ht,w存放已知的n个权值void CrtHuffmanTree(HuffmanTree *ht,int *w,int n) int m,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; (*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最小的结点,其序号分别赋值给s1、s2 Select(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; printf(%d (%d, %d)n,(*ht)i.weight,(*ht)s1.weight,(*ht)s2.weight); printf(n); /从叶子结点到根,逆向求每个叶子结点对应的哈夫曼编码void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n) char *cd; /定义的存放编码的空间 int a100; int i,start,p,w=0; unsigned int c; hc=(HuffmanCode *)malloc(n+1)*sizeof(char *); /分配n个编码的头指针 cd=(char *)malloc(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+; else cd-start=0; /右分支标0ai+; hci=(char *)malloc(n-start)*sizeof(char); /为第i个编码分配空间 strcpy(hci,&cdstart); /将cd复制编码到hc free(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);void main() HuffmanTree HT; HuffmanCode HC; int *w,i,n,wei; printf(*哈夫曼编码*n ); printf(请输入结点个数: ); 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);实验结果实验体会哈夫曼编码算法:每次将集合中两个权值最小的二叉树合并成一棵新二叉树,n-1次合并后,成为最终的一棵哈夫曼树。这既是贪心法的思想:从某一个最初状态出发,根据当前的局部最优策略,以满足约束方程为条件,以使目标函数最快(或最慢)为原则,在候选集合中进行一系列的选择,以便尽快构成问题的可行解。 每次选择两个权值最小的二叉树时,规定了较小的为左子树。
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号