# 不过一笑

Well life is tough,make a good laugh

C++博客 :: 首页 :: 联系 :: 聚合 :: 管理
 8 Posts :: 0 Stories :: 1 Comments :: 0 Trackbacks

### 公告

This guy's no expert,he's just to build a solid foundation,that may turn out to be useful in the future

•

### 评论排行榜

HOJ1065--Entropy
Analysis:
This problem requires that we find the optimal coding strategy for a given string,and compare the length of the code by bits with the length when using the ASCII(8-bit) code.Apparently,we know that the optimal coding strategy will be the Huffman Coding.
Huffman Coding has been proved to be the most efficient way of coding,in terms of prefix-free encoding.The idea is quite simple.Given a set of characters,and the frequncies of appearance in the given string(or we can find that out easily if it's not given),we constantly apply the following rule to encode the whole thing:First we find the two characters with the lowest frequencies,and let them be the children in a binary tree,with their father having the frequency equal to the sum of the two frequencies.Then we keep doing this until we build a Binary Tree,which is called in this case,a Huffman Tree.Mission accomplished!If we want to know exactly the code for each character,we assign the edge between father and its left child the value 0,and the other edge value 1.Thus we can get the code by following the path from each leaf to the root.If we want to know the total code length of the whole string,we then make a sum of the code length of each character multiplied by its frequency.OK,problem solved!
Code:
1 #include<iostream>
2 #include<cstring>
3 #include<algorithm>
4 using namespace std;
5 const int MAXSIZE=20001;
6 struct elementype
7 {
8     int value;
9     int lchild,rchild;
10     bool isleaf;
11     int rank;
12 }pool[MAXSIZE];
13 struct HEAP
14 {
15     int n;
16     int elements[MAXSIZE];
17 }heap;
18 void MakeHeap()
19 {
20     heap.n=0;
21 }
22 bool HeapEmpty()
23 {
24     return (!heap.n);
25 }
26 bool HeapFull()
27 {
28     return heap.n==MAXSIZE-1;
29 }
30 int HeapSize()
31 {
32     return heap.n;
33 }
34 void Insert_Heap(int element)
35 {
36     int i;
37     if(!HeapFull())
38     {
39         i=++heap.n;
40         while(i>1 && pool[element].value < pool[heap.elements[i/2]].value)
41         {
42             heap.elements[i]=heap.elements[i/2];
43             i/=2;
44         }
45     }//Insert strategy,put the new element at the bottom and move it up according to its value
46      //compared with its father
47     heap.elements[i]=element;
48 }
49 int Delete_Heap()
50 {
51     int parent=1,child=2;
52     int tmp,result;
53     if(!HeapEmpty())
54     {
55         result=heap.elements;//remove the element on top
56         tmp=heap.elements[heap.n--];//put the last element on top temporarily
57         while(child<=heap.n)
58         {
59             if(child<heap.n && pool[heap.elements[child+1]].value<pool[heap.elements[child]].value)
60             {
61                 child++;
62             }//compare each node with the larger one of its children
63             if(pool[tmp].value<=pool[heap.elements[child]].value) break;//put the element where it belongs
64             heap.elements[parent]=heap.elements[child];//if the child has a larger value,make it father
65             parent=child;
66             child*=2;
67         }
68         heap.elements[parent]=tmp;
69     }
70     return result;
71 }
72 double s;
73 void Preorder(int root)
74 {
75     if(pool[root].isleaf)
76     {
77         s+=pool[root].value*pool[root].rank;
78     }
79     else
80     {
81         pool[pool[root].lchild].rank=pool[pool[root].rchild].rank=pool[root].rank+1;
82         Preorder(pool[root].lchild);
83         Preorder(pool[root].rchild);
84     }
85 }
86 char op;
87 int main()
88 {
89     int n,k,p1,p2;
90     while(gets(op))
91     {
92         if(strcmp(op,"END")==0break;
93         MakeHeap();
94         n=(int)strlen(op);
95         sort(op,op+n);
96         char cur=op;int counter=0;k=1;
97         for(int i=0;i<=n;i++)
98         {
99             if(cur!=op[i])
100             {
101                 cur=op[i];
102                 pool[k].value=counter;
103                 pool[k].lchild=pool[k].rchild=k;
104                 pool[k].isleaf=true;Insert_Heap(k);k++;
105                 counter=1;
106             }
107             else counter++;
108         }
109         if(k==2)
110         {
111             printf("%d %d %.1lf\n",8*n,n,8.0);
112             continue;
113         }
114         while(1)
115         {
116             p1=Delete_Heap();p2=Delete_Heap();
117             pool[k].lchild=p1;pool[k].rchild=p2;pool[k].value=pool[p1].value+pool[p2].value;
118             pool[k].isleaf=false;
119             if(HeapEmpty())
120                 break;
121             else
122             {
123                 Insert_Heap(k);
124                 k++;
125             }
126         }
127         pool[k].rank=0,s=0;
128         Preorder(k);
129         printf("%d %.0lf %.1lf\n",8*n,s,(double)(8*n)/s);
130         //getchar();
131     }
132     return 0;
133 }
134
135
Note that,when trying to find the two characters with the lowest frequencies,we use a Binary Heap here.This task can also be completed by other methods.

posted on 2010-09-02 00:01 雨过有声 阅读(439) 评论(0)  编辑 收藏 引用 所属分类: ACM-ICPC 只有注册用户登录后才能发表评论。 【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库 相关文章: