哈夫曼树实现哈夫曼编码（C++）

哈夫曼树实现哈夫曼编码（C++）"/>

哈夫曼树实现哈夫曼编码（C++）

   题目要求：根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求赫夫曼编码，并能把给定的编码进行译码。

（1）初始化：从键盘输入一字符串（或读入一文件），统计出现的字符和每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树。对各个字符进行哈夫曼编码，最后打印输出字符及每个字符对应的哈夫曼编码。

（2）编码：利用已建好的哈夫曼树对“输入串”进行哈夫曼编码，最后打印输入串对应的哈夫曼编码（写入文件）。

（3）译码：利用已建好的哈夫曼树对给定的一串代码进行译码，并打印输出得到的字符串。（选作）

#include<iostream>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
map<char, int> mp;
typedef struct node
{int data=0;char name;
}node;
node sum[100];
typedef struct Ht
{int w;char name;string code;int parent, lchild, rchild;
}Ht,*Htree;
int flag[100] = { 0 };
void Select(Htree& ht, int n, int& s1, int& s2)
{int min1 = 999, min2 = 999;for (int i = 1; i <= n; i++)//查找权值第一小的点{if (flag[i] == 0 && (ht[i].w < min1)){min1 = ht[i].w;s1 = i;ht[i].code = "0";//小的在左}}flag[s1] = 1;//标记该点移出for (int i = 1; i <= n; i++)//查找权值第二小的点{if (flag[i] == 0 && (ht[i].w < min2)){min2 = ht[i].w;s2 = i;ht[i].code = "1";//大的在右}}flag[s2] = 1;//标记该点移出
}
void Inithtree(Htree& ht, int n)//初始化
{if (n <= 1) return;int m = 2 * n - 1;ht = new Ht[m + 1];for (int i = 1; i <= m; i++)//将1到m点中的父亲、左孩子、右孩子下标都初始为0{ht[i].name = sum[i].name;ht[i].parent = 0, ht[i].lchild = 0, ht[i].rchild = 0;ht[i].w = sum[i].data;}
}
void Createtree(Htree& ht, int n)
{int s1, s2;for (int i = n + 1; i <= 2 * n - 1; i++)//循环n-1次，建树{Select(ht, i - 1, s1, s2);//查找两个父亲为0且权值最小的点，并返回序号s1、s2ht[s1].parent = i, ht[s2].parent = i;//s1、s2父亲改为iht[i].lchild = s1, ht[i].rchild = s2;//s1、s2分别作为i的左右孩子ht[i].w = ht[s1].w + ht[s2].w;//i的权值为左右孩子权值之和}
}
void Printtree(Htree& ht, int n)//打印
{for (int i = 1; i <= 2 * n - 1; i++)cout << ht[i].name << " " << ht[i].w << " " << ht[i].parent << " " << ht[i].lchild << " " << ht[i].rchild << endl;
}
void bianma(Htree& ht, int n)//编码
{for (int i = 1; i <= n; i++){int parent = ht[i].parent;//获取该点父亲while (parent != 0)//不到根节点{ht[i].code = ht[parent].code + ht[i].code;//编码等于父亲加上自身parent = ht[parent].parent;//找父亲的父亲}}
}
int main()
{Htree h;string str;cin >> str;for (int i = 0; i < str.length(); i++){mp[str[i]]++;}int k = 1;int n = mp.size();//字符种类for (auto i : mp){sum[k].name = i.first;sum[k++].data = i.second;}Inithtree(h, n);Createtree(h, n);//Printtree(h, n);bianma(h, n);cout << "编码：" << endl;for (int i = 1; i <= n; i++)//输出各字符的编码cout << h[i].name << ": " << h[i].code << endl;for (int i = 0; i < str.length(); i++)//字符串转为编码{for (int j = 1; j <= n; j++){if (str[i] == h[j].name){cout << h[j].code << " ";break;}}}cout << endl;string str1;string str2[100];int d = 0;cout << "译码：" << endl;cin >> str1;for (int i = 0; i < str1.length(); i++){str2[d] += str1[i];for (int j = 1; j <= n; j++){if (str2[d] == h[j].code){cout << h[j].name;d++;break;}}}
}