c++实现huffman哈夫曼编码

#include<iostream> #include<stdio.h> #include<string> using namespace std; //本程序为对初始数组进行排序，而是在编码的过程中动态寻找最小的两个节点。 typedef struct { int weight; int parent,lchild,rchild; }HuffNode,*HuffTree; void select(HuffTree HT,int n,int &s1,int &s2);//s1、s2为搜索到的未被访问过的节点中权值最小的两个节点的标号 void HuffCoding(HuffTree &HT,int *w,int n);//w为要编码的数据，n为数据的大小。 int w[]={4,2,13,3,7,10,8,23,22,35,52,31};//数据数值大小作为频率大小。 void select(HuffTree HT,int n,int &s1,int &s2) {//寻找值最小的两个节点，&s1,&s2是引用，这样才此处修改s1,s2的值后主程序中的值也相应改变。如果是临时变量的话则需要返回值，略麻烦。 s1=s2=0; int b1,b2=9999; for (int i=0;i<n;++i) //寻找未被访问过的第一个节点 if (HT[i].parent==0){ b1=HT[i].weight; break; } for(int i=0;i<n;i++)//寻找值最小的节点 if(HT[i].parent==0) if(HT[i].weight<=b1){ b1=HT[i].weight; s1=i; } HT[s1].parent=1;//将上面找到的最小的节点的父节点设置为1（其实任意值都行，因为之后主程序会对其重新赋值，此处只是起标记的作用） for(int i=0;i<n;i++)//寻找值第二小的节点 if(HT[i].parent==0) if(HT[i].weight<b2){ b2=HT[i].weight; s2=i; } } void HuffCoding(HuffTree &HT,int *w,int n) { //w[]={4,2,13,3,7,10,8}; int m=2*n-1;//m为总节点数目 HT=(HuffNode*)malloc(m*sizeof(HuffNode));//创建m个节点，作为Huffman树 int s1=0,s2=0;//权值最小的两个节点 memset(HT,0,m*sizeof(HuffNode));//将所有节点的值初始化 for(int i=0;i<n;i++) HT[i].weight=w[i];//将需要编码的节点的值赋值给二叉树的叶子节点。 for(int i=n;i<m;i++) { select(HT,i,s1,s2);//每次寻找节点时包括新生成的节点，注意此处i值是一直变化的。 HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; HT[s1].parent=HT[s2].parent=i; } for(int i=0;i<n;i++) { int a=i,j=0; string temp; while(HT[a].parent!=0) { if(a==HT[HT[a].parent].lchild) temp+='0';//左树编码为0 else if(a==HT[HT[a].parent].rchild) temp+='1';//右树编码为1 j++; a=HT[a].parent; } reverse(temp.begin(),temp.end()); cout<<"第"<<i+1<<"个数的huffman编码是："<<temp<<"\t"; cout<<endl; } free(HT); } void main() { int len=sizeof(w)/sizeof(w[0]);//获取数组长度 for(int i=0;i<len;i++) cout<<w[i]<<"\t"; cout<<endl; HuffTree HT; HuffCoding(HT,w,len); system("pause");//在程序运行结束后等待，否则程序运行后会闪退。 }