数据结构实验报告-文件压缩文档格式.doc
《数据结构实验报告-文件压缩文档格式.doc》由会员分享，可在线阅读，更多相关《数据结构实验报告-文件压缩文档格式.doc（19页珍藏版）》请在冰点文库上搜索。
l统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树，
并将该哈夫曼树保存到文件HufTree.dat中。
l根据哈夫曼树（保存在HufTree.dat中）对每个字符进行哈夫曼编码，并
将字符编码保存到HufCode.txt文件中。
l压缩：
根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。
l解压：
将CodeFile.dat文件利用哈夫曼树译码解压，恢复为源文件。
二、数据结构设计
由于哈夫曼树中没有度为1的结点，则一棵树有n个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中，而且对每个结点而言，即需知双亲结点的信息，又需知孩子结点的信息，由此可采用如下数据结构。
1.使用结构体数组统计词频，并存储:
typedefstructNode{
intweight;
//叶子结点的权值
charc;
//叶子结点
intnum;
//叶子结点的二进制码的长度
}LeafNode[N];
2.使用结构体数组存储哈夫曼树:
typedefstruct{
unsignedintweight;
//权值
unsignedintparent,LChild,RChild;
}HTNode,Huffman[M+1];
//huffman树
3.使用字符指针数组存储哈夫曼编码表：
typedefchar*HuffmanCode[2*M];
//haffman编码表
三、算法设计
1.读取文件，获得字符串
voidread_file（charconst*file_name,char*ch）{
FILE*in_file=Fopen（file_name,"
r"
）;
unsignedintflag=fread（ch,sizeof（char）,N,in_file）;
if（flag==0）{
printf（"
%s读取失败\n"
file_name）;
fflush（stdout）;
}
printf（"
读入的字符串是:
%s\n\n"
ch）;
Fclose（in_file）;
intlen=strlen（ch）;
ch[len-1]='
\0'
;
}
2.统计叶子结点的字符和权值并存储
voidCreateLeaf（charch[],int*ch_len,LeafNodeleaves,int*leaf_num）{
intlen,j,k;
inttag;
*leaf_num=0;
//叶子节点个数
//统计字符出现个数,放入CW
for（len=0;
ch[len]!
='
len++）{//遍历字符串ch[]
tag=1;
for（j=0;
j<
len;
j++）{
if（ch[j]==ch[len]）{
tag=0;
break;
}
}
if（tag）{//*leaf_num=0不用
leaves[++*leaf_num].c=ch[len];
leaves[*leaf_num].weight=1;
for（k=len+1;
ch[k]!
k++）//在之后的字符串中累计权值
if（ch[len]==ch[k]）
leaves[*leaf_num].weight++;
//权值累加
*ch_len=len;
//字符串长度
3．创建HuffmanTree，并存储
创建：
voidCreateHuffmanTree（Huffmanht,LeafNodew,intn）{
inti,j;
ints1,s2;
//初始化哈夫曼树
for（i=1;
i<
=n;
i++）{
ht[i].weight=w[i].weight;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
for（i=n+1;
=2*n-1;
ht[i].weight=0;
for（j=1;
j<
=i-1;
j++）
if（!
ht[j].parent）
s1=j;
//找到第一个双亲为零的结点
for（;
s1=ht[s1].weight>
ht[j].weight?
j:
s1;
ht[s1].parent=i;
ht[i].LChild=s1;
s2=j;
//找到第二个双亲为零的结点
s2=ht[s2].weight>
s2;
ht[s2].parent=i;
ht[i].RChild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
存储：
voidsave_HufTree（Huffmanht,LeafNodele,intln）{
inti;
FILE*HufTree=Fopen（"
HufTree.dat"
"
a"
CreateHuffmanTree（ht,le,ln）;
\n哈夫曼树\n"
编号权值parentLChildRChild\n"
//fputs（"
编号|权值|parent|LChild|RChild\n"
HufTree）;
i<
=2*ln-1;
i++）{/*打印Huffman树的信息*/
%d\t%d\t%d\t%d\t%d\n"
i,（ht）[i].weight,（ht）[i].parent,（ht）[i].LChild,（ht）[i].RChild）;
fprintf（HufTree,"
%d|%d|%d|%d|%d\n"
Fclose（HufTree）;
哈弗曼树已保存至HufTree.dat\n"
4.读取哈夫曼树至新的结构体数组
voidread_HufTree（Huffmanht）{//记得从1开始存储
inti=1,j;
while（（fscanf（HufTree,"
&
j,&
（（ht）[i].weight）,&
（（ht）[i].parent）,&
（（ht）[i].LChild）,&
（（ht）[i].RChild）））==5）{
//printf（"
%d\t%d\t%d\t%d\n"
（ht）[i].weight,（ht）[i].parent,（ht）[i].LChild,（ht）[i].RChild）;
i++;
已从HufTree.dat读取哈弗曼树\n"
5.根据哈夫曼树生成每个叶子结点的编码
voidCrtHuffmanNodeCode（Huffmanht,charch[],HuffmanCodecode_of_leaf,LeafNodeweight,intm,intn）{
inti,c,p,start;
char*cd;
cd=（char*）malloc（n*sizeof（char））;
cd[n-1]='
//末尾置0
start=n-1;
//cd串每次从末尾开始
c=i;
p=ht[i].parent;
//p在n+1至2n-1
while（p）{//沿父亲方向遍历,直到为0
start--;
//依次向前置值
if（ht[p].LChild==c）//与左子相同,置0
cd[start]='
0'
else//否则置1
1'
c=p;
p=ht[p].parent;
weight[i].num=n-start;
//二进制码的长度（包含末尾0）
code_of_leaf[i]=（char*）malloc（（n-start）*sizeof（char））;
strcpy（code_of_leaf[i],&
cd[start]）;
//将二进制字符串拷贝到指针数组code_of_leaf中
free（cd）;
//释放cd内存
6.保存每个叶子结点的信息
voidsave_HufCode（Huffmanht,char*ch,HuffmanCodecode_of_leaf,LeafNodeleaves,intch_len,intleaf_num）{
FILE*HufCode=Fopen（"
HufCode.txt"
CrtHuffmanNodeCode（ht,ch,code_of_leaf,leaves,ch_len,leaf_num）;
//叶子结点的编码
\n每个叶子节点的前缀码\n"
//打印叶子结点的编码
=leaf_num;
i++）{
%c:
%s\n"
leaves[i].c,code_of_leaf[i]）;
fprintf（HufCode,"
leaves[i].c,code_of_leaf[i]）;
Fclose（HufCode）;
每个叶子节点的前缀码已保存至HufCode.txt\n"
7.读取每个叶子节点的信息到新的字符指针数组
voidread_HufCode（HuffmanCodecode_of_leaf）{
inti=1;
charc,tem[10];
while（（fscanf（HufCode,"
&
c,tem））==2）{
intlen=strlen（tem）;
code_of_leaf[i]=（char*）malloc（len*sizeof（char））;
strcpy（code_of_leaf[i],tem）;
c,code_of_leaf[i]）;
已从HufCode.txt读取每个叶子节点信息\n"
8.生成所有字符的编码
voidCrtHuffmanCode（charch[],HuffmanCodecode_of_leaf,HuffmanCodecode_of_ch,LeafNodeleaves,intleaf_num,intch_len）{
inti,k;
for（i=0;
ch_len;
for（k=1;
k<
k++）/*从weight[k].c中查找与ch[i]相等的下标K*/
if（ch[i]==leaves[k].c）
code_of_ch[i]=（char*）malloc（（leaves[k].num）*sizeof（char））;
strcpy（code_of_ch[i],code_of_leaf[k]）;
//拷贝二进制编码
9.保存字符串的编码信息（压缩）
FILE*Fopen（charconst*filename,charconst*mode）{
FILE*idlist;
idlist=fopen（filename,mode）;
if（idlist==NULL）{
perror（filename）;
exit（EXIT_FAILURE）;
}else{
returnidlist;
10.解码并保存到str2.txt
voidTrsHuffmanTree（Huffmanht,LeafNodew,HuffmanCodehc,intn,intm）{
inti=0,j,p;
FILE*str2=Fopen（"
str2.txt"
\n经解压得原文件中的字符串:
"
while（i<
m）{
p=2*n-1;
//从父亲节点向下遍历直到叶子节点
hc[i][j]!
j++）{
if（hc[i][j]=='
）
p=ht[p].LChild;
else
p=ht[p].RChild;
%c"
w[p].c）;
/*打印原信息*/
fputc（w[p].c,str2）;
Fclose（str2）;
\n已将解压得到的字符串保存至str2.txt\n"
11.释放huffman编码内存
voidFreeHuffmanCode（HuffmanCodeh1,HuffmanCodeh2,HuffmanCodehc,intleaf_num,intch_len）{
i++）{//释放叶子结点的编码
free（h1[i]）;
free（h2[i]）;
}
i++）//释放所有结点的编码
free（hc[i]）;
四、运行测试与分析及运行界面
1.文件str1.txt内容：
2.运行程序，读取文件
3.统计叶子节点的权值
4.根据权值生成哈夫曼树，保存至HufTree.dat，并用新的结构体数组读取哈夫曼树
5.HufTree.dat内容
6.根据哈夫曼树生成叶子节点的前缀码，保存至HufCode.txt，之后用新的结构体数组读取HufCode.txt
7.HufCode.txt内容
8.根据前缀码生成哈夫曼编码，保存至CodeFile.dat
9.CodeFile.dat内容
10．根据CodeFile.dat解压，获得原字符串，并保存至str2.txt
11.str2.txt内容
五、实验收获与思考
通过使用哈夫曼树实现文件压缩，使我充分理解哈夫曼树的构造方法以及实际应用，巩固了课堂知识，同时认识到自己的不足。
在编程中发现问题，通过查询求助解决问题，使我不断地我加深数据结构的学习。
六、附录（原程序）
#include<
stdio.h>
stdlib.h>
string.h>
#defineN100
#defineM2*N-1
//haffman编码
//huffman树
//叶子结点的权值
//叶子结点
//叶子结点的二进制码的长度
//产生叶子结点的字符和权值
//创建HuffmanTree
//生成每个叶子结点的编码
//生成所有字符的编码
strcpy（code_of_ch[
升级会员 