哈夫曼编码译码器
学院班级: 信息工程学院软件1501
****: ***
小组成员: 刘洋蒋佳烨冀若含
本人学号: *********
报告书写: 冀若含
学生成绩:
目录
一、总体介绍·····························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)
小。
注：具体程序中加入了输出各个字符的哈夫曼编码的功能，在流程图没有显示。
没画完下面还有哟！！！！
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最小的一个。记录下它
