【数据结构与算法综合实验】二叉树与赫夫曼图片压缩实践

本文主要是介绍【数据结构与算法综合实验】二叉树与赫夫曼图片压缩实践，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

说明：这是武汉理工大学计算机学院数据结构与算法综合实验课程的第一次项目：二叉树与赫夫曼图片压缩实践代码。

>>点击查看武汉理工大学计算机专业课程资料汇总

源码+实验报告下载地址（运行环境：VS2017）：

1. 面包多平台下载：https://mianbaoduo.com/o/bread/YZWcm5tq

2. 公众号文章下载：https://mp.weixin.qq.com/s/yBc4T9B4G4Tp5ufHglzXww

3. CSDN下载：https://download.csdn.net/download/cxh_1231/10450976

笔者本科资料汇总：https://blog.csdn.net/cxh_1231/article/details/112465790

纸上得来终觉浅，绝知此事要躬行。

实验教材：

任务列表：

阶段	工作内容	交付物	参考资料
实验一	二叉树与赫夫曼图片压缩	上机实验代码	《数据结构和C++编程》第5章树和二叉树

实验内容：

1、创建工程。

2、读取源文件。

3、生成哈夫曼树。

4、生成哈夫曼编码。

5、压缩原文件。

6、保存压缩文件。

7、扩展功能。

项目截图：

实验代码：

Huffman.h 头文件代码：

#ifndef HUFFMAN_H
#define HUFFMAN_H//Huffman树节点
typedef struct 
{int weight;	//权值int parent;	//父节点int lchild;	//左孩子int rchild;	//右孩子
}HTNode, *HuffmanTree;typedef char **HuffmanCode;		//Huffman编码//生成Huffman树
int CreateHuffmanTree(HuffmanTree pHT,int weight[],int n);
int CreateHuffmanTree2(HuffmanTree &pHT, int w[], int n);//生成Huffman编码
int HuffmanCoding(HuffmanCode &pHC, HuffmanTree  &pHT);int Select(HuffmanTree pHT, int nSize);
void Select(HuffmanTree &HT, int i, int&s1, int&s2);int TestHufTree(HuffmanTree pHT);
void TestHufCode(int root, HuffmanTree &pHT, HuffmanCode &pHC);#endif

Huffman.cpp 源文件代码：

