哈夫曼编码译码系统实验报告

《哈夫曼编码译码系统实验报告》由会员分享，可在线阅读，更多相关《哈夫曼编码译码系统实验报告（36页珍藏版）》请在装配图网上搜索。

1、目 录摘 要 . IIAbstract . II第一章 课题描述. 11.1 问题描述.11.2 需求分析. 11.3 程序设计目标第二章设计简介及设计方案论述 22.1 设计简介.2 2.2 设计方案论述.2 2.3 概要设计.2 第三章详细设计. 43.1 哈夫曼树.4 3.2 哈夫曼算法.4 3.2.1 基本思想.43.2.2 存储结构.43.3 哈夫曼编码.53.4 文件I/O流.63.4.1 文件流.63.4.2 文件的打开与关闭.73.4.3 文件的读写.73.5 C语言文件处理方式第四章设计结果及分析. 84.1 设计系统功能.8 4.2 进行系统测试.8 总 结 .13致 .1

2、4参考文献 .15附录 主要程序代码 .16摘 要在这个信息高速发展的时代,每时每刻都在进行着大量信息的传递,到处都离不开信息,它贯穿在人们日常的生活生产之中,对人们的影响日趋扩大,而利用哈夫曼编码进行通信则可以大大提高信道利用率,缩短信息传输时间,降低传输成本。在生产中则可以更大可能的降低成本从而获得更大的利润,这也是信息时代发展的趋势所在。本课程设计的目的是使学生学会分析待加工处理数据的特性,以便选择适当的逻辑结构、存储结构以及进行相应的算法设计。学生在学习数据结构和算法设计的同时,培养学生的抽象思维能力、逻辑推理能力和创造性的思维方法,增强分析问题和解决问题的能力。此次设计的哈夫曼编码译

3、码系统,实现对给定报文的编码和译码,并且任意输入报文可以实现频数的统计,建立哈夫曼树以及编码译码的功能。这是一个拥有完备功能的系统程序,对将所学到的知识运用到实践中,具有很好的学习和研究价值.关键词：信息；通讯；编码；译码；程序AbstractThis is a date that information speeding highly development and transmitinformation every time, everywhere cannot leave the information, it passes through during the people daily

4、 life production, the influence expands day by day to the people, but codes using Huffman carries on the correspondence to be possible to raise the channel use factor greatly, reduces the intelligence transmission time, reduces the transmission cost. May greatly possible reduce the cost in the produ

5、ction, thus obtains a bigger profit, this is also the information age development tendency is. This curriculum projects goal is makes the student academic society to analyze treats the processing data the characteristic, with the aim of choosing the suitable logical organization, the memory structur

6、e as well as carries on the corresponding algorithm design. The student during the study construction of data and algorithm designs raises students abstract thinking ability, logic reasoning ability and the creative thought method, the enhancement analysis question and solves the question ability. T

7、his designs Huffman codes the code recognition system, realizes to assigns the text the code and the decoding, and the arbitrary input text may realize the frequency statistics, establishes the Huffman tree as well as the code decoding function. This is one has the complete function system program,

8、to the knowledge which will learn utilizes in the practice, has the very good study and the research value.Keywords：Information; Communication; Coding; Decoding; Procedure 32 / 36第一章 课题描述1.1问题描述利用哈夫曼编码进行通信,可以压缩通信的数据量,提高传输效率,缩短信息的传输时间,还有一定的性。现在要求编写一程序模拟传输过程,实现在发送前将要发送的字符信息进行编码,然后进行发送,接收后将传来的数据进行译码,即将

9、信息还原成发送前的字符信息。1.2需求分析在本例中设置发送者和接受者两个功能,1.2.1发送者的功能：输入待传送的字符信息；统计字符信息中出现的字符种类数和各字符出现的次数频率；根据字符的种类数和各自出现的次数建立哈夫曼树；利用以上哈夫曼树求出各字符的哈夫曼编码；将字符信息转换成对应的编码信息进行传送。1.2.2接受者的功能：接收发送者传送来的编码信息；利用上述哈夫曼树对编码信息进行翻译,即将编码信息还原成发送前的字符信息。从以上分析可发现,在本例中的主要算法有三个：1哈夫曼树的建立；2哈夫曼编码的生成；3对编码信息的翻译。1.3程序设计目标层次一：编程从文件中读取一段报文,首先统计字符的频度

