head.h

我做的一个霍夫曼编码

//head.h
enum Error_code {success,underflow,overflow,rangeerror};
const max_list=60;
const int maxsize=100;
const maxnode=100;//定义最大节点个数
#define MAXBIT 20 /*定义哈夫曼编码的最大长度*/ 
#define MAXVALUE 1 /*定义最大权值*/ 
#define MAXLEAF 50 /*定义哈夫曼树中最多叶子节点个数*/ 
#define MAXNODE MAXLEAF*2-1 /*哈夫曼树最多结点数*/ 
template<class List_entry>
class List
{
public:
	List(){count=0;}
	int size() const;
	bool full() const;
	bool empty()const;
	void clear();
	void traverse(void(*visit)(List_entry&));
	Error_code retrieve(int position,List_entry &x)const;
	Error_code replace(int position,const List_entry &x);
	Error_code remove(int position,List_entry &x);
	Error_code insert(int position,const List_entry &x);
protected:
	int count;
	List_entry entry[max_list];
};

class Hcodetype//编码类
{
public:
   int bit[MAXBIT];  //记录编码位数
   int start;//记录编码在bit[MAXBIT]里的起始位置
};

class Hnodetype//节点类
{
public:
	Hnodetype();
	Hnodetype(Hnodetype* left,Hnodetype* right,float possibility);
	float value;           //存放节点的权值
    Hnodetype* parent;     //指向上个节点的指针
    Hnodetype* left_child; //指向左孩子指针
    Hnodetype* right_child;//指向右孩子指针
};
class Huffmantree  //哈夫曼树
{
public:
	Huffmantree();
	void MakeNode();  //构造节点的函数
    void GetCode(); //获取叶子节点编码函数
//	~Huffmantree();
private:
	Hnodetype *huffnode[MAXNODE]; //存储节点的指针数组
    Hcodetype huffcode[MAXLEAF]; //存放节点编码的数组
	int no;//记录叶子节点的个数
	List<char> original_text;//存放输入串
    char compact[maxsize]; //存放所有出现的不同的字符
};

template<class List_entry>
int List<List_entry>::size()const
/*Post:The function returns the number of entries in the List.*/
{
	return count;
}
template<class List_entry>
bool List<List_entry>::full()const
/*Post:The function returns true or false according to whether the List is empty or not.*/
{
	bool outcome=true;
	if(count>=0&&count<max_list)
		outcome=false;
	return outcome;
}
template<class List_entry>
bool List<List_entry>::empty()const
/*Post:The function returns true or false according to whether the List is empty or not.*/
{
	bool outcome=true;
	if(count!=0)
		outcome=false;
    return outcome;
}
template<class List_entry>
void List<List_entry>::clear()
/*Post:All List entries have been removed;the List is empty.*/
{
	count=0;
}
template<class List_entry>
void List<List_entry>::traverse(void(*visit)(List_entry &))
/*Post:The action specified by function(*visit) has been performed on every entry
       of the list,beginning at position 0 and doing each in turn.*/
{
	for(int i=0;i<count;i++)
		(*visit)(entry[i]);
}
template<class List_entry>
Error_code List<List_entry>::insert(int position,const List_entry &x)
/*Post: If the list is not full and 0<=position<=n,where n is the number of entries in
        the List,the function succeeds:Any entry formerly at position and all later entries 
		have their position numbers increased by 1 and x is inserted at position of the List.
		Else: The function fails with a diagnostic error code.*/
{
	if(full())
		return overflow;
	if(position<0||position>count)
		return rangeerror;
	for(int i=count-1;i>=position;i--)
		entry[i+1]=entry[i];
	entry[position]=x;
	count++;
	return success;
}
template<class List_entry>
Error_code List<List_entry>::remove(int position,List_entry &x)
/*Post:If 0<=position<n,where n is the number of entries in the List, the funcion succeeds:
        The entry at position is removed from the List,and all later entries have their position
		numbers decreased by 1.The parameter x records a copy of the entry formerly at position.
		Else: The function fails with a diagnostic error code.*/
{
	if(empty())
		return underflow;
	if(position<0||position>=count)
		return rangeerror;
	x=entry[position];
	for(int i=position;i<count-1;i++)
		entry[i]=entry[i+1];
	count--;
	return success;
}
template<class List_entry>
Error_code List<List_entry>::retrieve(int position,List_entry &x)const
/*Post:If 0<=position<n,where n is the number of entries in the List,the function succeeds:
       The entry at position is copied to x;all List entries remain unchanged.
	   Else:The function fails with a diagnostic error code.*/
{
	if(empty())
		return underflow;
	if(position<0||position>=count)
		return rangeerror;
	else
	x=entry[position];
	return success;
}
template<class List_entry>
Error_code List<List_entry>::replace(int position,const List_entry &x)
/*Post:If 0<=position<n,where n is the number of entries in the List,the function succeeds:
       The entry at position is replaced by x;all List entries remain unchanged.
	   Else:The function fails with a diagnostic error code.*/
{
	if(position<0||position>=count)
		return rangeerror;
	entry[position]=x;
	return success;
}