数据结构课程设计报告哈夫曼树.doc

计算机科学学院

数据结构课程设计

题 目：基于哈夫曼树的文献压缩/解压程序

学生姓名：林华
学 号：
专 业：计算机科学与技术
班 级：12级（2）班
指导教师姓名及职称：陈明 讲师
起止时间： 2023 年 3 月—— 2023 年 4 月

1 需求分析
1.1课题背景及意义
近年来，随着计算机技术的发展，多媒体计算机技术、计算机网络技术以及现代多媒体通信技术正在向着信息化、高速化、智能化迅速发展。各个领域的应用与发展，各个系统的数据量越来越大，给数据的存储、传输以及有效、快速获取信息带来了严重的障碍。数据压缩技术可以比较有效地解决这个问题。
尚有在最近几年中兴起的物联网和云计算都是对海量的数据进行解决和传输的，假如不对数据进行压缩，那么数据传输所需的带宽规定就很高，物理成本上也随之上升。所以说数据压缩在计算机通信中占有很重要的位置，且涉及领域多，应用广泛，与我们的生活息息相关。

1.2课题规定
1.2.1．实现一个基于哈夫曼树的文献压缩程序和文献解压程序。
1.2.2.压缩程序能输入源文献进行压缩，输出压缩文献；
1.2.3．解压程序读入压缩文献，根据相应的哈夫曼编码解压还原 ，得到相应的源文献。
1.2.4．可选做：求出压缩率；打印哈夫曼树；对文献夹压缩；图形图形化窗口操作界面。

1.3任务和规定
1.3.1选择1时：
输入一个待压缩的文本文献名称(可带途径)。
如:D:\1\XXX.txt
压缩文献名称= D:\1\XXX.zip
1.3.2选择2时：
输入一个待解压的压缩文献名称(可带途径)。
如:D:\1\YYY.txt
解压文献名称=D:\1\YYY.zip

2概要设计
2.1问题解决的思绪概述建立哈夫曼树

根据哈夫曼树解码
对二进制文献进行解码

记录字符，得出记录出字符的权值n
根据哈夫曼树编码

对编码进行压缩

生成哈夫曼树

生成相应文献
生成二进制文献

图1 主程序流程图

2.2 算法思想：
2.2.1输入要压缩的文献
一方面运营的时候，用户主界面上有菜单提醒该如何使用软件，根据菜单提醒选择所要执行的项，依次进行，由于各个环节之间有先后顺序。第一步为输入压缩软件的名称，由键盘输入文献途径和文献名称，读入字符数组中，打开该文献，按照提醒进行压缩。若打不开，则继续输入。
2.2.2读文献并计算字符频率
文献将信息存放在字符数组中；计算每个字符出现的次数，申请一个结构体数组空间， 用读取的字符减去字符结束符作为下标记录字符的频率。
2.2.3根据字符的频率，运用Huffman编码思想创建Huffman树
将所记录的字符的频率作为权值来创建Huffman树，依次选择权值最小的两个字符作为左右孩子，其和作为父结点的权值，依次进行下去，直到所有的字符结点都成为叶子结点。
2.2.4由创建的Huffman树来决定字符相应的编码，进行文献的压缩
根据创建的Huffman树来拟定个字符的01编码，左孩子为0，右孩子为1。读取文献，依次将每个字符用他们的编码表达，即完毕一次编码。
2.2.5解码压缩即根据Huffman树进行译码
读取编码文献，依据创建的Huffman树，定义一个指针指向根结点。从根结点开始，每读一个字符，指针变化一次（当读取的字符是‘1’时，指针指向当前所指结点的右孩子，当读取的字符是‘0’时，指针指向当前所指结点的左孩子），直至该指针所指结点为叶子结点时结束（即当结点的左右孩子均为空时）。将当前叶子结点所代表的字符值输出到译码文献中，依次读取编码文献中的字符，按照上述方法依次进行下去直至文献