10、,然后建立哈夫曼树,并给出报文的编码,然后根据使用者的需要对指定文件里的任意二进制编码进行译码并显示。层次二：使用者从系统界面输入字符串,统计从键盘输入的字符串信息,然后建立哈夫曼树,并给出报文的编码,然后根据使用者的需要对指定文件里的或者使用者从系统界面输入任意二进制编码的进行译码并显示。第二章 设计简介及设计方案论述2.1设计简介文字处理是现代计算机应用的重要领域。文本由字符组成,字符以某种编码形式存储在计算机中。每个字符的编码可以是相等长度的,也可以是不等长度的。ASCII编码是等长编码。为了提高存储和处理文本的效率,在一些计算机应用场合,如数据通信,常采用不等长的编码,对常用的字符用较

11、少的码位,不常出现的字符用较多的码位编码,从而减少文本的存储长度。哈夫曼编码就是用于此目的的不等长编码方法。所以本次设计就是通过构造哈夫曼树来生成哈夫曼编码,最终完成设计要求。2.2设计方案论述哈夫曼编码/译码程序主要由主函数、哈夫曼树类和各种功能函数组成,程序运行时首先进入主函数,对各种功能函数进行调用,从而实现了整个程序的运行。将各种不同的函数分别包含在各自的结构体中,使整个程序结构更加的清晰明了,各功能相互独立且紧密联系,有利于编程的实现,同时也体现了面向对象设计语言的封装性。在主菜单中运用了switch函数和case语句,便于对整个程序操作和控制；对数据保存在文档中,则运用了文件I/O

12、流和C语言的文件处理方式,进行文件与存之间输入,输出数据。2.3概要设计2.3.1第一部分功能的实现在主函数声明HuffmanTree1类的对象HuffmanNode,然后用HuffmanNode调用它的成员函数TranslatedCode,此函数能读取Adata.txt里的字符串并统计,然后建立哈夫曼树并对各个字符编码和保存相关信息。然后对象HuffmanNode再调用成员函数TranslateArtcle对指定文件得到的二进制编码进行译码,并保存翻译得到的信息。2.3.1第二部分功能的实现 获取并保存从键盘输入的字符串,并统计其信息。然后利用这些信息建立哈夫曼树对各个字符进行编码和保存相关

13、信息。接着可以调用函数HuffmanTranslateCoding2对指定文件得到的二进制编码信息进行译码和保存得到的翻译信息,或者可以调用HuffmanTranslateCoding对从系统页面输入的二进制编码进行翻译并保存翻译信息第三章 详细设计3.1 哈夫曼树哈夫曼树也称最优二叉树.给定一组具有确定权值的叶子结点,可以构造出不同的二叉树,将其中带权路径长度最小的二叉树称为哈夫曼树.其中,叶子结点的权值是对叶子结点赋予的一个有意义的数值量.设二叉树具有n个带权值的叶子结点,从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和叫做二叉树的带权路径长度,记为:WPL=,wk为第k个叶子

14、结点的权值,lk为从根结点到第k个叶子结点的路径长度.3.2 哈夫曼算法3.2.1 基本思想根据,哈夫曼的定义,一棵二叉树要使其带权路径长度最小,必须使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点.依据这个特点便提出了哈夫曼算法,其基本思想是:(1) 初始化:由给定的n个权值w1, w2, wn构造n棵只有一个根结点的二叉树,从而得到一个二叉树集合F= T1,T2,Tn;(2) 选取与合并:在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一颗新的二叉树,这棵新二叉树的根结点的权值为其左、右子树根结点的权值之和;(3) 删除与加入:在F中删除作为左、右子树的两棵二

15、叉树,并将新建立的二叉树加入到F中;(4) 重复、两步,当集合F中只剩下一棵二叉树时,这棵二叉树便是哈夫曼树.3.2.2 存储结构在由哈夫曼算法构造的哈夫曼树中,非叶子结点的度均为2,根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有2n-1个结点,其中有n-1个非叶子结点,它们是在n-1次的合并过程中生成的.为了便于选取根结点权值最小的二叉树以及合并操作,设置一个数组HuffmanNode2n-1保存哈夫曼树中各结点的信息,数组元素的结点结构如图3-1所示.weightparentlchildrchildinf图3-1 哈夫曼树的结点结构其中,weight:权值域,保存该结点的权值;lch

