#include<stdio.h>
#include<string.h>
#define maxsize 10000 /*編碼函數中，被編譯的字符串的最大長度*/
#define max 10000 /*最大字符的個數*/
typedef struct /*定義壹個huffnode結點 */
{
char data; /*數據域*/
int weight,parent,left,right;
}huffnode;
typedef struct /*定義壹個huffnode結點*/
{
char cd[max]; /*數組cd存放哈夫曼編碼*/
int start;
}huffcode;
huffcode hcd[max];
huffnode ht[2*max];
huffnode a[2*max];
void hfmtree ( huffnode ht[] ) /*創建壹棵哈夫曼樹*/
{
int i,k,x1,x2,n,m1,m2;
n = ht[0].weight;
for ( i=1; i<=2*n-1; i++ )
ht[i].parent = ht[i].left = ht[i].right = 0; /*初始化*/
for ( i=n+1; i<=2*n-1; i++ )
{
m1 = m2 = 200000000;
x1 = x2 = 0;
for ( k=1; k<=i-1; k++ ) /*k為可以進行比較的結點的下標*/
if ( ht[k].parent == 0 ) /*當前結點的父結點不存在時*/
if ( ht[k].weight < m1 ) /*當前結點的權值比最小權值還小時*/
{
m2 = m1;
x2 = x1;
m1 = ht[k].weight;
x1 = k;
}
else if ( ht[k].weight < m2 ) /*當前結點的權值比最小權值大但比第二最小權值小時*/
{
m2 = ht[k].weight;
x2 = k;
}
ht[x1].parent = ht[x2].parent = i;
ht[i].weight = ht[x1].weight + ht[x2].weight;
ht[i].left = x1;
ht[i].right = x2;
}
}
void output ( huffnode ht[] ) /*輸出哈夫曼編碼*/
{
huffcode d;
int i,n,c,f,k,x;
n = ht[0].weight;
for ( i=1; i<=n; i++ )
{
d.start = n+1;/*d.start為棧項*/
c = i; /*c存放當前結點*/
f = ht[i].parent;/*f存放當前結點的父結點*/
while ( f != 0 )
{
if ( ht[f].left == c ) /*若當前結點在其父結點的左邊時*/
d.cd[--d.start] = '0';
else
d.cd[--d.start] = '1'; /*當前結點在其父結點的右邊時*/
c = f; /*當前結點的父結點賦予c*/
f = ht[f].parent; /*c的父結點賦予f*/
}
hcd[i] = d; /*將當前結點的哈夫曼編碼賦予hcd[i]數組*/
}
printf ( "哈夫曼編碼: \n" );
for ( i=1; i<=n; i++ ) /*輸出各個結點的哈夫曼編碼*/
{
if ( ht[i].data == ' ' )
printf ( "' ' " );
else
printf ( "%c ",ht[i].data );
x = hcd[i].start;
for ( k=x; k<=n; k++ ) /*通過棧輸出哈夫曼編碼*/
printf ( "%c",hcd[i].cd[k] );
printf ( "\n" );
}
printf ( "* * * * * * * * * * * * * * * * * * * * \n\n" );
}
void coding ( huffcode hcd[],huffnode ht[] ) /*編碼函數，給定壹個字符串，輸出其對應的哈夫曼編碼*/
{
int i,j,n,m,k,x;
char in[maxsize],out[2*maxsize];/*in存放需編譯的字符串，out存放編譯後的代碼*/
m = 0;
printf ( "請輸入壹串字符串:" );
getchar();
gets(in);
n = strlen(in);
for ( i=0; i<n; i++ )
{
for ( j=1; j<=ht[0].weight; j++ ) /*ht[0].weight 存放的是帶權結點的個數*/
if ( in[i] == ht[j].data ) /*若輸入字符和壹個帶權結點相同*/
{
x = hcd[j].start;
for ( k=x; k<=ht[0].weight; k++ )
out[m++] = hcd[j].cd[k];
}
}
printf ( "編碼結果是:\n" );
for ( i=0; i<m; i++ )
printf ( "%c",out[i] );
printf ( "\n" );
}
void decoding ( huffcode hcd[],huffnode ht[] )/*譯碼函數，輸入壹個代碼流，輸出其對應的字符*/
{
int i,j,n,k,x,m,w;
char in[maxsize*2],out[maxsize];/*in數組存放代碼流，out數組存放對應數組*/
printf ( "請輸入由0和1組成的字符串:\n" );
scanf ( "%s",in );
n = strlen(in);
i = m = 0; /*i為in數組的下標，m為out數組的下標*/
while ( i<n )
{
for ( j=1; j<=ht[0].weight; j++ )/*ht[0].weight為帶權結點的個數*/
{
x = hcd[j].start;
for ( k=x,w=i; k<=ht[0].weight; k++,w++) /*k為hcd[j].cd[]的下標*/
if ( in[w] != hcd[j].cd[k] )
break;
if ( k > ht[0].weight )
{
out[m++] = ht[j].data;
break;
}
}
i = w;
}
printf ( "解碼結果是:\n" );
for ( i=0; i<m; i++ ) /*輸出結果*/
printf ( "%c",out[i] );
printf ( "\n" );
}
int main()
{
int select,index,i,k,len;
char str[10000];
printf ( "請輸入壹篇文章以便編碼:\n" );
gets (str);
for ( index=0; index<=200; index++ ){//初始化
a[index].data = '#';
a[index].weight = 0;
}
len = strlen(str);
k = 27;
for ( index=0; index<len; index++ ){//賦值
if ( str[index]>='A' && str[index]<='Z' ){
a[str[index]-'A'+1].data = str[index];
a[str[index]-'A'+1].weight++;
}
else{
a[k].data = str[index];
a[k].weight++;
k++;
}
}
k = 1;
for ( i=0; i<200; i++ )
if ( a[i].data != '#' ){
ht[k].data = a[i].data;
ht[k].weight = a[i].weight;
k++;
}
ht[0].weight = k-1;
hfmtree (ht); //建樹
output (ht);
do
{
printf ( "*************\n" );
printf ( "0.退出\n" );
printf ( "1.編碼\n" );
printf ( "2.解碼\n" );
printf ( "3.遍歷\n" );
printf ( "請輸入妳的選擇:" );
scanf ( "%d",&select );
if ( select == 0 )
{
printf ( "感謝使用!\n" );
return 0;
}
if ( select == 1 )
coding ( hcd,ht );
else if ( select == 2 )
decoding ( hcd,ht );
}while(1);
return 0;
}