#include "Huffman.h"
#include<iostream>
#include<malloc.h>#define OK 1
#define ERROR 0using namespace std;//生成Huffman树
int CreateHuffmanTree(HuffmanTree pHT,int weight[],int n){int s1, s2,i;int m = 2 * n - 1;for (i = 1; i <= n; i++) {pHT[i].weight = weight[i - 1];pHT[i].lchild = 0;pHT[i].rchild = 0;pHT[i].parent = 0;}for (i=n+1; i <= m; i++) {pHT[i].parent = 0;pHT[i].lchild = 0;pHT[i].rchild = 0;pHT[i].weight = 0;}//	cout << "测试初始化Huffman树后的列表" << endl;
//	if (TestHufTree(pHT))
//		cout << "测试完毕！" << endl;for (i = n + 1; i <= m; i++){//从pHT[1...i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2Select(pHT, i - 1, s1, s2);pHT[s1].parent = i;pHT[s2].parent = i; //修改s1和s2结点的父指针parentpHT[i].lchild = s1;pHT[i].rchild = s2; //修改i结点的左右孩子指针pHT[i].weight = pHT[s1].weight + pHT[s2].weight; //修改权值
//		cout << "257以及以后 修改权值后的值：" << i << "\t" << pHT[i].weight << endl;}//	cout << "测试生成Huffman树后的列表" << endl;
//	if (TestHufTree(pHT))
//		cout << "测试完毕！" << endl;return OK;
}int CreateHuffmanTree2(HuffmanTree &pHT, int w[], int n)
{//w存放n个结点的权值，将构造一棵哈夫曼树pHTint i, m;int s1, s2;//	HuffmanTree p;if (n <= 1) return ERROR;m = 2 * n - 1; //n个叶子结点的哈夫曼树，有2*n-1个结点pHT = (HuffmanTree)malloc((m +1 ) * sizeof(HTNode)); //开辟2*n各结点空间,0号单元未用for ( i = 1; i <= n; ++i) //进行初始化{pHT[i].weight = w[i];pHT[i].parent = 0;pHT[i].lchild = 0;pHT[i].rchild = 0;}for (; i <= m; ++i){pHT[i].weight = 0;pHT[i].parent = 0;pHT[i].lchild = 0;pHT[i].rchild = 0;}for (i = n + 1; i <= m; ++i) //建哈夫曼树{//从pHT[1...i-1]中选择parent为0且weight最小的两个结点，其序号分别为s1和s2Select(pHT, i - 1, s1, s2);pHT[s1].parent = i;pHT[s2].parent = i; //修改s1和s2结点的父指针parentpHT[i].lchild = s1;pHT[i].rchild = s2; //修改i结点的左右孩子指针pHT[i].weight = pHT[s1].weight + pHT[s2].weight; //修改权值}return OK;
}//查找Huffman树节点数组中权值最小的节点
int Select(HuffmanTree pHT, int nSize) {int minValue = 0x7FFFFFFF;	//最小值int min = 0;				//元素序号//找到最小权值的元素序号for (int i = 1; i <= nSize; i++){if (pHT[i].parent == 0 && pHT[i].weight<minValue){minValue = pHT[i].weight;min = i;}}return min;
}void Select(HuffmanTree &pHT, int i, int &s1, int &s2) {int minValue = 0x7FFFFFFF;//找到最小的一个权值for (int j = 1; j <= i; j++) {if (pHT[j].parent == 0 && pHT[j].weight<minValue) {minValue = pHT[j].weight;s1 = j;}}
//	cout << "最小权值：" << s1;minValue = 0x7FFFFFFF;//找到倒数第二小的权值for (int j = 1; j <= i; j++) {if (j != s1 && pHT[j].parent == 0 && pHT[j].weight < minValue) {minValue = pHT[j].weight;s2 = j;}}
//	cout << "\t次之权值：" << s2 << endl;
}//生成Huffman编码 
int HuffmanCoding(HuffmanCode &pHC, HuffmanTree &pHT)
{//无栈非递归遍历Huffman树，求Huffman编码char cd[256] = { '\0' };	//记录访问路径int cdlen = 0;				//记录当前路径长度for (int i = 1; i < 512; i++) {pHT[i].weight = 0;	//遍历Huffman树时用做节点的状态标志}int p = 511;			//根节点while (p != 0) {//向左if (pHT[p].weight == 0) {pHT[p].weight = 1;if (pHT[p].lchild != 0) {p = pHT[p].lchild;cd[cdlen++] = '0';}//登记叶子节点的字符的编码else if(pHT[p].rchild==0){pHC[p] = (char*)malloc((cdlen + 1) * sizeof(char));cd[cdlen] = '\0';strcpy(pHC[p], cd);//复制编码}}//向右else if (pHT[p].weight == 1) {pHT[p].weight = 2;//右孩子为叶子节点if (pHT[p].rchild != 0) {p = pHT[p].rchild;cd[cdlen++] = '1';}}//退回父节点，编码长度减一else {pHT[p].weight = 0;p = pHT[p].parent;cdlen--;}}return OK;
}int TestHufTree(HuffmanTree pHT) {cout << "Byte\t\tWeight\tParent\tLchild\tRchild\n";for (int i = 1; i < 512; i++) {if (i <= 99) {cout << "pHT[" << i << "]\t\t" << pHT[i].weight << "\t" << pHT[i].parent << "\t" << pHT[i].lchild << "\t" << pHT[i].rchild << endl;}else {cout << "pHT[" << i << "]\t" << pHT[i].weight << "\t" << pHT[i].parent << "\t" << pHT[i].lchild << "\t" << pHT[i].rchild << endl;}}return OK;
}void TestHufCode(int root, HuffmanTree &pHT, HuffmanCode &pHC) {if (root <= 1) return;if (pHT[root].lchild == 0 && pHT[root].rchild == 0){printf("0x%02X %s\n", root - 1, pHC[root - 1]);}if (pHT[root].lchild)//访问左孩子{TestHufCode(pHT[root].lchild, pHT, pHC);}if (pHT[root].rchild)//访问右孩子{TestHufCode(pHT[root].rchild, pHT, pHC);}}

Compress.h 头文件代码：

#ifndef COMPRESS_H
#define COMPRESS_H
//typedef char **HuffmanCode;//文件头
struct HEAD
{char type[4];int length;int weight[256];
};//实现文件压缩
int Compress(const char *pFilename);//读取源文件和初始化头文件的信息
int InitHead(const char * pFilname, HEAD & sHead);//利用Huffman编码 实现压缩编码
int Encode(const char *, char**, char *, const int);
//int Encode(const char *pFilname, const HuffmanCode pHC, char *pBuffer, const int nSize);//将二进制字符串转换成字节
char Str2byte(const char * pBinStr);//生成压缩文件
int WriteFile(const char * pFilename, const HEAD sHead, const char * pBuffer, const int nSize);//测试相关
int TestWeight(int weight[]);#endif

Compress.cpp 源文件代码：

#include <iostream>
#include <stdlib.h>
#include "Compress.h"
#include"Huffman.h"using namespace std;#define OK 1
#define ERROR 0const int SIZE = 256;//扫描文件和初始化头文件的信息
int InitHead(const char * pFilname, HEAD & sHead)
{strcpy(sHead.type, "HUF");		//文件类型sHead.length = 0;				//源文件长度for (int i = 0; i < SIZE; i++){sHead.weight[i] = 0;		//权值}//以二进制流形式打开文件FILE *in = fopen(pFilname, "rb");//扫描文件，获得权重int ch;while ((ch = fgetc(in)) != EOF){sHead.weight[ch]++;sHead.length++;}//关闭文件fclose(in);in = NULL;return OK;
}//得到编码文件
int Compress(const char * pFilename)
{/**************************************************///打开并扫描文件cout << "正在读取文件……" << endl;int weight[256] = { 0 };  //打开文件，获取权重FILE* in = fopen(pFilename, "rb");int tempch;while ((tempch = getc(in)) != EOF){weight[tempch]++;}//测试扫描结果：显示256种字节出现的次数//if (TestWeight(weight))//	cout << "测试完毕！！！" << endl << endl;cout << "文件读取完毕！\n" << endl<<endl;fclose(in);/**************************************************///将编码生成Huffman树int i;int n = 256;						//Huffman树共有n个叶子节点int m = 2 * n - 1;					//那么就有2n+1个节点HuffmanTree pHT = new HTNode[m + 1];	//定义Huffman树CreateHuffmanTree(pHT,weight,n);//	cout << "测试生成的Huffman树" << endl;
//	if (TestHufTree(pHT))
//		cout << "测试完毕！" << endl;//生成Huffman编码char** pHC = new char*[n + 1]; //编码for (int i = 1; i <= n; i++)pHT[i].weight = weight[i - 1];//	cout << "测试生成的Huffman树" << endl;//测试生成的Huffman树//cout << "生成Huffman树测试过程：\n";//if (TestHufTree(pHT))//	cout << "测试完毕！" << endl;HuffmanCoding(pHC, pHT);//cout << "测试：显示字节的Huffman编码" << endl;//cout << "Byte\tHuffmanCode" << endl;//TestHufCode(511, pHT, pHC);/**************************************************///计算编码缓冲区大小int nSize = 0;for (int i = 0; i < 256; i++)nSize += weight[i] * strlen(pHC[i + 1]);nSize = (nSize % 8) ? nSize / 8 + 1 : nSize / 8;//对编码文件进行压缩char *pBuffer = NULL;pBuffer = new char[nSize];memset(pBuffer, 0, (nSize) * sizeof(char));Encode(pFilename, pHC, pBuffer, nSize);if (!pBuffer) {return ERROR;}HEAD sHead;InitHead(pFilename, sHead);cout << "目标文件大小：" << sHead.length << "字节" << endl;int afterlen = WriteFile(pFilename, sHead, pBuffer, nSize);cout << "压缩文件大小：" << afterlen << "字节  \n其中头文件sHead大小：" << sizeof(sHead) << "字节" << endl;cout << "压缩比率：" << (double)afterlen * 100 / sHead.length << "%" << endl;delete pHT; delete[] pHC; delete pBuffer;return OK;
}//实现·压缩编码
int Encode(const char * pFilname, const HuffmanCode pHC, char * pBuffer, const int nSize)
{//打开文件FILE *in = fopen(pFilname, "rb");//开辟缓冲区nipBuffer = (char *)malloc(nSize * sizeof(char));if (!pBuffer){cout << "开辟缓冲区失败" << endl;}char cd[SIZE] = { 0 };		//工作区int pos = 0;				//缓冲区指针int ch;//扫描文件while ((ch = fgetc(in)) != EOF){strcat(cd, pHC[ch + 1]);//压缩编码while (strlen(cd) >= 8){pBuffer[pos++] = Str2byte(cd);for (int i = 0; i<SIZE - 8; i++){cd[i] = cd[i + 8];}}}if (strlen(cd) > 0){pBuffer[pos++] = Str2byte(cd);}fclose(in);		//关闭文件return OK;
}//生成压缩文件
int WriteFile(const char * pFilename, const HEAD sHead, const char * pBuffer, const int nSize)
{//生成文件名char filename[256] = { 0 };strcpy(filename, pFilename);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;
}//将字符串转换成字节
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;
}int TestWeight(int weight[]) {cout << "显示256种字节出现的次数：" << endl;cout << "Byte\t" << "Weight\t" << endl;for (int i = 0; i < 256; i++) {printf("0x%02X\t%d\n",i, weight[i]);//cout << i << "\t" << weight[i] << endl;}return OK;
}

Main.cpp 主函数代码：

// Main.cpp: 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
#include "Compress.h"
#include"Huffman.h"
using namespace std;int main()
{cout << "=========Huffman文件压缩=======" << endl;cout << "请输入文件名：";char filename[256];cin >> filename;if (Compress(filename) == 1) {cout << "\n压缩完成！" << endl;}else {cout << "\n压缩失败" << endl;}return 0;
}