16、ild:指针域,保存该结点的左孩子结点在数组中的下标;rchild:指针域,保存该结点的右孩子结点在数组中的下标;parent:指针域,保存该结点的双亲结点在数组中的下标.Inf:存储相关的字符信息可以用C中的结构类型定义上述结点.struct HuffmanNode char inf;int weight; int parent; int lchild,rchild; ;3.3 哈夫曼编码哈夫曼树可用于构造最短的不等长编码方案,具体做法如下:设需要编码的字符集合为d1,d2,dn,它们在字符串中出现的频率为w1, w2, wn,以d1,d2,dn作为叶子结点, w1, w2, wn作为叶子结

17、点的权值,构造一颗哈夫曼编码树,规定哈夫曼编码树的左分支代表0,右分支代表1,则从根结点到每个叶子结点所经过的路径组成的0和1的序列便为该叶子结点对应字符的编码,称为哈夫曼编码.在哈夫曼编码树中,数的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和,所以采用哈夫曼树构造的编码是一种能使字符串的编码总长度最短的不等长编码.由于哈夫曼编码树的每个字符结点都是叶子结点,它们不可能在根结点到其他字符结点的路径上,所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀,从而保证了解码的唯一性.3.4 C+文件I/O流3.4.1 文件的打开与关闭本程序中,建立流对象调用成员函数open和cl

18、ose进行文件的打开和关闭。成员函数open返回非零值或者true,表示流对象已经成功关联到磁盘文件,否则返回0或者false表示该流对象没有关联到文件。成员函数close首先刷新缓冲区,把所有等待输出的容写到磁盘文件中,然后关闭磁盘文件,并断开磁盘文件与文件缓冲区的联系。3.4.2 文件的读写由于ifstream、ofstream、fstream分别派生自istream、ostream、iostream,因此定义于类istream、ostream、iostream中的大部分共有成员函数。流插入运算符函数operator、put/get/getline函数主要用于格式化I/O。write/ r

19、ead函数则常用于无格式化I/O。3.5 C语言文件处理方式3.5.1 结构体FILE结构体FILE类型可以用来定义文件型指针变量,可以使指针指向某一个文件的结构体变量,从而通过该结构体变量中的文件信息能够访问该文件。例如： FILE *fp;3.5.2 文件的打开fopen函数和文件的打开fclose函数FILE *fp;fp= fopen；fclose文件指针；例如：FILE *fp;fp=fopen;fclose;3.5.3 文件的读写fputc函数把一个字符写到磁盘文件上去,其一般调用形式为putc; 其中ch是要输出的字符。fp是文件指针变量。 fget函数 从指定的文件读入一个字符

20、,该文件必须是以读或读写方式打开的。fgetc函数的调用形式 ch=fgetc;其中ch是要输出的字符。fp是文件指针变量。3.6程序功能的详细设计请看附录的源程序的 详细清单第四章 设计结果及分析4.1 设计系统功能层次一：编程从文件中读取一段报文,首先统计字符的频度,然后建立哈夫曼树,并给出报文的编码,然后根据使用者的需要对指定文件里的任意二进制编码进行译码并显示。层次二：使用者从系统界面输入字符串,统计从键盘输入的字符串信息,然后建立哈夫曼树,并给出报文的编码,然后根据使用者的需要对指定文件里的或者使用者从系统界面输入任意二进制编码的进行译码并显示。4.2 进行系统测试图4-1 系统界面

21、图4-2从文件中提取字符串并进行字符的统计图4-3A操作的字符串的哈夫曼编码图4-3 B操作对Acode.txt里的二进制编码进行译码和保存翻译信息图4-4 C操作从键盘输入字符串并统计、编码和保存图4-5D操作对Ccode.txt里的二进制编码进行译码再保存保存图4-6E操作对在系统页面输入的二进制编码进行译码 图4-7F操作退出系统图4-8 以上操作得到的相关数据图4-8 退出系统总 结通过本次课程设计使我对哈夫曼树及哈夫曼编码有了更深刻的理解,同时对C,C+的编程以及算法的实现产生了比较大的兴趣。还学到了许多在处理程序时的技巧和方法,这都对以后的学习大有裨益,以及感受到在编程设计中团队合

22、作精神的重要性。在这次程序设计中,我觉得重要的一点,那就是不要人云亦云,要有自己的主见,不管别人如何,一定要有自己的思想,并且始终不改变的去坚持,纵然,可能会遇到很多难以解决的困难,都要自始到终,相信自己能把这个程序做得出来。当自己最终在自己的努力下完成任务的时候,那就会有更多属于自己的收获,包括成功的喜悦以及程序中体现的思想。其次是我认为调试功能是整个编写程序过程中很重要的一个环节。通过此次实验我对调试有了更加深刻的理解,懂得怎么样去调试程序,如何发现错误,如何更高效的改正,最终能把程序实现。致 在本次课程设计的整个过程中,要特别感自始至终给我提供帮助和指导的X老师,是他耐心的指导才使得本次

