实验报告
哈夫曼编码及译码
班级：软件工程一班
学号：2220141524
姓名：孙正涛
1 问题描述
1.设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。
(1) 将权值数据存放在数据文件(文件名为data.txt，位于当前目录中)；
(2) 分别采用动态和静态存储结构; 初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树;
(3) 编码：利用建好的哈夫曼树生成哈夫曼编码；输出编码；
设计要求：
(1) 符合课题要求，实现相应功能；
(2) 要求界面友好美观，操作方便易行；
(3) 注意程序的实用性、安全性。
2 需求分析
编写此软件是为了实现一个利用哈夫曼算法的编码和译码系统。比如，再利用电报进行通讯时，需要将文字转换成由二进制的字符组成的字符串。比如需传送的电文为“A B A C C D A”假设将A,B,C,D分别编码为00、01、10、11.则上述电文遍为00010010101100，总长度为14位。但是在传送过程中，总希望长度能够尽可能的短，于是我们想采用长度不等的编码。但是这种编码必须遵循：任何一个字符的编码都不是另一个字符编码的前缀。
对此软件的要求：能够正确的使得对于输入的字符进行编码以及译码，并且是的在译码过程中不会出错，同时能够将编码以及译码的结果正确的存入文件当中。
3 概要设计
总体框图以及功能描述
4 详细设计
数据类型的定义
（1）哈夫曼树节点类型
struct hufmtreenode{ //哈弗曼树结点数据类型
char data;
float weight; //结点权值
int parent,lchild,rchild; //父结点，左、右孩子结点
};
（2）哈夫曼树类型
struct hufmtree{ //哈弗曼树数据类型
hufmtreenode *node; //结点数组（根据n的值动态分配）
int n; //叶子结点数
};
（3)哈夫曼编码数据类型
struct Codetype{ //哈弗曼编码数据类型
char *bits; //编码流数组，
int start;//编码实际在编码流数组里的开始位置
}
5 测试分析
(1)打开源文件统计各字符及权值信息并存入data.txt文件中
(2)将统计出的权值信息进行哈夫曼编码
（3）将编码内容存入CodeFile.txt文件中
（4）将CodeFile.txt文件中的内容译码
（5)成功译码把原字符信息存入DeCodeFile.txt文件中
（6）输入各字符及其权值
（7）将各字符的权值信息进行哈夫曼编码
（7）根据编码再进行译码工作
6 课程设计总结
课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程.随着科学技术发展的日新日异，当今计算机应用在生活中可以说得是无处不在。因此作为二十一世纪的大学来说掌握计算机开发技术是十分重要的。
回顾起此次课程设计，至今我仍感慨颇多，的确，自从拿到题目到完成整个编程，从理论到实践，在整整一个星期的日子里，可以学到很多很多的的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，这毕竟独立做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，比如说结构体……通过这次课程设计之后，一定把以前所学过的知识重新温故。
这次课程设计终于顺利完成了，在设计中遇到了很多编程问题，最后在谢老师的辛勤指导下，终于游逆而解。同时，在李玉蓉老师的《软件工程导论》课上我学得到很多实用的知识，在次我表示感谢！同时，对给过我帮助的所有同学和各位指导老师再次表示忠心的感谢！
附录（源程序清单）
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAXVAL 10000.0
struct hufmtreenode{//哈弗曼树结点数据类型
char data;
double weight;//结点权值
int parent,lchild,rchild;//父结点，左、右孩子结点
};
struct hufmtree{//哈弗曼树数据类型
hufmtreenode *node;//结点数组（根据n的值动态分配）
int n;//叶子结点数
};
struct Codetype{//哈弗曼编码数据类型
char *bits;//编码流数组，n为为哈夫曼树中叶子结点的数目，编码的长度不可能超过n
int start;//编码实际在编码流数组里的开始位置
};
void SortHufmtree(hufmtree *tree){//将哈夫曼树n个叶子结点由大到小排序
int i,j,k;
hufmtreenode temp;
if (tree==NULL)
return;
for (i=0;i<tree->n;i++)
{
k=i;
for(j=i+1;j<tree->n;j++)
if (tree->node[j].weight>tree->node[k].weight)
k=j;
if (k!=i)
{
temp=tree->node[i];
tree->node[i]=tree->node[k];
tree->node[k]=temp;
}
}
}
Codetype* HuffmanCode(hufmtree *tree){//哈弗曼编码的生成
int i,j,p,k;
Codetype *code;
if (tree==NULL)
return NULL;
code=(Codetype*)malloc(tree->n*sizeof(Codetype));
for (i=0;i<tree->n;i++)
{
printf("%c ",tree->node[i].data);//打印字符信息
code[i].bits=(char*)malloc(tree->n*sizeof(char));
code[i].start=tree->n-1;
j=i;
p=tree->node[i].parent;
while(p!=-1){
if (tree->node[p].lchild==j)
code[i].bits[code[i].start]='0';
else
code[i].bits[code[i].start]='1';
code[i].start--;
j=p;
p=tree->node[p].parent;
}
for (k=code[i].start+1;k<tree->n;k++)//打印字符编码
printf("%c",code[i].bits[k]);
printf("\n");
}
return code;
}
hufmtree* BuildHuffmanTree(hufmtree *tree){//构建叶子结点已初始化的哈夫曼树
//tree中所有叶子结点已初始化
int i,j,p1,p2,m;
float small1,small2;
m=2*(tree->n)-1;
for (i=tree->n;i<m;i++)//初始化所有非叶子结点
{
tree->node[i].parent=-1;
tree->node[i].lchild=-1;
tree->node[i].rchild=-1;
tree->node[i].weight=0.0;
}
for (i=tree->n;i<m;i++)//构建哈夫曼树
{
small1=small2=MAXVAL;
for (j=0;j<=i-1;j++)
{
if (tree->node[j].parent==-1 && tree->node[j].weight<=small1)
{
small1=tree->node[j].weight;
p1=j;
}
}
for (j=0;j<=i-1;j++)
{
if (tree->node[j].parent==-1 && tree->node[j].weight<=small2 && (j!=p1))
{
small2=tree->node[j].weight;
p2=j;
}
}
tree->node[p1].parent=tree->node[p2].parent=i;
tree->node[i].weight=tree->node[p1].weight+tree->node[p2].weight;
tree->node[i].lchild=p1;
tree->node[i].rchild=p2;
}
return tree;
}
hufmtree* CreateHuffmanTreeFromSourceFile(){//通过解析源文件建立哈夫曼树
FILE *textfile,*datafile;
char ch,sourcefilename[100];
int i,j=0,n=0;
float count[128]; //用于统计字符在源文件中出现的次数，27表示26个英文字母和1个空格字符
hufmtree *tree;
//打开一个源文件
printf("\n请输入源文件所在路径:\n");
scanf("%s",sourcefilename);
if ((textfile=fopen(sourcefilename,"r"))==NULL){
printf("\n找不到文件%s\n",sourcefilename);
return NULL;
}
for(i=0;i<128;i++)
count[i]=0;
//对源文件中各字符的个数统计
ch=fgetc(textfile);
while(!feof(textfile)){
for(i=0;i<128;i++)
if (ch==char(i)){
count[i]++;
break;
}
ch=fgetc(textfile);
}
//将统计结果写入权值信息文件data.txt中，并构建哈夫曼树
datafile=fopen("f:\\data.txt","w");
for (i=0;i<128;i++)
if (count[i]!=0)
n++;
fprintf(datafile,"%d\n",n);
tree=(hufmtree*)malloc(sizeof(hufmtree));
tree->node=(hufmtreenode*)malloc((2*n-1)*sizeof(hufmtreenode));
tree->n=n;
printf("\n源文件的字符集及其权值信息如下：\n");
for(i=0;i<128;i++)
if (count[i]!=0)
{
//fprintf(datafile,"%c%f\n",char(i),count[i]);
fprintf(datafile,"%c %.0f\n",char(i),count[i]);
printf("%c %.0f\n",char(i),count[i]);
tree->node[j].data=char(i);
tree->node[j].weight=count[i];
tree->node[j].parent=-1;
tree->node[j].lchild=-1;
tree->node[j].rchild=-1;
j++;
}
SortHufmtree(tree);
BuildHuffmanTree(tree);
fclose(textfile);
fclose(datafile);
printf("\n哈夫曼树建立完毕，已将权值信息保存至data.txt\n");
return tree;
}
hufmtree* CreateHuffmanTreeByInput(){//通过用户输入建立哈夫曼树
int n;
hufmtree *tree;
int i,m;
FILE *datafile;
tree=(hufmtree*)malloc(sizeof(hufmtree));
datafile=fopen("f:\\data.txt","w");
//由用户输入字符与权值信息并将其写入data.txt，同时进行哈夫曼树初始化
printf("请输入字符数：");
scanf("%d",&n);
if (n<=0)
{
printf("\n您的输入有误。\n");
return NULL;
}
tree->node=(hufmtreenode*)malloc((2*n-1)*sizeof(hufmtreenode));
tree->n=n;
m=2*n-1;
for (i=0;i<n;i++)
{
tree->node[i].parent=-1;
tree->node[i].lchild=-1;
tree->node[i].rchild=-1;
tree->node[i].weight=0.0;
}
fprintf(datafile,"%d\n",n);
for (i=0;i<n;i++)
{
printf("\n输入第%d个字符及其权值：",i+1);
tree->node[i].data=getche();
tree->node[i].weight=getche();
fprintf(datafile,"%c,%.0f\n",tree->node[i].data,tree->node[i].weight-48);
}
fclose(datafile);
//哈夫曼树构建
SortHufmtree(tree);
BuildHuffmanTree(tree);
printf("\n哈夫曼树建立完毕，已将权值信息保存至data.txt\n");
return tree;
}
hufmtree* CreateHuffmanTreeFromDataFile(){//通过读取权值信息文件建立哈夫曼树
FILE *datafile;
int i,n;
hufmtree *tree;
if ((datafile=fopen("f:\\data.txt","r"))==NULL){
printf("\n哈夫曼树尚未建立\n");
return NULL;
}
//哈夫曼树初始化
fscanf(datafile,"%d",&n);
fgetc(datafile);
tree=(hufmtree*)malloc(sizeof(hufmtree));
tree->node=(hufmtreenode*)malloc((2*n-1)*sizeof(hufmtreenode));
tree->n=n;
for (i=0;i<n;i++){
tree->node[i].data=fgetc(datafile);
fscanf(datafile,"%f\n",&tree->node[i].weight);
tree->node[i].parent=-1;
tree->node[i].lchild=-1;
tree->node[i].rchild=-1;
}
fclose(datafile);
//哈夫曼树构建
SortHufmtree(tree);
BuildHuffmanTree(tree);
return tree;
}
hufmtree* Encoding(hufmtree *tree){//对源文件进行编码并将其输出至新文件
FILE *textfile,*codefile;
char ch,sourcefilename[50];
int i,j;
Codetype *code;
if (tree==NULL)//如果内存中尚未建立哈夫曼树
{//试从data.txt中读取权值信息并建立哈夫曼树
tree=CreateHuffmanTreeFromDataFile();
if (tree==NULL)
return NULL;
}
//读取源文件
printf("\n请输入源文件所在路径:\n");
scanf("%s",sourcefilename);
if ((textfile=fopen(sourcefilename,"r"))==NULL){
printf("\n找不到文件%s\n",sourcefilename);
return NULL;
}
//打印源文件内容
printf("\n源文件的原文如下：\n");
ch=fgetc(textfile);
while(!feof(textfile)){
printf("%c",ch);
ch=fgetc(textfile);
}
//编码
printf("\n字符集的哈夫曼编码如下：\n");
code=HuffmanCode(tree);
//将源文件中各字符编码并写入codefile
codefile=fopen("f:\\CodeFile.txt","w");
fseek(textfile,0,SEEK_SET);
ch=fgetc(textfile);
while (!feof(textfile))
{
for(i=0;i<tree->n;i++)
if (ch==tree->node[i].data){
for(j=code[i].start+1;j<tree->n;j++)
fputc(code[i].bits[j],codefile);
break;
}
if (i==tree->n)//在哈夫曼树树中找不到与文本内容里对应的字符
{
printf("\n字符%c不在哈夫曼树中，不能正确编码。\n",ch);
fclose(codefile);
return NULL;
}
ch=fgetc(textfile);
}
fclose(codefile);
//提示成功信息并打印代码
printf("\n编码成功,已将代码写入CodeFile.txt,代码如下：\n");
codefile=fopen("f:\\CodeFile.txt","r");
ch=fgetc(codefile);
while(!feof(codefile)){
printf("%c",ch);
ch=fgetc(codefile);
}
printf("\n");
fclose(textfile);
fclose(codefile);
return tree;
}
void Decoding(hufmtree *tree)//对编码文件进行译码并将其输出至新文件
{
FILE *codefile,*decodefile;
char ch,codefilename[100];
int i;
if (tree==NULL)//如果尚未建立哈夫曼树
{//试从data.txt中读取权值信息并建立哈夫曼树
tree=CreateHuffmanTreeFromDataFile();
if (tree==NULL)
return ;
}
//打开编码文件
printf("\n请输入代码文件所在路径:\n");
scanf("%s",codefilename);
if ((codefile=fopen(codefilename,"r"))==NULL){
printf("\n找不到文件%s\n",codefilename);
return;
}
//打印编码文件的正文
printf("\n代码文件原文如下：\n");
ch=fgetc(codefile);
while(!feof(codefile)){
printf("%c",ch);
ch=fgetc(codefile);
}
//进行译码并将译文写入DecodeFile
decodefile=fopen("f:\\DecodeFile.txt","w");
fseek(codefile,0,SEEK_SET);
ch=fgetc(codefile);
while(!feof(codefile))
{
for(i=2*tree->n-2;tree->node[i].lchild>=0 && tree->node[i].rchild>=0 && ch!=EOF;)
{
if(ch=='0')
i = tree->node[i].lchild;
else if(ch=='1')
i = tree->node[i].rchild;
else{
//printf("\n存在异常字符%c，不能正确译码。\n",ch);
return ;
}
if (i==-1)//在哈夫曼树中找不到对应叶子结点
{
printf("\n编码与当前哈夫曼树结构不相符，不能正确译码。\n",ch);
fclose(decodefile);
return;
}
ch=fgetc(codefile);
}
if (tree->node[i].lchild>=0 && tree->node[i].rchild>=0)
{//寻找叶子结点的过程中突然读到了文件尾
printf("\n代码文件编码内容不完整，不能完整译码。\n",ch);
fclose(decodefile);
return;
}
fputc(tree->node[i].data,decodefile);
}
fclose(decodefile);
//提示成功信息并打印译文
printf("\n\n译码成功，译文已保存至DecodeFile.txt\n");
printf("译文如下：\n");
decodefile=fopen("f:\\DecodeFile.txt","r");
ch=fgetc(decodefile);
while(!feof(decodefile)){
printf("%c",ch);
ch=fgetc(decodefile);
}
printf("\n");
fclose(codefile);
fclose(decodefile);
}
void main(){
hufmtree *tree=NULL;
char choice;
do
{
system("cls");
printf("------------------\n");
printf(" 欢迎进入\n");
printf("哈夫曼编码译码系统\n");
printf("-*-*-*-*-*-*-*-*-*\n");
printf("(1)---读取解析源文件建立哈夫曼树\n");
printf("(2)---手动输入建立哈夫曼树\n");
printf("(3)---打印字符集的哈夫曼编码\n");
printf("(4)---对文本文件编码\n");
printf("(5)---对代码文件译码\n");
printf("(0)---退出系统\n");
printf("-*-*-*-*-*-*-*-*-*\n");
printf("请输入您的选择[0-5]:");
choice=getche();
printf("\n");
switch (choice)
{
case '1':
tree=CreateHuffmanTreeFromSourceFile();
break;
case '2':
tree=CreateHuffmanTreeByInput();
break;
case '3':
if (tree==NULL)
tree=CreateHuffmanTreeFromDataFile();
HuffmanCode(tree);
break;
case '4':
tree=Encoding(tree);
break;
case '5':
Decoding(tree);
break;
case '0':
exit(0);
break;
default:printf("无效的选项。\n");
}
printf("\n");
system("pause");
}while (choice!='0');
}