哈夫曼编码译码器

1、哈夫曼编码译码器学院班级:信息工程学院软件 1501指导教师:朱俊武小组成员:刘洋蒋佳烨 冀若含本人学号:151303107报告书写:冀若含 学生成绩:目录一、总体介绍03-04二、详细设计04-11三、运行测试 11-12四、课设总结 13-13五、附录代码 13-19一、总体介绍1.1任务概述我们小组做了两个版本，其中一个为文件操作版，另一个为键盘操作版。两个版本都实现了哈夫曼编码 /译码操做。我主要负责的是构造哈夫曼树，给出各个字符的哈夫曼编码，加密操做，整个键盘操 作版系统的代码重组、编辑。开发的过程中使用了Codelite、Dev、Vc等软件。参考书籍为数据结构（c语言版）。其中文件

2、操作版的具体实现为：够实现对26个小写字母外加空格进行哈夫曼编码，并能够对一整篇文章（有小写字母和空格组成）进行加密，生成密码文件。最后根据生成的密码翻译出原文并存档。葩使用程序时，使用者只需要对ToBetran文件进行原文的输入（使 用小写字母或空格），加密和解密功能由程序自主来完成。3程序运行的过程中会输出进行编码的 26个小写字母和空格（字符 型），并输出其对应的权值（整型）。还输出字符的编码及生成的密文。 最后输出解密后的原文。键盘操作版为：1要求从键盘输入字符集和字符的权值，大部分字符均可输入，需要各个字符的权值不能相同。2利用输入的权值建立哈夫曼树，得到每个字符的前缀编码。3输入字

3、符串，程序对其进行加密。4输入密文(1010101 :)对密文进行解密。两个版本都利用了哈夫曼树解决问题，通过建立哈夫曼树，得出 每个字符的独特前缀编码，也就是密文，然后利用密文对明文进行加 密得到密文。密文转换为明文则是通过对哈夫曼树的遍历。(之前想过字符串的匹配得到明文但是算法太为复杂)。1.2系统功能框图开始构建哈夫 曼树编码译码本系统分为三个大的模块：构造哈夫曼树，编码，译码1.3功能难点本系统的实现难点在于哈夫曼树的构造。编码、译码功能的实现 都是基于哈夫曼树的。二、详细设计2.1哈夫曼树的构造哈夫曼树，又称最优树，是一类带权路径长度最短的树，有着广泛的应用。哈夫曼树的构造过程如下：

4、1. 初始化：根据给定的n个权值w1,w2,wn构成n棵二叉树的集 合F=T1,T2,.,Tn，其中每棵二叉树Ti中只有一个带权wi的根节点， 左右子树均空。2. 找最小树：在F中选择两棵根结点权值最小的树作为左右子树构 造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上 根结点的权值之和。3. 删除与加入：在F中删除这两棵树，并将新的二叉树加入F中。4. 判断：重复前两步(2和3)，直到F中只含有一棵树为止。该树 即为哈夫曼树。2.2代码实现哈夫曼树和哈夫曼编码的储存表示typedef structint weight;int pare nt,lchild,rchild;HTNod

5、e,*Huffma nTree;/动态分配数组储存哈夫曼树typedef char* *Huffma nCode;/动态分配数组储存哈夫曼编码表void Select(HuffmanTree HT,int p,int *s1,int *s2)该函数的功能为：找出 HT1 ./中pare nt为0且weight最小的 两个结点，其序号为s1 , s2。void Huffma nCodi ng(Huffma nTreeHT,Huffma nCodeHC,i nt*w,i nt n, char *a)该函数的功能为构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC。以下为两个函数的流程图或详细设计。H

6、T,Huffma nCodeHC,i ntvoid Huffma nCodi ng(Huffma nTree*w,i nt n, char *a)指针a指向输入的字符集，指针 w指向字符集的度，n为字符集的大小。注：具体程序中加入了输出各个字符的哈夫曼编码的功能，在流程图没有显示。没画完下面还有哟！!为cd分配纯储存空间王Cd n-1=0王Start=n-1C=IF=HTI.PARENTweiHC指旨针分配空间详细代码:NHTF.LCHILD=C 对Cd-start= 1'CD-START= 0'fjC=f,f=HTf.pw1.arentYYi<=N?F!=0?为第i个字

