学生学号Xxx实验课成绩学生实验报告书实验课程名称数据结构与算法综合实验开课学院计算机科学与技术学院指导教师姓名xxx学生姓名xxx学生专业班级xxxx2015--2016学年第2学期1实验课程名称：数据结构与算法综合实验实验项目名称二叉树与赫夫曼图片压缩报告成绩实验者xx专业班级xxx组别同组者完成日期2016年5月2日第一部分：实验分析与设计（可加页）一、实验目的和要求1.目的=掌握树的存储结构=掌握二叉树的三种遍历方法=掌握Huffman树、Huffman编码等知识和应用=使用C++、文件操作和Huffman算法实现“图片压缩程序”专题编程。2.要求=针对一幅BMP格式的图片文件，统计256种不同字节的重复次数，以每种字节重复次数作为权值，构造一颗有256个叶子节点的哈夫曼二叉树。=利用上述哈夫曼树产生的哈夫曼编码对图片文件进行压缩。=压缩后的文件与原图片文件同名，加上后缀.huf（保留原后缀），如pic.bmp压缩后pic.bmp.huf二、分析与设计依据上述的实验目的与要求，可导出实现的二叉树与赫夫曼图片压缩软件的流程为：①读取图片文件、统计权值②生成Huffman树③生成Huffman编码④压缩图片文件⑤保存压缩的文件1.数据结构的设计记录统计256种不同字节的重复次数使用整型数组。intweight[256]={0};二叉树的存储结构。使用结构体存储节点，使用数组存储树的节点，使用静态二叉链表方式存储二叉树。Huffman编码存储结构structHTNode1{intweight;//权值intparent;intlchild;intrchild;charzifu;stringbianma;};压缩文件的算法的数据结构为正确解压文件，除了要保存原文件长度外，还要保存原文件中256种字节重复的次数，即权值。定义一个文件头，保存相关的信息：structHEAD{chartype[4];intlength;intweight[256];};压缩文件时，定义一个内存缓冲区：typedefchar*pBuffer;//其大小视原文件压缩后的大小2.核心算法设计(1)生成Huffman树和Huffman编码的算法voidSelect(HTNodehuffTree[],intm){intmin,min2,i;min=min2=1000;for(i=0;i<m;i++)if(huffTree[i].parent==-1)if(min>huffTree[i].weight){min2=min;min=huffTree[i].weight;x2=x1;x1=i;}elseif(min2>huffTree[i].weight){min2=huffTree[i].weight;x2=i;}}voidcreatHuffman(inthuff[]){2inti;ints=256;for(i=0;i<2*s-1;i++){HuffmanTree[i].parent=-1;HuffmanTree[i].lchild=-1;HuffmanTree[i].rchild=-1;}for(inti1=0;i1<s;i1++)HuffmanTree[i1].weight=huff[i1];for(intk=s;k<2*s-1;k++){Select(H...