huffmancoding.cpp

霍夫曼編碼：包括畫出霍夫曼樹 編解碼等功能。簡單易用

/*Copyright by Shihang Zouzhen Xuwenjie
  May 4th 2008

  filename:Huffman coding
  Used for用來完成對輸入的一組字符串的哈夫曼編碼，譯碼，以及編寫哈夫曼樹的小程序
*/
#include<iostream.h>
#include<stdlib.h>
#define N 100
	int weighti[N];
    char zifui[N];
	int zifushumu;
typedef  struct{  
	 int  weight;
     int  parent,lchild,rchild;
	 char zifu;
}HTNode,*HuffmanTree;//動態分配數組存儲哈夫曼樹

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


#include "iostream.h"
#include "string.h"
#include <stdlib.h>
#define SMAX 100
#define CMAX 20
int ch;
int DEPTH;
class  hufftree;             //聲明
class  huffnode{
public:
	int	weight;
	int parent;
	int lchild;
	int rchild;
public:
	friend hufftree;
};
 
class huffcode{
private:
	int start;
	char data;
	char code[CMAX];
public:
	friend hufftree;
};
class hufftree{
public:
	int charnumber;
	char str[SMAX];
	char stack[CMAX];
	int *w;
	huffnode *ht;
	huffcode *hc;

	hufftree();
	~hufftree();
    void getstr();
	void getdawt();
    void huffcoding();
    void getout();
	void painttree();
	void TreePrinting();
};
hufftree::hufftree()
{charnumber=0;
w=NULL;
ht=NULL;
hc=NULL;
}

hufftree::~hufftree()
{

	delete []w;
	delete []ht;
	delete []hc;
}

void hufftree::getstr()               //獲得字符串
{
cout<<"請輸入一組字符串:";
  cin>>str;
}
void hufftree::getdawt()              //分辨字符類型以及權重
{
char *p;
int  wt[CMAX];
int top;
int strlength;
strlength=strlen(str);
top=0;
p=str;
if(strlen(str)<1) return;
for(int i=0;i<strlength;i++,p++) 
    {int tag=0;
     int j=0;
     while(tag==0&&j<=top){
		 if(*p==stack[j]) tag=1;
		 else j++;}
	 if(tag==0)
	 {stack[top]=*p;
	  wt[top]=1;
	  top++;}
	 else wt[j]++;}
zifushumu=charnumber=top;
hc=new huffcode[charnumber+1];
w=new int[charnumber];
for(i=0;i<charnumber;i++){
	weighti[i]=w[i]=wt[i];
	zifui[i]=hc[i+1].data=stack[i];}
	cout<<"字符數目:"<<charnumber<<endl;
	cout<<endl;
	cout<<"字符權重統計:"<<endl;

	
for(i=0;i<charnumber;i++){

	cout<<"字符:"<<hc[i+1].data<<' ';
	cout<<"權重:"<<w[i]<<endl;
	}

cout<<endl;
cout<<endl;


}

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<<"-               Copyright by Shihang Zouzhen Xuwenjie          -"<<endl;
    cout<<"-          編碼規則：哈夫曼樹的左節點編0符，右節點編1符        -"<<endl;
	cout<<"-                             ^_^                              -"<<endl;
    cout<<"-                 先初始化，請錄入一組字符串                   -"<<endl;
	cout<<"----------------------------------------------------------------"<<endl;
	cout<<endl;
	int i,m,k;
	int j=1;
	int b;
	int weight[N];
    char zifu[N];
   hufftree hftree1;
   hftree1.getstr();
   hftree1.getdawt();
	//cin>>m;




for (i=1;i<=zifushumu;i++)
{
zifu[i]=zifui[i-1];
weight[i]=weighti[i-1];
}

	cout<<endl;
		cout<<"----------------------------------------------------------------"<<endl;
    cout<<"請選擇操作:  "<<endl;
	cout<<"         1.構造哈夫曼樹"<<endl;
    cout<<"         2.輸出字符對應的哈夫曼編碼"<<endl;
    cout<<"         3.輸入一串0 1代碼，進行哈夫曼譯碼"<<endl;
	cout<<"         4.結束本程序"<<endl;
	cout<<"----------------------------------------------------------------"<<endl;
    cin>>i;
   	while(j!=0)
    {switch(i)
        {//case 1:
         




         case 1:
			HTNode *HT;
            gouzao(HT,zifu,weight,zifushumu);
	        cout<<"	節點	字符	權重	父節點	 左子節點  右子節點"<<endl;
			for (k=1;k<=2*zifushumu-1;k++)
			{ 
				 cout<<"	"<<k<<"	"<<HT[k].zifu<<"	"<<HT[k].weight<<"	"<<HT[k].parent;
				 cout<<"        "<<HT[k].lchild<<"         "<<HT[k].rchild<<endl;
			}
	        cout<<endl; 
    cout<<"請選擇操作:"<<endl;

    cout<<"         1.構造哈夫曼樹"<<endl;
    cout<<"         2.輸出字符對應的哈夫曼編碼"<<endl;
    cout<<"         3.輸入一串0 1代碼，進行哈夫曼譯碼"<<endl;
	cout<<"         4.結束本程序"<<endl;
	cout<<"----------------------------------------------------------------"<<endl;
			cin>>i;
			j=1;
			break;
		 case 2:
            gouzao(HT,zifu,weight,zifushumu);
			HuffmanCoding(HT,zifu,zifushumu);
	        cout<<endl;
    cout<<"請選擇操作:"<<endl;

    cout<<"         1.構造哈夫曼樹"<<endl;
    cout<<"         2.輸出字符對應的哈夫曼編碼"<<endl;
    cout<<"         3.輸入一串0 1代碼，進行哈夫曼譯碼"<<endl;
	cout<<"         4.結束本程序"<<endl;
	cout<<"----------------------------------------------------------------"<<endl;
			cin>>i;
			j=1;
			break;
		 case 3: 
            gouzao(HT,zifu,weight,zifushumu);
			decode(HT,zifushumu);
            cout<<endl;
    cout<<"請選擇操作:"<<endl;

    cout<<"         1.構造哈夫曼樹"<<endl;
    cout<<"         2.輸出字符對應的哈夫曼編碼"<<endl;
    cout<<"         3.輸入一串0 1代碼，進行哈夫曼譯碼"<<endl;
	cout<<"         4.結束本程序"<<endl;
	cout<<"----------------------------------------------------------------"<<endl;
			cin>>i;
			j=1;
            break;
         case 4:
			cout<<"歡迎使用!"<<endl;
			j=0;
            break;
         default:
            cout<<"輸入有誤,重新輸入"<<endl;
			break;
        }
	} 
}