哈夫曼编码译码系统课程设计实验报告(含源代码C-C语言)

东北电力大学计算机科学与技术业综合设计报告目录摘要………………………..……………IIAbstract…………………II第一章课题描述…………11.1问题描述………………...1.2需求分析…………………..……………1.3程序设计目标……………第二章设计简介及设计方案论述…………2.1设计简介.………………..………….2.2设计方案论述……………..……………22.3概要设计…………………..……………2第三章详细设计…………..………………..3.1哈夫曼树…………………..……………43.2哈夫曼算法………………..……………43.2.1基本思想……………..……….43.2.2存储结构……………..…………43.3哈夫曼编码………………..……………53.4文件I/O流………………..……………63.4.1文件流………………63.4.2文件的打开与关闭………….…….73.4.3文件的读写………….……....73..5C语言文件处理方式……………………第四章设计结果及分析…………………..………………..4.1设计系统功能…………………….4.2进行系统测试……………..……………8总结…….…………………..…………致谢…….…………………..………….参考文献…….……………..………….附录主要程序代码………..………….16-I-

东北电力大学计算机科学与技术业综合设计报告摘

要在这个信息高速发展的时代，每时每刻都在进行着大量信息的传递，到处都离不开信息，它贯穿在人们日常的生活生产之中，对人们的影响日趋扩大,而利用哈夫曼编进行通信则可以大大提高信道利用率，缩短信息传输时间，降低传输成本。在生产中则可以更大可能的降低成本从而获得更大的利润，这也是信息时代发展的趋势所在。本课程设计的目的是使学生学会分析待加工处理数据的特性，以便选择适当的逻辑结构、存储结构以及进行相应的算法设计。学生在学习数据结构和算法设计的同时，培养学生的抽象思维能力、逻辑推理能力和创造性的思维方法，增强分析问题和解决问题的能力。此次设计的哈夫曼编码译码系统，实现对给定报文的编码和译码，并且任意输入报文可以实现频数的统,建立哈夫曼树以及编码译码的功能。这是一个拥有完备功能的系统程序，对将所学到的知识运用到实践中,具有很好的学习和研究价值关键词：信息；通讯；编码；译码；程序-II-

东北电力大学计算机科学与技术业综合设计报告Abstractisadatethatinformationhighlydevelopmentinformationeveryleaveinformation,itthroughduringthelifeproduction,theinfluenceexpandsdaybydaythepeople,usingHuffmancarriesoncorrespondencebepossibletochannelfactortheintelligencereducescost.Maygreatlycostinproduction,obtainsabiggerprofit,isalsotheinformationagedevelopmentThiscurriculumissocietyanalyzetreatstheprocessingdatawiththeaimofthesuitablelogicalthememorystructurewellontheduringconstructionofdataandalgorithmdesign’sraisesstudent'sabstractthinkingability,logicreasoningabilityandthemethod,enhancementthequestiondesign'sHuffmancodescodesystem,realizestothetextthethedecoding,thearbitraryinputtextmayrealizethethetreeaswellthecodedecodingfunction.iscompletefunctionsystemprogram,toknowledgewilllearnutilizesinthegoodthevalue.Keywords：Information;Coding;Procedure-III-

东北电力大学计算机科学与技术业综合设计报告第一章

课题描述1.1问题描述利用哈夫曼编码进行通信，可以压缩通信的数据量，提高传输效率，缩短信息的传输时间，还有一定的保密性。现在要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进行编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。1.2需求分析在本例中设置发送者和接受者两个功能，1.2.1发送的能①输入待传送的字符信息；②统计字符信息中出现的字符种类数和各字符出现的次数（频率②根据字符的种类数和各自出现的次数建立哈夫曼树；③利用以上哈夫曼树求出各字符的哈夫曼编码；④将字符信息转换成对应的编码信息进行传送。1.2.2接受的能①接收发送者传送来的编码信息；②利用上述哈夫曼树对编码信息进行翻译，即将编码信息还原成发送前的字符信息。从以上分析可发现，在本例中的主要算法有三个：（1）哈夫曼树的建立；（2）哈夫曼编码的生成；（3）对编码信息的翻译。1.3程序设目层次一编程从文件中读取一段报文首先统计字符的频度然后建立哈夫曼树，并给出报文的编码然后根据使用者的需要对指定文件里的任意二进制编码进行译码并显示。层次二：使用者从系统界面输入字符串，统计从键盘输入的字符串信息，然后建立哈夫曼树，并给出报文的编码，然后根据使用者的需要对指定文件里的或者使用者从系统界面输入任意二进制编码的进行译码并显示。--

东北电力大学计算机科学与技术业综合设计报告第二章2.1设计简介

