文件压缩程序设计报告

《数据结构》课程设计实验报告题目：压缩软件（选做题）姓名：学号：指导老师：时间：2015.09.06目录一、设计内容和要求 (3)二、算法思想描述 (3)三、程序结构 (4)四、结果与分析 (5)结果 (5)分析 (9)五、收获与体会 (9)一、设计内容和要求设计内容：压缩软件要求：建立一个文本文件A（可以是C/C++源程序），统计该文件中各字符频率。

首先对各字符进行Huffman编码，将该文件翻译成Huffman编码文件B；然后将Huffman编码文件译码成文件C，并对文件A与C进行比较。

二、算法思想描述1.Huffman编码解码思想：Huffman树是一种加权路径长度最短的二叉树。

编码时，是根据待编码文件中记录的关键字在文件中出现的频率进行编码，每个关键字都对应一个编码，频率较高则编码较短，频率较低则编码较长。

Huffman树解码时，根据记录的关键字的编码对文件进行解码。

具体方法为依次选择权值最小的两个关键字作为左右孩子，其和作为父结点的权值，将其父结点代替两个子结点，再次选择权值最小作为左右孩子，依次进行下去，直到所有的关键字结点都成为叶子结点。

根据创建的Huffman树来确定个关键字的01编码，左孩子为0，右孩子为1。

2.整体算法描述：首先读入待压缩文件，然后对每种字符出现的频度进行统计，以频率作为建立哈夫曼树的权值。

接着建立哈夫曼树，对出现的每种字符进行哈夫曼编码。

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

译码过程：读入被压缩文件，根据哈夫曼树对文件中的字符逐个译码，将译码结果逐个写入文件。

三、程序结构压缩软件的程序流程图压缩软件的函数功能结构图四、结果与分析结果1.界面2.压缩文件3.解压文件4.比较分析1.检查程序的正确性本程序运行时生成两个文件，文件名分别为A.txt 和C.txt 。

当C.txt 和原文件的内容大小一致时，说明程序功能已经实现的，在VC的环境下，二者是相同的，仅文件名的差异。

压缩实验报告数据分析1. 引言本文对压缩实验的数据进行了分析和总结。

压缩是一种常见的数据处理技术，通过减少文件的大小，可以提高存储和传输效率。

本实验旨在探究不同压缩算法对不同类型的数据的效果以及压缩率的变化情况。

2. 数据收集和实验设计在本实验中，我们收集了不同类型的数据文件，包括文本文件、图像文件和音频文件。

我们选择了三种常用的压缩算法，分别是gzip、zip和tar。

每个数据文件都分别用这三种算法进行了压缩，并记录了压缩前后的文件大小。

实验设计如下： - 数据收集：从不同来源收集文本、图像和音频文件。

- 压缩算法选择：选择gzip、zip和tar作为压缩算法。

- 压缩实验：分别使用这三种压缩算法对每个数据文件进行压缩。

- 数据记录：记录每个文件的原始大小和压缩后的大小。

3. 数据分析3.1 压缩率分析首先，我们对每个数据文件进行了压缩率的计算。

压缩率表示压缩后文件大小与原始文件大小的比值，可以反映出压缩算法的效果。

表格1：不同数据文件的压缩率文件名gzip压缩率zip压缩率tar压缩率文本文件0.4 0.3 0.35图像文件0.6 0.5 0.55音频文件0.2 0.15 0.18从表格1中可以看出，不同类型的数据文件在不同的压缩算法下的压缩率有所不同。

图像文件的压缩率相对较高，而音频文件的压缩率相对较低。

3.2 压缩算法效果比较接下来，我们对不同压缩算法在同一类型的数据文件上的效果进行了比较。

我们选择了文本文件进行分析。

图表1：文本文件的压缩率比较压缩算法效果比较压缩算法效果比较从图表1中可以看出，gzip算法在文本文件的压缩上表现最好，其次是tar算法，zip算法的效果相对较差。

4. 结论通过本次实验的数据分析，我们得出了以下结论： - 不同类型的数据文件在不同的压缩算法下的压缩率有所不同。

- 对于文本文件，gzip算法表现最好，zip算法效果相对较差。

压缩算法的选择应该根据具体的应用场景和需求来进行，综合考虑压缩率和解压缩速度等因素。

