哈夫曼编码译码器(共20页)

1、精选优质文档-倾情为你奉上哈夫曼编码译码器学院班级: 信息工程学院 软件1501 指导教师: 朱俊武 小组成员: 刘洋 蒋佳烨 冀若含 本人学号: 报告书写: 冀若含 学生成绩: 目录一、总体介绍·····························03-04二、详细设计···

2、;··························04-11三、运行测试······················

3、·······11-12四、课设总结·····························13-13五、附录代码··········&#

4、183;··················13-19一、总体介绍1.1任务概述我们小组做了两个版本，其中一个为文件操作版，另一个为键盘操作版。两个版本都实现了哈夫曼编码/译码操做。我主要负责的是构造哈夫曼树，给出各个字符的哈夫曼编码，加密操做，整个键盘操作版系统的代码重组、编辑。开发的过程中使用了Codelite、Dev、Vc等软件。参考书籍为数据结构（c语言版）。其中文件操作版的具体实现为：能够实现对26个小写字

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

6、个版本都利用了哈夫曼树解决问题，通过建立哈夫曼树，得出每个字符的独特前缀编码，也就是密文，然后利用密文对明文进行加密得到密文。密文转换为明文则是通过对哈夫曼树的遍历。（之前想过字符串的匹配得到明文但是算法太为复杂）。1.2系统功能框图本系统分为三个大的模块：构造哈夫曼树，编码，译码。1.3 功能难点本系统的实现难点在于哈夫曼树的构造。编码、译码功能的实现都是基于哈夫曼树的。二、详细设计2.1哈夫曼树的构造哈夫曼树，又称最优树，是一类带权路径长度最短的树，有着广泛的应用。哈夫曼树的构造过程如下：1.初始化： 根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,.,Tn，其中每棵

7、二叉树Ti中只有一个带权wi的根节点，左右子树均空。2. 找最小树：在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。3. 删除与加入：在F中删除这两棵树，并将新的二叉树加入F中。4. 判断：重复前两步（2和3），直到F中只含有一棵树为止。该树即为哈夫曼树。2.2 代码实现哈夫曼树和哈夫曼编码的储存表示typedef structint weight;int parent,lchild,rchild;HTNode,*HuffmanTree;/动态分配数组储存哈夫曼树typedef char* *HuffmanCode;/

8、动态分配数组储存哈夫曼编码表void Select(HuffmanTree HT,int p,int *s1,int *s2)该函数的功能为：找出HT1.i-1中parent为0且weight最小的两个结点，其序号为s1，s2。void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n,char *a)该函数的功能为构造哈夫曼树HT，并求出n个字符的哈夫曼编码HC。以下为两个函数的流程图或详细设计。void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n,char

