189 8069 5689

C++实现哈夫曼编码的方法

这篇文章主要讲解了C++实现哈夫曼编码的方法,内容清晰明了,对此有兴趣的小伙伴可以学习一下,相信大家阅读完之后会有帮助。

创新互联专注于南县企业网站建设,成都响应式网站建设,商城网站定制开发。南县网站建设公司,为南县等地区提供建站服务。全流程按需制作,专业设计,全程项目跟踪,创新互联专业和态度为您提供的服务

#include
#include
#include
#include
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 open;

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


int main(){
 int a[Max];
 for(int i = 0;i < Max;i++)
 a[i] = 0;  //初始化数组 
 string s;
 cout<<"请输入字符串:";
 cin>>s;
 
 vector v;
 vector::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<<"它的哈夫曼编码为:"<

看完上述内容,是不是对C++实现哈夫曼编码的方法有进一步的了解,如果还想学习更多内容,欢迎关注创新互联行业资讯频道。


分享文章:C++实现哈夫曼编码的方法
分享路径:http://jkwzsj.com/article/jheidg.html

其他资讯