《数据结构》课程设计数学与应用数学一班胡耕岩 2012214147一、问题分析和任务定义1.1设计任务采用哈夫曼编码思想实现文件的压缩和恢复功能，并提供压缩前后的占用空间之比。

要求（1）运行时的压缩原文件的规模应不小于5K。

（2）提供恢复文件与原文件的相同性对比功能。

1.2问题分析本课题是利用哈夫曼编码思想，设计对一个文本文件（.txt）中的字符进行哈夫曼编码，生成编码压缩文件，并且还可将一个压缩后的文件进行解码还原为原始文本文件（.txt）。

在了解哈夫曼压缩解压缩原理之前，首先让我们来认识哈夫曼树。

哈夫曼树又称最优二叉树，是带权路径长度最小的二叉树。

在文本文件中多采用二进制编码。

为了使文件尽可能的缩短，可以对文件中每个字符出现的次数进行统计。

设法让出现次数多的字符二进制码短些，而让那些很少出现的字符二进制码长一些。

若对字符集进行不等长编码，则要求字符集中任一字符的编码都不是其它字符编码的前缀。

为了确保哈夫曼编码的唯一性，我们可以对它的左右子树的大小给予比较限定，如：左子树的权值小于右子树的权值。

哈夫曼树中的左右分支各代表‘0’和‘1’,则从根节点到叶子节点所经历的路径分支的‘0’和‘1’组成的字符串，为该节点对应字符的哈夫曼编码。

统计字符中每个字符在文件中出现的平均概率（概率越大，要求编码越短）。

利用哈夫曼树的特点：权越大的叶子离根越近，将每个字符的概率值作为权值，构造哈夫曼树。

则概率越大的节点，路径越短。

哈夫曼译码是从二进制序列的头部开始，顺序匹配成共的部分替换成相应的字符，直至二进制转换为字符序列。

哈夫曼用于文件解压缩的基础是在压缩二进制代码的同时还必须存储相应的编码，这样就可以根据存储的哈夫曼编码对压缩代码进行压缩。

总之，该课题的任务应该是首先要打开要压缩的文本文件并读出其字符出现的频率，以其为权值构建哈夫曼树。

其次要找到构建压缩功能的方法，在构建哈夫曼树的基础上进行编码，改变字符原先的存储结构，以达到压缩文件的目的，以外还有存储相应的哈夫曼编码，为解压缩做准备。

用Huffman编码实现文档压缩实验目的1.了解有关文件的基本概念和操作2.掌握哈夫曼树的概念及其构造方法3.运用哈夫曼树及其编码实验环境Windows 7 Professional Service Park 1 ,64bitMicrosoft Visual Studio 2010实验内容输入需要压缩的文本文件名，对该文件中的各个字符出现的频度进行统计，然后构建Huffman编码树及Huffman编码表。

读入源文件，将源文件翻译成Huffman编码文件，输出到文件1.huf，最后读入1.huf文件，将Huffman编码文件翻译成文本文件，输出到_1.txt。

要求计算压缩比输出：压缩比是编码后文件字符数除以编码前文件中含有字符数。

设计概要压缩部分1.构造哈夫曼树，对其进行前缀编码（1）扫描待压缩文件，得出各字符出现频率。

（2）根据给定的n个权值{W1,W2,...Wn}构成n棵二叉树的集合F={T1，T2，…，Tn}，每棵二叉树Ti中只有一个带权为Wi的根节点，其左右子树均空。

（3）在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且值新的二叉树的根节点的权值为其左右子树上根节点的全值之和。

（4）在F中删除这两棵树。

同时将新得到的二叉树加入F中。

重置（2）和（3），直到F只含一棵树为止。

这棵树便是哈夫曼树。

2.由Huffman树得到各字符前缀编码。

3.根据前缀编码，对文件中各个字符进行编码，并按每八位一次写入压缩文件。

4.处理剩余不到八位部分，写入压缩文件。

5.将前缀编码及相关信息写入压缩文件。

6.关闭指针，完成压缩。

计算压缩率。

解压部分1.读入压缩文件长度和源文件长度、读入前缀编码。

2.对文件中各字符解码，写入解压文件。

