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

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

#include 
#include 
#include “Compress.h“
#include“Huffman.h“

using namespace std;

#define OK 1
#define ERROR 0

const 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<	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（pHTweightn）;

//	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树
//	if （TestHufTree（pHT））
//		cout << “测试完毕！“ << endl;


	HuffmanCoding（pHC pHT）;

	/**************************************************/


	//计算编码缓冲区大小
	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“）;

	//开辟缓冲区ni
	pBuffer = （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


 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-05-08 20:41  HfmCompressCPro\
     目录           0  2018-05-08 20:41  HfmCompressCPro\.vs\
     目录           0  2018-05-08 20:41  HfmCompressCPro\.vs\HfmCompressCPro\
     目录           0  2018-05-08 20:44  HfmCompressCPro\.vs\HfmCompressCPro\v15\
     文件       54784  2018-05-08 20:44  HfmCompressCPro\.vs\HfmCompressCPro\v15\.suo
     文件     5242880  2018-05-08 20:44  HfmCompressCPro\.vs\HfmCompressCPro\v15\Browse.VC.db
     目录           0  2018-05-08 20:41  HfmCompressCPro\.vs\HfmCompressCPro\v15\ipch\
     文件    25755648  2018-05-02 18:10  HfmCompressCPro\.vs\HfmCompressCPro\v15\ipch\54987a9fdebad512.ipch
     目录           0  2018-05-08 20:42  HfmCompressCPro\.vs\HfmCompressCPro\v15\ipch\AutoPCH\
     目录           0  2018-05-08 20:41  HfmCompressCPro\.vs\HfmCompressCPro\v15\ipch\AutoPCH\134c91a43b40e1b5\
     文件    26148864  2018-05-08 20:39  HfmCompressCPro\.vs\HfmCompressCPro\v15\ipch\AutoPCH\134c91a43b40e1b5\COMPRESS.ipch
     目录           0  2018-05-08 20:41  HfmCompressCPro\.vs\HfmCompressCPro\v15\ipch\AutoPCH\53b7047aad3a8af8\
     文件    26476544  2018-05-08 20:39  HfmCompressCPro\.vs\HfmCompressCPro\v15\ipch\AutoPCH\53b7047aad3a8af8\MAIN.ipch
     目录           0  2018-05-08 20:42  HfmCompressCPro\.vs\HfmCompressCPro\v15\ipch\AutoPCH\84b2b339d31b66c8\
     文件    26476544  2018-05-08 20:43  HfmCompressCPro\.vs\HfmCompressCPro\v15\ipch\AutoPCH\84b2b339d31b66c8\MAIN.ipch
     目录           0  2018-05-08 20:41  HfmCompressCPro\.vs\HfmCompressCPro\v15\ipch\AutoPCH\fd150ae0430a3a5c\
     文件    26148864  2018-05-08 20:30  HfmCompressCPro\.vs\HfmCompressCPro\v15\ipch\AutoPCH\fd150ae0430a3a5c\HUFFMAN.ipch
     文件    26345472  2018-05-07 18:09  HfmCompressCPro\.vs\HfmCompressCPro\v15\ipch\dcdbf1051398cea6.ipch
     目录           0  2018-05-08 20:42  HfmCompressCPro\Debug\
     文件       75776  2018-05-08 20:42  HfmCompressCPro\Debug\HfmCompressCPro.exe
     文件      492148  2018-05-08 20:42  HfmCompressCPro\Debug\HfmCompressCPro.ilk
     文件      610304  2018-05-08 20:42  HfmCompressCPro\Debug\HfmCompressCPro.pdb
     目录           0  2018-05-08 20:41  HfmCompressCPro\HfmCompressCPro\
     文件        4456  2018-05-08 20:36  HfmCompressCPro\HfmCompressCPro\Compress.cpp
     文件         716  2018-05-08 17:11  HfmCompressCPro\HfmCompressCPro\Compress.h
     目录           0  2018-05-08 20:42  HfmCompressCPro\HfmCompressCPro\Debug\
     文件       61612  2018-05-08 20:42  HfmCompressCPro\HfmCompressCPro\Debug\Compress.obj
     文件         455  2018-05-08 20:42  HfmCompressCPro\HfmCompressCPro\Debug\HfmCompressCPro.log
     目录           0  2018-05-08 20:42  HfmCompressCPro\HfmCompressCPro\Debug\HfmCompressCPro.tlog\
     文件        2766  2018-05-08 20:42  HfmCompressCPro\HfmCompressCPro\Debug\HfmCompressCPro.tlog\CL.command.1.tlog
     文件       54354  2018-05-08 20:42  HfmCompressCPro\HfmCompressCPro\Debug\HfmCompressCPro.tlog\CL.read.1.tlog
............此处省略19个文件信息