数据结构 第6章 实验报告 哈弗曼

数据结构 实验报告

数据结构

实验报告 第六章

实验名称： 文件压缩

实验类型： 综合性实验

班级：

学号：

姓名：

实验日期：2014年6月14日

1.问题描述

哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以达到压缩文件的目的，再用哈夫曼编码进行译码解压缩。

? 统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树，并将该哈夫曼树保存到文件HufTree.dat中。

? 根据哈夫曼树（保存在HufTree.dat中）对每个字符进行哈夫曼编码，并将字符编码保存到HufCode.txt文件中。

? 压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。 ? 解压：将CodeFile.dat文件利用哈夫曼树译码解压，恢复为源文件。

2.数据结构设计

在实验中数据结构设为：

typedef struct

{

char data; //存放字符

unsigned int weight;//权重

unsigned int parent,lchild,rchild;//左孩子标号，右孩子标号 }HTNode,*HuffmanTree; // 动态分配数组存储赫夫曼树

typedef char **HuffmanCode; // 动态分配数组存储赫夫曼编码表

3.算法设计

程序分为以下几个部分：

数据结构 实验报告

（1）统计数据文件里字符以及出现的次数

int *w; //存放每个字符的频数

int i; //用于各种计数

//*********************************************************** //统计1.txt中文件字符以及频数

ifstream fin("d:\\1.txt",ios::in);//从1.txt中读取字符 if(!fin)

{

cout<<"File open error!\n";

return 0;

}

int tongji[256];

int aa; //字符对应的ascii

char cc;//用来读取文件里的字符

for(int ii=0;ii<256;ii++)//初始化

{

tongji[ii]=0;

}

while((cc=fin.get())!=EOF)//从文件读取字符，并建立字符统计数组 {

aa=int(cc);

tongji[aa]++;

}

fin.close();//关闭文件

//**************************************

//用于建立哈弗曼树的统计变量

unsigned int n=0;

for(int ii=0;ii<256;ii++)

{

if(tongji[ii]!=0)

{

n++;

}

}

unsigned int pinshu[n];//每个字符的频数

char zifu[n];//文件中出现的字符

int n1=0;//范围从0--n-1，用于出现过字符的赋值

for(int ii=0;ii<256;ii++)

{

if(tongji[ii]!=0)

{

pinshu[n1]=tongji[ii];

数据结构 实验报告

zifu[n1]=char(ii); ++n1; } }

（2）依据字符出现的频率建立哈弗曼树

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n,char zi[])

{ // w存放n个字符的权值(均>0),zi[]存放n字符，6构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC

int m,i,s1,s2,start;

unsigned c,f;

HuffmanTree p;

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,++zi) //初始化哈弗曼树

{

(*p).weight=*w;

(*p).data=*zi;

(*p).parent=0;

(*p).lchild=0;

(*p).rchild=0;

}

for(;i<=m;++i,++p) //非叶子节点的父亲为0

(*p).parent=0;

for(i=n+1;i<=m;++i) // 建赫夫曼树

{ // 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2

select(HT,i-1,s1,s2);

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<=n;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

cd[--start]='1';

HC[i]=(char*)malloc((n-start)*sizeof(char));

// 为第i个字符编码分配空间

strcpy(HC[i],&cd[start]); // 从cd复制编码(串)到HC

}

free(cd); // 释放工作空间

}

int min(HuffmanTree t,int i)

{ // 函数void select()调用

int j,flag;

unsigned int k=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;

return flag;

}

void select(HuffmanTree t,int i,int &s1,int &s2)

{ // s1为最小的两个值中序号小的那个

int j;

s1=min(t,i);

s2=min(t,i);

if(s1>s2)

{

j=s1;

s1=s2;

s2=j;

}

}

（3）存储哈弗曼树，建立字符与哈弗曼编码的对应关系文件

//哈弗曼编码对应表写入

fstream f("d:\\HuffCode.txt",ios::out);//生成哈弗曼编码与字符的对照表 for(i=1;i<=n;i++)//输出字符与哈弗曼编码对照表

{ f<<zifu[i-1]<<"的哈弗曼编码："<<HC[i]<<endl;}

f.close();

fstream fouthf("d:\\文字翻译到哈弗曼.txt",ios::out);//将翻译后的文字，

数据结构 实验报告

//写入翻译后的文件

ifstream fin1("d:\\1.txt",ios::in);//从1.txt中逐个字符读取

if(!fin1)

{

cout<<"File open error!\n";

return 0;

}

while((cc=fin1.get())!=EOF)//从文件读取字符，

{

for(i=0;i<n;i++)

{

if(cc==zifu[i]) fouthf<<HC[i+1];//把字符对应哈弗曼编码写入 //文件“文字翻译到哈弗曼”

}

}

fin1.close();//关闭文件

fouthf.close();

（4）根据哈弗曼树对数据文件里的数据进行翻译，得到哈弗曼编码

fstream fouthf("d:\\文字翻译到哈弗曼.txt",ios::out);//将翻译后的文字，

写入翻译后的文件

ifstream fin1("d:\\1.txt",ios::in);//从1.txt中逐个字符读取

if(!fin1)

{

cout<<"File open error!\n";

return 0;

}

while((cc=fin1.get())!=EOF)//从文件读取字符，

{

for(i=0;i<n;i++)

{

if(cc==zifu[i]) fouthf<<HC[i+1];//把字符对应哈弗曼编码写入

文件“文字翻译到哈弗曼”

}

}

fin1.close();//关闭文件

fouthf.close();

（5）将哈弗曼编码的8位作为一个字节的8位，以字符形式存进另一文件

//把翻译后的哈弗曼存进数组zongchanghafu[]

char zongchanghafu[sum];

ifstream fin4("文字翻译到哈弗曼.txt",ios::in);//从 文字翻译到哈弗

//曼.txt 中逐个读取哈弗曼编码

if(!fin4)