数据结构哈夫曼编译码器

数据结构课设哈夫曼编译码器学号:姓名:提交日期:成绩:验名称哈夫曼编/译码器得实现

二、验要求【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本但就是，这要求在发送端通过一个编码系统对待传来数据预先编码，在接收端将传来得数据进行译码（复原）对于双工信道（即可以双向传输信息得信道），每端都需要一个完整得编/译码系统试为这样得信息收发站写一个哈夫曼码得编/译码系统【基本要求】一个完整得系统应具有以下功能:译码得过程与编码得过程相反，先将codefile文件中得二进制编码读出来，这时在主函数中也定义一个输入流类i fstream得对象i fs,同时将它与文件code file关联，通过i fs读取c odefile文件中得二进制编码,存放到数组buffer中，再通过译码函数进行译码，TranscodeHuffm an译码函数定义如下void Transco d elluf f manHufco deco d e[],II uf t ree tree[],c hars[]{oint i;，ch ar*q=NULL;o i=Hufnum-1;q=s;wh ile*q!=\0o if*q==O i=t ree[i]、Ichii d；if*q二二ri=tr ee[i]r c h ild；o iftree[i]1ch iId==0tr ee[i]r chil d==0{me out〈〈cod e[i]ch;=Hufnum—1；00}q++；}couten d1；}

五、该函数带三个参数，分别就是已建立好得哈夫曼树结点数组,哈夫曼编码表数组与需要进行译码得字符数组,该字符数组存放得即为由

0、1组成得一串编码,函数中设置字符类型指针q开始指向字符数组得第一个字符，若为0,则进入左孩子，否则进入右孩子，再执行q++,直到某结点得左右孩子下标值均为0得时候，此时得结点即为叶结点，于就是输出对应字符，再将起始结点设为根结点,重复上述过程，直到翻译出所有字符

六、测试结果

5.1哈夫曼树输出根据所给得27个字符及使用频度所建立得得哈夫曼树结构输出如图

5.123U8320024W18350025X1290026¥16340027Z12900282301118292302527304312829319323012321735233133283838343138172635354032243641401473745414223859443334396445513407646353641924737942994719204311448101544122493816451284923946156504021471915141424635364192473794299471920431144810154412249381645128492394615650402147191514142482175164349250524445503425246151408534748525925349505310000515211初始化Ini tializationo从终端读入字符集大小n,以及n个字符与n个权值，建立哈夫曼树,并将它存于文件h fmTree中2E:编码Enc oding.利用已建好得哈夫曼树如不在内存，则从文件hfmTree中读人,对文件T oBeTr an中得正文进行编码，然后将结果存入文件CodeFi1e中3D译码Dec oding利用已建好得哈夫曼树将文件CodeFile中得代码进行译码，结果0存入文件TextFile中4P打印代码文件Print将文件Cod eFile以紧凑格式显示在终端上,每行50个代码.同时将此字符形式得编码文件写入文件CodePri n中5T:打印哈夫曼树Tree printin g.将已在内存中得哈夫曼树以直观得方式树或凹入表形式显示在终端上，同时将此字符形式得哈夫曼树写入文件TreePrint中【测试数据】1利用教科书例6—2中得数据调试程序.A BC D E F G H I J K L M2用下表给出得字符集与频度得实际统计数据建立哈夫曼树，并实现以下报文得编码与译码”TH IS PR0GRAMI SM YFAVO RITEo字符频度153220字符N OP R S T U VW XY ZQ频度57681811613

三、求分析Huffman编码就是一种可变长编码方式,就是由美国数学家Dav id Huf f man创立得,就是二叉树得一种特殊转化形式编码得原理就是将使用次数多得代码转换成长度较短得代码，而使用次数少得可以使用较长得编码，并且保持编码得唯一可解性.Hu ffman算法得最根本得原则就是累计得（字符得统计数字*字符得编码长度）为最小，也就就是权值（字符得统计数字文字符得编码长度）得与最小

3.1设计简介本设计就是通过对给定字符及其使用频度构造哈夫曼树再根据哈夫曼树进行哈夫曼编码，在此之前，首先要理解哈夫曼树、哈夫曼算法、哈夫曼编译码得概念与原理

3.L1哈夫曼树从树得根结点到树得每个结点得路径长度之与即为该树得路径长度而在实际应用中，常将树得结点赋予一个有某种含义得数值,这个数值就称为结点得权从树得根结点到该结点之间得路径长度与结点权得乘积称为该结点得带权路径长度，树中所有叶结点得带权路径长度之与称为树得带权路径长度通常记作WP L=式中，n表示树中叶子结点得数目，wi表示叶结点ki得权，li表示根结点到叶结点Ki之间得路径长度.在n个权值为wl,w2,……w n得带权叶结点构成得所有二叉树中,其带权路径长度WPL最小得二叉树即为哈夫曼树或最优二叉树