源码：#include<stdio.h>#include<malloc.h>#include<string.h>#include <stdlib.h>struct hufflist{unsigned char asc;long weight;char code;int par,lch,rch;hufflist(){asc=-1;weight=0;par=lch=rch=-1;}; //初始化};//缓冲队列typedef struct temp{int n,fr,be;char ctemp[1200];temp(){n=fr=be=0;};int push(char ch){if(n>1024)return 1;ctemp[be]=ch;be++;be=be%1024;n++;return 0;};char pop(void){char ch;if(n==0)return 0;ch=ctemp[fr];fr++;fr=fr%1024;n--;return ch;};}temp;void main(){FILE *fp1,*fp2,*fp3;int ch=0;float ra;char infile[256];char outfile[256];float compress(FILE *infile,FILE *outfile);void uncompress(FILE *infile,FILE *outfile);while(ch!=3){system("cls");printf("==================文档压缩&解压工具================== \n\n\n");printf("① >> 压缩文档\n\n② >> 解压文档\n\n③ >> 退出程序\n\n\n");printf("请输入要进行的操作：\n");scanf("%d",&ch);switch(ch){case 1:{printf("请输入原文件路径：");getchar();gets(infile);if((fp1=fopen(infile,"r"))==NULL){printf("ERROR！文件打开失败！\n");getchar();break;}printf("请输入输出文件路径：");gets(outfile);if((fp2=fopen(outfile,"wb"))==NULL){printf("ERROR！文件打开失败！\n");getchar();break;}if(strcmp(infile,outfile)==0){printf("ERROR！文件路径冲突！\n");getchar();break;}ra=compress(fp1,fp2);printf("文件压缩完成！\n");printf("压缩比率为%.4f%%\n",ra*100);getchar();break;}case 2:{printf("请输入原文件路径：");getchar();gets(infile);if((fp2=fopen(infile,"rb"))==NULL){printf("ERROR！文件打开失败！\n");getchar();break;}printf("请输入输出文件路径：");gets(outfile);if((fp3=fopen(outfile,"w"))==NULL){printf("ERROR！文件打开失败！\n");getchar();break;}if(strcmp(infile,outfile)==0){printf("ERROR！文件路径冲突！\n");getchar();break;}uncompress(fp2,fp3);printf("文件解压完毕！\n");getchar();break;}default:{ch=3;printf("程序关闭！\n");break;}}}return;}float compress(FILE *infile,FILE *outfile){struct hufflist HT[513];char **HC;int ROOT,i,j,k,s,node_count=0,lnode_count,lnode_count_t,ad1,ad2;//node_count 总结点个数 lnode_count没有父节点的节点个数long weight2=0;float sv,a,b;unsigned char ch;temp mytemp;char *ct=NULL;//先统计输入文本infile中字符信息ch=fgetc(infile);while(!feof(infile)){for(i=0;i<=513;i++){if(HT[i].asc==ch){HT[i].weight++;break;}if(HT[i].weight==0){HT[i].asc=ch;HT[i].weight++;node_count++;break;}}ch=fgetc(infile);}lnode_count=node_count;lnode_count_t=lnode_count;while(lnode_count_t>1){//找到权值最小节点for(i=0;i<node_count;i++){if(HT[i].par==-1)break;}ad1=i;for(j=i+1;j<node_count;j++){if(HT[j].par==-1&&HT[j].weight<HT[i].weight)ad1=j;}HT[ad1].par=1;//找到权值次小节点for(i=0;i<=node_count;i++){if(HT[i].par==-1)break;}ad2=i;for(j=i+1;j<node_count;j++){if(HT[j].par==-1&&HT[j].weight<HT[i].weight)ad2=j;}HT[ad2].par=1;HT[ad1].par=HT[ad2].par=node_count;HT[node_count].lch=ad1;HT[node_count].rch=ad2;HT[ad1].code=0;HT[ad2].code=1;HT[node_count].weight=HT[ad1].weight+HT[ad2].weight;node_count++;lnode_count_t--;}ROOT=node_count-1;fwrite(HT,sizeof(struct hufflist),513,outfile);//建立编码表HC=(char **)malloc(256*sizeof(char *));ct=(char *)malloc((lnode_count+1)*sizeof(char));ct[lnode_count]=-1;for(i=0;i<=255;i++){HC[i]=NULL;}for(i=0;i<lnode_count;i++){for(k=i,j=lnode_count-1;HT[k].par!=-1;k=HT[k].par,j--){ct[j]=HT[k].code;}HC[HT[i].asc]=(char*)malloc(lnode_count*sizeof(char));for(s=0,j++;ct[j]!=-1;s++,j++){HC[HT[i].asc][s]=ct[j];}HC[HT[i].asc][s]=-1;}rewind(infile);//重编码ch=fgetc(infile);while(!feof(infile)){for(i=0;HC[ch][i]!=-1;i++){mytemp.push(HC[ch][i]);}while(mytemp.n>=8){ch=128*mytemp.pop()+64*mytemp.pop()+32*mytemp.pop()+16*mytemp.pop()+8*mytemp.pop()+4*my temp.pop()+2*mytemp.pop()+mytemp.pop();fwrite(&ch,1,1,outfile);weight2++;}ch=fgetc(infile);}while(mytemp.n>0){ch=128*mytemp.pop()+64*mytemp.pop()+32*mytemp.pop()+16*mytemp.pop()+8*mytemp.pop()+4*my temp.pop()+2*mytemp.pop()+mytemp.pop();fwrite(&ch,1,1,outfile);weight2++;}fclose(infile);fclose(outfile);a=weight2+513*sizeof(struct hufflist);b=HT[ROOT].weight;sv=a/b;return(sv);}void uncompress(FILE *infile,FILE *outfile){struct hufflist HT[513];int ROOT,i=0;unsigned char ch;temp mytemp;fread(HT,sizeof(struct hufflist),513,infile);while(HT[i].par!=-1){i=HT[i].par;}ROOT=i;fread(&ch,1,1,infile);while(!feof(infile)){while(mytemp.n<=768&&(!feof(infile))){for(i=0;i<=7;i++){mytemp.push((ch<<i&128)/128);}fread(&ch,1,1,infile);}i=ROOT;do{if(mytemp.pop())i=HT[i].rch;elsei=HT[i].lch;}while(HT[i].lch!=-1);fputc(HT[i].asc,outfile);}while(mytemp.n>0){i=ROOT;do{if(mytemp.pop())i=HT[i].rch;elsei=HT[i].lch;}while(HT[i].lch!=-1&& mytemp.n>0);fputc(HT[i].asc,outfile);}fclose(infile);fclose(outfile);return;}数据测试文件： D:\1.txt(英文原著《飘》) 大小：2.25MB 程序运行界面：压缩后实际文件大小对比：解压后文件对比：进一步测试了多个文本文件，程序运行正常，未发现错误。

