基于C++控制台的哈夫曼编码译码器

#

###

前言：

有个朋友最近让我帮他做一份大二课设，题目是哈夫曼编码译码器

开干

一.基本实现对数字操作♥

1.头文件的引入

先把应该会用到的头文件老老实实贴上

#include "pch.h" 
#include <iostream>
#include <iomanip> 
#include <conio.h> 
#include <windows.h>
#define ERROR -1 
#define OK 1 
typedef int STATUS;
using namespace std;

 

2.哈夫曼树的结构体定义

定义哈夫曼树的结构体

typedef struct { 
     int weight;                                     //结点的权值 
     int parent, lchird, rchird;                     //结点的双亲，左孩子，右孩子的下标 
}HTNode,*HuffmanTree;            //HTNode：结点类型。HuffmanTree：哈夫曼数的指针

 

3.构造哈夫曼树

STATUS CreateHuffmanTree(HuffmanTree &HT, int n)    //构造哈夫曼树
{
	if (n <= 1)      //结点数量不合法        
	{
		return ERROR;
	}
        int m = n * 2 - 1;          //为了方便，数组下标从1开始与结点对应
	HT = new HTNode[m + 1];     
	for (int i = 1; i <= m; ++i)    //做初始化，HT中每个单元的双亲，左右孩子的下标都初始化为0
	{
		HT[i].parent = 0;
		HT[i].lchird = 0;
		HT[i].rchird = 0;
	}
	for (int i=1;i<=n;++i)      //输入前n个单元中叶子结点的权值（1至n即为真正的原始结点）
	{
		cout <<"请输入第"<< i << "个结点的权值:";
		cin >> HT[i].weight;     
	}
	cout << endl;
	for (int i = n + 1; i <= m; i++)    //创造哈夫曼树的循环（m-n的空间存放构造哈夫曼中生成的结点）
	{
		int s1 , s2 ;
		Select(HT, i - 1, s1, s2);        //在已经创造的非0结点中，选择两个其双亲域为0且权值最小的结点，并返回他们在HT中的序号s1和s2
		if (s1 != 0 && s2 != 0)
		{
			HT[s1].parent = i;
			HT[s2].parent = i;
			//得到新结点i
			HT[i].lchird = s1;
			HT[i].rchird = s2;
			HT[i].weight = HT[s1].weight + HT[s2].weight;     //i结点的权值是左右孩子权值之和
		}
	}
	return OK;
}

4.Select函数的编写

void Select(HuffmanTree HT, int k, int &s1, int &s2)    //选择两个其双亲域为0且权值最小的结点，并返回他们在HT中的序号s1和s2
{
	int temp = 2147483646;            
	for (int i = 1; i <= k; i++)
	{
		if (HT[i].parent == 0)          //前提：双亲域为0
		{
			if (HT[i].weight < temp)          //选出权值最小的结点，并记录下标
			{
				s1=i;
				temp = HT[i].weight;
			}
		}
	}
	temp = 2147483646;
	for (int i = 1; i <= k; i++)
	{
		if (HT[i].parent == 0)          //前提：双亲域为0
		{
			if (HT[i].weight < temp&&i!=s1)          //选出权值最小的结点（除了s1），并记录下标
			{
				s2 = i;
				temp = HT[i].weight;
			}
		}
	}
}

 

5.哈夫曼编码

编码前要先定义HuffmanCode类型

typedef char ** HuffmanCode; //编码时存储空间的二级指针类型

 

空间理解：
HuffmanCode（一个字符型二级指针） HC;

