哈夫曼树实验报告Word下载.docx
- 文档编号:8041517
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:17
- 大小:209.94KB
哈夫曼树实验报告Word下载.docx
《哈夫曼树实验报告Word下载.docx》由会员分享,可在线阅读,更多相关《哈夫曼树实验报告Word下载.docx(17页珍藏版)》请在冰点文库上搜索。
io.h>
/*eof()*/
math.h>
/*floor(),ceil(),abs()*/
process.h>
/*exit()*/
/*函数结果状态代码*/
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
/*#defineOVERFLOW-2因为在math.h中已定义OVERFLOW的值为3,故去掉此行*/
typedefintStatus;
/*Status是函数的类型,其值是函数结果状态代码,如OK等*/
typedefintBoolean;
/*Boolean是布尔类型,其值是TRUE或FALSE*/
3.新建文件C/C++HeaderFile,输入文件名“huffermandef”,点击“确定”,在显示的代码编辑区中输入如下程序:
typedefstruct
{charch;
unsignedintweight;
unsignedintparent,lchild,rchild;
}HTNode,*HuffmanTree;
/*动态分配数组存储赫夫曼树*/
typedefchar**HuffmanCode;
/*动态分配数组存储赫夫曼编码表*/
4.新建文件C/C++HeaderFile,输入文件名“huffermandef”,点击“确定”,在显示的代码编辑区中输入如下程序:
intmin1(HuffmanTreet,inti)
{/*函数voidselect()调用*/
intj,flag;
unsignedintk=UINT_MAX;
/*取k为不小于可能的值*/
for(j=1;
j<
=i;
j++)
if(t[j].weight<
k&
&
t[j].parent==0)
k=t[j].weight,flag=j;
t[flag].parent=1;
returnflag;
}
voidselect(HuffmanTreet,inti,int*s1,int*s2)
{/*s1为最小的两个值中序号小的那个*/
intj;
*s1=min1(t,i);
*s2=min1(t,i);
if(*s1>
*s2)
{
j=*s1;
*s1=*s2;
*s2=j;
voidHuffmanCoding(HuffmanTree&
HT,HuffmanCode&
HC,int*w,char*ch,intn)/*算法6.12*/
{/*w存放n个字符的权值(均>
0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC*/
intm,i,j,s1,s2,start;
unsignedc,f;
HuffmanTreep;
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(;
=m;
++i,++p)
{(*p).ch='
*'
;
for(i=n+1,j=1;
++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);
\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;
/*从叶子到根逆向求每个字符的赫夫曼编码*/
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
/*分配n个字符编码的头指针向量([0]不用)*/
cd=(char*)malloc(n*sizeof(char));
/*分配求编码的工作空间*/
cd[n-1]='
\0'
/*编码结束符*/
for(i=1;
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
1'
HC[i]=(char*)malloc((n-start)*sizeof(char));
/*为第i个字符编码分配空间*/
strcpy(HC[i],&
cd[start]);
/*从cd复制编码(串)到HC*/
free(cd);
/*释放工作空间*/
voidReadDataFile(char*fileName,int*wt,char*chh)//读初始化文件内容
{
FILE*fp;
charch;
intw,i=0;
if((fp=fopen(fileName,"
r"
))==NULL)
\nerroronopen%s!
"
fileName);
exit
(1);
\n文件内容:
while(!
feof(fp))
fscanf(fp,"
%c"
&
ch);
if(ch=='
\n'
)continue;
//读到换行符,跳过,读下一行
chh[i]=ch;
ch=%c"
ch);
%5d"
w);
//fscanf中的格式化要加\n,文件指针才会指向下一行
wt[i]=w;
weight=%5d\n"
w);
i++;
}
fclose(fp);
voidWriteDataFile(char*fileName)//将初始化信息写入文件中
charc;
intweight;
w"
请输入相关字符及字符的权值,#结束:
c=getchar();
while((c=getchar())!
='
#'
)
fprintf(fp,"
c);
//将字符写入文件
scanf("
%d"
weight);
%5d\n"
weight);
//将字符的权值写入文件,采用fprintf格式化写入
voidWriteTextFile(char*fileName)//将初始化信息写入文件中
inti=0;
请输入需要编译的文本,#结束:
ch=getchar();
while(ch!
fputc(ch,fp);
putchar(10);
voidReadTextFile(char*fileName,charstr[])//读初始化文件内容
str[i++]=ch;
str[i]='
voidbianma(charstr[],HuffmanTree&
HC,intn)
inti,j,k=0;
while(str[k]!
)
k++;
for(i=0;
k-1;
{
for(j=1;
if(str[i]==HT[j].ch)
puts(HC[j]);
}
voidyima(HuffmanTree&
HT,intn,charstr4[],charhh[])
{inti,j,m=0;
for(i=0,j=2*n-1;
str4[i]!
i++)
if(str4[i]=='
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;
elseif(str4[i]=='
HT[j].rchild!
{j=HT[j].rchild;
hh[m]='
puts(hh);
voidWriteCodeFile(char*fileName)//将初始化信息写入文件中
请输入需要译的代码,#结束:
voidReadCodeFile(char*fileName,charstr4[])//读初始化文件内容
{ch=fgetc(fp);
str4[i++]=ch;
str4[i]='
5.新建文件C++SourceFile,输入文件名“huffermandef”,点击“确定”,在显示的代码编辑区中输入如下程序:
#include"
huffermanpubuse.h"
huffermandef.h"
huffermanalgo.h"
voidmain()
HuffmanTreeHT;
HuffmanCodeHC;
int*wt,n,m,i,y,x,s1,s2;
charstr[100];
charstr1[100],str2[100],str3[100],str4[100];
char*chh;
charhh[100];
请输入权值的个数(>
1):
n);
wt=(int*)malloc((n)*sizeof(int));
chh=(char*)malloc((n)*sizeof(char));
请输入数据文件名:
%s"
str1);
WriteDataFile(str1);
ReadDataFile(str1,wt,chh);
HuffmanCoding(HT,HC,wt,chh,n);
nodeletterweightparentlchildrchild"
{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"
1.对哈夫曼树进行编码\n"
2.对文本文件中的文本进行编码\n"
2.对代码文件中的代码进行译码\n"
3.感谢使用\n"
while(x)
请输入要实现功能的代码:
scanf("
y);
switch(y)
case1:
赫夫曼编码为:
for(i=1;
{printf("
%c的编码为:
*(chh+i-1));
puts(HC[i]);
}
case2:
请输入文本文件名:
str2);
WriteTextFile(str2);
ReadTextFile(str2,str);
\n文本编码为:
bianma(str,HT,HC,n);
break;
case3:
请输入代码文件名:
str3);
WriteCodeFile(str3);
ReadCodeFile(str3,str4);
\n代码译码为:
yima(HT,n,str4,hh);
case4:
感谢使用!
x=0;
default:
error!
break;
6.点击“文件”--“保存全部”;
7.编译Ctrl+F7;
8.运行F5;
7、实验操作结果:
ToBeTran.txt文件内容:
DataFile.txt文件内容:
CodeFile.txt文件内容:
报告评分:
指导教师签字:
批阅日期:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈夫曼树 实验 报告
![提示](https://static.bingdoc.com/images/bang_tan.gif)