Question

哈夫曼编码与压缩 输入一段文本，统计其中字符出现频率，设计相应的haffman树和haffman码，并完成对该段文

1、统计字符串中字符的总类以及各类字符的个数的函数，
2、实现构造haffman树的函数
3、haffman编码的函数
4、建立正文的编码文件的函数
5、建立代码文件的译码函数
6、在主函数中设计一个简单的菜单，分别调试上述算法

Answer 1

#include<iostream.h>
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
struct HuffmanTree
{
int weight;
int parent,lchild,rchild;
char ch;
};
typedef char** HuffmanCode;

struct return_value_sel
{
int re_s1;
int re_s2;

};
struct return_value_def
{
char re_p[100];
int *re_in;
int re_count;
};
struct return_value_HTHC
{
HuffmanTree *re_HT;
HuffmanCode re_HC;

};
return_value_def def_wei(char in_ch[])
{
char ch[100];
int ch_wei[100];
int i,j,n = 0,tab = 1;
return_value_def re;

for(i = 0;in_ch[i] != '\0';i++)
{
for(j = 0;j <= n;j++)
{
if(ch[j] == in_ch[i])
{
ch_wei[j]++;
tab = 1;
break;
}
else
tab = 0;
}
if(tab == 0)
{
ch[n] = in_ch[i];
ch_wei[n] = 1;
n++;

}
}
ch[n] = '\0';
strcpy(re.re_p,ch);
re.re_in = ch_wei;
re.re_count = n;
return re;
}

return_value_sel Select(HuffmanTree* HT,int i)
{
return_value_sel re;
int t = i;
int s1,s2,HT_wei = HT[i].weight;

for(;i>=1;i--)
if(HT[i].parent==0 && HT_wei>=HT[i].weight)
{HT_wei = HT[i].weight; s1 = i;}
if(s1==t)
{
HT_wei = HT[t-1].weight;

}
else
{
HT_wei = HT[t].weight;

}
for(i=t;i>=1;i--)
if(HT[i].parent==0 && HT_wei>=HT[i].weight && i!=s1)
{HT_wei = HT[i].weight; s2 = i;}
re.re_s1 = s1;
re.re_s2 = s2;
return re;

}