23、设计得以顺得完成,同时,也要感小组成员的不懈努力和互相配合,在此还要特别感为我们提供良好上机环境的学校.如果没有以上老师,同学和学校的帮助和支持,本次设计实难完成.再次感老师的精心辅导和同学的相互帮助,使我们顺利完成此次设计以及为学习以后的科目打下良好的基础.参考文献 1 C语言程序设计第三版 谭浩强 清华大学 2009.102 C+语言程序设计第四版。 莉 董渊 何江舟 清华大学2010.73 数据结构C版。曲 郭晓利 王晓慧 鸿飞 中国电力 2007.8附录 主要程序代码:/HuffmanCode1.h#ifndef HUFFMAMCODE_H #define HUFFMAMCODE_H#

24、include#includeusing namespace std;struct HuffmanNode /定义哈夫曼树各结点int weight; int parent; int lchild,rchild; int flag;class HuffmanCode1 /哈夫曼编码类public:char Info100;int Start;char Leaf;class HuffmanTree1 /建立哈夫曼树类private:HuffmanNode *Node; public: int f; HuffmanCode1 *hf;HuffmanTree1; HuffmanTree1; void

25、 TranslatedCode;void CodeHuf;void CreateHfmTree;void TransCode ;void TranslateArtcle ;#endif /HUFFMAMCODE_HHuffmanCode.cpp#include iostream#include#include math.h#include stdlib.h#includeHuffmanCode1.h#includeusing namespace std;#define MAXDATA 10000 /最长字符串#define MAXSIZE 150 /最多子叶数/第一部分功能W实现的代码$Huf

26、fmanTree1:HuffmanTree1Node=NULL; /将树结点初始化为空HuffmanTree1:HuffmanTree1delete Node; /释放结点空间void HuffmanTree1:CreateHfmTree/建立哈夫曼树int i,j,m1,m2,x1,x2;HuffmanNode *HfmNode=new HuffmanNode2*n-1;HuffmanCode1 *HfmCode=new HuffmanCode1n;fori=0;iHfmNodei.weight=0;HfmNodei.parent=0;HfmNodei.flag=0;HfmNodei.lch

27、ild=-1;HfmNodei.rchild=-1;fori=0;iHfmNodei.weight=mi;HfmCodei.Leaf=Stri;fori=0;im1=m2=32767;x1=x2=0;forj=0;jifHfmNodej.weightm2=m1;x2=x1;m1=HfmNodej.weight;x1=j;else ifHfmNodej.weightm2=HfmNodej.weight;x2=j;HfmNodex1.parent=n+i;HfmNodex2.parent=n+i;HfmNodex1.flag=1;HfmNodex2.flag=1;HfmNoden+i.weight

28、=HfmNodex1.weight+HfmNodex2.weight;HfmNoden+i.lchild=x1;HfmNoden+i.rchild=x2;CodeHuf;TransCode;/TranslateArtcle; hf=HfmCode; f=n;void HuffmanTree1:CodeHuf /对哈夫曼树进行编码HuffmanCode1 Hfd;int c,p;forint i=0;iHfd.Start=n-1;c=i;p=ac.parent;whileifHfd.InfoHfd.Start=0;elseHfd.InfoHfd.Start=1;Hfd.Start-;c=p;p=

29、ac.parent;printf;forint j=Hfd.Start+1;jbi.Infoj=Hfd.Infoj;printf;printf;bi.Start=Hfd.Start;void HuffmanTree1:TransCode /对文章进行翻译并保存ifstream ifs;ofstream ofs;char s1000;int t=0;char ch; cout*endl;printf;whileifs.getifst=ch;forint i=0;iifforint j=bi.Start+1;jprintf;ofsbi.Infoj;t+;printf;printf;cout*end

30、l;void HuffmanTree1:TranslateArtcle /将所译的码翻译成文章并保存int t=0;ifstream ifs;ofstream ofs;string s;getline;for;int l=0;int j=0;printf;whilelwhilejint hu=bj.Start+1;int k=0;whilehuifl+;hu+;k+;elsebreak;ifprintf;ofsbj.Leaf;j=0;break;else l=l-k;j+;continue;printf;printf;cout*endl;void HuffmanTree1:Translated