课程设计报告题目：简单压缩软件课程名称：并行与串行数据结构与算法专业班级：ACM1301学号：姓名：指导教师：报告日期：2015年9月27日计算机科学与技术学院任务书☐设计内容本实验要求实现一个简单的压缩软件。

压缩软件由两部分—编码器和译码器组成。

编码器位于发送端，可以将文件进行压缩，体积减小；译码器位于接收端，可以将文件进行解压，恢复原文件。

☐设计要求（1）压缩解压过程保证无损（2）实现两种压缩策略，第一种压缩文件后缀名记为.CS，要求在保证一定的压缩率的情况下体现压缩速率；第二种压缩文件后缀名记为.SCS，强调压缩率，但时间也需要比较合理（3）压缩文件中保存了需要解压的全部信息（4）具有图形化进度条显示压缩过程和解压过程的进度和显示估计剩余时间的功能（5）具有图形化选项选择将编码信息输出到指定磁盘目录的功能（6）实验所使用的算法不限，实验报告中需要详细描述使用的算法策略。

（7）软件的衡量标准对比标准的压缩软件，实验检查时需要准备一定的统计对比信息加以佐证，实验报告中也需要对压缩软件的优劣进行详细的建模分析。

☐参考文献[1]LZW for GIF 算法原理实现，/whycadi/article/details/760576[2]Qt参考文档，/qtdocument/[3] 几种压缩算法，/txz_yshb/article/details/9379265目录任务书 (I)1引言 (3)1.1课题背景与意义 (3)1.1.1数据压缩标准 (4)1.1.2数据压缩评价 (5)1.2国内外研究现状 (5)1.3课程设计的主要研究工作 (6)2系统需求分析与总体设计 (7)2.1系统需求分析 (7)2.2系统总体设计 (7)3系统详细设计 (8)3.1有关数据结构的定义 (8)3.2主要算法设计 (9)4系统实现与测试 (11)4.1系统实现 (11)4.2系统测试 (11)5总结与展望 (13)5.1全文总结 (13)5.2工作展望 (13)6体会 (14)附录 (15)1引言1.1课题背景与意义信息如何被高效存储和传递的问题一直是计算机研究的一个重要课题, 而解决这一问题的最常用的就是数据压缩技术。

