andalousie 发表于 2014-2-28 22:19:33

两种风格的Huffman编码(C++版)

最近几天在搞Huffman coding。现在给出两个版本的解决方案都是使用了优先队列。输入数据的运算量是N,Huffman树的运算量是RlogR。第一个版本有decode,但是decode需要根据writeTrie的结果来建立树,进而decode。采用preorder(前序)遍历。

(一)由Java翻译成的C++,但是有所修改(vc6.0亲测可行)
Huffman.cpp
#include <iostream>
#include <string>
#include "GPQ.h"

const int R = 256;

class Huffman
{
        class Node
        {
        public:
                const char _ch;
                const int    _freq;
                Node *_left, *_right;

                Node(char ch, int freq, Node* left, Node* right)
                        : _ch(ch), _freq(freq), _left(left), _right(right)
                {}
                bool isLeaf() { return !_left && !_right; }
                bool compareTo(Node *that){ return _freq > that->_freq; }
        };
        struct buf
        {
                buf(): _id(-1) {}
                int index() { _id++; return _id; }
                int _id;
        }id;
public:
        void expand(std::string& trie, std::string& s, int N)
        {
                id._id = -1;
                Node *root = readTrie(trie);

                id._id = -1;
                for (int i = 0; i < N; ++i)
                {
                        Node *x = root;
                        while (!(x->isLeaf()))
                        {
                                if(s == '0')
                                        x = x->_left;
                                elsex = x->_right;
                        }
                        std::cout << x->_ch;
                }
        }
        void writeTrie(Node* x)
        {
                if(x->isLeaf())
                {
                        std::cout << 1;
                        std::cout << x->_ch;
                        return;
                }
                std::cout << 0;
                writeTrie(x->_left);
                writeTrie(x->_right);
        }
        Node* readTrie(std::string& trie)
        {
                if(trie == '1')
                {
                        char c = trie;
                        Node *fresh = new Node(c, 0, 0, 0);
                        return fresh;
                }
                Node *x = readTrie(trie);
                Node *y = readTrie(trie);
                Node *fresh = new Node('\0', 0, x, y);
                return fresh;
        }
        void compress(std::string& s)
        {
                // Tabulate frequency counts.
                int freq = {0};
                for (int i = 0; i < s.size(); ++i)
                        freq]++;

                // Build Huffman code trie.
                Node *root = buildTrie(freq);

                std::string *st = new std::string ;
                buildCode(st, root, "");

                // Print trie for decoder (recursive).
                writeTrie(root);
                std::cout << std::endl;

                // Use Huffman code to encode input.
                for (int id = 0; id < s.length(); id++)
                {
                        std::string code = st];
                        std::cout << s << " ";
                        std::cout << code << std::endl;
                }
        }
private:
        Node* buildTrie(int *freq)
        {
                GenericPQ<Node*> pq(R);
                for (int i = 0; i < R; i++)
                        if (freq > 0)
                                pq.insert(new Node(i, freq, 0, 0));
                while (pq.size() > 1)
                {
                        Node *x = pq.pop();
                        Node *y = pq.pop();
                        Node *parent = new Node('\0', x->_freq + y->_freq, x, y);
                        pq.insert(parent);
                }
                return pq.pop();
        }
        std::string* buildCode(Node* root)
        {
                std::string *st = new std::string;
                buildCode(st, root, "");
                return st;
        }
        void buildCode(std::string *st, Node *x, std::string s)
        {
                if(x->isLeaf()) { st = s; return; }
                buildCode(st, x->_left, s + '0');
                buildCode(st, x->_right, s + '1');
        }
};

int main()
{
        Huffman code;
        std::string sample = "ABRACADABRA!";
        std::string trie = "01A001D01!1C01R1B";
        std::string coder= "0111110010110100011111001010";
        code.compress(sample);
        code.expand(trie, coder, 12);
    return 0;
}GPQ.h
#if !defined (GPQ_H)
#define GPQ_H

