接着学习C++哈夫曼编码

昨天 已经构建了哈弗曼树了。哈夫曼编码 就是从底倒着往前走 如果这点是左子 0右子1 直到根  而且每个编码都不能是别的编码的前缀

上完整马 看注释哈

#ifndef H_HPP#define H_HPP#include <iostream>//1 2 4 6 每两个顶点 都把权值相加合成一个新顶点 直到剩下一个点 就构建完成这个哈夫曼树了。 //         //         13                   //     6       7//       3       4//    1     2using namespace std;template<typename T>struct Huf{	int parent;	int lch;	int rch;	int w;	};template<typename T>struct HufCode{	int  bt[111];//这里就是放编码的地方了 当前顶点为左子 0 右子 1	int  start;//开始位置	int  w;};template<typename T>class Do{PRivate:	Huf<T> *huff;	HufCode<T>*huffcode;	int *a;	int n;	int m;public:	Do();	~Do();	void Q_Sort(int a[],int l,int r);	void setCode();	void show();};template<typename T>Do<T>::Do(){	a = new int[5]{23, 43, 13, 11, 5 };	//这里可以有一个char b[] 里面放着·每个点的信息 a b c d  e 然后上面这些a[]存的是每个点的频率	n = 5;	Q_Sort(a, 0, 4);	m = n * 2 - 1;	huff = new Huf<T>[m];	huffcode = new HufCode<T>[n];//初始化	for (int i = 0; i < m; i++)	{		huff[i].parent = -1;		huff[i].w = 0;		huff[i].lch = -1;		huff[i].rch = -1;	}			for (int i = 0; i < n - 1; i++)	{		int m1=9999999, m2=9999999, x1=0, x2=0;		for (int j = 0; j < n + i; j++)		{			if (huff[j].w < m1&&huff[j].parent == -1)//如果当前数比第一个数小 就替换第一个数 如果没使用过 他的父节点才是-1 使用过就不能用了			{				m2 = m1;				m1 = huff[j].w;				x2 = x1;				x1 = j;			}			else if (huff[j].w<m2&&huff[j].parent==-1)//当前数比第二个数小			{				m2 = huff[j].w;				x2 = j;			}		}//这里已经找出来最小的俩顶点了
		huff[x1].parent = n + i;//就合并成新的树		huff[x2].parent = n + i;		huff[n + i].w = huff[x1].w + huff[x2].w;		huff[n + i].lch = x1;		huff[n + i].rch = x2;	}}template<typename T>Do<T>::~Do(){	delete[]huff;	delete a;}template<>void Do<int>::Q_Sort(int a[], int l, int r){	int key = a[l];	int i = l;	int j = r;	if (i>=j)	{		return;	}	while (i < j)	{		while (i<j&&a[j]>key)			j--;		if (i < j)			a[i++] = a[j];		while (i<j&&a[i]<key)		{			i++;		}		if (i < j)			a[j--]= a[i];	}	a[i] = key;	Q_Sort(a, l, i - 1);	Q_Sort(a, i + 1, r);}template<typename T>void Do<T>::show()//看所有顶点权值{	for (int i = 0; i < m; i++)	{		cout << i << " " << huff[i].w << endl;	}	setCode();	for (int i = 0; i < n; i++)//访问每个顶点	{				for (int j = huffcode[i].start+1 ; j < n; j++)//将huffcode[i]的编码打印出来		{			cout << huffcode[i].bt[j];	        }		cout << endl;	}}template<typename T>void Do<T>::setCode(){		HufCode<T>*tempCode = new HufCode<T>;	for (int i = 0; i < n; i++)	{		tempCode->start = n - 1;//先从底部开始倒着走				tempCode->w = huff[i].w;		int child = i;//当前点作为孩子		int parent = huff[i].parent;//设置好父节点
			while (parent != -1)//父节点不为空就一直向上找			{				if (child == huff[parent].lch)//左 0					tempCode->bt[tempCode->start] = 0;				else					tempCode->bt[tempCode->start] = 1;				tempCode->start--;       // 假设最后那个是1 就变为00001 然后start-- 下一次还是1 就 00011了			child=parent;//往上走 父变子 找父的父作为新的parent			parent = huff[child].parent;			}			for (int j = n - 1; j > tempCode->start;j--)		{			huffcode[i].bt[j] = tempCode->bt[j];//找完了i这个顶点的全部父了 就把编码装进huffcode[i]的bt					}		cout << endl;			huffcode[i].start = tempCode->start;//编码开始位置			huffcode[i].w = tempCode->w;//权值也存好			}	delete tempCode;}#endif //H_HPP
#include "h.hpp"int main(){	Do<int>d;	d.show();	system("pause");}嗯。酱紫。