利用哈夫曼編碼進行通訊，可以壓縮通訊的資料量，提高傳輸效率，縮簡訊息的傳輸時間，還有一定的保密性。現在要求編寫一程式模擬傳輸過程，實現在傳送前將要傳送的字元資訊進行編碼，然後進行傳送，接收後將傳來的資料進行譯碼，即將資訊還原成傳送前的字元資訊，原始碼在最後。
工具/原料
vc2010
電腦
方法/步驟
在本例中設定傳送者和接受者兩個功能，
傳送者的功能包括：
①輸入待傳送的字元資訊；
②統計字元資訊中出現的字元種類數和各字元出現的次數（頻率）；
②根據字元的種類數和各自出現的次數建立哈夫曼樹；
③利用以上哈夫曼樹求出各字元的哈夫曼編碼；
④將字元資訊轉換成對應的編碼資訊進行傳送。
接受者的功能包括：
①接收發送者傳送來的編碼資訊；
②利用上述哈夫曼樹對編碼資訊進行翻譯，即將編碼資訊還原成傳送前的字元資訊。
從以上分析可發現，在本例中的主要演算法有三個：
（1）哈夫曼樹的建立；
（2）哈夫曼編碼的生成；
（3）對編碼資訊的翻譯。
1.演算法思想
輸入字串，建立求頻率和即求權重函式，將資料返回到哈夫曼函式中，求出每個字元的編碼，將資料返回到譯碼函式中進行運算得到編碼。
.除錯分析、測試結果
先手動輸入一段字元，將其先匯入頻率計算函式計算其權重， 然後返回到主函式裡在被哈夫曼建構函式呼叫
接收資訊，即呼叫譯碼函式
主函式呼叫
frequence( r, m,n,t,R);求頻率函式
HuffmanCoding(HT,HC,n,t );哈夫曼編碼函式
change(r, R, m,HC, Z);譯碼函式
選舉函式
選出父母為0，且權最小的兩個節點，賦值給s1和s2
程式碼入下
權重計算函式
通過不斷的比較迴圈求出每個字元的權重
原始碼集合
#include "stdafx.h"
#include
# include
# include
# include
# include
using namespace std;
typedef struct HTNode
{
char zf;
int weight;
int parent,lchild,rchild;
}*HuffmanTree;
typedef char* * HuffmanCode;
void select(HuffmanTree HT,int i,int& s1,int& s2)
{
int j,k=1;
while(HT[k].parent!=0)
k++;
s1=k;
for(j=1;j<=i;++j)
if(HT[j].parent==0&&HT[j].weight
s1=j;
k=1;
while((HT[k].parent!=0 k==s1))
k++;
s2=k;
for(j=1;j<=i;++j)
if(HT[j].parent==0&&HT[j].weight
s2=j;
}
char* HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int *w,int n)
{
if(n<=1)
{cout<<"無法生成樹"<
int m=2*n-1;
HuffmanTree p;
int i;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT+1, i=1;i<=n;++i,++p,++w)
{
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;++i,++p)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(i=n+1;i<=m;++i)
{
int s1; int s2;
select(HT,i-1, s1, s2);
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 ;
}
char * cd;
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
cd=(char*)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;++i)
{
int start=n-1;
HuffmanTree f;
for( int 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));
strcpy(HC[i],&cd[start]);
cout<<"HT["<
}
free(cd);
return* HC;
}
int frequence(char * r,int i,int *n ,int &_t,char R[100])
{
int t=0;
for(int g=1;g
{
int y=0;
char x;
char a;
int z=1;
if(g!=0)
{
int b=g;
for(;b!=0;--b)
{
if(r[g]==r[b-1]) {goto loop;}
}
}
for(a=r[g];y
{
x=r[y];
if(x==a&&y!=g) z++;
else z=z;
}
R[t]=r[g];
n[t]=z;
t++;
cout<<"字元"<
loop:;
}
_t=t;
return *n;
}
void change(char *r,char R[100],int m,HuffmanCode& HC,char *Z[100])
{
for(int g=1;g
{
for(int i=1;i
{
if(r[g]==R[i])
{
int o=1;
cout<
Z[o]=HC[i];
o++;
}
}
}
cout<<"是否接收"<
int v;
cin>>v;
if (v==2)
cout<
}
int _tmain(int argc, _TCHAR* argv[])
{
HuffmanTree HT;
HuffmanCode HC;
char *Z[100];
for(;;)
{
int t;
char R[100];
cout<<"----------歡迎進入哈夫曼編碼通訊系統----------"<
cout<<"選單："<
cout<<"\t\t1.傳送資訊"<
cout<<"\t\t2.接收資訊"<
int v;
cin>>v;
char r[100];
if(v==1)
{
char r[100];
cout<<"請輸入您要傳送的資訊"<
cin.getline (r,100,'#');
int m;
m=strlen(r);
int N[100], *n;
n=N;
frequence( r, m,n,t,R);
HuffmanCoding(HT,HC,n,t );
change(r, R, m,HC, Z);
}
else
cout<<"您沒有待接收資訊"<
}
}