数据结构课程设计报告.docx

数据结构课程设计报告.docx

《数据结构课程设计报告.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告.docx（18页珍藏版）》请在冰点文库上搜索。

数据结构课程设计报告

数据结构课程设计报告

压缩软件

---采用哈夫曼编码技术

学号：

姓名：

指导教师：

二○○七年九月七日星期五

目录

目录…………………………………………………..2

课程设计课题……………………………………………3

设计要求及分析…………………………………………3

软件开发…………………………………………………3

软件程序基本介绍………………………………………4

程序代码及功能介绍……………………………………4

---------建立哈夫曼树、压缩、解压缩

收获与体会……………………………………………10

附录……………………………………………………11

软件使用说明及图示…………………………………11

【一．】课程设计课题：

压缩软件

【二．】课程设计要求及分析：

要求：

准备一个文件，统计该文件中各种字符的频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成源文件。

数据压缩理论及哈夫曼树简介：

1）数据压缩有2种基本类型：

无损压缩和有损压缩,使用无损压缩方法压缩的文件不会丢失任何信息,他与原文件具有可逆性,就是可以通过解压缩的方法恢复原来的数据,通常对文本文件,字处理文件,应用程序等采用这种算法。

有损压缩算法在压缩时回丢失一些信息，压缩后不能完整恢复出原有信息，较多应用于音频，视频图象数据的处理。

2）此处我们所实现的是哈夫曼算法，在计算机信息处理中，哈夫曼编码是一种变长编码法（又称“熵编码法”），用于数据的无损压缩着一术语是指用一张特殊的编码表对源字符进行编码。

这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现频率高的字符使用教短的编码，出现频率高的则使用教长的，使编码后的字符串的平均期望长度降低，从而达到无损压缩数据的目的），同时保持编码的唯一可解性，这种方法是由美国科学家David.A.Huffman发展起来的。

哈夫曼树是哈夫曼算法的理论描述工具，也称最优二叉树，是一种加权路径长度最短的二叉树。

加权路径长度是指树中所有叶子结点的权值乘上其到根结点的路径长度。

N个叶子结点的哈夫曼树共有2n-1个结点，这个性质将运用于使用数组结构存储哈夫曼树，从根结点开始，左子结点分配0，右子结点分配1，沿着树根到各个结点就得到了哈夫曼编码，因为所有被编码的字符都作为叶子结点出现而每个叶子结点路径又是独立的，保障了每个编码都不会四其余码的前缀，这样的编码又称“哈夫曼无重复前缀编码”，着在下面的程序段会应用到。

3）哈夫曼树也应用于译码过程，译码过程中逐一扫描码文，从哈夫曼的根结点开始，将扫描得到的二进制位串中的相邻位与哈夫曼树上的0，1匹配。

需求分析：

设计目标是要实现哈夫曼压缩的编码器和译码器。

码器工作如下：

首先读入待压缩文件为了保证与原文件信息完全一致，对文件的读写都采用二进制的方式进行。

然后建立并分析字母表，最多只有256种可能的符，对每种字符出现的频度进行统计，以频度作为建立哈夫曼树的权值。

频度表建立好以后，可以建立哈夫曼树，对出现的每种字符进行哈夫曼编码。

此时再读入原文件，逐个字节进行编码，将得到的编码流逐个写入文件。

译码过程相对简单：

读入被压缩文件，将其解释为比特流，根据哈夫曼树对比特流逐个译码，将译码结果逐个写到磁盘文件。

【三．】软件开发：

该软件是在VisualC++6.0环境下编译和运行的,运行时可以直接双击图标:

。

VisualC++6.0是在Windows环境下运行C++的集成环境。

VisualC++6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导ClassWizard等开发工具。

这些组件通过一个名为DeveloperStudio的组件集成为和谐的开发环境。

【四．】软件程序基本介绍：

该压缩软件程序结构采用的是1个CPP文件和一个HEAD文件,界面采用菜单提示输入。

【五．】程序代码及功能介绍：

1．函数结构

