对不起,我重新整理一下
//status.h
typedef int status
#define FAILE 0
#define SUCCESS 1
#define TURE 1
#define FALSE 0
//huffman.cpp
从下面开始就是源文件,类都贴在前面。
#include <status.h>
#ifndef PRINTWIDTH
#define PRINTWIDTH 4
#endif
#ifndef BASICLEN 20
#define BASICLEN 20
#endif
//一个可自动分配存储空间的数组。
template <class Type>
class Array{
public:
Type* a;
int size;
int length;
Array();
~Array();
status Empty();//是否空?
status Full();//是否满?
void Reallocate();//重新分配空间
status Insert(Type& ins,int n);//在数组的第n个位置插入一个元素
void AddTail(Type ins); //在数组尾部添加一个元素
void Reverse();//逆置数组
void Read();//设置数组
void Print();//打印
}
//一个二进制类,用于存储二进制串。
struct Bit{
unsigned short * bits;
int length;//二进制串长度
int size;//分配给SHORT* BITS 的长度
Bit();
void Clear(); //清空
status Empty();//是否为空?
void ToString(Array<char> &s); //将二进制串转成字符串
void StringToBit(Array<char> &s);//将字符串转成二进制串
void Reallocate();//重新分配空间
void Union(Bit &t);//将另一个二进制串并入自己的尾部
void Read();//设置二进制串
void Print();//打印
status Full();//是否为满?
~Bit();
}
//哈夫曼树结点
struct Huffs{
int weight;//权重
int lc;//左子树
int rc;//右子树
int para;//父树
};
typedef char Data;
struct Huffman{
Huffs* huf; //哈夫曼树〈数组存储〉
Data* data;//数据组
int len;//数据组长度
Huffman();
status Create();//通过用户输入来设置哈夫曼树
void CreateBT();//通过数据组和权重来设置哈夫曼树
int DeepBT();//求树深度
int DeepBTs(int p);//求树深递归函数
void PrintBT();//打印树
void PrintBTs(int p,int x,int y,int d);//打印树子递归函数
};
template <class Type>
void Array<Type>::Reallocate(){
if(size==0){
a=new Type[BASICLEN];
size=BASICLEN;
}
else{
Type* t=new Type[length];
for(int i=0;i<length;i++){
t[i]=a[i];
}
delete(a);
a=new Type[size+=BASICLEN];
for(i=0;i<length;i++){
a[i]=t[i];
}
delete(t);
}
}
template <class Type>
status Array<Type>::Full(){
if(length>=size)
return TRUE;
else
return FALSE;
}
template <class Type>
status Array<Type>::Empty(){
if(length==0)
return TRUE;
else
return FALSE;
}
template <class Type>
void Array<Type>::Reverse(){
Type t;
for(int i=0;i<length/2;i++){
t=a[i];
a[i]=a[length-1-i];
a[length-1-i]=t;
}
}
template <class Type>
void Array<Type>::Read(){
cout<<"\nPlease enter the num of data:";cin>>length;
while(length<=0){
cout<<"\nPlease enter the num of data:";cin>>length;
}
while(Full())
Reallocate();
for(int i=0;i<length;i++){
cout<<"Data["<<i<<"]=";cin>>a[i];
}
}
template <class Type>
void Array<Type>::Print(){
if(!Empty()){
cout<<"\nPrint:\n";
for(int i=0;i<length;i++){
cout<<"Data["<<i<<"]="<<a[i]<<endl;
}
}
}
template <class Type>
Array<Type>::Array(){
a=new Type<BASICLEN>;
size=BASICLEN;
length=0;
}
template <class Type>
Array<Type>::~Array(){
delete(a);
}
template <class Type>
void Array<Type>::AddTail(Type ins){
if(Full())
Reallocate();
a[length++]=ins;
}
template <class Type>
status Array<Type>::Insert(Type& ins,int n){
if(n<0){
cout<<"\nerror: insert location <0\n";
return FAILE;
}
if(Full())
Reallocate();
if(n>length){
a[length]=ins;
}
else{
for(k=length;k>n;k--){
a[k]=a[k-1];
}
a[k]=ins;
}
length++;
return SUCCESS;
}
Bit::~Bit(){
delete(bits);
}
void Bit::Clear(){
delete(bits);
size=length=0;
}
status Bit::Full(){
if(length/8>=size+1)
return TRUE;
else
return FALSE;
}
void Bit::Reallocate(){
if(length){
int l=length/8;
l%8?l+1:l;
unsigned short* t=new unsigned short[l];
for(int i=0;i<l;i++)
t[i]=bits[i];
delete(bits);
bits=new unsigned short[size+BASICLEN];
for(i=0;i<l;i++)
bits[i]=t[i];
size+=BASICLEN;
for(;i<size;i++)
bits[i]=0;
delete(t);
}
else{
Clear();
bits=new unsigned short[BASICLEN];
size=BASICLEN;
for(int i=0;i<size;i++)
bits[i]=0;
}
}
status Bit::Empty(){
if(!size)
return TRUE;
else
return FALSE;
}
void Bit::Union(Bit& t){
if(Full())
Reallocate();
for(int i=0;i<t.length;i++){
bits[(length+i)/8]|=(((t.bits[i/8]&(1<<i%8))>>i%8)<<(length+i)%8);
}
length+=t.length;
}
void Bit::Read(){
Clear();
Reallocate();
char c;
c=getchar();
while(c=='0'||c=='1'){
bits[length/8]|=(c-'0')<<(length%8);
length++;
if(Full())
Reallocate();
c=getchar();
}
}
void Bit::Print(){
cout<<"\nPrint\n";
for(int i=0;i<length;i++){
if(bits[i/8]&(1<<(i%8)))
cout<<'1';
else
cout<<'0';
}
}
Bit::Bit(){
length=0;
bits=NULL;
}
void Bit::ToString(Array<char> &s){
int i=0;
char c;
while(i<length){
c=('0'+1&(bits[i/8]>>(i%8)));
s.AddTail(c);
i++;
}
}
void Bit::StringToBit(Array<char> &s){
length=s.length;
delete(bits);
if(length%8!=0)
bits=new unsigned short[length/8+1];
else
bits=new unsigned short[length/8];
for(int i=0;i<length/8;i++){
bits[i]=0;
}
if(length%8)
bits[i]=0;
i=0;
while(i<s.length){
bits[i/8]|=((s.a[i]-'0')<<i%8);
i++;
}
}
int pow(int p,int t){
while(t>0){
p*=p;
t--;
}
return p;
}
Huffman::Huffman(){
huf=NULL;
data=NULL;
len=0;
}
int Huffman::DeepBTs(int p){
int d1,d2;
if(huf[p].lc)
d1=DeepBTs(huf[p].lc);
if(huf[p].rc)
d2=DeepBTs(huf[p].rc);
d1<d2?d2:d1;
return d1+1;
}
int Huffman::DeepBT(){
return DeepBTs(2*len-1);
}
void Huffman::PrintBTs(int p,int x,int y,int d){
gotoxy(x,y);
cout<<huf[p].weight;
if(p<len){
gotoxy(x,y+1);
cout<<data[p];
}
else{
PrintBTs(huf[p].lc,x-PRINTWIDTH*pow(2,d),y+3,d-1);
PrintBTs(huf[p].rc,x+PRINTWIDTH*pow(2,d),y+3,d-1);
}
}
void Huffman::PrintBT(){
clrscr();
int d=DeepBT();
cout<<"\n\tBT\n";
PrintBTs(2*len-1,40,3,d-1);
}
void Huffman::CreateBT(){
int m1=0,m2=1,i,j;
if(huf[m1].weight>huf[m2].weight){
i=m1;
m1=m2;
m2=i;
}
for(i=0;i<len-1;i++){
for(j=0;j<len+i;j++){
if(huf[j].para==NULL){
if(huf[m1].para!=NULL)
m1=j;
else if(huf[m2].para!=NULL)
m2=i+j;
else{
if(huf[j].weight<=huf[m1].weight&&j!=m1&&j!=m2){
if(huf[j].weight<=huf[m2].weight)
if(j!=m2){
m2=j;
}
else{
m1=m2;
m2=j;
}
}
}
}
}
huf[j].lc=m1;
huf[j].rc=m2;
huf[m1].para=huf[m2].para=j;
}
}
status Huffman::Create(){
cout<<"enter the num of data(2 - 37568):";cin>>len;
if(len<2){
len=0;
cout<<"\nerror~\n";
return FAILE;
}
else{
data=new Data[len];
huf=new Huffs[2*len-1];
for(int i=0;i<len;i++){
cout<<"data"<<i<<"=";
cin>>data[i];
cout<<"weight:";
cin>>huf[i].weight;
huf[i].lc=huf[i].rc=huf[i].para=0;
}
for(;i<(2*len-1);i++){
huf[i].weight=huf[i].lc=huf[i].rc=huf[i].para=0;
}
CreateBT();
return SUCCESS;
}
}
void t1(){
Huffman h;
h.Create();
h.PrintBT();
getch();
}
void main(){
t1();
}