学步园

题目非常长,大致看了下,赤裸裸的HUFFMAN树,是数据结构中很基础的东西了,以前写过求HUFFMAN编码的程序,但是感觉这题没有必要把HUFFMAN全部球出来,上网查了一下,找到了一种不错的解法,是使用优先队列来解的.

关于Huffman树有什么不了解的可以看这篇文章,讲解的很详细,http://blog.csdn.net/hairetz/archive/2009/05/05/4151866.aspx

另外优先队列priority_queue是STL库中的,包含在头文件<queue>中,会自动对新放入队列的数据进行排序,这里采用的是队头数最小的排序方式.每次取出前两个(也就是权值最小的两节点)构成新的节点,再放入队列中,直到取到最后一个为止,这也符合HUFFMAN树的构造过程..

//关于Huffman树<br /> #include <iostream><br /> #include <queue><br /> #include <cstdlib><br /> #include <cstdio><br /> #include <algorithm><br /> using namespace std;<br /> int cmp(const void *a,const void *b);<br /> int main(){<br /> string line;<br /> while(1){<br /> getline(cin,line);<br /> if(line=="END")break;<br /> priority_queue<int ,vector<int>,greater<int> > qu;<br /> //对字符数组排序并将字符个数依次放入优先队列中<br /> sort(line.begin(),line.end());<br /> char c=line[0];<br /> int times=0;<br /> for(int i=0;i<line.length();i++){<br /> if(line[i]==c)times++;<br /> else{<br /> qu.push(times);<br /> c=line[i];<br /> times=1;<br /> }<br /> }<br /> qu.push(times);<br /> int oldLen=line.length()*8;<br /> int newLen=0;<br /> //构造Huffman树的过程<br /> int a,b;<br /> if(qu.size()==1)newLen=qu.top();<br /> while(1){<br /> a=qu.top();<br /> qu.pop();<br /> if(qu.empty())break;<br /> b=qu.top();<br /> qu.pop();<br /> newLen+=a+b;//这一步很巧,因为编码长度和其在树中的层数相关<br /> qu.push(a+b);<br /> }<br /> printf("%d %d %.1f/n",oldLen,newLen,oldLen*1.0/newLen);<br /> }</p> <p> return 0;<br /> }