哈夫曼树编码译码实验报告

一、 实验题目：哈夫曼编/译码系及其应用 二、 实验地点： 三、 实验目的： 1.掌握哈夫曼树的概念、存储结构 2.掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算 3.熟练掌握二叉树的应用 四、 实验内容： 实现哈夫曼树的生成，完成哈夫曼编/译码的输出。 1.初始化，从数据文件DataFile.data中读入字符及每个字符的权值，建立哈夫曼树HuffTree； 2.编码，用已建好的哈夫曼树，对文件ToBeTran.data中的文本进行编码形成报文，将报文写在文件Code.text中； 3.译码，利用已建好的哈夫曼树，对文件CodeFile.data中的代码进行解码形成原文，结果存入文件Textfile.txt中； 4.输出，输出DataFile.data中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.data及其报文Code.text；输出CodeFile.data及其原文Textfile.txt。 编写主程序，实现对各不同的算法调用。 五、 实验环境（使用的软件）： Visaul C+6.0 六、 实验步骤及操作： 打开VC++6.0创建工程/Win32 Console Application，输入工程名：哈夫曼树，新建三个.h文件一个.cpp文件 1．将一些常量定义，系统函数原型声明和类型（Status）重定义,结果状态代码等放在一个头文件中:取名为huffermanpubuse.h。 #include #include #include /* malloc()等*/ #include /* INT_MAX 等*/ #include /* EOF(=^Z 或F6),NULL */ #include /* atoi() */ #include /* eof() */ #include /* floor(),ceil(),abs() */ #include /* exit() */

1

/* 函数结果状态代码*/ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 /* #define OVERFLOW -2 因为在math. h 中已定义OVERFLOW 的值为3,故去掉此行*/ typedef int Status; /* Status 是函数的类型,其值是函数结果状态代码，如OK 等*/ typedef int Boolean; /* Boolean 是布尔类型,其值是TRUE 或FALSE */ 2．将哈夫曼树存储结构定义放在一个头文件：取名为huffermandef.h。 typedef struct {char ch; unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树*/ typedef char **HuffmanCode; /* 动态分配数组存储赫夫曼编码表*/ 3.将哈夫曼树的基本操作算法也集中放在一个文件之中，取名为huffermanalgo.h。 int min1(HuffmanTree t,int i) { /* 函数void select()调用*/ int j,flag; unsigned int k=UINT_MAX; /* 取k 为不小于可能的值*/ for(j=1;j<=i;j++) if(t[j].weight*s2) { j=*s1; *s1=*s2; 2

*s2=j; } } void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,char *ch,int n) /* 算法6.12 */ { /* w 存放n 个字符的权值(均>0),构造赫夫曼树HT,并求出n 个字符的赫夫曼编码HC */ int m,i,j,s1,s2,start; unsigned c,f; HuffmanTree p; char *cd; if(n<=1) return; m=2*n-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /* 0 号单元未用*/ for(p=HT+1,i=1;i<=n;++i,++p,++w,++ch) { (*p).ch=*ch; (*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; } for(;i<=m;++i,++p) {(*p).ch='*'; (*p).parent=0; } for(i=n+1,j=1;i<=m;++i,j++) /* 建赫夫曼树*/ { /* 在HT[1~i-1]中选择parent 为0 且weight 最小的两个结点,其序号分别为s1 和s2 */ select(HT,i-1,&s1,&s2); printf(\"第%d次比较min1与min2:%d %d\printf(\"\\n\"); HT[s1].parent=HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; }

3

/* 从叶子到根逆向求每个字符的赫夫曼编码*/ HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); /* 分配n 个字符编码的头指针向量([0]不用) */ 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)); /* 为第i 个字符编码分配空间*/ strcpy(HC[i],&cd[start]); /* 从cd 复制编码(串)到HC */ } free(cd); /* 释放工作空间*/ } void ReadDataFile(char *fileName1,int *wt,char *chh)//读初始化文件内容 { FILE *fp1; char ch;int w,i=0; if((fp1=fopen(fileName1,\"r\"))==NULL) { printf(\"\\nerror on open %s!\ exit(1); } printf(\"\\n文件内容：\\n\"); while(!feof(fp1)) { fscanf(fp1,\"%c\ if(ch=='\\n') continue; //读到换行符，跳过，读下一行 chh[i]=ch;

