huffman.cpp

实现哈夫曼编码功能,可任意输入一段报文,程序自动统计各字符的权值,并进行编码,可显示中间过程..编码后可输入一段密文进行解码...原创,请支持,

#include<iostream>
#include<string>
#include<fstream>
#include<iomanip>
using namespace std;

ofstream text("HuffmanCode.txt");   //文件操作，用于保存结果

#define WEIGHT_LIST_SIZE 128        //128对应128个ASCII码

typedef struct 
{
	int weight;
}WeightNode,*WeiNode;

typedef struct
 {
	char ch;
	unsigned int weight;
	unsigned int parent,lchild,rchild;
 }HTNode,*HuffmanTree;            //动态分配数组存储哈夫曼树

typedef char **HuffmanCode;       //动态分配数组存储哈夫曼编码表
typedef char * charp;

int *StatWeight(int & n,charp & cs)//统计各个字符的权值
{
	n = 0;
	WeiNode LN = new WeightNode[WEIGHT_LIST_SIZE];
	int serial;
	for(serial = 0;serial < WEIGHT_LIST_SIZE;serial++)
	{
		LN[serial].weight = 0;    //权值初始化
	}
	cout<<"请输入一段字符，以#号结束:"<<endl;
    text<<"请输入一段字符，以#号结束:"<<endl;
	char ch;
	while(true)
	{
		cin>>ch;
		text<<ch;
		if(ch == '#')
			break;              //输入结束，跳出
		serial = (int)ch;
		if(!LN[serial].weight)
		{
			n++;                 //如果与已出现字符不同，则字符个数加1
		}
		LN[serial].weight++;     //这个字符的权值加1
	}
	cout<<"字符的个数为:"<<n<<endl;
	int i = 0 ;
	char * c = new char[n];      //用于保存出现的字符
	char *cp = c;
	int * w = new int[n];        //用于保存字符的权值
	int *wp = w;
	cout<<"各个字符的权值依次为：";
	text<<endl;
    text<<"各个字符的权值依次为：";
	for(serial = 0;serial < WEIGHT_LIST_SIZE;serial++)
	{
		if(!LN[serial].weight)
			continue;
		*wp=LN[serial].weight;
		*cp=(char)serial;
		
		cout<<*cp<<"("<<*wp<<")"<<"  ";
		text<<*cp<<"("<<*wp<<")"<<"  ";
		wp++,cp++;
	
	}

	cs = c;
	return w;
}

int Min(HuffmanTree HT,int i)    //选择一个权值最小的结点
{
	 int j,temp;
	 unsigned int k=UINT_MAX;
	 for(j=1;j<=i;j++)
		 if(HT[j].weight<k && HT[j].parent==0)
			 k=HT[j].weight,temp=j;
	HT[temp].parent=1;
	return temp;
 }

void Select(HuffmanTree HT,int i,int &s1,int &s2) //选择两个权值最小的结点，并调整其次序
{
	 int j;
	 s1=Min(HT,i);
	 s2=Min(HT,i);
	 if(s1>s2)
	 {
		 j=s1;
		 s1=s2;
		 s2=j;
	 }
}