template<class T>
class GenericPQ{
private:
        T    *_pq;               // heap-ordered complete binary tree
        int_N;                  // in pq with pq unused
public:
        GenericPQ(int capacity);
        ~GenericPQ();
        bool isEmpty() { return _N == 0; }
        void insert(T x);
        int   size() { return _N; }
        T    pop();
private:
        void swim(int k);
        void sink(int k);
        //Compare and exchange methods for heap implementations
        bool comp(int i, int j) { return _pq->compareTo(_pq); }
        void swap(int i, int j)
        {
                T ex   = _pq;
                _pq = _pq;
                _pq = ex;
        }
};

template<class T>
GenericPQ<T>::GenericPQ(int capacity)
:_N(0)
{
        _pq = new T;
}

template<class T>
GenericPQ<T>::~GenericPQ(void)
{
        delete [] _pq;
}

/** Bottom-up reheapify (swim) implementation */
template<class T>
void GenericPQ<T>::swim(int k)
{
        while (k > 1 && comp(k/2, k))
        {
                swap(k, k/2);
                k = k/2;
        }
}

template<class T>
void GenericPQ<T>::insert(T x)
{
        _pq[++_N] = x;
        swim(_N);
}

/** Top-down reheapify (sink) implementation **/
template<class T>
void GenericPQ<T>::sink(int k)
{
        while (2*k <= _N)
        {
                int j = 2*k;
                if (j < _N && comp(j, j+1)) j++;
                if (!comp(k, j)) break;
                swap(k, j);
                k = j;
        }
}

template<class T>
T GenericPQ<T>::pop()
{
        T min = _pq;          // Retrieve max key from top.
        swap(1, _N--);         // Exchange with last item.
        sink(1);               // Avoid loitering.
        _pq = 0;    // Restore heap property.
        return min;
}

#endif(二)比较本土的C++泛型编程(g++可行,vc6不行,更高版本的vc未测试)
#include <iostream>
#include <queue>
#include <map>
#include <climits> // for CHAR_BIT
#include <iterator>
#include <algorithm>

const int UniqueSymbols = 1 << CHAR_BIT;
const char* SampleString = "this is an example for huffman encoding";

typedef std::vector<bool> HuffCode;
typedef std::map<char, HuffCode> HuffCodeMap;

class INode
{
public:
    const int f;

    virtual ~INode() {}

protected:
    INode(int f) : f(f) {}
};

class InternalNode : public INode
{
public:
    INode *const left;
    INode *const right;

    InternalNode(INode* c0, INode* c1) : INode(c0->f + c1->f), left(c0), right(c1) {}
    ~InternalNode()
    {
      delete left;
      delete right;
    }
};

class LeafNode : public INode
{
public:
    const char c;

    LeafNode(int f, char c) : INode(f), c(c) {}
};

struct NodeCmp
{
    bool operator()(const INode* lhs, const INode* rhs) const { return lhs->f > rhs->f; }
};

INode* BuildTree(const int (&frequencies))
{
    std::priority_queue<INode*, std::vector<INode*>, NodeCmp> trees;

    for (int i = 0; i < UniqueSymbols; ++i)
    {
      if(frequencies != 0)
            trees.push(new LeafNode(frequencies, (char)i));
    }
    while (trees.size() > 1)
    {
      INode* childR = trees.top();
      trees.pop();

      INode* childL = trees.top();
      trees.pop();

      INode* parent = new InternalNode(childR, childL);
      trees.push(parent);
    }
    return trees.top();
}

void GenerateCodes(const INode* node, const HuffCode& prefix, HuffCodeMap& outCodes)
{
    if (const LeafNode* lf = dynamic_cast<const LeafNode*>(node))
    {
      outCodes = prefix;
    }
    else if (const InternalNode* in = dynamic_cast<const InternalNode*>(node))
    {
      HuffCode leftPrefix = prefix;
      leftPrefix.push_back(false);
      GenerateCodes(in->left, leftPrefix, outCodes);

      HuffCode rightPrefix = prefix;
      rightPrefix.push_back(true);
      GenerateCodes(in->right, rightPrefix, outCodes);
    }
}