在head.h文件中共有3个函数，分别为：

voidSelect（intk,int&s1,int&s2）

voidcompress（）

voiduncompress（）

其中voidSelect（intk,int&s1,int&s2）是在voidcompress（）中调用的，他的功能是在K个元素中选择权值最小的两个结点S1，S2；

voidcompress（）和voiduncompress（）是在a.cpp的main函数中被调用的，他们的功能分别是压缩和解压缩。

2．函数结构图如下：

3．数据结构设计

哈夫曼算法的实现可以采用链表结构生成哈夫曼树，但是效率比较低，也可以使用堆排序，这里采用的是线形表的顺序存储结构：

structhead

{

unsignedcharb;//记录字符在数组中的位置

longcount;//字符出现频率（权值）

longparent,lch,rch;//定义哈夫曼树指针变量

charbits[256];//定义存储哈夫曼编码的数组

}

该存储结构在二叉树中的结点结构如下：

b

count

parent

lch

rch

bits

4．功能设计

compress函数：

该函数将完成压缩目标文件的功能，首先输入文件名，读取目标文件ifp=fopen（filename,"rb"），这里”rb”是按二进制方式进行读操作，输入压缩后的文件名fopen（outputfile,"wb"），其中”wb”是打开或建立一个二进制文件，只允许写数据。

（filename为需要压缩的文件名，outputfile为完成压缩后的文件名）

while（!

feof（ifp））

{

fread（&c,1,1,ifp）;

fread（buffer,size,count,fp）,

header[c].count++;//字符重复出现频率加1

flength++;//出现字符则原文长度加1

}

feof（）为文件检测函数，若文件没有结束返回是0，当文件结束时返回1。

fread（）是从一个流中读数据，fread（buffer,size,count,fp）,其中buffer是一个指针，在fread函数中，它表示存放输入数据的首地址。

size表示数据块的字节数。

count表示要读写的数据块块数。

fp表示文件指针。

for（i=0;i<512;i++）

{

if（header[i].count!

=0）header[i].b=（unsignedchar）i;//如果该字符出现过，将他的哈夫曼码值及其对应的ASCII码存放在一维数组header[i]中，且编码表中的下标和ASCII码满足顺序存放关系。

elseheader[i].b=0;

header[i].parent=header[i].lch=header[i].rch=-1;//是对结点进行初始化。

}

建立哈夫曼树：

for（i=0;i<256;i++）//根据频率（权值）大小，对结点进行排序，选择较小的结点进树。

{

for（j=i+1;j<256;j++）

{

if（header[i].count

{

tmp=header[i];

header[i]=header[j];

header[j]=tmp;

}

}

}

根据哈夫曼树的性质，n个叶子结点（权）需要2n-1个结点来构建一棵哈夫曼树：

for（i=n;i

{

Select（i-1,s1,s2）;

header[s1].parent=header[s2].parent=i;

header[i].lch=s1;

header[i].rch=s2;

header[i].count=header[s1].count+header[s2].count;

}

header[i].lch=s1;//计算左分支权值大小；

header[i].rch=s2;//计算右分支权值大小；

header[s1].parent=header[s2].parent=i;依据parent域值（结点层数）确定树中结点之间的关系；

header[i].count=header[s1].count+header[s2].count;//父结点的权值为其左孩子和右孩子权值之和；

构建哈夫曼树时用到了一个Select（）函数：

在K个元素中选择父结点不为-1的权值最小的两个结点S1，S2；

voidSelect（intk,int&s1,int&s2）

{

s1,s2=0;

longmin1=9999999;

for（intj=1;j

if（header[j].parent!

=-1）

{

if（header[j].count

{

s2=s1;

s1=j;

}

elseif（header[j].count

s2=j;

}

}

longmin1=9999999;假设字符出现频率的最大值（最大权值），比较如下图：

j=1,s1=s2=0

0

1

2

3

4

5

……

j=1,s1=0,header[j].count

0

1

2

3

4

5

……

j=2,s1=1,header[j].count

0

1

2

