完整word版哈夫曼编码和译码的设计与实现

1、算法与数据结构课程设计哈夫曼编码和译码的设计与实现1.问题描述利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输时间， 降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码， 在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息 的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个 哈夫曼码的编/译码系统。2.基本要求a.编/译码系统应具有以下功能:(1)(2)(3)(4)I :初始化（Initialization）。从终端读入字符集大小 n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。E：编码（Enco

2、ding）。利用已建好的哈夫曼树（如不在内存，则从文 件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将 结果存入文件CodeFile中。D：译码（Decoding）。利用已建好的哈夫曼树将文件 CodeFile中的代 码进行译码，结果存入文件 TextFile中。P:印代码文件（Print ）。将文件CodeFile以紧凑格式显示在终端上， 每行50个代码。同时将此字符形式的编码文件写入文件 CodePrin中。(5)T：印哈夫曼树（Tree printing ）。将已在内存中的哈夫曼树以直观的 方式（树或凹入表形式或广义表）显示在终端上，同时将此字符形式的哈夫曼树写入

3、文件Tree Print中。b.测试数据（1）利用下面这道题中的数据调试程序。其概率分别为0.25,0.29，0.07，某系统在通信联络中只可能出现八种字符，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。THIS P ROGRAM IS MY FAVOR”。（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以 下报文的编码和译码：字符空格A频103211547573220字符N O频度 57 63 15148 5180 23 8181 16 13.1程序的基本功能本程序可以对任何大小的字符型文件进行3. 需求分析生成一个编码文件。H

4、uffman 编码，并可以在程序运行结束后的任意时间对它解码还原生成字符文件。即：先对一条 电文进行输入，并实现Huffman编码，然后对Huffman编码生成的代码串进行译 码，最后输出电文数字3.2输入/输出形式当进行编码时输入为原字符文件文件名，当程序运行编码完成之后输入编码文件 名(默认名为code.dll)。当进行译码时输入为编码文件名(默认名为code.dll),从文件中读取 Huffman编码树后输入字符文件的文件名。3.3测试数据要求本程序中测试数据主要为字符型文件。4. 概要设计1. 系统结构图(功能模块图)哈弗曼树编码译码器厂译码退出编码2. 功能模块说明(1).编码：提示

5、要编码的文件文件名-读取文件-以字母出现次数为权值建立哈弗曼树T对文本进行哈弗曼编码并输出编码T提示将编码保存的文件名-保存编码文件；(2) .译码：提示输入要译码的文件名-利用建立好的哈弗曼树进行译码- 将译码输出-提示保存译码文件的文件名-保存译码文件；(3) .退出：退出系统，程序运行结束。5. 详细设计创建哈弗曼树编码译码6. 调试分析1. 从叶子节点开始向上遍历二叉树，获得哈夫曼编码；2. 根据哈夫曼编码遍历哈夫曼树直到叶子节点，获得译码3. 算法的时间复杂度分析：程序部分用双循环嵌套结构，时间复杂度为0(n2).4. 算法的空间复杂度分析：算法的空间复杂度为 0 (n)5. 程序需

6、要反复调试，并且调试过程比较慢，需要有一个比较正确的调试方 法，更需要我们有耐心7. 用户使用说明1输入字符的个数n2输入n个字符和n个权值3选择（15）操作可对huffman树进行编码和译码以及huffman树表的打 印4退出系统8. 测试结果abcWinTCpro j ect s4- exe19111I,nftcodingB.codeprintingblease input Che process: HI卩lease input the codinguH ：CC.ppi nttheHuffmanD.exit|A codingB. codepLxntxngplease input the p

7、rocess =C.p i*intthehuPFmanD.exitbbcA.coding B.codeprinting pIeAS& input the process: CC-printthehuffmanD.exitwd/务uaI leftchild rightcbild pvents0 9 40 0 512 53 4 0hiItn codingB.codeprintingplease input the puocess，C-printtheHuffmanD.exit:fin-TCprojects4- eseh2please Input the uard and thec3a 1b 2G

8、3 iiixVn.codingB.codeprintingplease input the process：7.A. codingB.cadB print insrplease input the process=mease input the uordsuHdbclaAcodingB.codeprintingplease input the ppocess:B“please input the codingu|fl Xequal：C.printC.printC-printthettiehuffmanliufFnanhuffiDitnP.exitD.exitD.exit9. 附录#in elu