设计简介及设方案论述文字处理是现代计算机应用的重要领域。文本由字符组成，字符以某种编码形式存储在计算机中。每个字符的编码可以是相等长度的，也可以是不等长度的。编码是等长编码。为了提高存储和处理文本的效率，在一些计算机应用场合，如数据通信，常采用不等长的编码常用的字符用较少的码位常出现的字符用较多的码位编码，从而减少文本的存储长度。哈夫曼编码就是用于此目的的不等长编码方法。所以本次设计就是通过构造哈夫曼树来生成哈夫曼编码，最终完成设计要求。2.2设计方案论述哈夫曼编码/译码程序主要由主函数哈夫曼树类和各种功能函数组成序运行时首先进入主函数，对各种功能函数进行调用，从而实现了整个程序的运行。将各种不同的函数分别包含在各自的结构体中，使整个程序结构更加的清晰明了，各功能相互独立且紧密联系，有利于编程的实现，同时也体现了面向对象设计语言的封装性。在主菜单中运用了switch()函数和”语句，便于对整个程序操作和控制；对数据保存在文档中，则运用了文件流和语言的文件处理方式，进行文件与内存之间输入，输出数据。2.3概要设计2.3.1

第一部分功能的实现在主函数声明HuffmanTree1类的对HuffmanNode后用HuffmanNode调用它的成员函数TranslatedCode()此函数能读取里的字符串并统计然后建立哈夫曼树并对各个字符编码和保存相关信息。然后对象HuffmanNode再调用成员函数TranslateArtcle（）对指定文件得到的二进制编码进行译码，并保存翻译得到的信息。2

.3.1第二部分功能的实现获取并保存从键盘输入的字符串，并统计其信息。然后利用这些信息建立哈夫曼树对各个字符进行编码和保存相关信息。接着可以调用函数HuffmanTranslateCoding2（）对指定文件得到的二进制编码信息进行译码和保存得到的翻译信息，或者可以调用HuffmanTranslateCoding()对从系统页面输入的二进制编码进行翻译并保存翻译信息--

东北电力大学计算机科学与技术业综合设计报告第三章

详细设计3.1夫曼树哈夫曼树也称最优二叉树.给定一组具有确定权值的叶子结点,可以构造出不同的二叉树将其中带权路径长度最小的二叉树称为哈夫曼树.其中,叶子结点的权值(weight)是对叶子结点赋予的一个有意义的数值量设二叉树具有n个带权值的叶子结点,从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和叫做二叉树的带权路径长度(weightedpathlength),记为:Wklk,w第k叶子结点的权值l从根结点到第k个叶子结点的路径kk长度.3.2夫曼算法基本思想根据,哈夫曼的定,一棵二叉树要使其带权路径长度最,必须使权值越大的叶子结点越靠近根结,而权值越小的叶子结点越远离根结点.依据这个特点便提出了哈夫曼算法,其基本思想是:(1)初始化:由给定的n个权值w,w,…,w}构造n只有一个根结点的二叉12n树,从而得到一个二叉树集合F={T,T,…,T};12n(2)选取与合并:在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一颗新的二叉树,这棵新二叉树的根结点的权值为其左右子树根结点的权值之和;(3)删除与加入:在F中删除作为左子树的两棵二叉树,并将新建立的二叉树加入到F中;(4)重复(2)两步,当集合F中只剩下一棵二叉树时,这棵二叉树便是哈夫曼--

东北电力大学计算机科学与技术业综合设计报告树.存储结构在由哈夫曼算法构造的哈夫曼树中,非叶子结点的度均为据二叉树的性质可知,具有n叶子结点的哈夫曼树共有2n-1个结点,其中个非叶子结点它们是在n-1次的合并过程中生成的.了便于选取根结点权值最小的二叉树以及合并操作,设置一个数HuffmanNode[2n-1]保存哈夫曼树中各结点的信息数组元素的结点结构如图3-1所示.

weightparentlchildrchildinf3-1哈夫曼树其中,weight:权值域,保存该结点的权值;lchild:指针域,保存该结点的左孩子结点在数组中的下标rchild:指针域,保存该结点的右孩子结点在数组中的下标parent:指针域,保存该结点的双亲结点在数组中的下标Inf:存储相关的字符信息可以用C中的结构类型定义上述结点.structHuffmanNode{charinf;intweight;intparent;intlchild,rchild;};3.3夫曼编码

的结点结构哈夫曼树可用于构造最短的不等长编码方案体做法如:设需要编码的字符集合为{d,d,…,d},它们在字符串中出现的频率为w,w,…,w},以d,d,…,d作为叶12n12n12n子结点,w,w,…,w作为叶子结点的权值,构造一颗哈夫曼编码树,规定哈夫曼编码树12n的左分支代表0右分支代表1则从根结点到每个叶子结点所经过的路径组成的和1的序列便为该叶子结点对应字符的编码,称为哈夫曼编码HuffmanCode).--

