哈夫曼编码译码器哈夫曼编码译码器学院班级: 信息工程学院软件1501 指导教师: 朱俊武小组成员: 刘洋蒋佳烨冀若含本人学号: 151303107 报告书写: 冀若含学生成绩:目录一、总体介绍·····························03-04二、详细设计·····························04-11三、运行测试·····························11-12四、课设总结·····························13-13五、附录代码·····························13-19一、总体介绍1.1任务概述我们小组做了两个版本，其中一个为文件操作版，另一个为键盘操作版。

两个版本都实现了哈夫曼编码/译码操做。

我主要负责的是构造哈夫曼树，给出各个字符的哈夫曼编码，加密操做，整个键盘操作版系统的代码重组、编辑。

开发的过程中使用了Codelite、Dev、Vc等软件。

参考书籍为《数据结构》（c语言版）。

其中文件操作版的具体实现为：○1能够实现对26个小写字母外加空格进行哈夫曼编码，并能够对一整篇文章（有小写字母和空格组成）进行加密，生成密码文件。

最后根据生成的密码翻译出原文并存档。

○2在使用程序时，使用者只需要对ToBetran文件进行原文的输入（使用小写字母或空格），加密和解密功能由程序自主来完成。

○3程序运行的过程中会输出进行编码的26个小写字母和空格（字符型），并输出其对应的权值（整型）。

还输出字符的编码及生成的密文。

最后输出解密后的原文。

键盘操作版为：○1要求从键盘输入字符集和字符的权值，大部分字符均可输入，需要各个字符的权值不能相同。

○2利用输入的权值建立哈夫曼树，得到每个字符的前缀编码。

○3输入字符串，程序对其进行加密。

○4输入密文（1010101……………..）对密文进行解密。

两个版本都利用了哈夫曼树解决问题，通过建立哈夫曼树，得出每个字符的独特前缀编码，也就是密文，然后利用密文对明文进行加密得到密文。

密文转换为明文则是通过对哈夫曼树的遍历。

（之前想开始构建哈夫编码译码曼树本系统的实现难点在于哈夫曼树的构造。

编码、译码功能的实现都是基于哈夫曼树的。

二、详细设计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 代码实现哈夫曼树和哈夫曼编码的储存表示typedef struct{int weight;int parent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组储存哈夫曼树typedef char* *HuffmanCode;//动态分配数组储存哈夫曼编码表void Select(HuffmanTree HT,int p,int *s1,int *s2)该函数的功能为：找出HT[1….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 *a)M=2*n-1开始为HT申请长度为m+1的内存空间给HT数组的前n个赋值为{*w，0，0，0}给HT数组的后n-1个赋值为{0，0，0，0}i=n+1Select（）HT[s1].parent=IHt[s2].parent=I;Ht[i],lchild=s1;Ht[i].rchild=s2;Ht[i].weight=HT[s1].weight +HT[s2].weight;i++;i<=m?YN weiHC指针分配空间小。

注：具体程序中加入了输出各个字符的哈夫曼编码的功能，在流程图没有显示。

没画完下面还有哟！！！！weiHC指针分配空间为cd分配纯储存空间Cd[n-1]=\0 i=1 Start=n-1C=IF=HT[I].PARENTHT[F].LCHILD==CYCD[--START]=0'NCd[--start]=1';C=f,f=HT[f].parentF!=0?YN为第i个字符分配空间复制cd到HCi<=N?N Free（cd）Yvoid *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("字符的个数过少\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;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';else cd[--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);}void Select(HuffmanTree HT,int p,int *s1,int *s2)详细设计：○1首先通过一个循环找出当前数组中weight最小的一个。

记录下它的序号。

○2也是一和一样的循环和算法。

加上一个if语句，如果循环到与第一次序号一样的那次，就continue跳过这次比较。

○3将得到的权值最小的两个传到s1和是s2指向的地址。

这就是哈夫曼树的构造和生成哈夫曼编码的过程。

详细代码：void Select(HuffmanTree HT,int p,int *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=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 编码（加密）void HuffmanEncryption(HuffmanCode HC,char *a,int n)此函数开始从键盘读入要加密的字符串i=0J=0Input[i]==a[j]Y输出HC[j+1]J++NJ<NYNI++I<LONY结束码在不同数组的对应关系，进行加密。