9、de stdio.h #i nclude stdlib.h#i nclude stri ng.h#defi ne MAX 100struct HafNodeint weight;int parent;char ch;int lchild;int rchild;*myHaffTree;struct Codi ngchar bitMAX;char ch;int weight;*myHaffCode;void Haffma n(i nt n)/*构造哈弗曼树*/int i,j,x1,x2,s1,s2;for (i=n+1;i=2* n-1;i+)s仁s2=10000;x1=x2=0;for (j=1

10、；j=i-1；j+)if(myHaffTreej. pare nt=0&m yHaf1Treej.weights1)s2=s1;x2=x1;s1=myHaffTreej.weight;x1=j;else if(myHaffTreej. parent=0&m yHaffTreej.weights2)s2=myHaffTreej.weight;x2=j;myHaffTreex1. paren t=i;myHaffTreex2. paren t=i;myHaffTreei.weight=s1+s2;myHaffTreei.lchild=x1;myHaffTreei.rchild=x2;void Ha

11、ffma nCode(i nt n)int start,c,f,i,j,k;char *cd;cd=(char *)malloc (n *sizeof(char);myHaffCode=(struct Codi ng *)malloc( n+1)*sizeof(struct Codi ng); cdn-1=0;for(i=1;i=n ;+i)start=n-1;for(c=i,f=myHaffTreei. paren t;f!=0;c=f,f=myHaffTreef. paren t) if(myHaffTreef.lchild=c) cd-start=0;else cd-start=1;fo

12、r(j=start,k=0;j n;j+)myHaffCodei.bitk=cdj;k+;myHaffCodei.ch=myHaffTreei.ch;myHaffCodei.weight=myHaffTreei.weight;free(cd);void prin t() prin tf(* *n);prin tf(* *n);prin tf(* *n);prin tf(* welcome to huffma n codi ng and code prin ti ng *n);prin tf(* *n);prin tf(* *n);2.codi ng3.code prin ti ng4.pnnt

13、 the huffma n5.exitprin tf(*1.i nit*n);prin tf(* *n);prin tf(* *n);Ini t()int i,n ,m;printf(now in itn ”)；printfCp lease input the nu mber of words: n);scan f(%d,&n);m=2* n-1;myHaffTree=(struct HafNode *)malloc(sizeof(struct HafNode)*(m+1);for(i=1;i=n ;i+)printfCpl ease input the word and the equal:

14、 n);sca nf(%s%d,&m yHaffTreei.ch, &m yHaffTreei.weight);myHaffTreei. paren t=0;myHaffTreei.lchild=0;myHaffTreei.rchild=0;for(i=n+1;i=m;i+)myHaffTreei.ch =#;myHaffTreei.lchild=0;myHaffTreei. paren t=0;myHaffTreei.rchild=0;myHaffrreei.weight=O;Haffma n(n);Haffma nCode( n);for(i=1;i=n ;i+)prin tf(%c %d

15、,myHaffCodei.ch,myHaffCodei.weight);prin tf(n);prin tf(i nit success! n);return n;*/void Caozuo_C(i nt m)/* 对字符进行编码int n,i,j;char stri ng50,* p;printfCplease input the words : n”)；scan f(%s,stri ng);n=strle n( stri ng);for(i=1, p=stri ng;i=n ;i+,p+)for(j=1;j=m;j+)if(myHaffCodej.ch=* p)prin tf(%sn,my

16、HaffCodej.bit);void Caozuo_D(i nt n)int i,c;char code1000,* p;printf(please input the coding : n”)；scan f(%s,code);for(p=code,c=2* n-1;* p!=0; p+)if(*p=0)c=myHaffTreec .l child;if(myHaffTreec.lchild=0)prin tf(%c,myHaffTreec.ch);c=2* n-1;con ti nue;else if(*p=1)c=myHaffTreec.rchild;if(myHaffTreec.lch

17、ild=0)prin tf(%c,myHaffTreec.ch); c=2* n-1;con ti nue;prin tf(n);void Caozuo_T(i nt n)int i;prin tf(word equalleftchild rightchild prentsn);for(i=1;i=2* n-1;i+) prin tf(%c %d %d %d %dn,myHaf1Treei.ch,myHaf1Treei.weight,myHaffTreei.lchild,myHaf fTreei.rchild,myHaffTreei. paren t);mai n()int n;char char1; prin t()