STATUS CreatHuffmanCode(HuffmanTree HT,HuffmanCode & HC,int n)		//根据哈夫曼树进行编码
{
	if (n <= 1)      //结点数量不合法        
	{
		return ERROR;
	}
	//从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
	HC = new char *[n + 1];         //分配存储n个字符编码的编码表空间（HC指向字符的地址）
	char* cd = new char[n];      //分配临时存放每个字符编码的动态数组空间 
	int start,c,f;
	cd[n - 1] = '\0';          //编码结束符
	for (int i=1;i<=n;i++)      //逐个字符求哈夫曼编码
	{
		start = n - 1;      //strat开始时指向最后，即编码结束符位置（读取编码是从叶子向根读，所以记录要从最后往前记录）
		c = i;              //记录i（结点）的下标
		f = HT[i].parent;     //记录当前结点的双亲下标
		while (f!=0)       //未到头结点则不断向上回溯
		{
			--start;           
			if (HT[f].lchird == c)   //判断子节点是父节点的左子还是右子（从而进行编码）
				cd[start] = '0';
			else
				cd[start] = '1';
			c = f;               //更新数据，实现回溯
			f = HT[f].parent;
		}
		//为第i个字符分配空间
		HC[i] = new char[n - start];
		strcpy(HC[i],&cd[start]);        //将这个字符对应的编码地址给了HC的[i]
	}
	delete cd;                      //释放临时空间
	cd = NULL;
	return OK;
}

 

6.展示编码

void show(HuffmanCode HC,int n)
{
	for (int i = 1; i <= n; i++) //先释放里指针空间（当年给他分配了n+1个空间，所以循环从0到n）
	{
		cout << HC[i]<<setw(5);         //输出编码（setw是为了美观，空几行）
	}
	cout << endl;
}

 

7.译码

对于哈夫曼编码的译码一定要根据哈夫曼树编译

STATUS translate(HuffmanTree HT, HuffmanCode HC,int n)   //译码（根据哈夫曼树进行翻译）
{
	if (n <= 1)      //结点数量不合法        
	{
		return ERROR;
	}
	char *str;
	for (int i = 1; i <= n; i++)
	{
		str = HC[i];      
		int f=2 * n - 1;             //定位最后的爸爸;
		while (*str!='\0')                //存在码
		{

			if (*str == '0')      //判断
			{
				f = HT[f].lchird;
			}
			else if (*str == '1')
			{
				f = HT[f].rchird;
			}
			str++;
			if (HT[f].lchird==0 && HT[f].rchird==0)     //是个叶子，处理它的权值
			{
				cout << HT[f].weight ;
			}
		}
	}
	return OK;
}

 

8.释放空间

因为树和编码的空间是建立在堆上的，所以要进行相应的释放

void Destroy(HuffmanTree &HT, HuffmanCode &HC,int n)
{
	delete [] HT;
	HT = NULL;
	for (int i = 1; i <=n; i++) //先释放里指针空间（当年给他分配了n+1个空间，所以循环从0到n）
	{
		delete[] HC[i];
	}
	delete[] HC;    //释放外指针
	cout << "\n空间已进行释放\n";
}

 

9.调用测试

void DoHuffman()
{
	int n;
	HuffmanTree HT;
	HuffmanCode HC;
	cout << "结点个数：";
	cin >> n;
	CreateHuffmanTree(HT,n);
	CreatHuffmanCode(HT,HC,n);
	show(HC,n);
	cout << "随便点一下进行翻译\n";
	_getch();
	translate(HT, HC,n );
	Destroy(HT,HC,n);
}

void main()
{
	DoHuffman();
}

 

效果：

效果虽然不太美观，但至少是正确了?

这些只是基本算法，后面再利用API加个界面啥的，就完成了！

二.实现对字符串操作♣

1.给哈夫曼树结构体增加一个字符

typedef struct
{
	char c;               //结点多带字符（这个就是新增加的）
	int weight;               //结点的权值
	int parent, lchird, rchird;   //结点的双亲，左孩子，右孩子的下标
}HTNode,*HuffmanTree;      //HTNode：结点类型。HuffmanTree：哈夫曼数的指针

另外定义一个MAXSIZE

一会有用

#define MAXSIZE 100