3

4

5

……

j=3,s1=2,header[j].count

0

1

2

3

4

5

……

哈夫曼无重复前缀编码：

for（i=0;i

{

f=i;

header[i].bits[0]=0;

while（header[f].parent!

=-1）

{

j=f;

f=header[f].parent;

if（header[f].lch==j）//置左分支编码0；

{

j=strlen（header[i].bits）;

memmove（header[i].bits+1,header[i].bits,j+1）;//依次存储连接”0””1”编码；

header[i].bits[0]='0';

}

else//置右分支编码1

{

j=strlen（header[i].bits）;

memmove（header[i].bits+1,header[i].bits,j+1）;

header[i].bits[0]='1';

}

}

}

其中header[i].bits[0]=0;根结点编码0。

将编码好的数据写入文件：

fseek（ifp,0,SEEK_SET）;从文件开始位置向前移动0字节，即定位到文件开始位置

fwrite（&flength,sizeof（int）,1,ofp）;用来将数据写入文件流中，参数flength指向欲写入的数据地址，总共写入的字符数以参数size*int来决定，返回实际写入的int数目；

buf[0]=0;定义缓冲区,它的二进制表示00000000。

while（!

feof（ifp））

{

c=fgetc（ifp）;

f++;

for（i=0;i

{

if（c==header[i].b）break;

}

strcat（buf,header[i].bits）;

j=strlen（buf）;

c=0;

下面对哈夫曼编码位操作进行压缩存储：

while（j>=8）

{

for（i=0;i<8;i++）

{

if（buf[i]=='1'）c=（c<<1）|1;

elsec=c<<1;

}

fwrite（&c,1,1,ofp）;

pt1++;

strcpy（buf,buf+8）;

j=strlen（buf）;

}

if（f==flength）break;

}

其中strcpy（buf,buf+8）;是将一个字节一个字节地拼接起来，pt1是统计压缩以后文件长度的。

对哈夫曼编码位操作进行压缩存储：

if（j>0）

{

strcat（buf,"00000000"）;

for（i=0;i<8;i++）

{

if（buf[i]=='1'）c=（c<<1）|1;

elsec=c<<1;

}

fwrite（&c,1,1,ofp）;

pt1++;

}

数据写入：

for（i=0;i

{

fwrite（&（header[i].b）,1,1,ofp）;

c=strlen（header[i].bits）;

fwrite（&c,1,1,ofp）;

j=strlen（header[i].bits）;

if（j%8!

=0）若存储的位数不是8的倍数，则补0；

{

for（f=j%8;f<8;f++）

strcat（header[i].bits,"0"）;

}

while（header[i].bits[0]!

=0）

{

c=0;

for（j=0;j<8;j++）//字符的有效存储不超过8位，则对有效位数左移实现两字符编码的连接

{

if（header[i].bits[j]=='1'）c=（c<<1）|1;//|1不改变原位置上的"0""1"值；

elsec=c<<1;

}

strcpy（header[i].bits,header[i].bits+8）;//把字符的编码按原先存储顺序连接。

fwrite（&c,1,1,ofp）;

}

}

uncompress函数：

该函数完成的功能是将一个目标压缩文件解压还原，首先输入文件名，读取目标文件ifp=fopen（filename,"rb"），这里”rb”是按二进制方式进行读操作，输入压缩后的文件名fopen（outputfile,"wb"），其中”wb”是打开或建立一个二进制文件，只允许写数据。

fread（&flength,sizeof（long）,1,ifp）;读取原文件长度，对文件进行定位。

fread（&f,sizeof（long）,1,ifp）;

fseek（ifp,f,SEEK_SET）;

fread（&n,sizeof（long）,1,ifp）;

for（i=0;i

