1 / 10
文档名称:

哈夫曼文件压缩实验报告.docx

格式:docx   大小:208KB   页数:10页
下载后只包含 1 个 DOCX 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

哈夫曼文件压缩实验报告.docx

上传人:东风倩倩 2022/11/30 文件大小:208 KB

下载得到文件列表

哈夫曼文件压缩实验报告.docx

相关文档

文档介绍

文档介绍:该【哈夫曼文件压缩实验报告 】是由【东风倩倩】上传分享,文档一共【10】页,该文档可以免费在线阅读,需要了解更多关于【哈夫曼文件压缩实验报告 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。数据构造实验报告三——哈夫曼文件压缩
实验题目:哈夫曼文件压缩
实验目标:
输入一个有10k单词的英文文档。输出压缩后的二进制文件,并计算压缩比。
数据构造:
栈和哈夫曼树。
1.

定义栈

()
typedefstruct

{
char

*elem;
intstacksize;
inttop;}STACK;
()
typedefstruct{
intweight;
intleft

,right;
intparent

;}HTNode;
需要的操作有:
(

Initstack)
voidInitstack(STACK*s){
s->elem=(char*)malloc(sizeof(int)*1000);
s-〉stacksize=1000;
s—〉top=—1;
}
2。压栈

(push)
voidpush(STACK*s,inte){
s—>elem[++s—〉top]=e;
}
3。弹栈