再定义一个枚举体以及一个全局变量，用来区分用户现在在进行哪个编码译码

enum Choose
{
	ToNum,
	ToStr
};
Choose cho = ToNum;

 

2.创建一个结构体Node（用来记录字符串中出现几种字符以及对应各个字符的频率）

typedef struct
{
	char c;             //对应字符
	int p;               //对应出现频率
}Node;

3.定义函数getNode（用来实现把字符串分析出有几个字符以及各个字符的频率并保存下来）

n是记录str中有几种字符。

如：”asswva”中有4种：’a’,’s’,’w’,’v’。

void getNode(string str, Node *nod,int &n)          //得到字符串中不同字符以及各自字符的频率并返回出去
{
	for (int i = 0; i < MAXSIZE; i++)           //初始化
	{
		nod[i].p = 0;
	}
	bool haveIn; 
	n = 0;

	for (int i = 0; i < str.length(); i++)         //对字符串str逐个操作
	{
		int L = n + 1;
		haveIn = false;             //布尔变量，负责记录
		for (int k = 0; k < L; k++)            //检验当前字符串是否是已经记录过的类型
		{
			if (nod[k].c == str[i])             //是，则在已记录中，对这个字符串的频率加一
			{
				nod[k].p++;
				haveIn = true;
			}
		}
		if (!haveIn)
		{
			nod[n].c = str[i];
			nod[n].p = 1;
			n++;
		}

	}
	//截止这步，nod就保存了str中各个字符以及对应频率,n记录了有几个不同字符
	cout << "展示细节：\n";
	for (int i = 0; i < n; i++)
	{
		cout << "字符：" << nod[i].c << "    出现次数：" << nod[i].p << endl;
	}
}

4.重载一个创造哈夫曼树的函数

这里定义了MAXSIZE个空间给 nod?

注意nod是从0开始保存，HT是从1开始

STATUS CreateHuffmanTree(HuffmanTree &HT,string str,int &n)    //构造哈夫曼树 （只是针对字符串情况的重载）
{
	if (str.length() < 1)
		return ERROR;

	n=0;
	Node nod[MAXSIZE];
	getNode(str,nod,n);

	int m = n * 2 - 1;          //为了方便，数组下标从1开始与结点对应
	HT = new HTNode[m + 1];
	for (int i = 1; i <= m; ++i)    //做初始化，HT中每个单元的双亲，左右孩子的下标都初始化为0
	{
		HT[i].parent = 0;
		HT[i].lchird = 0;
		HT[i].rchird = 0;
	}
	for (int i = 1; i <= n; ++i)      //输入前n个单元中叶子结点的权值（1至n即为真正的原始结点）
	{
		HT[i].c = nod[i - 1].c;     //字符保存到结点中         
		HT[i].weight=nod[i-1].p;     //出现频率作为权值
	}
	cout << endl;
	for (int i = n + 1; i <= m; i++)    //创造哈夫曼树的循环（m-n的空间存放构造哈夫曼中生成的结点）
	{
		int s1, s2;
		Select(HT, i - 1, s1, s2);        //在已经创造的非0结点中，选择两个其双亲域为0且权值最小的结点，并返回他们在HT中的序号s1和s2
		if (s1 != 0 && s2 != 0)
		{
			HT[s1].parent = i;
			HT[s2].parent = i;
			//得到新结点i
			HT[i].lchird = s1;
			HT[i].rchird = s2;
			HT[i].weight = HT[s1].weight + HT[s2].weight;     //i结点的权值是左右孩子权值之和
		}
	}
	return OK;
}

5.其他微调

处理字符串这里只是在哈夫曼树中给各个叶子结点增加了一个字符而已，并不影响编码译码啥的（但是概念已经变了，现在的权值是各个字符在字符串中对应的出现次数）

要改变的就是译码这里，利用先前定义的枚举，改变一下输出，来还原字符串（但是这个字符串暂且不能按照顺序还原）

