计算机算法设计与分析 赫夫曼编码

《计算机算法设计与分析 赫夫曼编码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机算法设计与分析作业1、题目描述：哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%~90%之间。哈夫曼编码算法使用字符在文件中出现的频率来建立一个用0,1串表示各字符的最优表示方法。现在给定一串字符出现的频率，求出其哈夫曼编码。。2、问题分析：（1）根据伪代码，先来分析复杂度。建立树从1到n-1需时间为O(n);从优先队列选择频度最小的点，实际优先队列就是一个堆，所以所需时间为O(logn);综合来看，该算法的时间复杂度为O（nlogn）。（2）赫夫曼算法的正确性1）具有贪心选择

2、性质设C是编码字符集，C中字符的频率为f(c),又设x和y是C中具有最小频率的两个字符，则存在C的最优前缀码使x和y具有相同码长且仅最后一位编码不同。2）具有最有子结构设T是表示字符集C的一个最优前缀码的完全二叉树。C中字符C的出现频率为f（c）。设x和y是树T种的两个叶子且为兄弟，z是它们的父亲。若将z看做是具有频率f(z)=f(x)+f(y)的字符，则树T’=T–{x,y}表示字符集C‘=C-{x,y}∪{z}的一个最优前缀码。贪心选择性质，贪心选择性所做的是一个非线性的子问题处理过程，即一个子问题并不依

3、赖于另一个子问题，但是子问题间有严格的顺序性。要证明一个问题具有“贪心选择性”，就必须证明每一步所做的贪心选择最终导致一个问题的整体最优解。这是必须的性质。具有最优子结构的性质，即每个子问题的最优解的集合就是整体最优解。这是必须的性质，因为贪心算法解决的问题流程就需要依序研究每个子问题，然后综合之得出最后结果。必须拥有最优子结构性质，才能保证贪心算法返回最优解。3、伪代码，算法思路：假设C是一个包含n个字符的集合，且每个字符c属于C都是一个出现频度为f[c]的对象。算法以自底向上的方式构造出最有编码所对应的数

4、T。Q是一个以f为关键字的最小优先队列。Huffman(C){n=

5、C

6、PushCintoQForifrom1ton-1Allocateanewnodez,x,yx=EXTRACT-MIN(Q)y=EXTRACT-MIN(Q)Z.left=x;Z.right=y;F[z]=f[x]+f[y]PushzintoQReturnEXTRACT-MIN(Q)}4.源代码#include#include#include#includeusingnam

7、espacestd;constintMAX=30;structtreeNode{charch;intweight;treeNode*left;treeNode*right;}*node[MAX];structmycomp{booloperator()(treeNode*a,treeNode*b){return(a->weight)>(b->weight);}};treeNode*Huffman(priority_queue,mycomp>q){intn=

8、q.size();for(inti=0;ileft=ln;z->right=rn;z->weight=(z->left)->w

9、eight+(z->right)->weight;q.push(z);}returnq.top();}voiddfs(treeNode*root,intmark[],intn){if(root->left==NULL)//叶子节点{cout<ch<<"";for(inti=0;ileft,mark,n+1);mark[n]=1;dfs(root->right,mark,n+1)

10、;}intmain(){intn;priority_queue,mycomp>pq;cout<<"输入需编码的元素的个数：";cin>>n;cout<<"分别输入各元素及其频度："<>node[i]