果子合并（ACM/ICPC训练题）

#include <iostream> #include <stdio.h> #include <malloc.h> #include <string.h> using namespace std; typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef char ** HuffmanCode; int sum=0; void Select(HuffmanTree HT,int i,int &s1,int &s2) //Select sub-function { int j,k=1; while(HT[k].parent!=0) k++; s1=k; for(j=1;j<=i;++j) // Select the first least of HT[].weight if(HT[j].parent==0&&HT[j].weight<HT[s1].weight) s1=j; k=1; while((HT[k].parent!=0||k==s1)) k++; s2=k; for(j=1;j<=i;++j) // Select the second least of HT[].weight if(HT[j].parent==0&&HT[j].weight<HT[s2].weight&&j!=s1) s2=j; } //Select() end void CreetTree(HuffmanTree &HT,int *w,int n) { int i; if(n<=1) return; int m=n*2-1; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); HuffmanTree p; for(p=HT+1,i=1;i<=n;i++,p++,w++) { 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; } } void HuffmanCoding(HuffmanTree HT,int n,HuffmanCode &HC) { int i,c,f; 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 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]='1'; else cd[--start]='0'; sum+=HT[i].weight; } HC[i]=(char *)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); } free(cd); } void main() { HuffmanTree HT; HuffmanCode HC; int w[4]={10,30,15,100}; int n=4; CreetTree(HT,w,n); //创建哈弗曼树 HuffmanCoding(HT,n,HC); for(int j=1;j<=n*2-1;j++) cout<<HT[j].weight<<"\t" <<HT[j].lchild<<"\t" <<HT[j].rchild<<"\t" <<HT[j].parent<<endl; for(int i=1;i<=4;i++) cout<<HC[i]<<'\t'; cout<<endl; cout<<"将果子合并为一堆的工作量最小为："<<sum<<endl; }