int main()
{
    // Build frequency table
    int frequencies = {0};
    const char* ptr = SampleString;
    while (*ptr != '\0')
      ++frequencies[*ptr++];

    INode* root = BuildTree(frequencies);

    HuffCodeMap codes;
    GenerateCodes(root, HuffCode(), codes);
    delete root;

    for (HuffCodeMap::const_iterator it = codes.begin(); it != codes.end(); ++it)
    {
      std::cout << it->first << " ";
      std::copy(it->second.begin(), it->second.end(),
                  std::ostream_iterator<bool>(std::cout));
      std::cout << std::endl;
    }
    return 0;
}

yuzhouliu2000 发表于 2014-3-1 08:28:17

涨姿势了,谢谢

andalousie 发表于 2014-3-6 23:08:30

看到一个真正让我佩服的Huffman压缩的代码。大家可以看一下~ 写的很全面#pragma warning (disable: 4786)

#include <math.h>
#include <stdlib.h>

#ifdef USE_DOT_H
    #include <iostream.h>
    #include <fstream.h>
    #define USE_STR_DOT_H
#else
    #include <fstream>
    #include <iostream>
    #if !defined( __BORLANDC__ ) || __BORLANDC__ >= 0x0530
      using namespace std;
    #else
      #define USE_STR_DOT_H
    #endif
#endif


#ifndef SAFE_STL
    #include <map>
    #include <vector>
    #include <string>
    #include <queue>
    #include <functional>
    #include <algorithm>
    using namespace std;
#else
    #include "map.h"
    #include "vector.h"
    #include "string.h"
    #include "queue.h"
    #include "functional.h"
    #include "algorithm.h"
    #include "StartConv.h"
#endif


#include "Wrapper.h"

class ibstream
{
public:
    ibstream( istream & is );

    int readBit( );
    istream & getInputStream( ) const;

private:
    istream & in;
    char buffer;
    int bufferPos;
};


class obstream
{
public:
    obstream( ostream & os );
    ~obstream( );

    void writeBit( int val );
    void writeBits( const vector<int> & val );
    ostream & getOutputStream( ) const;
    void flush( );

private:
    ostream & out;
    char buffer;
    int bufferPos;
};



class CharCounter
{
public:
    CharCounter( );
    CharCounter( istream & input );

    int getCount( char ch );
    void setCount( char ch, int count );

private:
    map<char,int,less<char> > theCounts;
};


struct HuffNode
{
    HuffNode *left;
    HuffNode *right;
    HuffNode *parent;
    int value;
    int weight;

    HuffNode( int v, int w, HuffNode *lt, HuffNode *rt, HuffNode *pt )
      : value( v ), weight( w ), left( lt ), right( rt ), parent( pt ) { }
};


class HuffmanTree
{
public:
    HuffmanTree( );
    HuffmanTree( const CharCounter & cc );

    enum { ERROR = -3, INCOMPLETE_CODE = -2, END = -1 };

      // Here, vector<int> is usable by ibstream and obstreams
    vector<int> getCode( int ch );
    int getChar( const vector<int> & code ) const;

      // Write the encoding table using character counts
    void writeEncodingTable( ostream & out );
    void readEncodingTable( istream & in );

private:
    CharCounter theCounts;
    map<int,HuffNode *,less<int> > theNodes;
    HuffNode *root;

    void createTree( );
    vector<int> getCode( HuffNode *current );
};

class Compressor
{
public:
    static void compress( const string & inFile );
    static void uncompress( const string & compressedFile );
};

static const int BITS_PER_CHAR = 8;
static const int DIFF_CHARS = 256;
static const int READ_MODE = ios::in | ios::binary;
static const int WRITE_MODE = ios::out | ios::binary;

int getBit( char pack, int pos )
{
    return ( pack & ( 1 << pos ) ) ? 1 : 0;
}

void setBit( char & pack, int pos, int val )
{
    if( val == 1 )
      pack |= ( val << pos );
}

ibstream::ibstream( istream & is ) : bufferPos( BITS_PER_CHAR ), in( is )
{
}

int ibstream::readBit( )
{
    if( bufferPos == BITS_PER_CHAR )
    {
      in.get( buffer );
      if( in.eof( ) )
            return EOF;
      bufferPos = 0;
    }

    return getBit( buffer, bufferPos++ );
}

