课程设计哈夫曼编码与译码

1、哈夫曼编码与译码学生姓名： 指导老师：摘 要 本课程设计主要解决的是利用哈夫曼树生成的哈夫曼编码进行字符串的加密和解密，并将加密的编码写入文件。在此课程设计中，系统开发平台为Windows XP，程序设计语言采用面向过程的高级语言C和面向对象的高级语言C+，程序运行平台为Visual C+ 6.0。在程序设计中，采用了结构化与面向过程两种解决问题的方法。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在商业中解决实际问题。关键词 哈夫曼树，编码，译码，文件操作，C，C+； 1 引 言1.1 课题背景随着信息时代的到来，各种信息日益丰富，信息迅速膨胀，对信息管理的工作量也日益

2、增大。在信息化未到来之前，信息的存储编码也变得尤为重要，公司之间的信息需要编码，用户个人数据需要编码，都需要占用很大的空间，所以一个好的、高效的编码译码算法是十分重要的。好的加密算法不仅可以降低管理方的工作量和存储量，还可以对用户的信息进行高效的管理，同时使在用中可以避免不必要的麻烦。 数据结构是指相互之间存在一定关系的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。数据的逻辑结构(logical structure)是指数据元素之间逻辑关系的整体。所谓逻辑关系是指数据元素之间的关联方式或邻接关系。根据数据元素之间逻辑关系的不同，数据结构分为四类：集合、线性结构、树结构、图结构

3、。数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式。为了区别于数据的存储结构，常常将数据的逻辑结构称为数据结构。数据的存储结构(storage structure)又称为物理结构，是数据及其逻辑结构在计算机中的表示，换言之，存储结构除了数据元素之外，必须隐式或显示地存储数据元素之间的逻辑关系。通常有两种存储结构：顺序存储结构和链接存储结构。树是一种在实际应用中被广泛使用的数据结构。它是由同一类型的记录构成的集合。哈夫曼树是树的一种子类型，又称最优树，是一类带权路径最短的树，利用哈夫曼树可以得到合适的字符编码，这样我们既可以对数据加密，也可以实现高效的存储信息。因此哈夫曼编码是

4、一种常用的编码方式。1.2 课程设计目的哈夫曼编码与译码系统是为了实现信息的高效存储与管理、加密、解密而设计的。通过建立一个有效，低存储量，易于管理的编码译码系统，使得企业对信息管理更加高效、准确，更加科学化和正规化，降低企业对信息管理的难度。本课程设计主要是用数据结构和文件实现的，通过程序的编写、调试和运行可以进一步掌握数据结构及算法的程序实现的基本方法。理解对数据结构的基本知识及应用，同时加深对哈夫曼树的运用及理解。本课程设计是利用哈夫曼编码实现对字符串的加密、解密和低存储量存储，程序实现哈夫曼树的建立和哈夫曼编码的生成，实现字符串的快速编码、解密和保存。掌握哈夫曼编码的工作原理，熟悉建立

5、哈夫曼树、利用哈夫曼编码进行实际编码、解码等功能的实现，同时加深对文件的操作原理。 课程设计内容本课程设计主要是采用哈夫曼编码对字符串的编码、解码，同时实现地存储量要求。在设计的过程中，共用到两种数据元素，第一种是哈夫曼树建立是用到树的结构，树节点信息包括父节点、左子树节点、右子树节点以及该节点的权值其信息如图1-1所示，第二种是在存储个字符对应编码时用到的结构，其中包括字符、字符密文以及其长度，如图1-2所示：树节点信息父节点左子树节点右子树节点权值图1-1 树节点数据元素 编码信息字符编码编码长度 图1-2 每个字符密文数据元素程序功能是实现对用户输入信息的编码与解码，并存入文件中，具体如

6、图1-3所示：对用户输入字符串编码解码将编码存入文件保存得到哈夫曼编码利用字符和权值建立哈夫曼树输入字符串或字符及权值信息哈夫曼编码与译码图1-3 功能模块图2 设计思路与方案2.1 设计思路C语言是结构化和模块化的语言，它是面向过程的。在处理较小规模的程序时，程序员用C语言还比较得心应手。C+是由C语言发展而来的，与C语言兼容。用C语言编写的程序基本上可以不加修改地用于C+。从C+的名字可以看出它是C的超集。C+既可以用于面向过程的结构化程序设计，又可用于面向对象的程序设计，是一种功能强大的混合型的程序设计语言。C+对C的“增强”，表现在两个方面： （1）在原来面向过程的机制基础上，对C语言

