10信计刘旭东-哈夫曼编码专业课程设计.doc

宜春学院本科课程设计阐明书学 院： 数计学院 专业年级： 10信息与计算科学 课 程： 信息论与编码课程设计 设计题目： Huffman编码设计与实现 指引教师： 赵志芳 12月学生姓名： 刘旭东 学 号：中文摘要哈夫曼编码是广泛用于数据文献压缩十分有效编码办法。其压缩普通在20%90%之间。哈夫曼编码算法使用字符在文献中浮现频率表来建立一种用0,1串表达各字符最优表达方式。哈夫曼算法构造扩充二叉树称为哈夫曼编码树或哈夫曼树。固然，尚有编码和译码某些。本系统前端开发工具是Visual C+6.0。具备输入字符集大小及权值大小，构造哈夫曼树，并对顾客输入字符串进行编码以及译码尚有退出四种功能。本程序通过测试后，功能均能实现，运营稳定。核心词：哈夫曼树，编码，权值 英文摘要 Huffman coding is widely used in data file compression coding method is very effective. The compression usually between 20% 90% in. Huffman use of the character encoding algorithm in the document appeared in frequency table with 0 to build a string of optimal each character said means. The algorithms construction huffman extended binary tree called huffman coding tree or huffman tree. Of course，there are coding and decoding parts. This system the front-end development tools is Visual c + + 6.0. With input character set size and weitht size，structure tree huffman，and user input string coding and decoding and exit four functions. This procedure after testing，functions are realized，steady operation.目 录引言31、问题分析42、算法设计53、算法实现63.1流程图63.2程序代码73.3调试成果103.3.1例题57测试成果103.3.2习题5-12调试成果114、结论135、参照文献13引言哈夫曼在上世纪五十年代初就提出这种编码时，依照字符浮现概率来构造平均长度最短编码。它是一种变长编码。哈夫曼编码应用广泛，如JPEG中就应用了哈夫曼编码。在编码中，若各码字长度严格按照码字所相应符号浮现概率大小逆序排列，则编码平均长度是最小。构造好哈夫曼树后，就可依照哈夫曼树进行编码。然而如何构造一棵哈夫曼树呢？最具备普通规律构造办法就是哈夫曼算法。字符依照其浮现概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到相应码值。只要使用同一棵哈夫曼树，就可把编码还原成本来那组字符。显然哈夫曼编码是前缀编码，即任一种字符编码都不是另一种字符编码前缀，否则，编码就不能进行翻译。运用哈夫曼算法编码和译码功能，重复地显示并解决如下项目，即构造哈夫曼树，编码及译码几项功能，直到选取退出为止。本次设计就是为这样一种哈夫曼编/译码器。哈夫曼编码因此能产生较短码文，是由于哈夫曼树具备最小加权途径长度二叉树。如果叶结点权值正好是某个需编码文本中各字符浮现次数，则编码后文本长度就是该哈夫曼树加权途径长度。译码过程为自做向右逐个扫描码文，并从哈夫曼树根开始，将扫到二进制位串中相邻位与哈夫曼树上标0，1相匹配，以拟定一条从根到叶子结点途径，一旦到达叶子，则译出了一种字符。再回到树根，从二进位串下一位开始继续译码。软件运营环境及开发工具是Visual C+6.0。 1、问题分析 为了建立哈夫曼树以及实现哈夫曼编码以及译码，因而咱们选取了结点构造体，运用这一构造体，咱们定义了一种构造体数组和一种树根指针，数组用来纪录输入数据多少，树根指针用来连接哈夫曼树。从程序中可以看到使用哈夫曼算法构造哈夫曼树过程，是从n棵知识一种根结点树构成森林开始。在算法执行中，哈夫曼树是由若干棵树构成森林，通过不断地合伙树，最后得到一棵哈夫曼树。为了便于实现哈夫曼树建树运算，定义程序哈夫曼树类HfmTree，它涉及如下两个私有数据成员tree和weight：其中，tree是一种二叉树BinaryTree类型对象，是一棵哈夫曼树，weight是tree所代表哈夫曼树权值。在本课程设计中使用函数Huffman（）。构造哈夫曼树算法：（1） 用给定一组权值W1,W2,Wn,生成一种有n棵树构成森林F=T1,T2,Tn,其中每棵二叉树Ti只有一种结点，即权值为 Wi根结点（也是叶子结点）；（2） 从F中选取两棵根结点权值最小树，作为新树根左右子树，新树根权值是左右子树根结点权值之和；（3） 从F中删除这两棵树，另将新二叉树加入F中；（4） 重复（2）和（3），直到F中只包括一棵树为止。本次程序设计是哈夫曼编码。由建立好哈夫曼树来进行编码，构造一种CodeNode构造体用来存储编码字符及各字符编码，从根结点开始，左走一步为0，右走一步为1，并将编码成果存入文献中，译码过程为从文献中逐个扫描码文，并从哈夫曼树根开始，将扫到二进制位串中相邻位与哈夫曼树上标0，1相匹配，以拟定一条从根到叶子结点途径，一旦到达叶子，则译出了一种字符。再回到树根从二进位串下一位开始继续译码。使用transcode()函数即可完毕。 2、算法设计Huffman编码是一种可变长编码方式，是由美国数学家David Huffman创立，是二叉树一种特殊转化形式。编码原理是：将使用次数多代码转换成长度较短代码，而使用次数少可以使用较长编码，并且保持编码唯一可解性。Huffman算法最主线原则是：合计(字符记录数字*字符编码长度)为最小，也就是权值(字符记录数字*字符编码长度)和最小。Huffman树是二叉树一种特殊转化形式。如下是构件Huffman树例子：例如有如下数据， ABFACGCAHGBBAACECDFGFAAEABBB先进行记录A(8) B(6) C(4) D(1) E(2) F(3) G(3) H(1) 括号里面是记录次数生成Huffman树：每次取最小那两个节点(node)合并成一种节点(node)，并且将合计数值相加作为新接点合计数值，最顶层是根节点(root) 注：列表中最小节点是指涉及合并了节点在内所有节点，已经合并节点不在列表。3、算法实现3.1流程图：3.2程序代码：#include#include#define N 15 /*最大符号数*/#define M 2*N-1 /*编码树最大节点数*/typedef struct /*编码树节点*/ float weight; int parent,lchild,rchild;HTNode;typedef structchar data;float weight;char codeN;HTCode;void Init(HTCode hc,int *n)int i； printf(n input n=)； /*输入n大小*/scanf(%d,&(*n)； /*取n地址值*/fflush(stdin)； /*stdin是默认输入流文献,相应输入缓冲区 fflush(stdin)作用就是清空输入缓冲区,避免缓冲区内残存读取函数无法取走内容!*/printf(n input %d character n,*n)； /*输入各个字符代号*/for(i=1;i=*n;i+) /*从1到n个*/printf(n the %d character is:,i)； /*输出显示信息提示*/scanf(%c,&(hci.data)； /*取hci地址所相应data值*/fflush(stdin)； /*同上*/for(i=1;i=*n;i+) /*从1到n输入它们各自所相应概率大小，即重量weight*/printf(n the %d character weight is:,i)； /*输出显示信息提示*/scanf(%f,&(hci.weight)； /*取hci地址所相应weight值*/void Select(HTNode ht,int k,int *s1,int *s2) /*定义Select选取函数*/ int i； /*定义一种整形数i*/ for(i=1;i=k;i+) if(hti.parent=0) /*i从1开始到k，如果i没有父节点，则把i赋给*s1，且跳出循环*/ *s1=i；break;for(i=1;i=k;i+) /*找任意不是第一次节点*/if(hti.parent=0&hti.weightht*s1.weight) /*i再从1开始，如果此时i没有父节点，且其重量不大于*s1重量，就把当前i赋给*s1*/*s1=i;for(i=1;i=k;i+) /*i再从1开始，如果此时i没有父节点，并且i不等于*s1值，则把当前i赋给*s2。跳出循环*/if(hti.parent=0&i!=*s1) *s2=i;break;for(i=1;i=k;i+)if(hti.parent=0&i!=*s1&hti.weightht*s2.weight)*s2=i;/*i再从1开始，如果此时i没有父节点，并且i不等于*s1值，其重量也不大于*s2重量，则把当前i赋给*s2。*/printf(n this is *s1:%dn,*s1)； /*输出*s1与*s2所指内容*/printf(n this is *s2:%dn,*s2);void HuffmanCoding(HTNode ht,HTCode hc,int n)char cdN； int i,m,c,f,s1,s2,start;m=2*n-1;for(i=1;i=m;i+) /*初始化节点，其中1n个原始节点具备概率值*/if(i=n)hti.weight=hci.weight;else hti.weight=0.0;hti.parent=hti.lchild=hti.rchild=0;for(i=n+1;i=m;i+) /*构造二叉树*/Select(ht,i-1,&s1,&s2)； /*选取最小两个概率节点，并且是没有编码过*/hts1.parent=i;hts2.parent=i;hti.lchild=s1;hti.rchild=s2;hti.weight=hts1.weight+hts2.weight;for(i=1;i=m;i+) /*调试二叉树*/printf(n the %d charactor weight is %f:,i,hti.weight);printf(n the %d charactor lchild is %d:,i,hti.lchild);printf(n the %d charactor rchild is %d:,i,hti.rchild);printf(n the %d charactor parent is %d:,i,hti.parent);for(i=0;iN;i+) /*编码初始化*/cdi= ;cdn-1=0;for(i=1;i=n;i+)start=n-1;for(c=i,f=hti.parent;f;c=f,f=htf.parent) /*遍历父节点*/if(htf.lchild=c)cd-start=1;else cd-start=0； /*提取码字*/strcpy(hci.code,&cdstart);void main()int i,n;float l=0.0； /*初始化l*/float arg,*point=&arg； /*定义指针类型平均码长arg*/HTNode htM+1； /*定义HTNode数组*/HTCode hcN+1； /*定义HTNode数组*/Init(hc,&n)； /*调用Init函数*/HuffmanCoding(ht,hc,n)； /*调用Huffman函数*/for(i=1;i=n;i+) /*从1到n输出字符代码以及编码*/printf(n the code of %c is:%s,hci.data,hci.code)；for(i=1;i=n;i+) /*每遍历一次求一次平均码长l*/ l+=strlen(hci.code)*hci.weight;printf(n the average length of the huffman coding is %f,l);3.3调试成果：1.测试成果：2.调试成果：4、结论：课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力重要环节,是对学生实际工作能力详细训练和考察过程. 通过实验更好掌握了哈夫曼编码，并对哈夫曼编码有了深一步理解。这次课程设计，通过用for多重循环，舍弃多余循环，提高了程序运营效率。在编写这个程序过程中，咱们复习了之前学基本语法，哈弗曼树最小途径求取，哈弗曼编码应用范畴，程序构造算法等一系列问题它使我对程序算法变化了看法。由于算法推敲局限性，使程序调试时费时不少；更好掌握了对程序调试，并从中感受到调试巨大力量，特别是当程序不能实现预想成果时。5、参照文献： 1.曹雪虹、张宗橙，信息论与编码，北京：清华大学出版社出版， 2.严蔚敏，吴伟民，数据构造，北京：清华大学出版出版，1997.4