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

哈夫曼编码译码系统实验报告 东北电力大学计算机科学与技术专业 综合 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 报告 目 录 摘 要 ………………………………………………………………………..……………… II Abstract …………………………………………………………………………..………... II 第一章 课题描述………………………..………………………………………………….. 1 1.1 问题描述………………………………………………………………………………...1 1.2 需求 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 …………………………………………………..…………………………… 1 1.3 程序设计目标…………………………………………………………………………… 第二章 设计简介及 设计方案 关于薪酬设计方案通用技术作品设计方案停车场设计方案多媒体教室设计方案农贸市场设计方案 论述 ………………………………………………………… 2 2.1 设计简介.………………………………………………..………………………..….…2 2.2 设计 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 论述……………………………………………..…………………….………2 2.3 概要设计…………………………………………………..………………………….…2 第三章 详细设计…………………………………………………………..……….….…….. 4 3.1 哈夫曼树…………………………………………………..………………………….…4 3.2 哈夫曼算法………………………………………………..……………………….….…4 3.2.1 基本思想………………………………………………..……………………..…..….…4 3.2.2 存储结构………………………………………………..………………………….....…4 3.3 哈夫曼编码………………………………………………..………………………….…5 3.4 文件I/O流………………………………………………..………………………….…6 3.4.1 文件流…………………………………………………..………………………………6 3.4.2 文件的打开与关闭………………………………………..…………………….……….7 3.4.3 文件的读写…………………………….………………..………………………..…..…7 3..5 C语言文件处理方式…………………………………………………………………… 第四章 设计结果及分析…………………………………………………..……………..….. 8 4.1 设计系统功能………………………………….……………………………….....….…8 4.2 进行系统测试……………………………………………..………………………….…8 总 结 …….……………………………………………………..…………………………...13 致 谢 …….……………………………………………………..……………………..…….14 参考文献 …….………………..………………………………..……………………..…….15 附录 主要程序代码 ………...………………………………..………………………..….16 - I - 东北电力大学计算机科学与技术专业 综合设计报告 摘 要 在这个信息高速发展的时代，每时每刻都在进行着大量信息的传递，到处都离不开信息，它贯穿在人们日常的生活生产之中，对人们的影响日趋扩大,而利用哈夫曼编码进行通信则可以大大提高信道利用率，缩短信息传输时间，降低传输成本。在生产中则可以更大可能的降低成本从而获得更大的利润，这也是信息时代发展的趋势所在。本课程设计的目的是使学生学会分析待加工处理数据的特性，以便选择适当的逻辑结构、存储结构以及进行相应的算法设计。学生在学习数据结构和算法设计的同时，培养学生的抽象思维能力、逻辑推理能力和创造性的思维 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 ，增强分析问题和解决问题的能力。此次设计的哈夫曼编码译码系统，实现对给定报文的编码和译码，并且任意输入报文可以实现频数的统计,建立哈夫曼树以及编码译码的功能。这是一个拥有完备功能的系统程序，对将所学到的知识运用到实践中,具有很好的学习和研究价值. 关键词:信息;通讯;编码;译码;程序 - II - 东北电力大学计算机科学与技术专业 综合设计报告 Abstract This is a date that information speeding highly development and transmit information every time, everywhere cannot leave the information, it passes through during the people daily 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 production, thus obtains a bigger profit, this is also the information age development tendency is. This curriculum project's 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 structure as well as carries on the corresponding algorithm design. The student during the study construction of data and algorithm design’s raises student's abstract thinking ability, logic reasoning ability and the creative thought method, the enhancement analysis question and solves the question ability. This design's 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, 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 - III - 东北电力大学计算机科学与技术专业 综合设计报告 第一章 课题描述 1.1问题描述 利用哈夫曼编码进行通信，可以压缩通信的数据量，提高传输效率，缩短信息的传输时间，还有一定的保密性。现在要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进行编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。 1.2需求分析 在本例中设置发送者和接受者两个功能， 1.2.1发送者的功能: ?输入待传送的字符信息; ?统计字符信息中出现的字符种类数和各字符出现的次数(频率); ?根据字符的种类数和各自出现的次数建立哈夫曼树; ?利用以上哈夫曼树求出各字符的哈夫曼编码; ?将字符信息转换成对应的编码信息进行传送。 1.2.2接受者的功能: ?接收发送者传送来的编码信息; ?利用上述哈夫曼树对编码信息进行翻译，即将编码信息还原成发送前的字符信息。 从以上分析可发现，在本例中的主要算法有三个: (1)哈夫曼树的建立; (2)哈夫曼编码的生成; (3)对编码信息的翻译。 1.3程序设计目标 层次一:编程从文件中读取一段报文，首先统计字符的频度，然后建立哈夫曼树，并给出报文的编码，然后根据使用者的需要对指定文件里的任意二进制编码进行译码并显示。 层次二:使用者从系统界面输入字符串，统计从键盘输入的字符串信息，然后建立哈夫曼树，并给出报文的编码，然后根据使用者的需要对指定文件里的或者使用者从系统界面输入任意二进制编码的进行译码并显示。 - 1 - 东北电力大学计算机科学与技术专业 综合设计报告 第二章 设计简介及设计方案论述 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()对从系统页面输入的二进制编码进行翻译并保存翻译信息 - 2 - 东北电力大学计算机科学与技术专业 综合设计报告 第三章 详细设计 3.1 哈夫曼树 哈夫曼树也称最优二叉树.给定一组具有确定权值的叶子结点,可以构造出不同的二叉树,将其中带权路径长度最小的二叉树称为哈夫曼树.其中,叶子结点的权值(weight)是对叶子结点赋予的一个有意义的数值量.设二叉树具有n个带权值的叶子结点,从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和叫做二叉树的带权路径长度(weighted path length),记为: n WPL=,w为第k个叶子结点的权值,l为从根结点到第k个叶子结点的路径Wklkkk,k,1 长度. 3.2 哈夫曼算法 3.2.1 基本思想 根据,哈夫曼的定义,一棵二叉树要使其带权路径长度最小,必须使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点.依据这个特点便提出了哈夫曼算法,其基本思想是: (1) 初始化:由给定的n个权值{w, w,„, w}构造n棵只有一个根结点的二叉12n 树,从而得到一个二叉树集合F={ T,T,„,T}; 12n (2) 选取与合并:在F中选取根结点的权值最小的两棵二叉树分别作为左、右子 树构造一颗新的二叉树,这棵新二叉树的根结点的权值为其左、右子树根结点的权值 之和; (3) 删除与加入:在F中删除作为左、右子树的两棵二叉树,并将新建立的二叉树 加入到F中; (4) 重复(2)、(3)两步,当集合F中只剩下一棵二叉树时,这棵二叉树便是哈夫曼 - 3 - 东北电力大学计算机科学与技术专业 综合设计报告 树. 3.2.2 存储结构 在由哈夫曼算法构造的哈夫曼树中,非叶子结点的度均为2，根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有2n-1个结点,其中有n-1个非叶子结点,它们是在n-1次的合并过程中生成的.为了便于选取根结点权值最小的二叉树以及合并操作,设置一个数组HuffmanNode[2n-1]保存哈夫曼树中各结点的信息,数组元素的结点结构如图3-1所示. weight parent lchild rchild i nf 图3-1 哈夫曼树的结点结构 其中, 权值域,保存该结点的权值; weight: lchild:指针域,保存该结点的左孩子结点在数组中的下标; rchild:指针域,保存该结点的右孩子结点在数组中的下标; parent:指针域,保存该结点的双亲结点在数组中的下标. Inf:存储相关的字符信息 可以用C中的结构类型定义上述结点. struct HuffmanNode {char inf; int weight; int parent; int lchild,rchild; }; 3.3 哈夫曼编码 哈夫曼树可用于构造最短的不等长编码方案,具体做法如下:设需要编码的字符集合为{d,d,„,d},它们在字符串中出现的频率为{w, w,„, w},以d,d,„,d作为叶12n12n12n子结点, w, w,„, w作为叶子结点的权值,构造一颗哈夫曼编码树,规定哈夫曼编码树12n 的左分支代表0，右分支代表1，则从根结点到每个叶子结点所经过的路径组成的0和1的序列便为该叶子结点对应字符的编码,称为哈夫曼编码(Huffman Code). - 4 - 东北电力大学计算机科学与技术专业 综合设计报告 在哈夫曼编码树中,数的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和,所以采用哈夫曼树构造的编码是一种能使字符串的编码总长度最短的不等长编码.由于哈夫曼编码树的每个字符结点都是叶子结点,它们不可能在根结点到其他字符结点的路径上,所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀,从而保证了解码的唯一性. 3.4 C++文件I/O流 3.4.1 文件的打开与关闭 本程序中，建立流对象调用成员函数open和close进行文件的打开和关闭。 成员函数open返回非零值或者true，表示流对象已经成功关联到磁盘文件，否则返回0或者false表示该流对象没有关联到文件。 成员函数close首先刷新缓冲区，把所有等待输出的内容写到磁盘文件中，然后关闭磁盘文件，并断开磁盘文件与文件缓冲区的联系。 3.4.2 文件的读写 由于ifstream、ofstream、fstream分别派生自istream、ostream、iostream，因此定义于类istream、ostream、iostream中的大部分共有成员函数。 流插入运算符函数operator<<和流提取运算符函数operator>>、put/get/getline函数主要用于格式化I/O。write/ read函数则常用于无格式化I/O。 3.5 C语言文件处理方式 3.5.1 结构体FILE 结构体FILE类型可以用来定义文件型指针变量，可以使指针指向某一个文件的结构体变量，从而通过该结构体变量中的文件信息能够访问该文件。例如: FILE *fp; 3.5.2 文件的打开(fopen函数)和文件的打开(fclose函数) FILE *fp; fp= fopen(文件名，使用文件方式); fclose(文件指针); 例如: - 5 - 东北电力大学计算机科学与技术专业 综合设计报告 FILE *fp; fp=fopen(“al”,”w”); fclose(fp); 3.5.3 文件的读写 fputc函数 把一个字符写到磁盘文件上去，其一般调用形式为 putc(ch,fp); 其中ch是要输出的字符。fp是文件指针变量。 fget函数 从指定的文件读入一个字符，该文件必须是以读或读写方式打开的。 fgetc函数的调用形式 ch=fgetc(fp); 其中ch是要输出的字符。fp是文件指针变量。 3.6程序功能的详细设计 请看附录的源程序的 详细清单 第四章 设计结果及分析 4.1 设计系统功能 层次一:编程从文件中读取一段报文，首先统计字符的频度，然后建立哈夫曼树，并给出报文的编码，然后根据使用者的需要对指定文件里的任意二进制编码进行译码并显示。 层次二:使用者从系统界面输入字符串，统计从键盘输入的字符串信息，然后建立哈夫曼树，并给出报文的编码，然后根据使用者的需要对指定文件里的或者使用者从系统界面输入任意二进制编码的进行译码并显示。 - 6 - 东北电力大学计算机科学与技术专业 综合设计报告 4.2 进行系统测试 图4-1 系统界面 - 7 - 东北电力大学计算机科学与技术专业 综合设计报告 图4-2从文件中提取字符串并进行字符的统计 - 8 - 东北电力大学计算机科学与技术专业 综合设计报告 图4-3A操作的字符串的哈夫曼编码 - 9 - 东北电力大学计算机科学与技术专业 综合设计报告 图4-3 B操作对Acode.txt里的二进制编码进行译码和保存翻译信息 - 10 - 东北电力大学计算机科学与技术专业 综合设计报告 图4-4 C操作从键盘输入字符串并统计、编码和保存 - 11 - 东北电力大学计算机科学与技术专业 综合设计报告 图4-5D操作对Ccode.txt里的二进制编码进行译码再保存保存 图4-6E操作对在系统页面输入的二进制编码进行译码 - 12 - 东北电力大学计算机科学与技术专业 综合设计报告 图4-7F操作退出系统 - 13 - 东北电力大学计算机科学与技术专业 综合设计报告 图4-8 以上操作得到的相关数据 图4-8 退出系统 总 结 通过本次课程设计使我对哈夫曼树及哈夫曼编码有了更深刻的理解，同时对C，C++的编程以及算法的实现产生了比较大的兴趣。还学到了许多在处理程序时的技巧和方法，这都对以后的学习大有裨益，以及感受到在编程设计中团队合作精神的重要性。 在这次程序设计中，我觉得重要的一点，那就是不要人云亦云，要有自己的主见，不管别人如何，一定要有自己的思想，并且始终不改变的去坚持，纵然，可能会遇到很多难以解决的困难，都要自始到终，相信自己能把这个程序做得出来。当自己最终在自己的努力下完成任务的时候，那就会有更多属于自己的收获，包括成功的喜悦以及程序中体现的思想。 - 14 - 东北电力大学计算机科学与技术专业 综合设计报告 其次是我认为调试功能是整个编写程序过程中很重要的一个环节。通过此次实验我对调试有了更加深刻的理解，懂得怎么样去调试程序，如何发现错误，如何更高效的改正，最终能把程序实现。 致 谢 在本次课程设计的整个过程中，要特别感谢自始至终给我提供帮助和指导的X老师，是他耐心的指导才使得本次设计得以顺得完成，同时，也要感谢小组成员的不懈努力和互相配合，在此还要特别感谢为我们提供良好上机环境的学校.如果没有以上老师，同学和学校的帮助和支持，本次设计实难完成.再次感谢老师的精心辅导和同学的相互帮助，使我们顺利完成此次设计以及为学习以后的科目打下良好的基础. - 15 - 东北电力大学计算机科学与技术专业 综合设计报告 参考文献 【1】 C语言程序设计(第三版) 谭浩强 清华大学出版社 2009.10 【2】 C++语言程序设计(第四版)。 郑莉 董渊 何江舟 清华大学出版社2010.7 【3】 数据结构(C版)。曲朝阳 郭晓利 王晓慧 孙鸿飞 中国电力出版社 2007.8 - 16 - 东北电力大学计算机科学与技术专业 综合设计报告 附录 主要程序代码: //HuffmanCode1.h #ifndef HUFFMAMCODE_H #define HUFFMAMCODE_H #include #include using namespace std; struct HuffmanNode //定义哈夫曼树各结点 { int weight; - 17 - 东北电力大学计算机科学与技术专业 综合设计报告 int parent; int lchild,rchild; int flag; }; class HuffmanCode1 //哈夫曼编码类 { public: char Info[100]; int Start; char Leaf; }; class HuffmanTree1 //建立哈夫曼树类 { private: HuffmanNode *Node; public: int f; HuffmanCode1 *hf; HuffmanTree1(); ~HuffmanTree1(); void TranslatedCode(); void CodeHuf(HuffmanNode a[],HuffmanCode1 b[],int n); void CreateHfmTree(char Str[],int m[],int n); void TransCode(HuffmanCode1 b[],int n) ; void TranslateArtcle(HuffmanCode1 b[],int n) ; }; #endif //HUFFMAMCODE_HHuffmanCode.cpp #include "iostream" #include - 18 - 东北电力大学计算机科学与技术专业 综合设计报告 #include "math.h" #include "stdlib.h" #include"HuffmanCode1.h" #include using namespace std; #define MAXDATA 10000 //最长字符串 #define MAXSIZE 150 //最多子叶数 ////////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////// ///////////第一部分功能(W)实现的代码$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ HuffmanTree1::HuffmanTree1() { Node=NULL; } //将树结点初始化为空 HuffmanTree1::~HuffmanTree1() { delete[] Node; } //释放结点空间 void HuffmanTree1::CreateHfmTree(char Str[],int m[],int n)//建立哈夫曼树 { int i,j,m1,m2,x1,x2; HuffmanNode *HfmNode=new HuffmanNode[2*n-1]; HuffmanCode1 *HfmCode=new HuffmanCode1[n]; for(i=0;i<2*n-1;i++) { HfmNode[i].weight=0; HfmNode[i].parent=0; HfmNode[i].flag=0; HfmNode[i].lchild=-1; HfmNode[i].rchild=-1; } for(i=0;i=HT[s1].weight && HT[i].weight<=HT[s2].weight) s2=i; while(HT[i].parent==0 && s1==s2) { m=i; m++; while(HT[m].parent!=0) m++; s2=m; } } } void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n, char *info) { //哈弗曼编码 int i,m; HuffmanTree p; if(n<1) return; m = 2*n-1; HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=HT+1,i=1;i<=n;++i,++p,++w,++info) { //初始化所有已存在的子叶信息 p->info = *info; p->weight = *w; p->parent = 0; p->lchild = 0; p->rchild = 0; }//for for(; i<=m;++i,++p) { //构造所需要的过度根节点 p->weight = 0; p->parent = 0; p->lchild = 0; p->rchild = 0; }//for for(i=n+1;i<=m;++i) - 25 - 东北电力大学计算机科学与技术专业 综合设计报告 { //建立哈弗曼树 int s1,s2; Select(HT,i-1,s1,s2); HT[s1].parent =i; HT[s2].parent =i; HT[i].lchild = s2; HT[i].rchild = s1; HT[i].weight = HT[s1].weight+HT[s2].weight; }//for //哈弗曼编码 HC = (HuffmanCode)malloc((n+1)*sizeof(char *)); char* cd = (char*)malloc(n*sizeof(char)); cd[n-1] = '\0'; for(i=1;i<=n;++i) { int f; unsigned int c; int start=n-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) { if(HT[f].lchild==c) cd[--start] = '0'; else cd[--start] = '1'; } HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i], &cd[start]); }//for free(cd); }//HuffmanCoding //Y功能实现 输出并保存字符串的二进制编码 void CheckCoding(HuffmanTree HT, HuffmanCode HC, char *strcheck, int m,int k) { ofstream ofs("BCode.txt"); //查询哈弗曼编码信息 int p; for(int i=0; i>choose; cout<<"******************************************************************************* "<>ch; HuffmanTranslateCoding(HT,n,ch); break; case 'T': case 't'://退出系统 return 0; case 'C': case 'c'://进行编码操作 cout<<"请输入您要编码的字符串:"<