{

fread（&header[i].b,1,1,ifp）;

fread（&c,1,1,ifp）;

p=（long）c;读取原文件字符的权值；

header[i].count=p;

header[i].bits[0]=0;

if（p%8>0）m=p/8+1;

elsem=p/8;

for（j=0;j

{

fread（&c,1,1,ifp）;

f=c;

itoa（f,buf,2）;//将f转换为二进制表示的字符串

f=strlen（buf）;

for（l=8;l>f;l--）

{

strcat（header[i].bits,"0"）;

}

strcat（header[i].bits,buf）;

}

header[i].bits[p]=0;

}

for（i=0;i

{

for（j=i+1;j

{

if（strlen（header[i].bits）>strlen（header[j].bits））

{

tmp=header[i];

header[i]=header[j];

header[j]=tmp;

}

}

}

解码：

通过哈夫曼编码的长短，依次解码，从原来的位存储还原到字节存储

while

（1）

{

while（strlen（bx）<（unsignedint）p）

{

fread（&c,1,1,ifp）;

f=c;

itoa（f,buf,2）;

f=strlen（buf）;

for（l=8;l>f;l--）//在单字节内对相应位置补0

{

strcat（bx,"0"）;

}

strcat（bx,buf）;

}

for（i=0;i

{

if（memcmp（header[i].bits,bx,header[i].count）==0）break;

}

strcpy（bx,bx+header[i].count）;//从压缩文件中的按位存储还原到按字节存储字符，字符位置不改变；

c=header[i].b;

fwrite（&c,1,1,ofp）;

m++;//m是用来统计解压后的文件长度

if（m==flength）break;//flength是原文件长度；

}

fclose（ifp）;

fclose（ofp）;关闭文件。

【六】收获与体会

1．静态哈夫曼编码方法有一些缺点：

对于过短的文件进行编码的意义不大，因为光以4BYTES的长度存储哈夫曼树的信息就需1024Bytes的存储空间；

2．对较大的文件进行编码时，频繁的磁盘读写访问会降低数据编码的速度。

经过网上查询已经有了改进之法--动态的哈夫曼编码方法。

动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。

编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。

动态哈夫曼编码比静态哈夫曼编码复杂的多；

3．哈夫曼树是哈夫曼编码的应用，也是编码和译码的核心，是连接编码和译码的纽带。

该压缩软件采用的正是哈夫曼算法，建立哈夫曼树，对原文件中的字符进行哈夫曼编码，通过将哈夫曼算法应用与压缩软件，更进一步理解哈夫曼树的建立和对各个叶子结点的编码。

哈夫曼压缩技术对文本文件压缩效率很高，对于2进制文件这种方法也很成功，但压缩比没有那么显著；

4．编码不是唯一的，但用你的代码算出来的是唯一的，所以传输一定要用自己的代码解码，构造好哈夫曼树后，就可根据哈夫曼树进行编码。

例如：

字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。

只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符；

5．该程序中因为涉及文件操作，多次读写文件，为了保证操作后的文件与原文件的一致性，在打开或者建立新文件时都是以二进制进行操作，着不仅加深了我们对文件操作的理解，也在程序中体现了完整性，并且将解压后的文件和原文件相比较具有一致性，体现的程序的健壮性。

【七】附录

源程序文件名清单：

head.h//完成压缩和解压功能函数

a.cpp//主函数

附：

软件使用说明及图示：

一．使用说明：

该压缩软件的使用界面十分简明，运行环境为DOS操作系统，进入界面后，就会提示输入字符串的输入形式，结束符为“回车符”。

分3个功能选项：

1压缩2解压3退出，选择1或者2时都会有语句提醒你输入被压缩（解压）的目标文件名及压缩（解压）后的生成文件名。

二．使用注意：

压缩的目标文档需要在当前文件夹下，使用时可以直接输入文件名（加后缀），解压后的文件名同理。

三．图示：

1．原始菜单界面：

2．压缩目标文件：

需要实现压缩功能时请按提示输入“1”，压缩的目标文件自备，需要手动输入，压缩后的文件名同理，见图；

3．压还原为原文件：

需要实现解压功能时请按提示输入选择“2”，解压的目标文件自备，需要手动输入，解压后的文件名同理，见图；

4．退出：

需要推出操作时请按提示输入“0”，见图；