2.3数据结构定义
typedef struct node //哈夫曼树结构体
{
long w;//权重
short p,l,r; //定义双亲，左孩子，右孩子
}htnode,*htnp;

typedef struct huffman_code
{
unsigned char len;//记录该结点哈夫曼编码的长度
unsigned char *codestr; //记录该结点的哈夫曼编码
}hufcode;
2.5主程序的流程及模块间关系
主函数实例化huffmanTree类，并实现菜单工具栏，通过用户的选择输入，用switch语句进行分支执行huffmanTree类中功能函数：
1:压缩函数 int compress(char *source_file,char *obj_file)；
2:解压函数 int decompress(char *source_file,char*obj_file)；
并可在完毕相应功能后安全退出，压缩或解压的文献在同文献夹下生成。
3. 具体设计
核心算法----huffman算法：
3.1根据给定的n个权值｛w1,w2,……,wn｝构成n棵二叉树的集合F=｛T1,T2,……,Tn｝,其中每棵二叉树T1中只有一个带权的 w1的根据点，其左右子树均空。
3.2在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右树上根结点的权值之和。
3.3在F中删除这两棵树，同时将所得到的二叉树加入F中。
3.4反复3.2,3.3,直到F中只含一棵树为止。这棵树便是Huffman树。Huffman树可用于构造代码总长度最短的编码方案。

为了具体说明这个问题，特以下面例子来说明:

图2 问题详解
编码完毕之后，开始对源文献进行压缩。
1. 从源文献读一个字符，从叶子结点中找出和此字符相同的字符结点，将其编码写入一个临时字符组codes；
2. 当codes的长度大于等于8时，将其前8位转换成字符写入目的文献中；
3. 反复1和2此过程，直至读完源文献中的所有字符；
4. 若codes最后尚有剩余的局限性8位的01代码，则将其低位补0至8位，再写入目的文献。

主程序模块:

图 3 主程序模块

4. 调试分析报告
由于压缩与解压过程中没有输入新生成文献的途径，因此解压后的文献会将原文献覆盖。如图：

图4 压缩前原文献

图 5 压缩后生成文献

图 6 解压后文献
5.用户使用说明
在运营程序之前，一方面在D盘先建立一个待压缩的文献1.doc，
运营程序如下图所示。
图7 版本测试结果图
压缩：在命令行下输入1对文献进行压缩，根据提醒输入刚刚建的文本文献（1.doc），和要生成的压缩文献名称，按回车确认进行压缩。
图 8 执行压缩操作图
成功执行完毕后如下图所示。

图 9 执行压缩操作图

选择打印哈夫曼树及编码。

图10 执行打印操作图
解压：
在命令行下输入2对本程序压缩的文献进行恢复，根据提醒输入待恢复的
文献名称和恢复后的文献名称，按回车拟定，成功执行后如下图所示。

图11 执行解压操作图

6.测试结果
具体测试结果请参见 5 使用功能。
6.1测试报告

原文献
压缩后
解压后
1
txt文献(14598b)
8192b
8192b
2
pdf文献(359398b)
356352b
359398b
3
jpg文献(31455b)
28672b
31455b
4
Mp3文献(72023b)
69632b
72023b

参考文献
[1]郑莉 等编著《C++语言程序设计（第三版）》北京：清华大学出版社.
[2]谭浩强 .C++面向对象程序设计(第二版) [M].北京：中国铁道出版社，2023.
[3]洪国胜 等编著 《C++ Builder程序设计轻松上手》北京：清华大学出版社.
[4]胡学钢等《数据结构算法设计指导》北京：清华大学出版社，1999年 第1版.
[5]王昆仑 等编著 《数据结构域算法（高等学校计算机精品课程系列教材）》 中国铁道工业出版社.

附录：源程序
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <windows.h>

typedef struct node //哈夫曼树结构体
{
long w;//权重
short p,l,r; //定义双亲，左孩子，右孩子
}htnode,*htnp;

