综合实验实验报告书示例.pdf

《综合实验实验报告书示例.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、学生学号实验课成绩学生实验报告书实验课程名称数据结构与算法综合实验开课学院计算机科学与技术学院指导教师姓名伍新华学生姓名学生专业班级2015--2016学年第2学期1实验课程名称：数据结构与算法综合实验实验项目名称二叉树与赫夫曼图片压缩报告成绩实验者专业班级组别同组者完成日期年月日第一部分：实验分析与设计（可加页）一、实验目的和要求1.目的ò掌握树的存储结构ò掌握二叉树的三种遍历方法ò掌握Huffman树、Huffman编码等知识和应用ò使用C++、文件操作和Huffman算法实现“图片压缩程序”专题编程。2.要求ò针对一幅BMP格式的图片文件，统

2、计256种不同字节的重复次数，以每种字节重复次数作为权值，构造一颗有256个叶子节点的哈夫曼二叉树。ò利用上述哈夫曼树产生的哈夫曼编码对图片文件进行压缩。ò压缩后的文件与原图片文件同名，加上后缀.huf（保留原后缀），如pic.bmp压缩后pic.bmp.huf二、分析与设计依据上述的实验目的与要求，可导出实现的二叉树与赫夫曼图片压缩软件的流程为：①读取图片文件、统计权值②生成Huffman树③生成Huffman编码④压缩图片文件⑤保存压缩的图片文件1.数据结构的设计ò记录统计256种不同字节的重复次数使用整型数组。Unsignedintweigh

3、t[256];ò二叉树的存储结构。使用结构体存储节点，使用数组存储树的节点，使用静态二叉链表方式存储二叉树。StructHTNode{Unsignedintweight;Intparent;Intlchild;Intrchild;};TypedefHTNode*HuffmanTree;1òHuffman编码存储结构定义一二维数组：charHufCode[256][];因考虑每个字节的Huffman编码长度不一样，可使用字符串指针数组：Char*HuffmanCode[256];ò压缩文件的算法的数据结构为正确解压文件，除了要保存原文件长度外，还要保

4、存原文件中256种字节重复的次数，即权值。定义一个文件头，保存相关的信息：StructfHEAD{Chartype[4];//文件类型Unsignedintlength;//原文件的长度Unsignedcharweight[256];//权值}压缩文件时，定义一个内存缓冲区：Unsignedchar*pBuffer;//其大小视原文件压缩后的大小2.核心算法设计1）生成Huffman树算法Input:Unsignedintweight[256];//权值Output:HuffmanTreepHT[512];//哈夫曼树，静态二叉链表Introot；

5、//树的根节点指针Process:intCreateHuffmanTree(HuffmanTree&pHT[],Unsignedintweight[]){pHT=(HuffmanTree)malloc((512)*sizeof(HTNode));for(p=pHT+1,i=1;i<256;++i,++p)*p={weight[i-1],0,0,0};for(;i<=511;++i,++p)*p={0,0,0,0};for(i=256;i<=511;++i){//构造n-1个分支结点Select(pHT,i-1,s1,s2);//pHT[1..i-1

6、]中parent为0的w最小的2个结点HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}Return511;}2）生成Huffman编码算法Input:HuffmanTreepHT[512];n;//n为叶子节点数Output:Char*HuffmanCode[256];Process:intHuffmanCoding(HuffmanCode&pHC,HuffmanTree&pHT，int

7、n){pHC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]=“”;2for(i=1;i<=n;++i){//为n个叶子结点编码start=n–1;for(c=i,f=pHT[i].parent;f!=0;c=f,f=pHT[f].parent)if(pHT[f].lchild==c)cd[--start]=“0”;elsecd[--start]=“1”;//判断c是f的左还是右孩子pHC[i]=(char*)malloc((n-

8、start)*sizeof(char));Strcpy(pHC[i],&cd[start]);}free(cd);}3）压