f.cpp

哈弗曼编码 根据给定的字母表 数据结构试验

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string>
#include <iomanip>
using namespace std;
typedef struct{
	int weight;
	int parent,lchild,rchild;
}HTNode,*HuffmanTree;
int s1,s2;
char cha[]={' ',' ','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char chA[]={' ',' ','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
int weight[]={0,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 HC[27][27];
//------------找寻parent为0,权最小的两个节点----------------
void select(HuffmanTree &tree,int k) 

{

 int i;

 for (i=1;i<=k && tree[i].parent!=0 ;i++); s1=i;

 for (i=1;i<=k;i++)

    if (tree[i].parent==0 && tree[i].weight<tree[s1].weight) s1=i;

 for (i=1; i<=k ; i++)

    if (tree[i].parent==0 && i!=s1) break; s2=i;

 for (i=1;i<=k;i++)

    if ( tree[i].parent==0 && i!=s1 && tree[i].weight<tree[s2].weight) s2=i;

}
//---------------建树---------------
void creatHuffman(HuffmanTree &HT,char HC[27][27],int w[])
{
	int n=27;
	int m=2*n-1;
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
	HuffmanTree p;
	int i;
	for(p=HT,i=1;i<=n;++i)
	{
		p[i].weight=w[i];
	    p[i].lchild=0;
		p[i].rchild=0;
		p[i].parent=0;
			
	}
	for(i=n+1;i<=m;++i)
	{
		p[i].weight=0;
	    p[i].lchild=0;
		p[i].rchild=0;
		p[i].parent=0;
	}
	for(i=n+1;i<=m;++i)
	{
		select(HT,i-1);
		HT[s1].parent=i;
		HT[s2].parent=i;
		HT[i].lchild=s1;
		HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
}
//--------------利用建好的树对字母表进行编码-------------------
void HuffmanCoding(HuffmanTree &HT)
{
	char cd[27];
	cd[26]='\0';
	int c,int f,int start;
	int n=27;
    cout<<"哈弗曼编码表为："<<endl;
	cout<<"###############################################################################";
	for(int k=1;k<=n;k++)
	{
	     
		 start=n-1;
		for(c=k,f=HT[k].parent;f!=0;c=f,f=HT[f].parent)
		{
		   
			if(HT[f].lchild==c)
				cd[--start]='0';
			else cd[--start]='1';
			strcpy(HC[k],&cd[start]);
		
		}
		cout<<"##"<<cha[k]<<'('<<chA[k]<<')'<<"----->"<<setw(28)<<HC[k];
       
	}
	cout<<"##"<<"                                      #";
	cout<<"################################################################################";

}//编码
//--------------利用建好的树对输入的任意字符串进行编码--------------------
void toHuffman()
{
	
      int n=27;
	  cout<<"请输入您要编码的任意长度的字符串:";
	  char s;
	  s=getchar();
	  while((s = getchar()) != '\n')
	  {
		for(int j=1;j<=n;j++)
		{
           if(s==cha[j]||s==chA[j])
			   cout<<HC[j];
		}
		
	  }
	  cout<<endl;
	   system("pause");

}
//------------根据建好的树对字串进行译码-------------------
void HuffmanDeCoding(HuffmanTree &HT)
{
     
	 int n=27;
	 int m=2*n-1;
	 int j=0;
	 cout<<"请输入要译码的哈弗曼码：";
	 string s;
     cin>>s;
	 cout<<"译码后的结果为：";
	 for(int i=m;j<s.length();)
	 {
		 int c,f;
		 
		 for(f=i,c=HT[f].lchild;c>n;f=c)
		 {
			 if(s[j]=='0')
				 c=HT[f].lchild;
			 if(s[j]=='1')
				 c=HT[f].rchild;
			 j++;
			 if(j==s.length()&&c>n)
			 {
				 cout<<'*'<<"(*部分为无法解码部分)";
				 break;
			 }
		 }
		if(c<n)
		cout<<cha[c];
		
	 }
	 cout<<endl;
	 system("pause");
	 
}
//-------------------测试函数----------------------
void main()
{  
	
	HuffmanTree t; 
	creatHuffman(t,HC,weight);
	HuffmanCoding(t);
	while(1)
	{
	    char ch;
    	cout<<"|-------------------------------|"<<endl
		    <<"|----- 请输入您选择的操作：-----|"<<endl
            <<"|-----     1.编码          -----|"<<endl
	    	<<"|-----     2.译码          -----|"<<endl
	        <<"|-------------------------------|"<<endl;
	
	   cin>>ch;
	   switch(ch)
	   {
	     case '1':toHuffman(); break;
	     case '2':HuffmanDeCoding(t);break;
		 default:break;
	   }
	}
}