哈夫曼码编、译码器的实现

1、综合实验四 哈夫曼码编、译码器的实现一、 实验名称哈夫曼码编、译码器的实现二、 实验目的1、熟练哈夫曼树的定义，掌握构造哈夫曼树的方法。2、掌握哈夫曼编码和译码方法。3、掌握文本文件的读写方法。三、 实验内容1、 实验内容：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编码、译码系统。试为这样的信息收发站写一个哈夫曼码的编码、译码系统。一个完整的系统应以下功能: (1 从终端读入字符集大小n，以及n个字符和n个权值,

2、建立哈夫曼树,并将它存放在文件hfmTree中。 (2 利用已建立好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码,然后将结果代码存(传输到文件CodeFile中. (3 译码(Decoding。利用已建好的哈夫曼树,对传输到达的CodeFile中的数据代码进行译码,将译码结果存入文件TextFile。(4 将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 (5 打印印哈夫曼树(TreePrinting。将已在内存中的哈夫曼树以直观的方式(树或凹入表的形式显示在终端上，同时将此字

3、符形式的哈夫曼树写入文件TreePrint中。 (6数据结构设计根据下面给出的存储结构定义typedef struct / 定义哈夫曼树中每个结点结构体类型char ch; /结点字符信息int weight; / 定义一个整型权值变量int lchild; / 定义左、右孩子及双亲指针int rchild;int parent; HTNode;typedef HTNode HFMTMAXLEN; /用户自定义HFMT数组类型 typedef char* HfCode;/动态分配字符数组存储哈夫曼编码表 （7）基本操作的函数设计void InitHFMT(HFMT T；/初始化哈夫曼树 voi

4、d InputWeight(HFMT T,char* weightFile；/ 输入权值void SelectMin(HFMT T,int i,int *p1,int *p2；/选择所有结点中较小的结点void CreatHFMT(HFMT T；/ 构造哈夫曼树，T2*n-1为其根结点void PrintHFMT (HFMT T；/ 输出向量状态表void printHfCode(HfCode hc；/输出字符的哈夫曼编码序列HfCode hfEnCoding(HFMT T；/利用构成的哈夫曼树生成字符的编码void print_HuffmanTree(HFMT HT,int t,int i/

5、按树形形态输出哈夫曼树的形态void Encoder(char* original,char* codeFile,HfCode hc,HFMT HT；/利用已建好的哈夫曼树,对original文件中要传输的原始数据进行编码，/将编码结果存入文件codeFile中void Decoder(char* codeFile ,char* textFile,HFMT HT；/利用已建好的哈夫曼树,对传输到达的codeFile中的数据代码进行译码, /将译码结果存入文件textFile中 2、 实验要求（1）、用C语言编程实现上述实验内容中的结构定义和算法。（2）、要有main(函数，并且在main(函数

6、中使用检测数据调用上述算法。（3）、实验完成后撰写实验报告，实验报告的具体格式参见实验报告须知。（4）、实验完成后把打印好的实验报告以及电子版的实验报告和源程序一并上交。四、 参考源代码：#include #include #include #include #define MAXLEN 100typedef struct / 定义哈夫曼树中每个结点结构体类型char ch; /结点字符信息int weight; / 定义一个整型权值变量int lchild; / 定义左、右孩子及双亲指针int rchild;int parent; HTNode;typedef HTNode HFMTMAXL

7、EN; /用户自定义HFMT数组类型 typedef char* HfCode;/动态分配字符数组存储哈夫曼编码表int n;void InitHFMT(HFMT T/初始化哈夫曼树 int i;printf ("ntt请输入共有多少个权值 (小于100："scanf ("%d",&n;getchar(;for (i=0; i<2*n-1; i+Ti.weight=0; Ti.lchild=-1;Ti.rchild=-1; Ti.parent=-1; void InputWeight(HFMT T,char* weightFile/ 输入权

8、值int w;int i;int n;char ch;FILE *fp;if (fp = fopen(weightFile, "r" != NULL fscanf(fp,"%dn",&n;for (i=0;i ch=fgetc(fp;fscanf(fp,"%dn",&w;Ti.ch=ch;Ti.weight=w; fclose(fp;void SelectMin(HFMT T, int i, int *p1,int *p2/ 选择所有结点中两个结点较小的结点long min1=999999; / 预设两个值，并使它大于

9、可能出现的最大权值long min2=999999; int j;for (j=0;j<=i;j+ if (Tj.parent=-1if (min1>Tj.weightmin1=Tj.weight; / 找出最小的权值*p1=j; / 通过*p1带回序号for (j=0;j<=i;j+ if (Tj.parent=-1 if (min2>Tj.weight && j!=(*p1 min2=Tj.weight; / 找出次最小的权值*p2=j; / 通过*p2带回序号 void CreatHFMT(HFMT T / 构造哈夫曼树，T2*n-1为其根结点in

10、t i,p1,p2;InitHFMT (T;InputWeight (T,"weight.txt"for (i=n;i<2*n-1;i+ SelectMin (T,i-1,&p1,&p2;Tp1.parent=Tp2.parent=i;/Ti.lchild=Tp1.weight;/Ti.rchild=Tp2.weight;Ti.lchild=p1;Ti.rchild=p2;Ti.weight=Tp1.weight+Tp2.weight;void PrintHFMT (HFMT T / 输出向量状态表 int i,k=0;for (i=0; i<2

11、*n-1; i+while (Ti.lchild!= -1 if (!(k%2printf ("n"printf ("tt(%d%d,(%d%d",Ti.weight,Ti.lchild,Ti.weight,Ti.rchild;k+;break;void printHfCode(HfCode hc/输出字符的哈夫曼编码序列for (int i=0;i printf("%s",hci;HfCode hfEnCoding(HFMT T/利用构成的哈夫曼树生成字符的编码int start;HfCode hc=new char*(n+1*si

12、zeof(char*;/分配n个字符编码char* cd=new charn*sizeof(char;/分配求编码的工作空间cdn-1='0'/编码结束符int c;int f;for (int i=0;i start=n-1;for (c=i,f=Ti.parent;f!=-1;c=f,f=Tf.parent/从叶子结点到根逆向求编码if (Tf.lchild=ccd-start='0'elsecd-start='1'hci=new char(n-start*sizeof(char;/为第i个编码分配空间strcpy(hci,&cdst

13、art;printf("n%c:%s",Ti.ch,hci;return hc;void print_HuffmanTree(HFMT HT,int t,int i/按树形形态输出哈夫曼树的形态if (HTt.rchild!=-1 /先打印出右子树print_HuffmanTree(HT,HTt.rchild,i+1;for (int j=1;j<=3*i;j+/打印空格表示结点所在的层次printf(" "/再输出根结点if (HTt.lchild!=-1 | HTt.rchild!=-1printf("%dn",HTt.we

14、ight;elseprintf("%c(%dn",HTt.ch,HTt.weight;/最后输出左子树if (HTt.lchild!=-1 print_HuffmanTree(HT,HTt.lchild,i+1;void Encoder(char* original,char* codeFile,HfCode hc,HFMT HT/利用已建好的哈夫曼树,对original文件中要传输的原始数据进行编码, /将编码结果存入文件codeFile中. char *str; /用于存储需编码内容 int i=0; char ch; int k=0; FILE* fin;FILE*

15、fout; if (fin = fopen(original, "r" != NULL fscanf(fin,"%c",&ch;while(!feof(fin k+; /计算CodeFile中代码长度 fscanf(fin,"%c",&ch; fclose(fin; str=new chark+1; k=0;if (fin = fopen(original, "r" != NULL fscanf(fin,"%c",&ch;while(!feof(fin strk+=ch;

16、 fscanf(fin,"%c",&ch; fclose(fin; strk='0' /结束标志符printf("要编码的数据是:n"printf("%sn",str; k=0;if (fout = fopen(codeFile, "w" != NULL while (strk!='0' /将字符编码for (i=0;i if (strk=HTi.chfprintf(fout,"%s",hci;break;k+;printf("已编码！且存到文件

17、CodeFile.dat中!nn" fclose(fout;void Decoder(char* codeFile ,char* textFile,HFMT HT /利用已建好的哈夫曼树,对传输到达的codeFile中的数据代码进行译码, /将译码结果存入文件textFile中. int i=0,k=0; int j=n*2-1-1; /表示从根结点开始往下搜索 char* bitStr; FILE* fin;/读取codeFile文本文件指针FILE* fout;printf("经译码的内容为:n" char ch;if (fin = fopen(codeFil

18、e, "r" != NULL fscanf(fin,"%c",&ch;while(!feof(fin k+; /计算CodeFile中代码长度 fscanf(fin,"%c",&ch; fclose(fin; bitStr=new chark+1; k=0;if (fin = fopen(codeFile, "r" != NULL fscanf(fin,"%c",&ch;while(!feof(fin bitStrk+=ch; fscanf(fin,"%c",&ch; fclose(fin; bitStrk='0' /结束标志符 if(HT=NULL /还未建哈夫曼树 printf("请先编码!n" return; if (fout = fopen(textFile, "w" != NULL /将字符形式的编码文件写入文件CodePrin中 while(bitStri!='0' if(bitStri='0' j=HTj.lchild; /往左走 else j=HTj.r