2.cpp

1.构造对应的哈夫曼树 2.输出字符对应的哈夫曼编码 3.输入一串0 1代码

#include<iostream.h>
#include<stdlib.h>
#define N 100
typedef  struct{  
	 int  weight;
     int  parent,lchild,rchild;
	 char zifu;
}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树

typedef   struct{
	int start;
	char cd[N];
}HCNode,*Huffmancode;


void gouzao(HuffmanTree &HT,char zifu[], int weight[], int n) 
{	// w存放n个字符的权值(均>0)，构造哈夫曼树HT，
	// 并求出n个字符的哈夫曼编码HC
	int i, k, l, m, r, s1, s2;
	if (n<=1) return;
	m=2*n-1;
	HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));  // 0号单元未用
	for (i=1; i<=n; i++) 
	{ 	HT[i].zifu=zifu[i];
		HT[i].weight=weight[i];//设有一组权值存放于数组中，通过数组weight[]传递进来
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	}
	for (i=n+1; i<=m; i++)
	{ 	HT[i].zifu='-';
		HT[i].weight=0;
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	}
	for (i=n+1; i<=m; i++) 
	{  // 建哈夫曼树
		// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，
		// 其序号分别为s1和s2。
        s1=s2=32767;
        l=r=0;             /*l和r是最小权重的两个结点位置*/
        for(k=1;k<=i-1;k++)
            if  (HT[k].parent==0)
                if(HT[k].weight<s1)
                {
                    s2=s1;
                    r=l;
                    s1=HT[k].weight;
                    l=k;
                }
                else if (HT[k].weight<s2)
                {
                    s2=HT[k].weight;
                    r=k;
                }

                HT[l].parent=i;
                HT[r].parent=i;
                HT[i].weight=HT[l].weight+HT[r].weight;
                HT[i].lchild=l;
                HT[i].rchild=r;
    }

}
	//--- 从叶子到根逆向求每个字符的哈夫曼编码 ---
void HuffmanCoding(HuffmanTree &HT,char zifu[],int n)
{	HCNode hcd[N],d;
	int f,i,c,k;
	d.cd[n+1] = '\0';                         // 编码结束符。
	for (i=1; i<=n; ++i) 
	{                  // 逐个字符求哈夫曼编码
		d.start = n+1;                          // 编码结束符位置
		for (c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent) 
			// 从叶子到根逆向求编码
			if (HT[f].lchild==c) d.cd[--d.start] = '0';
			else d.cd[--d.start] = '1';
			hcd[i]=d;}
    cout<<"输出哈夫曼编码: "<<endl;
    for(i=1;i<=n;i++)
    {
        cout<<zifu[i]<<": ";
		for(k=hcd[i].start;k<=n;k++)
        cout<<hcd[i].cd[k];
        cout<<endl;
    }
} // HuffmanCoding
void decode(HuffmanTree &HT,int m)
  {   int a=2*m-1;
	  int  i;
	  char b[N];
      i=0;        //从根结点开始往下搜索
	  cout<<"请输入一串二进制码: ";
      cin>>b;    //读入一个二进制码
	  cout<<"经译码后为: ";
      while (b[i]!='\0')
	  {if(HT[a].lchild!=0)
         { if(b[i]=='0')  
				a=HT[a].lchild;
           else 
			    a=HT[a].rchild;
		   i++;}
       if(HT[a].lchild==0)       //tree[i] 是叶子结点
              { cout<<HT[a].zifu; a=2*m-1; }
	} cout<<endl;
}

void main()
{   cout<<"----------------------------------------------------------------"<<endl;
    cout<<"请选择操作:"<<endl;
    cout<<"         1.构造对应的哈夫曼树"<<endl;
    cout<<"         2.输出字符对应的哈夫曼编码"<<endl;
    cout<<"         3.输入一串0 1代码，进行哈夫曼译码"<<endl;
	cout<<"         4.结束本程序"<<endl;
	cout<<"----------------------------------------------------------------"<<endl;
	cout<<endl;
	int i,m,k;
	int j=1;
	cout<<"请输入字符个数: ";
	cin>>m;
    int weight[N];
    char zifu[N];
	for(i=1;i<=m;i++)
	{   cout<<"请输入第"<<i<<"个字符及其对应权值"<<endl;
		cin>>zifu[i];
		cin>>weight[i];
	}
	cout<<endl;
    cout<<"请选择操作:  ";
    cin>>i;
   	while(j!=0)
    {switch(i)
        {case 1:
			HTNode *HT;
            gouzao(HT,zifu,weight,m);
	        cout<<"	结点	zifu	weight	parent	lchild	rchild"<<endl;
			for (k=1;k<=2*m-1;k++)
			{ 
				 cout<<"	"<<k<<"	"<<HT[k].zifu<<"	"<<HT[k].weight<<"	"<<HT[k].parent;
				 cout<<"	"<<HT[k].lchild<<"	"<<HT[k].rchild<<endl;
			}
	        cout<<endl;
			cout<<"请选择操作:  ";
			cin>>i;
			j=1;
			break;
		 case 2:
            gouzao(HT,zifu,weight,m);
			HuffmanCoding(HT,zifu,m);
	        cout<<endl;
			cout<<"请选择操作:  ";
			cin>>i;
			j=1;
			break;
		 case 3: 
            gouzao(HT,zifu,weight,m);
			decode(HT,m);
            cout<<endl;
			cout<<"请选择操作:  ";
			cin>>i;
			j=1;
            break;
         case 4:
			cout<<"欢迎使用!"<<endl;
			j=0;
            break;
         default:
            cout<<"输入有误,重新输入"<<endl;
			break;
        }
	} 
}