typedef struct huffman_code
{
unsigned char len;//记录该结点哈夫曼编码的长度
unsigned char *codestr; //记录该结点的哈夫曼编码
}hufcode;

typedef char **huffmancode;

int initial_files(char *source_file,FILE **inp,char *obj_file,FILE **outp);//文献初始信息

char *create_file(char *source_file,char* obj_file);//创建待压缩文献名

int compress(char *source_file,char *obj_file);//压缩函数

long frequency_data(FILE *in,long fre[]);//计算字符频率

int search_set(htnp ht,int n,int *s1, int *s2);//查找文献

int create_hftree(long w[],int n,htnode ht[]);//创建哈夫曼树

int encode_hftree(htnp htp,int n,hufcode hc[]);//记录哈夫曼编码

unsigned char chars_to_bits(const unsigned char chars[8]);//计算文献大小

int write_compress_file(FILE *in,FILE *out,htnp ht,hufcode hc[],char* source_file,long source_filesize);//输入待压缩文献途径

int decompress(char *source_file,char *obj_file);//解压函数

void get_mini_huffmantree(FILE* in,short mini_ht[][2]);//建立哈弗曼树中用于选择最小权值结点的函数

int write_decompress_file(FILE *in,FILE* out,short mini_ht[][2],long bits_pos,long obj_filesize);//输入待解压文献途径

int d_initial_files(char *source_file,FILE **inp,char *obj_file,FILE **outp);

main()
{
int s;
char file[10];
system("color 3F");
printf(" ***************************************\n");
printf(" * 菜单： *\n");
printf(" * 1.------压缩------ *\n");
printf(" * 2.------解压------ *\n");
printf(" * 0.------退出------ *\n");
printf(" ***************************************\n");
scanf("%d",&s);
while(s!=0)
{
getchar();
switch(s)
{
case 1:
puts("请输入待压缩文献途径：");
gets(file);
compress(file,NULL);
break;
case 2:
puts("请输入待解压文献途径：");
gets(file);
decompress(file,NULL);
break;
default :
printf("指令错误！请重新输入指令：\n");
}
puts(" ");
printf(" ***************************************\n");
printf(" * 菜单： *\n");
printf(" * 1.------压缩------ *\n");
printf(" * 2.------解压------ *\n");
printf(" * 0.------退出------ *\n");
printf(" ***************************************\n");
scanf("%d",&s);
}
}

