哈夫曼编码与解码实验报告.doc

哈夫曼编码与解码实验报告.doc:..粢孝理二夬專EASTCHINAINSTITUTEOFTECHNOLOGY数据结构课程设计报告题目:哈夫曼编码与解码学生姓名:学号:班级:指导教师:侯清源1021111118张军2012年6月1日目录需求分析说明总体设计详细设计实现部分程序测试部分实验总结附图:,利用变长编码的方式,可以有效充分利用带宽,实现信息传送前的压缩。,利用哈夫曼编码的方式,压缩文件。可以实现硬盘存储最大的信息量。:1,・学会使用哈夫曼进行对文本文件的编码与译码。2,通过对哈夫曼的编码与译码,能够理解通信领域中的数据传输的压缩原理。3,通过对哈夫曼的编码/译码器的研究与分析,能够彻底的理解软件设计的一般步骤和方法,灵活地运用各种数据结构进行操作,熟练地把所学地数据结构应用地软件开发当中,提高软件设计水平,增强程序设计能力。:实现对用户输入的字符串压缩,并在终端显示相应字符对应的频率,编码,编码长度,平均编码长度,字符个数。并显示字符串编码后的二进制文件。解压:实现对压缩后的二进制文件解压,还原为原来的字符串。并显示在终端。和用户输入的字符串比较。2,总体设计2,1开发环境介绍编译器:::ctagSstaglist>plpopo扌TJFsyntaxenable>syntaxon>setnumbero操作系统::Processor:Intel(R)Core™i5-******@:AcerTravelMate4750GBusinessLaptopMemory:(文字和图)1,首先,根据用户输入的字符串得到字符频率。根据频率得到频率数据,对该频率数组由栈顶到栈低由小到大排列,同时将从小到大顺序存入优先U列2,构造哈弗曼树,过程如下:从栈中取出两个最小频率。按照左小右大的原则。构造哈弗曼树。同时生成父节点,即频率和。同时父节点入栈,重新按照由小到大的顺序排列。3,重复2过程,直到栈为空。4,编码解码的过程编码时,根据哈弗曼树,左0右1,建立map<char,vector<bool>>容器,右边存储字符,右边存储编码。编码时,从根节点递归遍历算法编码,左节点编码时添加0,右节点编码添加1解码时,也是根据哈弗曼编码树,从根节点开始,如果碰到编码的首部是1,往右遍历;如果是0,往左遍历。直到叶子节点,遍历匹配字符成功,返回匹配的字符。同时回到根节点,重复该步骤,翻译下一个编码。3,,类模板设计1,类模板设计资料:高永平老师给的资料:《数据结构(STL框架)》王晓东编著,陈道蓄主审2,主要是STL编程,并利用了vectormapqueue等容器,使用了容器的迭代器iterator哈夫曼树类结构模板Hafflrec类模板原型Template<typenameDataType^typenameFrequency>Hufftree+template<typenameInputlterator>Hufftree(Inputlteratorbeginjnputlteratorend);构造哈夫曼树+~Hufftree()析构函数+template<typenameInputlterator>vector<bool>encode(lnputlteratorbeginjnputlteratorend);编码+vector<bool>encode(DataTypeconst&value);返冋字符编码+doubleencodelength(DataTypeconst&value);返回字符编码长度+template<typenameOutputlterator>voiddecode(vector<bool>const&v,Outputiteratoriler);对字符串解码-classNode;字符串节点类-classNodeOrder;排序时用的类-Node*tree;根节点-typedefmap<DataType,vector<bool>>encodemap;encodemapencodetable;编码表Node类成员:template<typenameDataType,typenameFrequency>Node+Frequencyfreqeuency;权或频率+Node*leftChi!d;左孩子指针+unionNode*rightChild;右孩子指针DataType*daia;字符域指针Template<ty