《数据结构哈夫曼编码实验报告》由会员分享，可在线阅读，更多相关《数据结构哈夫曼编码实验报告（7页珍藏版）》请在装配图网上搜索。
1、-
实验报告
实验课名称：数据构造实验
实验名称：文件压缩问题
班级：20132012
**：
：
时间：2015-6-9
一、问题描述
哈夫曼编码是一种常用的数据压缩技术，对数据文件进展哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进展哈夫曼编码以到达压缩文件的目的，再用哈夫曼编码进展译码解压缩。
二、数据构造设计
首先定义一个构造体：
struct head
{
unsigned char b; //记录字符
long count;
2、 //权重
int parent,lch,rch; //定义双亲，左孩子，右孩子
char bits[256]; //存放哈夫曼编码的数组
}
header[512],tmp; //头部一要定设置至少512个,因为结点最多可达256,所有结点数最多可达511
三、算法设计
输入要压缩的文件读文件并计算字符频率根据字符的频率，利用Huffman编码思想创立Huffman树由创立的Huffman树来决定字符对应的编码，进展文件的压缩解码压缩即根据Huffman树进展译码
设计流程图如图1.1所示。
3、
建立哈夫曼树
根据哈夫曼树解码
对二进制文件进展解码
统计字符，得出统计出字符的权值n
根据哈夫曼树编码
对编码进展压缩
生成哈夫曼树
生成对应文件
生成二进制文件
图1.1 设计流程图
(1)压缩文件
输入一个待压缩的文本文件名称(可带路径)如:D:\lu\lu.t*t统计文本文件中各字符的个数作为权值,生成哈夫曼树；将文本文件利用哈夫曼树进展编码,生成压缩文件。压缩文件名称=文本文件名.COD 如:D:\lu\lu.COD压缩文件内容=哈夫曼树的核心内容+编码序列
for(int i
4、=0;i<256;i++)
{
header[i].count=0; //初始化权重
header[i].b=(unsigned char)i; //初始化字符
}
ifstream infile(infilename,ios::in|ios::binary);
while(infile.peek()!=EOF)
{
infile.read((char *)&temp,sizeof(unsigned char)); //读入一个字符
header[temp].count++; //统计对应结
5、点字符权重
flength++; //统计文件长度
}
infile.close(); //关闭文件
for(i=0;i<256-1;i++) //对结点进展冒泡排序,权重大的放在上面，编码时效率高
for(int j=0;j<256-1-i;j++)
if(header[j].count
6、 }
for(i=0;i<256;i++)
if(header[i].count==0) break;
leafnum=i; //取得哈夫曼树中叶子结点数
pointnum=2*leafnum-1; //取得哈夫曼树中总结点数目
infile.open(infilename,ios::in|ios::binary); //翻开待压缩的文件
infile.clear();
infile.seekg(0);
ofstream outfile(outfilename,ios::out|ios::binary);
7、 //翻开压缩后将生成的文件
outfile.write((char *)&flength,sizeof(long)); //写入原文件长度
(2)哈夫曼编码
for(i=0;i
8、ar *)&header[i].count,sizeof(unsigned char)); //写入长度的ASCII码
if(header[i].count%8==0)
bytelen=header[i].count/8;
else
{
bytelen=header[i].count/8+1;
strcat(header[i].bits,"0000000"); //在编码后面补0，使其最后凑满8的倍数，
//超过无妨，可以用bytelen控制好写入字节的长度
}
fo
9、r(int j=0;j
10、后就完成了编码对照表的写入
(3) 解压文件
输入一个待解压的压缩文件名称(可带路径 )如:D:\lu\lu.COD从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码；生成(复原)文本文件。文件文件名称=压缩文件名+"_new.t*t"如:D:\lu\lu_new.t*t
while(1)
{
while(readlen<(clength-8)&&strlen(buf)<=256) //读满缓冲区
{
infile.read((char *)&temp,sizeof(temp));
ctoa(temp,code);
11、 //将字节转为数组
strcat(buf,code);
readlen++;
}//while
while(strlen(buf)>=256) //处理缓冲区，直到少于256位，再读满它
{
for(i=0;i
12、te((char *)&temp,sizeof(unsigned char));
writelen++;
strcpy(buf,buf+i+1); //缓冲区前移
break;
}
}//for
if(writelen>=flength) break; //如果写入到达原文件长度，退出
}//while
if(readlen>=(clength-8)/*编码长度*/||writelen>=flength) break; //如果写入
13、或者读入编码完毕，退出
}//退出此循环后，还有未解码完成的buf[]
//对buf[]缓冲的善后处理
while(writelen
14、i+1);
break;
}
}//for
}
infile.close(); //关闭文件
outfile.close();
四、界面设计
程序包含压缩功能，解压功能，输出功能，帮助，终止程序功能。
五、运行测试与分析
〔1〕运行程序，显示提示，如图1.2所示。
图1.2 启动界面
（2） 编码操作。
图1.3在D盘中建立一个文本文档，并命名为123.t*t
图1.4文件压缩，输出哈弗曼编码界面
图1.5在Ｄ盘中生成一个．COD的文档，并且名为12.COD:
〔3〕解码操作。根据实验要求输出实
15、验结果。如图1.4所示。
图1.4 数据结果输出界面
(4) 显示数据内容
假设用户想知道文本输入的内容，可输入"L〞， 然后界面提示输入文本文件的路径和文件名，完成输入后按回车键，界面会出现文本的内容。
六、实验收获与思考
在完成实验的过程中，使我明白了面向对象与面向对象的差异。在面向对象过程中，类的设计是至关重要的，类设计好了等于程序就成功了一半，所以这次的课程帮助我复习了这一学期面向对象课程的学习，刚好可以弥补这一学期面向对象学习的缺乏。同时，也使我对数据构造与算法的知识有了一定的了解，帮我在大二学习数据构造与算法的课程中奠定了一定的根底，使我以后学习数据构造与算法的时候可以更加轻松。
教师评分：
教师签字：
. z.
数据结构哈夫曼编码实验报告