//文献初始信息
int initial_files(char *source_file,FILE **inp,char *obj_file,FILE **outp)
{
if(fopen(source_file,"rb")==NULL)
{
return -1;
}

if(obj_file==NULL)
{
if((obj_file=(char*)malloc(256*sizeof(char)))==NULL)
{
return -1;
}
create_file(source_file,obj_file);
}
if(strcmp(source_file,obj_file)==0)
{
return -1;
}
printf("待压缩文献:%s,压缩文献:%s\n",source_file,obj_file);
if((*outp=fopen(obj_file,"wb"))==NULL)
{
return -1;
}
if((*inp=fopen(source_file,"rb"))==NULL)
{
return -1;
}
free(obj_file);
return 0;
}
//创建待压缩文献名
char *create_file(char *source_file,char* obj_file)
{
char *temp;
if((temp=strrchr(source_file,'.'))==NULL)
{
strcpy(obj_file,source_file);
strcat(obj_file,".zip");
}
else
{
strncpy(obj_file,source_file,temp-source_file);
obj_file[temp-source_file]='\0';
strcat(obj_file,".zip");
}
return obj_file;
}
//压缩函数
int compress(char *source_file,char *obj_file)
{
FILE *in,*out;
char ch;
int error_code,i,j;
float compress_rate;
hufcode hc[256]; //编码的位数最多为256位
htnode ht[256*2-1];
long frequency[256],source_filesize,obj_filesize=0;
error_code=initial_files(source_file,&in,obj_file,&out);
if(error_code!=0)
{
puts("文献打开失败！请重新输入文献途径：");
return error_code;
}
source_filesize=frequency_data(in,frequency);
printf("文献大小 %ld 字节\n",source_filesize);
error_code=create_hftree(frequency,256,ht);
if(error_code!=0)
{
puts("建立哈夫曼树失败！");
return error_code;
}

error_code=encode_hftree(ht,256,hc);
if(error_code!=0)
{
puts("建立哈夫曼编码失败！");
return error_code;
}
for(i=0;i<256;i++)
obj_filesize+=frequency[i]*hc[i].len;
obj_filesize=obj_filesize%8==0?obj_filesize/8:obj_filesize/8+1;
for(i=0;i<256-1;i++)
obj_filesize+=2*sizeof(short);
obj_filesize+=strlen(source_file)+1;
obj_filesize+=sizeof(long);
obj_filesize+=sizeof(unsigned int);
compress_rate=(float)obj_filesize/source_filesize;
printf("压缩文献大小:%ld字节,压缩比例:%.2lf%%\n",obj_filesize,compress_rate*100);
error_code=write_compress_file(in,out,ht,hc,source_file,source_filesize);
if(error_code!=0)
{
puts("写入文献失败！");
return error_code;
}
puts("压缩完毕!");
puts(" ");
puts("是否打印该文献中字符相应的huffman树及编码？");
puts(" Please input Y OR N");
do{
scanf("%s",&ch);
switch(ch)
{
case 'Y':
puts("以下是哈夫曼树：");
for(i=256;i<256*2-2;i++)
{
if(ht[i].w>0)
printf("%-10d%-10d%-10d%-10d%-10d\n",i,ht[i].w,ht[i].p,ht[i].l,ht[i].r);
}
puts("以下是哈夫曼编码：");
for(i=0;i<256;i++)
{
if(frequency[i]==0)
i++;
else
{
printf("%d\t",frequency[i]);
for(j=0;j<hc[i].len;j++)
printf(" %d",hc[i].codestr[j]);
printf("\n");
}
}
break;
case 'N': break;
default :
printf("指令错误！请重新输入指令：\n");
}
}while(ch!='Y'&&ch!='N');
fclose(in);
fclose(out);
for(i=0;i<256;i++)
{
free(hc[i].codestr);
}
return 0;
}
//计算字符频率
long frequency_data(FILE *in,long frequency[])
{
int i,read_len;
unsigned char buf[256];
long filesize;

for(i=0;i<256;i++) //去掉权值为0的结点
{
frequency[i]=0;
}
fseek(in,0L,SEEK_SET);
read_len=256;

while(read_len==256)
{
read_len=fread(buf,1,256,in);
for(i=0;i<read_len;i++) //初始化根结点
{
frequency[*(buf+i)]++;
}
}
for(i=0,filesize=0;i<256;i++)
{
filesize+=frequency[i];
}

return filesize;
}

int search_set(htnp ht,int n,int *s1, int *s2)
{
int i,x;
long minValue = 999999,min = 0;
for(x=0;x<n;x++)
{
if(ht[x].p==-1) break;

}
for(i=0;i<n;i++)
{
if(ht[i].p==-1 && ht[i].w < minValue)
{
minValue = ht[i].w;
min=i;
}
}
*s1 = min;

minValue = 999999,min = 0;
for(i=0;i<n;i++)
{
if(ht[i].p==-1 && ht[i].w < minValue && i != *s1)
{
minValue = ht[i].w;
min=i;
}
}

*s2 = min;
return 1;
}
//创建哈夫曼树
int create_hftree(long w[],int n,htnode ht[])
{
int m,i,s1,s2;

if (n<1) return -1;
m=2*n-1;
if (ht==NULL) return -1;
for(i=0;i<n;i++)
{
ht[i].w=w[i];
ht[i].p=ht[i].l=ht[i].r=-1;
}
for(;i<m;i++)
{
ht[i].w=ht[i].p=ht[i].l=ht[i].r=-1;
}

for(i=n;i<m;i++)
{
search_set(ht,i,&s1,&s2);

ht[s1].p = ht[s2].p = i;
ht[i].l = s1;
ht[i].r = s2;
ht[i].w = ht[s1].w + ht[s2].w;
}
return 0;
}

