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

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

概要：

项目简介：利用哈夫曼编码的方式对文件进行压缩，并且对压缩文件可以解压

开发环境：windows vs2013

项目概述：

        1.压缩

           a.读取文件，将每个字符，该字符出现的次数和权值构成哈夫曼树

           b.哈夫曼树是利用小堆构成，字符出现次数少的节点指针存在堆顶，出现次数多的在堆底

           c.每次取堆顶的两个数，再将两个数相加进堆，直到堆被取完，这时哈夫曼树也建成

           d.从哈夫曼树中获取哈夫曼编码，然后再根据整个字符数组来获取出现了得字符的编码

           e.获取编码后每次凑满8位就将编码串写入到压缩文件（value处理编码1与它即可，0只移动位）

            f.写好配置文件，统计每个字符及其出现次数，并以“字符+','+次数”的形式保存到配置文件中

        2.解压

            a.读取配置文件，统计所有字符的个数

            b.构建哈夫曼树，读解压缩文件，将所读到的编码字符的这个节点所所含的字符写入到解压缩文件中，知道将压缩文件读完

            c.压缩解压缩完全完成，进行小文件大文件的测试

实例代码：

#pragma once 
#include 
 
template 
struct Less 
{ 
  bool operator()(const T& l, const T& r) const 
  { 
    return l < r; 
  } 
}; 
 
template 
struct Greater 
{ 
  bool operator()(const T& l, const T& r) const 
  { 
    return l > r; 
  } 
}; 
 
template 
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 _array; 
 
 
}; 
 
 
 
 
void TestHeap() 
{ 
  int a[] = { 10, 11, 13, 12, 16, 18, 15, 17, 14, 19 }; 
  //Heap heap(a, sizeof(a) / sizeof(a[0])); 
  //Heap> heap(a, sizeof(a) / sizeof(a[0])); 
  Heap> heap(a, sizeof(a) / sizeof(a[0])); 
  heap.Print(); 
  heap.Push(25); 
  heap.Print(); 
  heap.Pop(); 
  heap.Print(); 
}

另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。