7、的功能做了不少扩充。 （2）增加了面向对象的机制。作为一种编程约定，C+程序员倾向于只有当所有的成员均为公共时才使用结构。结构（struct）是一种特殊的类，它的特殊之处在于其成员都是公共的（除非另作声明）。C+程序员只有在所有成员都是公共的时候才会使用结构。在计算机中进行编码的方法有很多种，此文选择哈弗曼编码。哈弗曼编码由哈弗曼树得到，所以我们要选择存储树的数据结构，为了高效的产生哈弗曼编码，树的存储采用三叉链表的方式，同时增加一个选项以存储各个树结点的权值。同时将得到的密文存储到文件中，以便我们进行查看。2.2 设计方案通过分析可知，本课程设计主要功能是通过哈弗曼树得到哈弗曼编码，利用得到

8、的哈弗曼编码对字符串进行编码与译码，并存入文件便于查看。由于构造哈弗曼树和根据哈弗曼树得到编码时要经常对节点的父结点，左右子树结点进行访问，所以采用三叉链表的方式存储树结点，同时在该结点信息中还需要增加一个选项存储结点的权值。其次，为了解决得到的哈弗曼编码的存储问题，再建立一个结构体，用于存储每个字符所对应编码及编码长度，编码的存储简化了编码与译码的操作。同时，将得到的密文存储到文件中，便于我们查看。定义一个结构体HTNode将树结点，父结点，左右子树结点及该结点的权值联系在一起，便于操作。具体定义如下：typedef struct/建立树结点 int weight;int parent,lc

9、hild,rchild;HTNode; 定义一个结构体CodeNode将各个字符对应编码及编码的长度联系在一起，便于操作。具体定义如下：typedef struct/建立每个编码的结构体char ch;char bits10;int len;CodeNode;同时，为了操作的方便，我们做如下处理：typedef HTNode HafumanTreem+1;/重命名HTNodetypedef CodeNode HafumanCoden+1;/重命名CodeNode3 详细设计3.1 menu菜单功能Menu菜单主要用于让用户选择何种方式构造哈弗曼树，此时需要用户输入0或者1来进行控制。该段代码位

10、于viod main()函数中。其代码如下：printf( - n);printf( 欢迎使用编码译码系统n);printf( - n);printf(请输入获得权值的方法,输入1表示自己输入每个节点的权值,输入0表示将每个字符在输入字符串中出现的次数作为其权值:);scanf(%d,&method); /通过用户的输入来判断使用何种方式其流程图如图3-1所示：开始第一种方式编码第二种方式编码输入错误 图3-1 menu菜单3.2 int counttotal(char *s,int quan,char str)函数当用户选择通过输入的字符串自动获取权值（统计出现的字符种数以及每种字符出现的次

11、数， 将该种字符出现的次数作为它的权值）时，main函数将会调用该函数计算各个节点的权值，将相应的字符存入str字符数组，同时该字符对应的权值存入quan数组中。算法流程图如图3-1：i+;是j+;strj=i+96; quanj=quantempi;结束i27?quantempi=0?k=getstri-96;quantempk+( quantemp为int型数组开始值都为0)i+;i=1,j=0判断getstri是否为26个小写字母开始获得输入的字符串getstr，i=0。i+;否否是否是图3-1计算字符权值及字符种类算说明：counttotal（）函数代码见附录。 3.3 void se

12、lectmin()函数 该函数的作用是在所有给定权值的结点中选出权值最小的两个结点并返回，用于构造哈弗曼树。代码如下： void selectmin(HafumanTree HT,int k,int *s1,int*s2)/选择权值最小的两个int i,j;int min=9999;/声明一个int类型的数值min，赋个较大的输给它for(i=1;i=k;i+)/选择权值最小的一个节点（且该节点无父节点）if(HTi.weightmin)&(HTi.parent=0)j=i;min=HTi.weight;*s1=j;min=9999;for(i=1;i=k;i+)if(HTi.weightmi

13、n)&(HTi.parent=0)&(i!=*s1)/选择权值最小的一个节点（且该节点无父节点） j=i;min=HTi.weight;*s2=j;说明:本函数返回两个权值最小的结点信息分别存储在s1和s2中，为下一步构造哈弗曼树做准备。3.4 void creathafumantree( )函数 Creathafumantree（）函数用于构造一棵哈夫曼树，构造哈弗曼树的步骤为：根据给定n个权值构成n棵二叉树的集合F，其中每棵二叉树Ti中只有一个权值为Wi的根结点，其左右字数均为空。在F中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上

