huffmancoding(usingclanguage).txt

来自「哈夫曼编码(用C语言编写), 可对输入的字符串进行加密解密」· 文本 代码 · 共 216 行

#include<stdio.h> 
#include<stdlib.h> 
#include<string.h> 
typedef struct htnode 
{ 
int ww,parent,llink,rlink; 
char cc,buffer[20]; //cc用来存放字母，buffer用来存放编码字符 
}datatype; 

struct httree 
{ 
int m; 
datatype * ht; 
}; 
typedef struct httree * phttree; 

phttree creatht(int m,char * n,int * w) 
{ 
phttree pht; 
int x1,x2,m1,m2; 
pht=(phttree)malloc(sizeof(struct httree)); 
if(pht==NULL) 
{ 
printf("申请空间失败！！\n"); 
return pht; 
} 
pht->m=m; 
pht->ht=(datatype *)malloc(sizeof(datatype)*(2*m-1)); 
for(int i=0;i<2*m-1;i++) 
{ 
pht->ht[i].llink=-1; 
pht->ht[i].rlink=-1; 
pht->ht[i].parent=-1; 
if(i<m) 
{ 
pht->ht[i].ww=w[i]; 
pht->ht[i].cc=n[i]; 
} 
else 
{ 
pht->ht[i].ww=-1; 
pht->ht[i].cc='^'; 
} 
} 
for(i=0;i<m-1;i++) 
{ 
m1=1000000; //有可能溢出 
m2=m1; 
x1=-1;x2=-1; 
for(int j=0;j<m+i;j++) 
{ 
if(pht->ht[j].ww<m1 && pht->ht[j].parent==-1) //寻找最小的数 
{ 
m2=m1; 
x2=x1; 
m1=pht->ht[j].ww; 
x1=j; 
} 
else if(pht->ht[j].ww<m2 && pht->ht[j].parent==-1) //寻找次小的数 
{ 
m2=pht->ht[j].ww; 
x2=j; 
} 
} 
pht->ht[x1].parent=m+i; //构造内部结点 
pht->ht[x2].parent=m+i; 
pht->ht[m+i].ww=m1+m2; 
pht->ht[m+i].llink=x1; 
pht->ht[m+i].rlink=x2; 
} 
return pht; 
} 

void bianma(phttree pht,FILE *f) //哈夫曼树编码 
{ 
int p,w; 
for(int i=0;i<pht->m;i++) 
{ 
int x=1,y=0; 
char bm[20]; 
p=pht->ht[i].parent; //取其父结点 
w=i; //取本次循环的数组下标 
printf("%c: ",pht->ht[i].cc); 
fprintf(f,"%c: ",pht->ht[i].cc); 
for(int j=0;j<20;j++) //令字符数组全为空 
{ 
pht->ht[i].buffer[j]='\0'; //令哈夫曼编码数组所有元素为结束符，否则会出错 
bm[j]=' '; //令bm数组所有元素为空字符，以便用来判断 
} 
bm[19]='\0'; //令bm数组最后一个元素为结束符，否则会出错 
while(p!=-1) //当前结点为树根的时候停止循环 
{ 
if(pht->ht[p].llink==w) //如果其左孩子为当前数组下标，则令编码为0 
{ 
bm[19-x]='0'; 
} 
else if(pht->ht[p].rlink==w) //如果其右孩子为当前数组下标，则令编码为1 
{ 
bm[19-x]='1'; 
} 
x+=1; 
w=p; //转换数组下标 
p=pht->ht[p].parent; //向上取父结点 
} 
for(j=0;j<20;j++) //输出字符数组的元素 
{ 
if(bm[j]!=' ' && bm[j]!='\0') 
{ 
pht->ht[i].buffer[y]=bm[j]; //如果bm元素不为空字符，则赋值给哈夫曼编码数组 
printf("%c",pht->ht[i].buffer[y++]); 
} 
} 
fprintf(f,"%s",pht->ht[i].buffer); 
y=0; 
printf("\n"); 
fputc('\n',f); 
} 
} 

