哈弗曼实验报告.doc

华北科技学院计算机系综合性实验实验报告课程名称数据结构实验学期2009至2010学年第二学期学生所在系部计算机系年级2008级专业班级信管B081学生姓名XX学号任课教师实验成绩计算机系制《数据结构》课程综合性实验报告开课实验室:基础一2010年6月22日实验题目用哈弗曼编码实现文件压缩一、实验目的了解文件的概念。掌握线性链表的插入、删除等算法。3、掌握Huffman树的概念及构造方法。4、掌握二叉树的存储结构及遍历算法。5、利用Huffman树及Huffman编码,掌握实现文件压缩的一般原理二、设备与环境微型计算机、Windows系列操作系统、VisualC++、实验内容根据ascii码文件中各ascii字符出现的频率情况创建Haffman树,再将各字符对应的哈夫曼编码写入文件中,实现文件压缩。四、,得出统计出的字符的权值n编码解码退出根据权值进行建立哈夫曼树输出哈夫曼树输出编码压缩编码生成二进制文件解压生成新的文本文档2、主要函数功能FileRead(intcount[],chars[],charfilename[])压缩文档存在。对该文档进行读取,求其所有出现的字符和字符的权值。CreateHuffmanTree(HTreeT,intN,intcount[],chars[])以求得该文档的字符和权值。建立Huffman树。HuffmanCoding(HTreeT,HCodeH,intN,chars[])求各个字符的Huffman编码。FilePrint(HTreeT,HCodeH,intN)求得Huffman编码以及各节点的权值。、、。FileWrite(HCodeH,intN,charfilename[])求得Huffman编码以及各节点的权值。。FileConvert(void)。将字符形式的Huffman编码翻译成二进制形式,,。FileRead(HTreeT,HCodeH)、、。读取字符及其权值和其Huffman编码。FileExtract(void)。,。FileTrans(HTreeT,HCodeH,intN)已生成File00,txt并已求得各个字符的Huffman编码,Huffman树已建立。:将Huffman编码翻译成原文件,。还需要包含调用若干库文件:,,。实验步骤进入主界面输出编码运行完毕处理结果如下:该文本文件保存的是测试文件中出现的字符以及相应的权值字母对应的权值,,将权值相加放在根节点中,将原节点删除,新节点放入数组。递归进行上述操作直到数组中只有一个节点为止。算法如下:2、建立哈夫曼树构造哈夫曼数时,首先将n个权值的叶子结点存放到数组huffTree[2*num]的前n个分量中,然后不断的将两棵子树合并为一棵子树,并将新子树的根结点顺序存放到数组huffTree[2*num]的前n个分量的后面。t[n]中,哈夫曼树的存储主要是利用数组存储伪代码描述为:,所有元素结点的双亲、左右孩子都置为0;[n];-、在二叉树集合中选取两个权值最小的根结点,其下标分别为i1和i2;、将二叉树i1和i2合并为一棵新的二叉树对每个叶子结点进行编码:,将孩子结点的双亲结点付给一个变量,双亲结点不为空时,深度加1,继续向上查找,这时该双亲结点已变成孩子结点,循环知道双亲结点为空,求出每一个叶子结点的深度。+1,将孩子结点的双亲结点付给一个变量,双亲结点不为空时,初始结点-1,如果此孩子为双亲的左孩子,则置为0,否则置为1,循环知道双亲结点为空。编码完毕压缩部分:主要思想为:对字符窜编码的解码是将编码窜从左