输入一段英文原文，构造哈夫曼树，生成对应的编码表，输出原文对应的编码，或者是根据已经生成的编码表，输入一段二进制数编码，得到对应的字符原文。
#include<stdio.h>
#include<iostream>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
using namespace std;
//哈夫曼树的存储表示
typedef struct{
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
//存储两个最小的权值
typedef struct{
int s1;
int s2;
}MinCode;
void print1(HuffmanTree &HT,int m){
printf("HT List:\n");
printf("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n");
for(int i=1;i<=m;i++){
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\t\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
}
system("pause");
}
//void fun(char* str){
// for(int i=0,ch='\0';ch!='\n';++i){
// ch=getchar();
// if(i>=100){
// continue;
// }
// if(ch=='\n' || i==100-1){
// str[i] = '\0';
// continue;
// }
// str[i] = ch;
// }
//}
//查找最小的两个权值
MinCode Select(HuffmanTree HT,int n){
int k=1,s1,s2;
MinCode code;
int min=666666;
for(k=1;k<=n;k++){
// cout<<"aaaaaaaaaa"<<endl;
if(HT[k].parent==0&&HT[k].weight<min){
min=HT[k].weight;
s1=k;
}
}
int smin=666666;
for(k=1;k<=n;k++){
// cout<<"aaaaaaaaaa"<<endl;
if(HT[k].parent==0&&(HT[k].weight<smin)&&(k!=s1)){
smin=HT[k].weight;
s2=k;
}
}
code.s1=s1;
code.s2=s2;
return code;
}
//构造哈夫曼树
HuffmanCode CreateHuffmanTree(HuffmanTree &HT,HuffmanCode &HC,int n,int *w){
int i,s1=0,s2=0;
char a;
MinCode Min;
HuffmanTree p;
if(n<=1) {
return 0;
}
int m=2*n-1;
//printf("%d",m);
HT=new HTNode[m+1];//零号单元未用，所以需要分配m+1个单元，HT[m]表示根节点
//初始化
for(p=HT,i=0;i<=n;i++,p++,w++){
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
//----------- 初始化结束-------------
//进行删除，合并 构造新的哈夫曼树
for(i=n+1;i<=m;i++){
Min=Select(HT,i-1);
s1=Min.s1;s2=Min.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;
}
printf("是否打印哈夫曼树？y or n\n");
scanf("%s",&a);
if(a=='y'){
print1(HT,m);
}else if(a!='y') {
printf("将返回主界面\n");
}
// //打印哈夫曼树
// printf("HT List:\n");
// printf("Number\t\tweight\t\t\tparent\t\tlchild\t\trchild\n");
// for(i=1;i<=m;i++){
// printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\t\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
// }
//从叶子到根逆向球每个字符的哈夫曼编码，存储在编码表HC中
int start,c,f;
char *cd;
HC=new char *[n+1];
cd=new char[n];
cd[n-1]='\0';
for(int i=1;i<=n;i++){
start=n-1;
c=i;f=HT[i].parent;
while(f!=0){
--start;
if(HT[f].lchild==c){
cd[start]='0';
}else{
cd[start]='1';
}
c=f;f=HT[f].parent;
}
HC[i]=new char[n-start];
strcpy(HC[i],&cd[start]);
}
delete cd;
return HC;
}
//哈夫曼译码，对输入的10组合进行译码
void HuffmanTranslateCoding(HuffmanTree HT,int n,char *ch,char *N){
int m=2*n-1;
int i,j=0;
while (ch[j]!='\0'){
i=m;
while(0!=HT[i].lchild && 0!=HT[i].rchild){
if('0'==ch[j]){
i=HT[i].lchild;
}else{
i=HT[i].rchild;
}
++j;
}
printf("%c",N[i-1]);
}
printf("\n");
}
int main(){
int n,i,m;
int *w=NULL;
int chioce;
HuffmanCode HC;
HuffmanTree HT=NULL;
char N[100];
char tran[100];
while(1){
system("cls");
printf("\t\t######################################\n");
printf("\t\t# 1.初始化 #\n");
printf("\t\t# 2.解码 #\n");
printf("\t\t# 3.打印哈夫曼树 #\n");
printf("\t\t# 4.打印译码表 #\n");
printf("\t\t# 0.退出 #\n");
printf("\t\t# （使用前必须初始化！！！） #\n");
printf("\t\t######################################\n");
printf("输入选择： ");
scanf("%d",&chioce);
if(chioce==0) break;
switch(chioce){
case 1:
{
printf("\t\t输入字符串:\n");
scanf("%s",&N);
//fflush(stdin);
n=strlen(N);
m=2*n-1;
w=(int *)malloc((n+1)*sizeof(int *));
w[0]=0;
printf("\t\t输入权值\n");
for(i=1;i<=n;i++){
printf("w[%d]=",i);
scanf("%d",&w[i]);
}
//fflush(stdin);
CreateHuffmanTree(HT,HC,n,w);
//fflush(stdin);
system("pause");
break;
}
case 2:
{ //译码过程
printf("Input HuffmanTranslateCoding:\n");
scanf("%s",&tran);
//打印1，0组合对应字符
HuffmanTranslateCoding(HT,n,tran,N);
system("pause");
break;
}
case 3:print1(HT,2*n-1);
break;
case 4: {
printf("HuffmanCode:\n");
printf("Number\t\tWeight\t\tCode\n");
for(i=1;i<=n;i++){
printf("%c\t\t%d\t\t%s\n",N[i-1],w[i],HC[i]);
}
system("pause");
break;
}
default :
printf("\t\t没有此选项\n");
break;
}
}
return 0;
}
