﻿ C++霍夫曼编码（Huffman Coding）_OC/C/C++_开心洋葱网
• 欢迎访问开心洋葱网站，在线教程，推荐使用最新版火狐浏览器和Chrome浏览器访问本网站，欢迎加入开心洋葱` QQ群`
• 为方便开心洋葱网用户，开心洋葱官网已经开启复制功能！
• 欢迎访问开心洋葱网站，手机也能访问哦~欢迎加入开心洋葱多维思维学习平台` QQ群`
• 如果您觉得本站非常有看点，那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~！
• 由于近期流量激增，小站的ECS没能经的起亲们的访问，本站依然没有盈利，如果各位看如果觉着文字不错，还请看官给小站打个赏~~~~~~~~~~~~~！

# C++霍夫曼编码（Huffman Coding）

2775次浏览

http://blog.csdn.net/here1009/article/details/8071251

``` #include<iostream>
#include<string>
#include<queue>
using namespace std;

class node{
public:
node(string con, float wht, node* left, node* right, string co ){
content=con;
weight=wht;
leftchild=left;
rightchild=right;
code=co;
}
string content;
float weight;
node* leftchild;
node* rightchild;
string code;
};
void insertion_sort(node** array, int low, int high){
for(int i=low+1;i<high;i++){
node* tem=array[i];
int j=i-1;
while(array[j]->weight>tem->weight&&j>=low){
array[j+1]=array[j];
j--;
}
array[j+1]=tem;
}
}
void create_huffman_tree(string* s, float* w,int n,node** array){
for(int i=0;i<n;i++){
array[i]=new node(s[i],w[i],NULL,NULL,"");
}
insertion_sort(array,0,n);
//~ for(int i=0;i<n;i++){
//~ cout<<array[i]->content<<"*";
//~ }
int p=0;
while(p!=n-1){
node* min_1=array[p];
node* min_2=array[p+1];
node* new_node=new node("",min_1->weight+min_2->weight,min_1,min_2,"");
//cout<<new_node->weight<<endl;
array[p+1]=new_node;
p=p+1;
insertion_sort(array,p,n);
}

}

void create_huffman_code(node* p){
queue<node*> nq;
nq.push(p);
while(nq.size()!=0){
node* cur=nq.front();
nq.pop();
node* l=cur->leftchild;
if(l!=NULL){l->code=cur->code+"0"; nq.push(l);}
node* r=cur->rightchild;
if(r!=NULL){r->code=cur->code+"1"; nq.push(r);}
if(l==NULL&&r==NULL){
cout<<cur->content<<": "<<cur->code<<endl;
}
}
}
int main(int argc, char** argv){
node* array[8];
string s[8]={"a","b","c","d","e","f","g","h"};
float w[8]={1,1,2,3,5,8,13,21};
create_huffman_tree(s,w,8,array);
create_huffman_code(array[7]);
}
```