东北电力大学计算机科学与技术业综合设计报告在哈夫曼编码树,数的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和所以采用哈夫曼树构造的编码是一种能使字符串的编码总长度最短的不等长编码.由于哈夫曼编码树的每个字符结点都是叶子结点,们不可能在根结点到其他字符结点的路径,所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀,从而保证了解码的唯一性.3.4文件I/O流文件的打开与关闭本程序中，建立流对象调用成员函数openclose进行文件的打开和关闭。成员函数回非零值或者true，表示流对象已经成功关联到磁盘文件，否则返回0或者false表示该流对象没有关联到文件。成员函数close首先刷新缓冲区，把所有等待输出的内容写到磁盘文件中，然后关闭磁盘文件，并断开磁盘文件与文件缓冲区的联系。文件的读写由于ifstream、ofstream、fstream分别派生自、iostream，因此定义于类istream、ostream、iostream中的大部分共有成员函数。流插入运算符函数operator<<和流提取运算符函数put/get/getline函数主要用于格式化I/O。write/read函数则常用于无格式化I/O。3.5言文件处理式体结构体FILE类型可以用来定义文件型指针变量，可以使指针指向某一个文件的结构体变量，从而通过该结构体变量中的文件信息能够访问该文件。例如：FILE*fp;文（（fcloseFILE*fp;fp=fopen(文件名，使用文件方式)；fclose（文件指针例如：--

东北电力大学计算机科学与技术业综合设计报告FILE*fp;fp=fopen(“al”,”w”);fclose(fp);fputc把一个字符写到磁盘文件上去，其一般调用形式为putc(ch,fp);其中ch是要输出的字符。fp是文件指针变量。fget函数从指定的文件读入一个字符，该文件必须是以读或读写方式打开的。fgetc数的调用形式ch=fgetc(fp);其中ch是要输出的字符。fp是文件指针变量。3.6程序功能的详细计详第四章4.1计系统功能

设计结果及分层次一编程从文件中读取一段报文首先统计字符的频度然后建立哈夫曼树，并给出报文的编码然后根使用者的需要对指定文件里的任意二进制编码进行译码并显示。层次二：使用者从系统界面输入字符串，统计从键盘输入的字符串信息，然后建立哈夫曼树，并给出报文的编码，然后根据使用者的需要对指定文件里的或者使用者从系统界面输入任意二进制编码的进行译码并显示。--

东北电力大学计算机科学与技术业综合设计报告4.2行系统测试图系统界面--

东北电力大学计算机科学与技术业综合设计报告图从文件中提取字符串并进行字符的统--

东北电力大学计算机科学与技术业综合设计报告图4-3A操作的字符串的哈夫曼编码--

东北电力大学计算机科学与技术业综合设计报告图B作对Acode.txt里的二进制编码进行译码和保存翻信息--

东北电力大学计算机科学与技术业综合设计报告图C作从键盘输入字符串并统计、编码和保存--

东北电力大学计算机科学与技术业综合设计报告图作对里的二进制编码进行译再保存保存图4-6E作对在系统页面输入的二进制编码进行译码--

东北电力大学计算机科学与技术业综合设计报告图作退出系统--

东北电力大学计算机科学与技术业综合设计报告图以上操作得到的相关数据图退出系统总结通过本次课程设计使我对哈夫曼树及哈夫曼编码有了更深刻的理解同时对CC++的编程以及算法的实现产生了比较大的兴趣。还学到了许多在处理程序时的技巧和方法，这都对以后的学习大有裨益，以及感受到在编程设计中团队合作精神的重要性。在这次程序设计中，我觉得重要的一点，那就是不要人云亦云，要有自己的主见，不管别人如何，一定要有自己的思想，并且始终不改变的去坚持，纵然，可能会遇到很多难以解决的困难，都要自始到终，相信自己能把这个程序做得出来。当自己最终在自己的努力下完成任务的时候，那就会有更多属于自己的收获，包括成功的喜悦以及程序中体现的思想。--

东北电力大学计算机科学与技术业综合设计报告其次是我认为调试功能是整个编写程序过程中很重要的一个环节通过此次实验我对调试有了更加深刻的理解，懂得怎么样去调试程序，如何发现错误，如何更高效的改正，最终能把程序实现。致

谢在本次课程设计的整个过程中别感谢自始至终给我提供帮助和指导X老师，是他耐心的指导才使得本次设计得以顺得完成，同时，也要感谢小组成员的不懈努力和互相配合，在此还要特别感谢为我们提供良好上机环境的学校.如果没有以上老师，同学和学校的帮助和支持，本次设计实难完.再次感谢老师的精心辅导和同学的相互帮助，使我们顺利完成此次设计以及为学习以后的科目打下良好的基础--

东北电力大学计算机科学与技术业综合设计报告参考文献【1语程序设（第三版）谭强清大学出版社2009.10【2】C++语言程序设计（第四版郑莉董渊何江舟清华大学出版社【3】数据结（C版朝阳郭晓利王晓慧孙鸿飞中国电力出版社2007.8--

东北电力大学计算机科学与技术业综合设计报告附录主要程序代码:--

东北电力大学计算机科学与技术业综合设计报告--

东北电力大学计算机科学与技术业综合设计报告