资源描述:
《数据结构课程设计报告压缩与解压缩系统》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、南京师范大学泰州学院数据结构课程设计报告压缩与解压缩系统K*#232・4********一、问题描述-二、算法思想2.2^y>■弘■弘rjwrj*rjwrj*ejwejwejwejw三、算法实现63.1数据结构3.2程序模块3.3各模块之间的调用关系五、总结六、参考文献问题描述设计目标是要实现哈夫曼压缩的编码器和译码器。编码器工作如下:首先读入待压缩文件,然后对每种字符出现的频度进行统计,以频率作为建立哈夫曼树的权值。接着建立哈夫曼树,对出现的每种字符进行哈夫曼编码。此时再读入原文件,逐个字节进行编码,将得到的编码流逐个写入文件。译码过
2、程相对简单:读入被压缩文件,根据哈夫曼树对文件中的字符逐个译码,将译码结果逐个写入文件。二、算法思想1哈夫曼树是哈夫曼算法的理论描述工具,也称最优二叉树,是一种加权路径长度最短的二叉树。加权路径长度是指树中所有叶子结点的权值乘上其到根结点的路径长度。N个叶子结点的哈夫曼树共有2n-1个结点,这个性质将运用于使用数组结构存储哈夫曼树,从根结点开始,左子结点分配0,右子结点分配X沿着树根到各个结点就得到了哈夫曼编码,因为所有被编码的字符都作为叶子结点出现而每个叶子结点路径又是独立的,保障了每个编码都不会四其余码的前缀.这样的编码又称“哈夫曼无重复前缀编码S着
3、在下面的程序段会应用到。2哈夫曼树也应用于译码过程,译码过程中逐一扫描码文,从哈夫曼的根结点开始,将扫描得到的二进制位串中的相邻位与哈夫曼树上的0,1匹配。三、算法实现3.1数据结构typedefstruct{charch;irrtweight;}charweight;定义结构模块charweightCh(字符)Weight〈权值〉typedefstructhftnode{intweight;intparent,IchildyrchiId;}HFMNode;建立哈夫曼二叉树HFMNodeweightparentIchiIdrchiIdtypedefstr
4、ucthe{charch;intstart;charlink[100];}HFMCode;哈夫曼编码HFMCodechstart3.2程序模块1・从文件中读出字符和出现的频率数(权值)irrtreadfiIe(charsrc[],charweight*fIist);2.根据字符和权值创建哈夫曼树voidCreate_HFM(intn,charweight*fIist,HFMNode*hfmtree):2.找出权值最小的两个voidseIect(intn,int*n1,int*n2,HFMNode*hfmtree);3.定义一个编码表voidinit_hf
5、mcode(intn,charweight*flist,HFMCode♦hfmcode);4.通过二叉树构建编码表内部值voidCreate_hfmcode(intn,HFMNode*hfmtree,HFMCode*hfmcode);5.在文件中输出字符和权值WriteHead(char*,charweight*,int);ad6.根据哈夫曼树和带有字符和权值的文件输出编码voidTranslate(char*srcfile,char*desfile,intn,HFMCode*hfmcode);3.3各模块之间的调用关系Main->(调用)readfiI
6、e和create_hfm->seIect和writehead和transIate->init_hfmcode!1!四、测试与分析要求分析设计目标是要实现哈夫曼压缩的编码器和译码器。码器工作如下:首先读入待压缩文件为了保证与原文件信息完全一致,对文件的读写都采用二进制的方式进行。然后建立并分析字母表,最多只有256种可能的符,对每种字符出现的频度进行统计,以频度作为建立哈夫曼树的权值。频度表建立好以后,可以建立哈夫曼树,对出现的每种字符进行哈夫曼编码。此时再读入原文件,逐个字节进行编码,将得到的编码流逐个写入文件。译码过程相对简单:读入被压缩文件,将其解释
7、为比特流,根据哈夫曼树对比特流逐个译码,将译码结果逐个写到磁盘文件。数据压缩有2种基本类型:无损压缩和有损压缩,使用无损压缩方法压缩的文件不会丢失任何信息,他与原文件具有可逆性,就是可以通过解压缩的方法恢复原来的数据,通常对文本文件,字处理文件,应用程序等采用这种算法。有损压缩算法在压缩时回丢失一些信息,压缩后不能完整恢复出原有信息,较多应用于音频,视频图象数据的处理。1・原程序文件(£)編辑@)格式(Q)查看①)帮助@)OnenighthoweuerouruicarwokeupwithastarttheclockwasstrikingthehoursL
8、ookingathiswatchhesawthatitwasoneoclockb