学生学号Xxx实验课成绩学生实验报告书实验课程名称数据结构与算法综合实验开课学院计算机科学与技术学院指导教师姓名xxx学生姓名xxx学生专业班级xxxx2015--2016学年第2学期实验课程名称：数据结构与算法综合实验实验项目名称二叉树与赫夫曼图片压缩报告成绩实验者xx专业班级xxx组别同组者完成日期2016年5月 2日第一部分：实验分析与设计（可加页）一、实验目的和要求1.目的掌握树的存储结构掌握二叉树的三种遍历方法掌握 Huffman树、Huffman编码等知识和应用使用 C++、文件操作和 Huffman算法实现“图片压缩程序”专题编程。
2.要求针对一幅 BMP 格式的图片文件，统计 256 种不同字节的重复次数，以每种字节重复次数作为权值，构造一颗有 256 个叶子节点的哈夫曼二叉树。
利用上述哈夫曼树产生的哈夫曼编码对图片文件进行压缩。
压缩后的文件与原图片文件同名，加上后缀.huf （保留原后缀），如 pic.bmp 压缩后 pic.bmp.huf二、分析与设计依据上述的实验目的与要求，可导出实现的二叉树与赫夫曼图片压缩软件的流程为：① 读取图片文件、统计权值②生成 Huffman树③生成 Huffman编码④ 压缩图片文件⑤ 保存压缩的文件1.数据结构的设计记录统计 256种不同字节的重复次数使用整型数组。
int weight[256] = { 0 };二叉树的存储结构。
使用结构体存储节点，使用数组存储树的节点，使用静态二叉链表方式存储二叉树。
Huffman编码存储结构struct HTNode{int weight;//权值1int lchild;int rchild;char zifu;string bianma;};压缩文件的算法的数据结构为正确解压文件，除了要保存原文件长度外，还要保存原文件中 256种字节重复的次数，即权值。
定义一个文件头，保存相关的信息：struct HEAD{char type[4];int length;int weight[256];};压缩文件时，定义一个内存缓冲区：typedef char *pBuffer;//其大小视原文件压缩后的大小2.核心算法设计(1) 生成 Huffman 树和 Huffman 编码的算法void Select(HTNode huffTree[],int m){int min,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;}else if(min2>huffTree[i].weight ){min2=huffTree[i].weight ;x2=i;}}void creatHuffman(int huff[]){int i;int s=256;for(i=0;i<2*s-1;i++){HuffmanTree[i].parent =-1;HuffmanTree[i].lchild =-1;HuffmanTree[i].rchild =-1;}for(int i1=0;i1<s;i1++)HuffmanTree[i1].weight=huff[i1];for(int k=s;k<2*s-1;k++){Select(HuffmanTree,k);HuffmanTree[x1].parent =k;HuffmanTree[x2].parent =k;HuffmanTree[k].weight =HuffmanTree[x1].weight +HuffmanTree[x2].weight ;HuffmanTree[k].lchild =x1;HuffmanTree[k].rchild =x2;}}void HuffmanCoding(HTNode huffTree[],int n){int i,j=0;for(i=2*(n-1);i>n-1;i--){huffTree[huffTree[i].lchild ].bianma ="0";huffTree[huffTree[i].rchild ].bianma ="1";}for(i=0,j=0;j<n;j++){while(huffTree[i].parent !=-1){huffTree[j].bianma =huffTree[huffTree[i].parent].bianma+huffTree[j].bianma ;i=huffTree[i].parent ;}i=j+1;}}(2)压缩编码算法struct HEAD{char type[4];int length;int weight[256];};char Str2byte(const char * pBinStr){char b=0x00;for(int i=0;i<8;i++){b=b<<1;if(pBinStr[i]=='1'){b=b|0x01;}}return b;}bool InitHead(const char *pFilename,HEAD &sHead){char ch;//初始化文件strcpy(sHead.type,"HUF");sHead.length=0;for(int i=0;i<256;i++){sHead.weight[i]=0;}ifstream in;in.open(pFilename,ios::binary);while(in.get(ch)){ sHead.weight[(unsigned char)ch]++;sHead.length++;} cout<<sHead.length<<" 字节 "<<endl;return true;}int Encode(const char *pFilename,char * &pBuffer,const int nSize){pBuffer=(char *)malloc(nSize * sizeof(char)+10);if(!pBuffer){cout<<" 开辟缓冲区失败 "<<endl;}char cd[256]={0};int pos=0;int ch;FILE *in=fopen(pFilename,"rb");while((ch=fgetc(in))!=EOF){strcat(cd,HuffmanTree[ch].bianma.c_str());while(strlen(cd)>=8){//cout<<cd<<" "<<Str2byte(cd)<<" ";pBuffer[pos++]=Str2byte(cd);//cout<<pBuffer[pos-1]<<endl;for(int i=0;i<256-8;i++){cd[i]=cd[i+8];}}}if(strlen(cd)>0){pBuffer[pos++]=Str2byte(cd);}return 1;}int WriteFile(const char * pFilename ,const HEAD sHead, char * pBuffer,const int nSize) {//生成文件名char filename[256]={0};strcpy(filename,pFilename);int i;for( i=strlen(filename);filename[i]!='.';i--);filename[i]='\0';strcat(filename,".huf");//以二进制流的形式打开文件FILE *out =fopen(filename ,"wb");//写文件头fwrite( & sHead,sizeof(HEAD),1,out);//写压缩后的编码fwrite(pBuffer,sizeof(char),nSize,out);//关闭文件释放文件指针fclose(out);out=NULL;cout<<" 生成压缩文件 "<<filename<<endl;int len=sizeof(HEAD)+strlen(pFilename)+1+nSize;return len;}int compress(const char *pFilename,int weight[256],const HEAD sHead){//计算缓冲区的大小int nSize=0; for(inti=0;i<256;i++){nSize+=weight[i]*HuffmanTree[i].bianma.length();}nSize=(nSize%8)?nSize/8+1:nSize/8;//cout<<"nSize"<<nSize<<endl;char *pBuffer=NULL;Encode(pFilename,pBuffer,nSize);//if(pBuffer==NULL)// cout<<" wrong"<<endl;if(!pBuffer){return 0;}int result=WriteFile(pFilename,sHead,pBuffer,nSize);return result;}3.测试用例设计使用一个文本文件作为压缩的例，观察其压缩比；通过屏幕截图形成一个 BMP图片文件，观察其压缩比；在互联网上搜索下载任意格式的图片文件，观察其压缩比。
三、主要仪器设备及耗材1. 安装了 Windows 10 或其它版本的 Windows操作系统的 PC机 1 台2.PC 机系统上安装了Microsoft Visual Studio 2010开发环境第二部分：实验过程和结果（可加页）一、实现说明在 Microsoft Visual Studio 2010集成开发环境中新建一个Win32 控制台应用程序工程HfmCompressConsole。