14、根结点权值之和。在F中删除这两棵树，同时将新得到的二叉树加入F中。重复步骤（2）和（3），直到F只含一棵树为止，得到的树便是哈夫曼树。 其算法流程图如图3-3所示：选择权值最小的两个节点将下标赋给s1,s2.HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;i+结束是i=num+1i=2*num-1?HTi.weight=quanii=1;(num为字符的种类)开始将所有的几点的父节点和子节点权值赋成0i=num否是否图 3-3 函数creathafumantre

15、e( )的算法流程图说明：其源代码见附录3.5 void Hafumanencode( )函数Hafumanencode( )函数是根据creathafumantree( )函数构造的哈弗曼树得到哈弗曼编码。根据每个字符在哈夫曼树中的位置来编译每个字符的0、1密文代码，从叶节点判断该叶节点是其父节点的左右字左字为0，右子为1，在判断父节点是上级父节点的左右子直至根节点，将生成的0、1字符串按所表示的字符倒序存入HC相应的字符的bins数组，代码如下：void Hafumanencode(HafumanTree HT,HafumanCode HC)int c,p,i;char cdn;/临时数组

16、用于记录字符在哈夫曼树的位置int start;cdnum=0;/给cd赋个结束符for(i=1;i0)/根据节点是其父节点的左右子来记录它的位置cd-start=(HTp.lchild=c)?0:1;c=p;/将父节点转为子节点strcpy(HCi.bits,&cdstart);/将得到的0、1字串存入结构体HCprintf(%c:%sn,HCi.ch,HCi.bits);HCi.len=num-start;/求每个字符0、1编码长度3.6 void codenum( )函数codenum（）函数主要用于对输入字符串进行编码。根据Hafumanencode( )函数得到的编码，将字符串转化为

17、密文，为了方便查看，最后会将得到的密文存入文件code.txt中。该函数由于要涉及到文件操作，故定义了文件流指针fp。该函数的算法流程图如图3-4所示：图3-4 编码算法否否是HTc.parent 0？cd-start=(HTp.lchild=c)?0:1; c= HTc.parent;i+start=num; c=i开始i=0;cdnum=0;将stri的值依次赋给HCi.chi=num？strcpy(HCi.bits,&cdstart); HCi.len=num-start;i+结束否打开code.txt文件,获得字符串str指针，i=0；HCi.ch=*str?i=num？将HCi.bi

