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

东北电力大学计算机科学与技术专业综合设计报告-I-目录摘要………………………………………………………………………..………………IIAbstract…………………………………………………………………………..………...II第一章课题描述………………………..…………………………………………………..11.1问题描述………………………………………………………………………………...11.2需求分析…………………………………………………..……………………………11.3程序设计目标……………………………………………………………………………第二章设计简介及设计方案论述…………………………………………………………22.1设计简介.………………………………………………..………………………..….…22.2设计方案论述……………………………………………..…………………….………22.3概要设计…………………………………………………..………………………….…2第三章详细设计…………………………………………………………..……….….……..43.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语言文件处理方式……………………………………………………………………第四章设计结果及分析…………………………………………………..……………..…..84.1设计系统功能………………………………….……………………………….....….…84.2进行系统测试……………………………………………..………………………….…8总结…….……………………………………………………..…………………………...13致谢…….……………………………………………………..……………………..…….14参考文献…….………………..………………………………..……………………..…….15附录主要程序代码………...………………………………..………………………..….16东北电力大学计算机科学与技术专业综合设计报告-II-摘要在这个信息高速发展的时代，每时每刻都在进行着大量信息的传递，到处都离不开信息，它贯穿在人们日常的生活生产之中，对人们的影响日趋扩大,而利用哈夫曼编码进行通信则可以大大提高信道利用率，缩短信息传输时间，降低传输成本。在生产中则可以更大可能的降低成本从而获得更大的利润，这也是信息时代发展的趋势所在。本课程设计的目的是使学生学会分析待加工处理数据的特性，以便选择适当的逻辑结构、存储结构以及进行相应的算法设计。学生在学习数据结构和算法设计的同时，培养学生的抽象思维能力、逻辑推理能力和创造性的思维方法，增强分析问题和解决问题的能力。此次设计的哈夫曼编码译码系统，实现对给定报文的编码和译码，并且任意输入报文可以实现频数的统计,建立哈夫曼树以及编码译码的功能。这是一个拥有完备功能的系统程序，对将所学到的知识运用到实践中,具有很好的学习和研究价值.关键词：信息；通讯；编码；译码；程序东北电力大学计算机科学与技术专业综合设计报告-III-AbstractThisisadatethatinformationspeedinghighlydevelopmentandtransmitinformationeverytime,everywherecannotleavetheinformation,itpassesthroughduringthepeopledailylifeproduction,theinfluenceexpandsdaybydaytothepeople,butcodesusingHuffmancarriesonthecorrespondencetobepossibletoraisethechannelusefactorgreatly,reducestheintelligencetransmissiontime,reducesthetransmissioncost.Maygreatlypossiblereducethecostintheproduction,thusobtainsabiggerprofit,thisisalsotheinformationagedevelopmenttendencyis.Thiscurriculumproject'sgoalismakesthestudentacademicsocietytoanalyzetreatstheprocessingdatathecharacteristic,withtheaimofchoosingthesuitablelogicalorganization,thememorystructureaswellascarriesonthecorrespondingalgorithmdesign.Thestudentduringthestudyconstructionofdataandalgorithmdesign’sraisesstudent'sabstractthinkingability,logicreasoningabilityandthecreativethoughtmethod,theenhancementanalysisquestionandsolvesthequestionability.Thisdesign'sHuffmancodesthecoderecognitionsystem,realizestoassignsthetextthecodeandthedecoding,andthearbitraryinputtextmayrealizethefrequencystatistics,establishestheHuffmantreeaswellasthecodedecodingfunction.Thisisonehasthecompletefunctionsystemprogram,totheknowledgewhichwilllearnutilizesinthepractice,hastheverygoodstudyandtheresearchvalue.Keywords：Information;Communication;Coding;Decoding;Procedure东北电力大学计算机科学与技术专业综合设计报告-1-第一章课题描述1.1问题描述利用哈夫曼编码进行通信，可以压缩通信的数据量，提高传输效率，缩短信息的传输时间，还有一定的保密性。现在要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进行编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。1.2需求分析在本例中设置发送者和接受者两个功能，1.2.1发送者的功能：①输入待传送的字符信息；②统计字符信息中出现的字符种类数和各字符出现的次数（频率）；②根据字符的种类数和各自出现的次数建立哈夫曼树；③利用以上哈夫曼树求出各字符的哈夫曼编码；④将字符信息转换成对应的编码信息进行传送。1.2.2接受者的功能：①接收发送者传送来的编码信息；②利用上述哈夫曼树对编码信息进行翻译，即将编码信息还原成发送前的字符信息。从以上分析可发现，在本例中的主要算法有三个：（1）哈夫曼树的建立；（2）哈夫曼编码的生成；（3）对编码信息的翻译。1.3程序设计目标层次一：编程从文件中读取一段报文，首先统计字符的频度，然后建立哈夫曼树，并给出报文的编码，然后根据使用者的需要对指定文件里的任意二进制编码进行译码并显示。层次二：使用者从系统界面输入字符串，统计从键盘输入的字符串信息，然后建立哈夫曼树，并给出报文的编码，然后根据使用者的需要对指定文件里的或者使用者从系统界面输入任意二进制编码的进行译码并显示。东北电力大学计算机科学与技术专业综合设计报告-2-第二章设计简介及设计方案论述2.1设计简介文字处理是现代计算机应用的重要领域。文本由字符组成，字符以某种编码形式存储在计算机中。每个字符的编码可以是相等长度的，也可以是不等长度的。ASCII编码是等长编码。为了提高存储和处理文本的效率，在一些计算机应用场合，如数据通信，常采用不等长的编码，对常用的字符用较少的码位，不常出现的字符用较多的码位编码，从而减少文本的存储长度。哈夫曼编码就是用于此目的的不等长编码方法。所以本次设计就是通过构造哈夫曼树来生成哈夫曼编码，最终完成设计要求。2.2设计方案论述哈夫曼编码/译码程序主要由主函数、哈夫曼树类和各种功能函数组成，程序运行时首先进入主函数，对各种功能函数进行调用，从而实现了整个程序的运行。将各种不同的函数分别包含在各自的结构体中，使整个程序结构更加的清晰明了，各功能相互独立且紧密联系，有利于编程的实现，同时也体现了面向对象设计语言的封装性。在主菜单中运用了switch()函数和“case”语句，便于对整个程序操作和控制；对数据保存在文档中，则运用了文件I/O流和C语言的文件处理方式，进行文件与内存之间输入，输出数据。2.3概要设计2.3.1第一部分功能的实现在主函数声明HuffmanTree1类的对象HuffmanNode，然后用HuffmanNode调用它的成员函数TranslatedCode()，此函数能读取Adata.txt里的字符串并统计，然后建立哈夫曼树并对各个字符编码和保存相关信息。然后对象HuffmanNode再调用成员函数TranslateArtcle（）对指定文件得到的二进制编码进行译码，并保存翻译得到的信息。2.3.1第二部分功能的实现获取并保存从键盘输入的字符串，并统计其信息。然后利用这些信息建立哈夫曼树对各个字符进行编码和保存相关信息。接着可以调用函数HuffmanTranslateCoding2（）对指定文件得到的二进制编码信息进行译码和保存得到的翻译信息，或者可以调用HuffmanTranslateCoding()对从系统页面输入的二进制编码进行翻译并保存翻译信息东北电力大学计算机科学与技术专业综合设计报告-3-第三章详细设计3.1哈夫曼树哈夫曼树也称最优二叉树.给定一组具有确定权值的叶子结点,可以构造出不同的二叉树,将其中带权路径长度最小的二叉树称为哈夫曼树.其中,叶子结点的权值(weight)是对叶子结点赋予的一个有意义的数值量.设二叉树具有n个带权值的叶子结点,从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和叫做二叉树的带权路径长度(weightedpathlength),记为:WPL=Wklk1nk,wk为第k个叶子结点的权值,lk为从根结点到第k个叶子结点的路径长度.3.2哈夫曼算法3.2.1基本思想根据,哈夫曼的定义,一棵二叉树要使其带权路径长度最小,必须使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点.依据这个特点便提出了哈夫曼算法,其基本思想是:(1)初始化:由给定的n个权值{w1,w2,…,wn}构造n棵只有一个根结点的二叉树,从而得到一个二叉树集合F={T1,T2,…,Tn};(2)选取与合并:在F中选取根结点的权值最小的两棵二叉树分别作为左、右子树构造一颗新的二叉树,这棵新二叉树的根结点的权值为其左、