哈夫曼编译码器.cpp

哈夫曼编译码器 实现简单

#include<iostream.h>
#include<string.h>
#define MAX 100 //定义一个最大值
typedef struct
{
	int weight;
    int parent,lchild,rchild; // 静态指针
    char code;
}hufftree;//定义哈夫曼树的类型

typedef char * huffcode;

void select(hufftree *p,int j,int *s)//查找j以前的两个权值最小的元素
{
	int i,m,n,mid,t;                    
    hufftree *q;
    m=n=MAX; // m中存放最小,n的中存放次小的
    for(i=0,q=p;i<j;i++,q++)
       if(q->parent==0)
	   {  
		   if(q->weight<m)
		   { 
			   mid=m; 
			   m=q->weight; 
			   n=mid;
               t=*s; *s=i; *(s+1)=t;
		   } // 若找到最小的则交换
           else 
			   if(q->weight<n)
			   {    
				   n=q->weight; 
				   *(s+1)=i;
			   }
	   }
}


void hcode(hufftree *ht,int *w,int n)//哈夫曼编码//
{
	int i,m,s[2]; 
    hufftree *p;
    m=2*n-1;

    for(i=0,p=ht;i<n;i++,p++,w++) // 树中各叶子结点的初始化
	{ 
		p->weight=*w;
        p->parent=p->lchild=p->rchild=0;
	}
    
	for(i=n;i<m;i++,p++) // 非叶子结点的初始化
	{
       p->weight=p->parent=p->lchild=p->rchild=0;
	}

    for(i=n;i<m;i++) // 合并n-1次
	{  
		select(ht,i,s); // 找出两个结点数值最小的两个结点
        (ht+s[0])->parent=i; 
		(ht+s[1])->parent=i;
        (ht+i)->code='*';
		(ht+i)->lchild=s[0]; 
		(ht+i)->rchild=s[1];
        (ht+i)->weight=(ht+s[0])->weight+(ht+s[1])->weight;
	}
}


void huffc(hufftree *ht,huffcode *hc,int n)
{   
	char *cd;
    int i,start,c,f;
    cd=new char[n];
    *(cd+n-1)='\0';

    for(i=0;i<n;i++)
	{ 
		start=n-1;
        for(c=i,f=(ht+i)->parent;f!=0;c=f,f=(ht+f)->parent)
			if((ht+f)->lchild==c)
				*(cd+(--start))='0';
            else 
				*(cd+(--start))='1';
        *(hc+i)=new char[n];
        strcpy(*(hc+i),cd+start);
	}
    delete []cd;
}
void change(hufftree *ht,huffcode *hc,int n)
{
	char c[10];
    int i,sign;
    huffcode *p;
    cout<<"如果想检验代码请输入1否则输入0\n";
    cin>>sign;
    while(sign==1)
	{  
		cout<<"请输入所要检验的代码\n";
        cin>>c;
        for(i=0,p=hc;i<n;i++,p++)
           if(!strcmp(c,*p))  break;
        if(i>=n)  cout<<"此代码有误\n";
          else cout<<"此代码对应的字符为:"<<(ht+i)->code<<endl;
        cout<<"如果想继续检验代码请输入1否则输入0\n";
        cin>>sign;
	}
}

int main()
{
	int n,m,i,*w,*p;
    hufftree *ht,*q;
    huffcode *hc,*r;
    cout<<"请输入字符的个数\n";
    cin>>n;
    m=2*n-1;
    w=new int[m]; 
    ht=new hufftree[m];
    cout<<"请逐个输入每个字符及其权值\n\n";

    for(i=0,p=w,q=ht;i<n;i++,q++)
	{   
		cout<<"请输入字符及其权值\n";
        cin>>q->code;
        cin>>p[i];
	}

    hcode(ht,w,n);
    hc=new huffcode[m];
    huffc(ht,hc,n);
    cout<<"编码如下:\n";
    for(i=0,q=ht,r=hc;i<n;i++,q++,r++)
       cout<<q->code<<"  "<<*r<<endl;
    change(ht,hc,n);
	
	return 0;
}