要解决的问题是关于霍夫曼树的,题目在:
http://acm.hdu.edu.cn/showproblem.php?pid=1053
直接写代码吧,不得不说写得真的很复杂,调试了半天,出了好多错哈:
#include<cstdio> #include<queue> #include<cstring> #include<string> using namespace std; const int R = 27; // A~Z, _ const int MAXLEN = 100; char str[MAXLEN]; class Item{ public: char ch; int freq; Item* left, *right; bool operator< (const Item i)const { return (this->freq > i.freq); } void clear() { ch = ' '; freq = 0; left = NULL; right = NULL; } Item(){} Item(char c, int f, Item* l, Item* r) { ch = c; freq = f; left = l; right = r; } }; priority_queue<Item> pq;// to implement the huffman trie string code; string ch[R]; // for implementing a codeword table Item item[R]; void clear() { code.clear(); while(!pq.empty()) pq.pop(); for(int i = 0; i < R; i++) { ch[i].clear(); item[i].clear(); } } void build_codetl(Item root) { // only one node if(root.left == NULL && root.right == NULL) { if(root.ch != '_') ch[root.ch - 'A'] = "0"; else ch[26] = "0"; return; } else build_codetl(root, code, ch); } void build_codetl(Item node, string code, string ch[]) { if(node.left == NULL && node.right == NULL) { if(node.ch != '_') ch[node.ch - 'A'] = code; else ch[26] = code; return; } build_codetl(*(node.left), code + "0", ch); build_codetl(*(node.right), code + "1", ch); } int main() { memset(str, 0, MAXLEN); while(scanf("%s", str) != EOF) { clear(); if(!strcmp(str, "END")) return 0; int slen = strlen(str); for(int i = 0; i < slen; i++) { if(str[i] != '_') { item[str[i] - 'A'].freq++; item[str[i] - 'A'].ch = str[i]; } else { item[26].freq++; item[26].ch = '_'; } } for(int i = 0; i < R; i++) if(item[i].freq != 0) pq.push(item[i]); while(pq.size() != 1) { Item *item1 = new Item(' ', 0, NULL, NULL); Item *item2 = new Item(' ', 0, NULL, NULL); Item *parent = new Item(' ', 0, NULL, NULL); *item1 = pq.top(); pq.pop(); *item2 = pq.top(); pq.pop(); parent->ch = ' '; parent->freq = item1->freq + item2->freq; parent->left = item1; parent->right = item2; pq.push(*parent); } build_codetl(pq.top()); int count = 0; for(int i = 0; i < R; i++) { count += ch[i].size() * item[i].freq; } printf("%d %d %.1f\n", slen*8, count, (slen*8.0) / count ); } return 0; }
这里的主要步骤是:1.统计字符及其出现的次数放到一个Item的对象中;2.为什么放到这样的对象中呢,因为是方便第二步的入队列,这里使用了一个优先级的队列,他们的优先级就是出现的频率,出现的频率越高,越是晚出队列;3,建立一个trie树,依次从队列中取出两个频率最低的元素,将其频率相加后再入队列,这样直到队列只剩下一个元素,这个元素就是trie树的根了;4,然后就是遍历trie树了,遍历的路径就是对应的huffman编码,分别给以存储就好了。这里用到两个函数,是因为假若输入的只有相同的元素的话,只有一个根节点,这样得不到正确的结果,因此对这种情况另外处理。
代码写得太罗嗦了。