Huffman树实现文件压缩

【问题描述】给定一个文件，文件由n个字符组成，但他们出现的频度不相同。要求对该文件中的字符集构造哈夫曼树，并计算编码后的文件长度。 【输入形式】

输入的第1行有1个数字n，表示文件中总的字符个数。接下来1行中有n个数字，分别表示n个字符出现的频度。 【输出形式】

输出1行包含1个数字，表示使用哈夫曼编码后该文件的长度。 【样例输入】

5

20 7 10 4 18 【样例输出】

129 【样例说明】

使用哈夫曼编码后，各字符的编码长度分别为2 3 2 3 2，文件长度为2*20+3*7+2*10+3*4+2*18=129

注意事项:

①已经在结构体内部重载了"<",在声明堆(优先队列)时不需要再使用less,greater了

②在堆中取出结点时,注意每次都要new 出一个新的结点,而不是指向堆中的结点,因为堆中的结点的指针在函数执行完毕之后就释放了

错误的Huffman函数:

void Huffman() { for(int i = 1; i <= n; i++) printf("访问节点%d, value=%d\n", i, Huf[i].value); priority_queue <HuffmanNode> heap; for(int i = 1; i <= n; i++) heap.push(Huf[i]); priority_queue<HuffmanNode> tempheap = heap; while(tempheap.size()) { HuffmanNode t = tempheap.top(); tempheap.pop(); printf("heap:访问节点value=%d\n", t.value); } while(heap.size() > 1) { HuffmanNode* h1 = new HuffmanNode(heap.top()); heap.pop(); HuffmanNode* h2 = new HuffmanNode(heap.top()); heap.pop(); HuffmanNode t; t.value = h1->value + h2->value; t.LChild = h1; t.RChild = h2; printf("新构建结点t的左孩子的值为:%d, 右孩子的值为:%d\n", (t.LChild)->value, (t.RChild)->value); printf("value:取出的两个结点值为%d和%d, 新构建的结点t的值为%d\n", h1->value, h2->value, t.value); heap.push(t); }

正确代码: 

#include<iostream> #include<queue> using namespace std; const int N=100; int n,ans; struct HuffmanNode { int value,h; HuffmanNode* LChild,*RChild; bool operator<(const HuffmanNode &H)const { return value>H.value; } HuffmanNode():LChild(NULL),RChild(NULL),value(0),h(0) {} }Huf[N]; void getHeight(HuffmanNode *root, int h) { if (root != NULL) { // printf("getHeight:访问节点value=%d\n", root->value); // 如果有左子树，递归处理左子树 if (root->LChild != NULL) { getHeight(root->LChild, h + 1); } // 如果有右子树，递归处理右子树 if (root->RChild != NULL) { getHeight(root->RChild, h + 1); } // 如果是叶子节点，设置深度 if (root->LChild == NULL && root->RChild == NULL) { root->h = h; ans+=(root->value)*(root->h); // printf("叶子节点value=%d，深度=%d\n", root->value, root->h); } } } void Huffman() { // for(int i = 1; i <= n; i++) // printf("访问节点%d, value=%d\n", i, Huf[i].value); priority_queue <HuffmanNode> heap; for(int i = 1; i <= n; i++) heap.push(Huf[i]); // priority_queue<HuffmanNode> tempheap = heap; // // while(tempheap.size()) { // HuffmanNode t = tempheap.top(); // tempheap.pop(); // printf("heap:访问节点value=%d\n", t.value); // } while(heap.size() > 1) { HuffmanNode* h1 = new HuffmanNode(heap.top()); heap.pop(); HuffmanNode* h2 = new HuffmanNode(heap.top()); heap.pop(); HuffmanNode t; t.value = h1->value + h2->value; t.LChild = h1; t.RChild = h2; // printf("取出的两个结点值为%d和%d, 新构建的结点t的值为%d\n", (t.LChild)->value, (t.RChild)->value); heap.push(t); } HuffmanNode t = heap.top(); heap.pop(); // 这里将 root 指向堆中的对象 HuffmanNode* root = new HuffmanNode(t); getHeight(root, 0); // 记得释放动态分配的内存 delete root; } /* 5 20 7 10 4 18 */ int main() { cin>>n; for(int i=1;i<=n;i++) scanf("%d",&Huf[i].value); Huffman(); printf("%d\n",ans); return 0; }