istream & ibstream::getInputStream( ) const
{
    return in;
}


obstream::obstream( ostream & os ) : bufferPos( 0 ), buffer( 0 ), out( os )
{
}

obstream::~obstream( )
{
    flush( );
}

void obstream::flush( )
{
    if( bufferPos == 0 )
      return;

    out.put( buffer );
    bufferPos = 0;
    buffer = 0;
}

void obstream::writeBit( int val )
{
    setBit( buffer, bufferPos++, val );
    if( bufferPos == BITS_PER_CHAR )
      flush( );
}

void obstream::writeBits( const vector<int> & val )
{
    for( int i = 0; i < val.size( ); i++ )
      writeBit( val[ i ] );
}

ostream & obstream::getOutputStream( ) const
{
    return out;
}



CharCounter::CharCounter( )
{
}

CharCounter::CharCounter( istream & input )
{
    char ch;
    while( !input.get( ch ).eof( ) )
      theCounts[ ch ]++;
}


int CharCounter::getCount( char ch )
{
    return theCounts[ ch ];
}

void CharCounter::setCount( char ch, int count )
{
    theCounts[ ch ] = count;
}


HuffmanTree::HuffmanTree( const CharCounter & cc ) : theCounts( cc )
{
    root = NULL;
    createTree( );
}

HuffmanTree::HuffmanTree( )
{
    root = NULL;
}

vector<int> HuffmanTree::getCode( int ch )
{
    if( root == NULL )
      return vector<int>( );
    return getCode( theNodes[ ch ] );
}

vector<int> HuffmanTree::getCode( HuffNode *current )
{
    vector<int> v;
    HuffNode *par = current->parent;   

    while( par != NULL )
    {
      if( par->left == current )
            v.push_back( 0 );
      else
            v.push_back( 1 );
      current = current->parent;
      par = current->parent;   
    }
    reverse( v.begin( ), v.end( ) );
    return v;
}

int HuffmanTree::getChar( const vector<int> & code ) const
{
    HuffNode *p = root;
    for( int i = 0; p != NULL && i < code.size( ); i++ )
      if( code[ i ] == 0 )
            p = p->left;
      else
            p = p->right;

    if( p == NULL )
      return ERROR;
    return p->value;
}

void HuffmanTree::writeEncodingTable( ostream & out )
{
    for( int i = 0; i < DIFF_CHARS; i++ )
      if( theCounts.getCount( i ) > 0 )
            out << static_cast<char>( i ) << theCounts.getCount( i ) << endl;
    out << '\0' << 0 << endl;
}

void HuffmanTree::readEncodingTable( istream & in )
{
    for( int i = 0; i < DIFF_CHARS; i++ )
      theCounts.setCount( i, 0 );

    char ch;
    int num;
    char nl;

    for( ; ; )
    {
      in.get( ch );
      in >> num;
      in.get( nl );
      if( num == 0 )
            break;
      theCounts.setCount( ch, num );
    }
    createTree( );
}


bool operator< ( const HuffNode & lhs, const HuffNode & rhs )
{
    return lhs.weight > rhs.weight;
}

void HuffmanTree::createTree( )
{
    priority_queue<Pointer<HuffNode>, vector<Pointer<HuffNode> >,
                   less<Pointer<HuffNode> > > pq;

    for( int i = 0; i < DIFF_CHARS; i++ )
      if( theCounts.getCount( i ) > 0 )
      {
            HuffNode *newNode = new HuffNode( i, theCounts.getCount( i ), NULL, NULL, NULL );
            theNodes[ i ] = newNode;
            pq.push( Pointer<HuffNode>( newNode ) );
      }

    theNodes[ END ] = new HuffNode( END, 1, NULL, NULL, NULL );
    pq.push( Pointer<HuffNode>( theNodes[ END ] ) );

    while( pq.size( ) > 1 )
    {
      HuffNode *n1 = pq.top( ); pq.pop( );
      HuffNode *n2 = pq.top( ); pq.pop( );
      HuffNode *result = new HuffNode( INCOMPLETE_CODE, n1->weight + n2->weight, n1, n2, NULL );
      n1->parent = n2->parent = result;
      pq.push( Pointer<HuffNode>( result ) );
    }

    root = pq.top( );
}


