哈夫曼树 C++数据结构之文件压缩（哈夫曼树）实例详解

#pragma once 
#include<vector> 
 
template<class T> 
struct Less 
{ 
  bool operator()(const T& l, const T& r) const 
  { 
    return l < r; 
  } 
}; 
 
template<class T> 
struct Greater 
{ 
  bool operator()(const T& l, const T& r) const 
  { 
    return l > r; 
  } 
}; 
 
template<class T, class Compare> 
class Heap 
{ 
public: 
  Heap() 
  {} 
 
  Heap(T* array, size_t n)   //建堆 
  { 
    _array.reserve(n); 
 
    for (size_t i = 0; i < n; i++) 
    { 
      _array.push_back(array[i]); 
    } 
 
    for (int i = (_array.size() - 2) >> 1; i >= 0; --i) 
    { 
      _AdjustDown(i); 
    } 
  } 
 
  const T& Top()const 
  { 
    return _array[0]; 
  } 
 
  void Push(const T& x) 
  { 
    _array.push_back(x); 
    _AdjustUp(_array.size() - 1); 
  } 
 
  size_t Size() 
  { 
    return _array.size(); 
  } 
 
  void Pop() 
  { 
    assert(_array.size() > 0); 
    swap(_array[0], _array[_array.size() - 1]); 
    _array.pop_back(); 
    _AdjustDown(0); 
  } 
 
  bool Empty() 
  { 
    return _array.size() == 0; 
  } 
 
  void Print() 
  { 
    for (size_t i = 0; i < _array.size(); ++i) 
    { 
      cout << _array[i] << " "; 
    } 
    cout << endl; 
  } 
 
protected: 
  void _AdjustUp(int child)  //上调 
  { 
    Compare ComFunc; 
    int parent = (child - 1) >> 1; 
    while (child) 
    { 
      if (ComFunc(_array[child], _array[parent])) 
      { 
        swap(_array[child], _array[parent]); 
        child = parent; 
        parent = (child - 1) >> 1; 
      } 
      else 
      { 
        break; 
      } 
    } 
  } 
 
 
 
 
  void _AdjustDown(int root)   //下调 
  { 
    Compare ComFunc; 
    int parent = root; 
    int child = root * 2 + 1; 
    while (child < _array.size()) 
    { 
      if (child + 1 < _array.size() && ComFunc(_array[child + 1], _array[child])) 
      { 
        ++child; 
      } 
 
      if (ComFunc(_array[child], _array[parent])) 
      { 
        swap(_array[child], _array[parent]); 
        parent = child; 
        child = parent * 2 + 1; 
      } 
      else 
      { 
        break; 
      } 
    } 
  } 
 
 
 
protected: 
  vector<T> _array; 
 
 
}; 
 
 
 
 
void TestHeap() 
{ 
  int a[] = { 10, 11, 13, 12, 16, 18, 15, 17, 14, 19 }; 
  //Heap<int> heap(a, sizeof(a) / sizeof(a[0])); 
  //Heap<int, Less<int>> heap(a, sizeof(a) / sizeof(a[0])); 
  Heap<int, Greater<int>> heap(a, sizeof(a) / sizeof(a[0])); 
  heap.Print(); 
  heap.Push(25); 
  heap.Print(); 
  heap.Pop(); 
  heap.Print(); 
} 

#pragma once 
#include"Heap.h" 
 
template<class T> 
struct HuffmanTreeNode 
{ 
  HuffmanTreeNode<T>* _left; 
  HuffmanTreeNode<T>* _right; 
  HuffmanTreeNode<T>* _parent; 
  T _w;       //权值 
 
 
  HuffmanTreeNode(const T& x) 
    :_w(x) 
    , _left(NULL) 
    , _right(NULL) 
    , _parent(NULL) 
  {} 
 
}; 
 
template<class T> 
class HuffmanTree 
{ 
  typedef HuffmanTreeNode<T> Node; 
public: 
  HuffmanTree() 
    :_root(NULL) 
  {} 
 
  HuffmanTree(T* a, size_t n, const T& invalid = T())  //构建哈夫曼树 
  { 
    struct Compare 
    { 
      bool operator()(Node* l, Node* r) const 
      { 
        return l->_w < r->_w; 
      } 
    }; 
 
    Heap<Node*, Compare> minHeap; 
    for (size_t i = 0; i < n; ++i) 
    { 
      if (a[i] != invalid) 
      { 
        minHeap.Push(new Node(a[i])); 
      } 
    } 
 
    while (minHeap.Size() > 1) 
    { 
      Node* left = minHeap.Top(); 
      minHeap.Pop(); 
      Node* right = minHeap.Top(); 
      minHeap.Pop(); 
      Node* parent = new Node(left->_w + right->_w); 
      parent->_left = left; 
      parent->_right = right; 
      left->_parent = parent; 
      right->_parent = parent; 
      minHeap.Push(parent); 
    } 
    _root = minHeap.Top(); 
  } 
 
 
  Node* GetRoot() 
  { 
    return _root; 
  } 
 