bool HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,char * cp,int n)
{//w存放n个字符胡权值，构造哈夫曼树HT，并求出n个字符的哈夫曼编码HC
	 int m,i,s1,s2,start;
	 unsigned c,f;
	 HuffmanTree p;
	 char *cd;
	 if(n<=1)
		 return false;
	 m=2*n-1;                       //n个叶子结点的哈夫曼树需要2*n-1个结点
	 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));  //0号单元未用
	 for(p=HT+1,i=1;i<=n;++i,++p,++w,++cp)// 初始化
	 {
		 p->ch=*cp;
		 p->weight=*w;
		 p->parent=0;
		 p->lchild=0;
		 p->rchild=0;
	 }
	 for(;i<=m;++i,++p)
		 p->parent=0;
	 for(i=n+1;i<=m;++i)
	 {
		 Select(HT,i-1,s1,s2);//选择parent为0且权值最小的两个结点，构造新的二叉杩
		 HT[s1].parent=HT[s2].parent=i;
		 HT[i].lchild=s1;
		 HT[i].rchild=s2;
		 HT[i].weight=HT[s1].weight+HT[s2].weight;
	 }
   //----------输出到屏幕和保存到文件中-----------
   cout<<"Huffman树存储结构的终结状态如下图："<<endl;
   cout<<"      "<<"weight"<<"  "<<"parent"<<" "<<"lchild"<<"  "<<"rchild"<<endl;
   for(i=1;i<=m;i++)
   {
	   
       cout<<"<"<<i<<"> "<<"\t"<<HT[i].weight<<"\t" <<HT[i].parent 
		   <<"\t"<<HT[i].lchild <<"\t"<<HT[i].rchild<<endl;
		  
	}
   text<<endl;
   text<<"Huffman树存储结构的终结状态如下图："<<endl;
   text<<"      "<<"weight"<<"  "<<"parent"<<" "<<"lchild"<<"  "<<"rchild"<<endl;
   for(i=1;i<=m;i++)
   {
	   
       text<<"<"<<i<<"> "<<"\t"<<HT[i].weight<<"\t" <<HT[i].parent 
		   <<"\t"<<HT[i].lchild <<"\t"<<HT[i].rchild<<endl;
		  
	}
	 HC=(HuffmanCode)malloc((n+1)*sizeof(char*));// 分配n个字符的头指针向量
	 cd=(char*)malloc(n*sizeof(char));           //分配求编码的工作空间
	 cd[n-1]='\0';                                //编码结束符
	
	 cout<<"各个字符的Huffman编码依次为："<<endl;
	 text<<endl;
	 text<<"各个字符的Huffman编码依次为："<<endl;
	for(i=1;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]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间
		strcpy(HC[i],&cd[start]);                   //从cd复制编码串到HC
		cout<<HT[i].ch<<"----"<<HC[i]<<endl;
		text<<HT[i].ch<<"----"<<HC[i]<<endl;
	 }

	 free(cd);                                    //释放工作空间
	 
 }


void  HuffmanDecoding(HuffmanTree &HT ,int n)
{ //从根结点到叶子结点译码
	int k=2*n-1;
	char ch;
	cout<<"请输入密文，以#号结束：";
	text<<"请输入密文，以#号结束："<<endl;
	while(1)
	{
		cin>>ch;
		if(ch!='#') text<<ch;
		
		if(ch=='#')      //输入以#号结束
		{
			break;
		}
		else
		{
			if(ch=='0')        //遇到0，则转向左孩子
			{
				k=HT[k].lchild;
			}
			else if(ch=='1')//遇到1，则转向右孩子
			{
				k=HT[k].rchild;
			}
			else
			{
			  cout<<" 发现无效编码"<<endl;
			}

			if(k<=n)
			{//找到叶子结点则输出对应的字符
				cout<<HT[k].ch;
				text<<"\t"<<"------->"<<HT[k].ch<<endl;
				k=2*n-1;
			}
		}
	}

}
		
int main()
{
	char slect;
	 do
	{
	 system("cls");      //当用户选择重来的时候，清理屏幕
	 HuffmanTree HT=NULL;
	 HuffmanCode HC=NULL;
	 int n=0;
	 char * c;
	 
	 int * w=StatWeight(n,c); //统计的权值传递给哈夫曼树
	 cout<<endl;
	
	 HuffmanCoding(HT,HC,w,c,n);
	
	 char slecta;
	 do
	 {
	  
	  HuffmanDecoding(HT,n);
	  cout<<endl;
	  
	  cout<<"您想要翻译另外一段密文吗？(Y继续，N退出)Y/N?"<<endl;
	  cin>>slecta;
	  if(slecta=='N' || slecta=='n')
		{
	 	   break;
		}
	
	 }while(slecta=='Y' || slecta=='y'); //用户选择是否翻译另外一段代码

	 cout<<"您想要对另外一段字符进行Huffman编码吗？(Y继续，N退出)Y/N?"<<endl;
	 
  	 cin>>slect;
	 	if(slect=='N' || slect=='n')
		{
	 	   system("exit");
		}
	}while(slect=='Y'|| slect=='y');   //用户选择是否对另外一段英文进行Huffman编码
    
	return 0;
}