数据结构课程设计报告实验二：文本文件压缩一、设计要求1、问题描述：根据huffman编码以及二叉树的相关知识实现文本文件的压缩（即将输入的字符串转换为二进制编码）和解压（即将二进制编码转换为字符串）2、输入：文本文件（压缩文件）。

3、输出：压缩文件（文本文件）。

知识点：堆、霍夫曼树、二叉树遍历实际输入输出情况：源文件为文本文件，内容如下：输出的文件是以.zl0010为扩展名的二进制文件，将其用记事本以文本方式打开得到如下文件：解压过程如下：解压获得的文件doc.txt.zl0010.txt比较发现源文件与解压缩后文件内容相同。

一、数据结构与算法描述1.对输入文件的处理创建文件输入流，将源文本文件以二进制方式打开，建立保存每个Byte频率的数组count[256]，并通过对文件的第一次遍历，完成对Byte频率的统计。

其中bytecount变量记录输入的字节数，关键代码如下：string filename;//文件名int count[256];//每个字符的频率for(int i=0;i<256;i++)count[i]=0;std::ifstream ifs;//输入流std::cout<<"请输入需要压缩的文件路径"<<std::endl;std::cin>>filename;ifs.open(filename,std::ifstream::binary);if(!ifs){std::cout<<"文件打开错误"<<std::endl;system("pause");exit(0);}char buf;int bytecount=0;//计算总共输入了多少字节std::cout<<"正在计算频率……"<<std::endl;while(!ifs.eof()){ifs.read((char*)&buf,1);/*buf+=128;count[buf]++;*/if(ifs.eof())break;count[(int)buf+128]++;bytecount++;/*std::cout<<(int)buf<<std::endl;*/}2.哈夫曼树的建立及编码过程以第一步中统计的Byte出现频率为每个树节点的权值，进行哈夫曼树的构建，并通过构建的哈夫曼树，获取std::string类型的哈夫曼编码。

LZSS压缩算法实验报告一、引言LZSS是一种常用的压缩算法，被广泛应用于数据压缩领域。

它的核心思想是通过利用数据中存在的重复信息来实现压缩。

本实验主要对LZSS压缩算法进行研究与实验，评估其压缩效果和性能。

二、算法原理LZSS算法是一种基于滑动窗口和查找缓冲区的字典算法。

其主要思想是将输入数据分为两个部分：滑动窗口和查找缓冲区。

滑动窗口维护了最长匹配的前缀字符串，而查找缓冲区则用来寻找重复的字符串。

具体实现步骤如下：1.初始化滑动窗口和查找缓冲区；2.在滑动窗口中寻找与查找缓冲区中最长匹配的字符串；3.若找到匹配字符串，则将其标记为索引和长度的形式；4.若未找到匹配字符串，则将当前字符输出；5.更新滑动窗口和查找缓冲区；6.重复2-5步骤，直到所有字符处理完毕。

三、实验设计本实验的主要目的是评估LZSS压缩算法的压缩效果和性能表现。

为了完成实验，我们设计了以下实验流程：1.实现LZSS压缩和解压缩算法；2.准备不同类型和大小的文件，用于测试压缩算法的效果；3.运行压缩算法，并记录压缩比、压缩时间和解压缩时间；4.对比不同类型和大小的文件的压缩比和压缩时间；5.分析实验结果并给出评估。

四、实验结果与分析我们分别对文本文件、图像文件和音频文件进行了压缩实验。

实验结果如下：1.文本文件压缩实验结果：压缩比为70%，压缩时间为0.5秒，解压缩时间为0.3秒。

2.图像文件压缩实验结果：压缩比为80%，压缩时间为1秒，解压缩时间为0.6秒。

3.音频文件压缩实验结果：压缩比为60%，压缩时间为0.8秒，解压缩时间为0.4秒。

从实验结果可以看出，不同类型的文件对LZSS压缩算法的效果存在差异。

