哈夫曼编码课程设计.docx
《哈夫曼编码课程设计.docx》由会员分享，可在线阅读，更多相关《哈夫曼编码课程设计.docx（16页珍藏版）》请在冰点文库上搜索。
哈夫曼编码课程设计
#include"stdio.h"//输入、输出函数
#include"stdlib.h"//定义杂项函数及内存分配函数
#include"string.h"
#defineM100
#defineN20
typedefcharElemType;
intn=0,m;//叶子结点个数，编码总长
charcode[M];
charcode2[M];
charresult[M];
typedefstruct//哈夫曼树的结点类型
{
chardata;
doubleweight;
intparent;//双亲节点
intlchild;//左孩子结点
intrchild;//右孩子结点
}HTNode;
typedefstruct//每个哈夫曼编码的类型
{
intcd[N];
intstart;
}HCode;
typedefstruct//串的类型定义
{
ElemTypedata[M];
intlen;
}sqstring;
intmenu（）//菜单系选择函数
{
intc;
do{
printf（"********************************************************\n"）;
printf（"\t\t****哈夫曼树的应用****\n"）;
printf（"\t\t1.输入字符统计后输出\n"）;
printf（"\t\t2.构造哈夫曼树并输出\n"）;
printf（"\t\t3.进行哈夫曼编码并输出\n"）;
printf（"\t\t4.保存编码到文件\n"）;
printf（"\t\t5.从文件读出编码后译码输出\n"）;
printf（"\t\t0.退出程序\n"）;
printf（"\t\t请选择（0-6）:
\n"）;
printf（"********************************************************\n"）;
scanf（"%d",&c）;
}while（c<0||c>6）;
returnc;/*返回选择*/
}
voidshuru（sqstring&s,charcstr[]）//输入字符串并统计后输出
{intp;
inti=0,k=0;
printf（"请输入一串字符:
"）;
getchar（）;
gets（cstr）;
for（i;cstr[i]!
='\0';i++）//只把a-z或A-Z赋给串s
{
if（（cstr[i]>='a'&&cstr[i]<='z'）||（cstr[i]>='A'&&cstr[i]<='Z'））
{
s.data[k]=cstr[i];k++;}
}
s.len=k;
if（s.len>0）
{printf（"输入的字符串为:
"）;
for（p=0;pprintf（"%c",s.data[p]）;
printf（"\n"）;
}
printf（"串字符长度为:
%d\n",s.len）;
}
voidtongji（sqstring&s,HTNodeht[]）//计算频率并赋给哈夫曼树
{
inti=0,j;
inta[26]={0};
for（j=0;j{
if（s.data[j]>='a'&&s.data[j]<='z'）a[s.data[j]-'a']++;
if（s.data[j]>='A'&&s.data[j]<='Z'）a[s.data[j]-'A']++;
}
for（intk=0;k<26;k++）//计算叶子结点的个数
{
if（a[k]!
=0）
n++;
}
j=0;
for（k=0;k<26;k++）//计算频率，把字符送入ht
{
if（a[k]!
=0）
{
ht[j].data=（char）（k+97）;
ht[j].weight=1.0*a[k]/s.len;
j++;
}
}
printf（"字符种类为:
%d\n",n）;
printf（"\n"）;
}
voidCreateHT（HTNodeht[],intn）//构造哈夫曼树后输出
{
inti,k,lnode,rnode;
doublemin1,min2;
for（i=0;i<2*n-1;i++）
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for（i=n;i<2*n-1;i++）//构造哈夫曼树
{
min1=min2=32767;
lnode=rnode=-1;//最小权值的两个位置
for（k=0;k<=i-1;k++）
if（ht[k].parent==-1）//只在尚未构造二叉树的结点中查找
{
if（ht[k].weight{
min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k;
}
elseif（ht[k].weight{
min2=ht[k].weight;rnode=k;;
}
}
ht[i].data='';
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;
ht[i].rchild=rnode;
ht[lnode].parent=i;
ht[rnode].parent=i;
}
printf（"序号---字母----权重----双亲结点---左孩子结点--右孩子结点\n"）;
for（i=0;i{
printf（"%3d%c%3.3lf%3d%3d%3d",i,
ht[i].data,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild）;
printf（"\n"）;}
for（i=n;i<2*n-1;i++）
printf（"%3d%c%3.3lf%3d%3d%3d\n",
i,ht[i].data,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild）;
}
voidCreatHCode（HTNodeht[],HCodehcd[],intn,sqstrings）//进行哈夫曼编码后输出
{
inti,f,j,c;
HCodehc;
for（i=0;i{
hc.start=n;c=i;
f=ht[i].parent;
while（f!
=-1）
{
if（ht[f].lchild==c）
{
hc.cd[hc.start--]='0';
}
else
{hc.cd[hc.start--]='1';
}
c=f;f=ht[f].parent;
}
hc.start++;
hcd[i]=hc;
}
for（i=0;i{
for（j=0;jif（s.data[i]==ht[j].data||s.data[i]==ht[j].data+32）
{
for（intk=hcd[j].start;k<=n;k++）
{
code[m]=hcd[j].cd[k];
m++;
}
}
}
printf（"各个结点对应的编码:
\n"）;
for（i=0;i{
printf（"%c--",ht[i].data）;
for（j=hcd[i].start;j<=n;j++）//输出哈夫曼编码
printf（"%c",hcd[i].cd[j]）;
printf（"\n"）;
}
printf（"输入的字符串为:
"）;
for（i=0;iprintf（"%c",s.data[i]）;
printf（"\n"）;
printf（"对应的字符串编码为:
"）;
for（i=0;iprintf（"%c",code[i]）;
printf（"\n"）;
}
intfindsubstr（char*S,intcm,HCodehcd[],intn,int&pos）//--------哈夫曼译码
{
inti,k,j;
if（pos>cm）return-1;
for（i=0;i{
j=pos;
for（k=hcd[i].start;k<=n;k++）
{
if（S[j]==hcd[i].cd[k]）
j++;
else
break;
}
if（k>n）
{
pos=j;
returni;
}
}
return-1;
}
intRecode（char*S,intcm,HTNodeht[],HCodehcd[],intn）//输出译码结果
{
charstrresult[80];
strcpy（strresult,""）;
intpos=0;
printf（"\n将其译码得:
"）;
while（pos{
intresult=findsubstr（S,cm,hcd,n,pos）;
if（result!
=-1）
{
printf（"%c",ht[result].data）;
}
else
returnfalse;
}
returntrue;
}
voidWritetoText（charresult[],charlastValueBits,intbyteCount）//将记录写入文件
{
FILE*fp;//定义文件指针
charfilename[20];//定义文件名
printf（"\t\t将编码保存入文件\n"）;//输入文件名
printf（"\t\t请输入文件名:
"）;
scanf（"%s",filename）;
strcat（filename,".txt"）;
if（（fp=fopen（filename,"wb"））==NULL）//打开文件
{
printf（"\t\t不能打开文件\n"）;
return;
}
fwrite（（void*）&lastValueBits,1,1,fp）;
fwrite（（void*）result,1,byteCount,fp）;
fclose（fp）;//关闭文件
printf（"\t\t保存成功!
\n"）;//返回成功信息
}
voidread（charresult[],int&lastValueBits,int&count）//从文件中读出
{
FILE*fp;
charfilename[20];
printf（"请输入文件名:
"）;
scanf（"%s",filename）;/*输入文件名*/
strcat（filename,".txt"）;
if（（fp=fopen（filename,"rb"））==NULL）
{
printf（"不能打开文件!
\n"）;
exit
（1）;
}
fread（（void*）&lastValueBits,1,1,fp）;
inti=0;
intrdCount=0;
do
{
rdCount=fread（（void*）（result+i）,1,1,fp）;
i+=rdCount;
}while（rdCount）;
count=i;//最后一个Byte中二进制的有效位数
fclose（fp）;
}
voidByteToStr（char*source,constcharresult）//二进制转ASCII
{
intmask=0x80;
for（inti=0;i<8;i++）
{
if（result&mask）
{
*（source+i）='1';
}
else
{
*（source+i）='0';
}
mask>>=1;
}
*（source+i）=0;
}
intstringToByte（char*source,char&result）//将ASCII转换成二进制
{
chartmp=0;
intvalueBits=0;
for（inti=0;i<8;i++）
{if（source[i]=='1'）
{
tmp<<=1;
tmp++;
valueBits++;
}
elseif（source[i]=='0'）
{
tmp<<=1;
valueBits++;
}
elseif（source[i]==0x00）
{
tmp<<=8-i;
break;
}
}
result=tmp;
returnvalueBits;//记录有效位数
}
voidmain（）///主函数
{
HTNodeht[M];
HCodehcd[M];
sqstrings;
inti,a=0;
charcstr[M];
intbyteCount=0;//有效字节数
intvalueBits=0;//最后一个字节的有效位数
intcount=0;
for（;;）
{
switch（menu（））
{
case1:
system（"cls"）;
shuru（s,cstr）;
tongji（s,ht）;
a=1;
printf（"各个字符的频率为:
\n"）;
for（i=0;i{
printf（"%c:
%3.3lf",ht[i].data,ht[i].weight）;
printf（"\n"）;}
break;
case2:
system（"cls"）;
if（a==0）
printf（"请先输入字符!
\n"）;
elseCreateHT（ht,n）;
break;
case3:
system（"cls"）;
if（a==0）
printf（"请先输入字符并构造哈夫曼树!
\n"）;
elseCreatHCode（ht,hcd,n,s）;
break;
case4:
system（"cls"）;
for（i=0;i{valueBits=stringToByte（code+i,result[i/8]）;
byteCount++;}
WritetoText（result,valueBits,byteCount）;
break;
case5:
system（"cls"）;
if（byteCount==0）printf（"文件为空!
\n"）;
else
{intcount=0;
read（result,valueBits,count）;
intrdsize=0;
for（inti=0;i{ByteToStr（code+i*8,result[i]）;}
code[i*8-（8-valueBits）]=0;//（8-valueBits）为求最后一位多加的0的个数，求出的二进制重新存入C
printf（"\n"）;
printf（"文件内容破译后是:
%s",code）;
intclength=strlen（code）;
if（!
Recode（code,clength,ht,hcd,n））
printf（"译密失败\n"）;
printf（"\n"）;
}
break;
case0:
exit（0）;
}
}
}
升级会员 