(pop)
voidpop(STACK*s,int*e){
if(s-〉top!=-1)
*e=s->elem[s->top-—];
}
4。构造哈夫曼树(Inithuffman)
voidInithuffman(intwset[n],intk,HuffTreeHT[]){

//构造哈夫曼树
inti,m;
ints1,s2;
m=k*2-1;
for(i=0;i〈m;i++){

//初始化

HT数组
HT[i]=(HuffTree)malloc(sizeof(HTNode));
HT[i]—〉weight=(i<k?wset[i]:0);
HT[i]-〉parent=—1;
HT[i]->left=HT[i]—>right=—1;
}
for(i=k;i<m;i++){
select(HT,k,i,&s1,&s2);
parent为0且weight为最小的两个结点,其下标分别为
HT[i]-〉left=s1;

//主循环,完成n—1次合并
//在HT[1。.。i-1]中选择
s1和s2
HT[i]->right=s2;
HT[i]—〉weight=HT[s1]->weight+HT[s2]—>weight;HT[s1]-〉parent=HT[s2]—>parent=i;
}
}
其中用到另一个基本操作:找到哈夫曼树中最小和次小的结点(select)
(select)
voidselect(HuffTreeHT[255],inta,inti,int*p,int*q){
intj=0,k=0,*HT1,temp;
HT1=(int*)malloc(sizeof(int)*(i-1));//存放权值
for(j=0;j<i;j++){
if(HT[j]-〉parent==—1){
HT1[k]=HT[j]->weight

;

//把没有

parent

的结点的权值放在

HT1中
k++;
}
//printf(”%4d%4d%n”,HT[j]-〉parent,HT[j]->left,HT[j]->right,HT[j]
—〉weight,HT1[k—1]);
}
j=0;
while(j〈2){//找到权值最小和第二小的结点
for(k=j;k〈(i—(i-a)*2);k++){
if(HT1[j]>HT1[k]){
temp=HT1[k];
HT1[k]=HT1[j];
HT1[j]=temp;
}
}
j++;
}
k=0;
for(j=0;j〈i;){
if(HT[j]—>parent==—1)
if(HT[j]->weight==HT1[0]&&k<1){

//将最小的权值赋到

*p


*p=j;
k++;
}
j++;
}
for(j=0;j<i;){
if(HT[j]->parent==—1)
if(j!=*p)
if(HT[j]—>weight==HT1[1]&&k〈2){//将第二小的权值
赋到*q中
q=j;
k++;
}
j++;
printf("%4d%4d%4d%4d\n",HT[i]—>parent,HT[i]—>left,HT[i]—〉
right,HT[i]->weight);
}
}
6。依照哈夫曼树获取各字符对应的哈夫曼编码(Huffman)
voidHuffman(HuffTreeHT[2*n-1],intk,charstr[][20]){
inti,j,e,t1=0,t2=0;
charc;
STACKst;
for(i=0;i<k;i++){
if(HT[i]—>right==-1&&HT[i]->left==-1){//找一个叶子结点
Initstack(&st);
HT[i]—〉right=HT[i]—>left==—2;
j=i;

//记录其下标
while(HT[j]->parent!=-1){
if(HT[HT[j]—>parent]->right==j)

//找到一个叶子结点

,若是他是其
parent

结点的右结点,就将此边记为
push(&st,’1');

1
else
push(&st,’0');
j=HT[j]—>parent;

//在左边记为0
//循环操作直到到达根结点
}
c=i;
printf

("\t%c

”,c);

//打印此字符
for(;!=

—1;){
pop(&st,&e);
printf(”%c",e);
str[t1][t2]=e;

//打印其二进制编码
//将二进制编码存放在

str中
t2++;
}
putchar('\n')

;
str[t1]

0’;
t2=0;
t1++;
}
}
}
算法设计:
1。从文件中逐个读取字符,记录其出现次数以及文件总字符数,由此确定其频率高低。
2。依照字符频率创办哈夫曼树,尔后求出哈夫曼编码.
3。将哈夫曼编码输出到另一个文件中,并统计字数,求出压缩率。
源程序
include<〉
#include〈〉
include<>
definen127
typedefstruct{
intweight;
intleft,right;
intparent;}HTNode;//哈夫曼数组构造种类
typedefHTNode*HuffTree;
typedefstruct{
char*elem;
intstacksize;
inttop;}STACK;//栈的构造种类
voidInitstack(STACK*s){
s->elem=(char*)malloc(sizeof(int)*1000);
s->stacksize=1000;
s—>top=-1;
}//初始化栈
voidpush(STACK*s,inte){
s—〉elem[++s—〉top]=e;
}//压栈
voidpop(STACK*s,int*e){
if(s->top!=-1)
*e=s—>elem[s—>top—-];
//弹栈
voidselect(HuffTreeHT[255],inta,inti,int*p,int*q){//找到哈夫曼树中权值最小和次小的结点并返回指针
intj=0,k=0,*HT1,temp;
HT1=(int*)malloc(sizeof(int)*(i-1));//存放权值
for(j=0;j<i;j++){
if(HT[j]->parent==—1){
HT1[k]=HT[j]—>weight;//把没有parent的结点的权值放在
HT1中
k++;
}
printf("%4d%4d%4d%4d%4d\n",HT[j]—〉parent,HT[j]—〉left,HT[j]—〉right,HT[j]—〉weight,HT1[k—1]);
}
j=0;
while(j<2){//找到权值最小和第二小的结点
for(k=j;k<(i—(i-a)*2);k++){
if(HT1[j]>HT1[k]){
temp=HT1[k];
HT1[k]=HT1[j];
HT1[j]=temp;
}
}
j++;
}
k=0;
for(j=0;j<i;){
if(HT[j]->parent==-1)
if(HT[j]-〉weight==HT1[0]&&k〈1){

//将最小的权值赋到

*p


*p=j;
k++;
}
j++;
}
for(j=0;j〈i;){
if(HT[j]—〉parent==—1)
if(j!=*p)
if(HT[j]—〉weight==HT1[1]&&k〈2){//将第二小的权值赋
到*q中
*q=j;
k++;
}
j++;
printf(%”4d%4d%4d%4d\n",HT[i]—〉parent,HT[i]—>left,HT[i]—〉right,
HT[i]—〉weight);
}
}
voidInithuffman(intwset[n],intk,HuffTreeHT[]){//构造哈夫曼树
inti,m;
ints1,s2;
m=k*2—1;
for(i=0;i<m;i++){

//初始化

HT数组
HT[i]=(HuffTree)malloc(sizeof(HTNode));
HT[i]-〉weight=(i<k?wset[i]:0);
HT[i]-〉parent=-1;
HT[i]->left=HT[i]->right=-1;
}
for(i=k;i<m;i++){
select(HT,k,i,&s1,&s2);

//主循环,完成n—1次合并
//在HT[1。。。i-1]中选择parent
为0且weight为最小的两个结点,其下标分别为s1和s2
HT[i]->left=s1;
HT[i]->right=s2;
HT[i]—〉weight=HT[s1]—〉weight+HT[s2]-〉weight;
HT[s1]—〉parent=HT[s2]—>parent=i;
}
}
voidHuffman

(HuffTreeHT[2*n-1],intk,charstr[][20]){

//依照哈夫曼树获取各字
符对应的哈夫曼编码
int

i,j,e,t1=0,t2=0;
charc;
STACKst;
for(i=0;i<k;i++){
if(HT[i]->right==-1&&HT[i]-〉left==—1){

//找一个叶子结点
Initstack(&st);
HT[i]—>right=HT[i]—〉left==-2;
j=i;

//记录其下标
while(HT[j]—〉parent!=-1){
if(HT[HT[j]—〉parent]—>right==j)

//找到一个叶子结点,若是
他是其

parent

结点的右结点

,就将此边记为

1
push(&st,'1');
else
push(&st,’0’);

//在左边记为

0
j=HT[j]-〉parent;

//循环操作直到到达根结点
}
c=i;
printf(”\t%c",c);

//打印此字符
for(;st。top!=—1;){
pop(&st,&e);
printf(”%c",e);

//打印其二进制编码
str[t1][t2]=e;

//将二进制编码存放在

str中
t2++;
}
putchar(n’);
str[t1][t2]='\0';
t2=0;
t1++;
}
}
}
voidmain(){
FILE*fp1,*fp2;
HuffTreeHT[2*n—1];
inti=0,sum1=0,sum2=0;
floatcompress;
charstr[n][20];
charelem,ch;
intcount[n]={0};
if((fp1=fopen(”text1。txt”,”r"))==NULL){
printf(”can’topenthe!filen”);
exit(0);
}
while(!feof(fp1)){
elem=fgetc(fp1);

//读取文件中字符
i=elem;
count[i]++;

//记录字符频率
}
Inithuffman(count,n,HT);
//for(i=0;i〈253;i++)
//printf("%4d%4d

%4d%

n”,HT[i]—>parent,HT[i]->left,HT[i]->right,HT

[i]
->weight);
Huffman(HT,2*n-1,str);//对文章进行哈夫曼编码
if((fp1=fopen(”text1。txt",”r"))==NULL){
printf("can’topenthefile!\n");
exit(0);
}
if((fp2=fopen("","w

))==NULL”){
printf(”can’topenthe!\n")file;
exit(0);
}
while(!feof(fp1)){
ch=fgetc(fp1);//读取text1中字符
i=ch;
fputs(str[i],fp2);//将此字符的二进制编码输出到text2中sum1++;
}
if((fp2=fopen("text2。txt,””r"))==NULL){
printf("can'topenthefile!n”);
exit(0);
}
while(!feof(fp2)){
ch=fgetc(fp2);
sum2++;
}
compress=(float)sum2/(float)(sum1*8);
printf(”\n\n原字节数:%d\n现字节数:

%d\n

//压缩率
压缩率:

%。6f\n"

,8*sum1,
sum2,compress);
}
截图
输入:(自动认定为text1。txt,其中有17,278w)文件
输出结果:
1。哈夫曼树(检验建树成功)
:原字节数:789656,现字节数:475137,压缩率:0。601701
实验总结与心得
程序较长,调试中遇到很多困难;从前写的程序,过几天就会感觉理解不是很顺畅,需要加合适说明。