return_value_HTHC HuffmanCoding(HuffmanTree *HT,int *w,int n,char ch_in[])
{
int m,i;
HuffmanTree *p;
char *cd;
HuffmanCode HC;
return_value_HTHC re_value_HTHC;
return_value_sel get_re;

if(n<=1) exit(0);
m = 2 * n - 1;

HT = (HuffmanTree*)malloc((m+1)*sizeof(HuffmanTree));

for(p=HT,i=1,p++;i<=n;++i,++p,++w)
{
p->weight = *w;
p->lchild = 0;
p->rchild = 0;
p->parent = 0;
p->ch = ch_in[i-1];

}
for(;i<=m;++i,++p)
{
p->weight = 0;
p->lchild = 0;
p->rchild = 0;
p->parent = 0;
p->ch = NULL;

}
for(i=n+1;i<=m;++i)
{
get_re = Select(HT,i-1);
HT[get_re.re_s1].parent = i;
HT[get_re.re_s2].parent = i;
HT[i].lchild = get_re.re_s1;
HT[i].rchild = get_re.re_s2;
HT[i].weight = HT[get_re.re_s1].weight + HT[get_re.re_s2].weight;

}

int c,f,start,j=0;
HC = (HuffmanCode)malloc((n+1)*sizeof(char*));
cd = (char *)malloc(n*sizeof(char));

cd[n-1] = '\0';
for(i=1;i<=n;++i)
{

start = n-1;
for(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[i].ch<<"的编码为: "<<HC[i]<<endl;

}
free(cd);

re_value_HTHC.re_HC = HC;
re_value_HTHC.re_HT = HT;

return re_value_HTHC;
}

void HuffmanTrans(char* tran_ch,HuffmanTree *HT,int count)
{
int i,n=count;
cout<<"译码结果为:"<<endl;
for(i=0;tran_ch[i]=='0'||tran_ch[i]=='1';i++)
if(tran_ch[i]=='0')
{
n = HT[n].lchild;
if(HT[n].lchild==0&&HT[n].rchild==0)
{
cout<<HT[n].ch;
n = count;
}
}
else
{
n = HT[n].rchild;
if(HT[n].lchild==0&&HT[n].rchild==0)
{
cout<<HT[n].ch;
n = count;
}
}
cout<<endl;
}

void main()
{
char edit_str[100],trans_str[1000],trans_str1[1000];
int m[100];
int i,n,j,t=0;
HuffmanTree *HT;
return_value_def get_value_def;
return_value_HTHC get_value_HTHC;
int start1 = 0;
char choose_re = 'y',choose,ch[10];

while(choose_re=='y'||choose_re=='Y')
{
cout<<"请选择您所将进行的操作！"<<endl;
cout<<"(1)字符编码"<<endl
<<"(2)需要对已编码过的字符译码"<<endl
<<"(3)通过输入进行译码"<<endl
<<"请输入您的选择:";
cin>>ch;
choose = ch[0];
for(;;)
{
if(choose != '1'&&choose!='2'&&choose!= '3'&&choose!='0')
{
cout<<"输入错误，请重新输入"<<endl;
cout<<"1、字符编码"<<endl
<<"2、对编码过的字符译码"<<endl
<<"3、通过输入进行译码"<<endl
<<"0、退出"<<endl
<<"清输入您要进行的选择:";
cin>>ch;
choose = ch[0];
}
else
break;
}
switch(choose)
{
case '1':
cout<<"请输入您要编码的字符串:"<<endl;
cin>>edit_str;
cout<<"进行编码..."<<endl;
get_value_def = def_wei(edit_str);
for( i=0;i<get_value_def.re_count;i++)
{
m[i] = *(get_value_def.re_in+i);
}
HT = (HuffmanTree*)malloc((2*get_value_def.re_count)*sizeof(HuffmanTree));
get_value_HTHC = HuffmanCoding(HT,m,get_value_def.re_count,get_value_def.re_p);
cout<<"编码为:"<<endl;
for(n=0;edit_str[n]!='\0';n++)
for(j=0;j<=get_value_def.re_count;j++)
if(edit_str[n]==get_value_HTHC.re_HT[j].ch)
{
cout<<get_value_HTHC.re_HC[j];
for(int x=0;get_value_HTHC.re_HC[j][x]=='0'||get_value_HTHC.re_HC[j][x]=='1';t++,x++)
trans_str1[t]=get_value_HTHC.re_HC[j][x];

}

cout<<endl;
start1 = 1;
break;
case '2':
if(start1!=1)
{
cout<<"您还没有进行建立编码表,请先执行第一步操作!!"<<endl;
break;
}
HuffmanTrans(trans_str1,get_value_HTHC.re_HT,2*get_value_def.re_count-1);

break;
case '3':
if(start1!=1)
{
cout<<"您还没有进行建立编码表,请先执行第一步操作!!"<<endl;
break;
}
cout<<"请输入您要译的代码:"<<endl;
cin>>trans_str;
for(i=0;trans_str[i]!='\0';i++)
if(trans_str[i]!='0'&&trans_str[i]!='1')
{
cout<<"输入中有非法字符，请重新输入!!"<<endl;
cout<<"请输入您要译的代码:"<<endl;
cin>>trans_str;
}

cout<<endl;
HuffmanTrans(trans_str,get_value_HTHC.re_HT,2*get_value_def.re_count-1);
break;
case '0':
break;
}
cout<<"是否继续进行操作(是:y 否:n )"<<endl;
cin>>choose_re;
for(;;)
{if(choose_re != 'y'&&choose_re != 'Y'&&choose_re != 'n'&&choose_re != 'N')
{
cout<<"输入错误请重新输入!!"<<endl;
cout<<"是否继续进行操作(是:y 否:n )"<<endl;
cin>>choose_re;
}
else
break;
}

}

}