STATUS translate(HuffmanTree HT, HuffmanCode HC,int n)   //译码（根据哈夫曼树进行翻译）
{
	if (n <= 1)      //结点数量不合法        
	{
		return ERROR;
	}
	char *str;
	for (int i = 1; i <= n; i++)
	{
		str = HC[i];      
		int f=2 * n - 1;             //定位最后的爸爸;
		while (*str!='\0')                //存在码
		{

			if (*str == '0')      //判断
			{
				f = HT[f].lchird;
			}
			else if (*str == '1')
			{
				f = HT[f].rchird;
			}
			str++;
			if (HT[f].lchird==0 && HT[f].rchird==0)     //是个叶子，处理它的权值
			{
				if(cho==ToNum)
					cout << HT[f].weight<<endl;
				else if(cho==ToStr)               
				{
					for (int k = 0; k < HT[f].weight; k++)      //根据权值多次输出对应的字符
					{
						cout << HT[f].c;
					}
				}
			}
		}
	}
	return OK;
}

6.调用测试：

根据不同的cho进行不同测试

void DoHuffman(Choose Cho)
{
	HuffmanTree HT;
	HuffmanCode HC;
	if (Cho == ToNum)
	{
		int n;
		cout << "请输入元素个数：（回车键输入）";
		cin >> n;
		if (ERROR == CreateHuffmanTree(HT, n))
		{
			cout << "请合法输入参数\n";
		}
		else
		{
			CreatHuffmanCode(HT, HC, n);
			show(HC, n);
			cout << "\n按t进行译码\n\n";
			char t = _getch();
			if (t == 't' || t == 'T')
				if (ERROR == translate(HT, HC, n))
					cout << "译码失败！未知错误！";
			Destroy(HT, HC, n);
		}
	}
	else if(Cho==ToStr)
	{
		int n;
		string str;
		cout << "请输入字符串：（回车键输入）";
		cin >> str;
		if (ERROR == CreateHuffmanTree(HT, str,n))
		{
			cout << "请合法输入参数\n";
		}
		else
		{
			CreatHuffmanCode(HT, HC, n);
			show(HC, n);
			cout << "\n按t进行译码\n\n";
			char t = _getch();
			if (t == 't' || t == 'T')
				if (ERROR == translate(HT, HC, n))
					cout << "译码失败！未知错误！";
			Destroy(HT, HC, n);
		}
	}
}
void main()
{
	cho = ToStr;
	DoHuffman(cho);
}

（一些输出我加了一些空格，换行之类的，文中没有细说）

可以看到结果是正确的

三.美化♠

最后就是利用各循环啥的那这个程序可以更“正经”

我这里就是加了个while循环，细节改了改

void welcome()
{
	string str = "欢迎来到哈夫曼编码译码器";
	cout << str;
}
void DoHuffman(Choose cho);
void over()
{
	exit(0);
}
void GameManager()
{
	system("cls");                     //清屏
	welcome();
	while (true)
	{
		system("color 0A");
		cout << "请输入你想要进行的操作的序号\n";
		cout << "1.对数字（权值）进行编码译码处理\n";
		cout << "2.对字符串进行编码译码处理\n";
		cout << "3.退出程序\n";
		char s = _getch();
		switch (s)
		{
		case '1':
			cho = ToNum;
			system("cls");                     //清屏
			DoHuffman(cho);
			break;
		case '2':
			cho = ToStr;
			system("cls");                     //清屏
			DoHuffman(cho);
			break;
		case '3':
			system("cls");
			over();
			break;
		default:
			break;
		}

	}
}

 

OK！课设完成了！

（有心的还可以加个读取文件功能，和字符串一个道理，我就懒得弄了?）

 

###

 

商业转载 请联系作者获得授权，非商业转载 请标明出处

打赏

发表评论

邮箱地址不会被公开。 必填项已用*标注