三进制哈弗曼编码C++程序

//**赫夫曼编码** #include <iostream.h> #include <math.h> #include <string.h> #include <stdio.h> #include <stdlib.h> #include <vector> //为了使用vector容器 using namespace std; ///vector属于std命名域，因此使用全局命名域方式 struct Huffman_InformationSource//信源类型 { char InformationSign[10]; //信源符号 double Probability; //概率 char Code[10]; //编码结果 int CodeLength; //码长 }; struct HuffNode //赫夫曼树的节点类型 { char InformationSign[10]; double Probability; HuffNode *LeftSubtree,*middleSubtree,*RightSubtree,*Next; char Code[10]; int CodeLength; }; class CHuffman_3 //三进制赫夫曼编码 { public: CHuffman_3() //初始化 { ISNumber=0; AvageCodeLength=0.0; InformationRate=0.0; CodeEfficiency=0.0; } ~CHuffman_3() { DestroyBTree(HuffTree); } void Huffman_Input(); //输入信息 void Huffman_Sort(); //排序 void Huffman_Tree(); //构造赫夫曼树 void Huffman_Coding(); //生成赫夫曼编码 void Huffman_CodeAnalyzing(); //结果分析 void Huffman_Display(); //显示结果信息 void DestroyBTree(HuffNode *TreePointer); //释放资源 private: vector<Huffman_InformationSource>ISarray; //声明ISarray数组，初始时为空 int ISNumber; //符号个数 double AvageCodeLength; //平均码长 double InformationRate; //信息率 double CodeEfficiency; //编码效率 HuffNode * HuffTree; //赫夫曼树 private: void Huffman_Code(HuffNode *TreePointer); }; //输入信源信息 void CHuffman_3::Huffman_Input() { Huffman_InformationSource temp1={"A",0.40,"",0}; ISarray.push_back(temp1); Huffman_InformationSource temp2={"B",0.18,"",0}; ISarray.push_back(temp2); Huffman_InformationSource temp3={"C",0.10,"",0}; ISarray.push_back(temp3); Huffman_InformationSource temp4={"D",0.10,"",0}; ISarray.push_back(temp4); Huffman_InformationSource temp5={"E",0.07,"",0}; ISarray.push_back(temp5); Huffman_InformationSource temp6={"F",0.06,"",0}; ISarray.push_back(temp6); Huffman_InformationSource temp7={"G",0.05,"",0}; ISarray.push_back(temp7); Huffman_InformationSource temp8={"H",0.04,"",0}; ISarray.push_back(temp8); ISNumber=ISarray.size(); } //按概率“从大到小”排序： void CHuffman_3::Huffman_Sort() { Huffman_InformationSource temp; int i,j; for(i=0;i<ISNumber-1;i++) for(j=i+1;j<ISNumber;j++) if(ISarray[i].Probability<ISarray[j].Probability) { temp=ISarray[i]; ISarray[i]=ISarray[j]; ISarray[j]=temp; } } //基于ISarray数组构造赫夫曼树 void CHuffman_3::Huffman_Tree() { int i; HuffNode *ptr1,*ptr2,*ptr3,*ptr4,*temp1,*temp2; //（1）：基于数组，创建单向链表 ptr1=new HuffNode; strcpy(ptr1->InformationSign,ISarray[0].InformationSign); ptr1->Probability=ISarray[0].Probability; strcpy(ptr1->Code,ISarray[0].Code); ptr1->LeftSubtree=NULL; ptr1->middleSubtree =NULL; ptr1->RightSubtree=NULL; ptr1->Next=NULL; HuffTree=ptr1; //赋给数据成员HuffTree for(i=1;i<ISNumber;i++) { ptr2=new HuffNode; strcpy(ptr2->InformationSign,ISarray[i].InformationSign); ptr2->Probability=ISarray[i].Probability; strcpy(ptr2->Code,ISarray[i].Code); ptr2->LeftSubtree=NULL; ptr2->middleSubtree =NULL; ptr2->RightSubtree=NULL; ptr2->Next=ptr1; ptr1=ptr2; } //结果：链表的表头为数组的最小元素。 HuffTree=ptr1; //使HuffTree指向链表头 //（2）：基于链表，构造赫夫曼树 int k; //树的层次 int s; //需要添加的无用符号的数目。参看教材P140-150。 k=ceil((double)(ISNumber-3)/(3-1));//“3”：表示三进制 //ceil函数：向上取整； //floor函数：向下取整 s=3+k*(3-1)-ISNumber; if(s==1) //第一次取m-s=3-1=2个符号 { //合并概率最小的二个节点ptr1、ptr2，生成一个新节点ptr4： ptr2=ptr1->Next; ptr4=new HuffNode; strcpy(ptr4->InformationSign,"*"); //新节点的符号为“*” ptr4->Probability=ptr1->Probability+ptr2->Probability; //新节点的概率为二者之和 strcpy(ptr4->Code,""); ptr4->LeftSubtree =NULL; ptr4->middleSubtree=ptr1; //最小的节点ptr1成为ptr4的“中”子树，将来赋予码元“1” ptr4->RightSubtree=ptr2; //次小的节点ptr2成为ptr4的“右”子树，将来赋予码元“0” HuffTree=ptr2->Next;//指向下一个节点 //重新排序： temp1=HuffTree; while(temp1&&(ptr4->Probability>temp1->Probability)) { temp2=temp1; temp1=temp1->Next; } ptr4->Next=temp1; //插在当前节点temp1之前 if(temp1==HuffTree) HuffTree=ptr4; else temp2->Next=ptr4; //插在temp2节点之后 ptr1=HuffTree; } while(ptr1->Next) { //合并概率最小的三个节点ptr1、ptr2，生成一个新节点ptr4： ptr2=ptr1->Next; ptr3=ptr2->Next; ptr4=new HuffNode; strcpy(ptr4->InformationSign,"*"); //新节点的符号为“*” ptr4->Probability=ptr1->Probability+ptr2->Probability +ptr3->Probability; //新节点的概率为三者之和 strcpy(ptr4->Code,""); ptr4->LeftSubtree=ptr1; //最小的节点ptr1成为ptr4的“左”子树，将来赋予码元“2” ptr4->middleSubtree=ptr2; //次小的节点ptr2成为ptr4的“中”子树，将来赋予码元“1” ptr4->RightSubtree=ptr3; //次次小的节点ptr3成为ptr4的“右”子树，将来赋予码元“0” HuffTree=ptr3->Next; temp1=HuffTree; while(temp1&&(ptr4->Probability>temp1->Probability)) { temp2=temp1; temp1=temp1->Next; } ptr4->Next=temp1; //插在当前节点temp1之前 if(temp1==HuffTree) HuffTree=ptr4; else temp2->Next=ptr4; //插在temp2节点之后 ptr1=HuffTree; } //释放： ptr1=NULL; ptr2=NULL; ptr3=NULL; ptr4=NULL; temp1=NULL; temp2=NULL; //设置根节点： strcpy(HuffTree->Code,""); HuffTree->CodeLength=0; } //生成赫夫曼码： void CHuffman_3::Huffman_Code(HuffNode *TreePointer) { if (TreePointer == NULL) return; char tempstr[10]=""; if(!TreePointer->LeftSubtree&&!TreePointer->middleSubtree &&!TreePointer->RightSubtree) { for(int i=0;i<ISNumber;i++) if(strcmp(ISarray[i].InformationSign,TreePointer->InformationSign)==0) { strcpy(ISarray[i].Code,TreePointer->Code); ISarray[i].CodeLength=TreePointer->CodeLength; return; } return; } if(TreePointer->LeftSubtree) { //生成左子树编码： strcpy(tempstr,TreePointer->Code); strcat(tempstr,"2"); strcpy(TreePointer->LeftSubtree->Code,tempstr); TreePointer->LeftSubtree->CodeLength=TreePointer->CodeLength+1; Huffman_Code(TreePointer->LeftSubtree); } if(TreePointer->middleSubtree) { //生成中子树编码： strcpy(tempstr,TreePointer->Code); strcat(tempstr,"1"); strcpy(TreePointer->middleSubtree->Code,tempstr); TreePointer->middleSubtree->CodeLength=TreePointer->CodeLength+1; Huffman_Code(TreePointer->middleSubtree); } if(TreePointer->RightSubtree) { //生成右子树编码： strcpy(tempstr,TreePointer->Code); strcat(tempstr,"0"); strcpy(TreePointer->RightSubtree->Code,tempstr); TreePointer->RightSubtree->CodeLength=TreePointer->CodeLength+1; Huffman_Code(TreePointer->RightSubtree); } } void CHuffman_3::Huffman_Coding() { Huffman_Code(HuffTree); } //编码结果分析 void CHuffman_3::Huffman_CodeAnalyzing() { //(1):平均码长 for(int i=0;i<ISNumber;i++) AvageCodeLength+=ISarray[i].Probability*ISarray[i].CodeLength; //(2):信息率 int L=1; //单符号时，L=1 int m=3; //三进制编码，m=3 InformationRate=AvageCodeLength/L*(log(m)/log(2)); //(3):编码效率 double Hx=0; for(int j=0;j<ISNumber;j++) //求信源熵 Hx+=-ISarray[j].Probability*log(ISarray[j].Probability)/log(2); CodeEfficiency=Hx/InformationRate; } //显示结果 void CHuffman_3::Huffman_Display() { cout<<"编码结果："<<endl; for(int i=0;i<ISNumber;i++) { cout<<"\'"<<ISarray[i].InformationSign<<"\'"<<": "<<ISarray[i].Code<<endl; } cout<<endl; cout<<"平均码长："<<AvageCodeLength<<endl<<endl; cout<<"信息率 ："<<InformationRate<<endl<<endl; cout<<"编码效率："<<CodeEfficiency<<endl<<endl; } //释放资源 void CHuffman_3::DestroyBTree(HuffNode *TreePointer) { if (TreePointer!= NULL) { DestroyBTree(TreePointer->LeftSubtree);