haffman.cpp

我的一次数据结构课程设计HUFFMAN树的C++源代码

#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
#include <string.h>

#define MaxValue 10000
#define MaxN 50

typedef struct haffman
{
	int weight;
	int parent;
	int lchild;
	int rchild;
	int flag;
}Haffnode;

typedef struct
{
	int weight;
	int bit[MaxN]; //数组
	int root;      //编码起始下标
}Code;

typedef struct //存放字符所对应的权值的数组
{
	char CB;     //大写
	char CS;     //小写
	int ww;      //权值
}list;


//实现一个二叉数组，并对其进行haffman编码
void Haffman(int weight[],int n, Haffnode hafftree[],Code haffcode[])
{
	int i,j,m1,m2,x1,x2;     //haffman初始化
	for(i=0;i<2*n-1;i++)     //n个叶结点的二叉树共有2n-1个结点
	{
		if(i<n)
		{
			hafftree[i].weight=weight[i];
		}
		else 
		{
			hafftree[i].weight=0;
		}
		hafftree[i].parent=0;
		hafftree[i].lchild=-1;
		hafftree[i].rchild=-1;
		hafftree[i].flag=0;
	}
	for(i=0;i<n-1;i++)   //构造haffman的n-1个非叶结点
	{
		m1=m2=MaxValue;
		x1=x2=0;
		for(j=0;j<n+i;j++)   //找出2个最小权值的字符，每加一个结点就多一次循环
		{
			if(hafftree[j].weight<m1&&hafftree[j].flag==0)
			{
				m2=m1;
				x2=x1;
				m1=hafftree[j].weight;
				x1=j;
			}
			else if(hafftree[j].weight<m2&&hafftree[j].flag==0)
			{
				m2=hafftree[j].weight;
				x2=j;
			}
		}
		hafftree[x1].parent=n+i;   
		hafftree[x2].parent=n+i;
		hafftree[x1].flag=1;
		hafftree[x2].flag=1;
		hafftree[n+i].weight=m1+m2;
		hafftree[n+i].lchild=x1;
		hafftree[n+i].rchild=x2;   
	}

	Code *cd=(Code *)malloc(sizeof(Code));
	int child,parent;
	for(i=0;i<n;i++)   //求N个叶结点的haffman
	{
		cd->root=n-1;     //不等长编码的最后一位为n-1
		cd->weight=hafftree[i].weight;  //取得编码对应的权值
		child=i;
		parent=hafftree[child].parent;
		while(parent!=0)    //由叶结点向上直到根结点
		{
			if(hafftree[parent].lchild==child)  
				cd->bit[cd->root]=0; 
			else
				cd->bit[cd->root]=1;
			cd->root--;
			child=parent;
			parent=hafftree[child].parent;
		}
		for(j=cd->root+1;j<n;j++)     //将每个字符的编码赋给bit[]
		{
			haffcode[i].bit[j]=cd->bit[j]; // cout<<cd->bit[j];
		} 
		haffcode[i].root=cd->root;   //保留每个字符编码的起始位置
		haffcode[i].weight=cd->weight;   //保留其对应的权值
	}//cout<<endl;
}


//操作1-----------------------------------------------------------------
void display()	//输出27个字符的haffman编码
{
	int i,j,n=27;
	int weight[]={186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,
				  63,15,1,48,51,80,23,8,18,1,16,1};
	Haffnode *Ht=(Haffnode *)malloc(sizeof(Haffnode)*(2*n+1));
	Code *Hc=(Code *)malloc(sizeof(Code)*n);
	Haffman(weight,n,Ht,Hc);   //调用haffman编码函数
	printf("char='%c' HaffCode=",32);
	for(j=Hc[0].root+1;j<n;j++)
		printf("%d",Hc[0].bit[j]);
	printf("\n");
	for(i=1;i<n;i++)
	{
		printf("char='%c' HaffCode=",64+i);
		for(j=Hc[i].root+1;j<n;j++)
			printf("%d",Hc[i].bit[j]);
		printf("\n");
	}
}


//操作2--------------------------------------------------------------------
void Info(list s[])     //构造一个数组来存放字符及权值信息
{
	int i;
	char CB,CS;
	int f[27]={186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,
				   63,15,1,48,51,80,23,8,18,1,16,1};
	s[0].CB=' ';
	s[0].ww=186;
	for(i=1,CB='A',CS='a';i<27;i++,CB++,CS++)
	{
		s[i].CB=CB;
		s[i].CS=CS;
		s[i].ww=f[i];  //cout<<s[i].ww<<endl;
	}
}

getww(list s[],int f[])    //接收一串字符，并把权值赋给f[]
{
	char str[MaxN];
	int i,k=0;	
	cout<<"请输入一串字符:"<<endl;
	gets(str);	
	for(i=0;i<(int)strlen(str);i++)
	{
		for(int j=0;j<27;j++)
		{
			if(str[i]==s[j].CB)
			{
				f[k]=s[j].ww;   
				k++;				
			}
			if(str[i]==s[j].CS)
			{
				f[k]=s[j].ww;
				k++;				
			}
		}
	}
	return ((int)strlen(str));
}

void inputm()  //输入m个字符，按他们的权值输入haffman编码
{	
	int i,j,m;
	list s[MaxN];
	int f[MaxN];
	Info(s);
	m=getww(s,f);
	cout<<"输入的字符个数是:"<<m<<endl;
	Haffnode *Ht1=(Haffnode *)malloc(sizeof(Haffnode)*(2*m+1));
	Code *Hc1=(Code *)malloc(sizeof(Code)*m);
	Haffman(f,m,Ht1,Hc1);
	for(i=0;i<m;i++)
	{
		for(j=Hc1[i].root+1;j<m;j++)
			printf("%d",Hc1[i].bit[j]);
		printf(" ");
	}
	printf("\n");
}



//操作3------------------------------------------------------------------
void outcode()
{
	int i,j,k,n=27;
	int weight[]={186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,
				  63,15,1,48,51,80,23,8,18,1,16,1};
	char str[MaxN];
	list s[MaxN];	
	Info(s);
	Haffnode *Ht=(Haffnode *)malloc(sizeof(Haffnode)*(2*n+1));
	Code *Hc=(Code *)malloc(sizeof(Code)*n);
	Haffman(weight,n,Ht,Hc);
	cout<<"请输入一串字符:"<<endl;
	gets(str);	
	for(i=0;i<(int)strlen(str);i++)
	{
		for(j=0;j<27;j++)
		{
			if(str[i]==s[j].CB)
			{
				for(k=Hc[j].root+1;k<n;k++)
					printf("%d",Hc[j].bit[k]);					
			}
			if(str[i]==s[j].CS)
			{
				for(k=Hc[j].root+1;k<n;k++)
					printf("%d",Hc[j].bit[k]);				
			}
		}
		printf(" ");
	}
	printf("\n");
}





void main()
{
    int i;
	int f=1;
	cout<<"欢迎进入我的哈夫曼"<<endl;
    while(f)
	{
		cout<<"请选择( 0 ~ 3 )"<<endl;
		cout<<"0.退出"<<endl;
		cout<<"1.显示27个字符的haffman编码"<<endl;
		cout<<"2.输入m个字符，对应27个字符的权值进行haffman编码"<<endl;
		cout<<"3.输入一串字符，用已经定义的haffman编码输出"<<endl;
        cin>>i;       
        switch(i)
        {
			case 1:
				display();
				break;
			case 2:
				inputm();
				break;
			case 3:
				outcode();
				break;
			case 0:
				f=0;
				cout<<"再见!"<<endl;
				break;
        }
	}
}