14251102202_陈晓俊_哈夫曼树编码解码.doc

课程设计课程名称数 据 结 构班级与班级代码14计算机2班，142511022专 业计 算 机 科 学 与 技 术指导教师罗 勇学 名陈晓俊电子邮箱827381654提交日期2016年6月29日广东财经大学教务处 制哈夫曼树编码解码1任务和要求哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。既然要设计哈夫曼树编码来进行通讯传输,那么就必须有一套哈夫曼树解码。通过对哈夫曼树编码解码的分析，此实验应该包含如下要求：（1）设计一组字符和字符出现的频率，即字符的权重，生成哈夫曼树；（2）利用哈夫曼树求出所对应的哈夫曼树编码；（3）打印所有字符以及所对应的哈夫曼编码，并显示平均编码长度；（4）利用哈夫曼树解码原理编写解码函数，由哈夫曼编码求解出所对应的字符；（5）显示所有哈夫曼编码及其所对应的字符；（6）对比分析编码解码的正确性；2总体设计2.1系统功能模块图：图一初始化哈夫曼树构造哈夫曼编码构造哈夫曼树打印哈夫曼编码哈夫曼树译码打印哈夫曼树打印哈夫曼译码主函数2.2哈夫曼树的特点：哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树，权值较大的结点离根较近。2.3哈夫曼树的构造过程：步骤1：根据给定的n个权值w1,w2,wn，构造n棵只有根节点的二叉树，这n棵二叉树构成一个森林f。步骤2：在森林f中选择两棵根节点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的权值为其左右子树上的根节点的权值之和。步骤3：在森林f中删除这两棵树，同时将新得到的二叉树放入到f中。步骤4：重复步骤2和步骤3，知道f中只有一棵二叉树为止。2.4哈夫曼树的编码相关性质：性质1：哈夫曼编码是前缀编码性质2：哈夫曼编码是最优前缀编码2.5哈夫曼树的编码过程：依次以叶子为出发点，向上回溯至根节点为止。回溯时走作分支则生成代码0，走右分支则生成代码1。3.详细设计3.1详细的涉及思路（1） 采用的节点类型：哈夫曼树的节点又四个类型，包括节点的权值weight、双亲节点parent、左孩子节点lchild、右孩子节点rchild。采用的逻辑结构：哈夫曼树为最优二叉树，其采用的逻辑结构为树状结构。采用的存储结构：由于哈夫曼树中没有度为1的节点，则一棵有n个节点的哈夫曼树共有2n-1个节点，可以存储在一个大小为2n-1的一维数组中。树中没个节点还要包含其双亲信息和孩子节点的信息，因此，每个节点的存储结构如下表一所示，哈夫曼树的结构体如下面所示的结构体。表一weightparentlchildrchild/-哈夫曼树的存储表示-typedef structchar data5;/定义节点值double weight;/节点的权重int parent,lchild,rchild; /定义哈夫曼树的双亲节点、左右孩子节点htnode，*huffmantree;/动态分配数组存储哈夫曼树采用的算法：本系统采用的算法为哈夫曼算法。3.2哈夫曼树编码解码详细的构造过程（1）设计如下字符权重表（即26字权重表） 表二字符abcdefghij权重121323156724369010019字符klmnopqrst权重391392343578895714589029字符uvwxyz权重701234561189111（2）根据字符权重表，利用哈夫曼算法构造哈夫曼数。下面取图三表格中的前面10个字符权重进行构造哈夫曼树的思路说明。注：全部字符的构造与实现将在程序中体现！步骤1：根据给定的10个字符权值，构造10棵只有根节点的二叉树，这10棵二叉树构成一个森林f。1213231567森林f19100903624步骤2：在森林f中选择两棵根节点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的权值为其左右子树上的根节点的权值之和。如下图a251213图a步骤3：在森林f中删除这两棵树，同时将新得到的二叉树放入到f中。如下图b36246715232519100901312图b步骤4：重复步骤2和步骤3，知道f中只有一棵二叉树为止。最后得到如图四的哈夫曼树。图四1733992268390100126364759672324253412131519（3）哈夫曼树编码原理及其算法： 哈夫曼编码是指利用哈夫曼树求得的用于通信的二进制编码。树中从根到每个叶子节点都有一条路径，对路径上的各分支约定指向左子树的分支表示”0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为各个叶子节点对应的字符编码，这就是哈夫曼编码原理。例如上图四的哈夫曼树的编码如下页图五所示，图五即为哈夫曼树的编码原理，编码是从叶子节点开始编起，往根节点回溯的过程。图五1733992268390100126364759672324253412131519000101011010110011abdjcfgehi 所以，图五中字符的二进制哈夫曼编码如下表三：字符abcdefghij哈夫曼编码00011100110100010111111100000100111011表三表四为26个字母经过哈夫曼树的构造、编码得到的二进制编码：字符abcdefghij权重1100000100010000101111000100100011110000100111101110011110101110字符klmnopqrst权重010110001011010011100101001100110001010010000101字符uvwxyz权重001100000111110000000110111001表四（4） 哈夫曼树解码原理：首先得知道编码用的哈夫曼树以及字符对应的二进制编码如图五。然后从哈夫曼树的根结点出发，逐个读入文件中的二进制码；若代码为“0”，则走左子树的根结点，否则走向右子树的根结点；一旦到达叶子结点，便译出代码所对应的字符。然后又重新从根结点开始继续译码，直到二进制文件结束。例如我想要对如下表五语句进行编码解码：表五canyougivemeakiss那么，得到的语句的二进制编码为下表六：表六canyougivemeakiss0101111110000010011100110101010001100011110111100000001111010001100011010110011111010解码只需发送上面表六的二进制编码进行解析即可得到:can you give me a kiss 这一语句。4 编码4.1 数据结构定义本实验所用的数据结构定义如下：typedef struct char ch; int weight; /权值，这个字符出现的频率 int parent; /父节点 int left; /左孩子 int right; / 右孩子huffnode; typedef struct char codemaxnum; int start; huffcode; huffnode htmaxnum*2; /存放哈夫曼树 huffcode hcdmaxnum; /存放ht数组中对应的字符的编码4.2 项目结构图4.3 功能函数的设计void chushihuaht(); /初始化哈夫曼树htvoid gouzaoht(); /构造哈夫曼树,看成有n棵树，选择权值最小的两棵树合并void gouzaohtcode(); /哈夫曼编码，通过父节点从下往上找，输出哈夫曼编码平均长度int jiemaht(char *str,char* code); /哈夫曼解码，每次都从根节点开始搜索void fanzhuan(char *str); /将一个字符串反转(将编码从叶子节点开始编)void shurubainmacode(); /用户输入编码字符,并将编码字符及其编码打印到文件当中void shurujiemacode(); /用户输入解码字串void main(); /主函数4.4 函数调用关系图main.cppchushihuaht.cppfanzhuan.cppgouzaoht.cppshurubianmacode.cppgouzaohtcode.cppshurujiemacode.cppjiemaht.cppgouzaohtcode.cppshurujiemacode.cpp图八4.5 程序实现/*全部代码实现如下：*/#include #include #include #include/*定义最大长度为字符常量*/#define maxnum 60/*定义哈夫曼树编码解码结构体*/typedef struct char ch; int weight; /权值，这个字符出现的频率 int parent; /父节点 int left; /左孩子 int right; /右孩子huffnode; typedef struct char codemaxnum; int start; huffcode;/*定义存放哈夫曼树、哈夫曼编码的全局变量*/extern huffnode htmaxnum*2; /存放哈夫曼树 extern huffcode hcdmaxnum; /存放ht数组中对应的字符的编码 extern int n; /字符的个数/*声明函数*/void main();void chushihuaht(); void gouzaoht();void fanzhuan(char *str);void gouzaohtcode();int jiemaht(char *str,char* code);void shurubainmacode();void shurujiemacode();/*下列为哈夫曼编码解码的主函数，该函数调用了chushihuaht()、gouzaoht()、gouzaohtcode()函数，其功能是读入文件zifuht.txt中的字符及其权重，生成对应的哈夫曼树编码并将其打印在dayincode.txt文件中；同时显示系统选择菜单，提供输入选项，选项1、2、3分别调用了函数shurubainmacode()、shurujiemacode()、gouzaohtcode()。*/void main() int choice=1;/设置while循环的标志 chushihuaht();/初始化哈夫曼树 gouzaoht(); /构造哈夫曼树 gouzaohtcode(); /构造哈夫曼编码并将字符及其哈夫曼编码打印出来 while(choice) system(cls); printf(/*哈曼编码与解码*/n); printf( 在zifuht.txt 文件中存放着各个英文字母的权值n); printf( 程序从中读出各个字母的权值构造哈夫曼树并进行编码n); printf( 各个字符的编码存在dayincode.txt文件中n); printf(/*/n); printf(n请输入你的选择：n); printf(n 1: 编码n); printf(n 2: 解码n); printf(n 3:平均编码长度n); printf(n 4:退出n); scanf(%d,&choice); switch(choice) case 1: shurubainmacode();/输入需要编码是字符，并将其打印出来 break; case 2: shurujiemacode();/输入需要解码的字符串，并将其打印出来 break; case 3: gouzaohtcode();/输出哈夫曼树平均编码长度 case 4: printf(谢谢使用！n);/推出系统 exit(0); break; default: choice=1; printf(你的输入错误！按任意键后重新输入！n); getch(); break; /*下列函数初始化哈夫曼树，定义文件指针file *fp,将含有字符及其权重的zifuht.txt文件读入到fp中进行初始化。*/void chushihuaht() file * fp; char ch; int i=0; /从文件“zifuht.txt”中读出要编码的字符和权值 if(fp=fopen(zifuht.txt,r)=null) printf(不能打开文件 zifuht.txt); exit(0); /将父节点、左孩子、右孩子置为-1 hti.left=hti.right=hti.parent=-1; while(ch=fgetc(fp)!=eof) /当文件没有读完，执行while循环 if(ch=n)/字符为空 i+; /父节点，左右孩子节点置-1 hti.left=hti.right=hti.parent=-1; else if(ch=a & ch=a & ch=0&ch=9)/字符为数字 hti.weight=hti.weight*10+ch-0;/读入权重 n=i+1; if(fclose(fp) printf(不能打开文件 zifuht.txt); exit(0); /*下列函数构造哈夫曼树，利用哈夫曼算法，将所有节点看成有n棵树，选择权值最小的两棵树合并，最终构成一棵完整的哈夫曼树。*/void gouzaoht() int i=0,k; int mini,minj; /表示存放权值最小的两个节点的数组下标 int f=0; mini=minj=-1; /miniminj for(k=n;k2*n-1;k+) /寻找ht中权值最小且无父结点的两个结点 i=0; f=0; while(hti.ch!=0) if(hti.parent=-1)/没有父节点，则执行下面语句 if(f=0) mini=i; f+; else if(f=1) if(hti.weighthtmini.weight) minj=mini; mini=i; else minj=i; f+; else/如果有父节点则比较权值的大小 if(hti.weighthtmini.weight)/如果父节点的权值比较小，则把父节点的下标赋值给mini minj=mini; mini=i; else if(hti.weighthtminj.weight)/如果父节点的权值比较大，则把父节点的下标赋值给minj minj=i; i+; /合并两个结点 htk.ch=#; htk.left=mini; htk.right=minj; htk.weight=htmini.weight+htminj.weight; htk.parent=-1; htmini.parent=htminj.parent=k;printf(aaaaa); /*下列函数构造哈夫曼编码，通过根节点从下往上找，输出哈夫曼编码平均长度；调用函数fanzhuan()将所得编码反转，然后将所得到的26个字母及其编码存放在文件dayincode.txt中。*/void gouzaohtcode() int i,j,length;int sum=0,m=0; file * fp; for(i=0;in;i+) /从父节点开始寻找 length=0; j=i; /给每个字符进行编码 while(htj.parent!=-1)/当存在父节点时执行 if(hthtj.parent.left=j) /第一个字符为父节点的左孩子 hcdi.codelength+=0+0; /置0 else /第一个字符为父节点的右孩子 hcdi.codelength+=1+0; /置1 j=htj.parent; /将此父节点的值赋给j /将字符编码从上往下存在hcdi.starthcdi.start=hcdi.codelength-1-0; hcdi.codelength=0; fanzhuan(hcdi.code); /将字符编码翻转 m+=hti.weight;/将所有的字符权值相加 sum+=hti.weight*j;/计算字符编码的平均长度 if(fp=fopen(dayincode.txt,w)=null)/把hcd字符编码写入文件dayincode.txt中 printf(不能打开文件 dayincode.txt); exit(0); for(i=0;in;i+)/往文件里写入字符和编码 fputc(hti.ch,fp); fputs( ,fp); fputs(hcdi.code,fp); fputc(n,fp); if(fclose(fp) printf(不能打开文件 dayincode.txt); exit(0); printf(平均编码长度=%gn,1.0*sum/m);/*下列函数为反转函数，将gouzaohtcode()函数从根节点编码的字符串反转变成从叶子节点开始编码。*/void fanzhuan(char *str) int i,j; char ch; for(i=0,j=strlen(str)-1;i=a&stri=a&stri=z)/字符为26字母 for(j=0;jn;j+) if(stri=htj.ch)/比较输入字符和文件coadht.txt中（即哈夫曼树中的字符） strcat(code,hcdj.code);/将编码存放在数组code中strcat(code1,&htj.ch);/将字符存放在数组code1中fputc(stri,fp);/将字符写入code.txt文件中 break; i+; else if(stri=#)/读到#符号puts(code1);/显示字符单词printf( );puts(code);/显示单词编码fputs( ,fp); fputs(code,fp); /将单词编码写入到文件code.txt中 fputc(n,fp);memset(code, 0, sizeof(code);/将code清空memset(code1, 0, sizeof(code1);/将code1清空i+;elsef=0;break; if(fclose(fp) printf(不能打开 code.txt 文件); exit(0); if(f) printf(你输入的每个单词所对应的二进制编码最终存放在 code.txt 文件中！n);printf(n); else printf(你输入的字符串错误！n); printf(n); printf(按任意键后重新选择！n); getch(); /*下列函数的功能为当用户在选择菜单上选择解码时，输入需要解码的字符串，调用函数jiemaht(str,code)进行解码，然后在运行界面会显示相应的字符。*/void shurujiemacode() char str50; char code500=0; printf(n请输入要解码的字串(用0和1表示)n); scanf(%s,code);printf(n各进制码所对应的单词如下：n); if(jiemaht(str,code)/所输入编码字符串与26字符的编码相等printf(n);puts(code);/显示编码 puts(str);/显示该编码所对应的字符 else printf(你输入的字串错误！n); printf(按任意键后重新选择！n); getch(); /*下列函数为解码函数，是对函数shurujiemacode()输入的字符串进行解码,输出相应的字符单词。*/int jiemaht(char *str,char* code) int root=2*n-2; int length=0,i=0; while(codei) /当编码不为空 if(codei=0+0) /为0 root=htroot.left; /向左搜索 else if(codei=0+1)/为1 root=htroot.right; /向右搜索 else return 0; /否则报错 if(htroot.left=-1 & htroot.right=-1)/如果左右节点都不存在 strlength+=htroot.ch; root=2*n-2; /重新搜索 i+; strlength=0; if(root=2*n-2) return 1; return 0; 5 测试5.1程序测试用例 主菜单界面功能测试用例如下表5.1表5.1字段名称描述内容测试项程序主菜单功能测试测试目的查看主菜单是否按照预想的那样出现运行界面，测试程序是否按照选择成功运行输入标准1. 输入1，然后按enter2. 输入2，然后按enter3. 输入3，然后按enter4. 输入4，然后按enter5. 输入其他输出标准1. 进入编写英文单词界面，通过英文单词从而得到哈夫曼编码2. 进入哈夫曼解码界面，通过0、1编码得到英文单词3. 进入输出哈夫曼编码平均长度界面4. 退出系统5. 提示输入非法错误原因可能由于代码编写错误、逻辑错误、运行错误而导致界面没有达到所需要的效果当前状态显示当前测试结果的状态哈夫曼编码测试用例如下表5.2所示表5.2字段名称描述内容输入测试的字符can you give me a kiss测试目的查看函数chushihuaht()、gouzaoht()、gouzaohtcode()是否逻辑正确以及是否进行正确的哈夫曼树编码，同时测试函数shurubainmacode()是否能正确输出想要的结果预测输出can 010111111000001001110you 011010101000110give 00111101111000000011me 110100011a 11000001kiss 010110011111010实际输出测试实际输出的结果，比较实际输出和预测输出的结果是否相同错误原因如果实际输出和预测输出的结果不一致，则分析产生错误的原因当前状态显示当前测试结果的状态表5.2哈夫曼解码测试用例如表5.2字段名称描述内容输入测试的字符串01111 001001010000000011 011010101000110测试目的查看函数shurujiemacode()、jiemaht(char *str,char* code)是否逻辑正确以及是否进行正确的哈夫曼解码预测输出01111 i001001010000000011 love011010101000110 you实际输出测试实际输出的结果，比较实际输出和预测输出的结果是否相同错误原因如果实际输出和预测输出的结果不一致，则分析产生错误的原因当前状态显示当前测试结果的状态5.2程序运行结果（1） 上述源程序在vc+6.0中编译运行后，得到如下页实验截图5.4所示。界面中首先给出运行代码函数chushihuaht()、gouzaoht()、gouzaohtcode()后的说明和结果，运行结果为系统将存有权重的英文字母的文件zifuht.txt读入到系统中，对其进行哈夫曼编码，并将字符和相应的编码写入文件dayincode.txt中；主菜单中共有1-4共4个选项，1为输入相应的英文单词从而对其进行编码，2为输入相应的哈夫曼编码从而对其进行解码，3为输出哈夫曼树编码解码的平均长度，4为退出该系统。实验截图5.4(2）选择选项1，添加一组英文单词，按照提示输入can#you#give#me#a#kiss#,操作成功后会输出每个单词以及其哈夫曼编码，并且将结果写入到文件code.txt中保存方便使用，如实验截图5.5；如果操作失败就提示错误，按任意键重新选择，如下页的实验截图5.6。实验截图5.5实验截图5.6（2）按任意健，系统回到主菜单界面。选择选项2，添加一组哈夫曼编码，按照提示输入01111001001010000000011011010101000110，操作成功后会输出所对应的单词i love you，如实验截图5.7所示；如果操作不成功，则提示错误，按任意键重新选择，如实验截图5.8所示。实验截图5.7实验截图5.8（3）按任意健，系统回到主菜单界面。选择选项3，输出系统的哈夫曼编码平均编码长度，如实验截图5.9。实验截图5.9（4）按任意健，系统回到主菜单界面。选择选项4，系统自动退出程序，如实验截图5.10。实验截图5.106 总结6.1 不足与设想不足：这个程序只是实现哈夫曼树编码解码系统中最基本的几个功能，如基本编码功能、基本解码功能、计算哈夫曼树平均编码长度，没有更深层次地设计其他功能，如通过读入一篇英文文章，从而计算各个字母出现的频率，进行哈夫曼编码等等！除此之外，本程序出现程序冗余情况，如函数fanzhuan(char *str)，如果按照先读叶子节点的方法实现编码，这个函数的存在就不必要了。设想：本程序可以向更高级的功能实现，就如上面