centos 树莓派USB pandas Jenkins RabbitMQ flask ipad serialization mtu原理 seo教程下载 datetimepicker赋值 nikto扫描web漏洞 linux获取当前时间 wordpress本地建站 python3入门 python的数据类型 java正则 javamysql javaforeach java循环语句 java获取文件大小 广告代码 计算机电子书 flash实例 刷机工具下载 博途v14安装教程 js跳出for循环 视频md5修改器 php正则匹配 网卡驱动安装包 小米8游戏模式 头条视频解析 mmap文件怎么打开 spring拦截器 捷速pdf编辑器 js继承的几种方式 mxf是什么格式 方正美黑简体 企业路由器设置 图片批处理
当前位置: 首页 > 学习教程  > 编程语言

哈夫曼编码的实现

2021/5/8 21:04:41 文章标签:

#include<iostream> #include<cstdlib> #include <cstring> using namespace std; class Code //分配动态数组&#xff0c;存储哈夫曼编码&#xff1b; { public:char* hfmcode;//存储编码char data; }; class TREE { private:char data;//保存数据…

#include<iostream>
#include<cstdlib>
#include <cstring>
using namespace std;
class Code           //分配动态数组,存储哈夫曼编码;
{
public:
	char* hfmcode;//存储编码
	char data;
};
class TREE
{
private:
	char data;//保存数据
	int weight, parent, lchild, rchild;//权值域,双亲域,左孩子域,右孩子域
	int* code;//用来存储编码
	//权值域保存该结点的权值,双亲域保存该节点的双亲在该数组的下标,左右孩子保存该结点的左右孩子在数组中的下标
public:
	void setdata(char data)
	{
		this->data = data;
	}
	char getdata()
	{
		return data;
	}
	void creathufftree(TREE*& HT, int* w, int n);//创建哈夫曼树
	void select(TREE*& HT, int n, int& s1, int& s2);//选择出最小和次小的下标
	void huffmancode(TREE*& HT, Code*& HC, int n);//哈夫曼编码
	void translate(TREE*& hu,char jieguo[]);//解码
	void show(char *str ,Code*& HC,int n, TREE*& hu);

};