文本文件由于存在大量的重复信息，所以可以获得较高的压缩比。

而图像文件和音频文件的压缩比较低，因为它们的数据特征较为复杂，存在较少的重复信息。

压缩时间和解压缩时间较短，说明LZSS压缩算法具有较好的性能表现。

五、总结本实验通过对LZSS压缩算法的实验研究，评估了其压缩效果和性能表现。

东北大学信息科学与工程学院数据结构课程设计报告题目哈夫曼压缩软件设计课题组长王健课题组成员张颖刘琪张晓雨专业名称计算机科学与技术班级计1307指导教师杨雷2015 年1月课程设计任务书目录1 课题概述 (4)1.1 课题任务 (4)1.2 课题原理 (4)1.3 相关知识 (4)2 需求分析 (5)2.1 课题调研 (5)2.2 用户需求分析 (5)3 方案设计 (5)3.1 总体功能设计 (5)3.2 数据结构设计 (6)3.3 函数原型设计 (6)3.4 主算法设计 (7)3.5 用户界面设计 (9)4 方案实现 (12)4.1 开发环境与工具 (12)4.2 程序设计关键技术 (12)4.3 个人设计实现（按组员分工）4.3.1 王健设计实现 (12)4.3.2 张颖设计实现 (17)4.3.3 刘琪设计实现 (20)4.3.4 张晓雨设计实现 (22)5 测试与调试 (25)5.1 个人测试（按组员分工） (25)5.1.1 王健测试 (25)5.1.2 张颖测试 (26)5.1.3 刘琪测试 (27)5.1.4 张晓雨测试 (31)5.2 组装与系统测试 (32)5.3 系统运行 (32)6 课题总结 (33)6.1 课题评价 (33)6.2 团队协作 (33)6.3 下一步工作 (33)6.4 个人设计小结（按组员分工） (33)6.4.1 王健设计小结 (33)6.4.2 张颖设计小结 (34)6.4.3 刘琪设计小结 (34)6.4.4 张晓雨设计小结 (34)7 附录A 课题任务分工 (35)A-1 课题程序设计分工 (35)A-2 课题报告分工 (36)附录B 课题设计文档（光盘） (37)B-1源程序代码（*.H，*.CPP） (37)B-2工程与可执行文件） (37)附录C 用户操作手册（可选） (37)C.1 运行环境说明 (37)C.2 操作说明 (37)1 课题概述1.1课题任务采用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。

数据结构课程设计报告压缩软件---采用哈夫曼编码技术学号：二○○八年九月三日星期三目录课程设计课题 (3)设计要求及分析 (3)软件开发 (3)类的结构图 (4)程序类的说明 (4)较有特色的函数 (5)测试结果 (6)收获与体会 (7)【一】课程设计课题：压缩软件【二】设计要求及分析：要求：建立一个文本文件A，统计该文件中各字符的频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件B，再将Huffman编码文件译码成文件C，并对文件A与C进行比较。

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

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

哈夫曼树简介：标准ASCII码把每个字符分别用一个7位的二进制数表示，这种方法使用最少的位表示了所有ASCII码中的128个字符，称为等长编码，如果每个字符的使用频率相等，等长编码是空间效率最高的方法。

如果字符出现的频率不同，可以让频率高的字符采用尽可能短的编码，频率低的字符采用稍长的编码，来构造一种不等长编码，则会获得更好的空间效率。

而此处我们所实现的哈夫曼算法，就是一种不等长编码，用于数据的无损压缩。

术语是指用一张特殊的编码表对源字符进行编码。

这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的，同时保持编码的唯一可解性，这种方法是由美国科学家David.A.Huffman发展起来的。

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

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

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

