Huffman 哈夫曼编码 信息论 c++代码

    #include<iostream>
    #include<vector>
    #include <algorithm>
    using namespace std;
    
    struct nnode{
    	float p;
    	nnode *parent=NULL;
    	nnode *rchild=NULL;
    	nnode *lchild=NULL;
    }; 
    
    bool GSort (nnode a,nnode b) { return (a.p>b.p); }
    
    void bianli(nnode* &head,string str){
    	if(head->lchild!=NULL){
    		bianli(head->lchild,str+"1");
    	}
    	if(head->rchild!=NULL){
    		bianli(head->rchild,str+"0");
    	}
    	if(head->rchild==NULL&&head->lchild==NULL){
    		cout<<"概率"<<head->p<<"的霍夫曼编码是："<<str<<endl;
    	}
    }
     
    int main(int argc, char** argv) {
    	cout<<"请输入信源符号个数"<<endl;
    	int n;
    	cin>>n;
    	cout<<"请输入分布概率"<<endl;
    	vector<nnode> v;
    	float a=0; 
    	for(int i=0;i<n;i++){
    		nnode p1;
    		p1.lchild=NULL;
    		p1.parent=NULL;
    		p1.rchild=NULL;
    		cin>>p1.p;
    		v.push_back(p1);
    		a+=p1.p;
    	}
    	if(a!=1){
    		cout<<"错误！分布概率之和不为0"<<endl;
    		return 0;
    	}
    	sort(v.begin(),v.end(),GSort);
    	nnode *root=new nnode;
    	for(int j=0;j<n-1;j++){
    		nnode* pnode=new nnode;
    		nnode* left=new nnode;
    		*left=v.back();
    	    v.pop_back();
    	    nnode *right=new nnode;
    		*right=v.back();
    	    v.pop_back();
    	    pnode->p=right->p+left->p;
    	    pnode->rchild=right;
    	    pnode->lchild=left;
    	    right->parent=left->parent=pnode;
    	    for(vector<nnode>::iterator k = v.begin(); k <= v.end(); k++){
    	    	nnode p2=*k;
    	    	if(pnode->p>=p2.p){
    	    		v.insert(k,*pnode);
    	    		break;
    			}else{
    				if(k==v.end()){
    					v.push_back(*pnode);
    				}
    			}
    		}
    		root=pnode;
    	}
    	cout<<"霍夫曼编码如下（概率大的用短码，概率小的用长码）："<<endl;
    	bianli(root,"");
    	return 0;
    }
    
    
    
![](https://ad.itadn.com/c/weblog/blog-img/images/2025-08-17/EP20HXoSNGYUmyqWQFcwxKAO7i4v.png)