void Compressor::compress( const string & inFile )
{
    string compressedFile = inFile + ".huf";
    ifstream in( inFile.c_str( ), READ_MODE );

    CharCounter countObj( in );
    HuffmanTree codeTree( countObj );

    ofstream out( compressedFile.c_str( ), WRITE_MODE );
    codeTree.writeEncodingTable( out );
    obstream bout( out );

    in.clear( ); in.seekg( 0, ios::beg ); // Rewind the stream

    char ch;
    while( in.get( ch ) )
      bout.writeBits( codeTree.getCode( ch & (0xff) ) );
   
    bout.writeBits( codeTree.getCode( EOF ) );
}

void Compressor::uncompress( const string & compressedFile )
{
    int i;
    string inFile;
    string extension;

    for( i = 0; i < compressedFile.length( ) - 4; i++ )
      inFile += compressedFile[ i ];

    for( ; i < compressedFile.length( ); i++ )
      extension += compressedFile[ i ];

    if( extension != ".huf" )
    {
      cerr << "Not a compressed file" << endl;
      return;
    }

    inFile += ".uc";// for debugging, so as to not clobber original
    ifstream in( compressedFile.c_str( ), READ_MODE );
    ofstream out( inFile.c_str( ), WRITE_MODE );

    HuffmanTree codeTree;
    codeTree.readEncodingTable( in );

    ibstream bin( in );
    vector<int> bits;
    int bit;
    int decode;

    for( ; ; )
    {
      bit = bin.readBit( );
      bits.push_back( bit );

      decode = codeTree.getChar( bits );
      if( decode == HuffmanTree::INCOMPLETE_CODE )
            continue;
      else if( decode == HuffmanTree::ERROR )
      {
            cerr << "Error decoding!" << endl;
            break;
      }
      else if( decode == HuffmanTree::END )
            break;
      else
      {
            out.put( static_cast<char>( decode ) );
            bits.resize( 0 );
      }
    }
}

int main( int argc, char *argv[] )
{
    if( argc < 3 )
    {
      cerr << "Usage: " << argv << " - files" << endl;
      return 1;
    }

    string option= argv[ 1 ];

    for( int i = 2; i < argc; i++ )
    {
      string nextFile = argv[ i ];
      if( option == "-c" )
            Compressor::compress( nextFile );
      else if( option == "-u" )
            Compressor::uncompress( nextFile );
      else
      {
            cerr << "Usage: " << argv << " - files" << endl;
            return 1;
      }
    }

    return 0;
}


#ifdef SAFE_STL
    #include "EndConv.h"
#endif

柠“萌”圆 发表于 2014-3-9 11:43:29

我也在用C++写这个。。。。。。
某百科说啥不用STL库。。。。。。目前只实现了优先级队列。。。。。。

枫界易城 发表于 2014-3-9 12:47:21

哇,,,,,代码也太长了吧,,,,,,,,,,,,,

andalousie 发表于 2014-3-10 16:10:36

柠“萌”圆 发表于 2014-3-9 11:43 static/image/common/back.gif
我也在用C++写这个。。。。。。
某百科说啥不用STL库。。。。。。目前只实现了优先级队列。。。。。。

加油加油,我写了不短时间。

柠“萌”圆 发表于 2014-3-15 21:59:45

andalousie 发表于 2014-3-10 16:10 static/image/common/back.gif
加油加油,我写了不短时间。
我目前写了这么多,看看你能不能找出问题(其实我也不知道问题在哪,没有测试过)
编译这些代码需要编译器支持C++11
main()函数是空的,没写,就不发了
这些代码在我的编译器上能编译成功#ifndef SORT_H_INCLUDED
#define SORT_H_INCLUDED // 这个头文件提供快速排序算法
/*
**写于2014年2月29日
**星期五
*/

template <typename Binary_iterator>
void qsort(Binary_iterator left, Binary_iterator right);