9、*a) 指针a指向输入的字符集，指针w指向字符集的度，n为字符集的大小。注：具体程序中加入了输出各个字符的哈夫曼编码的功能，在流程图没有显示。没画完下面还有哟！详细代码：void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n,char *a)int m=0;int c;int f;int start;char *cd;int *s1;int *s2;int i;s1=(int*)malloc(sizeof(int);s2=(int*)malloc(sizeof(int);m=2*n-1;if(n<=1)printf(&q

10、uot;字符的个数过少n");return;HuffmanTree p;p=HT;p+;for(i=1;i<=n;+i,+p,+w)p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;for(;i<=m;+i,+p)p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;for(i=n+1;i<=m;+i)Select(HT,i-1,s1,s2);HT*s1.parent=i;HT*s2.parent=i;HTi.lchild=*s1

11、;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=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c) cd-start='0'else cd-start='1'HCi=(char *)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstar

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

13、nt *s1,int *s2)/i为遍历长度int i=1;int x=0;int y=0;int min=1000;int min1=1000;int v=1;*s1=1;*s2=1;for(i=1;i<=p;i+)x=HTi.parent;y=HTi.weight;if(x=0&&min>y)min=HTi.weight;*s1=i;v=i;for(i=1;i<=p;i+)x=HTi.parent;y=HTi.weight;if(i=v)continue;if(x=0&&min1>=y)min1=HTi.weight;*s2=i;2.

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

15、ntf("请输入你要加密的字符串n");while(lu=getchar()!='n'&&lu!=EOF);c=getchar();while(c!='n')inputi=c;i+;c=getchar();lo=i;for(i=0;i<lo;i+)for(j=0;j<n;j+)if(inputi=aj)printf("%s",HCj+1);printf("n");三、运行测试菜单界面：构造哈夫曼树：编码：译码：密钥：译码测试：四、总结经过几天的设计与编码我们小组终于完成了两个

16、不同的版本的哈夫曼编码译码器。虽然两个系统大部分的算法相同，但是也算我们的尝试。美中不足的是我们没能把两个版本的系统融合起来。开发过程中遇到的最大的问题就是输入输出流的问题。因为是从键盘输入数据的所以难免会遇到这种问题。我通过输入流的过滤解决了此问题。通过这几天的实验，加深了我对哈夫曼树的理解，也加强了自己的动手能力。数据结构这门课程还有很多很多的东西，我们仍应该继续努力。附录全部代码：#include <stdio.h>#include <stdlib.h>#include <string.h>#include <windows.h>typed

17、ef structint weight;int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char* *HuffmanCode;void Select(HuffmanTree HT,int p,int *s1,int *s2)/i为遍历长度，bigint i=1;int x=0;int y=0;int min=1000;int min1=1000;int v=1;*s1=1;*s2=1;for(i=1;i<=p;i+)x=HTi.parent;y=HTi.weight;if(x=0&&min>y)min=HTi

18、.weight;*s1=i;v=i;for(i=1;i<=p;i+)x=HTi.parent;y=HTi.weight;if(i=v)continue;if(x=0&&min1>=y)min1=HTi.weight;*s2=i;void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n,char *a)int m=0;int c;int f;int start;char *cd;int *s1;int *s2;int i;s1=(int*)malloc(sizeof(int);s2=(int*)mall

19、oc(sizeof(int);m=2*n-1;if(n<=1)printf("字符的个数过少n");return;HuffmanTree p;p=HT;p+;for(i=1;i<=n;+i,+p,+w)p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;for(;i<=m;+i,+p)p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;for(i=n+1;i<=m;+i)Select(HT,i-1,s1,s2);H

20、T*s1.parent=i;HT*s2.parent=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=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c) cd-start='0'else cd-start='1'HCi=(char *)malloc(n

21、-start)*sizeof(char);strcpy(HCi,&cdstart);printf("%c ",*a);a+;printf("%sn",HCi);free(cd);void HuffmanEncryption(HuffmanCode HC,char *a,int n)char input100;int i=0,j=0;char lu=' 'int lo=0;/要加密的字符串的长度char c;printf("请输入你要加密的字符串n");while(lu=getchar()!='n'

22、;&&lu!=EOF);c=getchar();while(c!='n')inputi=c;i+;c=getchar();lo=i;for(i=0;i<lo;i+)for(j=0;j<n;j+)if(inputi=aj)printf("%s",HCj+1);printf("n");void Huffmandeciphering(HuffmanCode HC,char *a,int n,HuffmanTree HT)/解密int input100=0;char c=' 'int num=0;int

23、 m=1;int t=0;printf("请输入你要解密的字符串n");int i=0;getchar();while(c!='n')c=getchar();inputi=(int)c-48;i+;num=i;for(i=1;t=0;i+)if(HTi.parent =0)t=i;/根结点的位置m=t;for(i=0;i<num;i+)if(inputi=0)m=HTm.lchild;if(inputi=1)m=HTm.rchild;if(HTm.lchild=0)printf("%c",am-1);m=t;void view()p

24、rintf("tt*n");printf("tt* 哈夫曼编码/译码器 *n");printf("tt*n");printf("tt*冀若含 刘洋 蒋佳烨*n");printf("tt* B 构造哈夫曼树 C 编码 D 译码 E 退出 *n");printf("tt* A 清屏 F 初始化 *n");printf("tt*n");printf("tt*必须先构建哈夫曼树*n");int main(int argc, char *argv

25、)view();char lu=' 'HuffmanCode HC;HuffmanTree HT;char *a;/存放字符int *w;int n;int i;char inp=' 'int inpt=0;char choice=' '/储存你要选择的功能选项a=(char*)malloc(n+2)*sizeof(char);w=(int*)malloc(n*sizeof(int);HT=(HuffmanTree)malloc(2*n)*sizeof(HTNode);HC=(HuffmanCode)malloc(n+1)*sizeof(char

26、*);while(1)printf("请选择你要执行的功能n");printf(">: ");scanf("%c",&choice);switch(choice)case 'a':case 'A':system("cls");view();getchar();break;case 'b':case 'B':printf("请输入字符集大小n");scanf("%d",&n);printf("请输入字符名和度数中间以空格隔开n");for(