赫夫曼课程设计

1、目目 录录前言前言.1 1正文正文.1 11.1 课程设计的教学目的和任务 .11.2 课程设计的主要内容 .11.3 课程设计报告的要求.22.1.问题描述及基本要求 .22.2. 算法思想 .22.3 模块划分 .22.3.1 构造赫夫曼树.22.3.2 赫夫曼编码(huffmancode).32.4. 数据结构 .52.5. 算法的时空分析 .52.6 测试数据 .62.7. 测试情况 .6总总 结结.7 7参考文献：参考文献：.7 7附附 录录.9 9塔里木大学信息工程学院课程设计第 1 页 共 14 页前言前言赫夫曼编码(Huffman Coding)是一种编码方式，赫夫曼编码是可变

2、字长编码(VLC)的一种。赫夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。赫夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。赫夫曼编码的应用很广泛，利用赫夫曼树求地的二进制编码称为赫夫曼编码。赫夫曼树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为对应的编码，这就是赫夫曼编码。我们在对一些问题进行求解时，会发现有些问题很难找到规律，或者根本无规

3、律可寻。对于这样的问题，可以利用计算机运算速度快的特点，先搜索查找所有可能出现的情况，再根据题目条件从所有可能的情况中，删除那些不符合条件的解。由赫夫曼算法的定义可知，初始森林中共有 n 棵只含有根结点的二叉树。算法的的第二步是：算法的的第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树，每合并一次，森林中就减少一棵树，产生一个新结点。则要进行 n-1 次合并，所以共产生 n-1 个新结点。由此可知，最终求得的赫夫曼树中一共有 2n-1 个结点。其中， n 个结点是初始森林中的 n 个孤立结点。并且赫夫曼树中没有度数为 1 的分支的结点。采用赫夫曼编码方案，即应用赫夫曼树

4、构造使电文的编码总长最短的编码方案。正文正文1.1 课程设计的教学目的和任务(1) 使学生进一步理解和掌握所学的各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。(2) 使学生初步掌握软件开发过程的问题分析、设计、编码、测试等基本方法和基本技能。(3) 使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。(4) 使学生能用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。1.2 课程设计的主要内容(1) 问题分析和任务定义。根据题目的要求，充分地分析和理解问题，明确问题要求做什么？限制条件是什么？(

5、2) 逻辑设计。对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明） ，各个主要模块的算法，并画出模块之间的调用关系图。(3) 物理设计。定义相应的存储结构并写出各函数的伪代码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。(4)程序编码

6、。把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚。(5) 程序调试与测试。塔里木大学信息工程学院课程设计第 2 页 共 14 页采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。(6) 结果分析。程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。(7) 撰写课程设计报告。1.3 课程设计报告的要求课程设计报告要求规范书写。应当包括如下内容： 问题描述：描述

7、要求编程解决的问题。 基本要求：给出程序要达到的具体的要求。 测试数据：设计测试数据，或具体给出测试数据。要求测试数据能全面地测试所设计程序的功能。 算法思想：描述解决相应问题算法的设计思想。 模块划分：描述所设计程序的各个模块（即函数）功能。 数据结构：给出所使用的基本抽象数据类型，所定义的具体问题的数据类型，以及新定义的抽象数据类型。 源程序：给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参数的含义和函数返回值的含义。 测试情况：给出程序的测试情况，并分析运行结果。 算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；经验和体会等。 参考文献

8、：列出参考的相关资料和书籍。2.1.问题描述及基本要求利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本，试设计一个赫夫曼编码系统。从键盘输入一段报文（如what did you do that made you so happy） ，输出这段报文的赫夫曼编码。2.2. 算法思想赫夫曼编码是根据可变长最佳编码定理，应用赫夫曼算法而产生的一种编码，是消除编码冗余度最常用的方法。它的平均码字长度在具有相同输入概率集合的前提下，比其它任何一种可译码都小，因此，也常被称为紧凑码。将输入的字符串统计其个数算出百分率，最为它的权值，然后将各权值创建赫夫曼树，计算出对应的编码。通过