template <typename Binary_iterator>
void qsort(Binary_iterator left, Binary_iterator right)
{
    if (!(left < right))
      return;

    Binary_iterator i = left;
    Binary_iterator j = right;
    auto key = *i; // key的值只有实例化了之后才能确定,因此使用auto自动推断类型

    while (i != j) // 用运算符!=比较的缘故是为了兼容非顺序存储的数据(如队列和链表)
    {
      while (i != j && !(*j < key))
            --j;

      if (i != j)
            *(i++) = *j;

      while (i != j && *i < key)
            ++i;

      if (i != j)
            *(j--) = *i;
    }
    *i = key;
    qsort(left, --i); // 快排前半部分
    ++i; // 这样写是为了可以少定义一个friend operator+(iterator & iter, int i)函数
    qsort(++i, right); // 快排后半部分
}


#endif // SORT_H_INCLUDED#ifndef STATEMENT_H_INCLUDED
#define STATEMENT_H_INCLUDED // 这个头文件提供了关于一些数据结构节点的定义
/*
**写于2014年3月1日
**星期六
*/

class HTreeNode // 哈夫曼树的节点
{
private:
    char m_data; // 存储的字符
    unsigned int m_weight; // 节点权值
    HTreeNode * m_lSubTree; // 指向左子树的指针
    HTreeNode * m_rSubTree; // 指向右子树的指针
public:
    typedef HTreeNode * HTree;
    HTreeNode(HTreeNode * l = nullptr, HTreeNode * r = nullptr, const unsigned int w = 0,
             const char d = '\0')
      : m_lSubTree(l), m_rSubTree(r), m_weight(w), m_data(d) {}
    char& data() { return m_data; } // 返回引用的版本可供修改元素的值
    const char data() const { return m_data; }
    unsigned int & weight() { return m_weight; }
    const unsigned int weight() const { return m_weight; }
    HTree& lSubTree() { return m_lSubTree; }
    const HTree lSubTree() const { return m_lSubTree; }
    HTree& rSubTree() { return m_rSubTree; }
    const HTree rSubTree() const { return m_rSubTree; }
    bool operator< (const HTreeNode & t)
    {
      return m_weight < t.m_weight;
    }
    /*
    **不定义operator=() 函数,使用默认的即可,虽然有指针元素,
    **但是没有必要进行深复制
    */
};

template <typename ElemType> // 这个队列可以存储树节点,也可以在解码时存储字符,因此使用模板
class HQueNode // 快速排序算法需要双向迭代器,所以应使用双向队列
{
private:
    ElemType m_data; // 数据域
    HQueNode<ElemType> * m_next; // 指针域,指向后继结点
    HQueNode<ElemType> * m_prev; // 指针域,指向前驱结点
    unsigned int m_weight; // 用于排序
    typedef HQueNode<ElemType> * HQueue; // 这个typedef只能用于简化类内声明,不能为外界可见
public:
    HQueNode(ElemType & d) : m_data(d), m_next(nullptr) {}
    HQueNode() : m_next(nullptr) {}
    ElemType & data() { return m_data; }
    const ElemType data() const { return m_data; }
    HQueue& next() { return m_next; }
    const HQueue next() const { return m_next; }
    HQueue& prev() { return m_prev; }
    const HQueue prev() const { return m_prev; }
    unsigned int& weight() { return m_weight; }
    const unsigned int weight() const { return m_weight; }
};#ifndef QUE_BASE_H_INCLUDED
#define QUE_BASE_H_INCLUDED //这个头文件声明并定义了Bit_que类和Huffman_queue类的基类
/*
**写于2014年3月7日
**星期五
*/

#include "statement.h"

template <typename ElemType> class Que_base {
private:
    typedef HQueNode<ElemType>* Link_;
    Link_ front;
    Link_ rear;

    unsigned int length;

    void push_(const ElemType&);

protected:
    ~Que_base(); // 由于这个没有多态析构的必要,将析构函数设为保护的以免外界创建Que_base类对象
    Link_ Rear() { return rear; }
    Link_ Front() { return front; }
    virtual void push(const ElemType& data) { return push_(data); }
    // 这个保护虚函数给了派生类扩展的空间
public:
    Que_base() : front(nullptr), rear(nullptr), length(0) {}
    void enqueue(const ElemType& data) { push(data); } // 将元素加入到队尾
    void dequeue(ElemType&); // 队首元素出队列
    const unsigned int size() const { return length; }
    virtual bool empty() const = 0;
};

