两种风格的Huffman编码（C++版）

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

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

最近几天在搞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[id.index()] == '0')
x = x->_left;
else x = 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[id.index()] == '1')
{
char c = trie[id.index()];
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[R] = {0};
for (int i = 0; i < s.size(); ++i)
freq[s[i]]++;
// Build Huffman code trie.
Node *root = buildTrie(freq);
std::string *st = new std::string [R];
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[s[id]];
std::cout << s[id] << " ";
std::cout << code << std::endl;
}
}
private:
Node* buildTrie(int *freq)
{
GenericPQ<Node*> pq(R);
for (int i = 0; i < R; i++)
if (freq[i] > 0)
pq.insert(new Node(i, freq[i], 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[R];
buildCode(st, root, "");
return st;
}
void buildCode(std::string *st, Node *x, std::string s)
{
if(x->isLeaf()) { st[x->_ch] = 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[1..N] with pq[0] 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[i]->compareTo(_pq[j]); }
void swap(int i, int j)
{
T ex = _pq[i];
_pq[i] = _pq[j];
_pq[j] = ex;
}
};
template<class T>
GenericPQ<T>::GenericPQ(int capacity)
:_N(0)
{
_pq = new T[capacity+1];
}
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[1]; // Retrieve max key from top.
swap(1, _N--); // Exchange with last item.
sink(1); // Avoid loitering.
_pq[_N+1] = 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)[UniqueSymbols])
{
std::priority_queue<INode*, std::vector<INode*>, NodeCmp> trees;
for (int i = 0; i < UniqueSymbols; ++i)
{
if(frequencies[i] != 0)
trees.push(new LeafNode(frequencies[i], (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[lf->c] = 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[UniqueSymbols] = {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[0] << " -[cu] 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[0] << " -[cu] 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

登录/注册后可看大图

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

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

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

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

登录/注册后可看大图

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

我目前写了这么多,看看你能不能找出问题(其实我也不知道问题在哪,没有测试过)
编译这些代码需要编译器支持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

登录/注册后可看大图

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

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

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

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

登录/注册后可看大图

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

发现了吗,我的程序不能用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

登录/注册后可看大图

我目前写了这么多,看看你能不能找出问题(其实我也不知道问题在哪,没有测试过)
编译这些代码需要编译器支 ...

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

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

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

登录/注册后可看大图

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

登录/注册后可看大图

nullptr其实就是C宏NULL，用于表示空指针，不过比NULL更安全，清晰。auto用于自动类型推断，例如：
std: ...

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

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

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

登录/注册后可看大图

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

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

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

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

登录/注册后可看大图

目前我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

登录/注册后可看大图

可以看看Data Structures and Problem Solving Using C++，Mark Allen Weiss写的，清华大学出版社出过翻译 ...

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

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

路过，了解下

账号		自动登录	找回密码
密码			立即注册

[技术交流] 两种风格的Huffman编码（C++版）

马上注册，结交更多好友，享用更多功能^_^