int encode_hftree(htnp htp,int n,hufcode hc[])
{
int i,j,p,codelen;
unsigned char *code=(unsigned char*)malloc(n*sizeof(unsigned char));

if (code==NULL) return -1;
for(i=0;i<n;i++)
{
for(p=i,codelen=0;p!=2*n-2;p=htp[p].p,codelen++)
{
code[codelen]=(htp[htp[p].p].l==p?0:1);
}
if((hc[i].codestr=(unsigned char *)malloc((codelen)*sizeof(unsigned char)))==NULL)
{
return -1;
}
hc[i].len=codelen;
for(j=0;j<codelen;j++)
{
hc[i].codestr[j]=code[codelen-j-1];
}
}
free(code);
return 0;
}

unsigned char chars_to_bits(const unsigned char chars[8])
{
int i;
unsigned char bits=0;
bits|=chars[0];
for(i=1;i<8;++i)
{
bits<<=1;
bits|=chars[i];
}
return bits;
}

int write_compress_file(FILE *in,FILE *out,htnp ht,hufcode hc[],char* source_file,long source_filesize)
{
unsigned int i,read_counter,write_counter,zip_head=0xFFFFFFFF;
unsigned char write_char_counter,code_char_counter,copy_char_counter,
read_buf[256],write_buf[256],write_chars[8],file_size=strlen(source_file);
hufcode *cur_hufcode;

fseek(in,0L,SEEK_SET);
fseek(out,0L,SEEK_SET);
fwrite(&zip_head,sizeof(unsigned int),1,out);
fwrite(&file_size,sizeof(unsigned char),1,out);
fwrite(source_file,sizeof(char),file_size,out);
fwrite(&source_filesize,sizeof(long),1,out);
for(i=256;i<256*2-1;i++)
{
fwrite(&(ht[i].l),sizeof(ht[i].l),1,out);
fwrite(&(ht[i].r),sizeof(ht[i].r),1,out);
}
write_counter=write_char_counter=0;
read_counter=256;
while(read_counter==256)
{
read_counter=fread(read_buf,1,256,in);
for(i=0;i<read_counter;i++)
{
cur_hufcode=&hc[read_buf[i]];
code_char_counter=0;
while(code_char_counter!=cur_hufcode->len)
{
copy_char_counter= (8-write_char_counter > cur_hufcode->len-code_char_counter ?
cur_hufcode->len-code_char_counter : 8-write_char_counter);
memcpy(write_chars+write_char_counter,cur_hufcode->codestr+code_char_counter,copy_char_counter);
write_char_counter+=copy_char_counter;
code_char_counter+=copy_char_counter;
if(write_char_counter==8)
{
write_char_counter=0;
write_buf[write_counter++]=chars_to_bits(write_chars);
if(write_counter==256)
{
fwrite(write_buf,1,256,out);
write_counter=0;
}
}
}
}

}
fwrite(write_buf,1,write_counter,out);
if(write_char_counter!=0)
{
write_char_counter=chars_to_bits(write_chars);
fwrite(&write_char_counter,1,1,out);
}
return 0;
}
//建立哈弗曼树中用于选择最小权值结点的函数
void get_mini_huffmantree(FILE* in,short mini_ht[][2])
{
int i;
for(i=0;i<256;i++)
{
mini_ht[i][0]=mini_ht[i][1]=-1;
}
fread(mini_ht[i],sizeof(short),2*(256-1),in);
}

int write_decompress_file(FILE *in,FILE* out,short mini_ht[][2],long bits_pos,long obj_filesize)
{
long