《数据结构》实验报告利用Huffman编码对文件进行压缩解压学生:XXX学号:XXXXXXXX联系:XXXXXX@(一)基本信息1.实验题目利用Huffman编码对文件进行压缩解压2.完成人（姓名、学号）姓名：XXX 学号：XXXXXXXX3.报告日期2007年12月12日星期二(二)实习内容简要描述1.实习目标学会对树的基本操作学会对文件进行操作利用Huffman编码对文件压缩解压2.实习要求实现最小堆模板类利用最小堆构建Huffman树实现Huffman编码和解码根据用户从键盘输入的报文文本,输出各字符的Huffman编码以及报文的编码根据用户从键盘输入一串报文文本，输出各字符的Huffman编码输出报文的Huffman编码及长度根据输入的Huffman编码，解码输出利用Huffman编码和解码对二进制文件的压缩和解压(三)报告主要内容1.设计思路开发环境：Microsoft Visual C++ 2005设计思路：1.设计Pack类储存字符的权值2.设计MinHeap模板类构建最小堆3.设计ExtBinTree模板类为带权二叉树4.设计Compress模板类以实现文件的压缩解压2.主要数据结构1.MinHeap.h: 头文件,包含MinHeap模板类的类界面以及定义;2.HuffmanTree.h:头文件,包含ExtBinTree模板类以及Compress模板类的类的的类界面以及定义3.main.cpp:调用上述头文件实现相关操作3.主要代码结构主要代码结构为见附件中各文件的代码注释4.主要代码段分析主要代码段分析，见附件中的代码注释(四)实习结果1.基本数据源程序代码行数：约800行完成该实习投入的时间：二十四小时(不包括写实验报告的时间)与其他同学讨论交流情况:感谢刘畅同学对程序的测试2.测试数据设计1.对屏幕输入字符进行Huffman编码2.根据Huffman树非唯一性,虽然和课件上有些许不同,但是还是正确的3.输入字符串:CASTCASTSATATATASA4.输出编码:A:0 C:110 S:111 T:105.输入霍夫曼编码:01110101101106.输出译码:ASATCC7.8.对”实验05.PPT”的压缩操作9.使用0秒(不足一秒按0秒计算),压缩率为56.1755%10.对”实验05.ppt.hfm”(即刚才生成的压缩文件)的解压操作11.使用0秒(不足一秒按0秒计算),解压后文件无异常12.对一个18M的EXE安装包前后进行压缩和解压操作,分别用时10秒和9秒3.测试结果分析A)程序运行的系统资源配置操作系统：Microsoft Windows XP Professional SP2CPU: AMD Athlon 3600+ 2.0GRAM: 1024M DDRII开发环境：Microsoft Visual C++ 2005B)对TXT文档进行压缩和解压后,通过WinMerge检验和原文件无差异C)对MP3和EXE文件压缩和解压后仍能正常使用D)对于中文名字和带有空格的路径均能正确无误识别E)文件名只能小于16个字符(包括后缀名),否则解压会出错(只预留了16个字节用于储存文件名)F)相对于不用文件块读写的程序,效率提高了三倍以上G)具有动态进度条,可以显示当前压缩和解压的进度百分比(当然消耗了一些系统资源)H)出错处理不够充分,特别是cin部分,如果误输入可能会造成死循环(五)实习体会1.实习过程中遇到问题及解决过程A)一开始时候的程序运行很慢,,压缩一个4M左右的文件需要七八秒,后来改用文件块缓存字节来读写后,压缩一个4M的文件只需要两秒左右的时间.本来是只想写一个进度条而已的,后来发现如果只读一个字节就判断一次进度条的话会很消耗系统资源,后来干脆麻烦点用文件块来缓存.不过至于一次缓存多少字节才能达到最好的效果还未知,现在设置的是一次缓存40KB 的数据B)本来一个一个字节读的时候对最后一个字节的操作基本没费什么劲,但是在文件块读写的时候就不是那么清晰明了了,后来经过仔细Debug,才找到错误的所在.许多问题都是这样C)对于中文名和带空格路径,用C++的fstream就不支持,但是C中的FILE*就支持,不知道为什么.还有C++中的fstream的成员函数read返回值很奇怪,不知道如何获取成功读入的项数.改用C中的FILE*文件指针后就解决掉了D)由于这次实验的各个步骤是一环套一环的,在哪里出错很难找得出来,所以这次实验调试消耗的时间特别多.最郁闷的一次错误是发现在取得字符C的第N位函数中,居然把0x40写成了0x30.有时候文件解压出来不对,但是又不清楚是压缩时候错了,还是解压时候错了,然后就要两个函数都要检查一遍.2. 实习体会和收获这次实验最大的特点在于难找错,很锻炼自己的Debug能力(六)自评成绩分数：90 //功能做得较齐全,程序的效率也不错(七)参考文献MSDN还有某网站上树的遍历算法(八)源程序见同一文件夹内.。