《哈夫曼编码译码器(共20页).docx》由会员分享,可在线阅读,更多相关《哈夫曼编码译码器(共20页).docx(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(&
27、quot;请输入字符名和度数中间以空格隔开n");for(i=0;i<n;i+)while(lu=getchar()!='n'&&lu!=EOF);scanf("%c %d",&inp,&inpt);*(a+i)=inp;*(w+i)=inpt;HuffmanCoding(HT,HC,w,n,a);/构建哈夫曼树getchar();break;case 'c':case 'C':HuffmanEncryption(HC,a,n);/加密break;case 'D'
28、:case 'd':Huffmandeciphering(HC,a,n,HT);/解密break;case 'F':case 'f':printf("你确定要初始化吗Y or Nn");char yn;getchar();scanf("%c",&yn);if(yn='Y')free(a);free(w);free(HT);free(HC);lu=' 'inp=' 'inpt=0;a=(char*)malloc(n+2)*sizeof(char);w=(
29、int*)malloc(n*sizeof(int);HT=(HuffmanTree)malloc(2*n)*sizeof(HTNode);HC=(HuffmanCode)malloc(n+1)*sizeof(char*);printf("初始化完成n");getchar();break;else getchar();break;case 'E':case 'e':goto LAST;default:printf("没有这个选型哟n");system("pause");LAST:return 0;专心-专注-专业
限制150内