C++实现哈夫曼编码

本文实例为大家分享了C++实现哈夫曼编码的具体代码，供大家参考，具体内容如下

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int Max = 300;

class tree{
public:
char s;
int num;
tree *left;
tree *right;
tree(){
 s= '!';
 num = 0;
 left = 0;
 right = 0;
}
tree(char a,int n,tree* p1,tree* p2){
 s = a;
 num = n;
 left = p1;
 right = p2;
}
};

vector<tree *> open;

/*********************************
**中序遍历输出各节点及其哈夫曼编码
*********************************/
void inorder(tree *t,string s){
if(t != 0){
inorder(t->left,s+'0');
if(t->s != '!')
 cout<<t->s<<":"<<s<<endl;
inorder(t->right,s+'1');
}
}

int main(){
int a[Max];
for(int i = 0;i < Max;i++)
a[i] = 0;  //初始化数组
string s;
cout<<"请输入字符串：";
cin>>s;

vector<char> v;
vector<char>::iterator vit;
for(int i = 0;i < s.length();i ++){
a[s[i]]++;  //确定每个字符出现的次数（频率）
vit = find(v.begin(),v.end(),s[i]);
if(vit == v.end()) //相同的字符只保留一个
 v.push_back(s[i]);
}
for(int i = 0;i < v.size();i ++){
tree *n = new tree();
n->s = v[i];
n->num = a[v[i]];
open.push_back(n); //存入open表中
}

/************************
**
**构造哈夫曼树
**
*************************/
tree *root;
while(open.size() != 1){
tree *min1,*min2; //min1,min2是当前open表中num值最小的节点
int sit1,sit2;
min1 = open.front();
sit1 = 0;
for(int i = 0;i < open.size();i++){
 if(open[i]->num < min1->num){
 min1 = open[i];
 sit1 = i;
 }
}
open.erase(open.begin()+sit1);

min2 = open.front();
sit2 = 0;
for(int i = 0;i < open.size();i++){
 if(open[i]->num < min2->num){
 min2 = open[i];
 sit2 = i;
 }
}
open.erase(open.begin()+sit2);

tree *t = new tree('!',min1->num + min2->num,min1,min2); //构造新节点，左右指针指min1和min2
open.push_back(t); //存入open表中
root = t;
}

cout<<"它的哈夫曼编码为："<<endl;
string s1 = "";
inorder(root,s1);

return 0;
}```

来源：https://blog.csdn.net/TKFEET/article/details/89394104