void TREE::select(TREE *& HT, int n, int& s1, int& s2)//把最小和次小的下标找出来
{
	int minum;      // 定义一个临时变量保存最小值?
	for (int i = 1; i <= n; i++)     // 以下是找到第一个最小值
	{
		if (HT[i].parent == 0)
		{
			minum = i;
			break;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (HT[i].parent == 0)
			if (HT[i].weight < HT[minum].weight)
				minum = i;
	}
	s1 = minum;
	// 以下是找到第二个最小值,且与第一个不同
	for (int i = 1; i <= n; i++)
	{
		if (HT[i].parent == 0 && i != s1)
		{
			minum = i;
			break;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (HT[i].parent == 0 && i != s1)
			if (HT[i].weight < HT[minum].weight)
				minum = i;
	}
	s2 = minum;
}
void TREE::huffmancode(TREE*& HT, Code*& HC, int n)//n代表要编码的叶子结点的个数,建立哈夫曼编码
{
	char* cd = new char[n];//分配当前编码的工作空间;
	int c, p, i;   //c为当前节点,p指向双亲节点;
	HC = new Code[n + 1];

	cd[n - 1] = '\0';     //从右往左存放 ,首先存放编码结束符;
	for (i = 1; i <= n; i++)
	{
		HC[i].data = HT[i].data;
		int start = n - 1;    //初始化编码的起始指针;
		for (c = i, p = HT[i].parent; p != 0; c = p, p = HT[p].parent)
		{
			if (HT[p].lchild == c)
				cd[--start] = '0';
			else
				cd[--start] = '1';
		}
		HC[i].hfmcode = (char*)malloc(n * sizeof(char)); //为第i个编码分配空间;
		strcpy_s(HC[i].hfmcode,strlen(cd)+1, &cd[start]);
	}
	delete[] cd;
}
void TREE::creathufftree(TREE *&HT, int* w,int n)//创建哈夫曼树 //n记录传入数据的个数
{
	int m, s1, s2;
	m = n * 2 - 1;  // 总结点的个数
	HT = new TREE[m + 1]; // 分配空间
	for (int i = 1; i <= n; i++) // 1 - n 存放叶子结点,初始化
	{
		HT[i].weight = w[i];
		HT[i].parent = 0;
		HT[i].lchild = 0;
		HT[i].rchild = 0;
	}
	for (int i = n + 1; i <= m; i++)   // 非叶子结点的初始化
	{
		HT[i].weight = 0;
		HT[i].parent = 0;
		HT[i].lchild = 0;
		HT[i].rchild = 0;
	}
	for (int i = n + 1; i <= m; i++)     // 创建非叶子节点,建哈夫曼树
	{   // 在HT[1]~HT[i-1]的范围内选择两个parent为0且weight最小的两个结点,其序号分别赋值给 s1 s2
		select(HT, i - 1, s1, s2);
		HT[s1].parent = i;  // 删除这两个结点
		HT[s2].parent = i;
		HT[i].lchild = s1;      // 生成新的树,左右子节点是 s1和s2
		HT[i].rchild = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;   //新树权值
	}
}

int number(char* input, int* p, int q[], char c[])
{
	//c判断到底都有那些字符
	//q给字符统计出现几次
	int g = 0; //字符数量以及出现几次用到,看存几个元素
	for (int i = 0; i < 256; i++)
	{
		p[i] = 0;
	}
	for (int j = 0; input[j] != '\0'; j++)
	{
		p[(input[j])]++;//p给字符计数
	}
	for (int k = 0; k < 256; k++)
	{
		if (p[k] != 0)
		{
			q[g] = p[k];//统计字符出现几次
			c[g] = (char)k;//统计都有哪些字符
			g++;
		}
	}
	return g;
}

void TREE::translate(TREE*& HT,char jieguo[])
{
	int i, k = 0;
	int p = 0, root; //root为根节点;
	cout << "请输入数据:";
	string st1; cin >> st1;
	for (root = 1; HT[root].parent != 0; root = HT[root].parent);//把root循环到根
	for (i = 0, p = root; i < st1.size(); i++)
	{
		if (st1[i] == '0')
			p = HT[p].lchild;       //下一步是向左子树前进;
		else
			p = HT[p].rchild;
		if (HT[p].lchild == 0 && HT[p].rchild == 0)
		{
			jieguo[k++] = HT[p].data;
			p = root;
		}
	}
	jieguo[k] = '\0';
}

void TREE::show(char* str, Code*& HC,int n,TREE*& hu)
{
	for (int j = 0; j < strlen(str); j++)
	{
		for (int i = 1; i <= n; i++)
		{
			if (str[j] == hu[i].data)
			{
				cout << HC[i].hfmcode;
			}
		}
	}
}

void Menu()
{
	int a;
	char str[100];
	TREE tree; Code* hfcode;
	int* p = new int[256];
	int q[1000];//给字符统计出现几次
	char c[1000];//判断到底都有那些字符
	cout << "请输入数据:" << endl;
	cin >> str;
	system("pause");
	system("cls");
	int g = number(str, p, q, c);
	TREE* F = (TREE*)malloc(sizeof(TREE) * (2 * g - 1));
		while (1)
		{
			cout << "\n";
			cout << "                         -----------1.计算权值-------" << endl;
			cout << "                         ------------2.编码----------" << endl;
			cout << "                         ------------3.编码序列------" << endl;
			cout << "                         ------------4.解码----------" << endl;
			cout << "                         ------------5.退出----------" << endl;
			cout << "                         ----------------------------" << endl;
			cout << "\n\n请选择:";
			while (1)
			{
				cin >> a;
				if (a < 1 || a > 4)
				{
					cout << "输入错误请重新输入" << endl;
				}
				else
				{
					break;
				}
			}
			switch (a)
			{
			case 1:
			{
				int n = 0;
				while (n != g)
				{
					cout << c[n] << "权值:" << q[n] << endl;
					n++;
				}
				int k = strlen(str);
				int* weight = new int[g]; int m = 1;
				for (int j = 0;m<=g; j++,m++)
				{
					weight[m] = q[j];
					F[m].setdata(c[j]);
				}
				tree.creathufftree(F, weight,g);
				system("pause");
				system("cls");
				break;
			}
			case 2:
			{
				int g = number(str, p, q, c);
				for (int j = 0; j < g; j++)
				{
						cout<<c[j]<<endl;
				}
				tree.huffmancode(F,hfcode,g);
				for (int j = 1; j <= g; j++)
				{
					cout << hfcode[j].hfmcode << endl;
				}
				system("pause");
				system("cls");
				break;
			}
			case 3:
			{	int m = 1;
				for (int j = 0; m <= g; j++, m++)
				{
					F[m].setdata(c[j]);
				}
				for (int j = 0; j < strlen(str); j++)
				{
					cout << str[j];
				}
				cout << "\n";
				tree.show(str,hfcode,g,F);
				system("pause");
				system("cls");
				break;
			}
			case 4:
			{
				char jieguo[100]; int m = 1;
				for (int j = 0; m <= g; j++, m++)
				{
					F[m].setdata(c[j]);
				}
				tree.translate(F, jieguo);
				for (int j = 0; jieguo[j] != '\0'; j++)
				{ //条件默认为jieguo[i]不为空;
					cout << jieguo[j];
				}
			}
				system("pause");
				system("cls");
				break;
			case 5:
				exit(0);
			default:
				printf("输入无效!");
				system("pause");
				system("cls");
				break;
			}
		}
}
int main()
{
	Menu();
	return 0;
}

本文链接: http://www.dtmao.cc/news_show_995017.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?