31、Codeifstream ifs;char str1000; char Str100;int i=0,j,m100,h,k=0;int n=0;cout*endl;printf;char ch;whileifs.getprintf;ifstrn+=ch;printf;printf;fori=0;ij=0;h=0;whilej+;ifStrk=stri;printf;elsecontinue;forj=i;jifh+;printf;mk=h;k+;cout*endl; printf;cout*endl;printf;CreateHfmTree;cin.get;/printf;/main.cpp/

32、#includeHuffmanCode1.h/ /第二部分功能实现的代码$typedef struct /哈弗曼树节点的结构体 char info; /关联字符信息 unsigned int weight; /每个节点的权职 unsigned int parent, lchild, rchild;HTNode,*HuffmanTree;typedef char *HuffmanCode; /存储哈弗曼编码void Select /选择双亲节点为0,并且最小的两个子叶节点 int i=1,m; while i+; /找第一个双亲节点为0的子叶结点 fors2=s1=i;i /保证s1中的权值最小

33、,s2次小 ifHTi.parent=0 & HTi.weight s2=s1; s1=i; else if=HTs1.weight & HTi.weight s2=i; while m=i; m+; while m+; s2=m; void HuffmanCoding /哈弗曼编码 int i,m; HuffmanTree p; ifn return; m = 2*n-1; HT = malloc*sizeof; forp=HT+1,i=1;i /初始化所有已存在的子叶信息 p-info = *info; p-weight = *w; p-parent = 0; p-lchild = 0;

34、p-rchild = 0; /for for; i /构造所需要的过度根节点 p-weight = 0; p-parent = 0; p-lchild = 0; p-rchild = 0; /for fori=n+1;i /建立哈弗曼树 int s1,s2; Select; HTs1.parent =i; HTs2.parent =i; HTi.lchild = s2; HTi.rchild = s1; HTi.weight = HTs1.weight+HTs2.weight; /for /哈弗曼编码 HC = malloc*sizeof; char* cd = mallocn*sizeof;

35、 cdn-1 = 0; fori=1;i int f; unsigned int c; int start=n-1; for if cd-start = 0; else cd-start = 1; HCi=malloc*sizeof; strcpy; /for free;/HuffmanCoding/Y功能实现 输出并保存字符串的二进制编码void CheckCoding ofstream ofs; /查询哈弗曼编码信息 int p;forint i=0; i for; coutHCj; /输出并保存字符串的二进制编码ofsHCj; coutendl;cout字符串的二进制编码已经保存在BCo

36、de.txt中endl;/cout译码翻译得到的文章已保存在Data.txt中endl;cout*endl; cout各字符对应的编码为:endl; /输出各字符对应的哈夫曼编码for p=1;pcoutHTp.info : HCpendl;/CheckCoding/对键盘输入的二进制代码进行译码void HuffmanTranslateCoding ofstream ofs; /译码过程 int m=2*n-1; int i,j=0;cout译码翻译得到的文章已保存在TransBData.txt中endl;cout译码翻译得到的文章为:; while i=m; while if i=HTi.

37、lchild; else if i=HTi.rchild; j+; coutHTi.info; /翻译成字符串并输出和保存 ofsHTi.info; /译码过程、对BCode.txt的编码进行译码void HuffmanTranslateCoding2 ifstream ifs; ofstream ofs; string c; int m=2*n-1; int i,j=0;getline;cout译码翻译得到的文章已保存在TransBData2.txt中endl;cout译码翻译得到的文章为:; while i=m; while if i=HTi.lchild; else if i=HTi.r

38、child; j+; coutHTi.info; /翻译成字符串并输出和保存 ofsHTi.info; void Menushow cout |*|endl; cout | HuffmanCode and HUffmanTranslate System |endl; cout | *哈夫曼编码/译码系统* |endl; cout | *欢迎使用本系统* |endl; cout | 东北电力大学 信息工程学院 计机093班 兴趣小组 |endl; cout | 制作人：辉强组长 哲 周兴宇 |endl; cout |*|endl; cout |在本系统中您可以进行如下操作： |endl; cout |第一部分功能： |endl; cout | A :从文件提取字符串,然后对提取的字符串进行编码 |endl; cout | B :根据W操作对WCode.txt里的二进制编码进行译码 |endl; cout