本文主要是介绍哈弗曼编码（C++），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
通过参考网上资料和自己调试，终于编写好了哈弗曼编码#include <iostream>
#include <fstream>
#include <string>
using namespace std;
struct node
{int weight;int parent;int lchild;int rchild;
};
struct Nchar
{char n;int weight;char* code;};
class huffman
{int n;string text;node * huffTree;Nchar * nchar,CharMapNode;void select(int n, int &s1, int &s2);//查询权值最小的两项
public:void gettext(char* CHAR);//读取文件内容void savetext(char* CHAR);//将结果保存void creattable();//根据读取文件内容，确定的权值，创建表void CountCharsWeight();//统计读取的文件内容的各字符的权值void display();//显示表，及权值void coding();//编码};
void huffman::gettext(char* CHAR)
{ifstream into(CHAR);if(!into){cerr << "无法打开文件！" <<endl;exit(0);}char a;while(into.get(a)){text+=a;}
}
void huffman::savetext(char* CHAR)
{ofstream out(CHAR);int m=2*n-1;for(int a=1;a<=m;a++){out<<a<<": rchild:"<<huffTree[a].rchild<<" lchild:"<<huffTree[a].lchild<<" parent:"<<huffTree[a].parent<<" weight:"<<huffTree[a].weight<<endl;}out<<"---------------------------------------------"<<endl;for(int h=1;h<=n;h++){out<<nchar[h].n<<"的权值为："<<nchar[h].weight<<" 编码为："<<nchar[h].code<<endl;}}
void huffman::select(int n, int &s1, int &s2)
{s1 = s2 = 0;for (int i = 1; i <= n; ++i){if (huffTree[i].parent != 0)continue;if (s1 == 0)s1 = i;else if (s2 == 0){//此处采用的策略，使得整个过程中s1的权值小于s2的权值if (huffTree[i].weight < huffTree[s1].weight){s2 = s1;s1 = i;}elses2 = i;}else{if (huffTree[i].weight < huffTree[s1].weight){s2 = s1;s1 = i;}else if (huffTree[i].weight < huffTree[s2].weight)s2 = i;}}
}
void huffman::creattable()
{huffTree = new node[2*n];for(int m1=1;m1<=n;m1++){huffTree[m1].lchild=0;huffTree[m1].rchild=0;huffTree[m1].parent=0;huffTree[m1].weight=nchar[m1].weight;}for(int k=n+1;k<=2*n-1;k++){huffTree[k].lchild=0;huffTree[k].rchild=0;huffTree[k].parent=0;huffTree[k].weight=0;}int m = 2 * n - 1;for (int i = n + 1; i <= m; ++i)
{int s1,s2;select(i - 1, s1, s2);huffTree[s1].parent = huffTree[s2].parent = i;huffTree[i].lchild = s1;huffTree[i].rchild = s2;huffTree[i].weight = huffTree[s1].weight + huffTree[s2].weight;
}
}void huffman::CountCharsWeight()
{int i = 0;n = 0;nchar = new Nchar[2];nchar[1].n=text[i];nchar[1].weight=1;n++;for(i=1;i<text.size();i++){int j;for (j = 1; j <= n; ++j) //遍历当前字符表，如果已存在该字符，权值+1{if (text[i] == nchar[j].n){++nchar[j].weight;break;}}if(j>n){++n;Nchar* newchars = new Nchar[n + 1];memcpy(newchars, nchar, n * sizeof(Nchar));delete nchar;nchar = newchars;nchar[n].n = text[i];nchar[n].weight = 1;}}huffman::n=n;}
void huffman::display()
{int m=2*n-1;for(int a=1;a<=m;a++){cout<<a<<": rchild:"<<huffTree[a].rchild<<" lchild:"<<huffTree[a].lchild<<" parent:"<<huffTree[a].parent<<" weight:"<<huffTree[a].weight<<endl;}cout<<"---------------------------------------------"<<endl;for(int h=1;h<=n;h++){cout<<nchar[h].n<<"的权值为："<<nchar[h].weight<<" 编码为："<<nchar[h].code<<endl;}cout<<"---------------------------------------------"<<endl;}
void huffman::coding()
{//从叶子到根节点逆向求每个字符的哈弗曼编码char *cd = new char[n]; //分配求编码的工作空间（每个字符编码结果最长n-1再加上'\0'）cd[n-1] = '\0'; //编码结束符for(int i = 1; i <= n; ++i) //逐个字符求哈弗曼编码{int start = n - 1;int c,f;//从叶子到根逆向求编码for (c = i, f = huffTree[i].parent; f != 0; c = f, f = huffTree[f].parent){if (huffTree[f].lchild == c) //左孩子编码为0cd[--start] = '0';else //右孩子编码为1cd[--start] = '1';}nchar[i].code = new char[n - start]; //为第i个字符编码分配空间strcpy(nchar[i].code,&cd[start]);}delete cd;
}void main()
{huffman hum;hum.gettext("text.txt");hum.CountCharsWeight();hum.creattable();hum.coding();hum.savetext("SaveText.txt");hum.display();
}
这篇关于哈弗曼编码（C++）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