7、符分配空 间n复制cd到HCIFree(cd)Nvoid Huffma nCodi ng(Huffma nTree HT,Huffma nCode HC,i nt *w,i nt n, char*a)int m=0;int c;int f;int start;char *cd;int *s1;int *s2;int i;s1=(i nt*)malloc(sizeof(i nt);s2=(i nt*)malloc(sizeof(i nt); m=2* n-1;if(n<=1)printf(”字符的个数过少n"); return;Huffma nTree p;P=HT;P+;for

8、(i=1;i<=n;+i,+p,+w) p->weight=*w;p->pare nt=O;p->lchild=O;p->rchild=0;for(;i<=m;+i,+p)p->weight=0;p->pare nt=O;p->lchild=O;p->rchild=O;for(i=n+1;i<=m;+i)Select(HT,i-1,s1,s2);HT*s1.pare nt=i;HT*s2.pare nt=i;HTi.lchild=*s1;HTi.rchild=*s2;HTi.weight=HT*s1.weight+HT*s2.w

9、eight;cd=(char *)malloc( n*sizeof(char);cdn-1='0'for(i=1;i<=n;+i)start=n-1;for(c=i,f=HTi.pare nt;f!=0;c=f,f=HTf.pare nt)if(HTf.lchild=c) cd-start='0'else cd-start='1'HCi=(char *)malloc( n-start)*sizeof(char);strcpy(HCi,&cdstart);prin tf("%c ",*a);a+;prin tf(&

10、quot;%sn",HCi);free(cd);void Select(HuffmanTree HT,int p,int *s1,int *s2)详细设计：1首先通过一个循环找出当前数组中weight最小的一个。记录下它的序号。1也是一和一样的循环和算法。加上一个if语句，如果循环到与第一 次序号一样的那次，就continue跳过这次比较。1将得到的权值最小的两个传到s1和是s2指向的地址。这就是哈夫曼树的构造和生成哈夫曼编码的过程。详细代码：void Select(Huffma nTree HT, in t p,i nt *s1,i nt *s2)/i为遍历长度int i=1;in

11、t x=0;int y=0;in t min=1000;in t min 1=1000;int v=1;*s1=1;*s2=1;for(i=1;i<=p;i+)x=HTi.pare nt;y=HTi.weight;if(x=O&&min>y)mi n=HTi.weight;*s1=i;v=i; for(i=1;i<=p;i+)x=HTi.pare nt;y=HTi.weight;if(i=v)con ti nue;if(x=0&&min 1>=y)mi n仁HTi.weight;*s2=i;2.3编码(加密)此函数void Huffman

12、Encryption(HuffmanCode HC,char *a,int n)为加密函数。该加密函数的流程图如下：该功能的实现就是通过一个简单的查找， 通过字符与字符的哈夫曼编 码在不同数组的对应关系，进行加密。Input储存输入的字符串。 Lo为输入的字符串长度，n为原字符集的字符个数。详细代码如下：void HuffmanEncryption(HuffmanCode HC,char *a,int n)char in put100;int i=0,j=0;char lu=''int lo=0;要加密的字符串的长度char c;printf("请输入你要加密的字符串

13、n");while(lu=getchar()!='n'&&lu!=EOF)Jc=getchar();while(c!='n')in puti=c;i+;c=getchar();lo=i;for(i=0;i<lo;i+)for(j=0;j <n ;j+)if(i nputi=aj)prin tf("%s",HCj+1);prin tf("n");三、运行测试X菜单界面:D :xu nl e1 myti uff D ebu gmyh u ff. exe*哈夬晏编码刀?码器*KMCXJMJI

14、 >!耳H:Wl軍 若含1L S l-M 'J鼻彳士悍* ®构造哈夬-H KKXH WK 贰 MIX WIN WLXJLMJtK Ml JCJtJCM KU! JO4J<J<MJIKJ< JCJHJCJtWKKKK*必须先构建哈夫晨樹 WM" Hlf “ 请选择你要埶行的功畿码、铎码E退出按微敦拼音半:构造哈夫曼树:编码：侖J入你要加密的字符串I LIKE IT0011S100B1118111111B0e01情选择你要执行的功能A ： A译码：密钥：I 00110L 1BK 1110E 1111T 81译码测试:崔话入你要解密的宇符串adii

15、oitiaa 丄 1i like it谙选择彳尔要执行的功能養嶋入你要解密的字符串I请选择你要执行的功能四、总结经过几天的设计与编码我们小组终于完成了两个不同的版本的哈 夫曼编码译码器。虽然两个系统大部分的算法相同， 但是也算我们的 尝试。美中不足的是我们没能把两个版本的系统融合起来。 开发过程 中遇到的最大的问题就是输入输出流的问题。 因为是从键盘输入数据 的所以难免会遇到这种问题。我通过输入流的过滤解决了此问题。 通 过这几天的实验，加深了我对哈夫曼树的理解，也加强了自己的动手 能力。数据结构这门课程还有很多很多的东西，我们仍应该继续努力。附录全部代码：#i nclude <stdi

16、o.h>#i nclude <stdlib.h>#in elude <stri ng.h>#in elude <win dows.h>typedef structint weight;int pare nt,lchild,rchild; HTNode,*Huffma nTree;typedef char* *Huffma nCode;为遍历长度,bigvoid Select(HuffmanTree HT,int p,int *s1,int *s2)/i int i=1;int x=0;int y=0;int min=1000;int min 1=100

17、0;int v=1;*s1= 1;*s2=1;for(i=1;i<=p;i+)x=HTi.pare nt;y=HTi.weight;if(x=0&&min>y)mi n=HTi.weight;*s1=i;v=i;for(i=1;i<=p;i+)x=HTi.pare nt;y=HTi.weight;if(i=v)con ti nue;if(x=0&&mi n1>=y)mi n仁HTi.weight;*s2=i;void Huffma nCodi ng(Huffma nTree HT,Huffma nCode HC,i nt *w,i nt

18、n,char *a)int m=0;i nt c;i nt f;int start;char *cd;int *s1;int *s2;int i;s1=(i nt*)malloc(sizeof(i nt);s2=(i nt*)malloc(sizeof(i nt);m=2* n-1;if(n <=1)printf(”字符的个数过少n");return;Huffma nTree p;P=HT;P+；for(i=1;i<=n;+i,+p,+w)p->weight=*w;p->pare nt=O;p->lchild=O;p->rchild=O;for(;

19、i<=m;+i,+p)p->weight=0;p->pare nt=O;p->lchild=0;p->rchild=0;for(i=n+1;i<=m;+i)Select(HT,i-1,s1,s2);HT*s1.pare nt=i;HT*s2.pare nt=i;HTi.lchild=*s1;HTi.rchild=*s2;HTi.weight=HT*s1.weight+HT*s2.weight;cd=(char *)malloc (n *sizeof(char);cdn-1='0：for(i=1;i<=n ;+i)start=n-1;for(c=

20、i,f=HTi.pare nt;f!=O;c=f,f=HTf.pare nt)if(HTf.lchild=c) cd-start='0'else cd-start='1'HCi=(char *)malloc( n-start)*sizeof(char);strcpy(HCi,&cdstart);prin tf("%c ",*a);a+;prin tf("%sn",HCi);free(cd);void HuffmanEncryption(HuffmanCode HC,char *a,int n)char in put

21、1OO;int i=0,j=0;char lu=''int lo=0; 要加密的字符串的长度char c;printf("请输入你要加密的字符串n");while(lu=getchar()!='n'&&I u!=EOF)5c=getchar();while(c!='n')in puti=c;i+;c=getchar();lo=i;for(i=0;i<lo;i+)for( j=O;j<n;j+)if(in puti=a j)prin tf("%s",HCj+1);prin tf(&

22、quot;n");解密void Huffma ndecipheri ng(Hufma nCode HC,char *a,i nt n,Huffman Tree HT)in t in put100=0;char c=''int num=O;int m=1;int t=0;n");printf("请输入你要解密的字符串int i=0;getchar();while(c!='n')c=getchar();inputi=(i nt)c-48;i+;num=i;for(i=1;t=0;i+)if(HTi.pare nt =0)t=i;根结点的

23、位置m=t;for(i=0;i< nu m;i+)if(in puti=O)m=HTm.lchild;if(in puti=1) m=HTm.rchild;if(HTm.lchild=0)prin tf("%c",am-1);m=t;void view()* n");*prin tf("tt*哈夫曼编码/译码器*n");prin tf("tt* n");prin tf("tt*冀若含文U洋蒋佳烨*n"）;printf（"tt* B构造哈夫曼树C编码 D译码 E退出 *n”）;prin tf

24、("tt* n");prin tf("tt*A 清屏 F 初始化*n”)；prin tf("tt*必须先构建哈夫曼树* n");int main (i nt argc, char *argv)view();char lu=''Huffma nCode HC;Huffma nTree HT;char *a;存放字符int *w;int n;int i;char in p=''int in pt=0;char choice=' '/储存你要选择的功能选项a=(char*)malloc( (n+2)*s

25、izeof(char);w=(i nt*)malloc( (n *sizeof( in t);HT=(Huffma nTree)malloc(2* n)*sizeof(HTNode);HC=(Huffma nCode)malloc( n+1)*sizeof(char*);while(1)printf("请选择你要执行的功能n"); prin tf(">:");scan f("%c",&choice);switch(choice)case 'a':case 'A':system("cls");view();getchar();break;case 'b':case 'B':printf("请输入字符集大小n");scan f("%d",&n);printf(”请输入字符名和度数中间以空格隔开n");for(i=0;i< n;i