C++數(shù)據(jù)結(jié)構(gòu)之文件壓縮（哈夫曼樹）實例詳解

創(chuàng)新互聯(lián)公司是一家專注于網(wǎng)站設(shè)計制作、做網(wǎng)站與策劃設(shè)計,高縣網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)公司做網(wǎng)站,專注于網(wǎng)站建設(shè)10余年,網(wǎng)設(shè)計領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:高縣等地區(qū)。高縣做網(wǎng)站價格咨詢:18982081108

概要：

項目簡介：利用哈夫曼編碼的方式對文件進行壓縮，并且對壓縮文件可以解壓

開發(fā)環(huán)境：windows vs2013

項目概述：

        1.壓縮

           a.讀取文件，將每個字符，該字符出現(xiàn)的次數(shù)和權(quán)值構(gòu)成哈夫曼樹

           b.哈夫曼樹是利用小堆構(gòu)成，字符出現(xiàn)次數(shù)少的節(jié)點指針存在堆頂，出現(xiàn)次數(shù)多的在堆底

           c.每次取堆頂?shù)膬蓚€數(shù)，再將兩個數(shù)相加進堆，直到堆被取完，這時哈夫曼樹也建成

           d.從哈夫曼樹中獲取哈夫曼編碼，然后再根據(jù)整個字符數(shù)組來獲取出現(xiàn)了得字符的編碼

           e.獲取編碼后每次湊滿8位就將編碼串寫入到壓縮文件（value處理編碼1與它即可，0只移動位）

            f.寫好配置文件，統(tǒng)計每個字符及其出現(xiàn)次數(shù)，并以“字符+','+次數(shù)”的形式保存到配置文件中

        2.解壓

            a.讀取配置文件，統(tǒng)計所有字符的個數(shù)

            b.構(gòu)建哈夫曼樹，讀解壓縮文件，將所讀到的編碼字符的這個節(jié)點所所含的字符寫入到解壓縮文件中，知道將壓縮文件讀完

            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)  //上調(diào) 
  { 
    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)   //下調(diào) 
  { 
    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(); 
}

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站www.cdcxhl.com，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

分享標(biāo)題：C++數(shù)據(jù)結(jié)構(gòu)之文件壓縮（哈夫曼樹）實例詳解-創(chuàng)新互聯(lián)
文章路徑：http://weahome.cn/article/jgjdd.html