?? 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;//動態(tài)分配數(shù)組存儲哈夫曼樹
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() //分辨字符類型以及權(quán)重
{
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<<"字符數(shù)目:"<<charnumber<<endl;
cout<<endl;
cout<<"字符權(quán)重統(tǒng)計:"<<endl;
for(i=0;i<charnumber;i++){
cout<<"字符:"<<hc[i+1].data<<' ';
cout<<"權(quán)重:"<<w[i]<<endl;
}
cout<<endl;
cout<<endl;
}
void gouzao(HuffmanTree &HT,char zifu[], int weight[], int n)
{ // w存放n個字符的權(quán)值(均>0)，構(gòu)造哈夫曼樹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];//社有一組權(quán)值存放于數(shù)組中，通過數(shù)組weight[]傳遞進(jìn)來
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最小的兩個節(jié)點，
// 其序號分別為s1和s2。
s1=s2=32767;
l=r=0; /*l和r是最小權(quán)重的兩個節(jié)點位置*/
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'; // 編碼結(jié)束符。
for (i=1; i<=n; ++i)
{ // 逐個字符求哈夫曼編碼
d.start = n+1; // 編碼結(jié)束符位置
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; //從根節(jié)點開始往下搜索
cout<<"請輸入一串二進(jìn)制碼: ";
cin>>b; //讀入一個二進(jìn)制碼
cout<<"經(jīng)譯碼后為: ";
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] 是葉子節(jié)點
{ cout<<HT[a].zifu; a=2*m-1; }
} cout<<endl;
}
void main()
{ cout<<"-------------------施行 鄒震 徐文杰 哈夫曼編碼------------------"<<endl;
cout<<"- Copyright by Shihang Zouzhen Xuwenjie -"<<endl;
cout<<"- 編碼規(guī)則：哈夫曼樹的左節(jié)點編0符，右節(jié)點編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.構(gòu)造哈夫曼樹"<<endl;
cout<<" 2.輸出字符對應(yīng)的哈夫曼編碼"<<endl;
cout<<" 3.輸入一串0 1代碼，進(jìn)行哈夫曼譯碼"<<endl;
cout<<" 4.結(jié)束本程序"<<endl;
cout<<"----------------------------------------------------------------"<<endl;
cin>>i;
while(j!=0)
{switch(i)
{//case 1:
case 1:
HTNode *HT;
gouzao(HT,zifu,weight,zifushumu);
cout<<" 節(jié)點 字符 權(quán)重 父節(jié)點 左子節(jié)點 右子節(jié)點"<<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.構(gòu)造哈夫曼樹"<<endl;
cout<<" 2.輸出字符對應(yīng)的哈夫曼編碼"<<endl;
cout<<" 3.輸入一串0 1代碼，進(jìn)行哈夫曼譯碼"<<endl;
cout<<" 4.結(jié)束本程序"<<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.構(gòu)造哈夫曼樹"<<endl;
cout<<" 2.輸出字符對應(yīng)的哈夫曼編碼"<<endl;
cout<<" 3.輸入一串0 1代碼，進(jìn)行哈夫曼譯碼"<<endl;
cout<<" 4.結(jié)束本程序"<<endl;
cout<<"----------------------------------------------------------------"<<endl;
cin>>i;
j=1;
break;
case 3:
gouzao(HT,zifu,weight,zifushumu);
decode(HT,zifushumu);
cout<<endl;
cout<<"請選擇操作:"<<endl;
cout<<" 1.構(gòu)造哈夫曼樹"<<endl;
cout<<" 2.輸出字符對應(yīng)的哈夫曼編碼"<<endl;
cout<<" 3.輸入一串0 1代碼，進(jìn)行哈夫曼譯碼"<<endl;
cout<<" 4.結(jié)束本程序"<<endl;
cout<<"----------------------------------------------------------------"<<endl;
cin>>i;
j=1;
break;
case 4:
cout<<"歡迎使用!"<<endl;
j=0;
break;
default:
cout<<"輸入有誤,重新輸入"<<endl;
break;
}
}
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -