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

计算机算法设计与分析作业 题目描述： 哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%~90%之间。哈夫曼编码算法使用字符在文件中出现的频率来建立一个用0,1串表示各字符的最优表示方法。现在给定一串字符出现的频率，求出其哈夫曼编码。 。 2、问题分析： （1）根据伪代码，先来分析复杂度。 建立树从1到n-1需时间为O(n);从优先队列选择频度最小的点，实际优先队列就是一个堆，所以所需时间为O(logn);综合来看，该算法的时间复杂度为O（nlogn）。 （2）赫夫曼算法的正确性 1）具有贪心选择性质 设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、伪代码，算法思路： 假设C是一个包含n个字符的集合，且每个字符c属于C都是一个出现频度为f[c]的对象。算法以自底向上的方式构造出最有编码所对应的数T。Q是一个以f为关键字的最小优先队列。 Huffman(C) { n=|C| Push C into Q For i from 1 to n-1 Allocate a new node z,x,y x=EXTRACT-MIN(Q) y=EXTRACT-MIN(Q) Z.left=x; Z.right=y; F[z]=f[x]+f[y] Push z into Q Return EXTRACT-MIN(Q) } 4.源代码 #includeiostream #includestring #includemalloc.h #includequeue using namespace std; const int MAX=30; struct treeNode { char ch; int weight; treeNode *left; treeNode *right; }*node[MAX]; struct mycomp { bool operator ()(treeNode* a,treeNode *b) { return (a-weight)(b-weight); } }; treeNode *Huffman(priority_queuetreeNode*,vectortreeNode*,mycomp q) { int n=q.size(); for(int i=0;in-1;i++) { treeNode *z=(treeNode*)malloc(sizeof(treeNode)); treeNode *ln=(treeNode*)malloc(sizeof(treeNode)); treeNode *rn=(treeNode*)malloc(sizeof(treeNode)); ln=q.top(); q.pop(); rn=q.top(); q.pop(); z-left=ln; z-right=rn; z-weight=(z-left)-weight+(z-right)-weight; q.push(z); } return q.top(); } void dfs(treeNode *root,int mark[],int n) { if(root-left==NULL)//叶子节点 { coutroot-ch ; for(int i=0;in;i++) coutmark[i]; coutendl; return ; } mark[n]=0; dfs(root-left,mark,n+1); mark[n]=1; dfs(root-right,mark,n+1); } int main() { int n; priority