4

printf(\"ch=%c \ fscanf(fp1,\"%5d\中的格式化要加\\n,文件指针才会指向下一行 wt[i]=w; printf(\"weight= %5d\\n\ i++; } fclose(fp1); } void WriteDataFile(char *fileName1)//将初始化信息写入文件中 { FILE *fp1; char c;int weight; if((fp1=fopen(fileName1,\"w\"))==NULL) { printf(\"\\nerror on open %s!\ exit(1); } printf(\"请输入相关字符及字符的权值,#结束:\\n\"); c=getchar(); while((c=getchar())!='#') { fprintf(fp1,\"%c\将字符写入文件 scanf(\"%d\ fprintf(fp1,\"%5d\\n\将字符的权值写入文件，采用fprintf格式化写入 } fclose(fp1); } void WriteToBeTran(char *fileName2)//将初始化信息写入文件中 { FILE *fp2; char ch; int i=0; if((fp2=fopen(fileName2,\"w\"))==NULL) { printf(\"\\nerror on open %s!\

5

exit(1); } printf(\"请输入需要编译的文本，#结束：\\n\"); ch=getchar(); ch=getchar(); while(ch!='#') { fputc(ch,fp2); ch=getchar(); } putchar(10); fclose(fp2); } void ReadToBeTran(char *fileName2,char str[])//读初始化文件内容 { FILE *fp2; char ch;int i=0; if((fp2=fopen(fileName2,\"r\"))==NULL) { printf(\"\\nerror on open %s!\ exit(1); } while(!feof(fp2)) { fscanf(fp2,\"%c\ if(ch=='\\n') continue; //读到换行符，跳过，读下一行 str[i++]=ch; } str[i]='\\0'; fclose(fp2); } void WriteCode(char *fileName3,char *fileName4, HuffmanTree &HT,HuffmanCode &HC,int n) {FILE *fp3,*fp4; char ch; int i;

6

if((fp3=fopen(fileName3,\"r\"))==NULL) {printf(\"\\n error on open %s!\exit(0); } if((fp4=fopen(fileName4,\"w\"))==NULL) {printf(\"\\n error on open %s!\exit(0); } while(!feof(fp3)) { ch=fgetc(fp3); for(i=1;i<=n;i++) if(ch==HT[i].ch) fprintf(fp4,\"%s\} fclose(fp3); fclose(fp4); } void ReadCode(char *fileName4) {FILE *fp4; char ch; if((fp4=fopen(fileName4,\"r\"))==NULL) {printf(\"\\n error on open %s!\exit(0); } printf(\"\\n输出编码后的文件内容:\\n\"); while(!feof(fp4)) { ch=fgetc(fp4); printf(\"%c\} fclose(fp4); printf(\"\\n\"); } void yima(HuffmanTree &HT,int n,char str4[],char hh[])

7

{int i,j,m=0; for(i=0,j=2*n-1;str4[i]!='\\0';i++) { if(str4[i]=='0'&&HT[j].lchild!=0) {j=HT[j].lchild; if(HT[j].lchild==0||HT[j].rchild==0) {hh[m++]=HT[j].ch;j=2*n-1;} } else if(str4[i]=='1'&&HT[j].rchild!=0) {j=HT[j].rchild; if(HT[j].lchild==0||HT[j].rchild==0) {hh[m++]=HT[j].ch;j=2*n-1;} } } hh[m]='\\0'; } void WriteCodeFile(char *fileName5)//将初始化信息写入文件中 { FILE *fp5; char ch; int i=0; if((fp5=fopen(fileName5,\"w\"))==NULL) { printf(\"\\nerror on open %s!\ exit(1); } printf(\"请输入需要译的代码，#结束：\\n\"); ch=getchar(); ch=getchar(); while(ch!='#') { fputc(ch,fp5); ch=getchar(); } putchar(10);

8

fclose(fp5); } void ReadCodeFile(char *fileName5,char str4[])//读初始化文件内容 { FILE *fp5; char ch;int i=0; if((fp5=fopen(fileName5,\"r\"))==NULL) { printf(\"\\nerror on open %s!\ exit(1); } while(!feof(fp5)) { ch=fgetc(fp5); str4[i++]=ch; } str4[i]='\\0'; fclose(fp5); } void WriteTextFile(char *fileName6,char hh[]) {FILE *fp6; char ch; int i; if((fp6=fopen(fileName6,\"w\"))==NULL) {printf(\"\\n error on open %s!\exit(0); } for(i=0;hh[i]!='\\0';i++) {ch=hh[i]; fprintf(fp6,\"%c\} fclose(fp6); } void ReadTextFile(char *fileName6) {FILE *fp6;

9

char ch; if((fp6=fopen(fileName6,\"r\"))==NULL) {printf(\"\\n error on open %s!\exit(0); } printf(\"\\n输出译码后的文件内容:\\n\"); while(!feof(fp6)) {ch=fgetc(fp6); printf(\"%c\} fclose(fp6); printf(\"\\n\"); } 4.将函数的测试和主函数组合成一个文件，取名为huffermanuse.cpp。 #include\"huffermanpubuse.h\" #include\"huffermandef.h\" #include\"huffermanalgo.h\" void main() { HuffmanTree HT; HuffmanCode HC; int *wt,n,m,i,y,x,s1,s2; char str[100]; char str1[100],str2[100],str3[100],str4[100],str5[100],str6[100]; char *chh; char hh[100]; printf(\"请输入权值的个数(>1)：\"); scanf(\"%d\m=2*n-1; wt=(int*)malloc((n)*sizeof(int)); chh=(char*)malloc((n)*sizeof(char)); printf(\"请输入数据文件名：\"); scanf(\"%s\WriteDataFile(str1); ReadDataFile(str1,wt,chh);

10

HuffmanCoding(HT,HC,wt,chh,n); printf(\" node letter weight parent lchild rchild\"); printf(\"\\n\"); for(i=1;i<=m;i++) {printf(\" %4d %6c %7d %8d %8d %8d\ printf(\"\\n\"); } printf(\"*********** 哈夫曼树编码译码 ***********\\n\"); printf(\"*********** 1.对哈夫曼树进行编码 ***********\\n\"); printf(\"*********** 2.对文本文件中的文本进行编码 ***********\\n\"); printf(\"*********** 2.对代码文件中的代码进行译码 ***********\\n\"); printf(\"*********** 3.感谢使用 ***********\\n\"); while(x) {printf(\"请输入要实现功能的代码:\\n\"); scanf(\"%d\ switch(y) { case 1: printf(\"赫夫曼编码为：\\n\"); for(i=1;i<=n;i++) {printf(\"%c的编码为:\ }break; puts(HC[i]); case 2: printf(\"请输入文本文件名：\"); scanf(\"%s\ WriteToBeTran(str2); ReadToBeTran(str2,str); printf(\"请输入文本编码存放文件名：\"); scanf(\"%s\ WriteCode(str2,str5,HT,HC,n); ReadCode(str5); break; case 3: printf(\"请输入代码文件名：\"); scanf(\"%s\ WriteCodeFile(str3); ReadCodeFile(str3,str4);

11

yima(HT,n,str4,hh); printf(\"请输入译文存放文件名：\"); scanf(\"%s\ WriteTextFile(str6,hh); ReadTextFile(str6); } } } 保存，编译，连接，运行。 break; x=0; break; case 4:printf(\"感谢使用！\\n\"); default: printf(\"error!\");break; 七、 实验结果： 12

13

14

15

16

八、 实验总结及心得体会： 九、 对本实验过程及方法、手段的改进建议： 报告评分： 指导教师签字： 批阅日期：

17

注意：

 实验报告以纸质文档形式上交。实验报告将记入平时成绩；

 每次实验开始时，交上一次的实验报告，否则将扣除此次实验成绩。

18