template <typename ElemType> void Que_base<ElemType>::push_(const ElemType& data) {
    static unsigned int weight = 0;
    Link_ add = new HQueNode<ElemType>;
    add -> data() = data;
    add -> weight() = weight++;

    ++length;

    if (!front) {
      front = rear = add;
      front -> prev() = nullptr;
    }
    else {
      rear -> next() = add;
      add -> prev() = rear;
      rear = add;
    }
}

template <typename ElemType> Que_base<ElemType>::~Que_base() {
    rear = front;
    while (front) {
      front = front -> next();
      delete rear;
      rear = front;
    }
}

template <typename ElemType> void Que_base<ElemType>::dequeue(ElemType& e) {
    if (length > 0) {
      --length;
      e = front -> data();
      Link_ temp = front;
      front = front -> next();
      delete temp;

      if (front == nullptr)
            rear = front;
    }
}



#endif // QUE_BASE_H_INCLUDED#ifndef HAFFMAN_QUEUE_H_INCLUDED
#define HAFFMAN_QUEUE_H_INCLUDED // 该头文件定义了哈夫曼队列以及迭代器类的实现
/*
**写于2014年3月7日
**星期五
*/

#include "sort.h"
#include "statement.h"
#include "que_base.h"

class Huffman_queue : public Que_base<HTreeNode> {
private:
    typedef HQueNode<HTreeNode>* HTree;

    class iterator {
    private:
      HTree pointer;
    public:
      iterator(HTree p = nullptr) : pointer(p) {}
      iterator& operator--();
      iterator operator--(int);
      iterator& operator++();
      iterator operator++(int);
      bool operator!= (const iterator& iter) const { return pointer != iter.pointer;};
      bool operator< (const iterator& iter) const { return pointer -> weight() < (iter.pointer) -> weight(); }
      HTreeNode& operator*() { return pointer -> data(); }
    };

    void push(const HTreeNode&);

    HTree End;

public:
    Huffman_queue() : Que_base(), End(new HQueNode<HTreeNode>) {End -> next() = nullptr; End -> prev() = nullptr;}
    bool empty() const { return size() == 1; }
    iterator begin() { return iterator(Front()); }
    iterator end() { return iterator(End); }
};


#endif // HAFFMAN_QUEUE_H_INCLUDED#include "haffman_queue.h" // 这个源文件实现了哈夫曼队列与迭代器

/*
**写于2014年3月8日
**星期六
*/

// 迭代器类实现
Huffman_queue::iterator& Huffman_queue::iterator::operator--() { // 前缀--运算符
      pointer = pointer -> prev();

    return *this;
}

Huffman_queue::iterator& Huffman_queue::iterator::operator++() { // 前缀++运算符
    pointer = pointer -> next();
    return *this;
}

Huffman_queue::iterator Huffman_queue::iterator::operator--(int o) { // 后缀--运算符
    HTree temp = pointer;

    pointer = pointer -> prev();

    return iterator(temp);
}

Huffman_queue::iterator Huffman_queue::iterator::operator++(int o) { // 后缀++运算符
    HTree temp = pointer;

    pointer = pointer -> next();
    return iterator(temp);
}

// 哈夫曼队列实现
void Huffman_queue::push(const HTreeNode& data) {
    Que_base<HTreeNode>::push(data);
    Rear() -> next() = End; // End节点的设置
    End -> prev() = Rear();
    qsort(begin(), end());
}
#ifndef BIT_QUE_H_INCLUDED

#define BIT_QUE_H_INCLUDED // 这个头文件定义了一个表示二进制位流的Bit_que类

/*
**写于2014年3月15日
**星期六
*/

class Bit_que : public Que_base<bool> {
public:
    bool empty() const { return size() == 0;}
};



#endif // BIT_QUE_H_INCLUDED目前还差哈夫曼树和编码没有实现,代码写了不下500行了吧

