武汉理工大学数据结构与算法综合实验哈夫曼树
- 格式：doc
- 大小：218.50 KB
- 文档页数：15
..
v
.. .
..
.
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++)
b=b<<1; if(pBinStr[i]=='1') {
b=b|0x01; } } return b; } bool InitHead(const char *pFilename,HEAD &sHead) { char ch;
..
v
.. . .. .
..
.
.. .
//初始化文件 strcpy(sHead.type,"HUF"); sHead.length=0; for(int i=0;i<256;i++) {
..
v
.. .
..
.
.. .
二叉树的存储结构。使用结构体存储节点，使用数组存储树的节点，使用静态二叉链表方 式存储二叉树。
Huffman编码存储结构 struct HTNode
{ int weight;//权值 int parent; int lchild; int rchild; char zifu; string bianma;
..
.
.. .
学生学号
Xxx
实验课成绩
学生实验报告书
实验课程名称 开课学院
指导教师姓名 学生姓名
学生专业班级
数据结构与算法综合实验 计算机科学与技术学院
xxx xxx xxxx
2015 -- 2016 学年 第 2 学期
..
v
.. .
..
.
.. .
实验课程名称： 数据结构与算法综合实验
实验项目名称
2.要求
针对一幅 BMP 格式的图片文件，统计 256 种不同字节的重复次数，以每
种字节重复次数作为权值，构造一颗有 256 个叶子节点的哈夫曼二叉树。
利用上述哈夫曼树产生的哈夫曼编码对图片文件进行压缩。 压缩后的文件与原图片文件同名，加上后缀.huf（保留原后缀），如 pic.bmp
压缩后 pic.bmp.huf
..
v
.. . .. .
..
.
.. .
} 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;
}; 压缩文件的算法的数据结构 为正确解压文件，除了要保存原文件长度外，还要保存原文件中256种字节重复的次数， 即权值。定义一个文件头，保存相关的信息：
struct HEAD {
char type[4]; int length; int weight[256]; };
压缩文件时，定义一个内存缓冲区：
..
v
.. .
..
.
.. .
} } 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)压缩编码算法
..
v
.. .
..
.
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++) {
sHead.weight[i]=0; } ifstream in; in.open(pFilename,ios::binary); while(in.get(ch)){ sHead.weight[(unsigned char)ch]++;sHead.length++;}
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; }
二、 分析与设计
依据上述的实验目的与要求，可导出实现的二叉树与赫夫曼图片压缩软件的流程为：
① 读取图片文件、统计权值 ② 生成 Huffman 树 ③ 生成 Huffman 编码
④ 压缩图片文件
⑤ 保存压缩的文件
1.数据结构的设计
记录统计256种不同字节的重复次数使用整型数组。
int weight[256] = { 0 };
二叉树与赫夫曼图片压缩
实验者
xx
专业班与设计（可加页）
一、 实验目的和要求
报告成绩 组别
完成日期
2016 年 5 月 2 日
1.目的
掌握树的存储结构 掌握二叉树的三种遍历方法 掌握 Huffman 树、Huffman 编码等知识和应用 使用 C++、文件操作和 Huffman 算法实现“图片压缩程序”专题编程。