9、译码字符串，从根部出发，按字符0和1确定找左右孩子。2.3 模块划分2.3.1 构造赫夫曼树给定 n 个实数 w1，w2， ，wn（n） ，求一个具有 n 个结点的二叉数，使其带权路径长度最小。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为 0 层，叶结点到根结点的路径长度为叶结点的层数） 。树的带权路径长度记为 WPL=(W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N 个权值 Wi(i=1,2,.n)构成一棵有N 个叶结点的二叉树，相应的叶结点的路径长度为 Li(i=1,2,.n)。可以证明赫夫曼树的WPL 是最小的。(1) 根据与 n 个权值

10、w1,w2wn对应的 n 个结点构成具有 n 棵二叉树的森林 F=T1,T2Tn,其中第 i 棵二叉树 Ti(1 i n)都只有一个权值为 wi 的根结点，其左、右子树均为空塔里木大学信息工程学院课程设计第 3 页 共 14 页(2) 在森林 F 中选出两棵根结点的权值最小的树作为一棵新树的左、右子树，且置新树的根结点的权值为其左、右子树上根结点权值之和(3) 从 F 中删除构成新树的那两棵，同时把新树加入 F 中(4) 重复第(2)和第(3)步，直到 F 中只含有一棵为止，此树便为赫夫曼树void CreatHFMTree(HFMTree *HT,int count)/创建赫夫曼树int i

11、;HFMTree p,HT1,HT2; /HT1，HT2 分别存放权值最小和次小的节点的位置p=*HT=(HFMTree)malloc(sizeof(HFMNode);p-next=p-LChild=p-RChild=p-Parent=NULL; /初始化赫夫曼链表且有 2n-1个节点for(i=1;inext=(HFMTree)malloc(sizeof(HFMNode); p=p-next; p-next=p-LChild=p-RChild=p-Parent=NULL; for(i=0,p=*HT;iweight=counti; p=p-next; for(i=n;iParent=HT2-

12、Parent=p; p-LChild=HT1; p-RChild=HT2;p-weight=HT1-weight+HT2-weight;/将两个节点的权值相加存入一个节点 p=p-next; /p 指向下一个没有存储权值的节点 2.3.2 赫夫曼编码(huffmancode)1 根据最优二叉树构造赫夫曼编码，利用赫夫曼树很容易求出给定字符集及其概率(或频度)分布的最优前缀码。赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。该技术一般可将数据文件压缩掉 20至 90，其压缩效率取决于被压缩文件的特征。（1）用字符 si作为叶子，counti做为叶子 si的权，构造一棵赫夫曼树，并将树中左分支

13、和右分支分别标记为 0 和 1；（2）将从根到叶子的路径上的标号依次相连，作为该叶子所表示字符的编码。该编码即为最优前缀码（也称赫夫曼编码） 。代码如下：void TotalCoding(char s,CodeNode HC,char code)/利用赫夫曼编码表对整个字符串进行编码 int i,j;code0=0; /编码数组初始化 for(i=0;si;i+) for(j=0;jn;j+) if(si=HCj.ch) strcpy(code+strlen(code),HCj.code+HCj.start);2 给定字符集的赫夫曼树生成后，求赫夫曼编码的具体实现过程是：依次以叶子 si塔里木

14、大学信息工程学院课程设计第 4 页 共 14 页(0in-1)为出发点，向上回溯至根为止。上溯时走左分支则生成代码 0，走右分支则生成代码 1。(1)由于生成的编码与要求的编码反序，将生成的代码先从后往前依次存放在一个临时向量中，并设一个指针 start 指示编码在该向量中的起始位置.(2)当某字符编码完成时，从临时向量的 start 处将编码复制到该字符相应的位串中即可。(3)因为字符集大小为 n，故变长编码的长度不会超过 n，加上一个结束符0 .2.3.3 建立赫夫曼表void HFMCode(HFMTree HT,CodeNode HC,char str)/从每个叶子节点开始，利用赫夫曼

15、树对每个字符进行编码，最终建立一个赫夫曼表int i;HFMTree q,p=HT;for(i=0;in;i+) /将字符存入赫夫曼编码结构体数组的字符单元中 HCi.ch=stri; HCi.coden-1=0; /初始化编码的最后一位 for(i=0;iParent;q=q-Parent) /判断 q 所指向的节点，左孩子置 0，右孩子置 1 if(q=q-Parent-LChild) HCi.code-HCi.start=0; else HCi.code-HCi.start=1; p=p-next; /判断下一个叶子节点 2.3.4 赫夫曼译码算法依次读人文件的二进制码，从赫夫曼树的根结

16、点(即 Tm-1)出发，若当前读人 0，则走向左孩子，否则走向右孩子。一旦到达某一叶子 T 时便译出相应的字符 H.ch。然后重新从根出发继续译码，直至文件结束。代码如下：void DeCoding(char code,HFMTree HT,char str,char s)/对赫夫曼编码进行解码，放入字符串 s 中int i,j,k=0;HFMTree root,p,q;for(root=HT;root-Parent;root=root-Parent); /用 root 指向赫夫曼树的根结点for(i=0,p=root;codei;i+) /从根结点开始按编码顺序访问树if(codei=0)

17、p=p-LChild; else p=p-RChild; if(p-LChild=NULL&p-RChild=NULL) /到根节点时将该节点对应的字符输出 for(j=0,q=HT;q!=p;q=q-next,j+); sk+=strj; p=root; /回溯到根结点 塔里木大学信息工程学院课程设计第 5 页 共 14 页sk=0; /解码完毕，在字符串最后一个单元存入02.4. 数据结构主要定义了两个结构体2.4.1 定义赫夫曼树节点结构体typedef struct node int weight;struct node *LChild,*RChild,*Parent; /分别

18、指向该节点的左孩子，右孩子，和双亲节点struct node *next; /指向建立的赫夫曼树的下一个节点HFMNode,*HFMTree;2.4.2 定义赫夫曼编码的结构体typedef struct char ch; /存储对应的字符char codeN+1; /存储对应字符的编码int start; /存储编码的起始位置CodeNode;2.4.3 各个函数间的关系如图：图图 2.12.1 各函数简的调用关系各函数简的调用关系2.5. 算法的时空分析时间复杂度：构造赫夫曼树:T(n)= O(n) 塔里木大学信息工程学院课程设计第 6 页 共 14 页建立赫夫曼表：T(n)=O(n2)

19、进行译码：T(n)= O(n) 赫夫曼编码 T(n)= O(n) 2.6 测试数据对下列给出的字符集数据建立赫夫曼树，并实现以下报文的编码和译码字符串：what did you do that made you so happy字符 空格 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 12.7. 测试情况2.7.1 编码首先在初始界面，选择编码，键盘中输入 1 如图 2.2

20、：图图 1 1 编译初始界面编译初始界面塔里木大学信息工程学院课程设计第 7 页 共 14 页图图 2 2 编码界面编码界面2.7.2 通过编码出来的密码文件解码最终的到的字符串，通过与原来的字符串对比，完全一样.说明编码解码成功。总总 结结通过该题目的设计过程,对数据结构以及二叉树的逻辑结构,存储结构的理解,对树的数据结构上基本运算的实现有所掌握,对课本中所学的各种数据结构进一步理解和掌握,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。完成所有的工作是非常困难和耗时的。在以后的学习中我会更加注意自己各个方面的能力的协调发展。在课程设计时我遇到了很多的问题，在老师的帮助，和对各

21、种资料的查阅中，将问题解决，培养了我自主动手，独立研究的能力，为今后在学习工作中能更好的发展打下了坚实的基础。参考参考文献：文献：1谭浩强编著.C+课程设计.北京：清华大学社，20042S.B.Lippman，J.Lajoie 著.潘爱民译.C+Primer（3rd Edition）中文版.北京：中国电力出版社，20023H.M.Deitel，Paul James Deitel 著.薛万鹏译.C+程序设计教程.北京：机械工业出版社，20004Stephen R.Savis 著.C+ For Dummies 4th edition，IDG Books Worldwide，Inc.，20025Ha

22、rvey M.Deitel .Jack W.Davidson 著.邱仲潘译.C+大学教程（第二版）.北京：电子工业出版社，20026James P.Cohoon.Jack W.Davidson 著.刘瑞挺等译.C+程序设计（第三版）.北京：电子工业出版社塔里木大学信息工程学院课程设计第 8 页 共 14 页7Decoder 编著.C/C+程序设计.北京：中国铁道出版社，20028Brian Overland 著.董梁等译.C+语言命令译解（第二版）.北京：机械工业出版社，20029 H.M.Deitel，Paul James Deitel 著.薛万鹏译.C/C+程序设计大全.北京：机械工业出版

23、社.199710Al Strevens,Clayton Walnum 著.林丽闽等译.标准 C+宝典.北京：电子工业出版社.2001 11Michael J.Young 著.Mastering Visual C+6.0 Sybex Inc.199912Leen Ammeraal 著.刘瑞挺等译.C+程序设计教程（第三版）.北京：zhongguo 铁道出版社，200313 吕凤翥著. C+语言程序设计.北方交通大学出版社，200314 袁启昌著.C+语言程序设计.清华大学出版社，200415 刘振安，刘燕君，孙忱 C+语言课程设计.机械工业出版社，200716 杨进才，沈显君，刘蓉编.C+语言程

24、序设计教程.清华大学出版社，200617 宋振会著. C+语言编程基础教程.清华大学出版社，2005塔里木大学信息工程学院课程设计第 9 页 共 14 页附附 录录#include#include#include#include#includetypedef struct /赫夫曼树的结构体char ch;int weight; /权值int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode;void Select(hfmtree &HT,int a,int *p1,int *p2) /Select 函数，选出 HT

25、树到 a 为止，权值最小且 parent 为 0 的 2 个节点int i,j,x,y;for(j=1;j=a;+j)if(HTj.parent=0)x=j;break;for(i=j+1;i=a;+i)if(HTi.weightHTx.weight&HTi.parent=0)x=i; /选出最小的节点for(j=1;j=a;+j)if(HTj.parent=0&x!=j)y=j;break;塔里木大学信息工程学院课程设计第 10 页 共 14 页for(i=j+1;i=a;+i)if(HTi.weighty)*p1=y;*p2=x;else*p1=x;*p2=y;void h

26、fmcoding(hfmtree &HT,hfmcode &HC,int n) /构建赫夫曼树 HT，并求出 n 个字符的赫夫曼编码 HCint i,start,c,f,m,w;int p1,p2;char *cd,z;if(n=1)return;m=2*n-1;HT=(hfmtree)malloc(m+1)*sizeof(htnode);for(i=1;i=n;+i) /初始化 n 个叶子结点printf(请输入第%d 字符信息和权值：,i);scanf(%c%d,&z,&w);while(getchar()!=n)continue;HTi.ch=z;HTi.

27、weight=w;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(;i=m;+i) /初始化其余的结点HTi.ch=0;HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;塔里木大学信息工程学院课程设计第 11 页 共 14 页for(i=n+1;i=m;+i) /建立赫夫曼树Select(HT,i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.w

28、eight;HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;+i) /给 n 个字符编码start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);int main()char code

29、100,h100,hl100;int n,i,j,k,l;ifstream input_file; /文件输入输出流ofstream output_file;char choice,str100;hfmtree HT;hfmcode HC;coutn;cout 计算机（3）班 Q07620307 XXXn;while(choice!=Q&choice!=q) /当 choice 的值不为 q 且不为Q 时循环cout *赫夫曼编码/译码器*n; cout I.Init E.Encoding D.Decoding Q.Exitn;塔里木大学信息工程学院课程设计第 12 页 共 14 页

30、coutchoice; if(choice=I|choice=i) /初始化赫夫曼树coutn;hfmcoding(HT,HC,n);for(i=1;i=n;+i)coutHTi.ch:HCiendl;output_file.open(hfmTree.txt);if(!output_file)coutcant oen file!endl;return 1;for(i=1;i=n;i+)output_file(HTi.chHCi);output_file.close();cout赫夫曼树已经创建完毕，并且已经放入 hfmTree.txt 文件中!endl; else if(choice=E|choice=e) /进行编码，并将字符放入ToBeTran.txt，码值放入 CodeFile.txt 中printf(请输入字符：);gets(str);output_file.open(ToBeTran.txt);if(!output_file)coutcant oen file!endl;return 1;output_filestrendl;output_file.close();output_file.open(CodeFile.txt);if(!output_f