哈夫曼编码译码器实验报告
中北大学
数 据 结 构
课 程 设 计 说 明 书
2011年12月20日
目 录
1 问题描述 .............................................................. 错误！未定义书签。 2 需求分析 .............................................................. 错误！未定义书签。 3 概要设计 ................................................................................................ 1 3．1抽象数据类型定义 ..................................................................... 1 3．2总体框图以及功能描述 ............................................................. 2 4 详细设计 ................................................................................................ 2 4．1数据类型的定义 ......................................................................... 2 4．2主要模块的算法描述 ................................................................. 3 5 测试分析 ................................................................................................ 4 6 课程设计总结 ........................................................................................ 6 附录（源程序清单） ................................................................................ 7
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.则上述电文遍为[1**********]100，总长度为14位。但是在传送过程中，总希望长度能够尽可能的短，于是我们想采用长度不等的编码。但是这种编码必须遵循：任何一个字符的编码都不是另一个字符编码的前缀。
对此软件的要求：能够正确的使得对于输入的字符进行编码以及译码，并且是的在译码过程中不会出错，同时能够将编码以及译码的结果正确的存入文件当中。
3 概要设计
3．1抽象数据类型定义
ADT BinaryTree{
数据对象：D={ai|ai∈ElemSet,i=1,2,...,n, n≥0} 数据关系：
若D为空集，则称为空树。
若D仅为一个数据元素，则R为空集，否则R={H}，H是如下的二元关系： （1）再D中存在唯一的称为根的数据元素root，它在关系H下无前驱。 （2）若D-{root}空集，则存在一个划分D1，D2，···，Dm（m>0）。 （3）对应于D-{root}的划分，H-{}
有唯一的一个划分H1，H2，···，Hm（m>0）。
基本操作： InitTree(&T)
操作结果：构造空树T。 DestroyTree(&T) 初始条件：树T已存在。 操作结果：树T被销毁。 ClearTree(&T)
初始条件：树T已存在。 操作结果：将树T清为空栈。 TreeEmpty(T)
初始条件：树T已存在。
操作结果：若树T为空，则返回TRUE，否则FALSE。 TreeDepth(T)
初始条件:树T已存在。 操作结果：返回T的深度。 Root（T）
初始条件：树T已存在。 操作结果：返回树T的根。
3．2总体框图以及功能描述
4 详细设计
4．1数据类型的定义
（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;//编码实际在编码流数组里的开始位置 }
4．2主要模块的算法描述 （1)主函数：
void main()
Decoding(tree); //对代码文件译码
tree=Encoding(tree); //对文本文件编码
{
HuffmanCode(tree); //打印字符集的哈夫曼编码 printf("哈夫曼编码译码系统\n");
tree=CreateHuffmanTreeFromSourceFile();//读取文件建立哈树
tree=CreateHuffmanTreeByInput(); //手动输入建立哈夫曼树
} （2）构造哈夫曼树
hufmtree* BuildHuffmanTree(hufmtree *tree){//构建叶子结点已初始化的哈夫曼树
For(p=HT,i=1;i
*p={0,0,0,0}; For(;i
Select(HT,i-1,s1,s2);
HT[s1].parent=i; HT[s2].parent=i; HT[s1].parent=s1; HT[s1].parent=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight; } }
（3）利用哈夫曼编码算法哈夫曼编码 HuffmanCode(tree){
hc=(HuffmanCode)malloc((n+1*sizeof(char *)) cd=(char *)malloc(n*sizeof(char)); cd[n-1]="\0"; for(c=i;i
for(c=i;f=HT[i].parent;f!=0;c=f,f =HT[f].parent) If(HT[f].lchild==c) cd[--start]='\0'; HC[i]=(car *)malloc((n-start)*sizeof(char)); Strcpy(HC[i],&cd[start]); }
5 测试分析
(1)打开源文件统计各字符及权值信息并存入data.txt文件中
(2)
将统计出的权值信息进行哈夫曼编码
（3）将编码内容存入CodeFile.txt文件中
（4）将CodeFile.txt文件中的内容译码
（5)成功译码把原字符信息存入DeCodeFile.txt文件中
（6）输入各字符及其权值
（7）将各字符的权值信息进行哈夫曼编码
（7）根据编码再进行译码工作
6 课程设计总结
课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问
题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程.随着科学技术发展的日新日异，当今计算机应用在生活中可以说得是无处不在。因此作为二十一世纪的大学来说掌握计算机开发技术是十分重要的。
回顾起此次课程设计，至今我仍感慨颇多，的确，自从拿到题目到完成
整个编程，从理论到实践，在整整一个星期的日子里，可以学到很多很多的的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有
理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，这毕竟独立做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，比如说结构体„„通过这次课程设计之后，一定把以前所学过的知识重新温故。
这次课程设计终于顺利完成了，在设计中遇到了很多编程问题，最后在
谢老师的辛勤指导下，终于游逆而解。同时，在李玉蓉老师的《软件工程导论》课上我学得到很多实用的知识，在次我表示感谢！同时，对给过我帮助的所有同学和各位指导老师再次表示忠心的感谢！
附录（源程序清单）
#include #include #include #define MAXVAL 10000.0
struct hufmtreenode{//哈弗曼树结点数据类型 };
struct hufmtree{//哈弗曼树数据类型 };
struct Codetype{//哈弗曼编码数据类型
char *bits;//编码流数组，n为为哈夫曼树中叶子结点的数目，编码的长hufmtreenode *node;//结点数组（根据n的值动态分配） int n;//叶子结点数 char data;
double weight;//结点权值
int parent,lchild,rchild;//父结点，左、右孩子结点
度不可能超过n
int start;//编码实际在编码流数组里的开始位置
void SortHufmtree(hufmtree *tree){//将哈夫曼树n个叶子结点由大到小排序
}
Codetype* HuffmanCode(hufmtree *tree){//哈弗曼编码的生成
int i,j,p,k; Codetype *code; if (tree==NULL) return NULL; int i,j,k; hufmtreenode temp; if (tree==NULL) return; for (i=0;in;i++) { } k=i; for(j=i+1;jn;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; code=(Codetype*)malloc(tree->n*sizeof(Codetype)); for (i=0;in;i++) { printf("%c ",tree->node[i].data);//打印字符信息
} } code[i].start=tree->n-1; j=i; p=tree->node[i].parent; while(p!=-1){ } for (k=code[i].start+1;kn;k++)//打印字符编码 printf("%c",code[i].bits[k]); 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; 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;inode[i].parent=-1; tree->node[i].lchild=-1;
tree->node[i].weight=0.0; } for (i=tree->n;inode[j].parent==-1 &&
tree->node[j].weight
} for (j=0;jnode[j].weight; p1=j; if (tree->node[j].parent==-1 && tree->node[j].weight
tree->node[i].weight=tree->node[p1].weight+tree->node[p2].weight; tree->node[i].lchild=p1; tree->node[i].rchild=p2; } tree->node[p1].parent=tree->node[p2].parent=i; { small2=tree->node[j].weight; p2=j; }
} return tree;
hufmtree* CreateHuffmanTreeFromSourceFile(){//通过解析源文件建立哈夫曼树
FILE *textfile,*datafile; char ch,sourcefilename[100]; int i,j=0,n=0; float count[128]; //用于统计字符在源文件中出现的次数，27表示26个英文字母和1个空格字符
//对源文件中各字符的个数统计 ch=fgetc(textfile); while(!feof(textfile)){ for(i=0;i
} ch=fgetc(textfile); } //将统计结果写入权值信息文件data.txt中，并构建哈夫曼树 datafile=fopen("f:\\data.txt","w"); for (i=0;inode=(hufmtreenode*)malloc((2*n-1)*sizeof(hufmtreenode)); tree->n=n; printf("\n源文件的字符集及其权值信息如下：\n"); for(i=0;inode[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(){//通过用户输入建立哈夫曼树
//由用户输入字符与权值信息并将其写入data.txt，同时进行哈夫曼树初int n; hufmtree *tree; int i,m; FILE *datafile; tree=(hufmtree*)malloc(sizeof(hufmtree)); datafile=fopen("f:\\data.txt","w"); 始化
printf("请输入字符数："); scanf("%d",&n); if (nnode=(hufmtreenode*)malloc((2*n-1)*sizeof(hufmtreenode)); tree->n=n; m=2*n-1; printf("\n您的输入有误。\n"); return NULL;
{ } fprintf(datafile,"%d\n",n); for (i=0;inode[i].data=getche(); tree->node[i].weight=getche(); tree->node[i].parent=-1; tree->node[i].lchild=-1; tree->node[i].rchild=-1; tree->node[i].weight=0.0; fprintf(datafile,"%c,%.0f\n",tree->node[i].data,tree->node[i].weight-48);
}
hufmtree* CreateHuffmanTreeFromDataFile(){//通过读取权值信息文件建立哈夫曼树
FILE *datafile; int i,n; //哈夫曼树构建 SortHufmtree(tree); BuildHuffmanTree(tree); printf("\n哈夫曼树建立完毕，已将权值信息保存至data.txt\n"); return tree; } fclose(datafile);
}
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;inode[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; //哈夫曼树构建 SortHufmtree(tree); BuildHuffmanTree(tree); return tree;
hufmtree* Encoding(hufmtree *tree){//对源文件进行编码并将其输出至新文
//读取源文件 printf("\n请输入源文件所在路径:\n"); scanf("%s",sourcefilename); if ((textfile=fopen(sourcefilename,"r"))==NULL){ } //打印源文件内容 printf("\n源文件的原文如下：\n"); ch=fgetc(textfile); while(!feof(textfile)){ printf("%c",ch); ch=fgetc(textfile); printf("\n找不到文件%s\n",sourcefilename); return NULL; 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"); code=HuffmanCode(tree); //将源文件中各字符编码并写入codefile codefile=fopen("f:\\CodeFile.txt","w"); fseek(textfile,0,SEEK_SET); ch=fgetc(textfile); while (!feof(textfile)) { } fclose(codefile); for(i=0;in;i++) if (ch==tree->node[i].data){ } for(j=code[i].start+1;jn;j++) fputc(code[i].bits[j],codefile); break; if (i==tree->n)//在哈夫曼树树中找不到与文本内容里对应的字符 { } ch=fgetc(textfile); printf("\n字符%c不在哈夫曼树中，不能正确编码。\n",ch); fclose(codefile); return NULL; //提示成功信息并打印代码 printf("\n编码成功,已将代码写入CodeFile.txt,代码如下：\n"); codefile=fopen("f:\\CodeFile.txt","r");
}
while(!feof(codefile)){ } printf("\n"); fclose(textfile); fclose(codefile); return tree; printf("%c",ch); ch=fgetc(codefile);
void Decoding(hufmtree *tree)//对编码文件进行译码并将其输出至新文件 {
//打开编码文件 printf("\n请输入代码文件所在路径:\n"); scanf("%s",codefilename); if ((codefile=fopen(codefilename,"r"))==NULL){ printf("\n找不到文件%s\n",codefilename); if (tree==NULL)//如果尚未建立哈夫曼树 {//试从data.txt中读取权值信息并建立哈夫曼树 } tree=CreateHuffmanTreeFromDataFile(); if (tree==NULL) return ; FILE *codefile,*decodefile; char ch,codefilename[100]; int i;
} //打印编码文件的正文 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{ } if (i==-1)//在哈夫曼树中找不到对应叶子结点 //printf("\n存在异常字符%c，不能正确译码。\n",ch); return ;
printf("\n编码与当前哈夫曼树结构不相符，不能正确译码。\n",ch);
//提示成功信息并打印译文 printf("\n\n译码成功，译文已保存至DecodeFile.txt\n"); printf("译文如下：\n"); decodefile=fopen("f:\\DecodeFile.txt","r"); ch=fgetc(decodefile); while(!feof(decodefile)){ } printf("\n"); fclose(codefile); printf("%c",ch); ch=fgetc(decodefile); } fclose(decodefile); } if (tree->node[i].lchild>=0 && tree->node[i].rchild>=0) {//寻找叶子结点的过程中突然读到了文件尾 } fputc(tree->node[i].data,decodefile); printf("\n代码文件编码内容不完整，不能完整译码。\n",ch); fclose(decodefile); return; } ch=fgetc(codefile); fclose(decodefile); return;
}
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':
} 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');