数据结构课程设计报告.docx
《数据结构课程设计报告.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告.docx（18页珍藏版）》请在冰点文库上搜索。
数据结构课程设计报告
数据结构课程设计报告
数据结构课程设计报告
压缩软件
一·问题描述
利用哈夫曼编码设计一个压缩软件，能对任何类型的文件进行哈夫曼编码，产生编码后的文件——压缩文件;也能对输入的压缩文件进行译码，生成压缩前的文件——解压文件。
二·基本要求
要求编码和译码的效率尽可能地高。
三·工具/准备工作
已学内容:
哈夫曼树，哈夫曼树构造算法，哈夫曼编码，Huffman压缩算法。
需要的硬件设施与开发软件：
一台计算机，并安装了VisualC++.
四·分析与实现
Huffman树中，叶子结点包含字符以及对应的字符频度（权值）
structHTNode{//压缩用Huffman树结点
unsignedlongweight;//字符频度（权值）
unsignedintparent,lchild,rchild;
};
使用哈夫曼编码可以对文件进行压缩，由于字符的哈夫曼编码以比特为单位，而当将哈夫曼编码以压缩文件进行存储时，压缩文件最少以字节为单位进行存储，因此需要定义字节缓冲器，以便自动将比特转换为字节，定义如下：
structBuffer{//字节缓冲压缩用Huffman树
charch;//字节
unsignedintbits;//实际比特数
};
定义哈夫曼树的抽象基类模板，实现建树，压缩，解压等功能
classHuffmanTree{//Huffman树
public:
voidCode（）;//编码
voidUnCode（）;//译码
private:
HTNodeHT[m+1];//树结点表（HT[1]到HT[m]）
charLeaf[n+1];//叶结点对应字符（leaf[1]到leaf[n]）
char*HuffmanCode[n+1];//叶结点对应编码（*HuffmanCode[1]到*HuffmanCode[n]）
unsignedintcount;//频度大于零的字符数
unsignedintchar_index[n];//字符对应在树结点表的下标（char_index[0]到char_index[n-1]）
unsignedlongsize;//被压缩文件长度
FILE*infp,*outfp;//输入/出文件
Bufferbuf;//字符缓冲
voidStat（）;//统计字符出现频度并过滤掉频度为零的字符
//在HT[0]~HT[k]中选择parent为-1，树值最小的两个结点s1,s2
voidSelect（unsignedintk,unsignedint&s1,unsignedint&s2）;
voidWrite（unsignedintbit）;//向outfp中写入一个比特
voidWrite（unsignedintnum,unsignedintk）;//向outfp中写入k个比特
voidWriteToOutfp（）;//强行写入outfp
voidRead（unsignedint&bit）;//从infp中读出一个比特
voidRead（unsignedint&num,unsignedintk）;//从infp中读出k个比特
intNToBits（unsignedintnum）;//0~num之间的整数用二进位表示所需的最少位数
voidCreateFromCodeFile（）;//由编码文件中存储的树结构建立Huffman树
//由被压缩文件建立Huffman树,将树结构存入编码文件的文件头部中,并求每个字符的Huffman编码
voidCreateFromSourceFile（）;
};
辅助函数Write用于一次向字符缓存中写入一比特，当缓冲器中的比特数为8（也就是一个字节）时，将缓存中的字符写入目标文件中，实现如下：
voidHuffmanTree:
:
Write（unsignedintbit）//向outfp中写入一个比特
{
buf.bits++;
buf.ch=（buf.ch<<1）+bit;
if（buf.bits==8）{//缓冲区已满,写入outfp
fputc（buf.ch,outfp）;
buf.bits=0;
buf.ch=0;
}
}
辅助函数WriteToOutfp用于在哈夫曼编码结束时，强行将缓存写入目标文件中，实现如下：
voidHuffmanTree:
:
WriteToOutfp（）//强行写入outfp
{
unsignedintl=buf.bits;
if（l>0）
for（unsignedinti=0;i<8-l;i++）Write（0）;
}
辅助函数Read用于从infp中读出一个比特，实现如下：
voidHuffmanTree:
:
Read（unsignedint&bit）//从infp中读出一个比特
{
if（buf.bits==0）{
buf.ch=fgetc（infp）;
buf.bits=8;
}
bit=（buf.ch&128）>>7;
buf.ch=buf.ch<<1;
buf.bits--;
}
由被压缩文件建立Huffman树,将树结构存入编码文件的文件头部中,并求每个字符的Huffman编码：
voidHuffmanTree:
:
CreateFromSourceFile（）
//由被压缩文件建立Huffman树,将树结构存入编码文件的文件头部中,并求每个字符的Huffman编码
{
Stat（）;//统计字符出现频度并过滤掉频度为零的字符
//由被压缩文件建立Huffman树
unsignedinti,s1,s2;
for（i=1;i<=count;i++）HT[i].parent=HT[i].lchild=HT[i].rchild=0;
for（i=count+1;i<=2*count-1;i++）{//建立Huffman树
Select（i-1,s1,s2）;//选择parent为0，权值最小的两个结点s1,s2
HT[s1].parent=HT[s2].parent=i;
HT[i].parent=0;HT[i].lchild=s1;HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
//将树结构存入编码文件的文件头部中
unsignedintl;
buf.bits=0;//清空缓冲区
buf.ch=0;
rewind（outfp）;
fwrite（&size,sizeof（unsignedint）,1,outfp）;
Write（count-1,8）;
for（i=1;i<=count;i++）
fwrite（&Leaf[i],sizeof（char）,1,outfp）;
l=NToBits（2*count-1）;
for（i=count+1;i<=2*count-1;i++）{
Write（HT[i].lchild,l）;
Write（HT[i].rchild,l）;
}
//求每个字符的Huffman编码
unsignedintstart,c,f;
char*cd;//编码临时变量
for（i=1;i<=n;i++）
if（HuffmanCode[i]!
=NULL）{
delete[]HuffmanCode[i];//释放存储空间
HuffmanCode[i]=NULL;
}
cd=newchar[count];//分配求编码的工作空间
cd[count-1]='\0';//编码结束符
for（i=1;i<=count;i++）{//逐位求Huffman编码
start=count-1;//编码结束符位置
for（c=i,f=HT[i].parent;f!
=0;c=f,f=HT[c].parent）//从叶到根求编码
if（HT[f].lchild==c）cd[--start]='0';
elsecd[--start]='1';
HuffmanCode[i]=newchar[count-start];//为第i个字符编码分配空间
strcpy（HuffmanCode[i],&cd[start]）;//从cd复制编码到HuffmanCode
}
delete[]cd;
}
同理，由编码文件中存储的树结构建立Huffman树：
voidHuffmanTree:
:
CreateFromCodeFile（）//由编码文件中存储的树结构建立Huffman树
{
buf.bits=0;//清空缓冲区
buf.ch=0;
unsignedintnum,l,i;
rewind（infp）;
fread（&size,sizeof（unsignedlong）,1,infp）;
Read（count,8）;
count=count+1;
for（i=1;i<=count;i++）
fread（&Leaf[i],sizeof（char）,1,infp）;
l=NToBits（2*count-1）;
for（i=1;i<=count;i++）{
HT[i].lchild=0;
HT[i].rchild=0;
}
for（i=count+1;i<=2*count-1;i++）{
HT[i].lchild=（Read（num,l）,num）;
HT[i].rchild=（Read（num,l）,num）;
}
}
压缩操作Code首先要求用户输入源文件与目标文件名，然后统计源文件中个字符出现的频度，以字符出现频度（权值）建立哈夫曼树，再将源文件大小和各字符出现的频度写入目标文件中，最后对源文件中各字节进行哈夫曼编码，将编码以比特为单位写入到目标文件，实现如下：
voidHuffmanTree:
:
Code（）//编码
{
charinfName[256],outfName[256];
cout<<"请输入源文件名（尺寸小于4GB）:
";//被压缩文件最多4GB
cin>>infName;
if（（infp=fopen（infName,"rb"））==NULL）{
cout<<"无法打开文件:
"<system（"PAUSE"）;
exit
（1）;
}
fgetc（infp）;
if（feof（infp））{
cout<<"源文件为空:
"<system（"PAUSE"）;
exit
（1）;
}
cout<<"请输入代码的文件名:
";
cin>>outfName;
if（（outfp=fopen（outfName,"wb"））==NULL）{
cout<<"无法打开文件:
"<system（"PAUSE"）;
exit
（1）;
}
cout<<"处理中..."<unsignedcharch;
unsignedinti,c;
for（i=0;i<=n;i++）HuffmanCode[i]=NULL;
CreateFromSourceFile（）;
rewind（infp）;
ch=fgetc（infp）;
while（!
feof（infp））{
c=char_index[ch];
for（i=0;iif（HuffmanCode[c][i]=='0'）Write（0）;
elseWrite
（1）;
}
ch=fgetc（infp）;
}
WriteToOutfp（）;
fclose（infp）;fclose（outfp）;
cout<<"处理结束."<}
解压操作UnCode，同样首先要求用户输入压缩文件与目标文件名，然后从压缩文件中读入源文件的大小以及各字符出现的频度，以字符出现频度为权值建立哈夫曼树，再对压缩文件的各字节进行解码，并将解码后的字符写入目标文件中，实现如下：
voidHuffmanTree:
:
UnCode（）//译码
{
charinfName[256],outfName[256];
cout<<"请输入代码的文件名:
";
cin>>infName;
if（（infp=fopen（infName,"rb"））==NULL）{
cout<<"无法打开文件:
"<system（"PAUSE"）;
exit
（1）;
}
fgetc（infp）;
if（feof（infp））{
cout<<"空的代码文件:
"<system（"PAUSE"）;
exit
（1）;
}
cout<<"请输入目标文件名:
";
cin>>outfName;
if（（outfp=fopen（outfName,"wb"））==NULL）{
cout<<"无法打开文件:
"<system（"PAUSE"）;
exit
（1）;
}
cout<<"处理中..."<unsignedintbit,c,i;
CreateFromCodeFile（）;//建立Huffman树
Read（bit）;
for（i=0;ic=2*count-1;//2*count-1为根结点的下标
while（（HT[c].lchild!
=0||HT[c].rchild!
=0）&&（feof（infp）==0））{
if（bit==0）c=HT[c].lchild;
elsec=HT[c].rchild;
Read（bit）;
}
fputc（Leaf[c],outfp）;//将字符写入outfp中
}
fclose（infp）;fclose（outfp）;
cout<<"Processend."<}
五·测试与实现
文件夹中有三个文件：
源文件.txt，压缩文件.txt，解压文件.txt，
源文件中如图:
压缩文件与解压文件现在都为空。
首先，进入时的主界面:
选择操作1，压缩文件
输入源文件名:
源文件.txt
输入代码的文件名:
压缩文件.txt
那么可以得到压缩文件:
压缩文件.txt
选择操作2，解压文件
输入代码文件名:
压缩文件.txt
输入目标文件名:
解压文件.txt
这样就得到解压后的文件:
解压文件.txt
查看压缩前文件与解压后的文件，发现完全相同，实际测试结果表明本程序满足
课程设计的要求。
对Word文档进行同样操作，发现解压前文件与解压后的文件也完全相同.
解压前的Word文档:
进行压缩和解压:
得到目标文件:
解压文件.doc
与源文件完全相同。
本程序可满足压缩多种类型软件，测试结果表明本程序满足课程设计的要求，实现了相关功能。
六·实验总结
本程序采用异构数据结构方式实现Huffman树的结点效率高，解压和压缩速率都快，是比较完美的方案。
方案实质是在读入文件字符时，不断地根据已读入的字符统计出各种字符出现的频度，动态建立哈夫曼树，实现对读入字符的编码。
实验的不足在于用了相对简单实用的类String，这样虽然通用性强，但是降低了算法效率，改进实验时可尝试采用C语言风材的串来进行处理。
通过这次课程设计，加深了我对课堂上所讲的哈夫曼算法的认识，了解到算法之中的优势以及不足，提高了对于所学算法的领悟能力，也认识到自己在编程方面的不足之处，有利于今后改进。
升级会员 