哈弗曼编译码器 (罗忠霖).doc

2010级计算机科学与技术专业 集美大学计算机工程学院 20112012学年第一学期数据结构实验报告题目： 实验五 哈夫曼编/译码器学号：2010810072成绩班级： 计算1013日期：2011.11.15姓名：罗忠霖指导老师：杨艳华一、实验目的：本次的实验目的在于使读者深入了解树的特性，以便在实际问题背景下灵活运用他们；同时还将巩固掌握对树结构的构造方法的理解，并且回顾文件操作的使用。二、实验环境： 本次试验在VC+环境下调试。三、实验内容与完成情况：1问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输的时间，降低传输成本。但是这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码。对于双工信道，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。2基本要求一个完整的系统应具有以下功能：（1） 初始化，构造哈弗曼树。（2） 编码。（3） 译码。（4） 印代码文件。（5） 印哈弗曼树。3. 程序代码#include#include#include#includetypedef structchar chr1;int weight;int parent,lchild,rchild;HTNode,*HuffmanTree;typedef structchar chr;int w1;char *code;/编码Ch;/字符和对应的权值及编码void Select(HuffmanTree &HT1,int j,int &s1,int &s2);void HuffmanCoding(HuffmanTree &HT, Ch *w, int n);/构造哈夫曼树HTvoid encoding(HuffmanTree &HT, Ch *ch, int n);/求每个字符的哈夫曼编码void Encoding(Ch *ch1, int n);/编码void Decoding(HuffmanTree &HT,int sum);/译码void caidan();void Printf();void main() FILE *p;int choice,n1,w2=1;int i,flag=1,m;char ch;HuffmanTree HTr;Ch *c; caidan();while(flag)loop: printf(n*请选择(0-5)：);scanf(%d,&choice);switch(choice)case 1:printf(请输入字符集大小n=); scanf(%d,&n1); c=(Ch *)malloc(n1+1)*sizeof(Ch); flushall(); for(i=1;i=n1;i+) printf(请输入字符及其权值：);scanf(%c%d,&ch,&w2);ci.chr=ch;ci.w1=w2;flushall(); HuffmanCoding(HTr,c,n1); encoding(HTr,c,n1); break;case 2:Encoding(c,n1); break;case 3:Decoding(HTr,n1); break;case 4:Printf(); break;case 5: m=2*n1-1;if(p=fopen(TreePrint.txt,w)=NULL)printf(File could not be openedn);elsefprintf(p,n哈夫曼树的构造如下所示：n);fprintf(p, 结点 weight parent lchild rchild);for (i=1; i=m; i+) fprintf(p,n%4d%8d%8d%8d%8d,i,HTri.weight,HTri.parent,HTri.lchild, HTri.rchild);fclose(p);printf(n哈夫曼树的构造如下所示：n);printf( 结点 weight parent lchild rchild);for(i=1; i=0;i-) if(HT1i.parent!=0) /在双亲不为0的条件下continue;if(d=0) /用s1记录第一个双亲为0的元素所在的位置 s1=i; d+;else if(d=1) /用s2记录第而个双亲为0的元素所在的位置 s2=i;d+;else if(d=2)if(HT1s1.weight=HT1s2.weight ) /s2用于存储最小值的位置 h=s1;s1=s2;s2=h; if(HT1i.weight0),构造哈夫曼树HT FILE *p; int i, j, m, s1, s2; if (n=1) return; m = 2 * n - 1;/树的结点总数 HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); / 0号单元未用 for (i=1; i=n; i+) /初始化 HTi.chr1=wi.chr;HTi.weight=wi.w1;/ HTi.parent=0; HTi.lchild=0; HTi.rchild=0; for (i=n+1; i=m; i+) /初始化 HTi.weight=0; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; for (i=n+1; i=m; i+)/ 建哈夫曼树 / 在HT1.i-1中选择parent为0且weight最小的两个结点，其序号分别为s1和s2。 Select(HT,i-1,s1,s2); HTs1.parent = i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; if(p=fopen(hfmTree.txt,w)=NULL) printf(File could not be openedn); else fprintf(p,n哈夫曼树的构造如下所示：n); fprintf(p, 结点 weight parent lchild rchild); for (i=1; i=m; i+) fprintf(p,n%4d%8d%8d%8d%8d,i,HTi.weight, HTi.parent,HTi.lchild, HTi.rchild); fclose(p);void encoding(HuffmanTree &HT, Ch *ch, int n) /- 从叶子到根逆向求每个字符的哈夫曼编码 -int i,c,f,start;/char *cd; cd = (char *)malloc(n*sizeof(char); / 分配求编码的工作空cdn-1 = 0; / 编码结束符。for (i=1; i=n; +i)/ 逐个字符求哈夫曼编码 start = n-1; / 编码结束符位置 for (c=i, f=HTi.parent; f!=0; c=f, f=HTf.parent) / 从叶子到根逆向求编码 if (HTf.lchild=c) cd-start = 0; else cd-start = 1; chi.code = (char *)malloc(n-start)*sizeof(char); / 为第i个字符编码分配空间 strcpy(chi.code, &cdstart); / 从cd复制编码(串)到code free(cd); / 释放工作空间 void Encoding(Ch *ch1, int n) /利用已经建立的哈弗曼树编码对输入的字符进行哈弗曼编码 FILE *q1,*q2; /char a100; /用于存放输入的字符 char num1000,c; char *p=num; /用于存放字符对应的哈弗曼编码 int i,j; if(q1=fopen(ToBeTran.txt,r)=NULL)printf(File could not be openedn); else rewind(q1); while(!feof(q1) /依次判断字符的对应的哈弗曼编码 c=fgetc(q1); for(j=1;j=n;j+) if(c=ch1j.chr)printf(%c:%s ,ch1j.chr,ch1j.code);strcpy(p,ch1j.code);p=p+strlen(ch1j.code);break;/如果找到就把对应的哈弗曼编码复制到字符数组num中 *p=0; printf(n得到的编码是：n); for(i=0;numi!=0;i+) /输出字符对应的哈弗曼编码 if(i=50) printf(n); /当输出50个字符时，进行换行 printf(%c,numi); printf(n); fclose(q1); if(q2=fopen(CodeFile.txt,w)=NULL)printf(File could not be openedn); else i=0;while(numi!=0) if(i=50) fprintf(q2,n); fprintf(q2,%c,numi+);fprintf(q2,n); fclose(q2);void Decoding(HuffmanTree &HT,int sum) /译码 FILE *p; /char code11000; /用于存放输入的密码 char a1100,c; /用于存放翻译好的字符 int n=0,i=0,b=2*sum-1; if(p=fopen(CodeFile.txt,r+)=NULL)printf(File could not be openedn);else while(!feof(p) c=fgetc(p); if(c=0) b=HTb.lchild; /当遇到0时指向哈弗曼树的左子树 if(c=1) b=HTb.rchild; /当遇到1时指向哈弗曼树的右子树 if(HTb.lchild=0&HTb.rchild=0) /当左右子树均为空时表明已找到对应的字符 a1n+=HTb.chr1;b=2*sum-1; /将对应的字符放在数组a1中，并重新设置b的值继续翻译 a1n=0; i=0; while(a1i!=0) /输出翻译好的字符 if(i=50) printf(n); printf(%c,a1i+); printf(n);fclose(p);if(p=fopen(TextFile.txt,w)=NULL)printf(File could not be openedn);elsei=0;fprintf(p,得到的翻译结果是：n);while(a1i!=0) if(i=50) fprintf(p,n); fprintf(p,%c,a1i+);fprintf(p,n);fclose(p);void Printf() FILE*p;if(p=fopen(CodeFile.txt,r