实验报告哈夫曼.docx

《算法分析与设计》课程设计报告题 目：利用哈夫曼编码算法实现字串最优前缀码的生成工作 专 业： 计算机科学与技术 班 级： 姓 名： 指导教师： 2016年 5 月 25日一、问题分析哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法 哈夫曼树注意事项：① 初始森林中的n棵二叉树，每棵树有一个孤立的结点，它们既是根，又是叶子② n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新结点最终求得的哈夫曼树中共有2n-1个结点③ 哈夫曼树是严格的二叉树，没有度数为1的分支结点前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀这种编码称为前缀码表示最优前缀码的二叉树总是一棵完全二叉树，即树中任意节点都有2个儿子带权值的结点都是叶子结点权值越小的结点，其到根结点的路径越长 所谓前缀码是指，对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，比如常见的等长编码就是前缀码。

所谓最优前缀码是指，平均码长或文件总长最小的前缀编码称为最优的前缀码（这里的平均码长相当于码长的期望值）哈夫曼编码算法实现字串最优前缀码的生成，这是压缩的一种方式，在实际生活中应用广泛，一般采用贪心算法，二、问题的解决方案/算法选择/设计思路1)哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树T (2)算法以|C|个叶结点开始，执行|C|－1次的“合并”运算后产生最终所要求的树T (3)假设编码字符集中每一字符c的频率是f(c)以f为键值的优先队列Q用在贪心选择时有效地确定算法当前要合并的2棵具有最小频率的树一旦2棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的2棵树的频率之和，并将新树插入优先队列Q经过n－1次的合并后，优先队列中只剩下一棵树，即所要求的树T生成哈夫曼树（1）根据给定的n个权值{w1,w2,...,wn}构造n棵二叉树的集合F={T1,T2,...,Tn}，其中Ti中只有一个权值为wi的根结点，左右子树为空； （2）在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和 （3）将新的二叉树加入到F中，删除原两棵根结点权值最小的树；（4）重复（2）和（3）直到F中只含一棵树为止，这棵树就是哈夫曼树。

图1在队列中取最小的两个数，根的权值是这两个数的和，在将根的值带回队列中，在取最小的两个数，重复进行，得到哈夫曼树记左子树为0，右子树为1，得到最优前缀数三、算法设计/问题求解中所遇到的问题及分析解决方案 生成树/*功能用于生成哈夫曼树*/ huffman ctrHuffmanTree(int n){ int m=2*n-1;//1~n存储叶子结点n+1~m存储树的n-1个内部结点 huffman tree=(huffman)malloc(sizeof(huffmanNode)*(m+1));//用于存储哈夫曼树各结点 priorityqueue h;//用于存储优先队列首地址 int i; if(tree==NULL){ printf("out of space"); exit(-1); } /*生成叶子结点*/ for(i=1;i<=n;i++){ printf("输入 %d 字母和权重:",i); scanf("%c%f",&tree[i].c,&tree[i].f); tree[i].i=i; tree[i].parent=tree[i].lchild=tree[i].rchild=-1; tree[i].code=NULL; getchar();//吸收回车 } /*初始化优先队列*/ h=initializePrioQueue(n,tree); /*生成n-1个内部结点*/ for(i=n+1;i<=m;i++){ huffmanNode x,y,z; x=popPrioQueue(h); y=popPrioQueue(h); z.f=x.f+y.f; z.lchild=x.i; z.rchild=y.i; z.parent=-1; z.i=i; tree[x.i].parent=i; tree[y.i].parent=i; tree[i]=z; pushPrioQueue(h,z); } /*前缀码生成*/ for(i=1;i<=n;i++){ char *c=(char *)malloc(sizeof(n)); int start=n-1; int j=i; if(c==NULL) { printf("out of space"); exit(-1); } c[n-1]='\0'; while(tree[j].parent!=-1){ if(tree[tree[j].parent].lchild==j)c[--start]='0'; else c[--start]='1'; j=tree[j].parent; } /*给编码申请空间*/ tree[i].code=(char *)malloc(sizeof(char)*(n-start)); strcpy(tree[i].code,c+start); } /*释放优先队列空间*/ free(h->element); free(h); return tree; }四、算法设计/问题求解特色及关键技术。

特点：随机生成权重 贪心算法：二叉树T表示字符集C的一个最优前缀码，证明可以对T作适当修改后得到一棵新的二叉树T”，在T”中x和y是最深叶子且为兄弟，同时T”表示的前缀码也是C的最优前缀码设b和c是二叉树T的最深叶子，且为兄弟设f(b)<=f(c)，f(x)<=f(y)由于x和y是C中具有最小频率的两个字符，有f(x)<=f(b)，f(y)<=f(c)首先，在树T中交换叶子b和x的位置得到T'，然后再树T'中交换叶子c和y的位置，得到树T''图2将原问题变为一个相似的、但规模更小的子问题、而后的每一步都是当前看似最佳的选择这种选择依赖于已做出的选择，但不依赖于未做出的选择//优先队列初始化 void pushPrioQueue(priorityqueue h,huffmanNode x){ int i; if(isFull(h)){ printf("队列已满\n"); return; } for(i=++h->size;h->element[i/2].f>x.f;i/=2){ h->element[i]=h->element[i/2];//父结点向下移 } h->element[i]=x; }五、算法测试。

图3六、结论根据各个字符的权值建立一颗哈夫曼树制作哈夫曼编码表，对数据文件的编码过程是：依次读人文件中的字符，在哈夫曼编码表中找到此字符，将字符转换为对应的哈夫曼编码对压缩后的数据文件进行解码则必须借助于哈夫曼树，其过程是：依次读人文件的二进制码，从哈夫曼树的根结点出发，若当前读入0，则走向左孩子，否则走向右孩子一旦到达某一叶子时便译出相应的字符然后重新从根出发继续译码，直至文件结束哈夫曼编码是动态变长编码，临时建立概率统计表和编码树概率小的码比较长，概率小的码比较长概率大的码短，这样把一篇文件编码后，就会压缩许多从树的角度看，哈夫曼编码方式是尽量把短码都利用上首先，把一阶节点全都用上，如果码字不够时，然后，再从某个节点伸出若干枝，引出二阶节点作为码字，以此类推，显然所得码长最短，再根据建立的概率统计表合理分布和放置，使其平均码长最短就可以得到最佳码该代码缺少可视化，缺乏实用性，不具有成为优秀代码的资格但该代码的构思独特，思路清晰，具有简约明了等特征，颇具使用性用取局部最优的贪心算法，更简单的将问题清晰化，更好的解决问题通过这次设计，我对二叉树和哈夫曼树有了更好的认识同时，在解决程序中遇到的一些问题的同时，我也对调试技巧有了更好的掌握，分析问题的能力也略有提高。

 需要我们有扎实的基础，需要有灵活的头脑，只有不断的练习，不断的训练，我们才能处理各种问题在以后的学习中，我要不断的努力，多联系，多思考，我相信我能有所进步的。