柠“萌”圆 发表于 2014-3-15 22:02:01

枫界易城 发表于 2014-3-9 12:47 static/image/common/back.gif
哇,,,,,代码也太长了吧,,,,,,,,,,,,,

哈夫曼编码本来就复杂......你看看我的代码吧

柠“萌”圆 发表于 2014-3-15 22:06:43

andalousie 发表于 2014-3-10 16:10 static/image/common/back.gif
加油加油,我写了不短时间。

发现了吗,我的程序不能用STL就写一个迭代器类模仿STL......求看看有没有问题

梦想☆飞扬 发表于 2014-3-15 22:11:02

你们好棒啊

qaed 发表于 2014-3-15 23:51:51

加油!!!!{:1_1:}{:1_1:}{:1_1:}{:1_1:}

andalousie 发表于 2014-3-16 09:29:59

柠“萌”圆 发表于 2014-3-15 21:59 static/image/common/back.gif
我目前写了这么多,看看你能不能找出问题(其实我也不知道问题在哪,没有测试过)
编译这些代码需要编译器支 ...

Well, uh... 你的迭代器写的不错啊~ 我反正没看到错误哦~ 反正我是用不惯快排的,所以用了一个堆实现的优先队列解决排序的问题。我其实不太了解C++11的,不过看了你的auto和nullptr的运用似乎懂了点,哈。一般有具体类型的构造函数我就直接用explicit了,这样编译器就不会误会了。你看过我写的《再看Huffman树》吗?上面有我实现的简易的位流。但是不是像你基于queue派生出来的,而是一个类似链表的衍生物。你加油吧,嘻嘻。会写出来的。

柠“萌”圆 发表于 2014-3-16 13:46:30

andalousie 发表于 2014-3-16 09:29 static/image/common/back.gif
Well, uh... 你的迭代器写的不错啊~ 我反正没看到错误哦~ 反正我是用不惯快排的,所以用了一个堆实现的优 ...
nullptr其实就是C宏NULL,用于表示空指针,不过比NULL更安全,清晰。auto用于自动类型推断,例如:
std::vector<std::string>::const_itrator p = v.begin();这种冗长的记法可以直接用 auto p = v.begin();减少了输入量,有时会使代码有更好的可读性

andalousie 发表于 2014-3-16 21:43:06

柠“萌”圆 发表于 2014-3-16 13:46 static/image/common/back.gif
nullptr其实就是C宏NULL,用于表示空指针,不过比NULL更安全,清晰。auto用于自动类型推断,例如:
std: ...

谢谢呦,基础果然比我扎实~~ 膜拜你。你写的我都能看懂。比书上讲的清楚多了{:1_1:}

柠“萌”圆 发表于 2014-3-19 18:47:54

andalousie 发表于 2014-3-16 21:43 static/image/common/back.gif
谢谢呦,基础果然比我扎实~~ 膜拜你。你写的我都能看懂。比书上讲的清楚多了

目前我C++ Programming Language都看得不明白。。。。。。能推荐几本书看看么?

andalousie 发表于 2014-3-19 22:41:39

柠“萌”圆 发表于 2014-3-19 18:47 static/image/common/back.gif
目前我C++ Programming Language都看得不明白。。。。。。能推荐几本书看看么?
可以看看Data Structures and Problem Solving Using C++,Mark Allen Weiss写的,清华大学出版社出过翻译本。还有C++ Annotations Version 9.7.3,中文叫做C++剖析应该~ Frank B. Brokken写的,可以看看,比Bjarne Stroustrup的神书好懂点。英文版网上都可以下载到。

柠“萌”圆 发表于 2014-3-21 22:16:09

andalousie 发表于 2014-3-19 22:41 static/image/common/back.gif
可以看看Data Structures and Problem Solving Using C++,Mark Allen Weiss写的,清华大学出版社出过翻译 ...

哈夫曼编码写出来了,但是崩溃了......貌似在迭代器上出了问题

zndownload 发表于 2017-1-2 16:28:33

路过,了解下
页: [1]
查看完整版本: 两种风格的Huffman编码(C++版)