数据结构—哈弗曼树的C++程序

#include <iostream> #include <vector> #include <cmath> #include <cstdlib> #define MAXSIZE 100 //最多子叶数 #define MAXCODE 10000 //编码最大长度 using namespace std; typedef struct { char info; //关联字符信息 unsigned int weight; //每个节点的权值 unsigned int parent, lchild, rchild; }HTNode,*HuffmanTree; typedef char **HuffmanCode; //存储哈弗曼编码 void Select(HuffmanTree HT, int j,int &s1,int &s2) {//选择双亲节点为0，并且最小的两个子叶节点 int i=1,m; while(HT[i].parent!=0) i++; //找第一个双亲节点为0的子叶结点 for(s2=s1=i;i<=j;i++) {//确保s1中的权值最小，s2次小 if(HT[i].parent==0 && HT[i].weight<HT[s1].weight) { s2=s1; s1=i; } else if(HT[i].parent==0 && HT[i].weight>=HT[s1].weight && HT[i].weight<=HT[s2].weight) s2=i; while(HT[i].parent==0 && s1==s2) { m=i; m++; while(HT[m].parent!=0) m++; s2=m; } } if(s1>s2) std::swap(s1,s2); } void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n, char *info) {//哈弗曼编码 int i,m; HuffmanTree p; if(n<1) return; m = 2*n-1; free(HT); HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=HT+1,i=1;i<=n;++i,++p,++w,++info) {//初始化所有已存在的子叶信息 p->info=*info; p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0; } for(; i<=m;++i,++p) {//构造所需要的过度根节点 p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; } for(i=n+1;i<=m;++i) {//建立哈弗曼树 int s1,s2; Select(HT,i-1,s1,s2); HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; } //哈弗曼编码 HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); char *cd=(char *)malloc(n*sizeof(char)); cd[n-1]='\0'; for(i=1;i<=n;++i) { int f; unsigned int c; int start=n-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) { if(HT[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; } HC[i]=(char *)malloc((n-start)*sizeof(char)); strcpy(HC[i], &cd[start]); } free(cd); } void CheckCoding(HuffmanTree HT, HuffmanCode HC, char *strcheck, int m) {//查询哈弗曼编码信息 //char *strcopy=new char[MAXCODE]; for(int i=0; i<m; i++) { for(int j=1; HT[j].info != strcheck[i]; j++); cout<<HC[j]; } cout<<endl; } void HuffmanTranslateCoding(HuffmanTree HT, int n,char *c) {//译码过程 int m=2*n-1; int i,j=0; while(c[j]!='\0') { i=m; while(HT[i].lchild && HT[i].rchild) { if(c[j]=='0') i=HT[i].lchild; else if(c[j]=='1') i=HT[i].rchild; j++; } cout<<HT[i].info; } cout<<endl; } void Print(HuffmanTree HT,int n) { int i=1,depth=log(2*n-1)/log(2)+1; //HuffmanTree的最大深度 vector<HTNode> q1,q2; HTNode pnode=HT[2*n-1]; //pnode指向根节点 HTNode temp={'\0',0,0,0,0}; q1.push_back(pnode); while(q1.size()!=0) { for(int j=0;j<q1.size();++j) { pnode=q1[j]; cout<<pnode.weight<<" "; if(j%2==1) cout<<" "; if(pnode.lchild==0) { q2.push_back(temp); q2.push_back(temp); } else { q2.push_back(HT[pnode.lchild]); q2.push_back(HT[pnode.rchild]); } } cout<<endl; ++i; q1=q2; if(pnode.lchild==0) break; q2.clear(); } } /* void Print(HuffmanTree HT,int n) { int j; int m=2*n-1; cout<<" 结点 weight parent lchild rchild"<<endl; for (j=1; j<=m; j++) cout<<" "<<j<<" "<<HT[j].weight<<" "<<HT[j].parent<<" "<<HT[j].lchild<<" "<<HT[j].rchild<<endl; } */ void main() { int i,n,*w,m; char choice; w=new int[MAXSIZE]; char *info; char *strcheck=new char[MAXSIZE]; info=new char[MAXSIZE]; char *ch=new char[MAXSIZE]; HuffmanTree HT=new HTNode[MAXSIZE]; HuffmanTree p=NULL; HuffmanCode HC=NULL; while(choice!='D') { system("cls"); cout<<"欢迎使用南京航空航天大学-080710212-郑勇的哈弗曼树编码系统"<<endl; cout<<"(A)创建哈弗曼树并打印"<<endl; cout<<"(B)使用创建的哈弗曼树编码"<<endl; cout<<"(C)使用创建的哈弗曼树译码"<<endl; cout<<"(D)退出"<<endl; cout<<"输入选项"<<endl; cin>>choice; switch(choice) { case'A': cout<<"输入叶子节点数 n= "; cin>>n; for(i=0; i<n;i++) { cout<<"读入第"<<i+1<<"个叶子结点的权值："; cin>>w[i]; cout<<"读入编码字符: "; cin>>info[i]; } HuffmanCoding(HT, HC, w, n,info); Print(HT,n); system("pause"); break; case'B': cout<<"读入要查询的字符串中字符个数: "; cin>>m; cout<<"读入要编码的字符串: "; cin>>strcheck; CheckCoding(HT,HC,strcheck,m); system("pause"); break; case'C': cout<<"读入编码: "<<endl; cin>>ch; HuffmanTranslateCoding(HT,n,ch); system("pause"); break; case'D': cout<<"欢迎使用"<<endl; break; } } }