  ~HuffmanTree() 
  { 
    _Destory(_root); 
  } 
 
 
 
 
 
protected: 
  void _Destory(Node* root) 
  { 
    if (root == NULL) 
    { 
      return; 
    } 
 
    _Destory(root->_left); 
    _Destory(root->_right); 
    delete root; 
  } 
 
  HuffmanTree(const HuffmanTree<T>& tree); 
  HuffmanTree& operator=(const HuffmanTree<T>& tree); 
 
protected: 
  Node* _root; 
 
}; 
 
 
void TestHuffmanTree() 
{<pre code_snippet_id="2340790" snippet_file_name="blog_20170418_2_3778260" name="code" class="cpp">#pragma once 
 
#include<iostream> 
using namespace std; 
#include<assert.h> 
#include"HuffmanTree.h" 
 
 
typedef long long LongType; 
struct CharInfo    
{ 
  unsigned char _ch;     //字符 
  LongType _count;     //字符出现的次数 
  string _code;      //huffman编码 
 
  CharInfo(LongType count = 0) 
    :_count(count) 
    , _ch(0) 
    , _code("") 
  {} 
 
 
  bool operator<(const CharInfo& info) const 
  { 
    return _count < info._count; 
  } 
 
  CharInfo operator+(const CharInfo& info) 
  { 
    return CharInfo(_count + info._count); 
  } 
 
  bool operator!=(const CharInfo& info)const 
  { 
    return _count != info._count; 
  } 
}; 
 
 
struct CountInfo 
{ 
  unsigned char _ch;    //字符 
  LongType _count;     //字符出现的次数 
}; 
 
 
 
 
class FileCompress 
{ 
public: 
  FileCompress() 
  { 
    for (size_t i = 0; i < 256; ++i) 
    { 
      _info[i]._ch = i; 
    } 
  } 
 
  void Compress(const char* filename) 
  { 
    assert(filename); 
     
    //统计字符出现的次数，均已二进制方式读写 
    FILE* fout = fopen(filename, "rb"); 
    assert(fout); 
    int ch = fgetc(fout); 
 
    string CompressFile = filename; 
    CompressFile += ".huffman"; 
    FILE* fin = fopen(CompressFile.c_str(), "wb"); 
    assert(fin); 
    CountInfo info; 
 
 
    while (ch != EOF) 
    { 
      _info[(unsigned char)ch]._count++; 
      ch = fgetc(fout); 
    } 
 
    //构建huffman tree 
    CharInfo invalid; 
    invalid._count = 0; 
    HuffmanTree<CharInfo> tree(_info, 256, invalid); 
 
    //生成huffman code 
    GetHuffmanCode(tree.GetRoot()); 
 
    //压缩 
    //写配置文件 
    for (size_t i = 0; i < 256; ++i) 
    { 
      if (_info[i]._count) 
      { 
        info._ch = _info[i]._ch; 
        info._count = _info[i]._count; 
        fwrite(&info, sizeof(info), 1, fin); 
      } 
    } 
 
    info._count = -1; 
    fwrite(&info, sizeof(info), 1, fin); 
 
    fseek(fout, 0, SEEK_SET);   //返回到文件开始 
    ch = fgetc(fout); 
    char value = 0;     //二进制 
    int pos = 0;    //左移位数 
    while (ch != EOF) 
    { 
      string& code = _info[(unsigned char)ch]._code; 
      size_t i = 0; 
      for (i = 0; i < code.size(); ++i) 
      { 
        value <<= 1; 
        ++pos; 
        if (code[i] == '1') 
        { 
          value |= 1; 
        } 
        if (pos == 8)       //满8位写进文件中 
        { 
          fputc(value, fin); 
          value = 0; 
          pos = 0; 
        } 
      } 
      ch = fgetc(fout); 
    } 
    if (pos) 
    { 
      value <<= (8 - pos); 
      fputc(value, fin); 
    } 
    fclose(fin); 
    fclose(fout); 
  } 
 
  void GetHuffmanCode(HuffmanTreeNode<CharInfo>* root)    //huffman编码 
  { 
    if (root == NULL) 
    { 
      return; 
    } 
 
    if (root->_left == NULL && root->_right == NULL) 
    { 
      HuffmanTreeNode<CharInfo> *parent, *cur; 
      cur = root; 
      parent = cur->_parent; 
      string& code = _info[(unsigned char)root->_w._ch]._code; 
      while (parent) 
      { 
        if (cur == parent->_left) 
        { 
          code += '0'; 
        } 
        else 
        { 
          code += '1'; 
        } 
        cur = parent; 
        parent = cur->_parent; 
      } 
      reverse(code.begin(), code.end()); 
    } 
    GetHuffmanCode(root->_left); 
    GetHuffmanCode(root->_right); 
  } 
 
  //解压 
  void UnCompress(const char* filename) 
  { 
    assert(filename); 
    string UnCompressFile = filename; 
    size_t index = UnCompressFile.rfind('.'); 
    assert(index != string::npos); 
    UnCompressFile = UnCompressFile.substr(0, index); 
    UnCompressFile += ".unhuffman"; 
    FILE* fout = fopen(filename, "rb"); 
    assert(fout); 
    FILE* fin = fopen(UnCompressFile.c_str(), "wb"); 
    assert(fin); 
    CountInfo info; 
    fread(&info, sizeof(CountInfo), 1, fout); 
 
    //读配置信息 
    while (1) 
    { 
      fread(&info, sizeof(CountInfo), 1, fout); 
      if (info._count == -1) 
      { 
        break; 
      } 
      _info[(unsigned char)info._ch]._ch = info._ch; 
      _info[(unsigned char)info._ch]._count = info._count; 
    } 
 
    //重建huffman树 
    CharInfo invalid; 
    invalid._count = 0; 
    HuffmanTree<CharInfo> tree(_info, 256, invalid); 
    HuffmanTreeNode<CharInfo>* root = tree.GetRoot(); 
    HuffmanTreeNode<CharInfo>* cur = root; 
    LongType count = root->_w._count; 
    int value = fgetc(fout); 
 
    if (value == EOF)       //只有一种字符 
    { 
      if (info._ch != 0) 
      { 
        while (cur->_w._count--) 
        { 
          fputc(cur->_w._ch, fin); 
        } 
      } 
    } 
    else 
    { 
      while (value != EOF) 
      { 
        int pos = 7; 
        char test = 1; 
        while (pos >= 0) 
        { 
          if (value & (test << pos)) 
          { 
            cur = cur->_right; 
          } 
          else 
          { 
            cur = cur->_left; 
          } 
          if (cur->_left == NULL && cur->_right == NULL) 
          { 
            fputc(cur->_w._ch, fin); 
            cur = root; 
            if (--count == 0) 
            { 
              break; 
            } 
          } 
          --pos; 
        } 
        value = fgetc(fout); 
      } 
    } 
 
    fclose(fout); 
    fclose(fin); 
  } 
 
protected: 
  CharInfo _info[256];   //所有字符信息 
}; 
 
void TestFileCompress() 
{ 
  FileCompress fc; 
  //fc.Compress("实验.doc"); 
  //fc.UnCompress("实验.doc.huffman"); 
  //fc.Compress("qq.JPG"); 
  //fc.UnCompress("qq.JPG.huffman"); 
  //fc.Compress("www.MP3"); 
  //fc.UnCompress("www.MP3.huffman"); 
 
  fc.Compress("yppppp.txt"); 
  fc.UnCompress("yppppp.txt.huffman"); 
}</pre><br> 
int array[10] = { 2, 4, 6, 9, 7, 8, 5, 0, 1, 3 };HuffmanTree<int> t(array, 10);} 
<pre></pre> 
<p></p> 
<pre></pre> 
<p></p> 
<p></p> 
<p></p> 
<pre code_snippet_id="2340790" snippet_file_name="blog_20170418_3_1128302" name="code" class="cpp">#include <iostream> 
#include <assert.h> 
#include <windows.h> 
using namespace std; 
 
#include"Heap.h" 
#include"HuffmanTree.h" 
#include"FileCompress.h" 
 
int main() 
{ 
  //TestHeap();   
  TestHuffmanTree(); 
  TestFileCompress(); 
 
 
  system("pause"); 
  return 0; 
}</pre><br> 
<br> 
<p></p> 
<p><br> 
</p> 
<p><br> 
</p> 
<link rel="stylesheet" href="http://static.blog.csdn.net/public/res-min/markdown_views.css?v=1.0" rel="external nofollow" >