哈夫曼树编码译码实验报告
实 验 报 告 一、 实验
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
目:哈夫曼编/译码系及其应用
二、 实验地点:
三、 实验目的:
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",j,HT[s1].weight,HT[s2].weight);
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!",fileName1); exit(1);
}
printf("\n文件内容:\n");
while(!feof(fp1))
{
fscanf(fp1,"%c",&ch);
if(ch=='\n') continue; //读到换行符，跳过，读下一行 chh[i]=ch;
4
printf("ch=%c ",ch);
fscanf(fp1,"%5d",&w); // fscanf中的格式化要加\n,文件指针才会指向下一行
wt[i]=w;
printf("weight= %5d\n",w);
i++;
}
fclose(fp1);
}
void WriteDataFile(char *fileName1)//将初始化信息写入文件中
{
FILE *fp1;
char c;int weight;
if((fp1=fopen(fileName1,"w"))==NULL) {
printf("\nerror on open %s!",fileName1); exit(1);
}
printf("请输入相关字符及字符的权值,#结束:\n"); c=getchar();
while((c=getchar())!='#')
{
fprintf(fp1,"%c",c);//将字符写入文件 scanf("%d",&weight);
fprintf(fp1,"%5d\n",weight);//将字符的权值写入文件，采用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!",fileName2);
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!",fileName2); exit(1);
}
while(!feof(fp2))
{
fscanf(fp2,"%c",&ch);
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!",fileName3); exit(0);
}
if((fp4=fopen(fileName4,"w"))==NULL) {printf("\n error on open %s!",fileName4); exit(0);
}
while(!feof(fp3))
{
ch=fgetc(fp3);
for(i=1;i<=n;i++)
if(ch==HT[i].ch)
fprintf(fp4,"%s",HC[i]);
}
fclose(fp3);
fclose(fp4);
}
void ReadCode(char *fileName4) {FILE *fp4;
char ch;
if((fp4=fopen(fileName4,"r"))==NULL) {printf("\n error on open %s!",fileName4); exit(0);
}
printf("\n输出编码后的文件内容:\n"); while(!feof(fp4))
{
ch=fgetc(fp4);
printf("%c",ch);
}
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!",fileName5); 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!",fileName5); 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!",fileName6); exit(0);
}
for(i=0;hh[i]!='\0';i++)
{ch=hh[i];
fprintf(fp6,"%c",ch);
}
fclose(fp6);
}
void ReadTextFile(char *fileName6) {FILE *fp6;
9
char ch;
if((fp6=fopen(fileName6,"r"))==NULL) {printf("\n error on open %s!",fileName6); exit(0);
}
printf("\n输出译码后的文件内容:\n"); while(!feof(fp6))
{ch=fgetc(fp6);
printf("%c",ch);
}
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",&n);
m=2*n-1;
wt=(int*)malloc((n)*sizeof(int)); chh=(char*)malloc((n)*sizeof(char)); printf("请输入数据文件名:"); scanf("%s",str1);
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",i,HT[i].ch,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].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(HC[i]);
}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);
WriteCodeFile(str3);
ReadCodeFile(str3,str4);
11
yima(HT,n,str4,hh);
printf("请输入译文存放文件名:");
scanf("%s",str6);
WriteTextFile(str6,hh);
ReadTextFile(str6);
break;
case 4:printf("感谢使用～\n");
x=0;
break;
default: printf("error!");break;
}
}
}
保存，编译，连接，运行。 七、 实验结果:
12
13
14
15
16
八、 实验
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
及
心得体会
决胜全面小康心得体会学党史心得下载党史学习心得下载军训心得免费下载党史学习心得下载
:
九、 对本实验过程及方法、手段的改进建议:
报告评分:
指导教师签字: 批阅日期:
17
注意:
, 实验报告以纸质文档形式上交。实验报告将记入平时成绩; , 每次实验开始时，交上一次的实验报告，否则将扣除此次实验成绩。
18
浙公网安备 33021202002483