18、tsj存进文件是否是是否3.7 char *decode( )函数文件夹中，一个一个字符的读出那串0、1代码赋给一个临时字符串cd，用该字符串与每个字符的HCi.bins密文比较，直到与一个字符的密文相同时，译出该字符，将字符存放在临时字符数组tempstr中，清空临时字符串继续读取0、1代码进行翻译，直至文件密文结束为止。于是就得到了原先被加密的那串字符串。该函数的算法流程图如图3-5所示：strk=HCj.ch;cjs=1;k+;strk=0;break;j+strcmp(HCj.bits,cd)=0j=numi+ 结束开始(inum)&(cjs=0)&(!feof(fp)打开文件夹cod

19、e.txt, cjs=0, i=0!feof(fp)cdi= ;cdi+1=0;cdi=fgetc(fp);j=1;图3-5 译码4 运行结果(1) 运行程序，菜单如图4-1：图 4-1 功能菜单(2) 若要自己输入每个字符的权值，输入1后回车，如图4-2：图4-2 菜单状态输入1(选择自己输入权值)(3) 在(2)之后需要输入字符的种类数，这里假定有三种，输入3回车，图4-3：图4-3 输入字符出现的种类数(4) 在(3)之后需要输入第一个字符和该字符的权值，假定输入字符a和权值3，回车会提示输入第二字符和其权值，输入字符b和权值5，回车，继续提示输入第三字符和其权值，输入字符c和权值7，确

20、认回车，如图4-3：图4-4 输入字符和字符的权值 (5) 在(4)确认之后哈夫曼树已经构造好，并且编码已经得到，这时会输出各个字符、相应权值及该字符的哈夫曼编码，同时会提示输入要按照得到的哈夫曼编码进行编码的字符串，如图4-5：图4-5 各字符的哈夫曼编码 (6) 在(5)之后需要输入要进行编码的字符串，假定输入字符串abcbcbaa，如图4-6： 图4-6 输入要编码的字符串 (7) 在(6)之后确认输入，程序会将得到的编码输出，并将编码写入文件code.txt(当前工程工作路径下)，写入后会提示写入文件成功，同时程序会根据每个字符的哈夫曼编码和code.txt文件中的字符串编码译码，并输

21、出，最后会提示是否要继续运行该程序。如图4-7：图4-7 编码译码及写入文件 (8) 在(7)之后输入1后回车，继续运行该编码译码程序，同时演示第二种编码译码方式(即不主动输入权值，将该种字符出现的次数作为它的权值)，输入0回车，如图4-8：图4-8 继续运行并选择第二种方式 (9) 在(8)之后确认回车，系统会提示输入将要编码的字符串，假定这里输入字符串asddcxxsad，如图4-9：图4-9 输入要进行编码的字符串 (10) 在(9)之后确认回车，系统将对输入的字符串进行统计，得到输入字符的种类并计算出各字符的权值，同时根据得到的权值构造哈夫曼树并得到哈夫曼编码，最后会根据哈夫曼编码对字

22、符串进行编码，同时会将编码写入文件，译码输出。如图4-10：图4-10 编码译码及写入文件 (11) 在程序运行后系统会提示输入0或1选择编码方式，若输入其它的数值，系统会提示错误输入，如图4-11：图4-11 错误输入 (12) 在程序运行后系统会提示是否需要继续进行编码译码，输入0则推出系统，如图4-12：图4-12 退出系统5 结束语数据结构课程设计和现代计算机技术的实际应用相结合，是我们在本学期学完理论课程之后对自己学习能力的一次很好的检验，从开始的算法思路到运行调试后的可执行程序，都是一个很好的学习和锻炼的过程。既可以使我们巩固了原有的理论知识，培养了我们灵活运用和组合集成所学过知识

23、及技能来分析、解决实际问题的能力，也可以使我们体会到自身知识和能力能在实际中的应用和发挥。不但可以激发创新意识，还可以开发创造能力、培养沟通能力。这次数据结构课程设计的时间里虽然时间有限，但确实使我受益非浅。通过实践课程设计我丰富了编译工具操作经验，更加深了对C和C+语言的了解，熟悉了其环境，更增强了对哈夫曼树的理解与运用。而且，在完成本课程设计的过程中，也充满磨练了我的意志，锻炼了我的耐心、认真。在实践的过程中，需要不倦的查阅资料，甚至需要求助于老师、同学。要善于思考，多动手。我深知，独立完成这样一项任务需要克服许多困难。总之，数据结构课程设计让我受益良多，我会好好珍惜像这种难得的机会，努力

24、学习知识。也感谢帮助了我的老师、同学。参考文献1 严蔚敏，吴伟民.数据结构（C语言版）. 2 3 谭浩强，C+程序设计（第一版）.4 谭浩强，C程序设计（第三版）.附 录 ：源程序/ 程序名称：哈夫曼编码与译码/ 程序 / 最后修改日期：2012-6-27#include #include #include using namespace std;#define n 100/叶节点的个数小等于n#define m 2*n-1/总结点的个数为m=2*n-1int num;/定义一个全局变量用于存放字符种类个数typedef struct /结构体用于存放树节点包括节点的父节点、左子、右子以及权值

25、 int weight;int parent,lchild,rchild;HTNode;typedef HTNode HafumanTreem+1;/重命名HTNode HTtypedef struct/结构体由于存放每个字符的密文和长度char ch;char bits10;int len;CodeNode;typedef CodeNode HafumanCoden+1;/重命名CodeNode HCint main(int argc, char* argv) int quan27,k=1,length,count=1,total,method;/声明一个数组用以存放26字符的权值,leng

26、th表示要加密字符串的长度/count用于控制输入字符和权值的次数,total用于循环控制,k用于控制解密，加密的次数/method用于控制使用何种方法进行输入权值char getstr300,str27;/声明两个字符串数组一个用于存输入,一个由于存放输入中含有的字符char *s; /声明一个char型指针用于指向字符HafumanTree HT;HafumanCode HC; /声明m+1个树节点HafumanTree HT; /声明n+1个codeint counttotal(char *s,int quan,char str);/声明需要调用的函数void creathafumant

27、ree(HafumanTree HT,HafumanCode HC,int quan,char str);void Hafumanencode(HafumanTree HT,HafumanCode HC);void codenum(HafumanCode HC,char *str);char *decode(HafumanCode HC);while(k)printf( - n);printf( 欢迎使用编码译码系统n);printf( - n);printf(请输入获得权值的方法,输入1表示自己输入每个节点的权值,输入0表示将每个字符在输入字符串中出现的次数作为其权值:);scanf(%d,

28、&method);if(method=0) printf(请输入要编码的字符串(请输入小写字母):);gets(getstr); /scanf(%s,&getstr); /获得输入的字符串num=counttotal(getstr,quan,str);/统计字符串中含有字符种类个数creathafumantree(HT,HC,quan,str); /根据字符权值构建哈夫曼树Hafumanencode(HT,HC);/根据哈夫曼树确定每个字符的codecodenum(HC,getstr);/将字符串译码存入文件夹s=decode(HC);/将暗文解码printf(解密为：n);printf(%s

29、n,s);printf(是否想继续编码、解码,是输入1回车,否输入0回车:);scanf(%d,&k);else if(method=1)total=1; /每次都要将其清零，以达到控制循环的效果printf(请输入要编码字符所出现的种类数:);scanf(%d,&length);for(count=1;countstrtotalquantotal;total+;num=length;creathafumantree(HT,HC,quan,str);/根据字符权值构建哈夫曼树Hafumanencode(HT,HC);/根据哈夫曼树确定每个字符的codeprintf(请输入要编码的字符串:);c

30、ingetstr;codenum(HC,getstr);/将字符串译码存入文件夹s=decode(HC);/将暗文解码printf(解密为：n);printf(%sn,s);printf(是否想继续编码、解码,是输入1回车,否输入0回车:n);scanf(%d,&k);elseprintf(错误输入!n);exit(0);system(pause);return 0;int counttotal(char *s,int quan,char str)/计算字符串中字符权值char *p;int i,j,k,quantemp27; for(i=1;i=a&*p=z)/判断字符是否为26字母k=*p

31、-96;/看是26个字符中的哪个字符quantempk+;/字符权值加1j=0;for(i=1,j=0;i27;i+)if(quantempi!=0)j+;/用于统计字符种类个数strj=i+96;/str按字母表顺序存储出现过的字符quanj=quantempi;return j; /返回该数据给num赋值void selectmin(HafumanTree HT,int k,int *s1,int*s2)/选择权值最小的两个int i,j;int min=9999;/声明一个int类型的数值min，赋个较大的输给它for(i=1;i=k;i+)/选择权值最小的一个节点（且该节点无父节点）i

32、f(HTi.weightmin)&(HTi.parent=0)j=i;min=HTi.weight;*s1=j;min=9999;for(i=1;i=k;i+)if(HTi.weightmin)&(HTi.parent=0)&(i!=*s1)/选择权值最小的一个节点（且该节点无父节点） j=i;min=HTi.weight;*s2=j;/构建哈夫曼树void creathafumantree(HafumanTree HT,HafumanCode HC,int quan,char str) int i,s1,s2;for(i=1;i2*num-1;i+)/将所有的节点赋空HTi.lchild=0

33、;HTi.rchild=0;HTi.parent=0;HTi.weight=0;for(i=1;i=num;i+)/将num个字符的权值赋给num叶节点HTi.weight=quani;for(i=1;i=num;i+)/将num个字符赋给codenodeHCi.ch=stri;i=1;while(i=num) printf(字符为%c,权值为%dn,HCi.ch,quani);i+;/输出每个字符的及其权值for(i=num+1;i=2*num-1;i+)selectmin(HT,i-1,&s1,&s2);/选择两个权值最小的叶节点,分别存放于s1和s2HTs1.parent=i;HTs2.parent=i;/两个节点指向同一父节点HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/父节点的权值为子节点相加（父节点继续放入选择区）void Hafumanencode(HafumanTree HT,HafumanCode HC)int c,p,i;char cdn;/临时数组用于