3.L2哈夫曼算法给定n个带权叶结点，如何构造一棵n个带有给定权值得叶结点得二叉树，使其带权路径长度最小？哈夫曼首先给出了构造最有二叉树得方法，故称其为哈夫曼算法，其基本得算法思想如下

①将n个权值分别就是wl,w2,wn得结点按权值递增排列将每个权值作为一个二叉树，构成n棵二叉树得森林F={T1,T2,…，Tn},其中每棵二叉树都只有一个权值为Wi得根结点，其左右子树均为空

②在森林F中选两棵根结点权值最小得二叉树，作为左右子树构造一棵新得二叉树,并使得新二叉树根结点得权值为其左右子树上根结点权值之与

③在森林F中，删除这两棵树，同时将新得到得二叉树代替这两棵树加入到森林F中去,因此，森林F中二叉树得个数比以前少一棵

④对新得森林F重复

②与

③，直到森林中只有一棵树为止这棵树就就是哈夫曼树

3.L3哈夫曼编码用哈夫曼树得到得二进制前缀编码就就是哈夫曼编码具体做法就是:对于给定得字符集C={cl,c2,•••,cn}及字符出现得频率W={wl,w2,••,wn,以cl,c2,…，cn作为叶结点,以wl,w2,…，wn作为该结点上得权，利用哈夫曼算法，构造一棵带权路径长度最小得得哈夫曼树然后对哈夫曼树中每个分支结点得左右分支分别用0与1进行编码，这样从树得根结点到每个叶结点之间,沿途路径上0与1组成得编码序列就就是叶结点所代表字符得二进制编码

4.L4哈夫曼译码哈夫曼译码过程与编码过程相反,译码过程就就是分解电文中字符串得过程，具体步骤如下首先输入要一点问得二进制编码，然后从哈夫曼树得根结点出发，对于电文得二进制编码,按照二进制位串中得0与1确定就是进入左分支还就是右分支若编码为0,则进入结点得左孩子,否则进入结点得右孩子，一旦到达叶结点,就译出该叶子结点所代表字符

3.2设计方案

3、

2.1设计思路要编程实现该系统,需逐步实现

1.哈夫曼树得建立，即根据所给字符及对应频度构造哈夫曼树，哈夫曼树构造函数包括对哈夫曼树得初始化、赋值与建立;

2.哈夫曼编码表得建立，即编写程序实现对所给字符进行哈夫曼编码，将每个字符得哈夫曼编码存储到一个位串数组中去；

3.打印输出哈夫曼树与哈夫曼编码表，在终端上显示出哈夫曼树得结构与各字符名称及对应得哈夫曼编码；

4.编码，对输入得字符串进行哈夫曼编码，将结果写入文件；

5.译码,将文件中得哈夫曼编码按照编码表翻译成对应字符串并显示到终端上设计流程图

1.图

2.1总流程图

2.定义哈夫曼结点存储结构与哈夫曼编码存储结构，之后定义一个结点存储结构数组用来存放结点信息，与定义一个编码存储结构数组用来存放字符得哈夫曼编码，同时定义全局数组存放字符与它得使用频度.

3.先将已建立好得二叉树初始化，再对其中得叶结点其赋予字符名与对应使用频度作为结点名与结点权值，最后通过哈夫曼算法构造哈夫曼树，同时在屏幕输出哈夫曼树.

4.通过已建立好得哈夫曼树再对字符进行二进制编码,编码结束后,对应每个字符都有一个二进制编码，此编码即为哈夫曼编码，将字符及其哈夫曼编码存放到哈夫曼编码存储结构体数组中去，构成哈夫曼编码表，同时在屏幕上输出哈夫曼编码表

5.编码函数执行，即对输入得字符串根据哈夫曼编码表进行编码,将字符串得二进制编码存放到一个字符数组中去

6.建立文件，将字符数组中得二进制编码写入文件，这需要定义输出流类得对象并与文件关联，通过操作对象来操作文件得数据写入

7.将文件中得二进制编码进行译码，这需要定义输入流类得对象并与文件关联，将文件中得编码读取到另一字符数组中去，调用译码函数进行译码

8.结束ere at tree h uffma ncreatco dehuffm anwrit ecodehuff mantranscodehuffmanprint tree huffmanp ri n tc odehuffma n

4.1哈夫曼树得建立

4、L1哈夫曼树得存储结构为了实现通过哈夫曼算法建立哈夫曼树,首先要定义哈夫曼树得存储结构由于构造哈夫曼树之后,编码时要从叶结点出发走一条从叶结点到根得路径，而译码时要从根结点出发走一条从根到叶结点得路径.对于每个结点而言，既需知道双亲得信息，又需知道孩子得信息因此，可以使用带双亲得孩子链表作为结点得存储结构由哈夫曼算法可知，如果哈夫曼有n个叶结点，则最终生成得哈夫曼树共有2n-l个结点因此，可以用一个长度为2n得一维数组存放哈夫曼树得所有结点详细定义如下#d ef i n e Leaf num27#de fineHufnum2*Leaf numty p e defchar DataType;typ edef stru ct Tn ode{DataT ypenam e；0do ubleweight;oint Ichild,r child,pa re nt;}Huf Iree；Hu ft reeTree[Hufnum];其中,name表示结点数据得名称（即字符名称），w eight表示结点得权值（即字符使用频度）/child、r chiId分别就是结点得左、右孩子在数组中得下标值，叶结点得左右孩子得下标值均为0；Pa rent表示结点双亲在数组中得位置.它得主要作用有两点第一,区分根结点与非根结点；第二，使得查找某个结点得双亲变得更为简单若parents,则该结点就是树得根结点，否则为非根结点因为把森林中得两棵二叉树合并成一棵二叉树时，必须从森林得所有结点中选取两个根结点得权值为最小得结点,此时就就是根据p arent来区分根与非根结点得

4、L2建立哈夫曼树本设计只对26个英文大写字符及空格进行了哈夫曼编码,各字符及对应使用频度如下表所V JW,，X，，Y\Z｝；示表

4、1字符及其使用频度字符AB CDEFGHIJKLM53220频度1N VW YZ字符0P QRSTUX频度57638181161需要定义全局数组来存放这些字符名称与对应频度char ch[]={\0,，A，J B「C，D,E，F,G,，H,I「，N，,，P「Q，「R\S,，T，/W,f1oat w[]={0,186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1};，定义函数Crea tTre eHuffman,其中包括对已建立好得哈夫曼树得初始化，即将结点数据名称初始化为\0,将结点权值、结点双亲及左右孩子得下标值都初始化为0；对已初始化得哈夫曼树赋值，将全局数组ch中存放得字符名称赋到叶结点得name上，将全局数组w中存放得字符使用频度赋到叶结点得weig ht上；最后根据哈夫曼算法对27个结点（每个结点可以瞧做就是一棵树）构造出哈夫曼树

4.2哈夫曼编码表得建立

4.

2、1哈夫曼编码表得存储结构利用哈夫曼树对字符进行哈夫曼编码，实际上就就是求出从根结点到叶结点得路径由于采用带双亲得孩子链表作为存储结构，因此,对于输入得每个字符,可以从哈夫曼树得叶结点出发，沿结点得双亲链回溯到根结点,在这个过程中，每回溯一步都会经过哈夫曼树得一个分支,从而得到一个哈夫曼编码因此,可设置一个位串数组b it S,将生成得代码序列从后到前依次存放到数组bits中哈夫曼编码表存储结构定义如下typedef structCn ode（char bits[Lea fnum+1]；int star t;char ch；由于叶子结点总数即字符个数为Leafnum,故不等长编码得长度不会超过Le afnum,再加上结束符号\0,位串数组b it s得大小应为LeafnumH,整型变量star t用来指示编码在数组中得起始位置,当某个字符编码完成时,从变量得st art处开始将编码复制到该字符对应得数组bits中去即可.建立哈夫曼编码表建立哈夫曼编码表即建立一个表格用来存储每个字符名称与对应得哈夫曼编码，此过程建立在已经构造好得哈夫曼树上,从叶结点开始,沿着双亲链向上，记录沿途经过分支上得二进制编码，直到到达根结点，于就是对应每一个字符都有一个二进制串，即它得哈夫曼编码，用上面定义得哈夫曼编码表存储结构数组存放起来,即存在位串数组b its中.

4.3编码本程序得功能就是能对从键盘输入得任意有限长度得字符串（限定在大写英文字符与空格）进行哈夫曼编码，因此需要定义函数WritecodeHuf fman来实现对输入得字符串逐个进行编码，此过程实质上就是将字符与编码表里得字符名称相比较，当名称一致时，就输出对应字符得bits数组中得二进制编码，然后依次输出每个字符得哈夫曼编码，将她们连续得显示在屏幕上

4.4文件写入由于要将这些二进制串写入文件,所以事先再定义一个全局字符数组Huffmanco de来存储这些二进制串在主函数先在某目录下建立一个、txt文件，名为codef i1e,再定义了一个输出流类of stream得对象o fs,定义ofs得同时将其与文件codef i1e关联,于就是,就可以通过操作fs来实现文件数据得写入，即将字符数组Huffman code中得二进制编码写入文件

[1]

4.5译码。