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

附录全部代码：
#include
#include
#include
#include
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;i24、 ';
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;im=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 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