#include
#include
#include
static float weights[]={12.702 ,9.056 ,8.167 ,7.507 ,6.966 ,6.749 ,6.327 ,
6.094 ,5.987 ,4.253 ,4.025 ,2.782 ,2.758 ,2.406 ,
2.360 ,2.228 ,2.105 ,1.974 ,1.929 ,1.492 ,0.978 ,
0.722 ,0.153 ,0.150 ,0.095 ,0.074 };//权值信息数组
static char values[]={'e','t','a','o','i','n','s',
'h','r','d','l','c','u','m',
'w','f','g','y','p','b','v',
'k','j','x','q','z'}; //字符数组信息
typedef struct{
float weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树
typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码表
int min(HuffmanTree t,int i){
int j,mark;
float k=26.4170;
for(j=1;j<=i;j++){
if(t[j].weight<k&&t[j].parent==0){
k=t[j].weight;
mark=j;
}
} //逐个迭代求解求小权值
t[mark].parent=1; //对选中节点进行标记,防止二次访问
return mark; //返回选中节点的索引值
} //返回i个节点中权值最小的树的根节点序号
void select(HuffmanTree t,int i,int &s1,int &s2){
int temp; //中间变量
s1=min(t,i);
s2=min(t,i);
if (s1>s2){
temp=s1;
s1=s2;
s2=temp;
}
} //从i个节点中选择两个权值最小的节点
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,float *w,int n){
int m,i,s1,s2,start; //中间变量
unsigned c,f;
HuffmanTree p;
char *cd;
if (n<=1){
return;
}
m=2*n-1; //所需节点总数
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.0;
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
} //初始化非终端节点
for (i=n+1;i<=m;++i){
select(HT,i-1,s1,s2);
HT[s1].parent=HT[s2].parent=i; //更新终端节点信息
HT[i].lchild=s1;
HT[i].rchild=s2; //更新非终端节点的子节点的索引值
HT[i].weight=HT[s1].weight+HT[s2].weight; //更新非终端节点的权值
} //创建哈夫曼树
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';//左分支为'0'
}
else{
cd[--start]='1';//右分支为'1'
}
}//根据节点的父节点索引值求解节点的哈夫曼编码
HC[i]=(char*)malloc((n-start)*sizeof(char));
//动态分配对应编码存储空间大小
strcpy(HC[i],&cd[start]);//字符串拷贝
}
free(cd);//释放内存空间
}
void coding(HuffmanCode HC){
int index;//索引变量
int textIndex;//电报正文索引值
int valueIndex;//电报正文字符的索引值
int teleLength;//电报正文包含的字符个数
int *codeIndex;//电报正文字符对应的哈夫曼编码表中的索引呢
char *teleText;//中间变量,存储电报正文
char *huCoding;//中间变量,用于存储电报正文的哈夫曼编码
int codeLength=0;//电报正文对应哈夫曼编码的总长度,初始化长度为0
printf("请输入电报正文长度:");
scanf("%d",&teleLength);
codeIndex=(int*)malloc(teleLength*sizeof(int));//分配用于存储编码表索引值的存储空间
teleText=(char*)malloc(teleLength*sizeof(char));
printf("请输入电报正文:");
scanf("%s",teleText);//输入电报正文字符串
for(textIndex=0;textIndex<strlen(teleText);textIndex++){
char textChar;
textChar=teleText[textIndex];
if((textChar<65)||(textChar>122)||(textChar<97&&textChar>90)){
printf("您输入了不合法字符%s!\n",teleText);
return;
}//如果输入非法字符,程序返回
if (textChar<96){
textChar=textChar+32;
}//如果电报正文为大写则进行转化
for(valueIndex=1;valueIndex<=26;valueIndex++){
if(values[valueIndex-1]==textChar){
codeIndex[textIndex]=valueIndex;//累计编码的索引值
codeLength+=strlen(HC[valueIndex]);//找到对应字符,累计编码长度值
break;
}
}//依次查找对应字符
} //根据哈夫曼编码表对电报正文进行编码
huCoding=(char*)malloc((codeLength+1)*sizeof(char));//动态分配存储电文编码的内存空间
for(index=0;index<=codeLength;index++){
huCoding[index]='\0';//字符串结束符
}//初始化上述内存数据
for(textIndex=0;textIndex<strlen(teleText);textIndex++)//strlen计数
{
huCoding=strcat(huCoding,HC[codeIndex[textIndex]]);//编码字符串连接
}//组装电文编码信息
printf("电报正文的哈夫曼编码:%s\n",huCoding);
free(teleText);
free(codeIndex);
free(huCoding);//释放内存空间
}
void decoding(HuffmanTree HT){
int index;//索引变量
int tempIndex=47;//记录临时索引值
char huCode;//单个编码
int huCodeLen;//电文编码的长度
char huCodes;//电文字符串
HTNode htNode;//哈夫曼树的节点
printf("请输入电报正文哈夫曼编码长度:");
scanf("%d",&huCodeLen);
huCodes=(char)malloc(huCodeLen*sizeof(char));//分配用于存储电文字符编码的存储空间
printf("请输入电报正文的哈夫曼编码字符串:");
scanf("%s",huCodes);//输入电报正文的编码字符串
htNode=HT[47];
for(index=0;index<strlen(huCodes);index++){
huCode=huCodes[index];//获取单个编码字符
if(tempIndex<=0){
printf("您输入的哈夫曼编码%s不合法!\n",huCodes);
return;
}//没有找到对应编码字符
if(huCode=='1'){
if(HT[htNode.rchild].lchild==0 && HT[htNode.rchild].rchild==0){
tempIndex=htNode.rchild;
printf("%c",values[tempIndex-1]);////遍历至叶子节点,找到一个电文子字符
htNode=HT[47];//再次指向根节点
}
else{
tempIndex=htNode.rchild;
htNode=HT[tempIndex];////继续遍历,记录当前节点的信息
}
} //向右遍历
else if(huCode=='0'){
if(HT[htNode.lchild].lchild==0 && HT[htNode.lchild].rchild==0){
tempIndex=htNode.lchild;
printf("%c",values[tempIndex-1]);//遍历至叶子节点,找到一个电文子字符
htNode=HT[47];//再次指向根节点
}
else{
tempIndex=htNode.lchild;
htNode=HT[tempIndex];//继续遍历,记录当前节点的信息
}
} //向左遍历
else{
printf("您输入的电报正文编码%s不合法!",huCodes);
return;
}
}
printf("\n");
} //将电报正文的哈夫曼编码进行译码操作
void printfHuffmanTree(HuffmanTree HT){
int index;
HTNode htNode;//哈夫曼树节点
printf("*************哈夫曼树表***********\n");
printf(" 权值 根节点 左子树 右子树\n");
for(index=1;index<48;index++){
htNode=HT[index];//获取当前树节点
printf("%12.4f%5d%6d%7d\n",htNode.weight,htNode.parent,htNode.lchild,htNode.rchild);
}
} //打印哈夫曼树表
void printfHuffmanCode(HuffmanCode HC){
int index;
printf("*******哈夫曼编码表*******\n");
for(index=1;index<=26;index++){
printf("%7c ------ ",values[index-1]);
printf("%s\n",HC[index]);
}
} //打印哈夫曼编码表
int main(){
HuffmanTree HT;
HuffmanCode HC;
HuffmanCoding(HT,HC,weights,26);//构造哈夫曼树
while(1){
int a;
printf("*******欢迎使用哈夫曼编码程序!*******\n");
printf("*********请输入您需要进行的操作*********\n");
printf("-->1.对电报正文编码 -->2.对电报编码译码\n");
printf("-->3.打印哈夫曼编码 -->4.打印哈夫曼树\n");
printf("****************选择0退出程序****************\n");
scanf("%d",&a);
getchar();
switch(a){
case 0:
return 0;
break;
case 1:
coding(HC);//编码,对已建好的哈夫曼树,对电报正文进行编码
break;
case 2:
decoding(HT);//译码,对电文的内容进行编码翻译处理
break;
case 3:
printfHuffmanCode(HC);
break;
case 4:
printfHuffmanTree(HT);
break;
default:
printf("您的输入有误!\n");
break;
}
}
}