void main() 
{ 
int m=27,r,i,j,k=0,l; 
char c[500],e[20]; 
char a[]=" "; 
FILE * f; 

/////////////// 初始化哈夫曼树 ////////////////////////////////////////// 

char n[27]={' ','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p', 
'q','r','s','t','u','v','w','x','y','z'}; 

int w[27]={186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1}; 
for(j=0;j<20;j++) //初始化数组 
e[j]='\0'; //令e数组的所有元素都为结束符，以便与哈夫曼编码比较 
f=fopen("data.txt","wr"); //打开文件 
if( f==NULL) 
{ 
printf("文件打开失败！\n"); 
exit(1); 
} 
phttree tree=creatht(m,n,w); //创建哈夫曼树 

////////////// 打印哈夫曼树 /////////////////////////////////////////// 
fprintf(f,"\t%s\t%s\t%s\t%s\t%s\n","字符","频度","父结点","左孩子","右孩子"); 
printf("\t字符\t频度\t父结点\t左孩子\t右孩子\n"); 
for(i=0;i<(m*2-1);i++) 
{ 
printf("%d\t%c\t%d\t%d\t%d\t%d\n",i,tree->ht[i].cc,tree->ht[i].ww, 
tree->ht[i].parent,tree->ht[i].llink,tree->ht[i].rlink); 
fprintf(f,"%d\t%c\t%d\t%d\t%d\t%d\n",i,tree->ht[i].cc,tree->ht[i].ww, 
tree->ht[i].parent,tree->ht[i].llink,tree->ht[i].rlink); 
} 
///////////// 打印哈夫曼编码 //////////////////////////////////////////// 

printf("\n此哈夫曼编码为：\n"); 
fprintf(f,"%s","\n此哈夫曼编码为：\n"); 
bianma(tree,f); 

//////////// 对字符串编码 ///////////////////////////////////////////////// 
printf("\n请输入要编码的字符串(以回车键结束输入):"); 
fprintf(f,"%s","\n请输入要编码的字符串(以回车键结束输入):"); 

gets(c); //获取字符串 
r=strlen(c); //获取字符串长度 
fprintf(f,"%s",c); 
printf("\n对应字符串的编码为："); 
fprintf(f,"\n\n%s","对应字符串的编码为："); 

for(i=0;i<r;i++) //用循环将字符编码 
{ 
for(j=0;j<m;j++) //从哈夫曼树中用循环寻找对应字符 
{ 
if(c[i]==tree->ht[j].cc) //找到对应字符，然后编码 
{ 
printf("%s",tree->ht[j].buffer); 
fprintf(f,"%s",tree->ht[j].buffer); 
break; 
} 
} 
} 
printf("\n"); 
fputc('\n',f); 

/////////////// 对编码进行译码 ////////////////////////////////////////////////////// 

printf("\n请输入要译码的编码："); 
fprintf(f,"\n%s","请输入要译码的编码："); 

gets(c); //获取字符串 
fprintf(f,"%s",c); 
printf("\n对应编码的字符串为："); 
fprintf(f,"\n\n%s","对应编码的字符串为："); 
r=strlen(c); //获取字符串长度 

for(i=0;i<r;i++) 
{ 
e[k++]=c[i]; //将第i个编码字符赋值给用来比较的数组 

for(j=0;j<tree->m;j++) //循环搜索哈夫曼编码 
{ 
if(strcmp(e,tree->ht[j].buffer)==0) //判断编码字符串与哈夫曼某个编码是否一样 
{ 
for(l=0;l<20;l++) //重新初始化e数组 
{ 
e[l]='\0'; //令e数组的所有元素都为结束符，以便与哈夫曼编码比较 
} 
printf("%c",tree->ht[j].cc); //找到符合的编码，然后打印对应的字符 
fprintf(f,"%c",tree->ht[j].cc); 
k=0; //使K指向e数组的首数组元素，以便重新装载编码字符 
break; 
} 
} 
} 
printf("\n\n"); 
fclose(f); //关闭文件,写出数据到文件 
}