数据结构设计哈夫曼编译码系统的设计与实现.docx
《数据结构设计哈夫曼编译码系统的设计与实现.docx》由会员分享，可在线阅读，更多相关《数据结构设计哈夫曼编译码系统的设计与实现.docx（21页珍藏版）》请在冰点文库上搜索。
数据结构设计哈夫曼编译码系统的设计与实现
哈夫曼编/译码系统的设计与实现
一、需求分析
1、问题描述
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。
对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。
试为这样的信息收发站设计一个哈夫曼编译码系统。
2、基本要求
（1）初始化（Initialzation）。
从数据文件DataFile.txt中读入字符及每个字符的权值，建立哈夫曼树HuffTree；
（2）编码（EnCoding）。
用已建好的哈夫曼树，对文件ToBeTran.txt中的文本进行编码形成报文，将报文写在文件Code.txt中；
（3）译码（Decoding）。
利用已建好的哈夫曼树，对文件CodeFile.txt中的代码进行解码形成原文，结果存入文件Textfile.txt中；
（4）输出（Output）。
输出DataFile.txt中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.txt及其报文Code.txt；输出CodeFile.txt及其原文Textfile.txt；
二、概要设计
1.数据结构
本程序需要用到以一个结构体HTNode，以及一个二维数组HuffmanCode。
2.程序模块
本程序包含两个模块，一个是实现功能的函数的模块，另一个是主函数模块。
系统子程序及功能设计
本系统共有七个子程序，分别是：
a.intmin1（HuffmanTreet,inti）//进行比较
b.voidselect（HuffmanTreet,inti,int*s1,int*s2）//求权值最小的两个数
c.voidHuffmanCoding（HuffmanTree*HT,HuffmanCode*HC,int*w,char*u,intn）///*w存放n个字符的权值（均>0）,构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC*/
d.voidInitialzation（HuffmanTree*HT,HuffmanCode*HC）//初始化
e.intEnCoding（HuffmanTree*HT,HuffmanCode*HC）//对文件ToBeTran.txt中的文本进行编码形成报文，将报文写在文件Code.txt中
f.intpipei（char*c,intn,HuffmanCode*HC）//在huffmancode寻找匹配的编码
g.voidDecoding（HuffmanTree*HT,HuffmanCode*HC）//对文件CodeFile.txt中的代码进行解码形成原文，结果存入文件Textfile.txt中
3.各模块之间的调用关系以及算法设计
主函数调用Initialzation，EnCoding，Decoding。
函数HuffmanCoding调用函数select。
函数select调用函数min1
函数Initialzation调用函数HuffmanCoding
函数Decoding调用函数pipei
三、详细设计
1.数据类型定义
typedefstruct
{
unsignedintweight;
unsignedintparent,lchild,rchild;
charch;
}HTNode,*HuffmanTree;/*动态分配数组存储赫夫曼树*/
typedefchar**HuffmanCode;/*动态分配数组存储赫夫曼编码表*/
2.系统主要子程序详细设计
a.构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC
voidHuffmanCoding（HuffmanTree*HT,HuffmanCode*HC,int*w,char*u,intn）/*算法6.12*/
{/*w存放n个字符的权值（均>0）,构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC*/
intm,i,s1,s2,start;
unsignedc,f;
HuffmanTreep;
char*cd;
if（n<=1）
return;
m=2*n-1;
*HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;/*0号单元未用*/
for（p=*HT+1,i=1;i<=n;++i,++p,++w,++u）
{
（*p）.ch=*u;
（*p）.weight=*w;
（*p）.parent=0;
（*p）.lchild=0;
（*p）.rchild=0;
}
for（;i<=m;++i,++p）
（*p）.parent=0;
for（i=n+1;i<=m;++i）/*建赫夫曼树*/
{/*在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2*/
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*））;
/*分配n个字符编码的头指针向量（[0]不用）*/
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））;
/*为第i个字符编码分配空间*/
strcpy（（*HC）[i],&cd[start]）;/*从cd复制编码（串）到HC*/
}
free（cd）;/*释放工作空间*/
}
b.初始化
voidInitialzation（HuffmanTree*HT,HuffmanCode*HC）//初始化
{
FILE*f1;
inti,n=0;
if（（f1=fopen（"DataFile.txt","r"））==NULL）
{
printf（"error\n"）;
}
intg[100];
charh[100];
printf（"从数据文件DataFile.txt中读入字符及每个字符的权值\n"）;
for（i=1;;i++）
{
fscanf（f1,"%c",&h[i]）;
if（h[i]=='#'）
break;
fscanf（f1,"%d",&g[i]）;
n++;
printf（"%c:
",h[i]）;
printf（"%d\n",g[i]）;
}
fclose（f1）;
HuffmanCoding（HT,HC,g,h,n）;
}
c.编码
intEnCoding（HuffmanTree*HT,HuffmanCode*HC）//对文件ToBeTran.txt中的文本进行编码形成报文，将报文写在文件Code.txt中
{
inti,j,m=0,n=0;
FILE*f1,*f2,*f3;
if（（f1=fopen（"DataFile.txt","r"））==NULL）
{
printf（"error\n"）;
}
intg[100];
charh[100];
for（i=1;;i++）
{
fscanf（f1,"%c",&h[i]）;
if（h[i]=='#'）
break;
fscanf（f1,"%d",&g[i]）;
n++;
}
fclose（f1）;
if（（f2=fopen（"ToBeTran.txt","r"））==NULL）
{
printf（"error\n"）;
}
printf（"从数据文件ToBeTran.txt中读入字符\n"）;
charu[100],a[100];
for（i=1;;i++）
{
fscanf（f2,"%c",&u[i]）;
if（u[i]=='#'）
break;
a[i]=u[i];
m++;
cout<}
cout<fclose（f2）;
if（（f3=fopen（"Code.txt","w"））==NULL）
{
printf（"error\n"）;
}
cout<<"输出报文"<for（i=0;ifor（j=1;j<=n;++j）
{
if（*（a+i）==（*HT）[j].ch）
{
printf（"%s",（*HC）[j]）;
fprintf（f3,"%s",（*HC）[j]）;
}
}
fclose（f3）;
cout<returnm;
}
intpipei（char*c,intn,HuffmanCode*HC）/*在huffmancode寻找匹配的编码*/
{
inti;
for（i=1;i<5;i++）
{
if（strcmp（c,（*HC）[i]）==0）
{
returni;
break;
}
}
return0;
}
d.译码
voidDecoding（HuffmanTree*HT,HuffmanCode*HC）//对文件CodeFile.txt中的代码进行解码形成原文，结果存入文件Textfile.txt中
{
inti=1,j=1,y=0,num=0,len,n=0,d,q,v,ii;
inta[2]={1,2};
charc[20];
for（i=0;i<20;i++）
c[i]='\0';
FILE*f1,*f4,*f5;
if（（f1=fopen（"DataFile.txt","r"））==NULL）//求权值个数n
{
printf（"error\n"）;
}
intg[100];
charh[100];
for（i=1;;i++）
{
fscanf（f1,"%c",&h[i]）;
if（h[i]=='#'）
break;
fscanf（f1,"%d",&g[i]）;
n++;
}
fclose（f1）;
if（（f4=fopen（"CodeFile.txt","r"））==NULL）//读字符
{
printf（"error\n"）;
}
printf（"从数据文件CodeFile.txt中读入代码\n"）;
charb[100];
for（i=1;;i++）
{
fscanf（f4,"%c",&b[i]）;
if（b[i]=='#'）
break;
cout<}
cout<fclose（f4）;
if（（f5=fopen（"TextFile.txt","w"））==NULL）
{
printf（"error\n"）;
}
cout<<"输出原文"<i=1;
j=1;
y=1;
while（true）
{
if（b[y]=='#'）
break;
for（j=0;j{
c[j]=b[y+j];
}
q=pipei（c,n,HC）;
if（q!
=0）
{
printf（"%c",（*HT）[q+1].ch）;
fprintf（f5,"%c",（*HT）[q+1].ch）;
y=y+i;
i=1;
}
else
i++;
for（ii=0;ii<20;ii++）
c[ii]='\0';
}
cout<}
四、测试与分析
1.显示主菜单，运行程序可以显示出如下界面。
2.初始化
在主菜单下选1，初始胡，即可从数据文件DataFile.txt中读入字符及每个字符的权值。
3.编码
在主菜单下选2，编码，将给定文件ToBeTran.txt中的字符输出报文。
4.译码
在主菜单下选3，完成译码功能，读取文件CodeFile.txt中的代码并输出原文。
5.退出
在主菜单下选4，退出系统
五、附录
1.哈夫曼编译码系统.h
#include
#include
#include
usingnamespacestd;
typedefstruct
{
unsignedintweight;
unsignedintparent,lchild,rchild;
charch;
}HTNode,*HuffmanTree;/*动态分配数组存储赫夫曼树*/
typedefchar**HuffmanCode;/*动态分配数组存储赫夫曼编码表*/
intmin1（HuffmanTreet,inti）
{/*函数voidselect（）调用*/
intj,flag;
unsignedintk=UINT_MAX;/*取k为不小于可能的值*/
for（j=1;j<=i;j++）
if（t[j].weightk=t[j].weight,flag=j;
t[flag].parent=1;
returnflag;
}
voidselect（HuffmanTreet,inti,int*s1,int*s2）
{/*s1为最小的两个值中序号小的那个*/
intj;
*s1=min1（t,i）;
*s2=min1（t,i）;
if（*s1>*s2）
{
j=*s1;
*s1=*s2;
*s2=j;
}
}
voidHuffmanCoding（HuffmanTree*HT,HuffmanCode*HC,int*w,char*u,intn）/*算法6.12*/
{/*w存放n个字符的权值（均>0）,构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC*/
intm,i,s1,s2,start;
unsignedc,f;
HuffmanTreep;
char*cd;
if（n<=1）
return;
m=2*n-1;
*HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;/*0号单元未用*/
for（p=*HT+1,i=1;i<=n;++i,++p,++w,++u）
{
（*p）.ch=*u;
（*p）.weight=*w;
（*p）.parent=0;
（*p）.lchild=0;
（*p）.rchild=0;
}
for（;i<=m;++i,++p）
（*p）.parent=0;
for（i=n+1;i<=m;++i）/*建赫夫曼树*/
{/*在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2*/
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*））;
/*分配n个字符编码的头指针向量（[0]不用）*/
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））;
/*为第i个字符编码分配空间*/
strcpy（（*HC）[i],&cd[start]）;/*从cd复制编码（串）到HC*/
}
free（cd）;/*释放工作空间*/
}
voidInitialzation（HuffmanTree*HT,HuffmanCode*HC）//初始化
{
FILE*f1;
inti,n=0;
if（（f1=fopen（"DataFile.txt","r"））==NULL）
{
printf（"error\n"）;
}
intg[100];
charh[100];
printf（"从数据文件DataFile.txt中读入字符及每个字符的权值\n"）;
for（i=1;;i++）
{
fscanf（f1,"%c",&h[i]）;
if（h[i]=='#'）
break;
fscanf（f1,"%d",&g[i]）;
n++;
printf（"%c:
",h[i]）;
printf（"%d\n",g[i]）;
}
fclose（f1）;
HuffmanCoding（HT,HC,g,h,n）;
}
intEnCoding（HuffmanTree*HT,HuffmanCode*HC）//对文件ToBeTran.txt中的文本进行编码形成报文，将报文写在文件Code.txt中
{
inti,j,m=0,n=0;
FILE*f1,*f2,*f3;
if（（f1=fopen（"DataFile.txt","r"））==NULL）
{
printf（"error\n"）;
}
intg[100];
charh[100];
for（i=1;;i++）
{
fscanf（f1,"%c",&h[i]）;
if（h[i]=='#'）
break;
fscanf（f1,"%d",&g[i]）;
n++;
}
fclose（f1）;
if（（f2=fopen（"ToBeTran.txt","r"））==NULL）
{
printf（"error\n"）;
}
printf（"从数据文件ToBeTran.txt中读入字符\n"）;
charu[100],a[100];
for（i=1;;i++）
{
fscanf（f2,"%c",&u[i]）;
if（u[i]=='#'）
break;
a[i]=u[i];
m++;
cout<}
cout<fclose（f2）;
if（（f3=fopen（"Code.txt","w"））==NULL）
{
printf（"error\n"）;
}
cout<<"输出报文"<for（i=0;ifor（j=1;j<=n;++j）
{
if（*（a+i）==（*HT）[j].ch）
{
printf（"%s",（*HC）[j]）;
fprintf（f3,"%s",（*HC）[j]）;
}
}
fclose（f3）;
cout<returnm;
}
intpipei（char*c,intn,HuffmanCode*HC）/*在huffmancode寻找匹配的编码*/
{
inti;
for（i=1;i<5;i++）
{
if（strcmp（c,（*HC）[i]）==0）
{
returni;
break;
}
}
return0;
}
voidDecoding（HuffmanTree*HT,HuffmanCode*HC）//对文件CodeFile.txt中的代码进行解码形成原文，结果存入文件Textfile.txt中
{
inti=1,j=1,y=0,num=0,len,n=0,d,q,v,ii;
inta[2]={1,2};
charc[20];
for（i=0;i<20;i++）
c[i]='\0';
FILE*f1,*f4,*f5;
if（（f1=fopen（"DataFile.txt","r"））==NULL）//求权值个数n
{
printf（"error\n"）;
}
intg[100];
charh[100];
for（i=1;;i++）
{
fscanf（f1,"%c",&h[i]）;
if（h[i]=='#'）
break;
fscanf（f1,"%d",&g[i]）;
n++;
}
fclose（f1）;
if（（f4=fopen（"CodeFile.txt","r"））==NULL）//读字符
{
printf（"error\n"）;
}
printf（"从数据文件CodeFile.txt中读入代码\n"）;
charb[100];
for（i=1;;i++）
{
fscanf（f4,"%c",&b[i]）;
if（b[i]=='#'）
break;
cout<
升级会员 