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

1、.实 验 报 告一、 实验题目：哈夫曼编/译码系及其应用二、 实验地点：三、 实验目的：1.掌握哈夫曼树的概念、存储结构2.掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算3.熟练掌握二叉树的应用四、 实验内容：实现哈夫曼树的生成，完成哈夫曼编/译码的输出。1.初始化，从数据文件Data中读入字符及每个字符的权值，建立哈夫曼树HuffTree；2.编码，用已建好的哈夫曼树，对文件ToBeTran.data中的文本进行编码形成报文，将报文写在文件Code.text中；3.译码，利用已建好的哈夫曼树，对文件Code中的代码进行解码形成原文，结果存入文件Text中；4.输出，输出Data中出现

2、的字符以及各字符出现的频度（或概率）；输出ToBeTran.data及其报文Code.text；输出Code及其原文Text。编写主程序，实现对各不同的算法调用。五、 实验环境（使用的软件）：Visaul C+6.0六、 实验步骤及操作：打开VC+6.0创建工程/Win32 Console Application，输入工程名：哈夫曼树，新建三个.h文件一个.cpp文件1将一些常量定义，系统函数原型声明和类型（Status）重定义,结果状态代码等放在一个头文件中:取名为huffermanpubuse.h。#include#include#include /* malloc()等*/#includ

3、e /* INT_MAX 等*/#include /* EOF(=Z 或F6),NULL */#include /* atoi() */#include /* eof() */#include /* floor(),ceil(),abs() */#include /* exit() */* 函数结果状态代码*/#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1/* #define OVERFLOW -2 因为在math. h 中已定义OVERFLOW 的值为3,故去掉此行*/typedef

4、int Status; /* Status 是函数的类型,其值是函数结果状态代码，如OK 等*/typedef int Boolean; /* Boolean 是布尔类型,其值是TRUE 或FALSE */2将哈夫曼树存储结构定义放在一个头文件：取名为huffermandef.h。typedef structchar ch;unsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树*/typedef char *HuffmanCode; /* 动态分配数组存储赫夫曼编码表*

5、/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(tj.weight*s2)j=*s1;*s1=*s2;*s2=j;void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,char *ch,int n) /* 算法6.12 */ /* w 存放n 个字符

6、的权值(均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=*;(*

7、p).parent=0;for(i=n+1,j=1;i=m;+i,j+) /* 建赫夫曼树*/ /* 在HT1i-1中选择parent 为0 且weight 最小的两个结点,其序号分别为s1 和s2 */select(HT,i-1,&s1,&s2);printf(第%d次比较min1与min2:%d %d,j,HTs1.weight,HTs2.weight);printf(n);HTs1.parent=HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/* 从叶子到根逆向求每个字符的赫夫曼编

8、码*/HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/* 分配n 个字符编码的头指针向量(0不用) */cd=(char*)malloc(n*sizeof(char); /* 分配求编码的工作空间*/cdn-1=0; /* 编码结束符*/for(i=1;i=n;i+) /* 逐个字符求赫夫曼编码*/start=n-1; /* 编码结束符位置*/for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/* 从叶子到根逆向求编码*/if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(cha

9、r*)malloc(n-start)*sizeof(char);/* 为第i 个字符编码分配空间*/strcpy(HCi,&cdstart); /* 从cd 复制编码(串)到HC */free(cd); /* 释放工作空间*/void ReadData * *wt,char *chh)/读初始化文件内容 FILE *fp1; char ch;int w,i=0; if(fp1=fopen(,r)=NULL) printf(nerror on open %s!,); exit(1); printf(n文件内容：n); while(!feof(fp1) fscanf(fp1,%c,&ch); if

10、(ch=n) continue; /读到换行符，跳过，读下一行 chhi=ch;printf(ch=%c ,ch); fscanf(fp1,%5d,&w); / fscanf中的格式化要加n,文件指针才会指向下一行 wti=w;printf(weight= %5dn,w); i+; fclose(fp1); void WriteData *)/将初始化信息写入文件中 FILE *fp1; char c;int weight; if(fp1=fopen(,w)=NULL) printf(nerror on open %s!,); exit(1); printf(请输入相关字符及字符的权值,#结束

11、:n); c=getchar();while(c=getchar()!=#) fprintf(fp1,%c,c);/将字符写入文件 scanf(%d,&weight); fprintf(fp1,%5dn,weight);/将字符的权值写入文件，采用fprintf格式化写入 fclose(fp1); void WriteToBeTran(char *)/将初始化信息写入文件中 FILE *fp2; char ch; int i=0;if(fp2=fopen(,w)=NULL) printf(nerror on open %s!,); exit(1); printf(请输入需要编译的文本，#结束：

12、n);ch=getchar();ch=getchar();while(ch!=#) fputc(ch,fp2);ch=getchar();putchar(10); fclose(fp2); void ReadToBeTran(char * str)/读初始化文件内容 FILE *fp2; char ch;int i=0; if(fp2=fopen(,r)=NULL) printf(nerror on open %s!,); exit(1); while(!feof(fp2) fscanf(fp2,%c,&ch); if(ch=n) continue; /读到换行符，跳过，读下一行 stri+=

13、ch; stri=0;fclose(fp2); void WriteCode(char * *, HuffmanTree &HT,HuffmanCode &HC,int n)FILE *fp3,*fp4;char ch;int i;if(fp3=fopen(,r)=NULL)printf(n error on open %s!,);exit(0);if(fp4=fopen(,w)=NULL)printf(n error on open %s!,);exit(0);while(!feof(fp3)ch=fgetc(fp3);for(i=1;i1)：);scanf(%d,&n);m=2*n-1;w

14、t=(int*)malloc(n)*sizeof(int);chh=(char*)malloc(n)*sizeof(char);printf(请输入数据文件名：);scanf(%s,str1);WriteData);ReadData);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,i,HTi.ch,HTi.weight,HTi.parent,HTi.lchild,HTi.

15、rchild); printf(n);printf(* 哈夫曼树编码译码 *n);printf(* 1.对哈夫曼树进行编码 *n);printf(* 2.对文本文件中的文本进行编码 *n);printf(* 2.对代码文件中的代码进行译码 *n);printf(* 3.感谢使用 *n);while(x)printf(请输入要实现功能的代码:n); scanf(%d,&y); switch(y) case 1: printf(赫夫曼编码为：n); for(i=1;i=n;i+) printf(%c的编码为:,*(chh+i-1); puts(HCi); break; case 2: printf(请输入文本文件名：); scanf(%s,str2); WriteToBeTran(str2); ReadToBeTran(str2,str);printf(请输入文本编码存放文件名：); scanf(%s,str5); WriteCode(str2,str5,HT,HC,n); ReadCode(str5); break; case 3: printf(请输入代码文件名：); scanf(%s,str3); WriteCode); ReadCode); yima(HT,n,str4,hh); printf(请输入译文存放文件名：);