哈夫曼编码译码器.docx

哈夫曼编码译码器

学院班级: 信息工程学院 软件1501
指导教师: 朱俊武
小组成员: 刘洋 蒋佳烨 冀若含
本人学号: 151303107
报告书写: 冀若含
学生成绩:

目录

一、总体介绍·····························03-04

二、详细设计·····························04-11

三、运行测试·····························11-12

四、课设总结·····························13-13

五、附录代码·····························13-19

一、总体介绍
1.1任务概述
我们小组做了两个版本，其中一个为文件操作版，另一个为键盘操作版。两个版本都实现了哈夫曼编码/译码操做。我主要负责的是构造哈夫曼树，给出各个字符的哈夫曼编码，加密操做，整个键盘操作版系统的代码重组、编辑。开发的过程中使用了Codelite、Dev、Vc等软件。参考书籍为《数据结构》（c语言版）。
其中文件操作版的具体实现为：
能够实现对26个小写字母外加空格进行哈夫曼编码，并能够对一整篇文章（有小写字母和空格组成）进行加密，生成密码文件。最后根据生成的密码翻译出原文并存档。
在使用程序时，使用者只需要对ToBetran文件进行原文的输入（使用小写字母或空格），加密和解密功能由程序自主来完成。
程序运行的过程中会输出进行编码的26个小写字母和空格（字符型），并输出其对应的权值（整型）。还输出字符的编码及生成的密文。最后输出解密后的原文。
键盘操作版为：
要求从键盘输入字符集和字符的权值，大部分字符均可输入，需要各个字符的权值不能相同。
利用输入的权值建立哈夫曼树，得到每个字符的前缀编码。
输入字符串，程序对其进行加密。
输入密文（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 代码实现
哈夫曼树和哈夫曼编码的储存表示
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)

指针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("字符的个数过少\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)
详细设计：
首先通过一个循环找出当前数组中weight最小的一个。记录下它的序号。
也是一和一样的循环和算法。加上一个if语句，如果循环到与第一次序号一样的那次，就continue跳过这次比较。
将得到的权值最小的两个传到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)此函数为加密函数。该加密函数的流程图如下：

该功能的实现就是通过一个简单的查找，通过字符与字符的哈夫曼编码在不同数组的对应关系，进行加密。Input[]储存输入的字符串。Lo为输入的字符串长度，n为原字符集的字符个数。
详细代码如下：
void HuffmanEncryption(HuffmanCode HC,char *a,int n){
char input[100];
int i=0,j=0;
char lu=' ';
int lo=0;//要加密的字符串的长度
char c;
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>
typedef struct{
int weight;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char* *HuffmanCode;
void Select(HuffmanTree HT,int p,int *s1,int *s2)//i为遍历长度，big
{
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;
}
}
}
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("字符的个数过少\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 HuffmanEncryption(HuffmanCode HC,char *a,int n){
char input[100];
int i=0,j=0;
char lu=' ';
int lo=0;//要加密的字符串的长度
char c;
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");
}
void Huffmandeciphering(HuffmanCode HC,char *a,int n,HuffmanTree HT)//解密
{
int input[100]={0};
char c=' ';
int num=0;
int m=1;
int t=0;
printf("请输入你要解密的字符串\n");
int i=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;
}
}
}
void view(){
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");
}
int main(int argc, char **argv)
{
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*));
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(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':case 'd':
Huffmandeciphering(HC,a,n,HT);//解密
break;
case 'F':case 'f':
printf("你确定要初始化吗Y or N\n");
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=(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;
}
20 / 20