哈夫曼编码译码器

...wd......wd......wd...哈夫曼编码译码器学院班级:信息工程学院软件1501指导教师:朱俊武小组成员:刘洋蒋佳烨冀假设含本人学号:151303107报告书写:冀假设含学生成绩:目录一、总体介绍·····························03-04二、详细设计·····························04-11三、运行测试·····························11-12四、课设总结·····························13-13五、附录代码·····························13-19一、总体介绍1.1任务概述我们小组做了两个版本，其中一个为文件操作版，另一个为键盘操作版。两个版本都实现了哈夫曼编码/译码操做。我主要负责的是构造哈夫曼树，给出各个字符的哈夫曼编码，加密操做，整个键盘操作版系统的代码重组、编辑。开发的过程中使用了Codelite、Dev、Vc等软件。参考书籍为《数据构造》〔c语言版〕。其中文件操作版的具体实现为：eq\o\ac(○,1)能够实现对26个小写字母外加空格进展哈夫曼编码，并能够对一整篇文章〔有小写字母和空格组成〕进展加密，生成密码文件。最后根据生成的密码翻译出原文并存档。eq\o\ac(○,2)在使用程序时，使用者只需要对ToBetran文件进展原文的输入〔使用小写字母或空格〕，加密和解密功能由程序自主来完成。eq\o\ac(○,3)程序运行的过程中会输出进展编码的26个小写字母和空格〔字符型〕，并输出其对应的权值〔整型〕。还输出字符的编码及生成的密文。最后输出解密后的原文。键盘操作版为：eq\o\ac(○,1)要求从键盘输入字符集和字符的权值，大局部字符均可输入，需要各个字符的权值不能一样。eq\o\ac(○,2)利用输入的权值建设哈夫曼树，得到每个字符的前缀编码。eq\o\ac(○,3)输入字符串，程序对其进展加密。eq\o\ac(○,4)输入密文〔1010101……………..〕对密文进展解密。 两个版本都利用了哈夫曼树解决问题，通过建设哈夫曼树，得出每个字符的独特前缀编码，也就是密文，然后利用密文对明文进展加密得到密文。密文转换为明文则是通过对哈夫曼树的遍历。〔之前想过字符串的匹配得到明文但是算法太为复杂〕。1.2系统功能框图本系统分为三个大的模块：构造哈夫曼树，编码，译码。1.3功能难点 本系统的实现难点在于哈夫曼树的构造。编码、译码功能的实现都是基于哈夫曼树的。二、详细设计2.1哈夫曼树的构造哈夫曼树，又称最优树，是一类带权路径长度最短的树，有着广泛的应用。哈夫曼树的构造过程如下：1.初始化：根据给定的n个权值{w1,w2,…wn}构成n棵二叉树的集合F={T1,T2,..,Tn}，其中每棵二叉树Ti中只有一个带权wi的根节点，左右子树均空。2.找最小树：在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。3.删除与参加：在F中删除这两棵树，并将新的二叉树参加F中。4.判断：重复前两步〔2和3〕，直到F中只含有一棵树为止。该树即为哈夫曼树。2.2代码实现哈夫曼树和哈夫曼编码的储存表示typedefstruct{ intweight; intparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组储存哈夫曼树typedefchar**HuffmanCode;//动态分配数组储存哈夫曼编码表voidSelect(HuffmanTreeHT,intp,int*s1,int*s2)该函数的功能为：找出HT[1….i-1]中parent为0且weight最小的两个结点，其序号为s1，s2。voidHuffmanCoding(HuffmanTreeHT,HuffmanCodeHC,int*w,intn,char*a)该函数的功能为构造哈夫曼树HT，并求出n个字符的哈夫曼编码HC。以下为两个函数的流程图或详细设计。voidHuffmanCoding(HuffmanTreeHT,HuffmanCodeHC,int*w,intn,char*a)指针a指向输入的字符集，指针w指向字符集的度，n为字符集的大小。注：具体程序中参加了输出各个字符的哈夫曼编码的功能，在流程图没有显示。没画完下面还有哟！！！！详细代码：voidHuffmanCoding(HuffmanTreeHT,HuffmanCodeHC,int*w,intn,char*a){ intm=0;intc;intf; intstart; char*cd; int*s1; int*s2; inti; s1=(int*)malloc(sizeof(int)); s2=(int*)malloc(sizeof(int)); m=2*n-1; if(n<=1) { printf("字符的个数过少\n"); return; } HuffmanTreep; 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; HT[i].lchild=*s1;HT[i].rchild=*s2; HT[i].weight=HT[*s1].weight+HT[*s2].weight; } cd=(char*)malloc(n*sizeof(char)); cd[n-1]='\0'; for(i=1;i<=n;++i){ start=n-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild==c)cd[--start]='0'; elsecd[--start]='1'; HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); printf("%c",*a); a++; printf("%s\n",HC[i]); } free(cd);}voidSelect(HuffmanTreeHT,intp,int*s1,int*s2)详细设计：eq\o\ac(○,1)首先通过一个循环找出当前数组中weight最小的一个。记录下它的序号。eq\o\ac(○,2)也是一和一样的循环和算法。加上一个if语句，如果循环到与第一次序号一样的那次，就continue跳过这次比拟。eq\o\ac(○,3)将得到的权值最小的两个传到s1和是s2指向的地址。这就是哈夫曼树的构造和生成哈夫曼编码的过程。详细代码：voidSelect(HuffmanTreeHT,intp,int*s1,int*s2)//i为遍历长度{ inti=1; intx=0; inty=0; intmin=1000; intmin1=1000; intv=1; *s1=1;*s2=1; for(i=1;i<=p;i++) { x=HT[i].parent; y=HT[i].weight; if(x==0&&min>y) { min=HT[i].weight; *s1=i;v=i; } } for(i=1;i<=p;i++){ x=HT[i].parent; y=HT[i].weight; if(i==v) continue; if(x==0&&min1>=y) { min1=HT[i].weight; *s2=i; } }}2.3编码〔加密〕voidHuffmanEncryption(HuffmanCodeHC,char*a,intn)此函数为加密函数。该加密函数的流程图如下：该功能的实现就是通过一个简单的查找，通过字符与字符的哈夫曼编码在不同数组的对应关系，进展加密。Input[]储存输入的字符串。Lo为输入的字符串长度，n为原字符集的字符个数。详细代码如下：voidHuffmanEncryption(HuffmanCodeHC,char*a,intn){ charinput[100]; inti=0,j=0; charlu=''; intlo=0;//要加密的字符串的长度 charc; printf("请输入你要加密的字符串\n"); while((lu=getchar()!='\n'&&lu!=EOF)) ; c=getchar(); while(c!='\n'){ input[i]=c; i++; c=getchar(); } lo=i; for(i=0;i<lo;i++){ for(j=0;j<n;j++) { if(input[i]==a[j]) printf("%s",HC[j+1]); } } printf("\n");}三、运行测试菜单界面：构造哈夫曼树：编码：译码：密钥：译码测试：四、总结 经过几天的设计与编码我们小组终于完成了两个不同的版本的哈夫曼编码译码器。虽然两个系统大局部的算法一样，但是也算我们的尝试。美中缺乏的是我们没能把两个版本的系统融合起来。开发过程中遇到的最大的问题就是输入输出流的问题。因为是从键盘输入数据的所以难免会遇到这种问题。我通过输入流的过滤解决了此问题。通过这几天的实验，加深了我对哈夫曼树的理解，也加强了自己的动手能力。数据构造这门课程还有很多很多的东西，我们仍应该继续努力。附录全部代码：#include<stdio.h>#include<stdlib.h>#include<string.h>#include<windows.h>typedefstruct{ intweight; intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;voidSelect(HuffmanTreeHT,intp,int*s1,int*s2)//i为遍历长度，big{ inti=1; intx=0; inty=0; intmin=1000; intmin1=1000; intv=1; *s1=1;*s2=1; for(i=1;i<=p;i++) { x=HT[i].parent; y=HT[i].weight; if(x==0&&min>y) { min=HT[i].weight; *s1=i;v=i; } } for(i=1;i<=p;i++){ x=HT[i].parent; y=HT[i].weight; if(i==v) continue; if(x==0&&min1>=y) { min1=HT[i].weight; *s2=i; } }}voidHuffmanCoding(HuffmanTreeHT,HuffmanCodeHC,int*w,intn,char*a){ intm=0;intc;intf; intstart; char*cd; int*s1; int*s2; inti; s1=(int*)malloc(sizeof(int)); s2=(int*)malloc(sizeof(int)); m=2*n-1; if(n<=1) { printf("字符的个数过少\n"); return; } HuffmanTreep; 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; HT[i].lchild=*s1;HT[i].rchild=*s2; HT[i].weight=HT[*s1].weight+HT[*s2].weight; } cd=(char*)malloc(n*sizeof(char)); cd[n-1]='\0'; for(i=1;i<=n;++i){ start=n-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild==c)cd[--start]='0'; elsecd[--start]='1'; HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); printf("%c",*a); a++; printf("%s\n",HC[i]); } free(cd);}voidHuffmanEncryption(HuffmanCodeHC,char*a,intn){ charinput[100]; inti=0,j=0; charlu=''; intlo=0;//要加密的字符串的长度 charc; printf("请输入你要加密的字符串\n"); while((lu=getchar()!='\n'&&lu!=EOF)) ; c=getchar(); while(c!='\n'){ input[i]=c; i++; c=getchar(); } lo=i; for(i=0;i<lo;i++){ for(j=0;j<n;j++) { if(input[i]==a[j]) printf("%s",HC[j+1]); } } printf("\n");}voidHuffmandeciphering(HuffmanCodeHC,char*a,intn,HuffmanTreeHT)//解密{ intinput[100]={0}; charc=''; intnum=0; intm=1; intt=0; printf("请输入你要解密的字符串\n"); inti=0; getchar(); while(c!='\n'){ c=getchar(); input[i]=(int)c-48; i++; } num=i; for(i=1;t==0;i++) { if(HT[i].parent==0) { t=i;//根结点的位置 } } m=t; for(i=0;i<num;i++){ if(input[i]==0) m=HT[m].lchild; if(input[i]==1) m=HT[m].rchild; if(HT[m].lchild==0){ printf("%c",a[m-1]); m=t; } }}voidview(){ printf("\t\t******************************************\n"); printf("\t\t***哈夫曼编码/译码器***\n"); printf("\t\t******************************************\n"); printf("\t\t***********冀假设含刘洋蒋佳烨*************\n"); printf("\t\t*B构造哈夫曼树C编码D译码E退出*\n"); printf("\t\t********A清屏F初始化************\n"); printf("\t\t******************************************\n"); printf("\t\t**********必须先构建哈夫曼树**************\n");}intmain(intargc,char**argv){ view(); charlu=''; HuffmanCodeHC; HuffmanTreeHT; char*a;//存放字符 int*w; intn; inti; charinp=''; intinpt=0; charchoice='';//储存你要选择的功能选项 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*)); 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("请输入字符名和