Huffcode.rar_数据结构 哈弗曼编码

#include <iostream> using namespace std; int const Maxbit=10; int const Maxvalue=10000; int const Maxleaf=30; int const Maxnode=Maxleaf*2-1; typedef struct { int bit[Maxbit]; int start; }HCodeType; typedef struct { int weight; int parent; int lchild; int rchild; }HNodeType; void HuffmanTree(HNodeType HuffNode[Maxnode],int n) { int i,j,m1,m2,x1,x2; for(i=0;i<2*n-1;i++) { HuffNode[i].weight=0; HuffNode[i].parent=1; HuffNode[i].lchild=-1; HuffNode[i].rchild=-1; } for(i=0;i<n;i++) { cout<<"input the weight of leaf"<<endl; cin>>HuffNode[i].weight; } for(i=0;i<n-1;i++) { m1=m2=Maxvalue; x1=x2=0; for(j=0;j<n+i;j++) { if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1) { m2=m1;x2=x1;m1=HuffNode[j].weight;x1=j; } else if(HuffNode[j].weight<m2&&HuffNode[j].parent==-1) { m2=HuffNode[j].weight;x2=j; } } HuffNode[x1].parent=n+i; HuffNode[x2].parent=n+i; HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight; HuffNode[n+i].lchild=x1; HuffNode[n+i].rchild=x2; } } void main() { HNodeType HuffNode[Maxnode]; HCodeType HuffCode[Maxleaf],cd; int i,j,c,p,n; cout<<"input the number of the leaf"<<endl; cin>>n; HuffmanTree(HuffNode,n); for(i=0;i<n;i++) { cd.start=n-1; c=i; p=HuffNode[c].parent; while(p!=-1) { if(HuffNode[p].lchild==c)cd.bit[cd.start]=0; else cd.bit[cd.start]=1; cd.start++; c=p; p=HuffNode[c].parent; } for(j=cd.start+1;j<n;j++) { HuffCode[i].bit[j]=cd.bit[j]; } HuffCode[i].start=cd.start; } for(i=0;i<n;i++) { cout<<"i "<<i; for(j=HuffCode[i].start+1;j<n;j++) cout<<HuffCode[i].bit[j]<<endl; } }